Rethinking the Expressiveness of GNNs: A Computational Model Perspective

Guanyu Cui, Zhewei Wei, Hsin-Hao Su

Abstract

Graph Neural Networks (GNNs) are extensively employed in graph machine learning, with considerable research focusing on their expressiveness. Current studies often assess GNN expressiveness by comparing them to the Weisfeiler-Lehman (WL) tests or classical graph algorithms. However, we identify three key issues in existing analyses: (1) some studies use preprocessing to enhance expressiveness but overlook its computational costs; (2) some claim the anonymous WL test's limited power while enhancing expressiveness using non-anonymous features, creating a mismatch; and (3) some characterize message-passing GNNs (MPGNNs) with the CONGEST model but make unrealistic assumptions about computational resources, allowing $\textsf{NP-Complete}$ problems to be solved in $O(m)$ depth. We contend that a well-defined computational model is urgently needed to serve as the foundation for discussions on GNN expressiveness. To address these issues, we introduce the Resource-Limited CONGEST (RL-CONGEST) model, incorporating optional preprocessing and postprocessing to form a framework for analyzing GNN expressiveness. Our framework sheds light on computational aspects, including the computational hardness of hash functions in the WL test and the role of virtual nodes in reducing network capacity. Additionally, we suggest that high-order GNNs correspond to first-order model-checking problems, offering new insights into their expressiveness.

Introduction: The Gap in GNN Expressivity

For years, the "gold standard" for measuring how well a Graph Neural Network (GNN) can distinguish different graph structures has been its alignment with the Weisfeiler-Lehman (WL) graph isomorphism test. However, this paradigm suffers from two major gaps. First, it assumes that one GNN layer is equivalent to one WL iteration, ignoring whether simulating a single WL step is actually "primitive" or computationally hard for a standard GNN. Second, there is a semantic misalignment: WL tests focus on graph distinction, whereas neural network theory typically focuses on function approximation.

Furthermore, many "expressive" GNNs achieve their power by adding complex features (like subgraph counts or resistance distances) during a preprocessing phase. This often introduces "shortcuts" that bypass the actual message-passing challenges, making the GNN appear more powerful than it truly is without accounting for the preprocessing cost.

The RL-CONGEST Framework

To provide a more realistic evaluation, we bridge the gap between deep learning and theoretical computer science using the CONGEST model from distributed computing. We treat a GNN as a distributed system where nodes are processors and edges are communication links with limited bandwidth.

We introduce the Resource-Limited CONGEST (RL-CONGEST) framework, which adds a preprocessing phase and places explicit bounds on a node's local computational power (e.g., limiting it to the $TC^0$ complexity class). This model allows us to analyze the trade-offs between depth, width, and preprocessing complexity.

The RL-CONGEST framework incorporates (1) Preprocessing, (2) Message-Passing with limited computational resources, and (3) Postprocessing to analyze GNN expressiveness.

By using communication complexity reductions, we can prove lower bounds on the depth required for a GNN to simulate a WL iteration. For instance, we reduce the "Equality" problem to the task of simulating WL, showing that in deterministic settings, a GNN might need depth proportional to the number of edges ($m$) just to simulate one WL iteration.

Key Results and the Power of Randomness

Our analysis provides tighter bounds on the depth ($d$) and width ($wp$) required for GNNs to match WL performance. A key insight is the significant advantage of randomized GNNs. While deterministic GNNs struggle with limited message width, randomized GNNs with sufficient random bits can simulate a WL iteration in a single layer with high probability.

A comparison of theoretical bounds for simulating WL iterations, showing the efficiency gains of randomized settings over deterministic ones.

As shown in the results table, to simulate one WL iteration without error (Deterministic/Las Vegas), a GNN needs depth $d = \Omega(D + \frac{m}{wp})$, where $D$ is the diameter and $m$ is the number of edges. In contrast, for the Bounded-Error Randomized setting, we show that with $R = \Theta(\log n)$ random bits, a GNN can achieve $d=1$ provided the color space $C$ is sufficiently large.

Preprocessing "Shortcuts" and Global Properties

We also expose how heavy-duty preprocessing can "cheat" expressivity metrics. Features like "Resistance Distance" essentially solve global structural problems before message passing begins. We proved that while biconnectivity is a global property, it becomes a 1-local property (requiring only one layer of message passing) when resistance distances are provided.

To verify this empirically, we tested biconnectivity on synthetic Erdős-Rényi graphs ($n \in [20, 100]$). The results confirmed that adding global features during preprocessing turns a global structural problem into a trivial task, supporting our argument that preprocessing costs must be accounted for in expressivity analyses.

Conclusion and Future Directions

The RL-CONGEST model provides a rigorous foundation for discussing GNN expressiveness by accounting for computational costs and communication limits. While our work proves what a GNN can do (existential results), future work should address whether these optimal parameters are learnable via gradient descent. Additionally, exploring how these computational limits affect higher-order WL tests ($k$-WL) remains a promising direction for understanding the true power of advanced GNN architectures.

Summary updated

Abstract

Graph Neural Networks (GNNs) are extensively employed in graph machine learning, with considerable research focusing on their expressiveness. Current studies often assess GNN expressiveness by comparing them to the Weisfeiler-Lehman (WL) tests or classical graph algorithms. However, we identify three key issues in existing analyses: (1) some studies use preprocessing to enhance expressiveness but overlook its computational costs; (2) some claim the anonymous WL test's limited power while enhancing expressiveness using non-anonymous features, creating a mismatch; and (3) some characterize message-passing GNNs (MPGNNs) with the CONGEST model but make unrealistic assumptions about computational resources, allowing $\textsf{NP-Complete}$ problems to be solved in $O(m)$ depth. We contend that a well-defined computational model is urgently needed to serve as the foundation for discussions on GNN expressiveness. To address these issues, we introduce the Resource-Limited CONGEST (RL-CONGEST) model, incorporating optional preprocessing and postprocessing to form a framework for analyzing GNN expressiveness. Our framework sheds light on computational aspects, including the computational hardness of hash functions in the WL test and the role of virtual nodes in reducing network capacity. Additionally, we suggest that high-order GNNs correspond to first-order model-checking problems, offering new insights into their expressiveness.
BibTeX
@misc{cui2024rethinking,
  author = {Guanyu Cui and Zhewei Wei and Hsin-Hao Su},
  title = {{Rethinking the Expressiveness of GNNs: A Computational Model Perspective}},
  year = {2024},
  eprint = {2410.01308},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.01308},
}
Figure