論文の概要: Adaptive Local Clustering over Attributed Graphs
- arxiv url: http://arxiv.org/abs/2503.20488v1
- Date: Wed, 26 Mar 2025 12:24:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-27 13:19:26.919158
- Title: Adaptive Local Clustering over Attributed Graphs
- Title（参考訳）: 分散グラフ上の適応型ローカルクラスタリング
- Authors: Haoran Zheng, Renchi Yang, Jianliang Xu,
- Abstract要約: 局所グラフクラスタリングは、G$のサブグラフである$C_sを、$C_s$のサイズとほぼ線形に囲む$v_s$で識別することを目的としている。
既存のソリューションのほとんどは、単に$G$のノード間のトポロジ的接続に依存しているだけであり、それらが欠落またはノイズの多いリンクに対して脆弱である。
本稿では,複数の実データセット上での超高速な経験的性能を実現するLGCの効率的かつ効果的なアプローチであるLACAを提案する。
- 参考スコア（独自算出の注目度）: 16.197833892857282
- License:
- Abstract: Given a graph $G$ and a seed node $v_s$, the objective of local graph clustering (LGC) is to identify a subgraph $C_s \in G$ (a.k.a. local cluster) surrounding $v_s$ in time roughly linear with the size of $C_s$. This approach yields personalized clusters without needing to access the entire graph, which makes it highly suitable for numerous applications involving large graphs. However, most existing solutions merely rely on the topological connectivity between nodes in $G$, rendering them vulnerable to missing or noisy links that are commonly present in real-world graphs. To address this issue, this paper resorts to leveraging the complementary nature of graph topology and node attributes to enhance local clustering quality. To effectively exploit the attribute information, we first formulate the LGC as an estimation of the bidirectional diffusion distribution (BDD), which is specialized for capturing the multi-hop affinity between nodes in the presence of attributes. Furthermore, we propose LACA, an efficient and effective approach for LGC that achieves superb empirical performance on multiple real datasets while maintaining strong locality. The core components of LACA include (i) a fast and theoretically-grounded preprocessing technique for node attributes, (ii) an adaptive algorithm for diffusing any vectors over $G$ with rigorous theoretical guarantees and expedited convergence, and (iii) an effective three-step scheme for BDD approximation. Extensive experiments, comparing 17 competitors on 8 real datasets, show that LACA outperforms all competitors in terms of result quality measured against ground truth local clusters, while also being up to orders of magnitude faster. The code is available at https://github.com/HaoranZ99/alac.
- Abstract（参考訳）: グラフ$G$とシードノード$v_s$が与えられたとき、ローカルグラフクラスタリング(LGC)の目的は、$C_s \in G$(つまり、ローカルクラスタ)というサブグラフを、$C_s$とほぼ線形に囲む時間で識別することである。
このアプローチは、グラフ全体にアクセスすることなくパーソナライズされたクラスタを生成するため、大きなグラフを含む多数のアプリケーションに非常に適している。
しかし、既存のほとんどのソリューションは、単に$G$のノード間のトポロジ的接続に依存しているだけであり、現実のグラフによく見られる欠落やノイズの多いリンクに対して脆弱である。
そこで本稿では,グラフトポロジとノード属性の相補的性質を活用して局所クラスタリングの品質を向上させる。
属性情報を効果的に活用するために,我々はまず,属性の存在下でノード間のマルチホップ親和性を捉えるための双方向拡散分布(BDD)の推定としてLGCを定式化する。
さらに,複数の実データに対して高い局所性を維持しつつ,超高効率な実験性能を実現するLGCの効率的かつ効果的なアプローチであるLACAを提案する。
LACAのコアコンポーネントには
(i)ノード属性の高速かつ理論的な前処理手法
(ii)厳密な理論的保証と高速収束を伴う$G$以上のベクトルを拡散する適応的アルゴリズム
三 BDD近似の効果的な三段階スキーム。
8つの実際のデータセット上の17の競合と比較した大規模な実験では、LACAは、地上の真実のローカルクラスタに対して測定された結果の品質において、すべての競合より優れており、同時に、桁違いに高速であることを示している。
コードはhttps://github.com/HaoranZ99/alac.comから入手できる。
関連論文リスト
- Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
この研究はグラフ局所クラスタリングに重点を置いており、様々なモダリティの内部接続性のため、グラフ以外の幅広い応用がある。
非近似型Andersen-Chung-Lang(ACL)アルゴリズムを離散グラフを超えて拡張し、その二次最適性をより広い範囲のグラフに一般化する。
理論的には、2つの穏やかな条件下では、両方のアルゴリズムが少なくとも1/2確率のコンダクタンスの観点から2次最適局所クラスターを識別できることが証明される。
論文 参考訳（メタデータ） (2024-12-04T03:56:14Z) - CiliaGraph: Enabling Expression-enhanced Hyper-Dimensional Computation in Ultra-Lightweight and One-Shot Graph Classification on Edge [1.8726646412385333]
CiliaGraphはグラフ分類のための拡張表現型だが超軽量なHDCモデルである。
CiliaGraphはメモリ使用量を削減し、トレーニング速度を平均292倍に高速化する。
論文 参考訳（メタデータ） (2024-05-29T12:22:59Z) - Graph Sparsification via Mixture of Graphs [67.40204130771967]
そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。
MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。
5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
論文 参考訳（メタデータ） (2024-05-23T07:40:21Z) - Cluster-based Graph Collaborative Filtering [55.929052969825825]
グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。
既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。
クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
論文 参考訳（メタデータ） (2024-04-16T07:05:16Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。
提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。
フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
論文 参考訳（メタデータ） (2023-08-13T18:12: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) - GC-Flow: A Graph-Based Flow Network for Effective Clustering [10.354035049272095]
グラフ畳み込みネットワーク(GCN)は、グラフデータの半教師付き分類のために、クラス後部$p(y|mathbfx)$を直接モデル化する固有モデルである。
この作業では、GCN層を置き換える正規化フローを設計し、クラス条件付き可能性$p(mathbfx|y)$とクラス前の$p(y)$の両方をモデル化する表現モデルを作成します。
結果のニューラルネットワークであるGC-Flowは、装備中にグラフ畳み込み操作を保持する
論文 参考訳（メタデータ） (2023-05-26T22:11:38Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。
SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。
OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
論文 参考訳（メタデータ） (2021-10-15T03:25:28Z) - Git: Clustering Based on Graph of Intensity Topology [25.679620842010422]
我々は、新しいクラスタリングアルゴリズムGIT(textbfIntensity textbfTopologyのtextbfGraphに基づくクラスタリング)を提案する。
高速な局所クラスタ検出、堅牢なトポグラフの構築、エッジカットにより、GITは魅力的なARISE性能を示す。
論文 参考訳（メタデータ） (2021-10-04T09:29:43Z) - Minimizing Localized Ratio Cut Objectives in Hypergraphs [32.80813008862995]
局所化率削減目標の最小化に基づく局所的ハイパーグラフクラスタリングのためのフレームワークを提案する。
我々のアルゴリズムは強局所的であり、その実行は入力セットのサイズにのみ依存し、優れたローカルクラスタを見つけるためにハイパーグラフ全体を探索する必要はない。
論文 参考訳（メタデータ） (2020-02-21T17:42:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。