Search papers, labs, and topics across Lattice.
This paper investigates the expressive power of global-attention graph transformers (GFMs) in the context of mixed-integer linear programs (MILPs) by employing graph isomorphism testing. The authors prove that a significant class of hierarchical graph transformers is limited by the one-dimensional Weisfeiler-Leman (1-WL) test, meaning that MILP graphs that are 1-WL-equivalent yield identical embeddings regardless of the model's parameters. Their findings reveal that certain graph invariants cannot be distinguished by these models, highlighting the constraints of current GFM architectures in capturing the full complexity of MILP structures.
Identical embeddings for non-isomorphic graphs reveal the limitations of global-attention graph transformers in capturing the nuanced structure of mixed-integer linear programs.
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.
