PaperlayerView exact revision on arXiv

Source-linked AI summary

How Powerful are K-hop Message Passing Graph Neural Networks

Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, Muhan Zhang

arXiv:2205.13328v4cs.LGcs.AI

TL;DR

The paper studies the uncharacterized expressive power of K-hop message passing beyond the 1-WL-limited 1-hop paradigm. It formally analyzes two K-hop kernels and introduces KP-GNN, showing stronger graph discrimination while retaining theoretical limits for standard K-hop methods.

  • Problem

    The expressive power of K-hop message passing, an extension that aggregates information from neighbors within K hops, had not been theoretically characterized beyond the 1-WL-bounded 1-hop framework.

  • Method

    The paper distinguishes graph diffusion and shortest path distance kernels, characterizes K-hop message passing theoretically, and introduces KP-GNN with peripheral subgraph aggregation at each hop.

  • Results

    K-hop GNNs distinguish almost all regular graphs but are bounded by 3-WL, while KP-GNN distinguishes many distance regular graphs and achieves competitive results across simulation and real-world datasets.

  • Takeaways & Limitations

    Peripheral subgraph information further enhances K-hop message passing beyond its standard expressive power and supports competitive performance across benchmark settings.

  • Takeaways & Limitations

    Standard K-hop message passing cannot distinguish some simple non-isomorphic regular structures, and its expressive power is bounded by 3-WL.

Abstract

from arXiv · show

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing -- aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by the Weisfeiler-Lehman (1-WL) test. Recently, researchers extended 1-hop message passing to K-hop message passing by aggregating information from K-hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of K-hop message passing. In this work, we theoretically characterize the expressive power of K-hop message passing. Specifically, we first formally differentiate two different kernels of K-hop message passing which are often misused in previous works. We then characterize the expressive power of K-hop message passing by showing that it is more powerful than 1-WL and can distinguish almost all regular graphs. Despite the higher expressive power, we show that K-hop message passing still cannot distinguish some simple regular graphs and its expressive power is bounded by 3-WL. To further enhance its expressive power, we introduce a KP-GNN framework, which improves K-hop message passing by leveraging the peripheral subgraph information in each hop. We show that KP-GNN can distinguish many distance regular graphs which could not be distinguished by previous distance encoding or 3-WL methods. Experimental results verify the expressive power and effectiveness of KP-GNN. KP-GNN achieves competitive results across all benchmark datasets.

1 Introduction

The paper addresses the unresolved expressive power of K-hop message passing, which extends 1-hop aggregation but has lacked theoretical characterization. It distinguishes K-hop kernels, establishes their expressive gains and limits, and introduces KP-GNN to further improve structural discrimination.

  • Motivation: K-hop message passing extends 1-hop GNNs by aggregating information from neighbors within K hops, but its expressive power had not been theoretically characterized.The paper frames whether K-hop message passing improves over 1-hop methods and to what extent as an open question.
  • Contributions: The paper formally distinguishes graph diffusion and shortest path distance kernels, showing that kernel choice produces different expressive power.These kernels are used in different prior K-hop methods and are often conflated.
  • Contributions: K-hop message passing is strictly more powerful than 1-hop message passing and can distinguish almost all regular graphs.
  • Contributions: K-hop message passing still fails on some simple regular graphs and remains bounded by the 3-WL test.
  • Contributions: KP-GNN augments each hop with peripheral subgraph information, improving expressive power while requiring only slight modification and little additional computational complexity.The framework is evaluated through experiments on simulation and real-world datasets.

2 K-hop message passing and its expressive power

K-hop message passing distinguishes more structures than 1-hop message passing by aggregating information across multiple hops, but its expressive power depends on the kernel and remains bounded by 3-WL.

  • K-hop message passing: K-hop message passing aggregates information from neighbors within multiple hops, whereas standard message passing uses direct 1-hop neighbors.The framework generalizes the same message and update mechanism to multiple hops, with separate functions and a combination operation across hops.
  • K-hop message passing: Shortest-path-distance and graph-diffusion kernels assign K-hop neighborhoods differently, producing different expressive power.Shortest-path kernels use exact graph distance, while diffusion kernels include nodes that can transmit information within a specified number of diffusion steps.
  • Expressive power: A proper K-hop GNN is strictly more powerful than 1-hop message passing when K > 1.Its node configuration includes the information available to 1-hop message passing and can additionally distinguish local structures through higher-hop neighborhoods.
  • Expressive power: With K = floor((1/2 + epsilon) log_2 n / log(r−1)) and one layer, shortest-path-distance K-hop GNNs distinguish almost all 1 − o(n^-1/2) pairs of n-sized r-regular graphs.The result applies for 3 ≤ r < (2 log_2 n)^1/2 and shows that modest K can distinguish almost all regular graphs.
  • Limitations: Proper K-hop message passing cannot distinguish some simple non-isomorphic structures and is bounded by the 3-WL test.These limitations motivate improving K-hop message passing with peripheral edges and subgraphs.
  • Limitations: Kernel choice limits what 2-hop message passing can distinguish: each kernel separates one Figure 1 example but fails on the other.The examples become distinguishable when peripheral subgraph information is added.

3 KP-GNN: improving the power of K-hop message passing by peripheral subgraph

KP-GNN strengthens K-hop message passing by adding peripheral subgraph information at each hop, enabling richer local structural features and distinguishing some distance-regular graphs beyond standard K-hop methods.

  • Peripheral-subgraph enhancement: Peripheral edges record connections among nodes within a hop, while the peripheral subgraph is the graph induced by those nodes.
  • Peripheral-subgraph enhancement: The added peripheral structure can separate nodes whose ordinary hop neighborhoods look similar but have different internal connectivity.Examples distinguish graphs using whether first-hop neighbors contain particular edges.
  • Peripheral-subgraph enhancement: KP-GNN augments each hop’s neighbor aggregation with the peripheral subgraph induced by nodes at that hop.The peripheral subgraph contains edges whose endpoints both belong to the relevant hop’s node set.
  • Implementation: KP-GNN can use flexible graph encoders for peripheral subgraphs and can enhance any base GNN by replacing its hop-specific message functions.The implementation encodes node configurations and peripheral-edge counts through a learnable embedding function.
  • Expressive power: For two non-isomorphic distance-regular graphs with the same diameter and intersection array, a proper 1-layer d-hop KP-GNN distinguishes them when some peripheral configuration differs.The paper illustrates this with the Shrikhande graph and the 4×4 Rook’s graph, whose first-hop peripheral structures differ.
  • Complexity and limitations: KP-GNN has O(n) space and O(n^2) time complexity for the shortest-path-distance kernel, while the paper notes intrinsic limitations and gives further discussion in Appendix H.The stated time complexity is lower than the at-least-O(nm) complexity of subgraph-based GNNs.

4 Related Work

Related work studies how to increase GNN expressive power through higher-order WL-like architectures, additional node features, distance information, and K-hop message passing.

  • Expressive power of GNN: Higher-order GNNs such as 1-2-3 GNN, PPGN, and ring-GNN mimic higher-order WL tests but require exponentially increasing space and time with node number.
  • Expressive power of GNN: Feature-based approaches add one-hot or random node features, but the paper notes that these can reduce generalization because identical local structures receive different representations.
  • K-hop message passing GNN: K-hop methods instantiate multi-hop aggregation in different ways, including graph-diffusion kernels, sequential hop processing, and other hop-aware mechanisms.MixHop concatenates representations from each hop, whereas K-hop processes hops from K to 1 and is not parallelizable.

5 Experiments

Experiments evaluate KP-GNN on simulation, graph, molecular, and real-world datasets, while also measuring its computational overhead. KP-GNN achieves strong performance across tasks, with overhead growing nearly linearly in K.

  • Experimental setup: KP-GNN is evaluated on expressive-power simulations, node and graph properties, substructure prediction, TU datasets, and molecular benchmarks.The experiments include EXP, SR25, CSL, TU, QM9, and ZINC datasets.
  • Simulation and property prediction: KP-GIN+ achieves state-of-the-art results on a majority of node, graph, and substructure prediction tasks.It is compared with GIN, GIN-AK+, PNA, PPGN, and normal K-hop GNNs.
  • TU datasets: KP-GNN achieves state-of-the-art performance on most TU datasets under the second evaluation setting and remains comparable under the first.The framework is instantiated with KP-GCN, KP-GraphSAGE, and KP-GIN.
  • Molecular prediction: KP-GNN achieves state-of-the-art performance on most QM9 targets, while its ZINC results are reported as not uniformly superior.The molecular baselines include DTNN, MPNN, Deep LRP, PPGN, Graphormer, GSN, GIN-AK+, and CIN.
  • Efficiency: The computational overhead of KP-GNN is almost linear in K when K = 4.The comparison uses GIN as the base model with matched layer counts and hidden dimensions; sparsity makes K-hop neighborhoods smaller than n for small K.

6 Conclusion

The paper characterizes K-hop message passing theoretically and introduces KP-GNN, which adds peripheral subgraph information to strengthen local structural representations. The resulting framework distinguishes many distance regular graphs and performs competitively across simulations and real-world datasets.

  • Conclusion: KP-GNN augments each hop’s neighbor aggregation with the peripheral subgraph induced by neighbors at that hop.This additional information is intended to capture more expressive local structural features.
  • Conclusion: K-hop GNNs can distinguish almost all regular graphs but remain bounded by the 3-WL test.The conclusion summarizes the theoretical expressive-power boundary of standard K-hop message passing.
  • Conclusion: KP-GNN can distinguish many distance regular graphs that standard K-hop message passing cannot distinguish.The framework uses peripheral subgraph information at each hop to improve expressive power.
  • Conclusion: KP-GNN achieves competitive results across simulation and real-world datasets.This empirical conclusion complements the theoretical characterization and proposed architectural improvement.
  • Conclusion: The paper distinguishes shortest-path-distance and graph-diffusion kernels, whose different node-h assignment behavior affects K-hop expressive power.Shortest-path kernels assign a node to at most one distance hop, whereas diffusion kernels may include nodes in multiple hop sets.

C.1 Proof of Theorem 1

The proof establishes that, under specified degree and hop conditions, one-layer K-hop message passing with the shortest-path kernel distinguishes almost all pairs of sampled regular graphs. Simulations then verify the theoretical predictions at node and graph levels.

  • Proof of Theorem 1: For n-sized r-regular graphs with 3 ≤ r < (2log2n)1/2, the proof uses K-hop shortest-path configurations to compare graph pairs.The argument is formulated through randomly sampled regular graphs and node configurations.
  • Proof of Theorem 1: Event A ensures that early exploration steps reach nearly the maximum number of nodes at successive distances from two selected nodes.This controls the number of nodes at distances {1, 2, ..., k} in the configuration model.
  • Proof of Theorem 1: The configuration-model argument shows that, with probability 1 − o(n−1/2), an injective readout distinguishes two sampled regular graphs.The proof combines node-level separation with an injective graph-level readout.
  • Proof of Theorem 1: The proof constructs a combined disconnected regular graph to transfer the node-level probability bound to comparisons between two graph components.The resulting separation probability is bounded by o(n−3/2) for the selected node pair.
  • Simulation verification: Simulations with 100 n-sized 3-regular graphs show that K-GIN matches the lemma’s predicted threshold and distinguishes almost all graphs even with K = 2.The experiments use n from 20 to 1280 and K from 1 to 6; node and graph results correspond to the two sides of Figure 4.

D.1 General K-hop color refinement algorithm

The general color refinement framework parameterizes which hop information is aggregated at each iteration, enabling comparisons among 1-WL, K-hop, and GINE+ procedures. These comparisons establish that shortest-path K-hop message passing can be strictly more expressive than standard 1-hop message passing, while differing from depth-based 1-hop models.

  • General framework: The refinement configuration specifies the maximum iterations and hops, together with which prior iteration’s information each hop aggregates.The resulting general color refinement algorithm changes when different configurations are selected.
  • Expressive-power comparisons: Adding layers or supplying more information makes the corresponding refinement algorithm at least as expressive as the less informative configuration.This follows from injective hashing and the monotonicity properties of the general refinement algorithm.
  • Expressive-power comparisons: Shortest-path K-hop message passing is at least as powerful as GINE+, and GINE+ is strictly more powerful than 1-hop message passing.The comparison applies to L-layer models with injective message and update functions.
  • Expressive-power comparisons: One-layer K-hop and K-layer 1-hop message passing are incomparable: each can distinguish graph pairs that the other cannot.The shortest-path kernel supplies the examples, including a pair of regular graphs distinguished by one-layer 2-hop message passing but not two-layer 1-hop message passing.
  • Comparison with distance encoding: Distance encoding and K-hop message passing are also incomparable because each distinguishes node pairs that the other fails to distinguish.The comparison uses node configurations for K-hop message passing and center-node distance labels for DE-1.

F Proof of Theorem 2

The proof implements K-hop neighbor extraction and message passing using 3-IGN orbit tensors. This establishes that both K-hop kernels fall within the expressive-power bound of 3-WL.

  • 3-IGN implementation: The construction implements K-hop neighbor extraction with 3-IGN orbit tensors.The implementation uses logical operations and tensor transformations to recover the required hop neighborhoods.
  • K-hop neighbor extraction: K-hop neighbor extraction stores hop-specific reachability in tensor channels and iteratively computes neighbors at distances up to K.For the shortest-path kernel, nodes appearing in earlier hops are removed; the diffusion kernel retains nodes reachable within each diffusion step.
  • K-hop message passing: The message-passing implementation broadcasts node representations, nullifies messages from non-target-hop nodes, and aggregates the remaining messages.Each hop uses a corresponding message function and can be combined with hop-specific updates and an MLP combine function.
  • Expressive-power bound: Because the extraction and message-passing layers are implementable by 3-IGN, K-hop message passing with either kernel is bounded by 3-WL.The same conclusion is stated for both graph diffusion and shortest-path distance kernels.

G Proof and discussion of Proposition 2

For distance-regular graphs, KP-GNN leverages regular peripheral subgraphs to distinguish node pairs when those peripheral structures differ. The analysis establishes linear space complexity and quadratic worst-case time complexity, but leaves quantitative expressive-power guarantees unresolved.

  • Distance-regular graphs: A distance-regular graph is regular, with the number of nodes at specified distances from two nodes determined only by those distances and the nodes’ separation.Its intersection array records the relevant neighbor counts between consecutive distance layers.
  • Peripheral subgraphs: Each peripheral subgraph of a node in a distance-regular graph is itself regular.The regularity follows from the intersection-array parameters governing connections among distance layers.
  • KP-GNN expressiveness: KP-GNN can distinguish nodes across non-isomorphic distance-regular graphs when corresponding peripheral subgraphs differ at some hop.The argument uses peripheral edge sets or peripheral configurations as the additional structural information.
  • Scope of the analysis: KP-GNN’s current analysis can distinguish peripheral subgraphs only through their peripheral configurations.This restricts the available discrimination mechanism within the presented proof.
  • Scope of the analysis: The paper leaves quantitative expressive-power analysis open because the peripheral subgraphs are not random configuration-model graphs and therefore do not satisfy the theorem used for almost-all regular graphs.The apparent extension to almost all distance-regular graphs is consequently not established.
  • Complexity: K-hop GNNs and KP-GNN use O(n) space, while their worst-case time complexity is O(n^2).Their space matches vanilla message passing and is lower than subgraph-based GNNs, PPGN, and 3-WL-GNNs; their time is higher than normal GNNs but lower than subgraph-based methods.

H.3 Limitations

The paper identifies stability and computational cost as limitations of KP-GNN and related K-hop or subgraph-based methods. It also describes implementation choices intended to mitigate receptive-field growth and improve structural encoding.

  • Stability: K-hop message passing expands a node's receptive field with K, which can hurt learning by aggregating unrelated information.The paper describes this as an intrinsic limitation of K-hop GNNs.
  • Stability: KP-GNN′ mitigates stability issues by using KP-GNN only in the first layer and 1-hop message passing afterward.This design supports larger K without causing training to fail and performs well on real-world datasets.
  • Time complexity: KP-GNN requires O(n^2) time, substantially higher than the O(m) complexity of standard MPNNs.The paper frames this cost as a trade-off for greater expressive power and notes that related subgraph methods are also expensive.
  • Implementation: KP-GNN combines representations from different hops using either learned attention or geometrically weighted summation.The geometric option assigns hop i weight θ_i = α(1 − α)^i, with α ∈ (0, 1].
  • Implementation: Path encoding augments hop information with the number of length-k walks between node pairs, computed from A^k without additional cost.The resulting information is added as extra features to the aggregation function.

J Experiential setting details

The experiments evaluate K-hop and KP-GNN variants across graph classification, property prediction, substructure counting, molecular, and TU benchmark settings. Protocols vary by dataset, including cross-validation, repeated runs, searched architectural choices, and dataset-specific kernels or hop counts.

  • Other datasets: EXP, SR25, and CSL experiments evaluate K-GIN and KP-GIN with dataset-specific hidden sizes, pooling, and validation procedures.The EXP setting uses 10-fold cross-validation, while SR25 reports best performance across 200 epochs.
  • Graph and node property datasets: Graph and node property experiments train K-GIN+ and KP-GIN+ for four independent runs and report mean results.They use hidden size 96, concatenated layer representations, and attention or sum pooling depending on task type.
  • Graph substructure counting dataset: Graph substructure counting experiments use four independent runs, mean results, hidden size 96, and shortest path distance kernels.The final representation concatenates layer outputs and uses summation pooling.
  • TU datasets: TU experiments use 10-fold cross-validation and search layers, hops, K-hop kernels, and combination functions for KP-GNN.The implementations include GCN, GraphSAGE, and GIN variants.
  • QM9 dataset: QM9 experiments compare KP-GIN+ with K=8 and eight layers against KP-GIN′ with K=16 and sixteen layers.Both models use hidden size 128 and attention pooling, with additional virtual-node or residual connections.
  • ZINC dataset: ZINC experiments run KP-GIN+ and KP-GIN′ independently four times, using eight or sixteen hops respectively.The two variants use different hidden sizes and layer counts.

K Additional results

Additional counting-substructure results show that increasing K consistently improves K-GIN+, while peripheral subgraph information often makes K=1 sufficient for KP-GIN+.

  • Counting substructure results: K-GIN+ improves steadily across all counting-substructure tasks as K increases.This observation aligns with the theoretical result that expressive power increases with K.
  • Counting substructure results: Path encoding can substantially boost counting-substructure performance, demonstrating its effectiveness for K-GIN+.For KP-GNN, path encoding has little effect because peripheral subgraphs already encode that information.
  • Counting substructure results: Most KP-GIN+ tasks achieve their best results with K=1, suggesting that local peripheral subgraph information is often sufficient.Although larger K increases theoretical expressive power, it may add noise during training.

L Datasets Description and Statistics

This section presents dataset statistics in Table 8. The supplied passage identifies the table but does not report individual dataset values.

  • Dataset statistics: Table 8 reports dataset statistics for the experiments.The supplied passage does not specify the statistics or values shown in the table.
  • Dataset statistics: The dataset-statistics section is distinct from the experimental protocol descriptions reported elsewhere.Only the table caption is available here.
  • Dataset statistics: No individual dataset names, sizes, or structural properties are stated in the supplied table caption.The caption identifies the table's purpose without providing its contents.
Loading 2205.13328v4…