A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs
作者: Md Abrar Jahin, Craig A. Knoblock, Jay Pujara
分类: cs.LG
发布日期: 2026-07-20
备注: Accepted to Topology, Algebra, and Geometry in Data Science (TAG-DS) 2026 (20 pages, 10 figures) [Lightning Oral Presentation]
💡 一句话要点
提出图基础模型以解决混合整数线性规划的表达能力问题
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 图基础模型 混合整数线性规划 全局注意力 图神经网络 表达能力 Weisfeiler-Leman测试
📋 核心要点
- 现有的图神经网络在处理混合整数线性规划时，难以捕捉全局结构信息，导致表达能力受限。
- 本文提出了一种结合全局线性注意力和边加权交叉注意力的层次图变换器，能够有效捕捉图的全局特征。
- 实验结果表明，所有测试的图编码器在1-WL等价的非同构图对上均产生相同的嵌入，验证了模型的表达能力和局限性。
📝 摘要（中文）
图基础模型（GFM）结合全局注意力机制在表示混合整数线性规划（MILP）中越来越受到关注，旨在捕捉超越标准图神经网络的局部结构。本文通过图同构测试研究其表达能力，证明了一类结合全局线性注意力、边加权交叉注意力和二分消息传递的层次图变换器受限于一维Weisfeiler-Leman（1-WL）测试：在任何参数设置下，1-WL等价的MILP图会接收相同的图嵌入。我们的组合证明显示，每个架构组件都是对称多重集函数，从而保持1-WL等价性。我们在十种不同的图编码器上验证了这一特征，结果表明所有测试的编码器将1-WL等价的非同构图对映射为数值上相同的嵌入。
🔬 方法详解
问题定义：本文旨在解决图基础模型在表示混合整数线性规划（MILP）时的表达能力不足问题，尤其是如何捕捉全局结构信息。现有方法多依赖局部特征，难以处理复杂的图结构。
核心思路：论文提出了一种新的层次图变换器架构，结合全局线性注意力、边加权交叉注意力和二分消息传递，旨在通过这些组件的组合来增强模型的表达能力。
技术框架：整体架构包括多个模块：首先，通过全局线性注意力捕捉图的全局特征；其次，利用边加权交叉注意力增强节点间的信息传递；最后，采用二分消息传递机制进一步优化信息流动。
关键创新：最重要的技术创新在于证明了该架构的表达能力受限于1-WL测试，且每个组件均为对称多重集函数，从而保持1-WL等价性。这一发现揭示了全局注意力机制的局限性。
关键设计：在参数设置上，论文探讨了不同的注意力机制和消息传递策略，使用随机游走位置编码来分离构造的图对，同时揭示了这种设计的局限性。
🖼️ 关键图片
📊 实验亮点
实验结果显示，所有测试的图编码器在1-WL等价的非同构图对上均产生相同的嵌入，验证了模型的表达能力。具体而言，随机游走位置编码能够有效区分构造的图对，展示了模型在不同参数设置下的稳定性。
🎯 应用场景
该研究的潜在应用领域包括优化问题、运筹学和机器学习中的图表示学习。通过提高图基础模型的表达能力，能够更有效地解决复杂的混合整数线性规划问题，进而推动相关领域的研究和应用发展。
📄 摘要（原文）
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.