論文の概要: Optimal Graph Clustering without Edge Density Signals

• arxiv url: http://arxiv.org/abs/2510.21669v1
• Date: Fri, 24 Oct 2025 17:24:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 09:00:15.556932
• Title: Optimal Graph Clustering without Edge Density Signals
• Title（参考訳）: エッジ密度信号のない最適グラフクラスタリング
• Authors: Maximilien Dreveton, Elaine Siyu Liu, Matthias Grossglauser, Patrick Thiran,
• Abstract要約: 本稿では,Popularity-Adjusted Block Model(PABM)に基づくグラフクラスタリングの理論的限界を確立する。 本研究の主な貢献は,PABMによるクラスタリングにおける最適誤差率の評価である。 合成データセットと実データセットの両方に関する数値実験により、$k2$固有ベクトルを組み込んだスペクトルクラスタリングアルゴリズムが従来のスペクトルアプローチより優れていることを確認した。
• 参考スコア（独自算出の注目度）: 11.198418635553976
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper establishes the theoretical limits of graph clustering under the Popularity-Adjusted Block Model (PABM), addressing limitations of existing models. In contrast to the Stochastic Block Model (SBM), which assumes uniform vertex degrees, and to the Degree-Corrected Block Model (DCBM), which applies uniform degree corrections across clusters, PABM introduces separate popularity parameters for intra- and inter-cluster connections. Our main contribution is the characterization of the optimal error rate for clustering under PABM, which provides novel insights on clustering hardness: we demonstrate that unlike SBM and DCBM, cluster recovery remains possible in PABM even when traditional edge-density signals vanish, provided intra- and inter-cluster popularity coefficients differ. This highlights a dimension of degree heterogeneity captured by PABM but overlooked by DCBM: local differences in connectivity patterns can enhance cluster separability independently of global edge densities. Finally, because PABM exhibits a richer structure, its expected adjacency matrix has rank between $k$ and $k^2$, where $k$ is the number of clusters. As a result, spectral embeddings based on the top $k$ eigenvectors may fail to capture important structural information. Our numerical experiments on both synthetic and real datasets confirm that spectral clustering algorithms incorporating $k^2$ eigenvectors outperform traditional spectral approaches.
• Abstract（参考訳）: 本稿では,Popularity-Adjusted Block Model (PABM) に基づくグラフクラスタリングの理論的限界を確立する。 均一頂点度を仮定するStochastic Block Model (SBM)や、クラスタ間の均一度補正を行うDegree-Corrected Block Model (DCBM)とは対照的に、PABMはクラスタ内およびクラスタ間接続に対する異なる人気パラメータを導入している。 SBMやDCBMとは異なり、従来のエッジ密度信号が消えても、クラスタ内およびクラスタ間人気係数が異なる場合でも、クラスタ回復はPABMで可能であることを示す。 接続パターンの局所的な差異は、グローバルエッジ密度とは無関係にクラスタ分離性を高めることができる。 最後に、PABMはよりリッチな構造を示すため、期待される隣接行列は、$k$と$k^2$の間のランクを持ち、$k$はクラスタの数である。 その結果、トップ$k$固有ベクトルに基づくスペクトル埋め込みは重要な構造情報の取得に失敗する可能性がある。 合成データと実データの両方に関する数値実験により、$k^2$固有ベクトルを組み込んだスペクトルクラスタリングアルゴリズムが従来のスペクトル手法より優れていることを確認した。

関連論文リスト

• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• MADCluster: Model-agnostic Anomaly Detection with Self-supervised Clustering Network [0.7373617024876725]
  自己教師付きクラスタリングを利用したモデルに依存しない異常検出フレームワークMADClusterを提案する。 中心となる考え方は、通常のパターンデータを'単一クラスタ'にクラスタ化すると同時に、クラスタセンタを学習し、このセンタに近いデータをマッピングすることです。 4つの時系列ベンチマークデータセットの実験では、MADClusterを適用することで、比較モデルの全体的なパフォーマンスが向上することが示された。
  論文  参考訳（メタデータ） (2025-05-22T04:50:44Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• Spectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models [22.421702511126373]
  ブロックモデルに対する統計的推測を利用して、有向グラフに対するスペクトルクラスタリングアルゴリズムの開発を導く。 我々は、スペクトル緩和の誤クラスタリング誤差に関する理論上界を確立し、この緩和に基づいて、有向グラフに対する新しい自己適応スペクトルクラスタリング法を導入する。
  論文  参考訳（メタデータ） (2024-03-28T15:47:13Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  半負のテンソル因子分解(Semi-NTF)に基づく新しいマルチビュークラスタリングを開発する。 本モデルは、ビュー間の関係を直接考慮し、ビュー間の補完情報を利用する。 さらに,提案手法の最適化アルゴリズムを提案し,そのアルゴリズムが常に定常KKT点に収束することを数学的に証明する。
  論文  参考訳（メタデータ） (2023-03-29T14:54:19Z)
• Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data [16.153709556346417]
  クラスタリングは広くデプロイされた学習ツールである。 iLA-SDPはEMよりも感度が低く、高次元データでは安定である。
  論文  参考訳（メタデータ） (2022-09-29T21:03:13Z)
• A class of network models recoverable by spectral clustering [11.635152494912003]
  ブロックモデル (sbm) で使用されるアルゴリズムがブロックモデルのより広いクラスで動作することを示す。 このモデルのクラスを指定するのに必要な自由なパラメータを明確に紹介し、その結果、このモデルクラスのリカバリエラーを制御するパラメータをより明確に公開します。
  論文  参考訳（メタデータ） (2021-04-21T04:22:18Z)

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

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