A Weisfeiler–Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs

Md Abrar Jahin, Craig A Knoblock, Jay Pujara
Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026), PMLR 334(2):123-142, 2026.

Abstract

Graph foundation models (GFMs) equipped with global attention are increasingly used to learn representations of mixed-integer linear programs (MILPs), with the stated aim of capturing structural information beyond the locality of standard graph neural networks. We study the expressive power of these architectures through the lens of graph isomorphism testing and ask 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: for any parameter setting, any pair of 1-WL-equivalent MILP graphs receives an identical graph embedding. The result follows from a compositional analysis in which each architectural component is shown to be a symmetric multiset function and therefore to preserve 1-WL equivalence. We validate the characterization across ten architecturally diverse graph encoders, including Graphormer-, GraphGPS-, Set-Transformer-, and Gasse-style models. Across model capacities, graph scales, and pooling operators, all tested encoders map 1-WL-equivalent non-isomorphic graph pairs to numerically identical embeddings. We then analyze the consequences of this representation equivalence for downstream prediction: graph invariants that vary within a 1-WL equivalence class are not recoverable from the resulting representations. Finally, we localize the source of expressiveness beyond 1-WL to the input encoding rather than the attention mechanism. Random-walk positional encodings separate the constructed pairs, while additional constructions characterize the limits of this remedy. Together, these results provide a theoretical and empirical characterization of the expressive power of global-attention graph foundation models, together with an encoder-agnostic diagnostic for detecting 1-WL-induced representation equivalence.

Cite this Paper

BibTeX
@InProceedings{pmlr-v334-jahin26a, title = {A Weisfeiler{–}Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs}, author = {Jahin, Md Abrar and Knoblock, Craig A and Pujara, Jay}, booktitle = {Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026)}, pages = {123--142}, year = {2026}, editor = {Berman, Eddie and Bernárdez, Guillermo and Chen, Samantha and Cloninger, Alex and Doster, Timothy and Emerson, Tegan and Grigsby, J. Elisenda and Kvinge, Henry and Lawrence, Hannah and Marrinan, Tim and Myers, Audun and Papillon, Mathilde and Tahmasebi, Behrooz and Telyatnikov, Lev and Walters, Robin and Weber, Melanie and Xie, YuQing and Yeats, Eric}, volume = {334}, number = {2}, series = {Proceedings of Machine Learning Research}, month = {18--20 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v334/main/assets/jahin26a/jahin26a.pdf}, url = {https://proceedings.mlr.press/v334/jahin26a.html}, abstract = {Graph foundation models (GFMs) equipped with global attention are increasingly used to learn representations of mixed-integer linear programs (MILPs), with the stated aim of capturing structural information beyond the locality of standard graph neural networks. We study the expressive power of these architectures through the lens of graph isomorphism testing and ask 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: for any parameter setting, any pair of 1-WL-equivalent MILP graphs receives an identical graph embedding. The result follows from a compositional analysis in which each architectural component is shown to be a symmetric multiset function and therefore to preserve 1-WL equivalence. We validate the characterization across ten architecturally diverse graph encoders, including Graphormer-, GraphGPS-, Set-Transformer-, and Gasse-style models. Across model capacities, graph scales, and pooling operators, all tested encoders map 1-WL-equivalent non-isomorphic graph pairs to numerically identical embeddings. We then analyze the consequences of this representation equivalence for downstream prediction: graph invariants that vary within a 1-WL equivalence class are not recoverable from the resulting representations. Finally, we localize the source of expressiveness beyond 1-WL to the input encoding rather than the attention mechanism. Random-walk positional encodings separate the constructed pairs, while additional constructions characterize the limits of this remedy. Together, these results provide a theoretical and empirical characterization of the expressive power of global-attention graph foundation models, together with an encoder-agnostic diagnostic for detecting 1-WL-induced representation equivalence.} }
Endnote
%0 Conference Paper %T A Weisfeiler–Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs %A Md Abrar Jahin %A Craig A Knoblock %A Jay Pujara %B Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026) %C Proceedings of Machine Learning Research %D 2026 %E Eddie Berman %E Guillermo Bernárdez %E Samantha Chen %E Alex Cloninger %E Timothy Doster %E Tegan Emerson %E J. Elisenda Grigsby %E Henry Kvinge %E Hannah Lawrence %E Tim Marrinan %E Audun Myers %E Mathilde Papillon %E Behrooz Tahmasebi %E Lev Telyatnikov %E Robin Walters %E Melanie Weber %E YuQing Xie %E Eric Yeats %F pmlr-v334-jahin26a %I PMLR %P 123--142 %U https://proceedings.mlr.press/v334/jahin26a.html %V 334 %N 2 %X Graph foundation models (GFMs) equipped with global attention are increasingly used to learn representations of mixed-integer linear programs (MILPs), with the stated aim of capturing structural information beyond the locality of standard graph neural networks. We study the expressive power of these architectures through the lens of graph isomorphism testing and ask 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: for any parameter setting, any pair of 1-WL-equivalent MILP graphs receives an identical graph embedding. The result follows from a compositional analysis in which each architectural component is shown to be a symmetric multiset function and therefore to preserve 1-WL equivalence. We validate the characterization across ten architecturally diverse graph encoders, including Graphormer-, GraphGPS-, Set-Transformer-, and Gasse-style models. Across model capacities, graph scales, and pooling operators, all tested encoders map 1-WL-equivalent non-isomorphic graph pairs to numerically identical embeddings. We then analyze the consequences of this representation equivalence for downstream prediction: graph invariants that vary within a 1-WL equivalence class are not recoverable from the resulting representations. Finally, we localize the source of expressiveness beyond 1-WL to the input encoding rather than the attention mechanism. Random-walk positional encodings separate the constructed pairs, while additional constructions characterize the limits of this remedy. Together, these results provide a theoretical and empirical characterization of the expressive power of global-attention graph foundation models, together with an encoder-agnostic diagnostic for detecting 1-WL-induced representation equivalence.
APA
Jahin, M.A., Knoblock, C.A. & Pujara, J.. (2026). A Weisfeiler–Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs. Proceedings of the 2nd Conference on Topology, Algebra, and Geometry in Data Science(TAG-DS 2026), in Proceedings of Machine Learning Research 334(2):123-142 Available from https://proceedings.mlr.press/v334/jahin26a.html.

Related Material