Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization

Arie Soeteman (University of Amsterdam; Institute for Logic, Language and Computation) · Balder ten Cate (University of Amsterdam)

color refinement algorithmsexperimental resultsexpressive modelsgraded hybrid logicgraph neural networkshierarchical ego graph neural networkshierarchical node individualizationhigher-order gnnsindividualization-refinement paradigmisomorphism testinglocal homomorphism count featurespractical feasibilityseparating powersubgraph-gnnstraditional gnn architectures

We propose and study Hierarchical Ego Graph Neural Networks (HE-GNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradigm for isomorphism testing. HE-GNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that, in the limit, distinguish graphs up to isomorphism. We show that, over graphs of bounded degree, the separating power of HE-GNN node classifiers equals that of 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.