論文の概要: Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction

• arxiv url: http://arxiv.org/abs/2609.34729v1
• Date: Mon, 28 Sep 2026 09:29:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 03:24:06.680458
• Title: Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction
• Title（参考訳）: GNNにおけるエッジレベル自己同型: リンク予測のための定量的フレームワークと効果的な設計
• Abstract要約: グラフニューラルネットワーク(GNN)は、置換同変アグリゲーションを通じてノードを学習し、埋め込みをリンクするのに有効である。 標準GNNは自己同型ノードを区別不能な表現に分解し、ノード自己同型問題を引き起こす。 グラフ内のリンクを識別するGNNの能力を定量化するスカラー計量であるエッジ自己同型比(EAR)を導入する。
• 参考スコア（独自算出の注目度）: 11.101672750624964
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNNs) are effective for learning node and link embeddings through permutation-equivariant aggregation. However, standard GNNs collapse automorphic nodes, i.e., those with identical structural roles (or orbits) into indistinguishable representations, leading to the node automorphism problem. This collapse limits their expressive power and degrades link prediction performance. Existing approaches to characterize GNN expressiveness rely primarily on Weisfeiler-Lehman (WL) analyses, but these methods are typically qualitative and often misaligned with empirical results. To address this gap, we begin by introducing a novel quantitative framework to assess GNN expressiveness for link prediction. We first formalize edge-level automorphism through edge orbits, which capture the set of structural role pairs for nodes that share a link. Then, we introduce the edge automorphism ratio (EAR), a scalar metric that quantifies a GNN's ability to distinguish links in a given graph. We empirically demonstrate that EAR correlates strongly with performance, validating its practical benefit. Building on this insight, we design EDGE-ORBIT EQUIVARIANT GRAPH NEURAL NETWORK (EO-GNN), a GNN architecture that addresses automorphism collapse while preserving equivariance and incurring minimal computational overhead. EO-GNN accomplishes this through two core designs combined with WL-based node hashes: (i) automorphism-aware dropouts and (ii) subgraph orbit-biased aggregation. Empirical evaluations on synthetic and real graphs show improvements of up to 42.36% and 28.44%, respectively, in predicting links in scenarios with high automorphism.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、置換同変アグリゲーションを通じてノードを学習し、埋め込みをリンクするのに有効である。 しかし、標準のGNNは自己同型ノード、すなわち同一の構造的役割(または軌道)を持つノードを区別不能な表現に分解し、ノード自己同型問題を引き起こす。 この崩壊は表現力を制限し、リンク予測性能を低下させる。 GNN表現性を特徴付ける既存のアプローチは、主にWeisfeiler-Lehman (WL)分析に依存しているが、これらの手法は定性的であり、しばしば経験的な結果と一致しない。 このギャップに対処するために、リンク予測のためのGNN表現性を評価するための新しい定量的フレームワークを導入することから始める。 まず、エッジ軌道を通してエッジレベルの自己同型を定式化し、リンクを共有するノードの構造的役割ペアの集合をキャプチャする。 次に、グラフ内のリンクを識別するGNNの能力を定量化するスカラー計量であるエッジ自己同型比(EAR)を導入する。 我々は、EARがパフォーマンスと強く相関し、その実用的利益を検証することを実証的に実証した。 この知見に基づいて,同値を維持し,計算オーバーヘッドを最小限に抑えながら自己同型崩壊に対処するGNNアーキテクチャであるEDGE-ORBIT EQUIVARIANT GRAPH NEURAL NWORK(EO-GNN)を設計する。 EO-GNNは、2つのコア設計とWLベースのノードハッシュを組み合わせることでこれを達成している。 (i)自己同型対応ドロップアウト (II)軌道バイアスアグリゲーション 合成グラフと実グラフの実証的な評価は、それぞれ42.36%と28.44%の改善を示し、高い自己同型を持つシナリオにおけるリンクを予測する。

関連論文リスト

• Directed Homophily-Aware Graph Neural Network [7.539052660225002]
  我々は、ホモフィア認識と指向性を考慮した新しいフレームワーク、Directed Homophily-aware Graph Neural Network (DHGNN)を提案する。 DHGNNは、ホモフィリーレベルと情報性に基づいてメッセージコントリビューションを適応的に変調するリセット可能なゲーティング機構を採用している。 解析により、このゲーティング機構は、方向のホモフィリギャップを捕捉し、層を横切るホモフィリを変動させ、複雑なグラフ構造上のメッセージパッシングの挙動について深い洞察を与えることが示された。
  論文  参考訳（メタデータ） (2025-05-28T13:41:04Z)
• Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
  Graph-aware Logistic Regression (GLR) はノード分類タスク用に設計された非神経モデルである。 GNNにアクセスできる情報のごく一部しか使わない従来のグラフアルゴリズムとは異なり、提案モデルではノードの特徴とエンティティ間の関係を同時に活用する。
  論文  参考訳（メタデータ） (2024-11-19T08:32:14Z)
• Heterophily-Aware Graph Attention Network [42.640057865981156]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において顕著な成功を収めている。 既存のヘテロフィル性GNNは、各エッジのヘテロフィリのモデリングを無視する傾向にあり、これはヘテロフィリ問題に取り組む上でも不可欠である。 本稿では,局所分布を基礎となるヘテロフィリーとして完全に探索し,活用することで,新たなヘテロフィア対応グラフ注意ネットワーク(HA-GAT)を提案する。
  論文  参考訳（メタデータ） (2023-02-07T03:21:55Z)
• A Variational Edge Partition Model for Supervised Graph Representation Learning [51.30365677476971]
  本稿では,重なり合うノード群間の相互作用を集約することで,観測されたエッジがどのように生成されるかをモデル化するグラフ生成プロセスを提案する。 それぞれのエッジを複数のコミュニティ固有の重み付きエッジの和に分割し、コミュニティ固有のGNNを定義する。 エッジを異なるコミュニティに分割するGNNベースの推論ネットワーク,これらのコミュニティ固有のGNN,およびコミュニティ固有のGNNを最終分類タスクに組み合わせたGNNベースの予測器を共同で学習するために,変分推論フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-02-07T14:37:50Z)
• Feature Correlation Aggregation: on the Path to Better Graph Neural Networks [37.79964911718766]
  グラフニューラルネットワーク(GNN)が導入される以前、不規則なデータ、特にグラフのモデリングと解析は、ディープラーニングのアキレスのヒールであると考えられていた。 本稿では,GNNのコア操作に対して,極めて単純かつ無作為な修正を施した中央ノード置換変分関数を提案する。 モデルの具体的な性能向上は、モデルがより少ないパラメータを使用しながら、有意なマージンで過去の最先端結果を上回った場合に観察される。
  論文  参考訳（メタデータ） (2021-09-20T05:04:26Z)
• SLGCN: Structure Learning Graph Convolutional Networks for Graphs under Heterophily [5.619890178124606]
  本稿では2つの側面から問題を緩和する構造学習グラフ畳み込みネットワーク(SLGCN)を提案する。 具体的には、全ての類似ノードから特徴表現を効率的に集約するために、アンカーを用いた効率的なスペクトルクラスタリング(ESC-ANCH)を設計する。 幅広いベンチマークデータセットの実験結果は、提案されたSLGCNが、最先端のGNNよりも優れていることを示している。
  論文  参考訳（メタデータ） (2021-05-28T13:00:38Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。 ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。 既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-01-25T18:59:01Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)

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

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