論文の概要: Robust Correlation Clustering with Asymmetric Noise

• arxiv url: http://arxiv.org/abs/2110.08385v1
• Date: Fri, 15 Oct 2021 21:47:27 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-19 20:50:46.123288
• Title: Robust Correlation Clustering with Asymmetric Noise
• Title（参考訳）: 非対称雑音によるロバスト相関クラスタリング
• Authors: Jimit Majmudar, Stephen Vavasis
• Abstract要約: 相関クラスタリング(英語版)はグラフクラスタリングの定式化であり、(1) ノード間の類似性/異性度を示すエッジウェイトを持つ符号付きグラフを入力とし、(2) 入力グラフ内のクラスタ数を事前に見積もる必要がない。 グラフノードの特徴ベクトル/埋め込みの生成に基づく新しいグラフ生成モデルNode Factors Model (NFM)を提案する。
• 参考スコア（独自算出の注目度）: 3.8073142980733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph clustering problems typically aim to partition the graph nodes such that two nodes belong to the same partition set if and only if they are similar. Correlation Clustering is a graph clustering formulation which: (1) takes as input a signed graph with edge weights representing a similarity/dissimilarity measure between the nodes, and (2) requires no prior estimate of the number of clusters in the input graph. However, the combinatorial optimization problem underlying Correlation Clustering is NP-hard. In this work, we propose a novel graph generative model, called the Node Factors Model (NFM), which is based on generating feature vectors/embeddings for the graph nodes. The graphs generated by the NFM contain asymmetric noise in the sense that there may exist pairs of nodes in the same cluster which are negatively correlated. We propose a novel Correlation Clustering algorithm, called \anormd, using techniques from semidefinite programming. Using a combination of theoretical and computational results, we demonstrate that $\texttt{$\ell_2$-norm-diag}$ recovers nodes with sufficiently strong cluster membership in graph instances generated by the NFM, thereby making progress towards establishing the provable robustness of our proposed algorithm.
• Abstract（参考訳）: グラフクラスタリングの問題は通常、2つのノードが同じパーティションセットに属するようにグラフノードを分割することを目的としている。 相関クラスタリングは、(1)ノード間の類似性/異質性指標を表す辺重み付き符号付きグラフを入力として、(2)入力グラフのクラスタ数を事前に見積もる必要はない、というグラフクラスタリングの定式化である。 しかし、相関クラスタリングの根底にある組合せ最適化問題はNPハードである。 本研究では,グラフノードの特徴ベクトル/埋め込みの生成に基づく新しいグラフ生成モデルであるノード因子モデル(NFM)を提案する。 NFMが生成したグラフは、負の相関関係を持つ同一クラスタに一対のノードが存在するという意味で非対称ノイズを含む。 半定義型プログラミングの手法を用いて,新しい相関クラスタリングアルゴリズムである \anormdを提案する。 理論と計算結果の組み合わせを用いて, nfm が生成するグラフインスタンスにおいて,$\texttt{$\ell_2$-norm-diag}$ が十分なクラスタメンバシップを持つノードを復元し,提案アルゴリズムの頑健性を確立するための一歩を踏み出した。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。 我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。 本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
  論文  参考訳（メタデータ） (2023-12-07T06:19:39Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• 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)
• ClusterFuG: Clustering Fully connected Graphs by Multicut [20.254912065749956]
  密マルチカットでは、クラスタリングの目的はノード特徴ベクトルの内部積として分解形式で与えられる。 我々は、密集した環境でのマルチカットのための古典的欲求アルゴリズムの書き直し方法と、より効率とソリューションの品質を高めるためにそれらをどう修正するかを示す。
  論文  参考訳（メタデータ） (2023-01-28T11:10:50Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。 アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。 理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
  論文  参考訳（メタデータ） (2021-11-12T07:08:13Z)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。 出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。 本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
  論文  参考訳（メタデータ） (2021-07-27T19:47:53Z)
• Seeing All From a Few: Nodes Selection Using Graph Pooling for Graph Clustering [37.68977275752782]
  ノイズの多いエッジとグラフのノードは、クラスタリング結果を悪化させる可能性がある。 ノイズの多いノードやエッジに対するグラフクラスタリングの堅牢性を改善するために,新しいデュアルグラフ埋め込みネットワーク(DGEN)を提案する。 3つのベンチマークグラフデータセットの実験は、いくつかの最先端アルゴリズムと比較して優位性を示す。
  論文  参考訳（メタデータ） (2021-04-30T06:51:51Z)

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

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