論文の概要: What Are Good Positional Encodings for Directed Graphs?

• arxiv url: http://arxiv.org/abs/2407.20912v2
• Date: Fri, 4 Oct 2024 08:32:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-08 14:05:01.001993
• Title: What Are Good Positional Encodings for Directed Graphs?
• Title（参考訳）: 方向性グラフのための良い位置エンコーディングとは何か?
• Authors: Yinan Huang, Haoyu Wang, Pan Li,
• Abstract要約: 我々は、有向グラフに対するウォークカウントシーケンスの一般化であるウォークプロファイルの概念を導入する。 磁気ラプラシアン固有ベクトル系PEを拡張した新しいマルチq磁気ラプラシアンPEを提案する。 提案するPEの表現性を検証し,ネットワークのソート性向上に有効であることを示す。
• 参考スコア（独自算出の注目度）: 13.076497906728333
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Positional encodings (PEs) are essential for building powerful and expressive graph neural networks and graph transformers, as they effectively capture the relative spatial relationships between nodes. Although extensive research has been devoted to PEs in undirected graphs, PEs for directed graphs remain relatively unexplored. This work seeks to address this gap. We first introduce the notion of Walk Profile, a generalization of walk-counting sequences for directed graphs. A walk profile encompasses numerous structural features crucial for directed graph-relevant applications, such as program analysis and circuit performance prediction. We identify the limitations of existing PE methods in representing walk profiles and propose a novel Multi-q Magnetic Laplacian PE, which extends the Magnetic Laplacian eigenvector-based PE by incorporating multiple potential factors. The new PE can provably express walk profiles. Furthermore, we generalize prior basis-invariant neural networks to enable the stable use of the new PE in the complex domain. Our numerical experiments validate the expressiveness of the proposed PEs and demonstrate their effectiveness in solving sorting network satisfiability and performing well on general circuit benchmarks. Our code is available at https://github.com/Graph-COM/Multi-q-Maglap.
• Abstract（参考訳）: 位置エンコーディング(PE)は、ノード間の相対空間関係を効果的に捉えるため、強力で表現力のあるグラフニューラルネットワークとグラフトランスフォーマーを構築するために不可欠である。 無向グラフのPEについて広範な研究が行われてきたが、有向グラフのPEは比較的未探索のままである。 この研究はこのギャップに対処しようと試みている。 まず、有向グラフに対するウォークカウントシーケンスの一般化であるウォークプロファイルの概念を紹介する。 ウォークプロファイルは、プログラム解析や回路性能予測など、有向グラフ関連アプリケーションに不可欠な多くの構造的特徴を含んでいる。 歩行プロファイルの表現における既存のPE手法の限界を特定し,複数のポテンシャル因子を組み込むことで,磁気ラプラシア固有ベクトルに基づくPEを拡張した,新しいMulti-q Magnetic Laplacian PEを提案する。 新しいPEは、歩行プロファイルを確実に表現できる。 さらに,従来の基底不変ニューラルネットワークを一般化し,複雑な領域における新しいPEの安定した利用を可能にする。 提案するPEの表現性を検証し,ネットワークの整合性の解決と回路ベンチマークの高速化に有効であることを示す。 私たちのコードはhttps://github.com/Graph-COM/Multi-q-Maglapで利用可能です。

関連論文リスト

• Range-aware Positional Encoding via High-order Pretraining: Theory and Practice [14.521929085104441]
  大量のグラフデータに対する教師なし事前トレーニングは、ラベル付きデータが制限された実世界のアプリケーションでは不可欠である。 本稿では,多解像度構造情報をモデル化することに焦点を当てたグラフの事前学習戦略を提案する。 このアプローチはグラフ構造にのみ依存するが、ドメインに依存しず、さまざまなドメインのデータセットに適応可能である。
  論文  参考訳（メタデータ） (2024-09-27T19:53:10Z)
• Graph Positional and Structural Encoder [11.647944336315346]
  グラフエンコーダは、任意のGNNを増大させるために、リッチなPSE表現をキャプチャするように設計されている。 GPSEは複数のPSEに対して効率的な共通潜伏表現を学習し、高い転送性を持つ。 GPSEにより強化されたモデルは、明示的に計算されたPSEを使用するモデルよりも大幅に優れており、少なくとも他のモデルではその性能に匹敵することを示す。
  論文  参考訳（メタデータ） (2023-07-14T01:04:18Z)
• Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata [20.539191533339427]
  重み付きグラフウォーキングオートマトンに基づく新しいグラフPE, Graph Automaton PE(GAPE)を提案する。 GAPEの性能を機械翻訳とグラフ構造化の両方における他のPE方式と比較する。
  論文  参考訳（メタデータ） (2022-12-13T20:51:03Z)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  本稿では,グラフ間のGNNの事前学習プロセスの監視を目的とした,MentorGNNというエンドツーエンドモデルを提案する。 我々は、事前学習したGNNの一般化誤差に自然かつ解釈可能な上限を導出することにより、関係データ(グラフ)に対するドメイン適応の問題に新たな光を当てた。
  論文  参考訳（メタデータ） (2022-08-21T15:12:08Z)
• Affinity-Aware Graph Networks [9.888383815189176]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータを学ぶための強力なテクニックとして登場した。 グラフニューラルネットワークの特徴としてアフィニティ尺度の利用について検討する。 本稿では,これらの特徴に基づくメッセージパッシングネットワークを提案し,その性能を様々なノードおよびグラフ特性予測タスクで評価する。
  論文  参考訳（メタデータ） (2022-06-23T18:51:35Z)
• Handling Distribution Shifts on Graphs: An Invariance Perspective [78.31180235269035]
  我々は、グラフ上のOOD問題を定式化し、新しい不変学習手法である探索・拡張リスク最小化(EERM)を開発する。 EERMは、複数の仮想環境からのリスクの分散を最大化するために、敵対的に訓練された複数のコンテキストエクスプローラーを利用する。 理論的に有効なOOD解の保証を示すことによって,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-05T02:31:01Z)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  任意のグラフの大きな問題は、ノードの標準位置情報の欠如である。 ノードの位置ノード(PE)を導入し、Transformerのように入力層に注入する。 両方のGNNクラスで学習可能なPEを考えると、分子データセットのパフォーマンスは2.87%から64.14%に向上する。
  論文  参考訳（メタデータ） (2021-10-15T05:59:15Z)
• Simple Graph Convolutional Networks [72.92604941595019]
  単一層グラフ畳み込みネットワークで実装可能な単純なグラフ畳み込み演算子を提案する。 我々の畳み込み演算子は、文献における多くの提案よりも理論的に基礎を置いており、検討されたベンチマークデータセットに最先端の予測性能を示す。
  論文  参考訳（メタデータ） (2021-06-10T15:23:59Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Path Integral Based Convolution and Pooling for Graph Neural Networks [12.801534458657592]
  グラフの分類と回帰処理のための経路積分に基づくグラフニューラルネットワーク(PAN)を提案する。 PANは、さまざまなサイズと構造を持つ異なるグラフデータ用に調整可能な、汎用的なフレームワークを提供する。 実験結果から,PANは様々なグラフ分類/回帰タスクにおいて最先端の性能を達成することが示された。
  論文  参考訳（メタデータ） (2020-06-29T16:20:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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