Technical Summary: Detecting Differences Is Not Understanding Structure

Problem Statement

While Large Language Models (LLMs) have demonstrated impressive performance on diverse reasoning tasks, their capacity for genuine structural reasoning in graph domains remains unclear. A fundamental requirement for valid structural reasoning is permutation invariance: the ability to recognize that two graphs are structurally identical (isomorphic) regardless of how their nodes are labeled or ordered.

The paper investigates whether LLMs truly understand graph isomorphism or if their high accuracy on standard benchmarks is an artifact of exploiting surface-level patterns in serialized representations. If an LLM fails to maintain consistent judgments when identical graphs are presented with permuted node labels, it suggests the model is detecting serialization differences rather than reasoning about abstract topology.

Methodology

The study employs a two-phase experimental design to evaluate three widely used LLMs: GPT-4o-mini (OpenAI), Gemini 2.5 Flash (Google), and Llama 3.3 70B Instruct (via Together AI).

Experimental Setup

1. Serialization Formats: Graphs were presented in three standard formats to test format sensitivity:
   • Edge List: Simple node pairs.
   • Edge Index: Source–target column vectors.
   • Adjacency Matrix: Binary connectivity matrices.
2. Prompting Strategies:
   • Zero-shot: Minimal task instructions without reasoning guidance.
   • Instructed: Explicit definitions of graph isomorphism and reasoning steps.
3. Experiment 1: Non-Isomorphism Detection:
   • The models were tested on 400 pairs of non-isomorphic graphs across four difficulty categories:
     • Category 1: Different node counts.
     • Category 2: Different edge counts.
     • Category 3: Different node and edge counts.
     • Category 4: Graphs indistinguishable by the 1-Weisfeiler-Lehman (1-WL) test (same node/edge counts and degree sequences) but non-isomorphic due to complex structural properties.
4. Experiment 2: Permutation Invariance:
   • The models were tested on 400 pairs of isomorphic graphs where one graph was a random permutation of the other's node labels.
   • The goal was to determine if the models correctly identified these pairs as isomorphic despite the label changes.

Key Results

High Accuracy on Standard Detection (Experiment 1)

In the first experiment, all three models achieved near-perfect accuracy (96–100%) across most categories and formats. Notably, they performed well even on Category 4, where graphs are indistinguishable by the 1-WL hierarchy and standard Graph Neural Networks (GNNs) typically struggle.

• Gemini maintained 100% accuracy across all conditions.
• OpenAI and Llama showed minor drops in specific conditions (e.g., OpenAI dropped to 88.0% on Category 4 with instructed prompting; Llama dropped to 96.0% on Category 2 zero-shot).

Failure of Permutation Invariance (Experiment 2)

In the second experiment, the models collapsed when faced with permuted node labels on isomorphic graphs:

• OpenAI: Accuracy ranged from 0.0% to 18.0%.
• Gemini: Accuracy ranged from 0.0% to 0.2%.
• Llama: Accuracy ranged from 2.0% to 39.2%.
• Observation: Performance varied significantly by serialization format, suggesting the models rely on input patterns (e.g., specific node index co-occurrences) rather than topology. Even "Instructed" prompting, which explicitly reminded models of permutation invariance, failed to produce robust reasoning.

Key Contributions

The paper makes three primary contributions:

1. Evaluation Protocol: Introduction of a simple protocol to test permutation invariance in LLM-based graph reasoning.
2. Empirical Evidence: Demonstration that while LLMs achieve high accuracy on graph isomorphism detection, they exhibit poor robustness to arbitrary node relabeling across various prompting strategies and serialization formats.
3. Methodological Argument: The assertion that invariance-based evaluations must complement accuracy metrics when assessing LLMs on graph-structured tasks, as high accuracy alone does not prove structural understanding.

Significance and Claims

The paper concludes that the success of LLMs on graph reasoning benchmarks is illusory. The models appear to exploit patterns in serialized representations (such as specific node label conventions or positional biases) rather than performing genuine topological reasoning.

• Implication for Practitioners: LLMs should not be relied upon for structure-critical graph reasoning tasks where robustness to node relabeling is required.
• Future Directions: The authors suggest focusing on developing permutation-invariant serialization methods that capture rich topological properties. They also advocate for the inclusion of invariance-based evaluations in standard benchmarking.
• Limitations: The study is limited to three specific LLMs and three serialization methods. The authors note that the mechanistic origins of this failure (whether due to fundamental symbolic reasoning limits or pretraining statistical patterns) remain an open question for future research. They also acknowledge that factors like tokenization choices and specific graph structural properties (e.g., girth, symmetry) were not systematically ablated.