論文の概要: Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models

• arxiv url: http://arxiv.org/abs/2403.19516v2
• Date: Tue, 03 Jun 2025 17:00:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 01:42:08.849362
• Title: Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models
• Title（参考訳）: 確率ブロックモデルに基づく近似推定による直接グラフのスペクトルクラスタリング
• Authors: Ning Zhang, Xiaowen Dong, Mihai Cucuringu,
• Abstract要約: ブロックモデルに対する統計的推測を利用して、有向グラフに対するスペクトルクラスタリングアルゴリズムの開発を導く。 我々は、スペクトル緩和の誤クラスタリング誤差に関する理論上界を確立し、この緩和に基づいて、有向グラフに対する新しい自己適応スペクトルクラスタリング法を導入する。
• 参考スコア（独自算出の注目度）: 22.421702511126373
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph clustering is a fundamental task in unsupervised learning with broad real-world applications. While spectral clustering methods for undirected graphs are well-established and guided by a minimum cut optimization consensus, their extension to directed graphs remains relatively underexplored due to the additional complexity introduced by edge directions. In this paper, we leverage statistical inference on stochastic block models to guide the development of a spectral clustering algorithm for directed graphs. Specifically, we study the maximum likelihood estimation under a widely used directed stochastic block model, and derive a global objective function that aligns with the underlying community structure. We further establish a theoretical upper bound on the misclustering error of its spectral relaxation, and based on this relaxation, introduce a novel, self-adaptive spectral clustering method for directed graphs. Extensive experiments on synthetic and real-world datasets demonstrate significant performance gains over existing baselines.
• Abstract（参考訳）: グラフクラスタリングは、広い現実世界のアプリケーションで教師なし学習を行う上で、基本的なタスクである。 無向グラフのスペクトルクラスタリング法は、最小カット最適化のコンセンサスによって十分に確立され、ガイドされているが、エッジ方向によってもたらされる複雑さにより、有向グラフへの拡張は比較的未探索のままである。 本稿では,確率ブロックモデルに対する統計的推測を利用して,有向グラフに対するスペクトルクラスタリングアルゴリズムの開発を導く。 具体的には、広く使われている有向確率ブロックモデルに基づいて最大推定を行い、基礎となるコミュニティ構造と整合する大域的目的関数を導出する。 さらに、スペクトル緩和の誤クラスタリング誤差に関する理論上界を確立し、この緩和に基づいて、有向グラフに対する新しい自己適応スペクトルクラスタリング法を導入する。 合成および実世界のデータセットに関する大規模な実験は、既存のベースラインよりも大きなパフォーマンス向上を示している。

関連論文リスト

• Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective [52.662463893268225]
  自己教師付きヘテロジニアスグラフ学習(SHGL)は様々なシナリオにおいて有望な可能性を示している。 既存のSHGLメソッドには2つの大きな制限がある。 ランクと二重整合性制約によって強化された新しいフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-12-01T09:33:20Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  グラフ畳み込みネットワーク(GCN)は、グラフベースのクラスタリングを改善する上で大きな可能性を秘めている。 モデルはGCNを適用するために初期グラフを事前に推定する。 一般的なデータクラスタリングには,Deep Contrastive Graph Learning (DCGL)モデルが提案されている。
  論文  参考訳（メタデータ） (2024-02-25T07:03:37Z)
• A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning [33.05104609131764]
  オープンワールド半教師あり学習は、未知のデータに既知のクラスと新しいクラスの両方を推定することを目的としている。 本稿では,オープンワールド設定に適したグラフ理論フレームワークを定式化する。 我々のグラフ理論フレームワークは実用的なアルゴリズムを照らし、保証を提供する。
  論文  参考訳（メタデータ） (2023-11-06T21:15:09Z)
• Distributed Linear Regression with Compositional Covariates [5.085889377571319]
  大規模合成データにおける分散スパースペナル化線形ログコントラストモデルに着目する。 2つの異なる制約凸最適化問題を解くために2つの分散最適化手法を提案する。 分散化されたトポロジでは、通信効率の高い正規化推定値を得るための分散座標ワイド降下アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2023-10-21T11:09:37Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  半負のテンソル因子分解(Semi-NTF)に基づく新しいマルチビュークラスタリングを開発する。 本モデルは、ビュー間の関係を直接考慮し、ビュー間の補完情報を利用する。 さらに,提案手法の最適化アルゴリズムを提案し,そのアルゴリズムが常に定常KKT点に収束することを数学的に証明する。
  論文  参考訳（メタデータ） (2023-03-29T14:54:19Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Generalized Spectral Clustering for Directed and Undirected Graphs [4.286327408435937]
  本稿では、有向グラフと無向グラフの両方に対処できる一般化スペクトルクラスタリングフレームワークを提案する。 我々のアプローチは、グラフ関数の一般化されたディリクレエネルギーとして導入する新しい函数のスペクトル緩和に基づいている。 また、グラフ上の自然ランダムウォークの反復パワーから構築された正規化尺度の実用的なパラメトリゼーションを提案する。
  論文  参考訳（メタデータ） (2022-03-07T09:18:42Z)
• Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
  カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。 フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
  論文  参考訳（メタデータ） (2022-03-02T20:07:04Z)
• A Modular Framework for Centrality and Clustering in Complex Networks [0.6423239719448168]
  本稿では,集中度とクラスタリングという2つの重要なネットワーク解析手法について検討する。 クラスタリングには情報フローベースのモデルが採用されている。 我々のクラスタリングは、エッジウェイトとノードの度合いの異なる解釈と相互作用と同様に、エッジ指向性に対応する柔軟性を自然に継承する。
  論文  参考訳（メタデータ） (2021-11-23T03:01:29Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)
• Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
  D$次元データポイントの分布から主グラフを学習するために,Mixture Modelsの正規化バージョンを提案する。 モデルのパラメータは期待最大化手順によって反復的に推定される。
  論文  参考訳（メタデータ） (2021-06-16T18:00:02Z)
• Spatially Coherent Clustering Based on Orthogonal Nonnegative Matrix Factorization [0.0]
  本稿では,クラスタメンバシップ行列の総変動(TV)正規化手順に基づく作業クラスタリングモデルを紹介する。 マトリックス支援レーザー脱離イオン化イメージング測定から得られた超スペクトルデータセット上の提案手法をすべて数値的に評価する。
  論文  参考訳（メタデータ） (2021-04-25T23:40:41Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。 新規な構造化融合正規化に基づく一般グラフ推定器を提案する。 提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T04:42:32Z)
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit [10.8145995157397]
  高階クラスタリングは、マルチウェイデータセットの異種サブ構造を特定することを目的とする。 非計算と問題の性質は統計学と統計学の両方に重大な課題をもたらす。
  論文  参考訳（メタデータ） (2020-12-18T00:48:27Z)
• Clustering Ensemble Meets Low-rank Tensor Approximation [50.21581880045667]
  本稿では,複数のクラスタリングを組み合わせ,個々のクラスタリングよりも優れたパフォーマンスを実現するクラスタリングアンサンブルの問題について検討する。 本稿では,この問題をグローバルな視点から解くために,新しい低ランクテンソル近似法を提案する。 7つのベンチマークデータセットを用いた実験の結果,提案手法は12の最先端手法と比較して,クラスタリング性能のブレークスルーを達成した。
  論文  参考訳（メタデータ） (2020-12-16T13:01:37Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。 本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。 我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
  論文  参考訳（メタデータ） (2020-08-31T08:41:20Z)
• Robust spectral clustering using LASSO regularization [0.0]
  本稿では,ブロックモデルと密接な関係を持つ新しいランダムモデルを用いて,スペクトルクラスタリングの一種である1スペクトルクラスタリングを提案する。 その目標は、グラフの自然な構造を明らかにする1の最小化問題のスパース固有基底解を促進することである。
  論文  参考訳（メタデータ） (2020-04-08T07:12:56Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく 我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。 EGAEは1つのエンコーダと2つのデコーダで構成される。
  論文  参考訳（メタデータ） (2020-02-20T09:53:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。