論文の概要: Learning Efficient Positional Encodings with Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2502.01122v1
- Date: Mon, 03 Feb 2025 07:28:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-05 14:58:01.307689
- Title: Learning Efficient Positional Encodings with Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークを用いた効率的な位置符号化の学習
- Authors: Charilaos I. Kanatsoulis, Evelyn Choi, Stephanie Jegelka, Jure Leskovec, Alejandro Ribeiro,
- Abstract要約: グラフのための学習可能なPEの新しいフレームワークであるPEARLを紹介する。
PEARL は線形複雑性を持つ固有ベクトルの同変関数を近似し、その安定性と高表現力を厳密に確立する。
解析の結果、PEARLは線形複雑度を持つ固有ベクトルの同変関数を近似し、その安定性と高表現能を厳密に確立することを示した。
- 参考スコア（独自算出の注目度）: 109.8653020407373
- License:
- Abstract: Positional encodings (PEs) are essential for effective graph representation learning because they provide position awareness in inherently position-agnostic transformer architectures and increase the expressive capacity of Graph Neural Networks (GNNs). However, designing powerful and efficient PEs for graphs poses significant challenges due to the absence of canonical node ordering and the scale of the graph. {In this work, we identify four key properties that graph PEs should satisfy}: stability, expressive power, scalability, and genericness. We find that existing eigenvector-based PE methods often fall short of jointly satisfying these criteria. To address this gap, we introduce PEARL, a novel framework of learnable PEs for graphs. Our primary insight is that message-passing GNNs function as nonlinear mappings of eigenvectors, enabling the design of GNN architectures for generating powerful and efficient PEs. A crucial challenge lies in initializing node attributes in a manner that is both expressive and permutation equivariant. We tackle this by initializing GNNs with random node inputs or standard basis vectors, thereby unlocking the expressive power of message-passing operations, while employing statistical pooling functions to maintain permutation equivariance. Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power. Experimental evaluations show that PEARL outperforms lightweight versions of eigenvector-based PEs and achieves comparable performance to full eigenvector-based PEs, but with one or two orders of magnitude lower complexity. Our code is available at https://github.com/ehejin/Pearl-PE.
- Abstract（参考訳）: 位置エンコーディング(PE)は、本来位置に依存しないトランスフォーマーアーキテクチャにおける位置認識を提供し、グラフニューラルネットワーク(GNN)の表現能力を高めるため、効果的なグラフ表現学習に不可欠である。
しかし、グラフの高効率なPEを設計することは、標準ノードの順序付けやグラフのスケールの欠如によって大きな課題となる。
この研究において、我々は、グラフPEが満たすべき4つの重要な特性、すなわち安定性、表現力、スケーラビリティ、ジェネリックネスを識別する。
既存の固有ベクトルに基づくPE法は,これらの基準を満たさないことが多い。
このギャップに対処するために、グラフのための学習可能なPEの新しいフレームワークであるPEARLを紹介する。
我々の第一の洞察は、メッセージパッシングGNNが固有ベクトルの非線形マッピングとして機能し、強力で効率的なPEを生成するためのGNNアーキテクチャの設計を可能にすることである。
重要な課題は、表現的かつ置換的同値な方法でノード属性を初期化することである。
我々は,GNNをランダムなノード入力や標準基底ベクトルで初期化することにより,メッセージパス操作の表現力を解放し,統計プール関数を用いて置換等価性を維持する。
解析の結果、PEARLは線形複雑度を持つ固有ベクトルの同変関数を近似し、その安定性と高表現能を厳密に確立することを示した。
実験により、PEARLは固有ベクトルベースPEの軽量バージョンよりも優れ、完全固有ベクトルベースPEに匹敵する性能を得るが、1～2桁の複雑さで達成できることが示された。
私たちのコードはhttps://github.com/ehejin/Pearl-PE.comで公開されています。
関連論文リスト
- Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks [53.10674067060148]
共有インタラクション(SI)は、複数のノード間のノードのコントリビューションとインタラクションを定量化する。
GNNアーキテクチャを利用して、ノード埋め込みにおける相互作用の構造がグラフ予測のために保存されていることを示す。
任意の順序SIを正確に計算するための効率的なアプローチであるGraphSHAP-IQを導入する。
論文 参考訳（メタデータ） (2025-01-28T13:37:44Z) - LASE: Learned Adjacency Spectral Embeddings [7.612218105739107]
グラフ入力から結節隣接スペクトル埋め込み(ASE)を学習する。
LASEは解釈可能で、パラメータ効率が高く、未観測のエッジを持つ入力に対して堅牢である。
LASEレイヤは、Graph Convolutional Network (GCN)と完全に接続されたGraph Attention Network (GAT)モジュールを組み合わせる。
論文 参考訳（メタデータ） (2024-12-23T17:35:19Z) - What Are Good Positional Encodings for Directed Graphs? [13.076497906728333]
我々は、有向グラフに対するウォークカウントシーケンスの一般化であるウォークプロファイルの概念を導入する。
磁気ラプラシアン固有ベクトル系PEを拡張した新しいマルチq磁気ラプラシアンPEを提案する。
提案するPEの表現性を検証し,ネットワークのソート性向上に有効であることを示す。
論文 参考訳（メタデータ） (2024-07-30T15:38:14Z) - Long Range Graph Benchmark [32.317725340138104]
単にワンホップメッセージパッシングに頼るMP-GNNは、既存のグラフベンチマークでよく使われる。
ベースラインのGNNとGraph Transformerネットワークの両方をベンチマークし、長距離依存をキャプチャするモデルがこれらのタスクにおいて著しく優れていることを検証した。
論文 参考訳（メタデータ） (2022-06-16T13:33:22Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Graph Neural Networks with Learnable Structural and Positional
Representations [83.24058411666483]
任意のグラフの大きな問題は、ノードの標準位置情報の欠如である。
ノードの位置ノード(PE)を導入し、Transformerのように入力層に注入する。
両方のGNNクラスで学習可能なPEを考えると、分子データセットのパフォーマンスは2.87%から64.14%に向上する。
論文 参考訳（メタデータ） (2021-10-15T05:59:15Z) - 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) - Building powerful and equivariant graph neural networks with structural
message-passing [74.93169425144755]
本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。
まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。
次に,メッセージのパラメトリゼーション手法を提案する。
論文 参考訳（メタデータ） (2020-06-26T17:15:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。