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

Md Abrar Jahin; Craig A. Knoblock; Jay Pujara

cs.LGJul 20, 2026

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

Authors: Md Abrar Jahin, Craig A. Knoblock, Jay Pujara

Organizations: University of Southern California, Los Angeles, CA 90089, USA · USC Information Sciences Institute, Marina del Rey, CA 90292, USA

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.

Explore similar work

Sep 14, 2026cs.SI

On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman

Whitney's theorem allows isomorphism testing for connected simple graphs, apart from

K_3

and

K_{1,3}

, to be formulated as distinguishing their line graphs. However, the relation between fixed-dimensional Weisfeiler--Leman (WL) expressivity on line graphs and on their roots remains unresolved. We study this relation through Implicit Line-Graph WL (ILG-

k

-WL), which is exactly

k

-WL on

L(G)

, executed over the edges of

G

with line-graph relations derived from endpoint incidence and without explicitly constructing

L(G)

. On the Whitney-general class, the relation between root-domain and line-graph WL depends on

k

. For

k=1,2

, ILG-

k

-WL adds no distinguishing power beyond root-domain

1

-WL and misses some pairs that

1

-WL separates. For

k=3

, we prove the backward containment

L(G)\equiv_{3\text{-WL}}L(H)\Rightarrow G\equiv_{3\text{-WL}}H

. Strongly regular witness pairs, including the Shrikhande/rook pair, show that ILG-

3

-WL is strictly more expressive than

3

-WL. The backward containment also extends to disconnected graphs with no isolated vertices when every connected component is Whitney-general. Deterministic ILG-

3

-WL separates all three substructure-counting witness pairs, all

105

pairs in SR25, and

359

400

BREC pairs. An untrained dense ILG-

3

-GNN gives the same pairwise verdicts on these evaluations.

Fan Yang

Graph Theory Product Spaces Expressivity

Ask PDF

Jan 8, 2026cs.AI

A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention

Mixed-integer linear programming (MILP) is a foundational framework for combinatorial optimization across science and engineering, but remains hard to solve at scale due to NP-hardness. Recent learning-based methods typically model MILP instances as variable-constraint bipartite graphs and use Graph Neural Networks (GNNs) for representation learning, yet their locality limits representation power. We propose an attention-driven neural backbone that adopts an element-centric view of variables and constraints, with dual attention performing parallel intra-type self-attention and inter-type cross-attention. Across three representative tasks at the instance, element, and solving-state levels, our model consistently outperforms conventional GNN-based architectures, highlighting attention-based, element-centric modeling as a powerful foundation for learning-enhanced combinatorial optimization.

Peixin Huang, Yaoxin Wu, Yining Ma +3

Mixed-Integer Programming Combinatorial Optimization Graph Neural Networks Neural Network Optimization Multilayer Perceptrons Molecular Dynamics

Ask PDF

May 11, 2026cs.LG

Teaching LLMs to See Graphs: Unifying Text and Structural Reasoning

Using Large Language Models (LLMs) to process graph-structured data is an active research area, yet current state-of-the-art approaches typically rely on multi-step pipelines with Graph Neural Network (GNN) encoders that compress rich textual attributes into solitary tokens, creating a significant semantic bottleneck. In this paper, we introduce the Graph Transformer Language Model (GTLM), a novel architecture that enables pretrained LLMs to natively process graph topologies while entirely eliminating this compressive bottleneck. GTLM is exceptionally parameter-efficient: by injecting graph-aware attention biases directly into the LLM's attention modules, it introduces only 0.015% additional parameters relative to the base model. We theoretically prove that our bidirectional attention prefix preserves node permutation equivariance while maintaining exact backward compatibility with the pretrained base model. Extensive evaluations demonstrate that a 1B-parameter GTLM matches or exceeds the performance of 7B-parameter state-of-the-art models on standard Text-Attributed Graph benchmarks, while significantly surpassing baselines on GraphQA. Finally, we demonstrate that GTLM attention heads implicitly learn to simulate message passing, explaining its superior performance on algorithmic tasks. This paradigm shift enables true algorithmic reasoning within LLMs and provides a scalable foundation for next-generation GraphRAG and relational deep learning.

Dario Vajda

Graph-Based Retrieval Augmented Generation Graph Language Models Relational Deep Learning Bottlenecks

Ask PDF