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.
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 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