論文の概要: 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モデルの下で理論的保証を提供する。 我々の知る限りでは、クラスタリング符号グラフの設定において正規化スペクトル法は検討されていない。 我々は, 理論結果を合成データに関する広範な数値実験で補完する。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Maximum Likelihood Estimation on Stochastic Blockmodels for Directed Graph Clustering [22.421702511126373]
  我々は、有向ブロックモデルにおいて、基盤となるコミュニティを推定するものとしてクラスタリングを定式化する。 本稿では,2つの効率的かつ解釈可能な有向クラスタリングアルゴリズム,スペクトルクラスタリングアルゴリズム,半定値プログラミングに基づくクラスタリングアルゴリズムを紹介する。
  論文  参考訳（メタデータ） (2024-03-28T15:47:13Z)
• Robustness for Spectral Clustering of General Graphs under Local Differential Privacy [2.4447259440166302]
  ソーシャルネットワークはブロックモデル(SBM)から派生していないと我々は主張する。 私たちの主な焦点は、エッジフリップメソッド -- ローカルな差分プライバシーを保護するための一般的なテクニック -- にあります。 クラスタリングの結果は、SBMから生成される密集グラフやクラスタリンググラフに対して安定しているが、一般に、スペクトルクラスタリングは特定の密集グラフやクラスタリンググラフに対して非常に不規則な結果をもたらす可能性があることを示す。
  論文  参考訳（メタデータ） (2023-09-13T10:23:29Z)
• 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)
• 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)

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

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