Memory Is No Longer a Bottleneck: Memory-Efficient Graph Filtering for Scalable Collaborative Filtering

Recommender systems have become a cornerstone component of modern online platforms [25, 3, 6, 7]. By leveraging the information of historical user–item interactions, collaborative filtering (CF) has proven one of the most effective recommendation techniques in uncovering latent user interests and item affinities, facilitating personalization and relevance for positive user experiences [11, 23, 5, 10].

On one hand, graph convolutional networks (GCNs) [18, 10, 52] have emerged as a state-of-the-art CF solution. Thanks to their intrinsic ability to model the high-order connectivity between users and items, GCN-based approaches have achieved high accuracy in various recommendation scenarios [10, 52, 30, 56, 15]. However, GCNs inherently suffer from scalability issues due to their recursive message-passing nature, which may limit their applicability to large-scale systems [1, 60]. As a result, the training time required for GCNs is often significantly longer compared to other architectures such as multi-layer perceptrons (MLPs) that are widely used for CF [60, 64]. This increased computational demand can hinder the efficiency of real-time recommendation systems, making it crucial to explore alternative methods that balance accuracy and scalability.

On the other hand, from the spectral viewpoint, GCNs can be regarded as approximate and learnable graph filters via parameter optimization [18, 43, 27]. To mitigate the extensive training time associated with GCNs, recent research on CF has increasingly focused on graph filtering (GF)-based CF methods that leverage predefined graph filters instead of learnable ones [43, 31, 59, 58, 27]. Due to their training-free nature, GF has been successfully applied beyond standard training-based CF to diverse recommendation scenarios, including sequential [58], group [15], cross-domain [20], multi-modal [40], and multi-criteria [32] recommendations, demonstrating its broad applicability and effectiveness. By using the item similarity graph, these GF-based CF methods transform each user’s interaction vector (i.e., graph signals) via various forms of graph filters, such as linear/ideal low-pass filters (LPFs) or polynomial approximations, to improve computational efficiency of the GF process [43, 58, 27, 31, 59, 36].

Despite these merits, many GF-based CF methods [43, 58, 27, 31, 59] still face a critical memory bottleneck when high-accuracy filters are deployed at scale. Fig. 1 showcases the RAM and VRAM (i.e., GPU memory) usage of six representative GF-based approaches (such as EASE [46], GF-CF [43], PGSP [27], Turbo-CF [31], FPSR [54], and HiGSP [59]) on the Amazon-book dataset [8]. In a single-node environment equipped with 48 GB of VRAM and 128 GB of RAM, most of these methods suffer from out-of-memory (OOM) errors, underscoring their limited feasibility for large-scale recommendation scenarios. The core design issue is not merely implementation, but the reliance on a universal (i.e., user-agnostic) graph filter whose dimension is $|\mathcal{I}|\times|\mathcal{I}|$, where $|\mathcal{I}|$ is the item cardinality, i.e., the number of items. Even when sparse matrix operations, top-$k$ eigenvalue components, or polynomial graph filters reduce computation, the filtering stage still tends to depend on the full-size item similarity matrix. As illustrated in Fig. 2, applying such filters uniformly to all user signals severely limits scalability and can make real-time inference infeasible under memory-constrained environments.

To address this challenge, we introduce Mem-GF, a memory-efficient GF method for CF that goes beyond straightforward Krylov subspace usage. Instead of treating Krylov methods [42, 47] as a computational shortcut, Mem-GF uses them as the filtering principle itself. For each user, a Krylov subspace captures progressively transformed directions of the user’s interaction vector under repeated applications of the item similarity matrix. This enables polynomial graph filtering without explicitly storing the full item similarity matrix. Importantly, Mem-GF facilitates the design of versatile graph filters through high-order polynomial approximations, exemplified by the fifth-order polynomial that closely approximates Gaussian filters widely used in image and graph domains [13, 21]. Notably, Mem-GF offers significant advantages in both preprocessing and inference efficiency. In particular, its memory-efficient and low-latency inference capability addresses a critical requirement for deploying GF-based recommenders in real-world environments, where tight hardware constraints and real-time responsiveness are essential [14, 22].

Our contributions are summarized as follows:

• •

  Problem identification: We clarify the universal (i.e., user-agnostic) graph filter design that causes the memory bottleneck in many GF-based CF methods and empirically demonstrate its impracticality on large-scale datasets.

• •

  Principled Krylov-based solution: We propose a novel GF approach that integrates Krylov subspaces at its core, achieving per-user filter approximation without storing the full item similarity matrix, thereby enhancing filter design flexibility.

• •

  Theoretical support: We rigorously analyze the condition on the number of Krylov subspace bases for which no approximation error occurs. We also theoretically show that Mem-GF achieves linear space/time complexity to the number of items, users, and interactions.

• •

  Comprehensive evaluation: We empirically show that Mem-GF delivers 5.74$\times$ memory savings and 4.38$\times$ speedup. Despite being primarily designed for improving efficiency, it still achieves state-of-the-art recommendation accuracy across all benchmark datasets.

The remainder of this paper is organized as follows. Section II surveys related work. Section III introduces the preliminaries by reviewing GF and Krylov subspaces. Section IV presents the proposed Mem-GF method, including its methodological details, theoretical analysis, and complexity analysis. Section V reports extensive experimental results and analyses evaluating efficiency, scalability, and accuracy. Section VI concludes the paper with a discussion of future research directions.

Table I summarizes the notation that is used in this paper. This notation will be formally defined in the following sections when we introduce our methodology.

We begin by presenting the basic concepts of GF (also known as graph signal processing). First, let us consider a weighted, undirected graph $G=(V,E)$, represented by an adjacency matrix $\mathbf{A}\in\mathbb{R}^{|V|\times|V|}$. A graph signal assigns a scalar or feature vector to each node; in this paper, we primarily consider a scalar signal represented as $\mathbf{x}=[x_{1},x_{2},\ldots,x_{|V|}]^{T}\in\mathbb{R}^{|V|}$, where $x_{i}$ indicates the signal strength of node $i$. The smoothness of $\mathbf{x}$ on $G$ is quantified by the graph quadratic form, a measure based on the graph Laplacian $\mathbf{L}=\mathbf{D}-\mathbf{A}$,¹¹1Alternatively, one may use the normalized Laplacian $\mathbf{L}=\mathbf{I}-\tilde{\mathbf{A}}$, where $\tilde{\mathbf{A}}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$. where $\mathbf{D}=\text{diag}(\mathbf{A}\mathbf{1})$ is the degree matrix and $\mathbf{1}$ denotes the all-ones vector of any dimension for simplicity. The smoothness measure $S(\mathbf{x})$ is formally given by

The smaller the value of $S(\mathbf{x})$, the smoother the signal $\mathbf{x}$ on the graph [45, 43]. Next, we define the graph Fourier transform (GFT) of a signal $\mathbf{x}$ as $\hat{\mathbf{x}}\;=\;\mathbf{U}^{T}\,\mathbf{x}$, where $\mathbf{U}\in\mathbb{R}^{|V|\times|V|}$ comprises the eigenvectors of $\mathbf{L}$. Specifically, from the eigen-decomposition $\mathbf{L}\;=\;\mathbf{U}\,\boldsymbol{\Lambda}\,\mathbf{U}^{T},$ let $\boldsymbol{\Lambda}=\mathrm{diag}(\lambda_{1},\dots,\lambda_{|V|})$ with ordered eigenvalues $\lambda_{1}\leq\dots\leq\lambda_{|V|}$. Because the GFT is an orthogonal linear transform, the inverse GFT is $\mathbf{x}\;=\;\mathbf{U}\,\hat{\mathbf{x}}.$ Finally, we formalize the notions of a graph filter and graph convolution:

In signal processing, signals are typically characterized by their smoothness and low-frequency components, whereas noise is usually non-smooth and dominates at high frequencies [43]. In this context, a significant category of filters is LPFs, which enhance the smoothness of graph signals, thereby aiding noise reduction. We formally define the LPF as follows:

Krylov subspaces compactly capture the repeated action of a large matrix on a vector. Thus, for a user signal, they approximate the spectral properties of the item similarity matrix using the directions generated from that user, instead of requiring a full matrix decomposition. They are mathematically formalized as follows.

Conventional training-free GF-based CF methods [43, 58, 27, 31, 59] in canonical recommendation tasks begin with constructing an item similarity graph, where each item is represented as a node and the similarities between items are modeled as edges. Its adjacency matrix is generally expressed as

where $|\mathcal{U}|$ is the number of users in a dataset; $\mathbf{R}\in\mathbb{R}^{|\mathcal{U}|\times|\mathcal{I}|}$ is the interaction matrix; $\tilde{\mathbf{R}}$ is the normalized interaction matrix; $\mathbf{D}_{\mathcal{U}}=\text{diag}(\mathbf{R}\mathbf{1})$ and $\mathbf{D}_{\mathcal{I}}=\text{diag}(\mathbf{1}^{\top}\mathbf{R})$; $\gamma\in[0,1]$ controls the normalization along users/items; and $\tilde{\mathbf{P}}$ is the adjacency matrix representing the item similarity graph. Meanwhile, the standard notion of GF involves performing full eigenvalue decompositions of the Laplacian or adjacency matrices representing the item similarity graph [29], which incurs a prohibitive computational complexity of $O(|\mathcal{I}|^{3})$. To prevent such computational issues, scalable GF-based CF methods exploit several techniques, including sparse matrix operations [43], top-$k$ eigenvalue components [43, 58], polynomial graph filters [31], and user clustering [59]. Nevertheless, they still depend on the full-size item similarity matrix during filtering. For example, GF-based CF methods [43, 58, 27, 59] typically leverage linear LPFs and/or ideal LPFs extracting only the top-$k$ eigenvalue components instead of fully decomposing the item similarity matrix:

where $\mathbf{s}_{u}\in\mathbb{R}^{|\mathcal{I}|}$ is the predicted preferences for user $u$; ${\mathbf{r}}_{u}$ denotes the $u$-th row of $\mathbf{R}$, treated as a column graph signal for user $u$; $\bar{\mathbf{U}}\in\mathbb{R}^{|\mathcal{I}|\times k}$ is the top-$k$ singular vectors of $\tilde{\mathbf{R}}_{0}$; $\tilde{\mathbf{P}}$ is the linear LPF; $\mathbf{D}^{-1/2}_{U}\bar{\mathbf{U}}\bar{\mathbf{U}}^{T}\mathbf{D}^{-1/2}_{I}$ is the ideal LPF of $\tilde{\mathbf{P}}$; and $\mu$ is a hyperparameter balancing between the two filters. However, due to their limited expressiveness in designing various filters having different frequency response functions, recent studies proposed to use polynomial graph filters to produce diverse frequency response functions using polynomial functions [31, 43, 36]. As representative work [31], the prediction score for user $u$ via polynomial GF is formulated as

where $\{a_{n}\}_{n=1}^{N}$ are the polynomial coefficients; $N$ is the maximum order of the matrix polynomial; and $\sum_{n=1}^{N}a_{n}\tilde{\mathbf{P}}^{n}$ represents the polynomial graph filter on the item similarity graph. It was proven that the polynomial graph filter $\sum_{n=1}^{N}{a_{n}}\tilde{\mathbf{P}}^{n}$ has a frequency response function of $\sum_{n=1}^{N}{a_{n}}(1-\lambda)^{n}$ [31, 43, 36].

While conventional GF-based CF methods have adopted user-specific batch strategies (see (7) and (8)), they still suffer from expensive costs for constructing or applying a universal (i.e., user-agnostic) graph filter across all users based on the large item similarity matrix $\tilde{\mathbf{P}}$ (see Fig. 2). For instance, a simple linear LPF (i.e., $\tilde{\mathbf{P}}$) having a frequency response function of $h(\lambda)=1-\lambda$ has a dimension of $(|\mathcal{I}|,|\mathcal{I}|)$. Moreover, ideal LPFs or higher-order polynomial filters can further increase memory footprint and computation. As a result, devising a memory-efficient polynomial GF technique that can effectively operate under resource-constrained environments becomes a critical research challenge. This raises a natural question: “How can we optimize batch processing for each user to enhance memory efficiency in GF-based recommendations?” To answer this question, we elaborate on the proposed Mem-GF method in the following subsection.

To directly overcome the challenges outlined in Section IV-A, we propose Mem-GF, a memory-efficient CF method that leverages polynomial GF without incurring the prohibitive memory costs of conventional GF-based CF approaches. The core idea is to use the Krylov subspace for each user signal, thereby approximating matrix-vector operations without explicitly forming or storing large matrices such as $\tilde{\mathbf{P}}$. The Krylov subspace $\mathcal{K}_{K}(\tilde{\mathbf{P}},\mathbf{r}_{u})$ in (5), defined as the span of vectors $\{\mathbf{r}_{u},\tilde{\mathbf{P}}\mathbf{r}_{u},\tilde{\mathbf{P}}^{2}\mathbf{r}_{u},\dots,$ $\tilde{\mathbf{P}}^{K-1}\mathbf{r}_{u}\}$, captures progressively transformed directions of user $u$’s interaction vector under the repeated action of $\tilde{\mathbf{P}}$. By restricting computations to $\mathcal{K}_{K}(\tilde{\mathbf{P}},\mathbf{r}_{u})$, we approximate the spectral properties of $\tilde{\mathbf{P}}$ in the user-specific Krylov subspace. To construct its orthonormal basis, we utilize the Lanczos algorithm [19], which avoids direct eigenvalue/eigenvector computation. The schematic overview of the Mem-GF method is illustrated in Fig. 3. We summarize the pseudocode of Mem-GF in Algorithm 1.

All GF-based CF algorithms [43, 31, 46, 27, 59] are implemented using PyTorch tensors [33] to ensure a consistent experimental environment. Whenever a method exceeds the size of GPU VRAM, we revert to CPU-only computation leveraging system RAM to complete the process without disrupting the pipeline. For FPSR [54], we use $\tau=0.3$ as a default hyperparameter to generate 6 partitions. For Turbo-CF, we identically use the three predefined filters presented in [31, 15]. Since the filtering matrix is constructed as $\bar{\mathbf{R}}^{\top}\bar{\mathbf{R}}$, using $\bar{\mathbf{r}}_{u}$ also aligns the user signal with the same normalization and adjustment applied to the item similarity matrix. This alignment is particularly helpful for the ML-20M dataset, where interactions are highly concentrated on popular items, because it mitigates popularity-dominated signal amplification.

To evaluate the scalability of our Mem-GF in Section V-D, we generated sets of synthetic interaction matrices with varying dimensions and sparsity levels. In particular, we employ the random matrix generation function provided by the scipy.random module in the SciPy package [49] to create these matrices. By default, the number of users, items, and nonzero entries (i.e., the number of interactions) was set to 5,000, 5,000, and 225,000, respectively. In order to assess scalability across a wide range of problem sizes, the experiments are carried out according to the following setup:

• •

  Varying the number of users/items: The number of users and items is systematically increased to each of the following values: 1,000, 5,000, 10,000, 15,000, 20,000, 30,000, 40,000, 50,000, 80,000, and 100,000.

• •

  Varying the number of interactions: The number of nonzero entries (i.e., $\mathrm{nnz}(R)$) is scaled to 225,000, 1,125,000, 2,250,000, 4,500,000, 6,750,000, 9,000,000, and 11,250,000.

For each configuration, we record the corresponding memory usage and runtime of our Mem-GF. These systematic variations allow us to quantify how the performance of our method scales w.r.t. the number of users, items, and interactions.

Table III summarizes the comparison of Mem-GF with existing GF-based recommendation methods in terms of memory usage and runtime on the three benchmark datasets during preprocessing (i.e., offline computation). Table IV shows the runtime comparison among Mem-GF and three representative CF methods that require model training (NGCF, LightGCN, and DiffRec). Our key observations are as follows:

1. (i)

   Leveraging the low-dimensional Krylov subspace, Mem-GF significantly reduces both memory consumption and computation time compared to other GF-based CF competitors.

2. (ii)

   On Amazon-book, where the set of items is relatively large, most GF-based CF competitors encounter OOM errors on the single GPU device. In contrast, Mem-GF efficiently operates within around 5GB of VRAM under the first-order polynomial filter, demonstrating up to a 574% memory advantage and a 438% runtime speedup compared to the second-best performers. Even with higher-order polynomial filters, Mem-GF maintains a VRAM usage of around 8GB.

3. (iii)

   On ML-20M, the extremely large number of interactions (20M) triggers buffer OOM issues for many competing methods when performing sparse matrix multiplications on the GPU, forcing them to rely solely on CPU computations and resulting in prolonged runtime. On the contrary, Mem-GF seamlessly handles high-order filters without such memory bottlenecks.

4. (iv)

   Table IV demonstrates the benefits of Mem-GF over representative CF methods that require model training in terms of runtime. Because Mem-GF is entirely training-free, it circumvents the costly iterative parameter optimization loops. Notably, on the datasets having a large amount of interactions, such as ML-20M, Mem-GF significantly outperforms two-tower models based on pairwise optimization (e.g., NGCF and LightGCN), highlighting its practical value in scenarios where both accuracy and speed are critical.

Table V reports the single-batch inference cost (i.e., the convolution with graph signals) on the Yelp dataset, as other datasets exhibit similar trends. The comparison assumes that the graph filter ($H(\mathbf{L})$ in (3)) has already been precomputed and focuses only on runtime and peak GPU memory usage during inference.

1. (i)

   By confining the graph convolution entirely within a low-dimensional Krylov subspace, Mem-GF completes inference in $0.0044$ seconds, yielding up to a 26.2$\times$ speedup over GF-CF and Turbo-CF, both of which require convolution with a full $|\mathcal{I}|\times|\mathcal{I}|$ graph filter. Even with the fifth-order filter, Mem-GF maintains low latency, supporting real-time recommendation systems.

2. (ii)

   Since Mem-GF avoids explicit construction and storage of the full-size $|\mathcal{I}|\times|\mathcal{I}|$ matrix, it achieves over a 10.5$\times$ reduction in peak VRAM usage compared to Turbo-CF. The memory footprint remains nearly unaffected by the polynomial order because the compact Krylov basis dominates the filtering cost, whereas GF-CF requires dense filter storage for ideal LPF computations.

To empirically validate our theoretical complexity analysis in Section IV-B4, we conduct experiments on synthetic datasets (i.e., interaction matrices) with varying scales of users, items, and interaction densities. Specifically, in Fig. 5, we present how Mem-GF’s memory usage and runtime for preprocessing scale as $|\mathcal{U}|$, $|\mathcal{I}|$, and $\mathrm{nnz}(R)$ grow. By default, the number of users, items, and interactions was set to 5,000, 5,000, and 225,000, respectively. Furthermore, in Fig. 6, we compare Mem-GF with two representative GF-based CF competitors (GF-CF and Turbo-CF) when $|\mathcal{I}|$ increases. For a fair comparison with GF-CF, both Turbo-CF and Mem-GF employ the first-order polynomial graph filter. We highlight the following observations:

1. (i)

   As shown in the left side of Fig. 5, Mem-GF exhibits memory usage growing nearly linearly with $|\mathcal{U}|$, $|\mathcal{I}|$, and $\mathrm{nnz}(R)$. Notably, the memory footprint is significantly reduced compared to the case of forming the item similarity matrix of size $|\mathcal{I}|\times|\mathcal{I}|$, allowing Mem-GF to make full use of GPU acceleration even on large datasets. We note that the size of RAM does not tend to scale with the increasing data dimension as long as VRAM is sufficiently available.

2. (ii)

   As shown in the right side of Fig. 5, the runtime of Mem-GF also scales linearly as each data dimension grows. This validates the scalability of Mem-GF. Moreover, since Mem-GF efficiently operates within the GPU VRAM, its runtime only takes less than 11 seconds even when $\mathrm{nnz}(R)$ increases up to $10^{7}$ via the exploitation of the GPU resource.

3. (iii)

   In Fig. 6, we observe that Mem-GF is substantially more scalable in both memory and runtime, compared to GF-CF and Turbo-CF. In particular, GF-CF incurs excessive memory overhead due to its dense ideal LPF matrix having dimensionality of $(|\mathcal{I}|,|\mathcal{I}|)$, thus yielding superlinear complexity in practice.

These results also indicate how sparsity affects Mem-GF: increasing $\mathrm{nnz}(\mathbf{R})$ raises runtime through sparse matrix-vector products, but the growth remains close to linear because the full item similarity matrix is never formed.

Table VI summarizes the recommendation accuracy of Mem-GF and various competitors across three distinct datasets. The main findings are as follows:

1. (i)

   Despite its exceptional computational efficiency, Mem-GF achieves the highest accuracy for all datasets (except the recall on Yelp), underscoring its robustness across diverse data characteristics.

2. (ii)

   In particular, the gains of Mem-GF over training-dependent models are indeed substantial across all datasets.

3. (iii)

   Mem-GF consistently exhibits gains over Turbo-CF, another polynomial GF approach. On the Amazon-book dataset, Turbo-CF was restricted only to the first-order linear filter to avoid OOM issues (see Table III), whereas Mem-GF can freely use higher-order filters without incurring any resource scarcity issues on a single device. This design can improve accuracy empirically, not because memory reduction itself guarantees better predictions, but because expressive polynomial filters can be selected within the user-specific Krylov subspace without being constrained by the storage cost of full-size graph filters.