論文の概要: A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs
- arxiv url: http://arxiv.org/abs/2607.17570v1
- Date: Mon, 20 Jul 2026 05:29:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-21 18:48:37.507508
- Title: A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs
- Title（参考訳）: 混合整数線形計画のためのグローバルアテンショングラフ変換器のWeisfeiler-Lemanによる評価
- Abstract要約: 世界的注目を集めるグラフ基礎モデル(GFM)は、混合整数線形プログラム(MILP)の表現に益々使われている。
グラフアイソモーフィズムテストにより,それらの表現力について検討し,どのMILPインスタンスを同一表現にマッピングするかを問う。
- 参考スコア（独自算出の注目度）: 11.365651352111769
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph foundation models (GFMs) with global attention are increasingly used to represent mixed-integer linear programs (MILPs), aiming to capture structure beyond the locality of standard graph neural networks. We study their expressive power through graph isomorphism testing, asking which MILP instances they map to identical representations. We prove that a broad class of hierarchical graph transformers combining global linear attention, edge-weighted cross-attention, and bipartite message passing is bounded by the one-dimensional Weisfeiler-Leman (1-WL) test: under any parameter setting, 1-WL-equivalent MILP graphs receive identical graph embeddings. Our compositional proof shows that each architectural component is a symmetric multiset function and thus preserves 1-WL equivalence. We validate this characterization across ten diverse graph encoders, including Graphormer-, GraphGPS-, Set-Transformer-, and Gasse-style models. Across model capacities, graph scales, and pooling operators, every tested encoder maps 1-WL-equivalent non-isomorphic graph pairs to numerically identical embeddings. Consequently, graph invariants that vary within a 1-WL equivalence class cannot be recovered from these representations. We further show that expressiveness beyond 1-WL arises from input encoding rather than attention: random-walk positional encodings separate the constructed pairs, while additional constructions expose the limits of this remedy. These results characterize the expressive power of global-attention GFMs and provide an encoder-agnostic diagnostic for detecting 1-WL-induced representation equivalence.
- Abstract（参考訳）: グラフ基盤モデル(GFM)は、標準グラフニューラルネットワークの局所性を超えた構造を捉えることを目的として、MILP(mixed-integer linear program)の表現にますます使われるようになっている。
グラフアイソモーフィズムテストにより,それらの表現力について検討し,どのMILPインスタンスを同一表現にマッピングするかを問う。
一次元Weisfeiler-Leman (1-WL) テストにより, 大域的線形注意, エッジ重み付きクロスアテンション, 二部的メッセージパッシングを結合した階層型グラフトランスフォーマーが有界であることが証明された。
構成的証明は、各アーキテクチャ成分が対称な多重集合関数であることを示し、したがって1-WL同値性を保持する。
この特徴は、Graphormer-, GraphGPS-, Set-Transformer-, Gasse-style modelを含む10種類のグラフエンコーダで検証する。
モデル容量、グラフスケール、プール演算子全体にわたって、テストエンコーダは1-WL-等価な非同型グラフ対を数値的に同一の埋め込みにマップする。
したがって、1-WL同値類で異なるグラフ不変量はこれらの表現から回復できない。
さらに、1-WLを超える表現性は、注意よりも入力エンコーディングから生じることを示す:ランダムウォーク位置エンコーディングは、構築されたペアを分離する一方、追加構成は、この治療の限界を露呈する。
これらの結果は、グローバルアテンションGFMの表現力の特徴であり、1-WLによる表現等価性を検出するエンコーダに依存しない診断を提供する。
関連論文リスト
- Generative Diffusion Models of Stochastic Graph Signals [74.4097723209053]
本稿では,条件付きグラフ信号生成モデルの問題に取り組み,単一の拡散フレームワークを用いてそれらに取り組む。
グラフトポロジとノード機能側情報に基づいて直接条件付きグラフ信号を描画するグラフニューラルネットワーク(GNN)によりパラメータ化された逆拡散過程を学習する。
本稿では,株価予測と最適無線リソース割り当てという2つの生成課題について,両領域で広範囲に数値計算を行った。
論文 参考訳（メタデータ） (2026-07-07T22:02:13Z) - Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
本稿では,グラフ畳み込みフィルタが生成するノイズ測定から有向ネットワークを推定する問題に対処する。
また、上記のステップを交互に交互に組み合わせて、サンプルの複雑さを向上する結合グラフフィルタとトポロジー同定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-06-25T18:25:57Z) - Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models [25.936601292112844]
ノードレベルのタスクのためのグラフ基盤モデルを第一原理から設計するためのレシピを提案する。
本研究の基盤となる重要な要素は,グラフ基盤モデルが尊重すべき対称性を体系的に調査することである。
我々は29の実世界のノード分類データセットに関する広範な実験を通して、我々のアプローチを検証する。
論文 参考訳（メタデータ） (2025-06-17T08:05:08Z) - What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
自己アテンションと位置エンコーディングを組み込んだグラフトランスフォーマーは、さまざまなグラフ学習タスクのための強力なアーキテクチャとして登場した。
本稿では,半教師付き分類のための浅いグラフ変換器の理論的検討について紹介する。
論文 参考訳（メタデータ） (2024-06-04T05:30:16Z) - Topology-Informed Graph Transformer [7.193109202139812]
グラフアイソモーフィズムの検出における識別力とグラフ変換器全体の性能を両立させる新しい変換器である「トポロジーインフォーマグラフ変換器(TIGT)」について検討した。
TIGTは4つの構成要素から構成される: 非同型普遍被覆を用いた位相的位置埋め込み層はグラフの巡回部分グラフに基づいて一意なグラフ表現を保証する。
TIGTは、グラフの同型クラスを識別することを目的とした合成データセットの分類において、従来のグラフ変換器よりも優れている。
論文 参考訳（メタデータ） (2024-02-03T03:17:44Z) - Isomorphic-Consistent Variational Graph Auto-Encoders for Multi-Level
Graph Representation Learning [9.039193854524763]
本稿では,タスク非依存グラフ表現学習のためのアイソモルフィック-一貫性VGAE(IsoC-VGAE)を提案する。
まず、同型整合性を維持する理論的保証を提供するための復号法を考案する。
次に,逆グラフニューラルネットワーク(Inv-GNN)デコーダを直感的な実現法として提案する。
論文 参考訳（メタデータ） (2023-12-09T10:16:53Z) - Discrete Graph Auto-Encoder [52.50288418639075]
離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。
まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。
2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
論文 参考訳（メタデータ） (2023-06-13T12:40:39Z) - Beyond 1-WL with Local Ego-Network Encodings [0.42970700836450487]
Ego-networksはWeisfeiler-Lehman (1-WL) テストよりも高い表現性を持つ任意のグラフの構造的符号化スキームを作成できることを示す。
我々は,ego-networksをスパースベクトルに符号化することで,ノード表現を増強する機能を前処理で生成するIGELを紹介した。
論文 参考訳（メタデータ） (2022-11-27T18:14:03Z) - Representation Power of Graph Neural Networks: Improved Expressivity via
Algebraic Analysis [124.97061497512804]
標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。
また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
論文 参考訳（メタデータ） (2022-05-19T18:40:25Z) - Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。
GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
論文 参考訳（メタデータ） (2022-05-07T04:11:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。