TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Message-passing GNNs cannot distinguish beyond one-dimensional Weisfeiler–Leman

Statement

Let $G, H$ be finite vertex-labeled simple undirected graphs with labels in a common set, and let a depth- $K$ aggregation-based message-passing graph neural network use the same initial embedding, layer maps, and graph readout on both graphs. If one-dimensional Weisfeiler–Leman color refinement has equal graph color multisets on $G$ and $H$ at every round $0, \dots, K$ , then the network gives the same graph output on $G$ and $H$ . Equivalently, whenever this network distinguishes the pair, one-dimensional Weisfeiler–Leman distinguishes the pair at some round at most $K$ .

Statement references

finite vertex-labeled graphs and neighborhoods

finite multisets and multiplicities

shared aggregation, update, and graph-readout maps

round colors and graph color multisets

Xu, Hu, Leskovec, and Jegelka, “How Powerful are Graph Neural Networks?”, Lemma 2

Morris et al., “Weisfeiler and Leman Go Neural,” §3, Theorem 1

Li and Leskovec, Graph Representation Learning, Chapter 5 §5.3.3, Theorem 5.2

Facts & Assumptions

Given: The two finite labeled graphs, their equal 1-WL color multisets through round $K$ , and one shared depth- $K$ message-passing GNN as in the Statement. Prove its graph outputs agree.

[F1]

Aggregation-based message-passing graph neural networks: Each layer applies the same aggregation function to the multiset of neighbor states and then the same update function to the center state and aggregate.

[F2]

Finite-round one-dimensional Weisfeiler–Leman color refinement: Each next WL color is the ordered pair of the current color and the multiset of current neighbor colors; the graph color multiset records every vertex color with multiplicity.

[F3]

Finite multisets as finitely supported multiplicity functions: A finite multiset is its multiplicity function, so applying a function to each occurrence preserves equality of multisets.

[F4]

Aggregation-based message-passing graph neural networks: The graph readout is a function of the multiset of final node states.

Proof

1.1givenF1F2inductionalgebra

By induction on $t = 0, \dots, K$ , equal round- $t$ WL colors of vertices from either graph imply equal GNN states after $t$ layers. At $t = 0$ , the shared initial embedding gives this implication. If it holds at $t$ and two vertices have equal round- $(t + 1)$ colors, [F2] says their center colors and neighbor-color multisets agree. By the induction hypothesis, equal neighbor colors have equal GNN states; applying this correspondence occurrence by occurrence gives equal neighbor-state multisets. The shared aggregation and update functions in [F1] therefore give equal next-layer states. Thus a well-defined map from each round- $t$ color occurring in either graph to its common GNN state exists.

2.1givenF2F3F4step 1.1algebra∎

At round $K$ , the assumed equal WL color multisets become equal multisets of GNN states when each color is sent to its common state from step 1.1; multiplicities are preserved by [F3]. The shared graph readout in [F4] receives equal multisets, so the two graph outputs are equal. The contrapositive gives the stated distinguishing implication.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

4 results within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka, How Powerful are Graph Neural Networks? (standard reference, not scraped)
Christopher Morris et al., Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks (standard reference, not scraped)
Pan Li and Jure Leskovec, Graph Representation Learning (standard reference, not scraped)