PaperlayerView exact revision on arXiv

Source-linked AI summary

How Powerful is Graph Convolution for Recommendation?

Yifei Shen, Yongji Wu, Yao Zhang, Caihua Shan, Jun Zhang, Khaled B. Letaief, Dongsheng Li

arXiv:2108.07567v1cs.IRcs.LGeess.SP

TL;DR

The paper examines how collaborative-filtering embedding quality relates to graph smoothness. It develops a unified graph-filter framework and a closed-form baseline, and reports that GF-CF performs competitively with or better than deep-learning methods.

  • Problem

    The paper examines how embedding quality in collaborative filtering relates to smoothness on the graph.

    Source: §3 · p. 4

  • Method

    The paper unifies collaborative-filtering methods as graph low-pass filters and presents GF-CF, a closed-form method that avoids expensive training.

    Source: §1 · p. 2, §4.1 · p. 5

  • Results

    GF-CF achieves competitive or better performance than deep-learning-based methods.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The authors suggest these insights can inform principled GCN architecture design for recommendation.

    Source: §7 · p. 9

    Untrained LightGCN is not practical when its large embedding dimension makes memory costs and inference time expensive.

    Source: §3 · p. 4

Abstract

from arXiv · show

Graph convolutional networks (GCNs) have recently enabled a popular class of algorithms for collaborative filtering (CF). Nevertheless, the theoretical underpinnings of their empirical successes remain elusive. In this paper, we endeavor to obtain a better understanding of GCN-based CF methods via the lens of graph signal processing. By identifying the critical role of smoothness, a key concept in graph signal processing, we develop a unified graph convolution-based framework for CF. We prove that many existing CF methods are special cases of this framework, including the neighborhood-based methods, low-rank matrix factorization, linear auto-encoders, and LightGCN, corresponding to different low-pass filters. Based on our framework, we then present a simple and computationally efficient CF baseline, which we shall refer to as Graph Filter based Collaborative Filtering (GF-CF). Given an implicit feedback matrix, GF-CF can be obtained in a closed form instead of expensive training with back-propagation. Experiments will show that GF-CF achieves competitive or better performance against deep learning-based methods on three well-known datasets, notably with a $70\%$ performance gain over LightGCN on the Amazon-book dataset.

1 INTRODUCTION

The paper addresses the unclear reasons for GCN-based collaborative filtering’s effectiveness and asks how graph convolution can exploit user-item interactions with less training. It connects recommendation methods through smoothness and low-pass filtering, then introduces closed-form methods including GF-CF.

1 INTRODUCTION

  • The paper asks what makes GCN-based methods effective and how to reduce training cost while using user-item graph information.It notes that LightGCN outperforms NGCF in accuracy and efficiency, while the reasons for GCN-based methods’ effectiveness remain elusive.Source: §1 · p. 1
  • The paper argues that embedding smoothness and low-pass filtering play a pivotal role in GCN-based collaborative filtering.It relates smoothness to similarity between embeddings of interacting users and items.Source: §1 · p. 1
  • LGCN-IDE, the closed-form infinite-dimensional untrained LightGCN, outperforms LightGCN by more than 40% on Amazon-book.The paper attributes untrained LightGCN’s competitiveness with trained LightGCN at sufficiently large embedding dimensions to light convolution’s smoothing effect.Source: §1 · p. 2
  • GF-CF achieves competitive or better performance than deep-learning methods on three datasets, with a closed-form solution that avoids expensive training.The paper describes GF-CF as computationally efficient and says it takes a small fraction of training time.Source: §1 · p. 2
  • Neighborhood-based methods, low-rank matrix factorization, and linear auto-encoders are special cases of the graph-filter framework with different low-pass filters.The paper also frames LightGCN’s light convolution as low-pass filtering.Source: §1 · pp. 1–2

2 PRELIMINARIES

The preliminaries establish the implicit-feedback setting, introduce graph signal processing concepts used to interpret recommendation methods, and outline LightGCN as the paper’s main baseline.

2.1 Notations and Terminology

  • The paper considers recommendation with implicit feedback and defines user and item sets.Source: §2.1 · p. 2

2.2 Graph Signal Processing

  • Graph-signal smoothness is associated with low frequency, while low-pass filters promote smoothness by limiting high-frequency components.Graph convolution transforms a signal to the graph Fourier basis, applies a filter, then transforms it back.Source: §2.2 · p. 3
  • The preliminaries connect linear filters to LightGCN and neighborhood methods, ideal low-pass filters to matrix factorization, and opinion dynamics to linear auto-encoders.Opinion-dynamics filtering requires a matrix inverse or eigenvalue decomposition and therefore introduces high memory cost.Source: §2.2 · p. 3

2.3 LightGCN Brief

  • LightGCN is presented as a state-of-the-art CF method and the paper’s main comparison baseline; it propagates embeddings over the user-item interaction graph.Its final embeddings combine representations across layers; prediction uses the user-item embedding inner product and optimization uses BPR loss.Source: §2.3 · p. 3
  • Figure 1 compares untrained LightGCN performance across embedding dimensions with the LightGCN performance reported in [13].Source: Figure 1 · p. 4

3 ON THE IMPORTANCE OF SMOOTHNESS AND LOW-PASS FILTERING

This section examines how smoothness and low-pass filtering help explain LightGCN’s performance, including when its initial embeddings are random. It develops theoretical and empirical support for this account and derives a closed-form infinite-dimensional variant.

3 ON THE IMPORTANCE OF SMOOTHNESS AND LOW-PASS FILTERING

  • Under the theorem’s stated conditions, smoothing can yield low BPR loss by making interacted pairs’ final embeddings similar despite random initialization.The theorem uses a high-dimensional embedding condition; its analysis also describes positive-pair scores exceeding negative-pair scores.Source: §3 · p. 4
  • The required embedding dimension grows with dataset density, so untrained LightGCN is more effective on sparse datasets.The analysis uses maximum and minimum degrees for a worst-case bound, but says average degree can replace them in practice.Source: §3 · p. 4
  • The section links the shared rating-matrix and graph information to the possibility that suitable low-pass filters can accelerate or avoid training.This is presented as the high-level reason untrained LightGCN can perform well.Source: §3 · p. 4
  • Untrained LightGCN’s test performance improves with embedding dimension and becomes competitive with trained LightGCN when the dimension is sufficiently large.Experiments on Gowalla and Amazon-book agree with the theoretical argument.Source: §3 · p. 4
  • Large embedding dimensions make untrained LightGCN impractical because of memory and inference costs; the infinite-dimensional case has a closed-form predicted score.The paper derives that score for i.i.d. initial embeddings with zero mean and non-zero variance as dimension tends to infinity.Source: §3 · pp. 4–5
  • The framework filters a user’s observed ratings with a graph low-pass filter, then may scale the filtered signal to produce prediction scores.The paper describes this operation as graph convolution.Source: §3 · p. 5
  • The item-item Gram matrix in LightGCN acts as a low-pass polynomial filter and provides a similarity measure underlying neighborhood-based recommendation.Directly using the Gram matrix as item similarity yields a neighborhood-based method.Source: §3 · p. 5
  • More than 40%: LGCN-IDE outperforms LightGCN on Amazon-book under identical training/test splits.The paper reports this comparison for the same training/test data splits.Source: §3 · p. 5

4 A UNIFIED FRAMEWORK

The section extends LGCN-IDE into a general graph low-pass filter framework and interprets several classic collaborative-filtering methods as graph convolutions. It then introduces GF-CF, which combines linear and ideal low-pass filters.

4.1 A Unified Graph Low-pass Filter Based Framework

  • The framework extends LGCN-IDE to general graph filters on a normalized item-to-item adjacency matrix whose eigenvalues lie between 0 and 1.The paper defines the corresponding graph Laplacian as I minus that adjacency matrix.Source: §4.1 · p. 5

4.2 Interpreting Classic Methods from Graph Signal Processing Perspective

  • The section derives spatial GCN interpretations of classic linear recommendation methods, while leaving performance tests of those induced GCNs for future work.The methods are analyzed through graph signal processing and their associated low-pass filters.Source: §4.2 · p. 5

4.2.1 Low-rank Matrix Factorization.

  • Low-rank matrix factorization corresponds to an ideal low-pass filter, and its spatial reformulation is equivalent to an infinite-layer GCN with convolutional normalization.The paper warns that this many-layer view suffers from over-smoothing, which hurts performance.Source: §4.2.1 · pp. 5–6

4.2.2 Linear Auto-encoders.

  • Linear auto-encoder filters act like graph diffusion; their layer-combination coefficients decrease quickly, while storing B carries high memory cost.The paper notes that layer combination helps alleviate over-smoothing and improve performance [13].Source: §4.2.2 · p. 6

4.2.3 Neighborhood-based Approaches.

  • The neighborhood-based formulation is a first-order filter and corresponds to a simple, scalable one-layer GCN that lacks higher-order graph information.The formulation uses the Gram matrix as its similarity matrix [1].Source: §4.2.3 · p. 6

4.2.4 LGCN-IDE.

  • LGCN-IDE corresponds to a multi-layer spatial GCN with a layer combination.Source: §4.2.4 · p. 7

4.3 A Simple yet Effective Baseline Algorithm

  • GF-CF combines a linear filter with an ideal low-pass filter; its formulation uses top-K singular vectors and a tuned parameter.The paper presents the method as a simple baseline and notes that its training is as efficient as LightGCN inference.Source: §4.3 · p. 7
  • GF-CF targets efficiency by combining linear filters, which require normalization during training, with an ideal low-pass filter computed using a generalized power method.The linear-filter training complexity is O(η), while the generalized power method has complexity O((dη + d^3) log(1/ε)) and is efficient when d^2 < η.Source: §4.3 · p. 7

5 EXPERIMENTS

Experiments reuse [13]’s setup to compare the proposed graph-filter methods with established baselines. GF-CF achieves competitive or better overall performance than deep learning-based methods.

5.1 Experimental Settings

5.2 Performance Comparison

  • GF-CF achieves competitive or better performance than deep learning-based methods in the overall benchmark comparison.The comparison is reported in Table 3.Source: Table 3 · p. 7, §5.2 · p. 7

5.1.1 Benchmarks.

  • Following [13], benchmarks include LightGCN, NGCF, GRMF and GRMF-norm, Mult-VAE, GF-CF, and LGCN-IDE; full-rank models [35] are excluded because of out-of-memory on Amazon-book.Source: §5.1.1 · p. 7

5.3 Comparison with LightGCN of Large Embedding Dimension

  • At tested large dimensions, GF-CF remains competitive or higher; LightGCN was not tested above 512 dimensions because of training cost.GF-CF’s total training time is less than one LightGCN training epoch, while LightGCN’s gains become marginal as dimension grows.Source: Table 4 · p. 8, §5.3 · p. 8

5.2.1 LGCN-IDE versus LightGCN.

  • LightGCN outperforms LGCN-IDE on Gowalla and Yelp2018, but LGCN-IDE leads by a large margin on Amazon-book.The authors suspect that uncompressed ratings and the difficulty of SGD optimization on larger data contribute to the Amazon-book gain.Source: §5.2.1 · p. 8
  • The authors argue that learning linear functions is non-trivial for deep networks and that implicit-feedback CF lacks rich features, favoring linear models.They cite these factors to explain why linear models can outperform deep models in this setting.Source: §5.2.2 · p. 8

6 RELATED WORKS

The related work frames collaborative filtering methods as graph signal processing with different low-pass filters. It also contrasts spectral and spatial GCNs by their computational demands and scalability.

6.1 Collaborative Filtering Methods

  • The paper connects model-based and graph-based collaborative filtering by treating their shared rating information through graph signal processing and different low-pass filters.The background describes matrix-factorization, autoencoder, neighborhood-based, and GCN-based approaches.Source: §6.1 · p. 8
  • The authors report that training LightGCN for 400–600 rather than 1000 epochs causes only slight performance loss, reduces training time, and leaves their conclusion unaffected because speedups exceed three magnitudes.Source: §6.1 · p. 8

6.2 Spectral and Spatial GCNs

  • Spectral GCNs require full eigendecomposition and are impractical on large graphs, while spatial GCNs reduce computation through one-hop aggregation and scale to sparse datasets.Prior work unified spectral and spatial GCNs as low-pass filters; this paper extends that view to classic CF methods.Source: §6.2 · p. 9

7 CONCLUSIONS

The conclusion presents embedding smoothness as a link between collaborative filtering and graph signal processing, and reports that GF-CF is competitive with or better than deep learning methods.

7 CONCLUSIONS

  • The paper links embedding smoothness to successful recommendation and shows that neighborhood methods, low-rank matrix completion, and linear autoencoders correspond to graph convolution with low-pass filters.It also presents GF-CF as a simple baseline with competitive or better performance than deep learning-based methods.Source: §7 · p. 9

8 PROOFS

The proof excerpts describe arguments for three results: a probability bound under embedding conditions, an infinite-dimensional LightGCN expression, and a spectral bound for normalized rating matrices.

8.1 Proof of Theorem 3.1

  • Theorem 3.1’s proof handles embedding mutual coherence and a dimension condition before establishing a probability bound of at least 3/4.The excerpt identifies the dimension condition in the proof of the stated result.Source: §8.1 · p. 9

8.2 Proof of Theorem 3.2

  • Theorem 3.2’s proof expands embedding updates into alternating normalized rating-matrix and transpose products, then uses an infinite-dimensional dot-product expectation.The excerpt also states that user embeddings are computed similarly.Source: §8.2 · p. 9

8.3 Proof of Theorem 4.1

  • Theorem 4.1’s proof uses block structure and positive semidefiniteness to show the normalized rating Gram matrix has eigenvalues between 0 and 1.The excerpt identifies the largest eigenvalue as 1 and the minimum as at least 0.Source: §8.3 · p. 10
Loading 2108.07567v1…