論文の概要: On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman
- arxiv url: http://arxiv.org/abs/2609.16412v1
- Date: Mon, 14 Sep 2026 22:34:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-16 14:56:08.257329
- Title: On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman
- Title（参考訳）: インシシットライングラフ高次ワイスフェイラの表現力について-リーマン
- Abstract要約: 線形グラフ上の固定次元Weisfeiler--Leman(WL)表現性とそれらの根との関係について検討する。
ILG-$3$-WLは$3$-WLより厳密に表現力が高いことを示す。
- 参考スコア（独自算出の注目度）: 2.6986809342283262
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Whitney's theorem allows isomorphism testing for connected simple graphs, apart from $K_3$ and $K_{1,3}$, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We study this relation through Implicit Line-Graph WL (ILG-$k$-WL), which is exactly $k$-WL on $L(G)$, executed over the edges of $G$ with line-graph relations derived from endpoint incidence and without explicitly constructing $L(G)$. On the Whitney-general class, the relation between root-domain and line-graph WL depends on $k$. For $k=1,2$, ILG-$k$-WL adds no distinguishing power beyond root-domain $1$-WL and misses some pairs that $1$-WL separates. For $k=3$, we prove the backward containment $L(G)\equiv_{3\text{-WL}}L(H)\Rightarrow G\equiv_{3\text{-WL}}H$. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG-$3$-WL is strictly more expressive than $3$-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG-$3$-WL separates all three substructure-counting witness pairs, all $105$ pairs in SR25, and $359$ of $400$ BREC pairs. An untrained dense ILG-$3$-GNN gives the same pairwise verdicts on these evaluations.
- Abstract（参考訳）: ホイットニーの定理は、連結単純グラフに対する同型テストを可能にし、$K_3$と$K_{1,3}$はそれらの線グラフの区別として定式化される。
しかし、線グラフとその根上の固定次元Weisfeiler--Leman (WL) 表現との関係は未解決のままである。
Inlicit Line-Graph WL (ILG-$k$-WL) は$L(G)$上で正確に$k$-WLであり、エンドポイントのインシデントから導かれる線グラフ関係を持ち、$L(G)$を明示的に構成することなく$G$のエッジ上で実行される。
ホイットニー一般類では、ルート領域と線グラフ WL の関係は$k$に依存する。
$k=1,2$の場合、ICG-$k$-WLはルートドメインの$$-WL以上の区別力を持たず、$-WLが分離するいくつかのペアを逃す。
k=3$ の場合、後方の包含 $L(G)\equiv_{3\text{-WL}}L(H)\Rightarrow G\equiv_{3\text{-WL}}H$ を証明する。
Shrikhande/rook のペアを含む、厳密な定期的な目撃者ペアは、ICG-$3$-WL が$3$-WL よりも厳密に表現可能であることを示している。
後方の包含は、すべての連結成分がホイットニー一般であるとき、孤立頂点を持たない非連結グラフにも拡張される。
決定論的ICG-$3$-WLは、3つのサブストラクチャカウントの証人ペア、全てSR25の105ドルペア、そして359ドル400ドルのBRECペアを分離する。
トレーニングされていない高密度IGG-$3$-GNNは、これらの評価について同じペアワイズな評価を与える。
関連論文リスト
- DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
本稿では,グラフ内のエッジの構造的類似性を洗練し,標準指紋を生成するフレームワークDRESSを紹介する。
フィンガープリントは構成上は同型不変であり、数値的には安定である(すべての値は$[0,2]$)。
$-DRESSは、包括的なStrongly Regular Graphベンチマークで7,983グラフを実証的に分離し、反復削除(k$-DRESS)が階段を登り、各深さk$で$(k+2)$-WLを達成する。
論文 参考訳（メタデータ） (2026-02-24T12:18:42Z) - Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts [3.652509571098291]
微分プライベート (DP) 合成グラフ $G'$ を、任意のグラフ $G'$ のすべてのカットの三角形-モチーフサイズをよく近似する問題について検討する。
このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。
論文 参考訳（メタデータ） (2025-07-20T06:20:53Z) - Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
大規模言語モデル(LLM)は、特に知識集約的なタスクにおいて幻覚に悩まされる。
既存の研究は、外部知識コーパスから取得した個々のテキスト単位でLLMを拡張することを提案する。
本稿では,グラフを反復的に推論することで,LLMをグラフで拡張するためのGraph Chain-of-thinkt (Graph-CoT) というフレームワークを提案する。
論文 参考訳（メタデータ） (2024-04-10T15:41:53Z) - Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning [17.646846505225735]
グラフ同型テストの新しい階層構造と対応するGNNフレームワークである$r$-$ell$MPNNを導入し、最大長さ$r + 2$までサイクルをカウントできる。
特に、$r$-$ell$WL がサクタスグラフの準同型を数えることができることを示す。
提案した$r$-$ell$MPNNの複数の合成データセットに対する表現力とカウント力を実証的に検証し,様々な実世界のデータセットに対する最先端の予測性能を示す。
論文 参考訳（メタデータ） (2024-03-20T16:58:28Z) - Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test [58.1543112860658]
グラフ機械学習実践者の表現力概念化と$k$-WLとの相違を明らかにする。
ベンチマークに基づく表現力の拡張的定義と測定について論じる。
論文 参考訳（メタデータ） (2023-07-11T20:06:12Z) - Extending the Design Space of Graph Neural Networks by Rethinking
Folklore Weisfeiler-Lehman [66.23316415757456]
近年、グラフニューラルネットワーク(GNN)の最も人気のあるフレームワークとして、メッセージパッシングニューラルネットワーク(MPNN)が登場している。
しかし、その表現力は1次元のWeisfeiler-Lehman (1-WL) テストによって制限される。
我々は、任意の同変集合をすべてのノードの代わりに隣人と考える拡張、$(k,t)$-FWLを提案する。
N$2-GNN は ZINC-Subset (0.059) で記録破りの結果を達成し、以前の SOTA の成績を 10.6% 上回った。
論文 参考訳（メタデータ） (2023-06-05T21:35:32Z) - Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points [45.15780579276503]
Wesfeiler--Lehman テストが完全距離グラフで表されるユークリッド点の雲に対して完備であるときの研究を行う。
$d$次元ユークリッド空間の任意の2つの非等尺点雲を区別するのに十分な次元はいくつあるか。
我々の主な結果は、$(d-1)$-dimensional WL テストが$d$-dimensional Euclidean 空間の点雲に対して完備であり、任意の$dge 2$ に対して完備であり、テストサッフィスを3回だけ繰り返すことである。
論文 参考訳（メタデータ） (2023-03-22T18:23:24Z) - WL meet VC [9.468816647649104]
本稿では,Vapnik-Chervonenkis(VC)次元理論のレンズによるグラフニューラルネットワーク(GNN)の表現力について検討する。
我々は、GNNのVC次元と1text-mathsfWL$およびGNNのVC次元によって生成される色数を用いて、GNNのVC次元の上限を導出する。
論文 参考訳（メタデータ） (2023-01-26T11:29:36Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。
境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。
治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文 参考訳（メタデータ） (2022-08-12T15:05:07Z) - Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link
Prediction [61.01337335214126]
グラフニューラルネットワーク(GNN)のリンク予測
リンク予測のためのほとんどの既存のGNNは、1次元Weisfeiler-Lehman (1-WL) テストに基づいている。
テキスト2次元Weisfeiler-Lehman (2-WL) テストに基づいて,ノード対(リンク)表現を直接取得可能な,まったく異なるアプローチを提案する。
論文 参考訳（メタデータ） (2022-06-20T04:50:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。