🤖 machine learning

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

The paper proposes Mem-GF, a memory-efficient graph filtering method for collaborative filtering that leverages Krylov subspaces to approximate polynomial filters without storing the full item similarity graph, thereby achieving significant reductions in memory usage and runtime while outperforming state-of-the-art methods in accuracy and scalability.

Original authors: Jin-Duk Park, Won-Yong Shin

Published 2026-06-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jin-Duk Park, Won-Yong Shin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "All-Encompassing" Map

Imagine you run a massive library with millions of books (items) and millions of readers (users). To recommend books, you want to know which books are similar to each other.

Traditional methods try to build a giant master map that connects every single book to every other book.

The Analogy: If you have 100,000 books, this map has 10 billion connections. If you have 1 million books, the map has 1 trillion connections.
The Bottleneck: To use this map, your computer needs to hold the entire thing in its memory (RAM) at once. For huge libraries, this map is so big it crashes the computer (an "Out of Memory" error). It's like trying to carry the entire library's catalog in your backpack; it's too heavy, so you can't even start the journey.

The Old Solution: "Training" vs. "Filtering"

The Old Way (GCNs): Some systems try to learn the map by studying every single reader's history over and over again. This is like hiring a librarian to read every book and talk to every customer to learn the connections. It's accurate but takes forever (slow) and requires a huge team (lots of computing power).
The Newer Way (Graph Filtering): Other systems skip the "learning" part. They just use math to smooth out the connections on the map. This is faster, but they still try to carry that giant, heavy master map in their backpack. If the library is too big, they still crash.

The New Solution: Mem-GF (The "Personal Pocket Guide")

The authors propose Mem-GF, a method that changes the strategy entirely. Instead of carrying the giant master map, Mem-GF gives each reader their own tiny, personalized pocket guide.

Here is how it works, using the analogy of a hiking trail:

Don't Draw the Whole Mountain: Instead of drawing a map of the entire mountain range (the item similarity graph), Mem-GF only looks at the path specifically for the person you are helping.
The "Krylov" Step (The Flashlight): Imagine a hiker (the user) standing at a trailhead. Mem-GF uses a mathematical trick called a Krylov subspace. Think of this as a flashlight that only shines on the path directly in front of the hiker, then the path a little further, then a bit further still.
- It doesn't need to see the whole mountain. It just needs to see the immediate steps the hiker will take.
- By taking these steps one by one (using a method called the Lanczos algorithm), it builds a small, local map just for that specific hiker.
The Result:
- Memory: You no longer need a backpack for the whole mountain. You just need a small pocket for the hiker's immediate path. This saves massive amounts of memory (up to 5.74 times less memory usage).
- Speed: Because the computer isn't wrestling with a giant file, it can calculate recommendations much faster (up to 4.38 times faster during setup and 26 times faster during actual use).
- Accuracy: Surprisingly, even though it's looking at a "small" local view, the math is so precise that it actually recommends better than the systems that try to see the whole mountain.

Why This Matters (The Paper's Claims)

The paper claims that Mem-GF solves the "Out of Memory" problem that stops other systems from working on huge datasets (like Amazon or MovieLens with millions of items).

No Crashes: While other methods crash (Out of Memory) when trying to process large datasets on a single computer, Mem-GF runs smoothly.
Training-Free: It doesn't need to spend days "learning" like a student; it just does the math instantly.
Flexible: It can use complex math (high-order polynomials) to make very smart recommendations, which was previously impossible because the computer would run out of memory trying to store the complex formulas.

Summary

Think of Mem-GF as a smart GPS that doesn't try to load the entire world map into your phone. Instead, it calculates the route step-by-step as you walk, keeping your phone's memory free and your battery life high, while still getting you to the right destination faster and more accurately than the old, heavy maps.

Key Takeaway: You don't need to store the whole library to recommend a book; you just need to know the path for the specific reader you are helping. Mem-GF does exactly that.

Technical Summary: Mem-GF (Memory-Efficient Graph Filtering)

1. Problem Statement

Collaborative Filtering (CF) has increasingly relied on Graph Convolutional Networks (GCNs) to model high-order user-item connectivity. However, GCNs suffer from scalability issues due to their recursive message-passing nature and extensive training requirements. As an alternative, training-free Graph Filtering (GF)-based CF methods have emerged, utilizing predefined filters (e.g., linear or polynomial) on item similarity graphs to smooth graph signals efficiently.

Despite their computational advantages, existing GF-based methods face a critical memory bottleneck. These approaches typically rely on a universal, user-agnostic graph filter with dimensions $|I| \times |I|$ (where $|I|$ is the number of items). Even when using sparse matrix operations or top- $k$ eigenvalue approximations, the filtering stage often necessitates storing or operating on the full item similarity matrix. As demonstrated in the paper, this leads to Out-of-Memory (OOM) errors on large-scale datasets (e.g., Amazon-book, ML-20M) even on hardware with 48GB VRAM and 128GB RAM, severely limiting the practical applicability of high-accuracy GF methods in real-world, resource-constrained environments.

2. Methodology: Mem-GF

The authors propose Mem-GF (Memory-efficient Graph Filtering), a novel CF method that eliminates the need to explicitly store the full item similarity matrix. The core innovation lies in leveraging the structure of Krylov subspaces not merely as a computational shortcut, but as the fundamental mechanism for approximating polynomial graph filters on a per-user basis.

Core Mechanism

Instead of applying a global filter to all users, Mem-GF constructs a user-specific Krylov subspace for each user's interaction vector $r_u$ .

Krylov Subspace Construction: For a user $u$ with interaction vector $r_u$ , the method generates a Krylov subspace $\mathcal{K}_K(\tilde{P}, r_u)$ spanned by $\{r_u, \tilde{P}r_u, \tilde{P}^2r_u, \dots, \tilde{P}^{K-1}r_u\}$ , where $\tilde{P}$ is the item similarity matrix.
Lanczos Algorithm: To avoid explicitly forming $\tilde{P}$ $\tilde{P}$ (which would require $O(|I|^2)$ $O (∣ I ∣^{2})$ memory), Mem-GF uses the Lanczos algorithm. It iteratively computes matrix-vector products using the adjusted interaction matrix $\bar{R}$ $\overset{ˉ}{R}$ (where $\tilde{P} = \bar{R}^\top \bar{R}$ $\tilde{P} = \overset{ˉ}{R}^{⊤} \overset{ˉ}{R}$ ). This generates:
- An orthonormal Krylov basis $Q_u \in \mathbb{R}^{|I| \times K}$ .
- A low-dimensional tridiagonal matrix $T_u = Q_u^\top \tilde{P} Q_u \in \mathbb{R}^{K \times K}$ .
Polynomial Filtering: A polynomial graph filter $f(\tilde{P}) = \sum a_n \tilde{P}^n$ is approximated within the subspace as $f(T_u)$ . The final prediction scores $s_u$ are computed as:
$s_u = \|r_u\|^2 Q_u f(T_u) e_1$
This formulation allows the computation of high-order polynomial filters (e.g., 5th order) without ever storing the dense $|I| \times |I|$ matrix.

Theoretical Guarantees

The paper provides a theoretical analysis (Theorem IV.1) stating that if the polynomial degree $N$ is less than the Krylov subspace size $K$ ( $N < K$ ), the Lanczos algorithm incurs no approximation error under exact arithmetic. This ensures that the subspace projection perfectly reproduces the action of the polynomial filter on the user's signal.

Complexity

Space Complexity: Reduced from $O(|I|^2)$ to $O(\text{nnz}(R) + |I|K + K^2)$ , where $\text{nnz}(R)$ is the number of interactions. Since $K \ll |I|$ , this is linear in the number of items.
Time Complexity: $O(|U| K (\text{nnz}(R) + |I|))$ , which scales linearly with the number of users, items, and interactions.

3. Key Contributions

Problem Identification: The authors empirically demonstrate that the reliance on universal, user-agnostic graph filters causes prohibitive memory usage in state-of-the-art GF methods, rendering them infeasible for large-scale datasets.
Principled Solution: Mem-GF introduces a training-free CF approach that integrates Krylov subspaces as the core filtering principle, enabling per-user filter approximation without storing the full item similarity matrix.
Theoretical Support: The paper rigorously analyzes the conditions for lossless approximation (specifically $K > N$ ) and proves linear space/time complexity relative to dataset size.
High-Order Filter Design: By operating in the reduced Krylov space, Mem-GF facilitates the use of high-order polynomial filters (up to 5th order) to approximate complex frequency responses (e.g., Gaussian filters), which were previously infeasible due to memory constraints.

4. Experimental Results

Experiments were conducted on three benchmark datasets: Yelp, Amazon-book, and MovieLens-20M (ML-20M). Mem-GF was compared against 21 competitors, including MF-based, GCN-based, autoencoder-based, and other GF-based methods.

Memory Efficiency: Mem-GF achieved up to 5.74 $\times$ lower memory usage compared to the best-performing GF-based competitors. Notably, while other methods (e.g., EASE, GF-CF, PGSP) failed with OOM errors on the Amazon-book and ML-20M datasets, Mem-GF operated successfully within ~5–8 GB of VRAM.
Runtime Speedup:
- Preprocessing: Mem-GF demonstrated a 4.38 $\times$ speedup in preprocessing time compared to the second-best GF method.
- Inference: It achieved up to a 26.2 $\times$ speedup in inference time compared to GF-CF and Turbo-CF, with inference times as low as 0.0044 seconds on Yelp.
Accuracy: Despite being designed primarily for efficiency, Mem-GF consistently achieved state-of-the-art recommendation accuracy (measured by Recall@20 and NDCG@20) across all datasets, outperforming both training-based GCNs (e.g., LightGCN, NGCF) and other training-free GF methods.
Scalability: The method exhibited near-linear scaling in both memory and runtime as the number of users, items, and interactions increased, validating the theoretical complexity analysis.

5. Significance and Claims

The paper claims that Mem-GF establishes a practically viable and theoretically grounded solution for efficient collaborative filtering. Its significance lies in:

Breaking the Memory Bottleneck: It enables the deployment of high-accuracy, training-free graph filtering on large-scale datasets (tens of millions of interactions) on standard hardware, where previous methods failed.
Balancing Accuracy and Efficiency: It demonstrates that memory efficiency does not require a trade-off in recommendation quality; in fact, the ability to use expressive, high-order filters within a memory-constrained framework leads to superior accuracy.
Real-World Applicability: The low-latency inference and training-free nature make Mem-GF suitable for real-time recommendation systems with stringent hardware constraints.

The authors note limitations, including the method's primary suitability for item similarity graphs derived from user-item interactions (rather than heterogeneous graphs) and potential sensitivity to extremely sparse user signals (cold-start scenarios). Future work is proposed to extend Mem-GF to heterogeneous graph structures and distributed systems.