論文の概要: Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle

• arxiv url: http://arxiv.org/abs/2605.13021v1
• Date: Wed, 13 May 2026 05:24:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:27.824889
• Title: Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle
• Title（参考訳）: 非セルフィッシュ原理による効率的なグラフ粗化の再考
• Authors: Xu Bai, Bin Lu, Kun Zhang, Shengbo Chen, Xinbing Wang, Chenghu Zhou, Meng Jin,
• Abstract要約: 粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。 局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。 粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
• 参考スコア（独自算出の注目度）: 56.92868481531399
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph coarsening is a graph dimensionality reduction technique that aims to construct a smaller and more tractable graph while preserving the essential structural and semantic properties of the original graph. However, most existing methods rely on pair-wise similarity matching, where each node independently searches for its best partner based on global information. This selfishness matching paradigm incurs substantial computational and memory overhead. To address this problem, we shift to a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening, and propose an efficient method named NOPE, which achieves linear memory consumption and near-linear computational complexity in the number of nodes. Furthermore, we derive a faster variant NOPE*, which reduces O(δ\dot d) interference evaluation to O(d) based on the local isotropy assumption, and consequently alleviates the computational bottleneck for high-degree nodes. Experimental results show that NOPE* achieves 1.8-10\times speedup over NOPE and surpass almost all baselines with 1-3 orders of magnitude acceleration. Meanwhile, learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning owing to compact graph information. The code can be available at https://github.com/dazonglian/NOPE-main.
• Abstract（参考訳）: グラフ粗化(Graph coarsening)とは、グラフの基本構造と意味性を保ちながら、より小さく、よりトラクタブルなグラフを構築することを目的としたグラフ次元削減手法である。 しかし、既存のほとんどの手法はペアワイズ類似性マッチングに依存しており、各ノードはグローバル情報に基づいて、独立して最高のパートナーを検索する。 この利己的なマッチングパラダイムは、かなりの計算とメモリオーバーヘッドを引き起こす。 この問題に対処するため、我々は、粗大化における近隣住民の集団干渉を優先する非利己主義に移行し、ノード数における線形メモリ消費とニア線形計算複雑性を実現する、NOPEと呼ばれる効率的な方法を提案する。 さらに、局所等方性仮定に基づいて、O(δ\dot d)干渉評価をO(d)に還元し、高次ノードの計算ボトルネックを軽減する高速なNOPE*を導出する。 実験の結果,NOPE*はNOPEよりも1.8-10\timesの高速化を実現し,ほぼすべてのベースラインを1-3桁の加速度で超えることがわかった。 一方、粗いグラフの学習は元のグラフに匹敵する性能を示し、コンパクトなグラフ情報による LLM ベースのグラフ推論よりも優れた性能を示すことができる。 コードはhttps://github.com/dazonglian/NOPE-mainで入手できる。

関連論文リスト

• Efficient Learning on Large Graphs using a Densifying Regularity Lemma [7.2134828716289645]
  交差する二部体成分の組み合わせに基づいて、大きな有向グラフの低ランク分解を導入する。 グラフ,スパース,あるいは密度を高密度IBGで効率的に近似する方法を示す。
  論文  参考訳（メタデータ） (2025-04-25T11:34:44Z)
• FIT-GNN: Faster Inference Time for GNNs that 'FIT' in Memory Using Coarsening [1.1345413192078595]
  本稿では,グラフ粗化を用いた推論フェーズにおける計算負担を軽減することにより,グラフニューラルネットワーク(GNN)のスケーラビリティを向上させる新しい手法を提案する。 本研究は,グラフ分類やグラフ回帰を含むグラフレベルのタスクに対するグラフ粗化の適用を拡大する。 その結果,提案手法は従来の手法に比べて単一ノード推定時間において桁違いに改善されていることがわかった。
  論文  参考訳（メタデータ） (2024-10-19T06:27:24Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)

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

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