# PriviRec: Confidential and Decentralized Graph Filtering for Recommender Systems

Julien Nicolas, César Sabater, Mohamed Maouche, Mark Coates, Sonia Ben Mokhtar

► To cite this version:

Julien Nicolas, César Sabater, Mohamed Maouche, Mark Coates, Sonia Ben Mokhtar. PriviRec: Confidential and Decentralized Graph Filtering for Recommender Systems. CIKM 2025 - ACM International Conference on Information and Knowledge Management, Nov 2025, Séoul, South Korea. pp.1-9, 10.1145/3746252.3761152 . hal-05308553

HAL Id: hal-05308553

https://hal.science/hal-05308553v1

Submitted on 10 Oct 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# PriviRec: Confidential and Decentralized Graph Filtering for Recommender Systems

Julien Nicolas

INSA Lyon

CNRS

Villeurbanne, France

julien.nicolas@insa-lyon.fr

César Sabater

INSA Lyon

CNRS

Villeurbanne, France

Mohamed Maouche

INSA Lyon

INRIA

Villeurbanne, France

Mark Coates

McGill University

ILLS

Montreal, Canada

Sonia Ben Mokhtar

INSA Lyon

CNRS

Villeurbanne, France

## Abstract

Recent advances in recommender systems have shown that relying on graph filters, such as the normalized item-item adjacency matrix and the ideal low-pass filter yields competitive performance and scales better than Graph Convolutional Networks-based solutions. However, these solutions require centralizing user data, which raises concerns over data privacy, security, and the monopolization of user data by a few actors. To address those concerns, we propose PriviRec and PriviRec-k, two complementary recommendation frameworks. In PriviRec, we show that it is possible to decompose widely used filters so that they can be computed in a distributed setting using Secure Aggregation and a distributed version of the Randomized Power Method, without revealing individual users contributions. PriviRec-k extends this approach by having users securely aggregate low-rank projections of their contributions, enabling a tunable balance between communication overhead and recommendation accuracy. We demonstrate theoretically as well as experimentally on Gowalla, Yelp2018, and Amazon-Book that our methods achieve performance comparable to centralized state-of-the-art recommender systems and superior to decentralized ones, while preserving confidentiality and low communication and computational overheads.

## CCS Concepts

* Information systems → Recommender systems; * Security and privacy → Software and application security; * Computing methodologies → Machine learning algorithms.

## Keywords

decentralized, distributed, privacy, Secure Aggregation, GF-CF, BSPM

## ACM Reference Format:

Julien Nicolas, César Sabater, Mohamed Maouche, Mark Coates, and Sonia Ben Mokhtar. 2025. PriviRec: Confidential and Decentralized Graph Filtering for Recommender Systems. In *Proceedings of the 34th ACM International Conference on Information and Knowledge Management (CIKM '25), November 10–14, 2025, Seoul, Republic of Korea*. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3746252.3761152

<figure><img src="image_2.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License. CIKM '25, *Seoul, Republic of Korea*

© 2025 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2040-6/2025/11 https://doi.org/10.1145/3746252.3761152

## 1 Introduction

Recommender systems enable personalized user experiences in services ranging from e-commerce to media streaming and social networks. Over the years, the quest for better performance has led back to classical Collaborative Filtering approaches such as Matrix Factorization [24] and Neural Network-based recommender systems, followed by Graph Neural Network approaches. More recently, state-of-the-art systems like Graph Filter based Collaborative Filtering [47] and Blurring-Sharpening Process Models for Collaborative Filtering [11] achieve superior performance by incorporating graph-based filters such as the normalized item-item matrix and the ideal low-pass filter [20, 21]. These methods are typically trained and evaluated on centralized datasets.

However, the wide use of centralized recommender systems raises concerns over data security, and the monopolization of user data by a few corporations, which could lead to censorship, promotion of some products over others, or private data leaks [1, 15].

Enforcing privacy in recommender systems is not a new goal: recommender systems relying on cryptographic techniques can offer strong guarantees but are generally computationally costly [8, 55]. On the other hand, the use of Differential Privacy may cause heavy utility loss [46]. Decentralization, which prioritizes keeping data locally rather than sharing it with a centralized entity, offers a flexible path to privacy and data ownership and can also be combined with cryptographic or differential privacy techniques for enhanced guarantees. In the context of recommender systems, decentralization allows users to retain control over their personal data while contributing to collaborative computations [4]. However, implementing decentralized learning presents a number of research challenges, such as ensuring competitive model accuracy, minimizing communication and computational costs.

Federated Learning (FL) [25, 39, 40] and Gossip Learning (GL) [22] emerged to address these challenges. FL allows multiple participants to collaboratively train machine learning models, while keeping their data locally, by coordinating the training through a
central server that aggregates locally computed updates. This framework has shown promise for simpler models, such as matrix factorization [8], but scaling it to graph-based recommender systems remains largely unexplored [19, 52] as some require knowledge of global graph information [20, 57] or external knowledge [54, 59]. GL is a fully decentralized paradigm which does not require a central server. Instead, participants exchange model updates or partial computations with a subset of their peers. Although gossip-based methods are more robust to failures and can scale to large networks [22], these advantages come with trade-offs in terms of convergence speed and implementation complexity for models involving global operations like Singular Value Decomposition. Therefore, most existing decentralized approaches [4, 17] for recommender systems focus on simple models (e.g., k-Nearest Neighbors, Generalized Matrix Factorization [8, 21, 24]) or use truncated versions of standard datasets (i.e., with ~1000 users for GL [4] or 6k-12k users for FL [35, 56]), facing scalability challenges in simulation.

Hence, while FL and other decentralized solutions are natural candidates for privacy-preserving recommender systems, they struggle to address the complexity of recent powerful methods that rely on global graph-based filtering, primarily due to the inherent reliance of these methods on global graph structures and operations that are challenging to distribute without compromising efficiency, convergence, or data privacy. Specifically, decentralizing these graph-based filtering methods requires solving the issues of securely aggregating node-level information across a distributed network without exposing user-sensitive data and efficiently computing low pass filters of the global graph.

## 2 Contributions

To address this gap, we introduce **PriviRec** and **PriviRec-k** to decentralize the computation of global graph-based filters in a confidential manner. This decentralization allows users to collaborate and to benefit from recommendations from latest recommender systems while retaining sensitive interaction data locally. In **PriviRec**, we show that it is possible to decompose widely used filters so that they can be computed in a distributed setting using Secure Aggregation Bell et al. [5] and a distributed version of the Randomized Power Method, without revealing individual users contributions. **PriviRec-k** extends this approach by the use of low-rank approximations to reduce communication costs while maintaining competitive recommendation accuracy compared to centralized methods. The communication and computation costs of both **PriviRec** and **PriviRec-k** scale logarithmically with the number of users, allowing for large scale recommendation scenarios.

Our main contributions are as follows:

(1) **Computations on decentralized data:** We propose collaborative and privacy-preserving methods to compute fundamental components in constructing filters for recommender systems, using decentralized data. Specifically, we propose decentralized methods to compute the normalized item-item matrix, used in [9, 11, 12, 20, 23, 28, 29, 33, 38, 42, 44, 47, 53] and the ideal low-pass filter, used in [11, 42, 47].

(2) **Confidentiality:** We stand on the formally proven security guarantees of Secure Aggregation [5] for our decentralized computations, and prove that the results of our computations

do not leak confidential user data. To the best of our knowledge, we are the first to decentralize key recommender system components while preserving user confidentiality while incurring no loss in recommendation utility, and keeping a reasonable computational overhead.

(3) **Communication and computation efficiency: PriviRec and PriviRec-k** use graph-based recommendation filters computed efficiently through a small number of power iterations, significantly reducing computational and communication complexity compared to previous costly gradient-based federated methods [35, 51]. Specifically, **PriviRec-k** achieves up to 95% communication reduction per client on Gowalla compared to federated GCN-based systems, while preserving recommendation accuracy similar to centralized methods. We also offer an analytical cost comparison with competitors.

(4) **Empirical benchmarking:** We validate our decentralized methods on standard full-scale recommendation datasets, including Gowalla, Yelp2018, and Amazon-Book, which contain up to 50,000 users, while competitors evaluate on reduced datasets containing 6,000-12,000 users [35, 56]. We show that the proposed methods achieve performance superior to existing decentralized methods in terms of NDCG and Recall. For instance, on the Amazon-Book dataset, **PriviRec**, attains an NDCG@20 of 0.0611, nearly doubling the performance of the best decentralized baseline, PerFedRec++ (0.0315).

## 3 Preliminaries

### 3.1 Centralized Recommender Systems

Recommender systems typically rely on a large dataset of user-item interactions held by a single central server to predict user preferences and recommend interesting items. These systems use algorithms such as matrix factorization, nearest-neighbor approaches, or graph-based methods to model user behavior and item similarities. We present here key background material for our contributions.

3.1.1 **Graph-Based Representation.** User-item interaction histories used to train a recommender systems are often modeled as user-item bipartite graphs [20, 47]. For one such graph $G(V, E)$, nodes $V$ represent either users ($U$) or items ($I$), and edges $E$ represent interactions between users and items. The whole graph is typically held by a central server.

3.1.2 **User-Item interaction matrix $R$:** This matrix captures user preferences, where each entry $r_{ui}$ represents the interaction between user $u \in U$ and item $i \in I$. $r_{ui}$ may be binary (whether there exists an edge in $E$ between the nodes associated with $u$ and $i$) or continuous (e.g., ratings). We focus on the binary case and define $r_{ui} = 1$ if user $u$ interacted with item $i$ and $r_{ui} = 0$ otherwise (as commonly done in prior work, e.g. [11, 20, 47]).

3.1.3 **Normalized User-Item interaction matrix $\tilde{R}$:** The User-Item Interaction Matrix $R$ is often normalized to avoid overweighting popular items or popular users. In Choi et al. [11], Shen et al. [47], the normalized users and items degrees matrices are defined as: $U = \text{Diag}(R \cdot 1_{|I|})$ and $V = \text{Diag}(1_{|U|} \cdot R)$. Then,

$$ \tilde{R} = U^{-\alpha} R V^{\alpha-1}, \quad (1) $$
where $\alpha$ is a hyperparameter.

### 3.1.4 Normalized Item-Item Matrix $\tilde{P}$, $\tilde{P}$ represents similarities or relationships between items based on user interactions. As in Choi et al. [11], Shen et al. [47], it is defined as:

$$ \tilde{P} = \tilde{R}^{\top} \tilde{R}. \qquad (2) $$

The normalized item-item matrix $\tilde{P}$ can be viewed as an adjacency matrix that models item connectivity.

### 3.1.5 Ideal Low Pass Filter $F_{IDL}$.
This filter is used in graph signal processing to smooth signals (e.g., ratings) over a graph, to keep dominant patterns while suppressing noise. It is defined as:

$$ F_{IDL} = V^{-\frac{1}{2}} S_k S_k^{\top} V^{\frac{1}{2}}, \qquad (3) $$

where $S_k$ contains the top-k singular vectors of the normalized interaction matrix $\tilde{R}$.

### 3.1.6 Workflow in Centralized Item-Item Matrix Based Systems.
In the centralized setting, the construction and application of an item-item matrix based recommender system is generally as follows:

(1) **Graph Construction:** Generate a graph representation of the data, for which nodes and edges correspond respectively to items and interactions.

(2) **Preprocessing:** Construct the interaction matrix $R$, normalize it using Eq. (1), and compute derived matrices like $\tilde{P}$ using Eq. (2).

(3) **Model Training:** Use models such as Matrix Factorization or GNNs to learn embeddings or predictive models.

(4) **Recommendation:** Predict user-item interactions using the learned model and components such as the item-item, user-item or user-user matrices or the Ideal Low Pass Filter.

**In this work,** we focus on recommender models GF-CF [47], BSPM [11] and Turbo-CF [42], which offer state-of-the-art recommendation accuracy, scalability and training time. Both GF-CF and BSPM use the normalized item-item matrix $\tilde{P}$ and the Ideal Low Pass Filter $F_{IDL}$ while Turbo-CF only uses $\tilde{P}$. We now present the inference procedures of each recommender model in more details.

**GF-CF.** During the inference phase of GF-CF, the predicted interaction matrix $S$ is computed as $S = R \cdot (\tilde{P} + \lambda \cdot F_{IDL})$, where $\lambda = 0.3$, and $\alpha = \frac{1}{2}$ for the computation of $\tilde{R}$ [47].

**Turbo-CF.** During the inference phase of Turbo-CF, the predicted interaction matrix $S$ is computed as $S = R \cdot (\sum_{k=1}^{K} \alpha_k \tilde{P})$, where $\tilde{P} = \tilde{P}^{os}$, with $\circ$ representing element-wise exponentiation. $s$, $K$, $\alpha$ and $\alpha_k$ are hyperparameters whose optimal values are given by Park et al. [42] depending on the datasets.

**BSPM.** We refer to the original paper of Choi et al. [11] for the computation of the interaction matrix $S$ using BSPM. It is a generalization of Eq. (3.1.6) using Ordinary Differential Equations. The set of hyperparameters can be selected so that its yields exactly Eq. (3.1.6). As for GF-CF, $\alpha = \frac{1}{2}$ for the computation of $\tilde{R}$.

## 3.2 Secure Aggregation

Let $\mathcal{U}$ be a set of users connected to a server and wanting to participate in a computation, with $|\mathcal{U}| = n$. Let matrices $\{R^{(u)}|u \in \mathcal{U}\}$ be held locally by users, i.e., $R^{(u)}$ is locally held by user $u$. We denote by $A = \text{SecAgg}(R^{(u)}, \mathcal{U})$ the Secure Aggregation of locally

held matrices $R^{(u)}$ over the set of users $\mathcal{U}$. This computation is equivalent to computing $A = \sum_{u \in \mathcal{U}} R^{(u)}$ over a secure channel, without revealing each individual contribution $R^{(u)}$ or any extra information other than this outcome. In this paper, we use a Secure Aggregation protocol introduced in Bell et al. [5] for its lightweight computation and communication overhead. This protocol scales poly-logarithmically in the number of parties. We note that our methods are compatible with a wide range of Secure Aggregation protocols (e.g., [5, 6, 48]) and decentralized private averaging methods using correlated noise (e.g., [2, 45]).

# 4 Proposed method

We propose collaborative and privacy-preserving methods to compute the normalized item-item matrix (Eq. (2), used in [9, 11, 12, 20, 23, 28, 29, 33, 38, 42, 44, 47, 53]) and the ideal low-pass filter (Eq. (3), used in [11, 42, 47]), which are fundamental components in constructing general filters for recommender systems. To enable their use in decentralized settings while preserving user privacy, we propose two variants of our method:

(1) **PriviRec:** A simple yet efficient approach for computing the graph filters in a confidential and distributed setting.

(2) **PriviRec-k:** A variant offering a trade-off between communication cost and recommendation accuracy using low-rank projections.

The components computed using either PriviRec or PriviRec-k can subsequently be used and combined in multiple ways. In our experiments, we use them to instantiate decentralized versions of GF-CF, Turbo-CF and BSPM to benchmark their utility. In the following subsections, we describe the major steps of our workflows.

## 4.1 System Model

We give an overview of our system in Figure 1. Our protocol involves $n$ clients and a coordinating server. Each client $u$ holds its private interaction vector $R^{(u)} \in \mathbb{R}^{|\mathcal{I}|}$, and never transmits raw data. Instead, the server orchestrates Secure Aggregation rounds to only have access to aggregations: it gathers masked contributions from all clients (step ①), homomorphically sums them (step ②) to form the item-degree vector $V$, normalized item-item matrix $\tilde{P}$ and the ideal low-pass filter $F_{IDL}$ via a distributed randomized power method, and then broadcasts these global filters back to every client (step ③) for local recommendation (step ④).

## 4.2 Threat model

We consider a **semi-honest threat model** [5, 6], in which both the server and users follow the protocol but may additionally attempt to infer private information. In this context, the server and a fraction of users $\gamma$ could collude by sharing any information (e.g. private keys or values) they hold to infer private data. Furthermore, a fraction of users $\delta$ could dropout. We want our system to be **confidential** under this threat model, that is, individual user contributions must not be exposed in the clear during the protocol and the aggregate must not leak sensitive information such as ratings.
<figure><img src="image_3.png" /><figcaption>Figure 1: Clients keep $R^{(u)}$ locally and send only masked data (①). The server orchestrate the protocol (and Secure Aggregation) to compute global filters $\tilde{P}$ and $F_{IDL}$ without access to confidential information (②), then broadcasts them (③) so that users can perform recommendation locally (④).</figcaption></figure>

## 4.3 PriviRec

PriviRec aims to compute the necessary components for recommendation securely in a distributed setting, where each user keeps their data locally. Our approach consists of two main steps, each using polylogarithmic communication and computation cost Secure Aggregation [5] to aggregate data from all users without revealing individual contributions. First, we collaboratively compute the item degrees matrix. Then, we compute the item-item matrix and the ideal low-pass filter in a distributed manner. To compute the ideal low-pass filter, we propose a distributed version of the Randomized Power Iteration algorithm, which approximates the leading singular vectors needed for this filter without centralizing any data. As opposed to centralized methods [11, 47], our computation of the ideal low-pass filter does not require the use of a Singular Value Decomposition, therefore reducing computational cost. We elaborate on the different steps of the algorithm in following sections.

**4.3.1 Distributed item degrees vector computation:** We denote the one-filled column vector of dimension $d$ as $1_d$. Recall that $R^{(u)}$ as the $u$th row of $R$, i.e., the part of $R$ locally held by user $u$.

In a distributed and confidential setting, each user $u$ usually only has access to its own interactions $R^{(u)}$. However, it is possible to confidentially compute the sums of distributed values among users using Secure Aggregation with low communication and computation overhead (see Subsection 6.1 for more details). By the following, we can compute $V$ (defined in Eq. (3.1.3)) without revealing each individual component $R^{(u)}$:

$$V = \text{Diag}(1_{|\mathcal{U}|}^{\top} \cdot R) = \text{Diag}(\text{SecAgg}(R^{(u)}, \mathcal{U})). \quad (4)$$

**4.3.2 Distributed item-item gram matrix computation:**

**Theorem 4.1.** We can compute $\tilde{P}$ (Eq. (2)) in a distributed and secure setting as $\tilde{P} = V^{-\frac{1}{2}}(\text{SecAgg}(\frac{1}{d_{user}(u)}R^{(u)\top}R^{(u)}, \mathcal{U}))V^{-\frac{1}{2}}$.

**PROOF.** The item-item normalized adjacency matrix is defined as $\tilde{P} = \tilde{R}^{\top}\tilde{R} = V^{-\frac{1}{2}}(U^{-\frac{1}{2}}R)^{\top}(U^{-\frac{1}{2}}R)V^{-\frac{1}{2}}$. We then define $P' = (U^{-\frac{1}{2}}R)^{\top}(U^{-\frac{1}{2}}R)$ and $P'_{ij}$ as the element of $P'$ at line i and column j and $d_{user}(u) = \sum_{i=0}^{|I|-1} r_{ui}$. This leads to the following expression for the (i, j)-th element of $P'$: $P'_{ij} = \sum_{u=0}^{N-1} \frac{1}{d_{user}(u)} \cdot r_{ui} \cdot r_{uj}$.

We can deduce that $P' = \sum_u \frac{1}{d_{user}(u)} R^{(u)\top}R^{(u)}$ and compute $\tilde{P}$ in a distributed and privacy-preserving setting:

$$\begin{aligned} \tilde{P} &= V^{-\frac{1}{2}} \left( \sum_u \frac{1}{d_{user}(u)} R^{(u)\top} R^{(u)} \right) V^{-\frac{1}{2}} \\ &= V^{-\frac{1}{2}} \left( \text{SecAgg} \left( \frac{1}{d_{user}(u)} R^{(u)\top} R^{(u)}, \mathcal{U} \right) \right) V^{-\frac{1}{2}}. \end{aligned} \quad \square$$

**4.3.3 Distributed Ideal Low Pass Filter computation:** He et al. [20] simplified the GCN architecture while improving recommendation performance. Shen et al. [47] then showed that the propagation of untrained GCN embeddings through its layers is akin to low-pass filtering, and proposed using the Ideal Low Pass Filter $F_{IDL}$ computed using the singular vectors $S_k$ of the normalized interaction matrix (Eq. (4.2)) instead of having to explicitly train a GCN. In the centralized recommender system literature [11, 47], these vectors are approximated using a centralized version of the randomized power method followed by a truncated Singular Value Decomposition (Algorithm 4.4 in Halko et al. [16]).

With Theorem 4.2 below, we simplify computation further by showing that the truncated SVD step can be avoided and that we can compute the Ideal Low Pass Filter using a secure decentralized randomized power method. Our proposed version of the power method has similarities to Algorithm 1 of Philippenko [43], although it is less susceptible to numerical instabilities (see Remark 4.3 in Halko et al. [16]) and uses QR decompositions to output an approximation of the leading eigenvectors and not of their range. Differentially private variants of this procedure for positive semi-definite matrices have also been explored [3, 18, 41], at steep utility costs.

**Algorithm 1: Distributed secure power method**

**Input:** distributed matrices $\{A^{(u)}|u \in \mathcal{U}\}$, iteration number $L$, target rank $k$, iteration rank $p \ge k$.

**Output:** approximated eigen-space $X_L \in \mathbb{R}^{m \times p}$, with orthonormal columns, upper triangular matrix $T_L$.

**Initialization:** orthonormal $X_0 \in \mathbb{R}^{m \times p}$ by QR decomposition on a random Gaussian matrix $G_0$; The central node broadcasts $X_0$ to all $n$ computing nodes;

Computing node $u$ computes $Y_0^{(u)} = A^{(u)\top} X_0$;

The central node computes with the clients

$Y_0 = \text{SecAgg}(Y_0^{(u)}, \mathcal{U})$.

The central node computes QR factorization $Y_0 = X_0 T_0$;

**for** $l = 1$ to $L-1$ **do**

1. The central node broadcasts $X_{l-1}$ to all clients;

2. Computing node $u$ computes $Y_l^{(u)} = A^{(u)\top} A^{(u)} X_{l-1}$;

3. The central node computes with the clients

$Y_l = \text{SecAgg}(Y_l^{(u)}, \mathcal{U})$;

4. The central node computes QR factorization $Y_l = X_l T_l$; **end for**

**Theorem 4.2.** Using Algorithm 1, we can collaboratively compute the ideal low-pass filter $F_{IDL}$. We provide the proof in Appendix A.
## 4.4 PriviRec-k

We now propose a variant that employs low-rank decomposition to reduce the communication cost of PriviRec. This version is also distributed and privacy-preserving but allows one to find a trade-off between communication cost and recommendation utility. PriviRec-k has 3 main steps, which we detail in the following sections:

(1) Distributed computation of the item degrees matrix (using polylogarithmic-cost Secure Aggregation [5]), as in PriviRec.

(2) Distributed computation of the top-k singular vectors and values of $\tilde{P}$ (using Secure Aggregation and a distributed version of Randomized Power Iteration [16, 43]).

(3) Computation of the ideal low-pass filter and the approximated item-item matrix using the resulting top-k singular vectors.

### 4.4.1 Communication efficient item-item matrix computation:
As introduced in Section 4.3.2, the normalized item-item matrix is defined as $\tilde{P} = \tilde{R}^T \tilde{R} = \sum_u \tilde{R}_u^T \tilde{R}_u$. Aggregating $\tilde{R}_u^T \tilde{R}_u \in \mathbb{R}^{|I| \times |I|}$, $\forall u \in \mathcal{U}$ can be communication-intensive. To reduce this cost, we develop Approximation 4.3, whose derivation is in Appendix D.

**Approximation 4.3.** We can approximate $\tilde{P} = S_k \text{Diag}(T_{L-1}) S_k^T$, where $S_k$ and $T_{L-1}$ are the outputs of the Distributed Secure Power method executed on the distributed $R^{(u)}$.

Thus, we only need to communicate $S_k \in \mathbb{R}^{|I| \times k}$ and the diagonal $\text{Diag}(T_{L-1})$ using this decomposition. The communication savings arises because $\text{Diag}(T_{L-1}) \in \mathbb{R}^k$ as opposed to $\tilde{P} \in \mathbb{R}^{|I| \times |I|}$. The matrix $S_k$ already needs to be broadcasted to compute the Ideal Low Pass Filter. We show in Section 5.4 that it is possible to retain a competitive NDCG while having $k \ll |I|$. We also note that using low-rank projections has been shown to amplify privacy protection [7] compared to using exact matrix computation.

## 4.5 Security analysis

Before proving that neither PriviRec nor PriviRec-k exposes individual user ratings, we first show in Lemma 4.4 that the item-item matrix itself does not uniquely identify user's interactions. We provide the proof in Appendix B.

**Lemma 4.4 (Different sets of user profiles lead to the same item-item matrix).** Let $\tilde{P} = V^{-\frac{1}{2}} (\text{SecAgg}(\frac{1}{d_{user}(u)} R^{(u)\top} R^{(u)}, \mathcal{U})) V^{-\frac{1}{2}}$ be the normalized item-item matrix representing the similarity of items. A single item-item matrix $\tilde{P}$ can be constructed from multiple different datasets, each with a different set of user profiles.

Having established that $\tilde{P}$ alone cannot leak any individual profile, we can now prove that the entire PriviRec protocol preserves confidentiality under our semi-honest threat model:

**Lemma 4.5.** PriviRec and PriviRec-k are confidential under the semi-honest threat model, i.e., individual user contributions ($R^{(u)}$) are not exposed in the clear during the protocol, and the aggregate does not leak sensitive information.

**PROOF OF LEMMA 4.5.** We build on the Secure Aggregation protocol, a well-established technique in Multi-Party Computation which guarantees that individual contributions from users ($R^{(u)}$) are never revealed; only the aggregate result (e.g., $\sum_{u \in \mathcal{U}} R^{(u)}$) is accessible. This is achieved through masking techniques and secret sharing [5].

It is resistant to user dropout and to collusions between the server and users. We now describe why the computations of the components of PriviRec and PriviRec-k are confidential:

**Item Degrees Computation.** The computation of the item degrees matrix $V' = \text{SecAgg}(\{R^{(u)}\})$ relies on Secure Aggregation, which ensures that individual contributions are masked, and only the aggregate is revealed. This step does not expose any user-specific data and is not sensitive because the aggregated item degrees vector only informs about the popularity of items.

**Item-Item Matrix Computation.** The computation of $\tilde{P}$ in Equation (4.1) also leverages Secure Aggregation. As in the previous step, individual user contributions remain confidential, and only the aggregated result is used. This matrix represents similarities between items but does not give information about individual user profiles, as we show in Lemma 4.4.

**Ideal Low-Pass Filter Computation.** The decentralized power method involves iterative computations using intermediate results aggregated through Secure Aggregation: $Y_l = \text{SecAgg}(\{Y_l^{(u)}\})$. These intermediate results are aggregated across users and do not reveal individual contributions. Furthermore, the final outputs ($S_k$, $F_{IDL}$) only depend on aggregated data and randomized computations. $S_k$ is a projector for rank $k$ approximations of the item-item matrix computation, which contains strictly less information than $\tilde{P}$. □

# 5 Experiments

In this section, we evaluate the impact of computing the filters of State of the Art methods GF-CF, BSPM, and Turbo-CF using our decentralized protocols. We also assess the impact of the number of factors $k$ on the recommendation performance of GF-CF when using PriviRec-k. These three methods were selected because they have demonstrated strong recommendation performance, scalability, and inference efficiency in prior work [11, 42, 47].

## 5.1 Datasets

<table><caption>Table 1: Statistics of datasets</caption><thead><tr><td>Dataset</td><td>Users</td><td>Items</td><td>Interactions</td><td>Density (%)</td></tr></thead><tbody><tr><td>Gowalla</td><td>29,858</td><td>40,981</td><td>1,027,370</td><td>0.084</td></tr><tr><td>Yelp2018</td><td>31,668</td><td>38,048</td><td>1,561,406</td><td>0.130</td></tr><tr><td>Amazon-Book</td><td>52,643</td><td>91,599</td><td>2,984,108</td><td>0.062</td></tr></tbody></table>

To compare fairly with the existing literature, we benchmark our approaches on the widely adopted (e.g. [11, 14, 20, 42, 47]) Gowalla [10], Yelp2018 [20] and Amazon-Book [50] datasets, using their standard train/test splits [20]. We show dataset statistics in Table 1.

## 5.2 Metrics

We use Recall@20 and NDCG@20 to measure the quality of top-k item ranking, two widely-employed metrics [11, 20, 27, 47].

**Recall@20** measures the proportion of relevant items successfully retrieved among the top 20 recommendations, which makes it particularly suitable for tasks where completeness is critical.

**NDCG@20** (Normalized Discounted Cumulative Gain) is used to evaluate the quality of ranking by assigning higher scores to
relevant items appearing earlier in the recommended list. This metric provides an assessment of both relevance and ranking order.

## 5.3 Experimental setup

The federated approaches (respectively FedMF/FMFSS, FedPerGNN, FedGCN, HN3S and PerFedRec++) are federated adaptations from their centralized counterparts (respectively MF-BPR, GAT, NGCF, Mult-VAE and PinSage) and were originally benchmarked on small and heterogeneous datasets, frequently with dataset-dependent hyperparameter tuning and evaluation metrics differing from those widely adopted in centralized recommender system research. Due to these discrepancies, reproducing and directly comparing results is challenging. By noting that the performance of centralized methods provides an upper bound for decentralized methods (as similarly observed in the federated papers [8, 26, 35, 51, 56]), we associate each federated method with its centralized counterpart, enabling a fair comparison and clear baseline against **PriviRec** with widely used metrics and datasets in Table 2.

Specifically, we compute the NDCG@20 on Gowalla, Yelp2018 and Amazon-Book to get the performance of BSPM-LM, BSPM-EM, GF-CF and Turbo-CF when using decentralized components computed with **PriviRec**. We use the same hyperparameter values as centralized version (which we show to be theoretically equivalent). We run the experiments with 10 different random seeds and report means and 95% confidence interval for the metrics.

We also study the impact of the number of factors *k* on recommendation performance of GF-CF when using **PriviRec-k**. We vary *k* between 256 and 3584 in increments of 256, set *L* = 2 and report our results in Figure 2. We run the experiments with 10 random seeds and report metrics means and 95% confidence intervals.

## 5.4 Results

*Comparison with existing decentralized approaches.* Table 2 compares the NDCG@20 of our proposed **PriviRec** with centralized versions of existing federated recommender systems on widely used datasets. These centralized versions are upper bounds on the actual performances of the federated recommender systems and allow us to compare fairly with existing literature. By adapting GF-CF, Turbo-CF, BSPM-LM and BSPM-EM to a confidential and decentralized framework with **PriviRec**, we attain better performance in the decentralized setting than those centralized upper bounds and we therefore bridge the gap between centralized recommender systems and their decentralized and confidential counterparts.

We recall that the protocol used by our closest competitor (PerFedRec++) is susceptible to collusion attacks, where the server and one of the clients collude, allowing the server to decipher every user interaction history, while our protocol is robust against such collusions. It also leaks additional information through users embeddings during the pre-training phase and at each training epoch.

*Impact of the number of factors k.* We illustrate the importance of the number of factors *k* by plotting recommendation performance of GF-CF when using **PriviRec-k** on Gowalla in Figure 2 and on Yelp2018 in Figure 2. For Gowalla, we can see that **PriviRec-k** offers competitive NDCGs compared to the regular **PriviRec** for *k* in the range [2048, 3584]. In fact, we can see that **PriviRec-k** with an approximate Item-Item matrix offers superior performance to **PriviRec**

(with an exact Item-Item matrix) on this dataset. We can note that Park et al. [42] also obtain superior performance on Gowalla with Turbo-CF compared to GF-CF although they use approximate filters. We hypothesize that using in some cases, approximations of the Item-Item matrix can filter noisy components, resulting in superior performance. **PriviRec-k** also offers competitive NDCG and Recall

<figure><img src="image_4.png" /><figcaption>**Figure 2:** Performance comparison between **PriviRec** and **PriviRec-k** as a function of *k* ranging between 256 and 3584 in increments of 256. Top shows NDCG and Recall on Gowalla; bottom shows those metrics on Yelp2018. Lines show mean over 10 seeds; shaded bands are 95% confidence intervals.</figcaption></figure>

(although slightly inferior to **PriviRec**) on Yelp2018 when *k* ranges between 2816 and 3584. To determine an appropriate value of *k* for a particular system, one approach is to optimize over a validation set by running **PriviRec-k** for different values of *k* to achieve the desired performance while minimizing communication costs.

## 6 Cost analysis

In this section, we discuss the **communication overhead** introduced by the different decentralized methods and the **computational complexity** of the proposed protocols compared with gradient-based federated baselines. We use symbols listed in Table 3.

<table><caption>**Table 3:** Symbols used in the cost analysis.</caption><tr><td>n</td><td>number of participating users (clients)</td></tr><tr><td>|I|</td><td>number of items in the catalogue</td></tr><tr><td>L</td><td>power-iteration steps in PRIVIREC/PRIVIREC-k</td></tr><tr><td>e</td><td>training epochs of gradient-based Federated baselines</td></tr><tr><td>k<sub>1</sub></td><td>rank used for the Ideal Low Pass Filter</td></tr><tr><td>k<sub>2</sub></td><td>approximation rank used in the low-rank variant PRIVIREC-k</td></tr><tr><td>k<sub>3</sub></td><td>embedding dimension in Federated GCN/ MF baselines</td></tr></table>

### 6.1 Communication cost

Table 4 presents the communication cost introduced by **PriviRec**, **PriviRec-k**, and federated learning based algorithms using Secure Aggregation. We provide the calculations details in Appendix C.
<table><caption>**Table 2:** Comparison of Recall@20 and NDCG@20 of decentralized PriviRec variants of centralized methods against baselines on Gowalla, Yelp2018 and Amazon-Book. The top block shows the best-case (centralized) performance of corresponding decentralized protocols displayed in the second column of the table (results from [11]); the bottom block shows the performance of PriviRec with decentralized filter computations (mean ± 95 % CI). Best result are bold and second best are underlined.</caption><thead><tr><th rowspan="2">Centr.</th><th rowspan="2">Decentr.</th><th colspan="2">Gowalla</th><th colspan="2">Yelp2018</th><th colspan="2">Amazon-Book</th></tr><tr><th>Recall</th><th>NDCG</th><th>Recall</th><th>NDCG</th><th>Recall</th><th>NDCG</th></tr></thead><tbody><tr><td>MF-BPR</td><td>FedMF/FMFSS</td><td>0.1291</td><td>0.1109</td><td>0.0433</td><td>0.0354</td><td>0.0250</td><td>0.0196</td></tr><tr><td>GAT</td><td>FedPerGNN</td><td>0.1401</td><td>0.1236</td><td>0.0543</td><td>0.0431</td><td>0.0326</td><td>0.0235</td></tr><tr><td>NGCF</td><td>FedNCF</td><td>0.1570</td><td>0.1327</td><td>0.0579</td><td>0.0477</td><td>0.0344</td><td>0.0263</td></tr><tr><td>Mult-VAE</td><td>HN3S</td><td>0.1641</td><td>0.1335</td><td>0.0584</td><td>0.0450</td><td>0.0407</td><td>0.0315</td></tr><tr><td>LightGCN</td><td>PerFedRec++</td><td>0.1830</td><td>0.1554</td><td>0.0649</td><td>0.0530</td><td>0.0411</td><td>0.0315</td></tr><tr><td>GF-CF</td><td rowspan="4">PriviRec</td><td>0.1853<sup>±2e-4</sup></td><td>0.1522<sup>±1e-4</sup></td><td>0.0661<sup>±1e-4</sup></td><td>0.0541<sup>±1e-4</sup></td><td><strong>0.0710<sup>±1e-4</sup></strong></td><td>0.0584<sup>±1e-4</sup></td></tr><tr><td>Turbo-CF</td><td>0.1835<sup>±1e-4</sup></td><td>0.1531<sup>±1e-4</sup></td><td>0.0693<sup>±1e-4</sup></td><td>0.0574<sup>±1e-4</sup></td><td><strong>0.0730<sup>±1e-4</sup></strong></td><td><strong>0.0611<sup>±1e-4</sup></strong></td></tr><tr><td>BSPM-LM</td><td><u>0.1906<sup>±1e-4</sup></u></td><td><u>0.1578<sup>±1e-4</sup></u></td><td><u>0.0702<sup>±1e-4</sup></u></td><td><u>0.0576<sup>±1e-4</sup></u></td><td>0.0610<sup>±1e-4</sup></td><td><u>0.0610<sup>±1e-4</sup></u></td></tr><tr><td>BSPM-EM</td><td><strong>0.1916<sup>±1e-4</sup></strong></td><td><strong>0.1595<sup>±1e-4</sup></strong></td><td><strong>0.0716<sup>±1e-4</sup></strong></td><td><strong>0.0589<sup>±1e-4</sup></strong></td><td>0.0609<sup>±1e-4</sup></td><td>0.0609<sup>±1e-4</sup></td></tr></tbody></table>

<table><caption>**Table 4:** Communication costs of federated GCNs (F. GCNs), matrix factorization (MFs) based recommender systems, PriviRec and PriviRec-k using Secure Aggregation.</caption><thead><tr><th></th><th>Client</th><th>Server</th></tr></thead><tbody><tr><td>F. GCNs/MFs</td><td>e log(n) + ek<sub>3</sub>(|I| + n)</td><td>en log(n) + ek<sub>3</sub>n(|I| + n)</td></tr><tr><td>PriviRec</td><td>L log(n) + |I|^2</td><td>Ln log(n) + n|I|^2</td></tr><tr><td>PriviRec-k</td><td>L log(n) + Lk<sub>2</sub> · |I|</td><td>Ln log(n) + Lk<sub>2</sub>n|I|</td></tr></tbody></table>

*Comparison between methods using Secure Aggregation.* Although we provide complexity expressions, the mapping to the actual number of floats transmitted for each algorithm is approximately the same as only the cluster size used in Secure Aggregation is approximated (and negligible compared to the matrices sizes).

For the Gowalla dataset, we use $L = 3$ for PriviRec and PriviRec-k and use $e = 1000$ for the Federated GCN methods (without Paillier encryption, Secret Sharing nor homomorphic encryption as baseline) as advised by He et al. [20]. For this dataset, we use $k_1 = 256$ [47], $k_2 = 2000$ (from our ablation study) and $k_3 = 64$ [20]. Using the communication overheads complexities from Table 4 with these values and the statistics of the Gowalla dataset yields terms for client costs of 1,679M floats for PriviRec, 246M floats for PriviRec-k and 4,534M floats for the Federated GCNs. This indicates that PriviRec and PriviRec-k not only preserve confidentiality but also offer significant communication advantages over traditional decentralized methods using Secure Aggregation. PriviRec and PriviRec-k also have a logarithmic dependence on the number of users $n$ as opposed to linear for federated GCNs and matrix factorization.

*Advantage of PriviRec-k.* As shown in Table 4, the communication overhead for both clients and the server is significantly lower when using PriviRec-k compared to PriviRec, because $L \cdot k_2 \ll |I|$. Moreover, computing the filters using PriviRec-k requires less total communication than regular decentralized gradient descent methods used in GCNs or matrix factorization and in particular much less communication bursts (which introduce latency). Indeed, the only iterative process in PriviRec-k is the decentralized randomized power iteration, which is more communication-efficient than gradient descent for computing matrix factorizations. Typically, PriviRec-k requires a small number of iterations (e.g., $L$ in the order of 2 to 5), whereas gradient descent methods may require a much larger number of iterations (e.g., $e = 1000$ [20]).

*Communication costs of other secure methods.* Most existing decentralized recommendation approaches rely on cryptographic primitives to ensure security, incurring additional communication costs for the users in addition to the cost of federated recommender systems compared to graph-filter based. FedMF, for instance, uses Paillier homomorphic encryption, requiring each floating-point number to be communicated using ≈ 4096 bits [13]. In contrast, Secure Aggregation protocols typically use only 32 or 64 bits [6].

Both HN3S and FMFSS adopt ad-hoc secret-sharing mechanisms, splitting embeddings into $p$ shares and communicating them with $p$ different users. While these works do not explicitly detail how this parameter is selected for guaranteed security, their designs resemble Secure Aggregation using Shamir's Secret Sharing. Therefore, we expect similar communication costs to federated systems using Secure Aggregation for similar security guarantees.

FedNCF leverages an earlier Secure Aggregation protocol proposed by Bonawitz et al. [6], which scales linearly with the number of users. Similarly to our protocol, it could benefit from adopting polylogarithmic Secure Aggregation [5] to reduce communication.

In both FedPerGNN and PerFedRec++, users need to send user and item embeddings after each federated training round. The dominant cost lies in the user-item graph expansion, which requires communications of high-order (typically $L \approx 3$) user-item interaction graphs at each training epoch along with updated user and item embeddings, for $e$ epochs. In contrast, our approach requires the communication of item embeddings for $L$ iterations (with logarithmic cost due to SecAgg) and of the item-item matrix for PriviRec.

## 6.2 Computational cost

*Cost of optimization.* The main competitors of our method are Graph Convolutional Networks and Matrix Factorization approaches. We will compare the computational complexity of our approach with LightGCN [20], a popular GCN designed to minimize computational costs, and with widely used FedMF [8].

LightGCN shares similarities with the power method: it propagates embeddings by multiplying the embedding matrix with the adjacency matrix over $L$ layers. After propagation, LightGCN and classical MF methods rely on gradient-based optimization performed locally on each client. Specifically, each client optimizes $k_3 \times (n+|I|)$ parameters for $e$ epochs. For LightGCN, each epoch includes both
forward and backward passes through *L* layers, resulting in a per-epoch complexity of approximately $O(Ln|\mathcal{I}|k_3)$ [47], thus yielding a total client-side optimization complexity of $O(eLn|\mathcal{I}|k_3)$. The MF approach has a total complexity of $O(en|\mathcal{I}|k_3)$ due to direct interactions between user and item embeddings. In contrast, our decentralized power method replaces repeated client-side gradient optimization with server-side QR decompositions, each of complexity $O(k_2|\mathcal{I}|^2)$, performed *L* times, resulting in a total cost of $O(Lk_2|\mathcal{I}|^2)$. We therefore shift the computational overhead from repeated client-side optimization to a centralized, one-time server computation. For further comparisons on the computational efficiency of graph-based collaborative filtering (e.g. GF-CF, BSPM) to GNN-based methods, we refer to [11, 47].

**Computational cost of Secure Aggregation.** Our approach incorporates Secure Aggregation to preserve user privacy, which introduce an additional complexity of $O(L(\log^2 n + k_2|\mathcal{I}|\log n))$ per client compared to centralized versions, with corresponding server complexity of $O(Ln(\log^2 n + k_2|\mathcal{I}|\log n))$.

**Computational costs of other secure methods.** We also note that most other decentralized protocols use cryptographic primitives to offer privacy guarantees, which will also incur additional computational costs. Indeed, FedMF, PerFedRec++ and FedPerGNN rely on Paillier encryption, while H3NS as well as FMFSS are based on Secret Sharing and FedNCF uses Secure Multi-Party Computation [5] to protect user tastes. In FedMF, the Paillier scheme is used to encrypt the gradients at user level, and the gradients are aggregated homomorphically at server level. PerFedRec++ and FedPerGNN use the scheme to encrypt the IDs of the items associated to each user and perform an anonymous user embeddings-item embeddings graph expansion at the server level. Overall, the aggregation protocol based on the Paillier scheme can be computationally costly [6, 8, 13], which motivated the use of Secure Aggregation [6].

FedNCF uses the linear cost Secure Aggregation protocol introduced by Bonawitz et al. [6]. In contrast, the Secret Sharing schemes used by HN3S and FMFSS are similar to polylogarithmic Secure Aggregation [5] and we can expect similar polylogarithmic costs for the same security guarantees in the process of aggregation.

# 7 Related work

**Federated Matrix Factorization and Collaborative Filtering.** Early efforts in decentralized recommendation focused on extending matrix factorization (MF) methods. For example, FedMF [8] adapts classic MF [31] to a decentralized scenario by employing Paillier homomorphic encryption to protect sensitive information in the training process. This decentralized approach achieves a direct equivalence to its centralized counterpart. However, their protocol requires a shared secret key between users, which hinders security in the case of one single user colliding with the server. Zheng et al. [58] replace Paillier homomorphic encryption with a protocol inspired by the cryptographic principles of secret sharing, reducing the risk of collusion while still maintaining the core principles of MF-based collaborative filtering for their Federated Matrix Factorization Recommendation Based on Secret Sharing for Privacy Preserving (FMFSS) approach. The security of this secret sharing protocol is however not studied in the security literature. Compared

to these approaches, PriviRec removes the need for shared secrets by relying instead on Secure Aggregation protocols with formally established confidentiality guarantees. It also goes beyond matrix factorization by enabling scalable computation of graph-based filters used in state-of-the-art models.

**Federated Neural Collaborative Filtering.** Recent work has extended neural architectures for recommendations into the federated learning paradigm. In particular, Federated Neural Collaborative Filtering (FedNCF). [26] is an extension of the Neural Matrix Factorization (NeuMF a.k.a. Neural Collaborative Filtering or NCF) [34] framework to a decentralized environment which uses early versions of Secure Aggregation [6]. By securely aggregating model updates while hiding individual contributions (gradients) during training, Jiang et al. [26] claim to guarantee *k*-anonymity. Unlike FedNCF, PriviRec does not rely on training large neural models and avoids the costly gradient aggregation process altogether. Instead, it focuses on efficient decentralized computation of inference-time components (e.g., item-item matrices and filters), which is both computationally cheaper and simpler to secure.

**Federated Graph-Based methods.** Graph-based techniques have been increasingly adopted to capture higher-order user-item interactions in federated environments. For instance, FedPerGNN [51] and PerFedRec++ [35] extend widely used Graph Neural Networks GAT [49] and LightGCN [20] to the decentralized setting. FedPerGNN and PerFedRec++ use a privacy-preserving user-item graph expansion based on encryption to expand the user's local interactions. In both protocols, similarly to FedMF, the secret key protecting users interaction histories is shared among users but hidden from the server. Additionally, the server in PerFedRec++ has access to user embeddings during the pre-training, and to noisy versions at each training epoch. In contrast, PriviRec does not transmit user embeddings and remains robust against server-user collusions.

**Clustering Methods.** Distributed bandit algorithms seem to be promising alternatives for decentralized recommendation scenarios, due to low communication overhead and favorable user count scalability. For instance, Korda et al. [30] propose a distributed clustering approach for linear bandits in peer-to-peer networks operating in a fully decentralized fashion, whereas Mahadik et al. [37] introduce fast distributed bandit algorithms specifically designed for online recommendation systems, improving user scalability while optimizing recommendation performance in online settings. However, these methods overlook privacy guarantees and graph-based filters.

**Federated Autoencoder-Based Frameworks.** Another promising direction involves decentralizing autoencoder-based models. The HN3S framework [56], for example, extends Mult-VAE [32] and MacridVAE [36] to the federated setting. While these models expose inherent privacy risks, HN3S tries to mitigate these issues using a secret sharing protocol, with only modest performance degradation.

**Differential Privacy.** DP is a framework which allows for privacy guarantees against strong adversaries with potential side knowledge. DP is applied only sparingly in decentralized recommender systems, primarily because of the considerable performance drop it incurs [26]. With the SOTA methods claiming little performance
drop, only some components are protected using DP and the cumulative privacy loss over multiple iterations or epochs are not studied [35, 51]. Their end-to-end DP guarantees are then unclear.

# 8 Conclusion & Future Work

We introduce PriviRec and PriviRec-k, two fully decentralized and secure framework that use Secure Aggregation and a distributed power method to compute the normalized item-item matrix and ideal low-pass filters with no loss in accuracy. PriviRec-k provides an efficient trade-off between communication cost and recommendation using low-rank approximation. Future work will target even larger item catalogs (e.g. via tensor-train factorizations) and explore complementary formal Differential Privacy guarantees.

## A Security of the decentralized randomized power iteration, proof of Theorem 4.2.

**PROOF.** Algorithm 1 allows us to compute the equivalent of the following using Secure Aggregation: $Y = (\tilde{R}^T \tilde{R})^\alpha \tilde{R}^T \Omega = QT$.

Here, $Y \in \mathbb{R}^{|I| \times p}$ is in the range of $\tilde{R}^T \in \mathbb{R}^{|I| \times |U|}$ and $QT$ is a Gram-Schmidt QR decomposition of $Y$, i.e. $Q \in \mathbb{R}^{|I| \times p}$ is an orthonormal matrix and $T \in \mathbb{R}^{p \times p}$ is an upper triangular matrix. Moreover, let $\alpha \in \mathbb{Z}^+$ and $\Omega \in \mathcal{N}(0, 1)^{|I| \times p}$.

According to [16], we can then compute a rank $K$ approximation of $\tilde{R}^T$ sharing its top-$K$ singular vectors: $\tilde{R}_K^T = QQ^T \tilde{R}^T$.

We also define $B = Q^T \tilde{R}^T$. If we define the SVD of $B$ as $B = Z\Sigma M^T$, then we can deduce the SVD of $\tilde{R}_K^T$ indirectly as $\tilde{R}_K^T = QZ\Sigma M^T$. We therefore have $\tilde{R}_K = M\Sigma^T Z^T Q^T = M\Sigma^T S^T$.

We recognize $S = QZ$ as the right singular vectors of $\tilde{R}_K$, therefore as the top-$K$ right singular vectors of $\tilde{R}$. We are only interested in the $SS^T$ product, we do not need $S$ itself. We notice that:

$$SS^T = QZZ^T Q^T = QIQ^T(Z \text{ orthonormal by def.}) = QQ^T. \quad (5)$$

It is therefore sufficient to apply the distributed version of the Randomized Power Iteration algorithm on $\tilde{R}$ and to compute a QR decomposition to be able to compute $F_{IDL}$ (V was computed in Sec. 4.3.2) and we do not need to compute the full SVD of $\tilde{R}$. □

## B Proof of Lemma 4.4

**PROOF.** Let $R' \in \mathbb{R}^{|U| \times |I|}$ be any normalized user-item interaction matrix. Form its item-item matrix $P' = (R')^T R' \in \mathbb{R}^{|I| \times |I|}$.

Now let $Q \in \mathbb{R}^{|U| \times |U|}$ be any orthonormal matrix satisfying $Q^T Q = I^T I$. Define a new user-item matrix $R'' = Q^T R'$.

$$(R'')^T R'' = (R')^T Q^T Q R' = (R')^T R' = P.$$

Since the orthogonal group $O(|U|)$ is infinite for $|U| > 1$, there are many distinct choices of $Q$, each yielding a different $R''$ (in particular permutations) but the same $P'$. Hence multiple different user-profile collections produce the same item-item matrix. We note that permutations also preserve the item degrees matrix. □

## C Communication overhead calculations

We analyze the communication overhead introduced by the different methods by breaking down the different communications costs in Table 4, for PriviRec, the federated GCN or matrix factorization.

For the PriviRec method, Secure Aggregation is performed on the item degrees vector (size $|I|$), the item-item matrix (size

$|I| \times |I|$), and on intermediate results from the randomized power iteration algorithm (each of size $|I| \times k_1$, where $k_1$ is the number of singular vectors), over $L$ iterations (typically $L = 2-5$).

For the PriviRec-k variant, Secure Aggregation is used to compute the item degrees vector (of size $|I|$), on intermediate results from the randomized power iteration over $L$ iterations and on the approximated singular values and vectors of the item-item matrix. The matrices exchanged are of sizes $|I| \times k_2$, where $k_2$ is the number of singular vectors used to compute both the low-rank approximation of the item-item matrix and the Ideal Low Pass Filter. For the Gowalla and Yelp2018 datasets, $k_2$ can be set in the order of 2000 to have NDCG values competitive with PriviRec, while for those datasets $|I|$ is fixed to 40, 981 and 38, 048 respectively.

In contrast, federated versions of graph convolutional networks (GCNs) or gradient-descent-based matrix factorization methods require more communication rounds because they train over $e$ epochs (typically $e = 1000$). They need to communicate user and item embeddings of dimension $k_3$ in each epoch, resulting in a total communication size of $(|I| + n) \times k_3 \times e$.

For one iteration of Secure Aggregation, the communication complexity for each client is $O(\log(n) + l)$ (Bell et al. [5, Sec. 3.4]), where $n$ is the number of clients and $l$ is the length of the message being communicated. In this protocol, each client communicates with $k = O(\log(n))$ other clients (the exact value of $k$ depends on the communication graph, $\gamma$ and $\delta$, see [5, Sec. 5.1]) to exchange the necessary information for mask generation and aggregation.

On the server side, the communication complexity is $O(n(\log n + l))$, as the server interacts with $n$ clients to aggregate the inputs and coordinate the secure computation process. By incorporating the number of iterations of Secure Aggregation required for the protocol and the sizes of the matrices involved, we derive the communication complexities presented in Table 4.

## D Derivation of Approximation 4.3

**DERIVATION.** Using the decentralized power method, clients collaborate to compute $S_k$, an approximation of the top-$k$ right singular vectors of $\tilde{R}$. This yields the approximation $\tilde{R}_k^T \approx S_k \Sigma_k Z_k^T$, where $\Sigma_k$ is rectangular diagonal, $S_k$ contains the top-$k$ right singular vectors and $Z_k$ contains the top-$k$ left singular vectors of $\tilde{R}_k$.

We use the low rank approximation $\tilde{P} \approx \tilde{R}_k^T \tilde{R}_k = S_k \Lambda_k S_k^T$, where $\Lambda_k \in \mathbb{R}^{k \times k}$ is a diagonal matrix.

At steps 2 and 3 of iteration $L-1$ of Algorithm 1, we compute $Y_{L-1} = A^T A X_{L-2}$. By injecting $A = \tilde{R}^T$ and using the approximation $X_{L-2} \approx S_k$, we obtain $Y_{L-1} = A^T A X_{L-2} \approx \tilde{P} S_k \approx S_k \Lambda_k$.

Then at step 4, the central node computes the QR factorization $Y_{L-1} = X_{L-1} T_{L-1}$, and we have approximately $X_{L-1} \approx S_k$. Therefore by left multiplication $\Lambda_k \approx T_{L-1}$ and since $\Lambda_k$ should be diagonal, $\Lambda_k = \text{Diag}(\Lambda_k) \approx \text{Diag}(T_{L-1})$. □

## Acknowledgments

This work was supported by the French government managed by the Agence Nationale de la Recherche (ANR) through France 2030 program with the reference ANR-23-PEIA-005 (REDEEM project). We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) [funding reference number 260250], and by the Fonds de recherche du Québec (FRQ).
# E GenAI Usage Disclosure

Generative AI was not used in the completion of this work.

## References

[1] R. Agrawal and R. Srikant. 2000. Privacy-preserving data mining. In Proc. ACM SIGMOD Int. Conf. Fund. Privacy Data. 439–450.

[2] Y. Allouah, A. Koloskova, A. E. Firdoussi, M. Jaggi, and R. Guerraoui. 2024. The privacy power of correlated noise in decentralized learning. arXiv:2405.01031 (2024).

[3] M.-F. Balcan, S. S. Du, Y. Wang, and A. W. Yu. 2016. An improved gap-dependency analysis of the noisy power method. In Proc. Conf. Learn. Theory. PMLR, 284–309.

[4] Y. Belal, A. Bellet, S. B. Mokhtar, and V. Nitu. 2022. Pepper: Empowering user-centric recommender systems over gossip learning. In Proc. ACM Interact. Mobile Wearable Ubiquitous Technol. 6, 3 (2022), 1–27.

[5] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova. 2020. Secure single-server aggregation with (poly) logarithmic overhead. In Proc. 2020 ACM SIGSAC CCS. 1253–1269.

[6] K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. 2017. Practical secure aggregation for privacy-preserving machine learning. In Proc. 2017 ACM SIGSAC CCS. 1175–1191.

[7] J. Burkhardt, H. Keller, C. Orlandi, and C. Schwiegelshohn. 2024. Distributed differentially private data analytics via secure sketching. arXiv:2412.00497 (2024).

[8] D. Chai, L. Wang, K. Chen, and Q. Yang. 2020. Secure federated matrix factorization. IEEE Intell. Syst. 36, 5 (2020), 11–20.

[9] L. Chen, L. Wu, R. Hong, K. Zhang, and M. Wang. 2020. Revisiting graph-based collaborative filtering: A linear residual graph convolutional network approach. In Proc. AAAI.

[10] E. Cho, S. A. Myers, and J. Leskovec. 2011. Friendship and mobility: User movement in location-based social networks. In Proc. 17th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining. 1082–1090.

[11] J. Choi, S. Hong, N. Park, and S.-B. Cho. 2023. Blurring-sharpening process models for collaborative filtering. In Proc. 46th Int. ACM SIGIR. 1096–1106.

[12] J. Choi, J. Jeon, and N. Park. 2021. LT-OCF: Learnable-Time ODE-based collaborative filtering. In Proc. CIKM.

[13] T. V. T. Doan, M.-L. Messai, G. Gavin, and J. Darmont. 2023. A survey on implementations of homomorphic encryption schemes. J. Supercomput. 79, 13 (2023), 15098–15139.

[14] W. Fan, X. Liu, W. Jin, X. Zhao, J. Tang, and Q. Li. 2022. Graph trend filtering networks for recommendation. In Proc. SIGIR. 112–121.

[15] F. González, Y. Yu, A. Figueroa, C. López, and C. Aragon. 2019. Global reactions to the Cambridge Analytica scandal: A cross-language social media study. In Companion Proc. WWW '19. 799–806.

[16] N. Halko, P.-G. Martinsson, and J. A. Tropp. 2011. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 2 (2011), 217–288.

[17] P. Han, B. Xie, F. Yang, and R. Shen. 2004. A scalable P2P recommender system based on distributed collaborative filtering. Expert Syst. Appl. 27, 2 (2004), 203–210.

[18] M. Hardt and E. Price. 2014. The noisy power method: A meta algorithm with applications. Adv Neural Inf. Process. Syst. 27 (2014), 2861–2869.

[19] C. He, K. Balasubramanian, E. Ceyani, C. Yang, H. Xie, L. Sun, L. He, L. Yang, P. S. Yu, Y. Rong, and et al. 2021. FedGraphNN: A federated learning system and benchmark for graph neural networks. arXiv:2104.07145 (2021).

[20] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang. 2020. LightGCN: Simplifying and powering graph convolution network for recommendation. In Proc. 43rd Int. ACM SIGIR Conf. Res. Dev. Inf. Retrieval. 639–648.

[21] X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T.-S. Chua. 2017. Neural collaborative filtering. In Proc. 26th Int. Conf. World Wide Web. 173–182.

[22] I. Hegedüs, G. Danner, and M. Jelasity. 2021. Decentralized learning works: An empirical comparison of gossip learning and federated learning. J. Parallel Distrib. Comput. 148 (2021), 109–124.

[23] J. Hu, S. Qian, Q. Fang, and C. Xu. 2022. MGDCF: Distance learning via Markov graph diffusion for neural collaborative filtering. arXiv:2204.02338 (2022).

[24] Y. Hu, Y. Koren, and C. Volinsky. 2008. Collaborative filtering for implicit feedback datasets. In Proc. 8th IEEE Int. Conf. Data Mining. IEEE, 263–272.

[25] A. Jalalirad, M. Scavuzzo, C. Capota, and M. Sprague. 2019. A simple and efficient federated recommender system. In Proc. 6th IEEE/ACM Int. Conf. Big Data Comput. Appl. Technol. 53–58.

[26] X. Jiang, B. Liu, J. Qin, Y. Zhang, and J. Qian. 2022. FedNCF: Federated neural collaborative filtering for privacy-preserving recommender system. In Proc. Int. Joint Conf. Neural Netw. (IJCNN). IEEE, 1–8.

[27] K. Järvelin and J. Kekäläinen. 2002. Cumulated gain-based evaluation of IR techniques. ACM Trans. Inf. Syst. 20, 4 (2002), 422–446.

[28] J. Klicpera, A. Bojchevski, and S. Günnemann. 2019. Predict then propagate: Graph neural networks meet personalized PageRank. In Proc. ICLR.

[29] T. Kong, T. Kim, J. Jeon, J. Choi, Y.-C. Lee, N. Park, and S.-W. Kim. 2022. Linear, or non-linear, that is the question! In Proc. WSDM. 517–525.

[30] N. Korda, B. Szörényi, and S. Li. 2016. Distributed clustering of linear bandits in peer-to-peer networks. In Proc. Int. Conf. Mach. Learn. PMLR, 1301–1309.

[31] Y. Koren, R. Bell, and C. Volinsky. 2009. Matrix factorization techniques for recommender systems. IEEE Computer 42, 8 (2009), 30–37.

[32] D. Liang, R. G. Krishnan, M. D. Hoffman, and T. Jebara. 2018. Variational autoencoders for collaborative filtering. In Proc. 2018 WWW. 689–698.

[33] F. Liu, Z. Cheng, L. Zhu, Z. Gao, and L. Nie. 2021. Interest-aware message-passing GCN for recommendation. In Proc. TheWebConf. 1296–1305.

[34] H. Liu, J. Yu, X. Chen, and L. Zhang. 2022. NeuMF: Predicting anti-cancer drug response through a neural matrix factorization model. Curr. Bioinform. 17, 9 (2022), 835–847.

[35] S. Luo, Y. Xiao, X. Zhang, Y. Liu, W. Ding, and L. Song. 2024. PerFedRec++: Enhancing personalized federated recommendation with self-supervised pre-training. ACM Trans. Intell. Syst. Technol. 15, 5 (2024), 1–24.

[36] J. Ma, C. Zhou, P. Cui, H. Yang, and W. Zhu. 2019. Learning disentangled representations for recommendation. Proc. Adv. Neur. Inf. Proc. Syst. 32 (2019), 1–12.

[37] K. Mahadik, Q. Wu, S. Li, and A. Sabne. 2020. Fast distributed bandits for online recommendation systems. In Proc. 34th ACM Int. Conf. Supercomput. 1–13.

[38] K. Mao, J. Zhu, X. Xiao, B. Lu, Z. Wang, and X. He. 2021. UltraGCN: Ultra simplification of graph convolutional networks for recommendation. In Proc. CIKM.

[39] H. B. McMahan, E. Moore, D. Ramage, and B. A. y Arcas. 2016. Federated learning of deep networks using model averaging. arXiv:1602.05629 (2016).

[40] K. Muhammad, Q. Wang, D. O'Reilly-Morgan, E. Tragos, B. Smyth, N. Hurley, J. Geraci, and A. Lawlor. 2020. FedFast: Going beyond average for faster training of federated recommender systems. In Proc. 26th ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining. 1234–1242.

[41] J. Nicolas, C. Sabater, M. Maouche, S. B. Mokhtar, and M. Coates. 2024. Differentially private and decentralized randomized power method. arXiv:2411.01931 (2024).

[42] J.-D. Park, Y.-M. Shin, and W.-Y. Shin. 2024. Turbo-CF: Matrix decomposition-free graph filtering for fast recommendation. In Proc. 47th Int. ACM SIGIR. 2672–2676.

[43] C. Philippenko. 2024. In-depth analysis of low-rank matrix factorisation in a federated setting. Unpublished (2024).

[44] Y. Rong, W. Huang, T. Xu, and J. Huang. 2020. DropEdge: Towards deep graph convolutional networks on node classification. In Proc. ICLR.

[45] C. Sabater, A. Bellet, and J. Ramon. 2022. An accurate, scalable and verifiable protocol for federated differentially private averaging. Mach. Learn. 111, 11 (2022), 4249–4293.

[46] J. Seeman and D. Susser. 2024. Between privacy and utility: On differential privacy in theory and practice. ACM J. Respons. Comput. 1, 1 (2024), 1–18.

[47] Y. Shen, Y. Wu, Y. Zhang, C. Shan, J. Zhang, B. K. Letaief, and D. Li. 2021. How powerful is graph convolution for recommendation? In Proc. CIKM. 1619–1629.

[48] J. So, C. He, C.-S. Yang, S. Li, Q. Yu, R. E. Ali, B. Güler, and S. Avestimehr. 2022. LightSecAgg: A lightweight and versatile design for secure aggregation in federated learning. Proc. Mach. Learn. Syst. 4 (2022), 694–720.

[49] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. 2018. Graph attention networks. In Proc. ICLR.

[50] X. Wang, X. He, M. Wang, F. Feng, and T.-S. Chua. 2019. Neural graph collaborative filtering. In Proc. 42nd Int. ACM SIGIR Conf. Res. Dev. Inf. Retrieval. 165–174.

[51] C. Wu, F. Wu, L. Lyu, T. Qi, Y. Huang, and X. Xie. 2022. A federated graph neural network framework for privacy-preserving personalization. Nat. Commun. 13, 1 (2022), 3091.

[52] G. Wu, W. Pan, and Z. Ming. 2023. GNN4FR: A lossless GNN-based federated recommendation framework. arXiv:2308.01197 (2023).

[53] J. Wu, X. Wang, F. Feng, X. He, L. Chen, J. Lian, and X. Xie. 2021. Self-supervised graph learning for recommendation. In Proc. SIGIR. 726–735.

[54] M. Wu, L. Li, C. Tao, E. Rigall, X. Wang, and C.-Z. Xu. 2022. FedCDR: Federated cross-domain recommendation for privacy-preserving rating prediction. In Proc. CIKM. 2179–2188.

[55] C. Zhang, S. Li, J. Xia, W. Wang, F. Yan, and Y. Liu. 2020. BatchCrypt: Efficient homomorphic encryption for cross-silo federated learning. In USENIX Annu. Tech. Conf. (USENIX ATC '20). 493–506.

[56] L. Zhang, G. Li, L. Yuan, X. Ding, and Q. Rong. 2024. HN3S: A federated autoencoder framework for collaborative filtering via hybrid negative sampling and secret sharing. Inf. Process. Manage. 61, 2 (2024), 103580.

[57] Y. Zhang, P. Wang, X. Zhao, H. Qi, J. He, J. Jin, C. Peng, Z. Lin, and J. Shao. 2022. IA-GCN: Interactive graph convolutional network for recommendation. arXiv:2204.03827 (2022).

[58] X. Zheng, M. Guan, X. Jia, L. Sun, and Y. Luo. 2023. Federated matrix factorization recommendation based on secret sharing for privacy preserving. IEEE Trans. Comput. Soc. Syst. 11, 3 (2023), 3525–3535.

[59] X. Zheng, Z. Wang, C. Chen, J. Qian, and Y. Yang. 2023. Decentralized graph neural network for privacy-preserving recommendation. In Proc. CIKM. 3494–3504.