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

• arxiv url: http://arxiv.org/abs/2407.20912v1
• Date: Tue, 30 Jul 2024 15:38:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-31 16:40:36.054702
• Title: What Are Good Positional Encodings for Directed Graphs?
• Title（参考訳）: 方向性グラフのための良い位置エンコーディングとは何か?
• Authors: Yinan Huang, Haoyu Wang, Pan Li,
• Abstract要約: 本研究では,所望の有向空間関係を表現するために表現可能な有向グラフのためのPEの設計について検討する。 磁気ラプラシアンPEを複数のポテンシャル因子で拡張するMulti-q Magnetic Laplacian PEを提案する。 数値実験により, 安定なニューラルネットワークを用いたマルチq磁気ラプラシアンPEの有効性を実証した。
• 参考スコア（独自算出の注目度）: 13.076497906728333
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Positional encodings (PE) for graphs are essential in constructing powerful and expressive graph neural networks and graph transformers as they effectively capture relative spatial relations between nodes. While PEs for undirected graphs have been extensively studied, those for directed graphs remain largely unexplored, despite the fundamental role of directed graphs in representing entities with strong logical dependencies, such as those in program analysis and circuit designs. This work studies the design of PEs for directed graphs that are expressive to represent desired directed spatial relations. We first propose walk profile, a generalization of walk counting sequence to directed graphs. We identify limitations in existing PE methods, including symmetrized Laplacian PE, Singular Value Decomposition PE, and Magnetic Laplacian PE, in their ability to express walk profiles. To address these limitations, we propose the Multi-q Magnetic Laplacian PE, which extends Magnetic Laplacian PE with multiple potential factors. This simple variant turns out to be capable of provably expressing walk profiles. Furthermore, we generalize previous basis-invariant and stable networks to handle complex-domain PEs decomposed from Magnetic Laplacians. Our numerical experiments demonstrate the effectiveness of Multi-q Magnetic Laplacian PE with a stable neural architecture, outperforming previous PE methods (with stable networks) on predicting directed distances/walk profiles, sorting network satisfiability, and on general circuit benchmarks. Our code is available at https://github.com/Graph-COM/Multi-q-Maglap.
• Abstract（参考訳）: グラフの位置エンコーディング(PE)は、ノード間の相対空間関係を効果的に捉えるために、強力で表現力のあるグラフニューラルネットワークとグラフトランスフォーマーを構築するのに不可欠である。 無向グラフのPEは広く研究されているが、有向グラフのPEは、プログラム解析や回路設計のような強い論理的依存を持つエンティティを表現する上で、有向グラフの基本的な役割にもかかわらず、ほとんど探索されていない。 本研究では,所望の有向空間関係を表現するために表現可能な有向グラフのためのPEの設計について検討する。 まず,方向グラフに対する歩行数列の一般化である歩行プロファイルを提案する。 既存のPE法では,歩行プロファイルの表現能力において,シンメトリゼーションされたラプラシアンPE,特異値分解PE,磁気ラプラシアンPEなどの制限が認められている。 これらの制約に対処するため,複数のポテンシャル因子を持つ磁気ラプラシアンPEを拡張したMulti-q Magnetic Laplacian PEを提案する。 この単純な変種は、歩行プロファイルを確実に表現できることが判明した。 さらに、磁気ラプラシアンから分離された複素領域PEを扱うために、以前の基底不変および安定なネットワークを一般化する。 数値実験により,マルチq磁気ラプラシアン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)

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

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