How Expressive are Graph Neural Networks in Recommendation?

Xuheng Cai, Lianghao Xia, Xubin Ren, Chao Huang

Introduction

Graph Neural Networks (GNNs) have become the standard architecture for modern recommendation systems, yet their theoretical foundations remain largely borrowed from other domains. Specifically, the "expressiveness" of GNNs is traditionally measured by the Weisfeiler-Lehman (WL) test, a benchmark designed to determine if a model can distinguish between different graph structures. While the WL test is highly effective for tasks like molecule classification, it does not align with the primary objective of recommendation: ranking items for a specific user. This paper challenges the standard expressiveness paradigm and proposes a more relevant metric for recommendation tasks: Topological Closeness (TC).

The Expressiveness Gap in Recommendation

In recommendation systems, the goal is not to classify the entire graph but to understand the relationship between specific nodes (users and items). Standard GNNs often struggle with "automorphic nodes"—nodes that are structurally symmetric within the graph. To a traditional message-passing GNN, these nodes appear identical, making it impossible for the model to rank one over the other for a given user.

Furthermore, there is a notable gap between the empirical success of GNNs and our theoretical understanding of why they work. While models like LightGCN perform well, we lack a metric that explains how effectively they capture the distance and structural relationship between users and items. The authors argue that instead of focusing on graph-level symmetry, researchers should focus on a model's ability to capture the topological nuances of the user-item bipartite graph.

Redefining Expressiveness: Topological Closeness

The authors propose a three-level framework to analyze GNN expressiveness:

  1. Graph-level: Graph isomorphism (the classic WL test).
  2. Node-level: Node automorphism (the ability to distinguish symmetric nodes).
  3. Link-level: Topological Closeness (TC).

Topological Closeness is a new metric that counts the number of paths of length $k$ between two nodes. Unlike traditional metrics like geodesic distance (shortest path), TC accounts for both the distance and the local cluster density. For example, if a user has multiple paths to Item A but only a single path to Item B, TC recognizes Item A as more relevant, even if the shortest path to both items is the same length.

The Graph Topology Encoder (GTE)

To demonstrate the power of the TC metric, the authors introduced the Graph Topology Encoder (GTE). GTE is a "learning-less" GNN, meaning it contains no trainable weights and requires no backpropagation. The model operates through a deterministic process:

  • Initialization: Each item is assigned a unique one-hot ID.
  • Message Passing: The model uses simple message passing (summing neighbor features) combined with residual connections.
  • Scoring: The raw values in specific dimensions of the resulting embeddings are used directly as recommendation scores.

By using one-hot IDs and residual connections, GTE can perfectly distinguish all symmetric nodes on a bipartite graph—a feat that many complex, trainable GNNs fail to achieve. GTE serves as a pure mathematical implementation of topological closeness, stripping away the "learning tax" associated with gradient descent.

Experimental Results

The authors evaluated GTE against state-of-the-art (SOTA) Graph Contrastive Learning (GCL) models across six real-world datasets, ranging from dense (Yelp, Tmall) to extremely sparse (Amazon-beauty, Sparser-Tmall).

Performance on Sparse Data

GTE consistently outperformed complex deep learning models on sparse datasets. On the Sparser-Tmall dataset, GTE improved Recall@20 by 14% and NDCG@20 by 23% over the best-performing baseline. This suggests that on sparse data, the process of training weights can actually introduce noise, whereas GTE’s reliance on pure graph topology provides a more stable and accurate signal.

Computational Efficiency

Because GTE requires no training, its efficiency is orders of magnitude higher than its competitors. On the Yelp dataset, the SOTA model (LightGCL) required 216 minutes of training on a high-end GPU. In contrast, GTE completed the same task in 1.85 minutes on a standard CPU. Even on denser datasets where learning-based models have a slight edge in accuracy, GTE remained highly competitive while being significantly cheaper to deploy.

Conclusion and Future Directions

The success of GTE reveals an "alignment gap" in current GNN research. Using Kendall’s Tau correlation, the authors showed that popular models like LightGCN often correlate poorly with the ideal topological closeness ranking, suggesting they are not fully utilizing the structural information available in the graph.

While GTE is highly effective, it is currently limited to structural data and ignores "side information" such as user demographics or item descriptions. The authors suggest that future research should focus on developing "well-justified model structures"—architectures that combine the provable structural power of Topological Closeness with the ability to integrate rich, non-topological features.

Summary updated

BibTeX
@inproceedings{cai2023how,
  author = {Xuheng Cai and Lianghao Xia and Xubin Ren and Chao Huang},
  title = {{How Expressive are Graph Neural Networks in Recommendation?}},
  booktitle = {ACM International Conference on Information and Knowledge Management},
  year = {2023},
  doi = {10.1145/3583780.3614917},
}
Figure