AI summaryⓘ
The authors studied how well certain graph-based models, called graph foundation models (GFMs) with global attention, can tell apart different mixed-integer linear programs (MILPs). They found that these models, even with complex features, cannot distinguish graph structures that look the same to a known test called the one-dimensional Weisfeiler-Leman (1-WL) test. Their proof showed that all parts of these models treat graph information symmetrically, preserving this limitation. They also found that adding special input encodings can help a bit, but attention mechanisms alone don't overcome this problem. Overall, their work explains a fundamental limitation in how these models represent MILPs and offers a way to test for it.
Graph Foundation ModelsMixed-Integer Linear ProgramsGlobal AttentionGraph Neural NetworksWeisfeiler-Leman TestGraph IsomorphismPositional EncodingGraph RepresentationGraph EmbeddingsSymmetric Multiset Function
Authors
Md Abrar Jahin, Craig A. Knoblock, Jay Pujara
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.