論文の概要: Effective Clustering on Large Attributed Bipartite Graphs
- arxiv url: http://arxiv.org/abs/2405.11922v1
- Date: Mon, 20 May 2024 09:58:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-21 13:34:30.807018
- Title: Effective Clustering on Large Attributed Bipartite Graphs
- Title（参考訳）: 大規模分散二部グラフの効率的なクラスタリング
- Authors: Renchi Yang, Yidu Wu, Xiaoyang Lin, Qichen Wang, Tsz Nam Chan, Jieming Shi,
- Abstract要約: 分散二部グラフ(ABG)は、2つの異種ノード間の相互作用を記述するための表現型データモデルである。
このようなグラフに設定された対象ノードを(k-ABGCと呼ばれる) k 個の非連結クラスタに分割すると、様々な領域で広く使われるようになる。
しかし、k-ABGCに対する既存の解のほとんどは、属性情報を見渡すか、二部グラフ構造を正確に捉えないかのいずれかである。
我々は,複数の実データセット上でのスーパーブクラスタリング性能を実現する,k-ABGCの効率的かつ効率的なアプローチであるTPOを提案する。
- 参考スコア（独自算出の注目度）: 10.701751248623863
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Attributed bipartite graphs (ABGs) are an expressive data model for describing the interactions between two sets of heterogeneous nodes that are associated with rich attributes, such as customer-product purchase networks and author-paper authorship graphs. Partitioning the target node set in such graphs into k disjoint clusters (referred to as k-ABGC) finds widespread use in various domains, including social network analysis, recommendation systems, information retrieval, and bioinformatics. However, the majority of existing solutions towards k-ABGC either overlook attribute information or fail to capture bipartite graph structures accurately, engendering severely compromised result quality. The severity of these issues is accentuated in real ABGs, which often encompass millions of nodes and a sheer volume of attribute data, rendering effective k-ABGC over such graphs highly challenging. In this paper, we propose TPO, an effective and efficient approach to k-ABGC that achieves superb clustering performance on multiple real datasets. TPO obtains high clustering quality through two major contributions: (i) a novel formulation and transformation of the k-ABGC problem based on multi-scale attribute affinity specialized for capturing attribute affinities between nodes with the consideration of their multi-hop connections in ABGs, and (ii) a highly efficient solver that includes a suite of carefully-crafted optimizations for sidestepping explicit affinity matrix construction and facilitating faster convergence. Extensive experiments, comparing TPO against 19 baselines over 5 real ABGs, showcase the superior clustering quality of TPO measured against ground-truth labels. Moreover, compared to the state of the arts, TPO is often more than 40x faster over both small and large ABGs.
- Abstract（参考訳）: 分散二部グラフ(ABG)は、顧客-商品購入ネットワークや著者-紙の著者間グラフなど、豊富な属性に関連付けられた2組の異種ノード間の相互作用を記述するための表現力のあるデータモデルである。
このようなグラフにセットされたターゲットノードを(k-ABGCと呼ばれる)非結合クラスタに分割すると、ソーシャルネットワーク分析、レコメンデーションシステム、情報検索、バイオインフォマティクスなど、様々な領域で広く利用される。
しかし、k-ABGCに対する既存のソリューションの大半は属性情報を見落としているか、二部グラフ構造を正確に捉えていないかのいずれかであり、非常に妥協された結果の品質を損なう。
これらの問題の重大さは、数百万のノードと大量の属性データを含む実際のABGでアクセント化され、そのようなグラフ上で有効なk-ABGCをレンダリングする。
本稿では,複数の実データセット上でのスーパーブクラスタリング性能を実現する,k-ABGCの効率的かつ効率的なアプローチであるTPOを提案する。
TPOは2つの主要な貢献を通じて高いクラスタリング品質を得る。
i) ABGにおけるマルチホップ接続を考慮したノード間の属性親和性獲得に特化したマルチスケール属性親和性に基づくk-ABGC問題の新たな定式化と変換
(II) 明確な親和性行列の構成をサイドステッピングし、より高速な収束を容易にするために、慎重に設計された最適化を含む高効率な解法。
5つの実ABGに対してTPOと19の基線を比較した大規模な実験では、TPOが地上トルスラベルに対して測定された優れたクラスタリング品質を示した。
さらに、最先端技術と比較して、TPOは小さなABGと大きなABGのどちらよりも40倍以上高速であることが多い。
関連論文リスト
- A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
グラフ構造を先行として扱うことで,特徴中心の事前学習の視点を導入する。
我々のフレームワークであるGraph Sequence Pretraining with Transformer (GSPT)はランダムウォークを通してノードコンテキストをサンプリングする。
GSPTはノード分類とリンク予測の両方に容易に適応でき、様々なデータセットで有望な経験的成功を示す。
論文 参考訳（メタデータ） (2024-06-19T22:30:08Z) - Effective Edge-wise Representation Learning in Edge-Attributed Bipartite Graphs [22.896511369954286]
本稿では,エッジ分散二部グラフ(EABG)のためのグラフ表現学習法を提案する。
エッジの観点からの構造と属性のセマンティクスを取り入れ、AEBGにおける2つの異種ノード集合 U と V の別個の影響を考慮している。
APでは少なくとも38.11%、AUCでは1.86%を達成している。
論文 参考訳（メタデータ） (2024-06-19T09:11:03Z) - Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks [2.7523980737007414]
高次グラフ(HDG)上のグラフニューラルネットワーク(GNN)のための効率的かつ効果的なフロントマウントデータ拡張フレームワークであるTADを提案する。
内部では、(i)構造埋め込みによる機能拡張と(ii)トポロジと属性対応グラフのスパース化という、2つの重要なモジュールが含まれている。
TADAは、ノード分類の観点から8つの実ホモ親和性/ヘテロ親和性HDG上でのメインストリームGNNモデルの予測性能を大幅に改善する。
論文 参考訳（メタデータ） (2024-06-08T14:14:19Z) - 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) - Efficient Multi-View Graph Clustering with Local and Global Structure
Preservation [59.49018175496533]
局所・グローバル構造保存を用いた効率的なマルチビューグラフクラスタリング(EMVGC-LG)という,アンカーベースのマルチビューグラフクラスタリングフレームワークを提案する。
具体的には、EMVGC-LGがクラスタリング品質を向上させるために、アンカー構築とグラフ学習を共同で最適化する。
さらに、EMVGC-LGはサンプル数に関する既存のAMVGCメソッドの線形複雑性を継承する。
論文 参考訳（メタデータ） (2023-08-31T12:12:30Z) - Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
GRCCAと呼ばれるクラスタ割り当てを対比して、教師なしグラフ表現モデルを提案する。
クラスタリングアルゴリズムとコントラスト学習を組み合わせることで、局所的およびグローバルな情報を合成的にうまく活用する動機付けがある。
GRCCAは、ほとんどのタスクにおいて強力な競争力を持っている。
論文 参考訳（メタデータ） (2021-12-15T07:28:58Z) - Attention-driven Graph Clustering Network [49.040136530379094]
我々は、注意駆動グラフクラスタリングネットワーク(AGCN)という新しいディープクラスタリング手法を提案する。
AGCNは、ノード属性特徴とトポロジグラフ特徴を動的に融合するために、不均一な融合モジュールを利用する。
AGCNは、教師なしの方法で特徴学習とクラスタ割り当てを共同で行うことができる。
論文 参考訳（メタデータ） (2021-08-12T02:30:38Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。