論文の概要: GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing

• arxiv url: http://arxiv.org/abs/2506.19224v1
• Date: Tue, 24 Jun 2025 01:18:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-25 19:48:23.429995
• Title: GBGC: Efficient and Adaptive Graph Coarsening via Granular-ball Computing
• Title（参考訳）: GBGC: グラニュラーボールコンピューティングによる効率的かつ適応的なグラフ粗大化
• Authors: Shuyin Xia, Guan Wang, Gaojie Xu, Sen Zhao, Guoyin Wang,
• Abstract要約: グラニュラーボール(GBGC)を用いた新しい多粒度, 効率的, 適応的粗大化法を提案する。 GBGCは、適応的な粒度グラフ精錬機構を導入し、元のグラフを粗いものから細かいものへと適応的に分割し、異なる大きさの粒度と最適な粒度に分割する。 GBGCの精度は、グラニュラーボール計算の優れた堅牢性と一般化のため、元のグラフよりもほぼ常に高い。
• 参考スコア（独自算出の注目度）: 14.285582054503973
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The objective of graph coarsening is to generate smaller, more manageable graphs while preserving key information of the original graph. Previous work were mainly based on the perspective of spectrum-preserving, using some predefined coarsening rules to make the eigenvalues of the Laplacian matrix of the original graph and the coarsened graph match as much as possible. However, they largely overlooked the fact that the original graph is composed of subregions at different levels of granularity, where highly connected and similar nodes should be more inclined to be aggregated together as nodes in the coarsened graph. By combining the multi-granularity characteristics of the graph structure, we can generate coarsened graph at the optimal granularity. To this end, inspired by the application of granular-ball computing in multi-granularity, we propose a new multi-granularity, efficient, and adaptive coarsening method via granular-ball (GBGC), which significantly improves the coarsening results and efficiency. Specifically, GBGC introduces an adaptive granular-ball graph refinement mechanism, which adaptively splits the original graph from coarse to fine into granular-balls of different sizes and optimal granularity, and constructs the coarsened graph using these granular-balls as supernodes. In addition, compared with other state-of-the-art graph coarsening methods, the processing speed of this method can be increased by tens to hundreds of times and has lower time complexity. The accuracy of GBGC is almost always higher than that of the original graph due to the good robustness and generalization of the granular-ball computing, so it has the potential to become a standard graph data preprocessing method.
• Abstract（参考訳）: グラフ粗化の目的は、元のグラフのキー情報を保持しながら、より小さく、より管理しやすいグラフを生成することである。 従来の研究は主にスペクトル保存の観点に基づいており、いくつかの事前定義された粗い規則を用いて元のグラフのラプラシアン行列の固有値と粗いグラフを可能な限り一致させる。 しかし、彼らは、元のグラフが異なる粒度の部分領域で構成されているという事実を概ね見落としており、そこでは、高連結で類似したノードが、粗いグラフのノードとして集約される傾向が強い。 グラフ構造の多粒度特性を組み合わせることで、最適粒度で粗いグラフを生成することができる。 この目的のために,多粒度におけるグラニュラーボールコンピューティングの適用に触発されて,グラニュラーボール(GBGC)による新しい多粒度,効率的,適応的な粗化法を提案し,粗化結果と効率を大幅に改善する。 具体的には、GBGCは、適応的な粒度グラフ精錬機構を導入し、元のグラフを粗くして、異なる大きさと最適粒度の粒度に適応的に分割し、これらの粒度グラフをスーパーノードとして、粗度グラフを構築する。 また、他の最先端グラフ粗化法と比較して、この手法の処理速度は数十倍から数百倍に向上し、時間的複雑さを低減できる。 GBGCの精度は、グラニュラーボール計算の堅牢性と一般化のため、元のグラフよりも常に高いので、標準グラフデータ前処理法になる可能性がある。

関連論文リスト

• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。 本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
  論文  参考訳（メタデータ） (2025-06-19T08:01:00Z)
• Efficient Learning on Large Graphs using a Densifying Regularity Lemma [7.2134828716289645]
  交差する二部体成分の組み合わせに基づいて、大きな有向グラフの低ランク分解を導入する。 グラフ,スパース,あるいは密度を高密度IBGで効率的に近似する方法を示す。
  論文  参考訳（メタデータ） (2025-04-25T11:34:44Z)
• Training-free Heterogeneous Graph Condensation via Data Selection [74.06562124781104]
  本稿では, 高速かつ高品質な不均質凝縮グラフ生成を容易にする, FreeHGC と呼ばれる, 基礎となる不均質グラフ凝縮法について紹介する。 具体的には、不均質グラフの凝縮問題をデータ選択問題として再構成し、不均質グラフにおける代表ノードとエッジを評価し、凝縮するための新たな視点を提供する。
  論文  参考訳（メタデータ） (2024-12-20T02:49:32Z)
• Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training [30.354103857690777]
  グラフデータを効果的に圧縮するために粒度計算を用いる。 我々は、純度閾値に基づいてグラフをグラニュラーボールに繰り返し分割することにより、粗いグラフネットワークを構築する。 我々のアルゴリズムは、予め定義された粗大化率を必要とせずに、スプリッティングを適応的に行うことができる。
  論文  参考訳（メタデータ） (2024-12-18T13:36:03Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。 我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
  論文  参考訳（メタデータ） (2022-06-28T02:10:05Z)
• Scaling R-GCN Training with Graph Summarization [71.06855946732296]
  リレーショナルグラフ畳み込みネットワーク(R-GCN)のトレーニングは、グラフのサイズに合わない。 本研究では,グラフの要約手法を用いてグラフを圧縮する実験を行った。 AIFB, MUTAG, AMデータセットについて妥当な結果を得た。
  論文  参考訳（メタデータ） (2022-03-05T00:28:43Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。 粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
  論文  参考訳（メタデータ） (2021-02-02T06:50:07Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  本稿では,グラフクラスタメンバシップを潜在因子とするDGVAE(Dirichlet Graph Variational Autoencoder)を提案する。 バランスグラフカットにおける低パス特性により、入力グラフをクラスタメンバシップにエンコードする、Heattsと呼ばれるGNNの新しい変種を提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:35:26Z)
• High-Order Relation Construction and Mining for Graph Matching [36.880853889521845]
  高次情報を記述するために、反復線グラフが最初に導入された。 本稿では,HGMN(High-order Graph Matching Network)と呼ばれる新しいグラフマッチング手法を提案する。 実用的な制約を課すことで、HGMNは大規模グラフに拡張性を持たせることができる。
  論文  参考訳（メタデータ） (2020-10-09T03:30:02Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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