Research map / Graph learning / GNN architectures

Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization

NeurIPS 2025 · Graph learning › GNN architectures · approach: Weisfeiler-Leman expressivity hierarchies

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Hierarchical Ego GNNs (HE-GNNs), which extend GNNs with hierarchical node individualization, and characterizes their separating power logically via graded hybrid logic, relating them to WL, IR, higher-order GNNs and homomorphism-count GNNs.

Problem

Understanding and improving the separating (expressive) power of GNNs beyond 1-WL, especially in a way that approaches graph isomorphism via individualization-refinement while remaining efficient.

Approach

Alternate node individualization (marking a node with a unique binary feature) with message passing in a hierarchy of nesting depth; subgraph-restricted variants use radius-r ego networks. The separating power is characterized exactly by graded hybrid logic GML(↓) (and its subgraph fragments), and linked to IR trees, homomorphism counts (via ego-rank), and k-GNNs.

Key results

• HES-GNN with depth 1 outperforms F-GNN on ZINC-12k despite ZINC target including cycle counts; HES-GNN depth 2 (r=3) matches F-GNN with depth-1 homomorphism counts.
• Depth-1 HE-GNN and ID-GNN perform at chance on strongly regular graph isomorphism datasets, while depth-2 HE-GNNs distinguish them and generalize to unseen isomorphisms.
• Theorem shows HE-GNN classifiers match graded hybrid logic GML(↓) separating power over bounded-degree graphs, with strict hierarchy in nesting depth d and radius r.

Measured effects reported in the paper

Surprising findings

• Tinhofer-ordering GNN reaches 100% test precision on SRG datasets but does not generalize to test isomorphisms because the orderings are not isomorphism-invariant on those graphs.
• Depth-1 HE-GNNs (and ID-GNN) remain at chance level on strongly regular graphs even with added cycle counts.

Limitations

• Exponential number of message-passing runs in nesting depth d makes large d infeasible.
• Results concern separating power, not uniform expressibility or learnability.
• Some conjectures open, e.g., whether (d+1)-WL is strictly less separating than HE-GNN depth d, and necessity of ego-rank conditions for homomorphism counting.

Experimental setup

Datasets: ZINC-12k strongly regular graphs (synthetic, 4 parameter settings, 10 graphs x 30 isomorphisms each)

Benchmarks: ZINC-12k strongly regular graph isomorphism classification

Metrics: mean absolute error precision time per forward pass memory per sample

Baselines: GCN GIN PNA GNN+RID GNN+T (Tinhofer orderings) F-GNN (homomorphism counts) ID-GNN

Builds on: graded modal logic k-GNN (Morris et al.) ID-GNN subgraph GNNs homomorphism count GNNs

Closest papers by meaning

• Towards a Complete Logical Framework for GNN Expressiveness (ICLR 2025 · similarity 0.92)
• $\mathscr{N}$-WL: A New Hierarchy of Expressivity for Graph Neural Networks (ICLR 2023 · similarity 0.91)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.91)
• On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks (NeurIPS 2024 · similarity 0.90)
• Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.89)
• Recurrent Graph Neural Networks and Their Connections to Bisimulation and Logic (AAAI 2024 · similarity 0.89)