Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization

Arie Soeteman, Balder ten Cate

Introduction

Standard Message-Passing Neural Networks (MPNNs) are fundamentally limited by the 1-dimensional Weisfeiler-Leman (1-WL) test, preventing them from distinguishing certain non-isomorphic graph structures. While higher-order $k$-GNNs can overcome these limits, they require $O(n^k)$ memory, which is impractical for large-scale applications. This paper introduces Hierarchical Ego Graph Neural Networks (HE-GNNs), a framework that achieves high expressive power with significantly better space complexity by adopting the "individualization-refinement" (IR) strategy from classical graph isomorphism solvers.

Hierarchical Node Individualization

The core mechanism of HE-GNNs is the recursive marking of nodes. In the IR paradigm, a node is "individualized" by giving it a unique identifier, and the graph is then "refined" through message passing to see how this mark propagates. HE-GNNs extend this by nesting these operations: a depth-$d$ model marks a node, and within that context, recursively marks another, up to $d$ levels.

Individualized graph pairs (G, v) and (G', v') illustrating the marking of specific nodes to break structural symmetry.

This hierarchical approach allows the model to capture complex structural dependencies without the memory overhead of $k$-GNNs. While $k$-GNNs store $O(n^k)$ features simultaneously, HE-GNNs process information sequentially, requiring only $O(n^2)$ space to store node features regardless of depth $d$.

Logical Characterization and Hierarchy

A key contribution of this work is the formal link between GNNs and Graded Hybrid Logic ($GML(\downarrow)$). The authors prove that the expressive power of HE-GNNs exactly matches this logic, providing a theoretical "ceiling" for what the model can compute. This allows researchers to determine if a graph property is learnable by checking if it can be expressed in $GML(\downarrow)$.

The hierarchical dependency structure in HE-GNNs, where node markings (dep) create a nested context for message passing.

The authors also introduce HES-GNNs, a practical variant that restricts the model's view to a local subgraph (radius $r$) around the marked node. They demonstrate a strict hierarchy: increasing the depth $d$ or the radius $r$ strictly increases the model's ability to distinguish graphs, eventually reaching full graph isomorphism.

Experimental Results

The effectiveness of HE-GNNs was validated on both synthetic and real-world datasets:

  • Strongly Regular Graphs (SRGs): These graphs are notoriously difficult for GNNs (indistinguishable by 2-WL). Depth-2 HE-GNNs successfully distinguished SRGs where standard ID-GNNs and 3-GNNs failed.
  • ZINC-12k: On this molecular benchmark, HES-GNNs (depth 1, radius 3) achieved a Mean Absolute Error (MAE) of 0.140, outperforming standard GCN (0.216) and GIN (0.193) models.

Conclusion

HE-GNNs provide a powerful, logically grounded alternative to higher-order GNNs. By leveraging hierarchical individualization, they bridge the gap between deep learning and classical isomorphism algorithms, offering a scalable path toward more expressive graph representation learning. Future work will focus on optimizing the recursive computation steps to handle massive graphs more efficiently.

Summary updated

BibTeX
@inproceedings{soeteman2025logical,
  author = {Arie Soeteman and Balder ten Cate},
  title = {{Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=yvGnOqy0Zf},
}
Figure