{"id":"1c3a78d8-3a6c-4541-a766-5cc392f7a7c9","arxiv_id":"2501.16888","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"PriviRec and PriviRec-k compute graph-based recommendation filters in a federated, confidential manner with centralized-equal accuracy and reduced communication via low-rank approximations.","lead":"This paper proposes two decentralized protocols, PriviRec and PriviRec-k, that compute the item-item similarity matrix and low-pass filter used by modern graph-based recommender systems, using secure aggregation so user interactions stay on-device. A central server coordinates masked sums, and the methods report recommendation accuracy on par with centralized versions at lower communication cost than federated graph networks.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Output leakage contradicts the confidentiality claim: in sparse data, any item with a single user makes that user's full profile readable from the broadcast P~, so §3.5.2's assertion that the item-item matrix gives no user information is false.","rationale":"The reader's weakest assumption is output confidentiality, and I agree with that identification. The security Lemma 3.4 is not merely unproven; it is contradicted by the protocol's own output. The item-item matrix P' is a sum of rank-one per-user Gram matrices. When an item appears in only one user's row, that user's entire interaction row appears as a scaled indicator in P'. This is exactly the sparse-data regime that all three benchmark datasets occupy. Since the server broadcasts P~ (and V is computed via SecAgg and broadcast), any honest-but-curious client can invert the normalization and read the leaked rows. Therefore the central claim of 'confidentiality with no loss in recommendation utility' fails on its own terms. The algebraic equivalence in Theorem 3.1 and the empirical NDCG parity are plausible and are not the issue, but they do not rescue the privacy claim. The proof of Theorem 3.2 also does not match Algorithm 1 (Appendix A uses Y = (A^T A)^alpha A^T Omega, whereas Algorithm 1 starts from a random X0 and alternates A^T and A^T A with a single QR per iteration), but the output-leakage issue is decisive and independent. Because the confidentiality assertion is central to the paper's contribution and is demonstrably false in the stated setting, the appropriate verdict is rejection rather than a conditional acceptance.","tokens_in":14807,"tokens_out":6608,"duration_ms":61334,"concrete_test":"Take the Gowalla training matrix R. Compute P' = sum_u (1/d_user(u)) R(u)^T R(u), as in Eq. (7). For every item i whose column degree is exactly 1, identify the unique user u, and compare the support of row (P')_{i,:} with the support of R(u). If the supports match (they will by the algebra above), the broadcast P~ discloses complete user profiles. Report the number and fraction of users who have at least one degree-1 item; if this fraction is nonzero, the confidentiality guarantee of Lemma 3.4 is false. A minimal synthetic check is also useful: construct one user with a unique item and confirm that the corresponding row of P' equals that user's indicator vector scaled by 1/d_user.","verdict_should_be":"REJECT","load_bearing_attack":"Section 3.5.2 asserts that P' 'does not give information about users' and Lemma 3.4 claims confidentiality, but the disclosed output itself leaks. The protocol broadcasts P~ = V^{-1/2} P' V^{-1/2} (Figure 4), and V is public, so P' is available to every honest-but-curious client. For any item i with degree V_ii = 1, exactly one user u interacted with i. Then (P')_{ij} = sum_v (1/d_user(v)) r_{vi} r_{vj} = (1/d_user(u)) r_{uj}, since all other r_{vi} = 0. Thus the support of row (P')_{i,:} is exactly R(u), the full interaction vector of user u, and the constant 1/d_user(u) is recoverable from that row. Gowalla, Yelp2018, and Amazon-Book have densities 0.084%, 0.130%, and 0.062%, respectively, so many items have degree one. This is a direct violation of the stated requirement that 'the aggregate must not leak sensitive information' (§3.2). Secure aggregation only protects the computation phase; it does nothing to protect the final aggregate that is deliberately broadcast to all clients. The same issue affects F_IDL through S_k S_k^T if a singular vector is dominated by a rare user-item pattern. No proof in the paper addresses this, because the security analysis treats output confidentiality as self-evident rather than proving it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PriviRec and PriviRec-k, two decentralized protocols that use Secure Aggregation to compute the normalized item-item matrix and the ideal low-pass filter used by graph-based recommender systems such as GF-CF and BSPM. The core algebraic claim is that the normalized item-item matrix can be written as a secure aggregation of per-user Gram terms, and the ideal low-pass filter can be obtained from a distributed randomized power method. The authors evaluate the resulting filters by plugging them into GF-CF, Turbo-CF, and BSPM on Gowalla, Yelp2018, and Amazon-Book, reporting NDCG@20 values within a few thousandths of the centralized counterparts. The paper also provides communication-complexity comparisons showing that the low-rank variant PriviRec-k is cheaper than federated GCN/matrix-factorization baselines.","tokens_in":15104,"tokens_out":7532,"duration_ms":74321,"significance":"The algebraic decomposition in Theorem 3.1 is clean and correct, and the empirical finding that the distributed protocol reproduces centralized recommendation accuracy up to numerical noise is a useful and convincing demonstration. The communication-cost analysis is also an asset: it gives concrete complexity expressions and translates them to float counts for Gowalla, making the claimed efficiency concrete. However, the headline contribution is confidentiality, and that claim is not supported. The broadcast output itself leaks user profiles, as detailed below, so the paper does not establish the advertised privacy guarantee. If the confidentiality claims were removed and replaced by an honest analysis of output leakage, the distributed-computation contribution could be salvageable, but as submitted the main advertised benefit is invalidated.","major_comments":[{"comment":"The confidentiality claim fails for the broadcast aggregate. The protocol broadcasts P~ = V^{-1/2} P' V^{-1/2} (Figure 4), and V is public (Eq. (6)), so every honest-but-curious client recovers P'. For any item i with V_ii = 1, exactly one user u has r_ui = 1. Equation (9) then gives P'_{i,j} = (1/d_user(u)) r_{u,j} for every j, so the support of row i of P' is exactly the full interaction vector of user u, and the normalization constant 1/d_user(u) is recoverable from that row. The benchmark datasets have densities 0.084%, 0.130%, and 0.062% (Table 2), and sparse long-tail item degree distributions make degree-one items common; even a single degree-one item suffices to violate the confidentiality requirement stated in §3.2 and contradicted by the §3.5.2 assertion that the item-item matrix 'does not give information about users.' Secure aggregation protects only the computation phase; it does not protect the deliberately broadcast final output. The same structural issue can affect F_IDL through S_k S_k^T whenever a top singular vector is aligned with a rare user-item pattern. No part of the security analysis addresses this, because the proof treats output confidentiality as self-evident rather than proving it.","section":"§3.5.2, Lemma 3.4, Eq. (7), Figure 4"},{"comment":"The proof in Appendix A does not match the algorithm as written. Algorithm 1 iteratively computes Y_0 = SecAgg(A(u)^T X_0) and then Y_ell = SecAgg(A(u)^T A(u) X_{ell-1}), with one QR factorization per iteration. The proof in Eq. (17), by contrast, analyzes Y = (\\tilde R^T \\tilde R)^\\alpha \\tilde R^T \\Omega and derives SS^T = QQ^T. The relationship between the generic A(u), the normalized matrix \\tilde R, the exponent \\alpha, and the two-phase power iteration is never defined or justified. Since Theorem 3.2 is the load-bearing justification for the distributed ideal low-pass filter, the authors must reconcile the proof with Algorithm 1, or state exactly which variant of the randomized power method is implemented and prove the algorithm that is actually run.","section":"Appendix A, Algorithm 1, Theorem 3.2"},{"comment":"The security proof of Lemma 3.4 is not a proof of the stated confidentiality property. Point 1 of the lemma requires that 'the aggregate must not leak sensitive information,' but the proof only cites properties of Secure Aggregation regarding individual contributions and correctness. The item-item matrix computation in §3.5.2 asserts that the aggregate 'does not give information about users' without any formal argument, and this assertion is false for the degree-one-item attack described above. A revision must either provide a rigorous information-theoretic or computational argument for output privacy, or substantially weaken the confidentiality claim and add an explicit leakage analysis.","section":"§3.5, Lemma 3.4"}],"minor_comments":[{"comment":"The caption says the server 'homomorphically sums' masked data, but Bell et al.'s Secure Aggregation relies on mask cancellation and secret sharing rather than homomorphic encryption; the wording should be corrected.","section":"Figure 1 caption"},{"comment":"There is a typo: 'we use use L = 3' should be 'we use L = 3'.","section":"§3.6"},{"comment":"The notation in Eq. (10) writes \\tilde P = \\sum_u \\tilde R_u^T \\tilde R_u, but earlier definitions include the V^{-1/2} normalization on both sides; the relationship between these expressions should be stated explicitly to avoid confusion.","section":"§3.4.1, Eq. (10)"},{"comment":"The proof introduces \\alpha and \\Omega without connecting them to Algorithm 1; either define them precisely in the algorithm or remove them from the proof.","section":"Appendix A"}],"recommendation":"reject","confidential_remarks":"The algebraic derivation and the empirical reproduction of centralized results are solid, and I could see a reframed version being publishable as a distributed computation paper. However, the paper's headline claim is confidentiality, and the broadcast item-item matrix leaks complete user profiles for degree-one items. That is a load-bearing error in the central contribution, not a local gap that minor edits can close. If the authors are willing to remove the confidentiality claim and add an explicit analysis of output leakage (for example, by quantifying leakage and adding differential privacy), the work would deserve re-review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The algebraic core of this paper is correct: Theorem 3.1 cleanly expresses the normalized item-item matrix as a secure aggregation of per-user Gram terms, and the distributed power iteration is a sensible adaptation of known work, properly citing [42]. The empirical parity with centralized GF-CF and BSPM is expected because it is the same computation modulo numerical noise. I give credit for a well-written, honest treatment of the no-dropout, honest-but-curious model.\n\nThe soft spot is not minor; it is load-bearing. Section 3.5.2 claims that P' \"does not give information about users,\" but the protocol broadcasts ~P, and V is public, so every client can compute P' = V^{1/2} ~P V^{1/2}. For any item i with only one interaction (V_ii = 1), the row P'_ij equals r_uj / d_user(u) for that single user u. That row is u's entire interaction vector, scaled. With dataset densities of 0.06–0.13%, degree-1 items are plentiful, so the confidentiality guarantee fails for exactly the sparse data this method targets. The stress-test note is correct, and it directly contradicts the threat model's requirement that the aggregate not leak sensitive information.\n\nA second issue: the proof of Theorem 3.2 in Appendix A does not match Algorithm 1. The proof discusses building QZ from a randomized SVD, but the algorithm never forms QZ; it only does QR decompositions of secagg outputs. This may be repairable, but as written the proof does not cover the implementation.\n\nSmaller concerns: the communication-cost comparison in Table 1 is helpful but the experiments lack error bars, and the fixed-participant assumption is stated, which is fine, but it further limits the practical reach.\n\nWho gets value from this paper? Readers working on decentralized recommender systems will appreciate the algebraic decomposition and the power-method adaptation, and the paper is a good case study of why output privacy is harder than input privacy. I would not cite it as a secure protocol, but I would send it to peer review: the flaw is important, subtle, and fixable (e.g., restricting to items with degree above a threshold, adding differential privacy, or not broadcasting the filter), and the non-privacy contributions deserve referee time.","headline":"The algebra is right and the privacy claim is wrong: the broadcast item-item matrix leaks full user profiles through degree-1 items.","tokens_in":15623,"tokens_out":2170,"would_cite":false,"duration_ms":22157,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that the normalized item-item matrix and the ideal low-pass filter can be computed over user-held data with secure aggregation, matching centralized accuracy to within 0.001 NDCG@20.","keywords":["secure aggregation","graph filtering","item-item matrix","low-pass filter","federated recommender system","multi-party computation","low-rank approximation","privacy-preserving recommendation"],"falsifier":"Take a synthetic dataset with one distinctive user who has interacted with a rare pair of items that no other user has both interacted with; if the released normalized item-item matrix allows an observer to recover that pair, the confidentiality claim is false.","tokens_in":14603,"feed_emoji":"🔐","tokens_out":8016,"duration_ms":59070,"temperature":0.7,"pith_summary":"This paper aims to establish that two graph-based components central to state-of-the-art recommender systems—the normalized item-item matrix and the ideal low-pass filter—can be computed from user-held data without any central server seeing individual interactions. The key move is rewriting the normalized item-item matrix as a sum of per-user terms, each the user's local gram matrix divided by their degree, so a secure aggregation protocol can add them up without revealing them. When these components are plugged into the recommender models GF-CF and BSPM, ranking quality measured by NDCG@20 stays within roughly 0.001 of the centralized versions on Gowalla, Yelp2018, and Amazon-Book. A low-rank variant, PriviRec-k, trades a small accuracy difference for much lower communication cost.","feed_headline":"Private recommender filters match centralized accuracy","feed_subtitle":"Item-item matrix and low-pass filter computed over user-held data via secure aggregation; low-rank variant lowers cost.","key_machinery":"The load-bearing object is the per-user gram term $R^{(u)\\\\top} R^{(u)}$ divided by the user's degree, together with the secure aggregation that sums these terms into the global item-item matrix. A distributed randomized power iteration over the normalized interaction matrix supplies the top singular vectors needed for the ideal low-pass filter, with only the server performing QR factorizations.","core_discovery":"The central claim is Theorem 3.1: the normalized item-item matrix can be written as a secure aggregation of per-user terms, $\\tilde{P} = V^{-1/2}\\,\\mathrm{SecAgg}_u(d_{\\mathrm{user}}(u)^{-1} R^{(u)\\\\top} R^{(u)})\\, V^{-1/2}$. This identity turns a global gram-matrix computation into a sum of local contributions, so the filter is computed without exposing any individual row of the interaction matrix. The paper also supplies a distributed version of the randomized power iteration that computes the ideal low-pass filter, and it proves that the protocol is confidential and correct under the honest-but-curious threat model with no dropouts. The empirical result is that the decentralized filters reproduce centralized recommendation accuracy to within 0.001 NDCG@20 on three standard datasets.","pith_inferences":["A natural extension is to apply the same per-user gram decomposition to other gram-matrix-based filters, such as user-user similarity or higher-order graph filters, provided each local term is a polynomial in $R^{(u)}$.","The confidentiality guarantee depends on the released aggregates not revealing individual patterns; one could test this by bounding the information in the public item-item matrix under a differential-privacy-style adversary.","Moving beyond the no-dropout assumption would require pairing the protocol with drop-out-resistant secure aggregation and client sampling, which the paper does not analyze.","The paper's empirical claim covers only binary interactions; extending to explicit ratings or multi-valued feedback would require a different normalization but the same aggregation structure."],"forward_implications":["If the central claim is correct, recommender systems that rely on the normalized item-item matrix or the ideal low-pass filter can be instantiated over user-held data with no central curator, because the computed filters are algebraically equivalent to the centralized ones.","PriviRec-k shows that keeping only $k$ singular vectors (around 2000 to 3584 on the benchmark datasets) preserves competitive NDCG while cutting communication from order $|I|^2$ to order $k |I|$.","Because the protocol uses secure aggregation with polylogarithmic overhead, the per-client communication grows slowly with the number of participants.","The same filters can then be combined with other components of GF-CF, BSPM, or Turbo-CF without changing the inference formulas."],"supporting_citations":[{"why":"Supplies the polylogarithmic-cost secure aggregation protocol used for every distributed sum in the paper.","marker":"[5]"},{"why":"Provides the randomized power iteration that the distributed algorithm adapts to compute the ideal low-pass filter.","marker":"[18]"},{"why":"Defines GF-CF, the centralized recommender whose filters are decentralized and benchmarked in the experiments.","marker":"[46]"},{"why":"Defines BSPM, the second centralized model whose filters are decentralized and benchmarked in the experiments.","marker":"[13]"},{"why":"Supplies the federated low-rank power-iteration variant that PriviRec-k adapts.","marker":"[42]"},{"why":"Provides the Gowalla dataset used to evaluate recommendation utility.","marker":"[11]"},{"why":"Provides the Yelp2018 dataset and the LightGCN baseline used in the experiments.","marker":"[23]"},{"why":"Provides the Amazon-Book dataset used in the evaluation.","marker":"[50]"}],"fun_headline_variants":["Federated graph filters keep recommendations private","Secure graph filters match central accuracy in recommenders","Private federated filtering for recommenders without data leaks","Decentralized graph filters hit central-accuracy on recommenders"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole protocol stays confidential only if the final aggregate outputs—the item-item matrix and the released singular vectors—cannot be used to reconstruct any user's interaction pattern; the paper asserts this without proving a formal bound.","fun_headline_variants_meta":{"raw":{"variants":["Federated graph filters keep recommendations private","Secure graph filters match central accuracy in recommenders","Private federated filtering for recommenders without data leaks","Decentralized graph filters hit central-accuracy on recommenders"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000194,"raw_usage":{"total_tokens":1303,"prompt_tokens":842,"completion_tokens":461,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":399}},"tokens_in":458,"tokens_out":461,"duration_ms":5079,"temperature":1.0,"reasoning_tokens":399,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T05:51:00.503669+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a synthetic dataset with one distinctive user who has interacted with a rare pair of items that no other user has both interacted with; if the released normalized item-item matrix allows an observer to recover that pair, the confidentiality claim is false.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the polylogarithmic-cost secure aggregation protocol used for every distributed sum in the paper."},{"cited_title":"Halko, P.-G","cited_arxiv_id":null,"evidence_quote":"Provides the randomized power iteration that the distributed algorithm adapts to compute the ideal low-pass filter."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines GF-CF, the centralized recommender whose filters are decentralized and benchmarked in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines BSPM, the second centralized model whose filters are decentralized and benchmarked in the experiments."},{"cited_title":"Philippenko","cited_arxiv_id":null,"evidence_quote":"Supplies the federated low-rank power-iteration variant that PriviRec-k adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Gowalla dataset used to evaluate recommendation utility."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Yelp2018 dataset and the LightGCN baseline used in the experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Amazon-Book dataset used in the evaluation."}],"review_version":1}