# How Expressive are Graph Neural Networks in Recommendation?

arXiv: https://arxiv.org/abs/2308.11127 · HTML: https://mlsanity.com/paper/2308.11127/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 42 references that are in the map.
- First posted on arXiv 22 Aug 2023.

## Builds on (most cited first, 30 of 30)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [Deep Graph Contrastive Representation Learning](https://mlsanity.com/paper/2006.04131/) (2020)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Self-supervised Graph Learning for Recommendation](https://mlsanity.com/paper/2010.10783/) (2020)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Are We Really Making Much Progress? A Worrying Analysis of Recent Neural Recommendation Approaches](https://mlsanity.com/paper/1907.06902/) (2019)
- [Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2112.08679/) (2021)
- [SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation](https://mlsanity.com/paper/2202.03104/) (2022)
- [A Survey on Knowledge Graph-Based Recommender Systems](https://mlsanity.com/paper/2003.00911/) (2020)
- [Revisiting Graph based Collaborative Filtering: A Linear Residual Graph Convolutional Network Approach](https://mlsanity.com/paper/2001.10167/) (2020)
- [LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2302.08191/) (2023)
- [A Troubling Analysis of Reproducibility and Progress in Recommender Systems Research](https://mlsanity.com/paper/1911.07698/) (2019)
- [Hypergraph Contrastive Collaborative Filtering](https://mlsanity.com/paper/2204.12200/) (2022)
- [STAR-GCN: Stacked and Reconstructed Graph Convolutional Networks for Recommender Systems](https://mlsanity.com/paper/1905.13129/) (2019)
- [How Powerful is Graph Convolution for Recommendation?](https://mlsanity.com/paper/2108.07567/) (2021)
- [Multi-Modal Self-Supervised Learning for Recommendation](https://mlsanity.com/paper/2302.10632/) (2023)
- [Knowledge-Enhanced Hierarchical Graph Transformer Network for Multi-Behavior Recommendation](https://mlsanity.com/paper/2110.04000/) (2021)
- [Self-Supervised Hypergraph Transformer for Recommender Systems](https://mlsanity.com/paper/2207.14338/) (2022)
- [Graph Transformer for Recommendation](https://mlsanity.com/paper/2306.02330/) (2023)
- [Disentangled Contrastive Collaborative Filtering](https://mlsanity.com/paper/2305.02759/) (2023)
- [SAIL: Self-Augmented Graph Contrastive Learning](https://mlsanity.com/paper/2009.00934/) (2020)
- [Critically Examining the Claimed Value of Convolutions over User-Item Embedding Maps for Recommender Systems](https://mlsanity.com/paper/2007.11893/) (2020)

## Built on by (most cited first, 3 of 3)

- [A Directional Diffusion Graph Transformer for Recommendation](https://mlsanity.com/paper/2404.03326/) (2024)
- [Graph Spectral Filtering with Chebyshev Interpolation for Recommendation](https://mlsanity.com/paper/2505.00552/) (2025)
- [Graph Neural Diffusion via Generalized Opinion Dynamics](https://mlsanity.com/paper/2508.11249/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have demonstrated superior performance on various graph learning tasks, including recommendation, where they leverage user-item collaborative filtering signals in graphs. However, theoretical formulations of their capability are scarce, despite their empirical effectiveness in state-of-the-art recommender models. Recently, research has explored the expressiveness of GNNs in general, demonstrating that message passing GNNs are at most as powerful as the Weisfeiler-Lehman test, and that GNNs combined with random node initialization are universal. Nevertheless, the concept of "expressiveness" for GNNs remains vaguely defined. Most existing works adopt the graph isomorphism test as the metric of expressiveness, but this graph-level task may not effectively assess a model's ability in recommendation, where the objective is to distinguish nodes of different closeness. In this paper, we provide a comprehensive theoretical analysis of the expressiveness of GNNs in recommendation, considering three levels of expressiveness metrics: graph isomorphism (graph-level), node automorphism (node-level), and topological closeness (link-level). We propose the topological closeness metric to evaluate GNNs' ability to capture the structural distance between nodes, which aligns closely with the objective of recommendation. To validate the effectiveness of this new metric in evaluating recommendation performance, we introduce a learning-less GNN algorithm that is optimal on the new metric and can be optimal on the node-level metric with suitable modification. We conduct extensive experiments comparing the proposed algorithm against various types of state-of-the-art GNN models to explore the explainability of the new metric in the recommendation task. For reproducibility, implementation codes are available at https://github.com/HKUDS/GTE.