Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
This addresses the expressiveness bottleneck in GNNs for graph learning tasks, offering a novel hierarchical approach that is incremental in extending existing subgraph-GNNs.
The paper tackles the problem of limited expressiveness in graph neural networks (GNNs) by proposing Hierarchical Ego Graph Neural Networks (HEGNNs), which can distinguish graphs up to isomorphism in the limit and show practical benefits over traditional GNNs in experiments.
We propose and study Hierarchical Ego Graph Neural Networks (HEGNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradigm for graph isomorphism testing. HEGNNs 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 HEGNN node classifiers, with and without subgraph restrictions, using graded hybrid logic. This characterization enables us to relate the separating power of HEGNNs 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 HEGNNs and show benefits in comparison with traditional GNN architectures, both with and without local homomorphism count features.