Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
Arie Soeteman, Balder ten Cate
We propose and study Hierarchical Ego Graph Neural Networks (HE-GNNs), an expressive extension of GNNs with hierarchical node individualization, inspired by the Individualization-Refinement paradigm for graph isomorphism testing. HE-GNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that, in the limit, can distinguish graphs up to isomorphism.We provide a logical characterization of HE-GNN node classifiers, with and without subgraph restrictions, using graded hybrid logic. This characterization enables us to relate the separating power of HE-GNNs to that of higher-order GNNs, GNNs enriched with local homomorphism count features, and color refinement algorithms based on Individualization-Refinement.Our experimental results confirm the practical feasibility of HE-GNNs and show benefits in comparison with traditional GNN architectures, both with and without local homomorphism count features.