論文の概要: Edge-Girth as a Structural Edge Feature for Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2609.01441v1
• Date: Tue, 01 Sep 2026 15:50:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-02 16:31:36.826632
• Title: Edge-Girth as a Structural Edge Feature for Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークの構造的エッジ特徴としてのエッジGirth
• Authors: Lilian Marey, Charlotte Laclau,
• Abstract要約: メッセージパッシングに基づくグラフニューラルネットワーク(GNN)は1次元Weisfeiler-Leman色補正テスト(1-WL)ほど強力ではないことが証明された。 一般的な治療は、前もって計算された構造記述子でノードやエッジの機能を増強し、多くの場合、三角形や長いサイクルのような固定された小さな部分グラフを数えている。 我々は、この選択を避ける記述子について研究する。エッジのエッジ幅は、それを通る最も短いサイクルの長さであり、その乗法性はそのような最も短いサイクルの数である。
• 参考スコア（独自算出の注目度）: 2.16169908192004
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNN) based on message passing are provably no more powerful than the one-dimensional Weisfeiler--Leman colour-refinement test (1-WL): two graphs it cannot tell apart receive identical representations, however deep or wide the network. A common remedy augments node or edge features with precomputed structural descriptors, most often counts of a fixed small subgraph such as triangles or longer cycles, but such counts require committing in advance to the size of the substructure counted, a choice usually made blind to the data. We study a descriptor that avoids this choice. The edge-girth of an edge is the length of a shortest cycle through it, and its multiplicity is the number of such shortest cycles; together they form a per-edge invariant that reports cycles of arbitrary length, computable exactly by a single breadth-first search per edge. Injected into a gated message-passing architecture, EGAGNN, it reaches a test MAE a factor three below the closest gated comparator on the ZINC-12k regression benchmark at 104k parameters; against bounded cycle-counting descriptors under the same architecture, it matches only a dictionary counting cycles up to length eight, using twice as many channels, while a dictionary capped at length four performs no better than no structural information at all. On graph discrimination we prove a matching limitation: on graphs where every edge sees the same number of shortest cycles of the same length, the descriptor becomes constant and any model built on it collapses back to the 1-WL bound. This holds without exception across all 400 pairs of the BREC benchmark: not one of the 90 such pairs is distinguished.
• Abstract（参考訳）: メッセージパッシングに基づくグラフニューラルネットワーク(GNN)は、1次元のWeisfeiler-Leman色補正テスト(1-WL):2つのグラフが同一表現を受け取らないが、ネットワークの深さや幅は広い。 一般的な治療は、事前に計算された構造記述子でノードまたはエッジの機能を増強し、多くの場合、三角形や長いサイクルのような固定された小さな部分グラフをカウントするが、そのようなカウントは、カウントされた部分構造のサイズに前もってコミットする必要がある。 我々はこの選択を避ける記述子を研究する。 エッジのエッジ幅は、最も短いサイクルの長さであり、その多重度は、そのような最も短いサイクルの数である。 ゲート型メッセージパスアーキテクチャであるEGAGNNに注入され、104kパラメータでZINC-12k回帰ベンチマークの最も近いゲート型コンパレータより3倍低い係数でテストMAEに達する。 グラフ判別では、全てのエッジが同じ長さの最も短いサイクルの数を同じ数と見るグラフにおいて、記述子は定数となり、その上に構築されたモデルは1-WL境界まで崩壊する。 これは、BRECベンチマークの400対全てに例外がなく、90対のうちの1つが区別されない。

関連論文リスト

• SEMIR: Topology-Preserving Graph Minors for Thin-Structure Segmentation [1.5222045235700188]
  SEMIRはピクセル格子をパラメータ化グラフマイナーに置き換えるフレームワークである。 軽量GNNは縮小グラフを分類し、正確なマップはピクセル解像度に予測を持ち上げる。 1つのパイプライン・アイデンティティ・アーキテクチャ-TTPLA(パワーライン)のドメイン固有のベースライン、CrackSeg9k(舗装クラック)、Dice、IoU、Boundary F1のSkyScapes Lane(空中マーキング)をマッチまたは越える。
  論文  参考訳（メタデータ） (2026-06-22T14:43:31Z)
• Bridging the Divide: End-to-End Sequence-Graph Learning [47.95529678412846]
  シーケンスとグラフは別の問題ではなく、同じデータセットの相補的な側面であると主張する。 BRIDGEは,シーケンスエンコーダとGNNを結合したエンドツーエンドアーキテクチャである。 BRIDGEは、静的GNN、時間グラフ法、およびランク付けと分類基準に基づくシーケンスのみのベースラインを一貫して上回ることを示す。
  論文  参考訳（メタデータ） (2025-10-29T03:06:54Z)
• Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations [5.193718340934995]
  MEGA-GNNは、マルチグラフ上のメッセージパッシングのための統一されたフレームワークである。 我々は, MEGA-GNN が置換同変であるだけでなく,エッジ上で厳密な全順序付けを与えられることも示す。 実験の結果、MEGA-GNNはアンチ・モニー・ロンダリングのデータセットで最先端のソリューションを最大13%上回っていることがわかった。
  論文  参考訳（メタデータ） (2024-11-29T20:15:18Z)
• Edge-Parallel Graph Encoder Embedding [0.0]
  One-Hot Graph Embedding (GEE) は1つの線形パスオーバーエッジを使用し、スペクトル埋め込みに収束する埋め込みを生成する。 本稿では,グラフのエッジ上で関数をマッピングし,ロックフリーなアトミックインストラクションを用いてデータ競合を防止するLigraグラフエンジンの並列プログラムを提案する。
  論文  参考訳（メタデータ） (2024-02-06T21:04:57Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。 本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。 これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
  論文  参考訳（メタデータ） (2023-10-14T07:02:54Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs [24.761152163389735]
  ランダムエッジ符号化(Random Edge Coding)と呼ばれる大きなラベル付きグラフを圧縮するためのワンショット方式を提案する。 実験によると、ランダムエッジ符号化は実世界のネットワークデータセット上での競合圧縮性能を実現することができる。
  論文  参考訳（メタデータ） (2023-05-16T12:23:18Z)
• DepGraph: Towards Any Structural Pruning [68.40343338847664]
  我々は、CNN、RNN、GNN、Transformersのような任意のアーキテクチャの一般的な構造解析について研究する。 本稿では,階層間の依存関係を明示的にモデル化し,包括的にグループ化してプルーニングを行う汎用かつ完全自動な手法であるemphDependency Graph(DepGraph)を提案する。 本研究では,画像用ResNe(X)t,DenseNet,MobileNet,Vision Transformer,グラフ用GAT,3Dポイントクラウド用DGCNN,言語用LSTMなど,さまざまなアーキテクチャやタスクに関する手法を広範囲に評価し,言語用LSTMと並行して示す。
  論文  参考訳（メタデータ） (2023-01-30T14:02:33Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE)。 まず,各エッジをトポロジや監督のためにのみ使用するエッジ分割手法を提案する。 監視エッジで接続されたペアと接続されていないペアの差を強調するために、さらにメッセージを重み付けして、その差を反映できる相対的なペアを強調します。
  論文  参考訳（メタデータ） (2022-12-25T23:19:56Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。 本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
  論文  参考訳（メタデータ） (2021-12-08T08:23:37Z)

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

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