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
this https URL

本文提供了关于图神经网络在推荐系统中表达能力的全面理论分析，考虑了图同构、节点自同构和拓扑接近度等三个层面的表达能力指标，并引入了拓扑接近度指标来评估图神经网络对节点之间结构距离的捕捉能力，从而更好地满足推荐任务的目标。为了验证这一新指标对推荐性能评估的有效性，我们介绍了一种适用于该指标的无学习图神经网络算法，并进行了广泛的实验证明其可解释性在推荐任务中的表现，代码可在给出的链接中获得。