論文の概要: Regularized spectral methods for clustering signed networks
- arxiv url: http://arxiv.org/abs/2011.01737v1
- Date: Tue, 3 Nov 2020 14:40:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 04:36:53.815688
- Title: Regularized spectral methods for clustering signed networks
- Title(参考訳): クラスタリング符号ネットワークのための正規化スペクトル法
- Authors: Mihai Cucuringu, Apoorv Vikram Singh, D\'eborah Sulem, Hemant Tyagi
- Abstract要約: 署名付きグラフにおける$k$-wayクラスタリングの問題について検討する。
我々は,SPONGE と Signed Laplacian の正規化バージョンに対して,[CDGT 2019] の2つの面で結果に基づいて構築する。
- 参考スコア(独自算出の注目度): 7.547306670351599
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of $k$-way clustering in signed graphs. Considerable
attention in recent years has been devoted to analyzing and modeling signed
graphs, where the affinity measure between nodes takes either positive or
negative values. Recently, Cucuringu et al. [CDGT 2019] proposed a spectral
method, namely SPONGE (Signed Positive over Negative Generalized Eigenproblem),
which casts the clustering task as a generalized eigenvalue problem optimizing
a suitably defined objective function. This approach is motivated by social
balance theory, where the clustering task aims to decompose a given network
into disjoint groups, such that individuals within the same group are connected
by as many positive edges as possible, while individuals from different groups
are mainly connected by negative edges. Through extensive numerical
simulations, SPONGE was shown to achieve state-of-the-art empirical
performance. On the theoretical front, [CDGT 2019] analyzed SPONGE and the
popular Signed Laplacian method under the setting of a Signed Stochastic Block
Model (SSBM), for $k=2$ equal-sized clusters, in the regime where the graph is
moderately dense.
In this work, we build on the results in [CDGT 2019] on two fronts for the
normalized versions of SPONGE and the Signed Laplacian. Firstly, for both
algorithms, we extend the theoretical analysis in [CDGT 2019] to the general
setting of $k \geq 2$ unequal-sized clusters in the moderately dense regime.
Secondly, we introduce regularized versions of both methods to handle sparse
graphs -- a regime where standard spectral methods underperform -- and provide
theoretical guarantees under the same SSBM model. To the best of our knowledge,
regularized spectral methods have so far not been considered in the setting of
clustering signed graphs. We complement our theoretical results with an
extensive set of numerical experiments on synthetic data.
- Abstract(参考訳): 署名付きグラフにおける$k$-wayクラスタリングの問題について検討する。
近年の注目は、ノード間の親和性尺度が正または負の値を取る符号付きグラフの分析とモデル化に向けられている。
最近はCucuringuなど。
そこで, [CDGT 2019] はSPONGE (Signed Positive over Negative Generalized Eigenproblem) というスペクトル法を提案した。
このアプローチは、クラスタ化タスクが所定のネットワークを非結合グループに分解することを目的としている社会バランス理論によって動機付けられており、同じグループ内の個人は可能な限り多くの正のエッジで接続され、異なるグループの個人は主に負のエッジによって接続される。
広範な数値シミュレーションにより、SPONGEは最先端の実証的な性能を達成できた。
理論的な面では、[cdgt 2019]はグラフが適度に密集している状態において、ssbm(signed stochastic block model)をk=2$等サイズのクラスタに設定して、スポンジと一般的なラプラシアン法を解析した。
本研究では,SPONGE の正規化バージョンと Signed Laplacian の2つの面で [CDGT 2019] の結果に基づいて構築する。
まず、両方のアルゴリズムに対して、[CDGT 2019]の理論的解析を、適度に高密度な状態にある$k \geq 2$不等サイズのクラスターの一般的な設定に拡張する。
第二に、スパースグラフを扱うための2つの手法の正規化バージョン(標準スペクトル法が性能が劣る体制)を導入し、同じSSBMモデルの下で理論的保証を提供する。
我々の知る限りでは、クラスタリング符号グラフの設定において正規化スペクトル法は検討されていない。
我々は, 理論結果を合成データに関する広範な数値実験で補完する。
関連論文リスト
- Understanding Heterophily for Graph Neural Networks [46.5811999777132]
グラフニューラルネットワーク(GNN)における異方性パターンの影響に関する理論的理解について述べる。
分離性ゲインは、$l$の近隣分布の正規化距離によって決定されることを示す。
合成データと実世界のデータの両方の実験により、我々の理論の有効性が検証された。
論文 参考訳(メタデータ) (2024-01-17T11:01:28Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳(メタデータ) (2023-08-13T18:12:28Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳(メタデータ) (2023-06-18T08:46:06Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳(メタデータ) (2023-05-28T15:33:24Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳(メタデータ) (2023-05-12T11:27:20Z) - Inhomogeneous graph trend filtering via a l2,0 cardinality penalty [9.485385888848489]
グラフ信号の断片的スムーズさを推定するために,$ell_2,0$-norm Penalized Graph Trend Filtering (GTF) モデルを提案する。
提案したGTFモデルは,エッジセットが大きいデータセットに対して,既存のモデルよりも効率的に解けることを示す。
論文 参考訳(メタデータ) (2023-04-11T13:46:59Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳(メタデータ) (2022-05-24T00:03:25Z) - On consistency of constrained spectral clustering under
representation-aware stochastic block model [20.6072287343024]
制約付きスペクトルクラスタリングは、与えられたテクスト類似性グラフ$mathcalG$でバランスの取れたクラスタを見つけることを目的として研究される。
この環境では、スペクトルクラスタリングの非正規化および正規化の変種を開発する。
これらのアルゴリズムは$mathcalR$を使用して、提案された制約をほぼ満たした$mathcalG$のクラスタを見つける。
論文 参考訳(メタデータ) (2022-03-03T20:41:14Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳(メタデータ) (2020-08-31T08:41:20Z) - Strong Consistency, Graph Laplacians, and the Stochastic Block Model [1.2891210250935143]
ブロックモデルを学ぶために,古典的な2段階のスペクトルクラスタリングの性能をグラフラプラシアンを用いて検討する。
スペクトルクラスタリングは,情報理論の限界に合致する条件下で,植民コミュニティ構造を正確に復元できることを示す。
論文 参考訳(メタデータ) (2020-04-21T07:16:46Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく
我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。
EGAEは1つのエンコーダと2つのデコーダで構成される。
論文 参考訳(メタデータ) (2020-02-20T09:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。