Source-linked AI summary
k-hop Graph Neural Networks
Giannis Nikolentzos, George Dasoulas, Michalis Vazirgiannis
TL;DR
Standard GNNs may share the Weisfeiler-Leman test’s inability to identify fundamental graph properties. The paper proposes k-hop GNNs, which aggregate information from nodes’ k-hop neighborhoods; they identify properties missed by standard GNNs and achieve competitive results on node and graph classification datasets.
Problem
Whether GNNs can identify fundamental graph properties remains unclear, since the Weisfeiler-Leman test cannot identify properties such as connectivity and triangle-freeness.
Source: §1 · p. 2Method
k-hop GNNs update node representations using information from the nodes’ k-hop neighborhoods, not only their direct neighbors.
Source: §1 · p. 2Results
Standard GNNs cannot identify connectivity, bipartiteness, or triangle-freeness, while k-hop GNNs identify missed properties and achieve competitive results on node and graph classification datasets.
Source: §1 · p. 2, §6 · p. 17Takeaways & Limitations
The paper concludes that k-hop GNNs can identify graph properties that standard GNNs do not capture.
Source: §6 · p. 17Standard GNNs assign the same graph representation to regular graphs with the same node degree and size, limiting their ability to distinguish property-bearing pairs of such graphs.
Source: §3 · p. 5
Abstract
from arXiv · showhide
Graph neural networks (GNNs) have emerged recently as a powerful architecture for learning node and graph representations. Standard GNNs have the same expressive power as the Weisfeiler-Leman test of graph isomorphism in terms of distinguishing non-isomorphic graphs. However, it was recently shown that this test cannot identify fundamental graph properties such as connectivity and triangle freeness. We show that GNNs also suffer from the same limitation. To address this limitation, we propose a more expressive architecture, k-hop GNNs, which updates a node's representation by aggregating information not only from its direct neighbors, but from its k-hop neighborhood. We show that the proposed architecture can identify fundamental graph properties. We evaluate the proposed architecture on standard node classification and graph classification datasets. Our experimental evaluation confirms our theoretical findings since the proposed model achieves performance better or comparable to standard GNNs and to state-of-the-art algorithms.
1 Introduction
The introduction identifies a gap in whether standard GNNs can recognize fundamental graph properties, given their link to the limited Weisfeiler–Lehman test. It presents k-hop GNNs, which aggregate beyond direct neighbors, and reports competitive classification performance.
1 Introduction
- GNNs are no more powerful than the Weisfeiler–Lehman test, whose subtree kernel has been shown insufficient for identifying fundamental graph properties.Source: §1 · p. 2
- k-hop GNNs address the myopic reach of direct-neighbor message passing by incorporating each node’s whole k-hop neighborhood.This captures structural information not visible through 1-hop aggregation alone.Source: §1 · p. 2
- Standard GNNs cannot identify connectivity, bipartiteness, or triangle-freeness.Source: §1 · p. 2
- Across node- and graph-classification datasets, k-hop GNNs achieved performance better or comparable to standard GNNs and state-of-the-art algorithms.The introduction also reports that they outperform traditional GNNs on most datasets.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish graph notation and outline the standard GNN framework, from neighborhood aggregation to node- and graph-level representations.
2 Preliminaries
- The section fixes notation before presenting the standard graph neural network framework.Source: §2 · p. 3
2.1 Notation
- A k-hop neighborhood contains nodes at distance at most k from a node; its neighborhood subgraph is induced by those nodes and the node itself.Source: §2.1 · p. 3
- Graphs may carry discrete node labels or categorical and real-valued attributes, represented through a labeling function or feature vectors.Source: §2.1 · p. 3, §2.2 · p. 3
2.2 Graph Neural Networks
- A GNN consists of neighborhood aggregation layers that combine graph structure and prior node features to generate new representations.For unlabeled graphs, initial features may include renumbering-invariant local properties such as degree, k-core number, or triangle count.Source: §2.2 · p. 3
- GNN variants differ in their AGGREGATE and MERGE functions; both must be differentiable, and aggregation must be permutation invariant.Source: §2.2 · p. 3
- Some implementations combine aggregation and merging into one function, including variants that use a multilayer perceptron.Source: §2.2 · pp. 3–4
- Node tasks use final-layer node vectors; graph tasks apply a permutation-invariant READOUT, commonly a mean, with sorting, concatenation, and clustering alternatives also noted.Source: §2.2 · p. 4
3 Limitations of the Standard GNN Model
The section shows that standard GNNs cannot identify connectivity, bipartiteness, or triangle-freeness, using collisions between regular graphs to establish the limitation.
3 Limitations of the Standard GNN Model
- The analysis uses concepts from property testing to study whether GNN representations identify graph properties.A property is identified when graphs with different property membership cannot receive the same representation.Source: §3 · p. 4
- Under the stated feature assumption, same-size regular graphs of the same degree receive identical node representations.The assumption is that all nodes, or nodes with the same degree, have the same feature vector.Source: §3 · p. 5
- The standard GNN cannot identify connectivity, bipartiteness, or triangle-freeness.The proof uses pairs of regular graphs with the same size and degree that receive identical representations.Source: §3 · p. 5
- A six-node cycle and two disjoint triangles are both 2-regular, but differ in connectivity while yielding identical graph representations.Their identical representations follow because the READOUT function receives identical inputs.Source: §3 · p. 5, Figure 1 · p. 5
- The second counterexample pair consists of same-size, same-degree graphs that differ in bipartiteness and triangle-freeness yet receive identical representations.One graph contains triangles and is not bipartite; the other is bipartite and triangle-free.Source: §3 · p. 5, Figure 2 · p. 6
4 k-hop Graph Neural Networks
k-hop GNNs replace direct-neighbor aggregation with aggregation over a node’s full k-hop neighborhood. The section describes their ring-wise updates, theoretical identifiability results, and computational cost.
4 k-hop Graph Neural Networks
- The proposed k-hop GNN aggregates over a node’s entire k-hop neighborhood and is strictly stronger than standard GNNs at distinguishing non-isomorphic graphs.The section presents this architecture as capable of identifying graph properties that standard GNNs do not capture.Source: §4 · p. 6
4.1 Proposed Architecture
- Within each k-hop neighborhood, the model processes nodes from the frontier inward, updating inner representations across then within distance rings before aggregating the root.Each inner representation is updated at most twice, and these auxiliary vectors are used to compute the root’s layer representation.Source: §4.1 · p. 7
4.2 Example
- In the 2-hop example, frontier nodes v4 and v5 remain unchanged but contribute to updating v2; same-level nodes v2 and v3 are then updated before the root.The final step updates the root by aggregating information from its direct neighbors.Source: §4.2 · p. 8
4.3 Expressive Power
- The theorem establishes identification of connectivity for k > δmin and bipartiteness for k ≥ (l−1)/2, where δmin is the minimum component diameter and l the smallest odd-cycle length.The passage defines l when the graph has an odd cycle.Source: §4.3 · p. 9
- Polynomial [9] and ARMA [3] filters use k-hop information, but these models fail to consistently capture the three properties; adjacency-matrix powers are another higher-order method [1].Source: §4.3 · p. 9
4.4 Computational Complexity
- For sparse graphs and small k, k-hop GNN complexity O(n d̄^k) is comparable to standard GNN complexity O(km), despite worst-case O(nm) complexity.Preprocessing is computed once; the message-passing layer allows a GPU-friendly implementation, and the authors report that running time is not prohibitive in practice.Source: §4.4 · pp. 9–10
5 Experimental Evaluation
The evaluation tests k-hop GNNs on node classification, synthetic graph-property classification, and standard graph-classification datasets. Across these settings, results vary by dataset and metric, but k-hop models outperform standard GNNs and perform competitively with other methods.
5.1.1 Synthetic Datasets
- Across synthetic node-classification configurations, k-hop GNNs outperform standard GNNs in every experiment and are less prone to noise than the baselines.The 3-hop model leads in both perturbed configurations; the 2-hop model leads in the varied configuration, and both tie in basic.Source: Table 2 · p. 12, §5.1.1 · p. 12
5.1.2 Real-World Dataset
- On Enron, ARMA models lead in accuracy, while 2-hop GNN leads in F1-score, followed by 3-GNN and ARMA (T = 2).Supervised neural network models outperform the unsupervised algorithms overall; struc2vec is the only unsupervised method with comparable performance.Source: §5.1.2 · pp. 12–13, Table 3 · p. 13
5.2.1 Synthetic Datasets
- On the three synthetic graph-property datasets, k-hop GNNs achieve much higher accuracy than standard GNN, ChebNet, and ARMA; 3-hop leads on connectivity and bipartiteness, while 2-hop leads on triangle-freeness.Standard GNNs achieve only slightly above 50% average accuracy on all three datasets.Source: Table 4 · p. 14, §5.2.1 · p. 14
5.2.2 Real-World Datasets
- On standard graph-classification datasets, k-hop GNNs outperform standard GNNs on every dataset and are only slightly less accurate than the best method on most datasets.They rank second on MUTAG, fourth on IMDB-BINARY and IMDB-MULTI, and sixth on NCI1 and PROTEINS.Source: §5.2.2 · p. 16
- On the five standard graph-classification datasets, proposed k-hop models take about twice the average time per epoch of corresponding standard GNNs, and preprocessing time increases with k.Standard GNN preprocessing time is independent of k.Source: §5.2.2 · p. 17
6 Conclusion
The paper shows that a wide class of GNN architectures cannot identify fundamental graph properties and proposes k-hop GNNs, which aggregate information from nodes’ k-hop neighborhoods. On node and graph classification datasets, the proposed model achieves results competitive with state-of-the-art algorithms.
6 Conclusion
- The proposed k-hop GNN aggregates information from nodes’ k-hop neighborhoods and identifies graph properties missed by standard GNNs, with competitive results on node and graph classification datasets.The analysis finds that a wide class of GNN architectures cannot identify fundamental graph properties.Source: §6 · p. 17
Proof of Theorem 2
The proof shows how k-hop updates can distinguish graphs with different connectivity, triangle-freeness, or bipartiteness. Its argument uses expressive aggregation functions and property-specific patterns in neighborhood subgraphs.
Proof of Theorem 2
- The aggregation scheme can represent functions over a node and its neighbor multiset, using injective encodings and UPDATE modules modeled by MLPs.The proof assumes countable feature vectors and invokes the universal approximation theorem for the MLPs.Source: Proof of Theorem 2 · pp. 17–18
- For triangle-freeness, adjacent nodes within a triangle trigger an update absent in triangle-free graphs, allowing their neighborhood representations to differ.The proof applies the within-ring update to two connected nodes in a triangle’s 1-hop neighborhood.Source: Proof of Theorem 2 · p. 18
- Connectivity is distinguished when a disconnected component’s rings end at its minimum diameter, while a connected graph has a node with nonempty rings beyond that boundary.The resulting updates yield different neighborhood-subgraph representations for connected and disconnected graphs.Source: Proof of Theorem 2 · p. 18
- An odd cycle in a k-hop neighborhood is equivalent to an edge between two nodes at the same distance from its root, providing a local criterion used in the bipartiteness proof.The proof relates this equal-distance pattern to the presence of an odd cycle in the neighborhood subgraph.Source: Proof of Theorem 2 · pp. 18–19