論文の概要: A Spectral Framework for Evaluating Geodesic Distances Between Graphs
- arxiv url: http://arxiv.org/abs/2406.10500v3
- Date: Fri, 15 Aug 2025 05:34:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-18 16:53:24.067843
- Title: A Spectral Framework for Evaluating Geodesic Distances Between Graphs
- Title（参考訳）: グラフ間の測地距離評価のためのスペクトルフレームワーク
- Authors: Soumen Sikder Shuvo, Ali Aghdaei, Zhuo Feng,
- Abstract要約: 本稿では,グラフデータサンプル間の差分を定量化するために,グラフ測地距離(GGD)という新しい指標を提案する。
提案したGGD測度は、鍵構造(スペクトル)特性の相違をカプセル化することにより、2つのグラフ間の相違性を効果的に定量化することができる。
我々は,グラフ分類以外のGGDの適用を,GNNの安定性解析やデータセット間の距離の定量化に拡張する。
- 参考スコア（独自算出の注目度）: 4.110108749051657
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper presents a spectral framework for quantifying the differentiation between graph data samples by introducing a novel metric named Graph Geodesic Distance (GGD). For two different graphs with the same number of nodes, our framework leverages a spectral graph matching procedure to find node correspondence so that the geodesic distance between them can be subsequently computed by solving a generalized eigenvalue problem associated with their Laplacian matrices. For graphs of different sizes, a resistance-based spectral graph coarsening scheme is introduced to reduce the size of the larger graph while preserving the original spectral properties. We show that the proposed GGD metric can effectively quantify dissimilarities between two graphs by encapsulating their differences in key structural (spectral) properties, such as effective resistances between nodes, cuts, and the mixing time of random walks. Through extensive experiments comparing with state-of-the-art metrics, such as the latest Tree-Mover's Distance (TMD), the proposed GGD metric demonstrates significantly improved performance for graph classification, particularly when only partial node features are available. Furthermore, we extend the application of GGD beyond graph classification to stability analysis of GNNs and the quantification of distances between datasets, highlighting its versatility in broader machine learning contexts.
- Abstract（参考訳）: 本稿では,グラフ測地距離 (GGD) という新しい指標を導入することで,グラフデータサンプル間の差分を定量化するためのスペクトルフレームワークを提案する。
同じ数のノードを持つ2つの異なるグラフに対して、我々のフレームワークはスペクトルグラフマッチング手法を利用してノード対応を見つけ、それらの間の測地距離を、ラプラシア行列に関連する一般化固有値問題を解くことによって計算することができる。
異なる大きさのグラフに対して、抵抗ベースのスペクトルグラフ粗化スキームを導入し、元のスペクトル特性を保ちながら、より大きなグラフのサイズを小さくする。
提案手法は,ノード間の有効抵抗,カット,ランダムウォークの混合時間などの重要な構造(スペクトル)特性の違いをカプセル化することにより,二つのグラフ間の相違性を効果的に定量化できることを示す。
最新のTree-Mover's Distance (TMD) など,最先端のメトリクスと比較した広範な実験を通じて,提案したGGD測定はグラフ分類において,特に部分ノードの特徴しか利用できない場合に,大幅に改善された性能を示す。
さらに,グラフ分類を超えたGGDの適用範囲を,GNNの安定性解析やデータセット間の距離の定量化に拡張し,より広範な機械学習コンテキストにおけるその汎用性を強調した。
関連論文リスト
- Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [33.266521866968304]
ノード属性を持つ属性グラフ上でのグラフニューラルネットワーク(GNN)の普遍性と一般化を解析する。
我々は、GNNに対する普遍近似定理と、属性グラフの任意のデータ分布上のGNNの有界一般化を証明した。
我々の研究は、属性のないグラフのみの導出理論、GNNが連続だが分離パワーのない導出コンパクトなメトリクス、GNNが連続かつ分離ポイントである導出指標を拡張・統合する。
論文 参考訳（メタデータ） (2024-11-08T10:34:24Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes [3.8823562292981393]
本稿では,ノード数が異なる可能性のあるグラフ間の相似性を測定する指標を提案する。
提案したグラフGOSPAメトリクスは、適切に割り当てられたノード、ミスノード、偽ノード、グラフ間のエッジミスマッチに対するノード属性エラーに関連するコストを含む。
論文 参考訳（メタデータ） (2023-11-10T11:40:24Z) - Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
グラフニューラルネットワーク(GNN)を用いたハイパーグラフでサポートする信号処理アーキテクチャを提案する。
スペクトル類似性により任意のグラフにまたがってGNNの安定性と転送可能性の誤差をバウンドするフレームワークを提供する。
論文 参考訳（メタデータ） (2022-11-11T23:44:20Z) - A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
そこで我々は,グラフスペクトルの空間分布がグラフスペクトルに与える影響を解析し,グラフニューラルネットワーク(GNN)の高密度グラフとスパースグラフのノード分類における性能について検討した。
GNNはスパースグラフのスペクトル法よりも優れており、これらの結果を合成グラフと実グラフの両方で数値例で示すことができる。
論文 参考訳（メタデータ） (2022-11-06T22:38:13Z) - Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph
Neural Networks [54.225220638606814]
本稿では,属性グラフの擬似測度,ツリー・モーバー距離(TMD)を提案し,その一般化との関係について検討する。
まず、TMDはグラフ分類に関連する特性をキャプチャし、単純なTMD-SVMは標準のGNNと競合することを示す。
第2に、分散シフトの下でのGNNの一般化とTMDを関連付け、そのようなシフト下での性能低下とよく相関していることを示す。
論文 参考訳（メタデータ） (2022-10-04T21:03:52Z) - Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。
GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
論文 参考訳（メタデータ） (2022-05-07T04:11:23Z) - SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
グラフマッチングの精度、構造的不整合(SI)を測定するための新しい基準を提案する。
具体的には、SIは、グラフのマルチホップ構造に対応するために熱拡散ウェーブレットを組み込む。
ミラー降下法を用いて,新しいK-ホップ構造に基づくマッチングコストでGromov-Wasserstein距離を解くことにより,SIGMAを導出可能であることを示す。
論文 参考訳（メタデータ） (2022-02-06T15:18:37Z) - Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。
そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
論文 参考訳（メタデータ） (2021-11-19T08:54:21Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。
近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
論文 参考訳（メタデータ） (2021-06-26T06:24:51Z) - Graphon Pooling in Graph Neural Networks [169.09536309161314]
グラフニューラルネットワーク(GNN)は、グラフによってモデル化された不規則構造上の信号の処理を含む様々なアプリケーションで効果的に使用されている。
本稿では,グラフのスペクトル特性を保存したグラフオンを用いて,GNNのプールとサンプリングを行う新しい手法を提案する。
論文 参考訳（メタデータ） (2020-03-03T21:04:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。