論文の概要: Efficient High-Quality Clustering for Large Bipartite Graphs

• arxiv url: http://arxiv.org/abs/2312.16926v1
• Date: Thu, 28 Dec 2023 09:50:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-29 16:49:54.612575
• Title: Efficient High-Quality Clustering for Large Bipartite Graphs
• Title（参考訳）: 大規模二部グラフの高速クラスタリング
• Authors: Renchi Yang and Jieming Shi
• Abstract要約: k-Bipartite Graph Clustering (k-BGC) は、2部グラフにセットされたターゲット頂点を k 個の非結合クラスタに分割する。 クラスタリングの品質は、ソーシャルネットワーク分析、レコメンデーションシステム、テキストマイニング、バイオインフォマティクスといった様々な応用において、k-BGCの有用性にとって重要である。 本稿では,大規模二部グラフ上での最先端性能を実現する2つの効率的なk-BGCソリューション,HOPEとHOPE+を提案する。
• 参考スコア（独自算出の注目度）: 7.533043289759316
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A bipartite graph contains inter-set edges between two disjoint vertex sets, and is widely used to model real-world data, such as user-item purchase records, author-article publications, and biological interactions between drugs and proteins. k-Bipartite Graph Clustering (k-BGC) is to partition the target vertex set in a bipartite graph into k disjoint clusters. The clustering quality is important to the utility of k-BGC in various applications like social network analysis, recommendation systems, text mining, and bioinformatics, to name a few. Existing approaches to k-BGC either output clustering results with compromised quality due to inadequate exploitation of high-order information between vertices, or fail to handle sizable bipartite graphs with billions of edges. Motivated by this, this paper presents two efficient k-BGC solutions, HOPE and HOPE+, which achieve state-of-the-art performance on large-scale bipartite graphs. HOPE obtains high scalability and effectiveness through a new k-BGC problem formulation based on the novel notion of high-order perspective (HOP) vectors and an efficient technique for low-rank approximation of HOP vectors. HOPE+ further elevates the k-BGC performance to another level with a judicious problem transformation and a highly efficient two-stage optimization framework. Two variants, HOPE+ (FNEM) and HOPE+ (SNEM) are designed when either the Frobenius norm or spectral norm is applied in the transformation. Extensive experiments, comparing HOPE and HOPE+ against 13 competitors on 10 real-world datasets, exhibit that our solutions, especially HOPE+, are superior to existing methods in terms of result quality, while being up to orders of magnitude faster. On the largest dataset MAG with 1.1 billion edges, HOPE+ is able to produce clusters with the highest clustering accuracy within 31 minutes, which is unmatched by any existing solution for k-BGC.
• Abstract（参考訳）: バイパルタイトグラフは、2つの非結合頂点セット間のセット間のエッジを含み、ユーザ・イテム購入記録、著者・アーティクルの出版物、薬物とタンパク質間の生物学的相互作用などの現実世界のデータモデリングに広く用いられている。 k-Bipartite Graph Clustering (k-BGC) は、2部グラフに設定されたターゲット頂点を k 個の非結合クラスタに分割する。 クラスタリングの品質は、ソーシャルネットワーク分析、レコメンデーションシステム、テキストマイニング、バイオインフォマティクスといった様々な応用において、k-BGCの有用性にとって重要である。 k-BGCに対する既存のアプローチは、頂点間の高次情報の不十分な利用による品質の損なわれたクラスタリング結果を出力するか、数十億のエッジを持つ巨大な二部グラフを処理できないかのいずれかである。 そこで本研究では,大規模二部グラフ上での最先端性能を実現する2つの効率的なk-BGCソリューションHOPEとHOPE+を提案する。 HOPEは,高次視点ベクトル(HOP)の概念に基づく新しいk-BGC問題定式化と,HOPベクトルの低ランク近似のための効率的な手法により,高いスケーラビリティと有効性を得る。 HOPE+ はさらに k-BGC の性能を他のレベルに高め、高効率な2段階最適化フレームワークである。 2つの変種 HOPE+ (FNEM) と HOPE+ (SNEM) は、変換においてフロベニウスノルムまたはスペクトルノルムが適用されるときに設計される。 HOPEとHOPE+を10の現実世界のデータセット上の13の競合と比較した大規模な実験では、私たちのソリューション、特にHOPE+は、結果の品質という点で既存の方法よりも優れているが、桁違いに高速である。 1.1億エッジを持つ最大のデータセットmagでは、ホープ+は31分以内にクラスタを生成できるが、k-bgcの既存のソリューションには一致しない。

関連論文リスト

• 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)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• GLCC: A General Framework for Graph-level Clustering [5.069852282550117]
  本稿では,グラフレベルのクラスタリングの問題について検討する。 GLCC(Graph-Level Contrastive Clustering)というグラフレベルの一般的なクラスタリングフレームワークを提案する。 様々なよく知られたデータセットに対する実験は、競合するベースラインよりも提案したGLCCの方が優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T11:08:10Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  我々はフォン・ノイマンエントロピーに基づく新しい計量を提案し、GNNのヘテロフィリー問題を再検討する。 また、異種データセット上でのほとんどのGNNの性能を高めるために、Conv-Agnostic GNNフレームワーク(CAGNN)を提案する。
  論文  参考訳（メタデータ） (2022-03-19T14:26:43Z)
• Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
  GRCCAと呼ばれるクラスタ割り当てを対比して、教師なしグラフ表現モデルを提案する。 クラスタリングアルゴリズムとコントラスト学習を組み合わせることで、局所的およびグローバルな情報を合成的にうまく活用する動機付けがある。 GRCCAは、ほとんどのタスクにおいて強力な競争力を持っている。
  論文  参考訳（メタデータ） (2021-12-15T07:28:58Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。 提案されたSSCAGは最先端のアプローチと競合する。
  論文  参考訳（メタデータ） (2021-04-24T08:09:27Z)
• Effective and Scalable Clustering on Massive Attributed Graphs [25.161619807810215]
  本稿では,k-AGCに対する効果的なアプローチであるACMinを提案する。 ACMinは、グランドトラストラベルに対して測定された結果の質において、競争相手を一貫して上回り、桁違いに高速である。 特に、265.2百万のエッジと11億の属性値を持つMicrosoft Academic Knowledge Graphデータセットでは、ACMinは1つのCPUコアを使用して1.68時間以内に5-AGCの高品質な結果を出力する。
  論文  参考訳（メタデータ） (2021-02-07T15:50:28Z)
• Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
  重複する部分グラフを多数必要とせず,完全に学習可能なクラスタリングフレームワークを提案する。 提案手法はクラスタリングの精度を大幅に向上させ,その上で訓練した認識モデルの性能を向上させるが,既存の教師付き手法に比べて桁違いに効率的である。
  論文  参考訳（メタデータ） (2020-04-01T13:39:37Z)

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

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