論文の概要: MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion
- arxiv url: http://arxiv.org/abs/2312.04067v1
- Date: Thu, 7 Dec 2023 06:19:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-08 16:07:25.267889
- Title: MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion
- Title（参考訳）: MeanCut:パスベースの類似性とDregree Descent Criterionによるグレディ最適化グラフクラスタリング
- Authors: Dehua Peng, Zhipeng Gui, Huayi Wu
- Abstract要約: スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
- 参考スコア（独自算出の注目度）: 0.6906005491572401
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As the most typical graph clustering method, spectral clustering is popular
and attractive due to the remarkable performance, easy implementation, and
strong adaptability. Classical spectral clustering measures the edge weights of
graph using pairwise Euclidean-based metric, and solves the optimal graph
partition by relaxing the constraints of indicator matrix and performing
Laplacian decomposition. However, Euclidean-based similarity might cause skew
graph cuts when handling non-spherical data distributions, and the relaxation
strategy introduces information loss. Meanwhile, spectral clustering requires
specifying the number of clusters, which is hard to determine without enough
prior knowledge. In this work, we leverage the path-based similarity to enhance
intra-cluster associations, and propose MeanCut as the objective function and
greedily optimize it in degree descending order for a nondestructive graph
partition. This algorithm enables the identification of arbitrary shaped
clusters and is robust to noise. To reduce the computational complexity of
similarity calculation, we transform optimal path search into generating the
maximum spanning tree (MST), and develop a fast MST (FastMST) algorithm to
further improve its time-efficiency. Moreover, we define a density gradient
factor (DGF) for separating the weakly connected clusters. The validity of our
algorithm is demonstrated by testifying on real-world benchmarks and
application of face recognition. The source code of MeanCut is available at
https://github.com/ZPGuiGroupWhu/MeanCut-Clustering.
- Abstract（参考訳）: 最も典型的なグラフクラスタリング法として、スペクトルクラスタリングは、顕著な性能、実装が容易で、適応性が強いため、人気があり魅力的である。
古典的なスペクトルクラスタリングは、ペアワイズユークリッド計量を用いてグラフのエッジウェイトを測定し、指標行列の制約を緩和し、ラプラシアン分解を実行することで最適なグラフ分割を解く。
しかしながら、ユークリッドに基づく類似性は非球面データ分布を扱う際に歪グラフ切断を引き起こす可能性があり、緩和戦略は情報損失をもたらす。
一方、スペクトルクラスタリングでは、十分な事前知識なしでは判断が難しいクラスタの数を指定する必要がある。
本研究では,経路に基づく類似性を活用してクラスタ内の関連性を高めるとともに,MeanCut を目的関数として提案し,非破壊グラフ分割の次々に下降順に最適化する。
このアルゴリズムは任意の形状のクラスタを識別でき、ノイズにロバストである。
類似度計算の計算複雑性を低減するため,最適経路探索を最大スパンニングツリー(MST)の生成に変換するとともに,その時間効率を向上する高速MSTアルゴリズムを開発した。
さらに、弱い連結クラスタを分離するための密度勾配係数(DGF)を定義する。
本アルゴリズムの妥当性は,実世界のベンチマークと顔認識の応用によって実証される。
MeanCutのソースコードはhttps://github.com/ZPGuiGroupWhu/MeanCut-Clusteringで入手できる。
関連論文リスト
- Interpretable Multi-View Clustering Based on Anchor Graph Tensor Factorization [64.00146569922028]
アンカーグラフの分解に基づくマルチビュークラスタリング法では,分解行列に対する適切なクラスタ解釈性が欠如している。
複数のビューからアンカーグラフを合成するアンカーグラフテンソルを分解するために、非負のテンソル因子分解を用いることにより、この制限に対処する。
論文 参考訳（メタデータ） (2024-04-01T03:23:55Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12:28Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - 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) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。
本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。
提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
論文 参考訳（メタデータ） (2021-08-15T13:14:28Z) - Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
スペクトルクラスタリングにインスパイアされた手法として,ランダムな次元還元プロジェクションから得られた行列スケッチを用いる。
提案手法は,完全に動的なブロックモデルストリームが与えられた場合,性能の高いクラスタリング結果が得られる埋め込みを生成する。
また、ブロックモデルパラメータがその後の埋め込みの必要次元に与える影響についても検討し、ランダムなプロジェクションが分散メモリにおけるグラフクラスタリングの性能を大幅に改善できることを示す。
論文 参考訳（メタデータ） (2020-07-24T17:38:04Z) - Local Graph Clustering with Network Lasso [90.66817876491052]
局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。
nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
論文 参考訳（メタデータ） (2020-04-25T17:52:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。