論文の概要: Effective and Scalable Clustering on Massive Attributed Graphs

• arxiv url: http://arxiv.org/abs/2102.03826v1
• Date: Sun, 7 Feb 2021 15:50:28 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-09 15:20:41.966653
• Title: Effective and Scalable Clustering on Massive Attributed Graphs
• Title（参考訳）: 大規模グラフ上の効率的かつスケーラブルなクラスタリング
• Authors: Renchi Yang, Jieming Shi, Yin Yang, Keke Huang, Shiqi Zhang and Xiaokui Xiao
• Abstract要約: 本稿では,k-AGCに対する効果的なアプローチであるACMinを提案する。 ACMinは、グランドトラストラベルに対して測定された結果の質において、競争相手を一貫して上回り、桁違いに高速である。 特に、265.2百万のエッジと11億の属性値を持つMicrosoft Academic Knowledge Graphデータセットでは、ACMinは1つのCPUコアを使用して1.68時間以内に5-AGCの高品質な結果を出力する。
• 参考スコア（独自算出の注目度）: 25.161619807810215
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a graph G where each node is associated with a set of attributes, and a parameter k specifying the number of output clusters, k-attributed graph clustering (k-AGC) groups nodes in G into k disjoint clusters, such that nodes within the same cluster share similar topological and attribute characteristics, while those in different clusters are dissimilar. This problem is challenging on massive graphs, e.g., with millions of nodes and billions of edges. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality. In this paper, we propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. The main contributions of ACMin are twofold: (i) a novel formulation of the k-AGC problem based on an attributed multi-hop conductance quality measure custom-made for this problem setting, which effectively captures cluster coherence in terms of both topological proximities and attribute similarities, and (ii) a linear-time optimization solver that obtains high-quality clusters iteratively, based on efficient matrix operations such as orthogonal iterations, an alternative optimization approach, as well as an initialization technique that significantly speeds up the convergence of ACMin in practice. Extensive experiments, comparing 11 competitors on 6 real datasets, demonstrate that ACMin consistently outperforms all competitors in terms of result quality measured against ground-truth labels, while being up to orders of magnitude faster. In particular, on the Microsoft Academic Knowledge Graph dataset with 265.2 million edges and 1.1 billion attribute values, ACMin outputs high-quality results for 5-AGC within 1.68 hours using a single CPU core, while none of the 11 competitors finish within 3 days.
• Abstract（参考訳）: 各ノードが属性の集合に関連付けられているグラフGと、出力クラスタの数を指定するパラメータkと、Gのk属性グラフクラスタリング(k-AGC)は、同じクラスタ内のノードが同じ位相特性と属性特性を共有しているように、G内のノードをk非結合クラスタにグループ化する。 この問題は、例えば数百万のノードと数十億のエッジを持つ巨大なグラフでは難しい。 このようなグラフの場合、既存のソリューションは、非常に高いコストを負うか、あるいは妥協された品質でクラスタリング結果を生成する。 In this paper, we propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. The main contributions of ACMin are twofold: (i) a novel formulation of the k-AGC problem based on an attributed multi-hop conductance quality measure custom-made for this problem setting, which effectively captures cluster coherence in terms of both topological proximities and attribute similarities, and (ii) a linear-time optimization solver that obtains high-quality clusters iteratively, based on efficient matrix operations such as orthogonal iterations, an alternative optimization approach, as well as an initialization technique that significantly speeds up the convergence of ACMin in practice. 6つの実際のデータセット上の11の競合他社を比較した広範な実験は、ACMinが地上トラスラベルに対して測定された結果品質の点ですべての競合他社を一貫して上回ることを示しています。 特に、265.2百万のエッジと11億の属性値を持つMicrosoft Academic Knowledge Graphデータセットでは、ACMinは1つのCPUコアを使用して1.68時間以内に5-AGCの高品質な結果を出力する。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation [14.327262299413789]
  ANCKAは、属性グラフクラスタリング(AGC)、属性多重グラフクラスタリング(AMGC)、属性ハイパーグラフクラスタリング(AHC)が可能な汎用属性ネットワーククラスタリングフレームワークとして開発されている。 我々は,提案手法を8つの属性付きハイパーグラフ上の19の競合,6つの属性付きグラフ上の16の競合,および3つの属性付き多重グラフ上の16の競合と比較した。
  論文  参考訳（メタデータ） (2024-08-10T06:59:51Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
  グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。 既存のGCメソッドは複雑な最適化プロセスに悩まされており、過剰な計算資源を必要とする。 我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。 CGCはより効率的な凝縮プロセスで最先端の性能を達成する。
  論文  参考訳（メタデータ） (2024-05-22T14:57:09Z)
• Effective Clustering on Large Attributed Bipartite Graphs [10.701751248623863]
  分散二部グラフ(ABG)は、2つの異種ノード間の相互作用を記述するための表現型データモデルである。 このようなグラフに設定された対象ノードを(k-ABGCと呼ばれる) k 個の非連結クラスタに分割すると、様々な領域で広く使われるようになる。 しかし、k-ABGCに対する既存の解のほとんどは、属性情報を見渡すか、二部グラフ構造を正確に捉えないかのいずれかである。 我々は,複数の実データセット上でのスーパーブクラスタリング性能を実現する,k-ABGCの効率的かつ効率的なアプローチであるTPOを提案する。
  論文  参考訳（メタデータ） (2024-05-20T09:58:27Z)
• Cluster-based Graph Collaborative Filtering [55.929052969825825]
  グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。 既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。 クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
  論文  参考訳（メタデータ） (2024-04-16T07:05:16Z)
• Efficient High-Quality Clustering for Large Bipartite Graphs [7.533043289759316]
  k-Bipartite Graph Clustering (k-BGC) は、2部グラフにセットされたターゲット頂点を k 個の非結合クラスタに分割する。 クラスタリングの品質は、ソーシャルネットワーク分析、レコメンデーションシステム、テキストマイニング、バイオインフォマティクスといった様々な応用において、k-BGCの有用性にとって重要である。 本稿では,大規模二部グラフ上での最先端性能を実現する2つの効率的なk-BGCソリューション,HOPEとHOPE+を提案する。
  論文  参考訳（メタデータ） (2023-12-28T09:50:56Z)
• Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
  グラフクラスタリングフレームワーク textitPCon を開発した。 既存のソリューションの多くをフレームワークに還元できることを示します。 本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
  論文  参考訳（メタデータ） (2022-11-22T12:45:27Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。 SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。 OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
  論文  参考訳（メタデータ） (2021-10-15T03:25:28Z)
• Attention-driven Graph Clustering Network [49.040136530379094]
  我々は、注意駆動グラフクラスタリングネットワーク(AGCN)という新しいディープクラスタリング手法を提案する。 AGCNは、ノード属性特徴とトポロジグラフ特徴を動的に融合するために、不均一な融合モジュールを利用する。 AGCNは、教師なしの方法で特徴学習とクラスタ割り当てを共同で行うことができる。
  論文  参考訳（メタデータ） (2021-08-12T02:30:38Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)

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

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