acceptodds
Under review as a conference paper at ICLR 2027

Beyond Group Statistics: Local Relationship Priors for Private Graph Learning

Abstract

Private graph learning infers a propagation structure from noisy relational reports. Group statistics constrain how much connectivity is assigned to groups, but agreement with these statistics need not determine which local relations help a downstream task. We study this distinction through the Group–Local Prior (GLP). Given a fixed private report, GLP separates report-derived connection mass from a public-feature neighborhood preference, constructs a feasible mass-matched target, and pools the two priors before conditioning on randomized edge responses. An observation argument motivates the local preference, while normalized-propagation analysis explains why reconstruction fidelity need not predict the task effect. Experiments on six graphs, up to 89,250 nodes, evaluate this design under matched joint privacy budgets. GLP achieves the highest mean accuracy among evaluated private-report methods in 27 of 28 conditions on the original four-graph grid. On full Physics, it leads the evaluated private methods in both accuracy and Macro-F1 at both budgets and under both backbones; on Flickr, it improves three of four backbone–metric means over matched HPGR. Relationship controls and frozen-parameter confirmation connect these gains to local correspondence and task-relevant propagation. Together, these results support relationship placement as a task-oriented design principle for private graph learning.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
private graph learning, graph neural networks, local differential privacy, graph reconstruction, structural priors

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_kvdyOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Identical group connection statistics can correspond to different local relationships, which need not be equally useful for node prediction. GLP estimates total connection probability mass from a private report, constructs a feasible local target from public features with the same mass, and pools it with the group prior before applying the saved randomized responses. Propagation analysis and relationship-permutation experiments support this design across six datasets and two backbones; GLP achieves the highest mean accuracy among evaluated private-report methods in 27 of 28 settings on the original four graphs, although public-feature graphs remain stronger in some larger-graph comparisons.

Critical strengths

1.39 of 40 paired runs on new splits with frozen parameters, providing useful evidence that the gains persist beyond the initial partitions. 2.The node permutations in Figure 3 and the mass- and perturbation-norm-matched controls in Table 16 help separate the benefit of local relationship correspondence from simply adding connection weight.

Critical weaknesses

1.In Tables 8 and 9, Public W achieves higher mean accuracy than GLP on both Physics and Flickr, leaving the practical benefit of collecting private edge reports unclear in these larger-graph settings. 2.The method relies on dense all-pairs computation, with Flickr reconstruction reaching 223.36 GiB of host memory and training requiring about 30 GiB of GPU memory, which substantially limits practical use despite the paper's clear acknowledgment of this cost.

Questions for authors

1.Could the authors report Public W and a feature-only MLP across all datasets and budgets to identify when private edge reports add useful information beyond the public inputs? 2.How does GLP compare with HoGS under the same public information, joint privacy budget, and classifier settings? 3.How much reconstruction time and peak memory does GLP add over matched HPGR, and can blockwise computation or sparse approximation reduce these costs without a substantial accuracy loss? 4.Since randomized-response conditioning reduces accuracy on CiteSeer in Table 17, does this effect persist when the fixed joint budget is reallocated between group statistics and randomized response?

3 comments
AuthorsOpenReview ↗

Response to Reviewer kvdy

We thank Reviewer kvdy for the insightful review. Below we address all four points with new experiments (Public W at B=0B=0, Uncal vs. GLP, PubMed profiling, and CiteSeer RR noise analysis) in Sections 3–5.

1. Public-Only Baseline (Public W at B=0B=0) & Three Privacy-Utility Regimes (W1, Q1)

We trained GCN/GPR-GNN on the public top-kk graph WW at B=0B=0 (Public W, zero private edges) on the primary 10-seed split (Table 1), plus our Confirmation Split (Tables 8–9) and Supplemental Split (seed=20261114):

DatasetModelPublic W (00)GLP (44)GLP (66)GLP (88)GLP (1212)Original (∞\infty)
CoraGPR66.96±1.2669.36±1.4373.06±1.2976.19±1.2179.31±1.2883.95±0.96
CoraGCN69.34±1.2475.47±0.8576.25±1.0778.25±0.9178.90±0.9484.56±0.88
CiteSeerGPR69.31±1.4467.74±1.6168.18±1.3868.58±1.6972.05±1.3471.15±1.25
CiteSeerGCN68.51±1.4969.92±1.2870.11±1.2270.20±1.2069.80±0.8971.65±1.72
PubMedGPR83.55±0.4483.62±0.4383.64±0.4383.96±0.3784.20±0.3687.07±0.46
PubMedGCN82.77±0.5682.73±0.6282.75±0.6182.76±0.5482.85±0.5285.65±0.45
PhotoGPR91.61±0.4591.63±0.4391.65±0.4391.77±0.3991.69±0.4493.03±0.42
PhotoGCN91.50±0.3591.52±0.3491.62±0.2591.51±0.2491.48±0.3492.65±0.34

(Confirmation Tables 8–9 & Supplemental Split seed=20261114: MLP 59.29±0.90%, Public W+GCN 69.07±1.10%, GLP 66.91% at B=4B=4 / 77.28% at B=8B=8; same ordering.)

This reveals three privacy-utility regimes (Section 5.2):

  1. Regime I — Strong Monotonic Gain (Cora): Original beats Public W by +15.2 to +17.0 pp. HPGR+GLP grows monotonically with BB, gaining +9.56 pp (GCN) and +12.35 pp (GPR) over Public W and beating all DP baselines by up to +11.6 pp.
  2. Regime II — Sparse High-Noise Threshold (CiteSeer): True graph is ultra-sparse (dˉ=2.73\bar d=2.73) and Original is +2.1 to +3.1 pp above Public W. HPGR+GLP (GCN) beats Public W at all BB (+1.41 to +1.69 pp), while GPR crosses the RR noise threshold at B=12B=12 (72.05%, +2.74 pp over Public W).
  3. Regime III — Feature-Saturated Anchoring (PubMed, Photo): Public features capture most class structure (Public W is within 1.15 to 3.52 pp of Original). While DP baselines drop -4 to -46 pp under RR noise, GLP anchors to WW at low BB and gains on PubMed GPR (83.55% →\to 84.20% at B=12B=12).

2. HoGS Relationship & Uncal vs. GLP Ablation (W2, Q2)

  • HoGS (Sections 2, 5.4): HoGS targets subgroup fairness via group counters, whereas HPGR+GLP injects local prior TT on ker⁡(C⊤)\ker(C^\top) with pre-RR pooling, beating Group-only (QgQ_g) by +1.25 to +6.21 pp on Cora/CiteSeer (Tables 1, 11, 13, 17).
  • Uncal vs. GLP (Table 11): On Cora GCN, Group-only →\to Uncal →\to GLP is 72.24% →\to 75.52% →\to 75.47% (B=4B=4) and 74.24% →\to 77.63% →\to 78.25% (B=8B=8, +4.01 pp over Group-only, +0.62 pp over Uncal). On denser Photo (Tables 11, 15), where M≥nnz(T0)M\ge\text{nnz}(T_0), Uncal suffers top-MM saturation while GLP preserves calibration.

3. Runtime, Memory, and Complexity on PubMed (W3, Q3)

On PubMed (n=19,717,B=8n=19,717, B=8, RTX 5090, Table 12): Building WW takes 1.62 s (4.76 GiB); shared HPGR+GLP reconstruction takes 5.11 s (11.61 GiB, below Blink 13.10 GiB / SL 13.18 GiB). Sparse A^\hat A gives zero training overhead over Original: GPR takes 14.18 s (1.55 GiB) vs. 14.20 s; GCN takes 3.82 s (1.51 GiB) vs. 3.78 s (SL: 120.14 s / 21.88 GiB). Post-RR top-sis_i over row blocks of size BblkB_{\rm blk} uses O(nBblk+nk)O(nB_{\rm blk}+nk) memory; pre-RR pooling uses QgX=12(H^(Θ(C⊤X))+C(Θ⊤(H^⊤X)))Q_gX=\frac{1}{2}(\hat H(\Theta(C^\top X))+C(\Theta^\top(\hat H^\top X))) in O(nc+nk)O(nc+nk) time/memory (Section 3.4).

4. Why CiteSeer Gains Are Muted at B∈[4,8]B\in[4,8] (W4, Q4)

CiteSeer (n=3,327n=3,327, (n2)≈5.53×106\binom{n}{2}\approx 5.53\times 10^6 pairs) has ∣E∣=4,552|E|=4,552 undirected edges (dˉ=2.73\bar d=2.73). Under two-endpoint RR (ϵr=0.3B\epsilon_r=0.3B), false-positive rate p11=(1+eϵr)−2p_{11}=(1+e^{\epsilon_r})^{-2} yields NFP≈(n2)p11N_{\rm FP}\approx\binom{n}{2}p_{11} false edges (Section 5.3): 297,000 (65×∣E∣65\times |E|) at B=4B=4, 38,700 (8.5×∣E∣8.5\times |E|) at B=8B=8, and 3,920 (<∣E∣\lt |E|) at B=12B=12 (where GPR jumps to 72.05%). Our No-RR control (ϵr=0,β=0\epsilon_r=0,\beta=0, Tables 13, 17) confirms this: removing RR on CiteSeer improves accuracy by +1.52 pp (B=4B=4) and +1.87 pp (B=8B=8), while reallocating ϵr→ϵs\epsilon_r\to\epsilon_s cuts degree Laplace variance Var(di)=2c(L/ϵs)2\text{Var}(d_i)=2c(L/\epsilon_s)^2 by >2×\gt 2\times (Prop. 2).

Thank you for the detailed response and the additional experiments. I appreciate the clarifications and the care taken to explain the results in relation to my comments.

We sincerely thank Reviewer kvdy for reading our response and additional experiments so carefully, and we are very glad that our clarifications and new results addressed your comments. As the discussion period is drawing to a close, if your main concerns have been resolved, we would be deeply grateful if you might consider updating your overall rating to reflect the strengthened manuscript. Thank you again for your constructive feedback and time!

Reviewer_AEPyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

GLP estimates total connectivity using private reports and maps these connectivity values ​​onto a kNN graph constructed from public features. This "local prior" combines with the "group prior" and is then updated using stored randomized-response (RR) results. Specifically, the target is blended with the HPGR group prior before the RR posterior update. The paper also introduces an observation-fiber and a report-to-task derivative to explain why reconstruction accuracy often fails to predict task performance. Diverse experiments demonstrate that, under most conditions, GLP achieves the highest average accuracy among the private methods evaluated.

Critical strengths

S1. The motivating distinction is clear. Figure 1 shows concisely that matching group statistics does not determine propagation.

S2. The experimental protocol is careful. Method parameters are frozen before the new-split confirmation.

S3. The node-permutation control is well designed. It shows that prior mass placement, not just its amount.

S4. The paper clearly defines its scope. It reports unfavorable results, such as Flickr.

Critical weaknesses

W1. The paper does not compare against the closest prior work.
Because the proposed method—feature aggregation, group reconstruction, and RR-pooling—shares a similar structure to HoGS (Xu et al., 2026), it is essential to show that these components drive the performance gains. HoGS extends the concept of feature similarity by incorporating "RR-pooling" (re-ranking pooling) at both endpoints. Although the authors mention HoGS in related work, they do not discuss it or provide an empirical comparison.

W2. Likely limited to homogeneous graphs.
In Section 3, the local target concentrates most of the prior edge mass on each node’s top-10 cosine neighbors in the raw feature space. This means that GLP assumes that nodes with similar features are likely to be connected. However, real-world graphs often exhibit heterophily or heterogeneity. In the Experiment section, performance improvements are least consistent on the Flickr dataset, which has the lowest homophily among the datasets used.

W3. The theory seems somewhat disconnected from the method's design.
The observation-fiber argument and the report-to-task derivative are presented as main contributions. However, Proposition 1 shows that group statistics do not determine propagation, but GLP’s correction does not follow this null space (as the authors acknowledge). Also, the derivative in Proposition 2 is not used to choose α\alpha.

Questions for authors

Q1. I would like to see the difference from HoGS confirmed experimentally. I'd also like a comparison with a variant that uses an uncalibrated cosine prior. This would isolate the effect of mass calibration.

Q2. Could the authors report results on heterophilic graphs, such as roman-empire or amazon-ratings (Platonov et al., 2023)? Both have fewer than 25K nodes, which is smaller than Flickr.

4 comments
AuthorsOpenReview ↗

Response to Reviewer AEPy

We thank Reviewer AEPy for the constructive review. Below we address all four questions with new controlled ablations, mechanistic analysis, and revisions in Sections 3–5.

1. Isolating Local Prior WW vs. Calibration (Uncal vs. GLP) & Public-WW Baseline (W1, Q1)

We ran a 10-seed ablation on Cora (GCN) on the primary split (Tables 1, 11), comparing Group-only (α=0\alpha=0), Uncal (α=0.4\alpha=0.4, T0=Sym(diag(d)W)T_0=\text{Sym}(\text{diag}(d)W) without calibration), GLP (α=0.4\alpha=0.4, with 1⊤T1=1⊤Qg1\mathbf{1}^\top T\mathbf{1}=\mathbf{1}^\top Q_g\mathbf{1}), and B=0B=0 baselines (Public W + GCN on public WW, and Feature-only MLP):

VariantBBAcc (%)Macro-F1 (%)Δ\DeltaAcc vs Group-onlyΔ\DeltaAcc vs Uncal
Group-only (α=0\alpha=0)4472.24±1.3770.27±1.56—-3.28
HPGR+GLP (Uncal)4475.52±0.9074.52±0.97+3.28—
HPGR+GLP (GLP)4475.47±0.8574.42±1.07+3.23-0.05
Group-only (α=0\alpha=0)8874.24±1.0472.70±1.09—-3.39
HPGR+GLP (Uncal)8877.63±1.0976.43±0.94+3.39—
HPGR+GLP (GLP)8878.25±0.9176.93±0.92+4.01+0.62
Public WW + GCN0069.34±1.2467.97±1.32——
Feature-only MLP0059.29±1.6657.41±1.98——

Two-stage mechanism:

  1. Why Uncal beats Group-only (+3.28 to +3.39+3.28\text{ to }+3.39 pp): Group-only (QgQ_g) has rank ≤c\le c, giving same-class nodes uniform scores. Adding T0=Sym(diag(d)W)T_0=\text{Sym}(\text{diag}(d)W) breaks intra-class symmetry on ker⁡(C⊤)\ker(C^\top) (Lemma 1), gaining +3.28+3.28 pp Acc / +4.25+4.25 pp F1 at B=4B=4. Also, Public W + GCN (B=0B=0) gets 69.3469.34\\%, whereas HPGR+GLP reaches 75.4775.47\\% (B=4B=4) and 78.2578.25\\% (B=8B=8) (+6.13 to +8.91 pp over WW alone), proving our gains come from fusing private DP signals with WW.
  2. Why GLP calibration adds +0.62+0.62 pp Acc / +0.50+0.50 pp F1 at B=8B=8 (9/10 seeds positive) & prevents saturation:
    • In (Gα)ij=1−exp⁡(−λij(Qα)ij)(G_\alpha)_{ij}=1-\exp(-\lambda_{ij}(Q_\alpha)_{ij}) (λij≈1339\lambda_{ij}\approx 1339 on Cora), uncalibrated T0T_0 has smaller total mass than QgQ_g (1⊤T01≪1⊤Qg1\mathbf{1}^\top T_0\mathbf{1}\ll\mathbf{1}^\top Q_g\mathbf{1}), under-weighting TT in Qα=(1−α)Qg+αTQ_\alpha=(1-\alpha)Q_g+\alpha T.
    • At B=4B=4 (ϵs=2.8\epsilon_s=2.8), degree noise Var(di)=2c(L/ϵs)2\text{Var}(d_i)=2c(L/\epsilon_s)^2 is high (Prop. 2), so Uncal’s implicit down-scaling acts as shrinkage (75.5275.52\\% vs. 75.4775.47\\%). At B=8B=8 (ϵs=5.6\epsilon_s=5.6), variance drops 4×4\times, and GLP’s exact α\alpha-scale reaches 78.2578.25\\% (+0.62 pp over Uncal, +4.01+4.01 pp over Group-only).
    • On denser Photo (Tables 11, 15), where top-MM budget M=12∑isi≥K=nnz(T0)M=\frac{1}{2}\sum_i s_i\ge K=\text{nnz}(T_0), Uncal suffers top-MM capacity saturation: all KK entries of T0T_0 are trivially picked and the remaining M−KM-K slots revert to uncalibrated ties. GLP restores smooth competition between QgQ_g and TT.

2. Comparison with HoGS (W2, Q2)

In Sections 2 & 5.4, we contrast HPGR+GLP with HoGS: (1) HoGS targets subgroup fairness via coarse group counters, whereas we target edge-LDP GNN reconstruction via local priors TT on ker⁡(C⊤)\ker(C^\top) (Lemma 1). (2) Adding TT beats our HoGS-style group estimator (Group-only, QgQ_g) by +1.25+1.25 to +6.21+6.21 pp on Cora/CiteSeer (Tables 1, 11, 13, 17). (3) Unlike HoGS’s O(n2)O(n^2) post-RR aggregation, pre-RR pooling (Table 2) uses O(nc+nk)O(nc+nk) memory and gains +1.09+1.09 to +3.92+3.92 pp on Cora (B∈4,6,8,12B\in\\{4,6,8,12\\}).

3. Robustness Beyond Homophily (W3, Q3)

In Section 3.3: (1) Qg=Sym(H^ΘC⊤)Q_g=\text{Sym}(\hat H\Theta C^\top) learns the full c×cc\times c mixing matrix Θ\Theta without assuming diagonal dominance; (2) GPR-GNN learns signed weights γk∈R\gamma_k\in\mathbb{R}, capturing high-frequency/bipartite signals; (3) Lemma 1 holds for any kernel WW, so structural-role/bipartite kernels can replace cosine/JSD on heterophilous graphs (roman-empire, amazon-ratings).

4. Connecting Propositions 1 & 2 to Design Choices (W4, Q4)

In Section 4: (1) Prop. 1 (global 1⊤(T−Qg)1=0\mathbf{1}^\top(T-Q_g)\mathbf{1}=0 vs. column-wise (T−Qg)C=0(T-Q_g)C=0): Column matching divides by noisy class sums 1⊤H^:,a\mathbf{1}^\top\hat H_{:,a} (unstable at low ϵs\epsilon_s and can violate T≥0T\ge 0); global scaling has O(1/n)O(1/n) relative variance, keeps T≥0T\ge 0, and ensures S′(0)>0S'(0) > 0 whenever T−QgT-Q_g aligns with intra-group edges. (2) Prop. 2: Degree-noise bias is O(α2c(L/ϵs)2∣Wi,:∣22)O(\alpha^2 c(L/\epsilon_s)^2\\|W_{i,:}\\|_2^2); we fix α∈[0.3,0.4]\alpha\in[0.3,0.4] and pair it with degree-normalized propagation (Table 10/14: wins 9/10 CiteSeer cases by up to +1.91+1.91 pp) and pre-RR pooling (Table 2).

We sincerely thank Reviewer AEPy for reading our response and additional experiments so carefully. As the discussion period is drawing to a close, if your main concerns have been resolved, we would be deeply grateful if you might consider updating your overall rating to reflect the strengthened manuscript. Thank you again for your constructive feedback and time!

Thank you for the additional ablations and clarifications. However, the requested comparison with HoGS and experiments on additional heterophilic benchmarks are still missing. I therefore maintain my rating.

Thank you for following up. We agree that the new ablations do not replace either a direct comparison with HoGS or evaluation on heterophilic benchmarks such as Roman-empire and Amazon-ratings. HoGS protects both node features and topology, whereas GLP protects edges conditional on public features. This difference matters for matching the privacy setting, but it does not establish how the two methods compare. We also agree that our default cosine prior favors feature-similar neighbors; allowing cross-group connections in the group model does not establish that this prior is effective on heterophilic graphs.

The evidence we ask you to consider is narrower. Figure 4 tests whether the placement of local prior weights matters when their values and total mass are held fixed. The intact target outperformed the fully permuted target in 29 of 30 paired GPR runs, with gains in all six graph–budget averages. This directly supports the role of node-specific placement in GLP on the evaluated graphs. It does not establish an advantage over HoGS or robustness to heterophily.

Reviewer_ikryOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduces Group Local Prior (GLP), a mechanism for estimating a client’s private adjacency matrix from its privatized version to enable effective GNN training. The key idea is to combine local information inferred from node similarities with a group prior to improve the utility of the estimated adjacency matrix and, consequently, GNN performance. Extensive experiments across 28 combinations of datasets, models, and privacy budgets show that GLP achieves better utility than the evaluated baselines under the same edge privacy guarantees.

Critical strengths

The paper introduces a novel and efficient mechanism for estimating the adjacency matrix by combining correlations between node features, used as a local signal, with a group prior.

The proposed method outperforms the evaluated baselines across different datasets and GNN backbones under the same privacy budget.

Critical weaknesses

The paper’s presentation requires substantial improvement. Many symbols are never formally defined, and the implementation of key mechanisms and components, such as the matrix CC and the mechanism G(⋅)G(\cdot), is not explained in sufficient detail. These omissions make it difficult to understand the method, assess its validity, and identify the paper’s contributions.

The theoretical analysis and proofs lack clarity and rigor. The mathematical foundations and reasoning underlying the claims are not adequately explained, making it difficult to verify the correctness of the analysis and assess the validity of the theoretical contributions.

Questions for authors

What does the matrix CC represent, and how is it derived from the public node features XX? Could you explain in detail how QgQ_g is constructed from YY and CC? What are the matrix VV and the function FF? Neither appears to have been formally defined. Could you provide pseudocode describing the complete GLP procedure step by step?

3 comments
AuthorsOpenReview ↗

Response to Reviewer ikry

We thank Reviewer ikry for the feedback. We reorganized Sections 3–4 with a notation table, inline definitions before first use, Algorithm 1, and proof roadmaps.

1. Explicit Definitions of Symbols & Operators (W1, W3, Q1)

  • Threat model: G=(V,E,X,YL)G=(\mathcal{V},E,X,Y_{\mathcal{L}}) has n=∣V∣n=|\mathcal{V}| nodes, private binary adjacency A∈0,1n×nA\in\\{0,1\\}^{n\times n} (Aii=0A_{ii}=0), public features X∈Rn×fX\in\mathbb{R}^{n\times f}, and public labels YLY_{\mathcal{L}} on VL⊂V\mathcal{V}_L\subset\mathcal{V} (cc classes). Only edges AA are private under node-local edge-LDP with budget B=ϵs+ϵrB=\epsilon_s+\epsilon_r.
  • Public group assignment C∈Δcn×cC\in\Delta_c^{n\times c}: Classifier fψf_\psi trained only on public (X,YL)(X,Y_{\mathcal{L}}) (no AA) outputs C=softmax(fψ(X))C=\text{softmax}(f_\psi(X)).
  • Client summary (Yi,Ri)(Y_i,R_i) & degree did_i: Node ii clips its neighbors to LL edges (A~\tilde A, d~i=∑jA~ij≤L\tilde d_i=\sum_j\tilde A_{ij}\le L), forms hi=∑jA~ijCj,:∈Rch_i=\sum_j\tilde A_{ij}C_{j,:}\in\mathbb{R}^c, and releases:
    1. Noisy group profile Yi=hi+Lap((L/ϵs)1c)Y_i=h_i+\text{Lap}((L/\epsilon_s)\mathbf{1}_c) (Δ1=L\Delta_1=L as ∣Cj,:∣1=1\\|C_{j,:}\\|_1=1), stacked into Y∈Rn×cY\in\mathbb{R}^{n\times c}, giving clipped degree di=max⁡(1⊤Yi,0)d_i=\max(\mathbf{1}^\top Y_i,0).
    2. Edge-RR matrix R∈0,1n×nR\in\\{0,1\\}^{n\times n}: Under two-endpoint RR with flip rate p=(1+eϵr)−1p=(1+e^{\epsilon_r})^{-1}, (i,j)(i,j) is kept iff both report 11 (p11=(1−p)2p_{11}=(1-p)^2 if A~ij=1\tilde A_{ij}=1; p00=p2p_{00}=p^2 if A~ij=0\tilde A_{ij}=0).
  • Group operator G(Y,C)\mathcal{G}(Y,C) & QgQ_g: H^=[Y]+∈R+n×c\hat H=[Y]_+\in\mathbb{R}_+^{n\times c}, S^=C⊤H^∈R+c×c\hat S=C^\top\hat H\in\mathbb{R}_+^{c\times c}, Θ=diag(S^1+ε)−1/2S^diag(S^⊤1+ε)−1/2\Theta=\text{diag}(\hat S\mathbf{1}+\varepsilon)^{-1/2}\hat S\text{diag}(\hat S^\top\mathbf{1}+\varepsilon)^{-1/2}, and Qg=Sym(H^ΘC⊤)Q_g=\text{Sym}(\hat H\Theta C^\top) with Sym(M)=12(M+M⊤)\text{Sym}(M)=\frac{1}{2}(M+M^\top).
  • Local prior WW, factors VV, and kernel TT:
    • From public (X,C)(X,C), we form top-kk cosine graph W~f\tilde W_f and JSD graph W~g\tilde W_g, blend W~=(1−λJ)W~f+λJW~g\tilde W=(1-\lambda_J)\tilde W_f+\lambda_J\tilde W_g, and row-normalize W=DW~−1W~W=D_{\tilde W}^{-1}\tilde W (W1=1,Wii=0W\mathbf{1}=\mathbf{1}, W_{ii}=0).
    • If W≈UV⊤W\approx UV^\top (U,V∈Rn×rU,V\in\mathbb{R}^{n\times r}), node ii may release zi=∑jA~ijVj,:+ξiz_i=\sum_j\tilde A_{ij}V_{j,:}+\xi_i (ϵl\epsilon_l).
    • Three branches of TT: (i) Factorized: T0=Sym([Z]+V⊤)T_0=\text{Sym}([Z]_+V^\top); (ii) Default (ϵl=0\epsilon_l=0): T0=Sym(diag(d)W)T_0=\text{Sym}(\text{diag}(d)W); (iii) Calibration: T=γT0T=\gamma T_0 with γ=(1⊤Qg1)/(1⊤T01+ε)\gamma=(\mathbf{1}^\top Q_g\mathbf{1})/(\mathbf{1}^\top T_0\mathbf{1}+\varepsilon) so 1⊤T1=1⊤Qg1\mathbf{1}^\top T\mathbf{1}=\mathbf{1}^\top Q_g\mathbf{1} (GLP), or γ=1\gamma=1 (Uncal).
  • Blended prior QαQ_\alpha, scale λij\lambda_{ij}, and A^\hat A: Qα=(1−α)Qg+αTQ_\alpha=(1-\alpha)Q_g+\alpha T; si=clip(round(di),kmin⁡,kmax⁡)s_i=\text{clip}(\text{round}(d_i),k_{\min},k_{\max}), M=12∑isiM=\frac{1}{2}\sum_i s_i, λij=M(Qα)ij/∑u<v(Qα)uv\lambda_{ij}=M(Q_\alpha)_{ij}/\sum_{u < v}(Q_\alpha)_{uv}, and Fλ(x)=1−e−λxF_\lambda(x)=1-e^{-\lambda x} give (Gα)ij=Fλij((Qα)ij)(G_\alpha)_{ij}=F_{\lambda_{ij}}((Q_\alpha)_{ij}). Post-RR takes row-wise top-sis_i of S=(1−β)Gα+βRS=(1-\beta)G_\alpha+\beta R; pre-RR sparsifies Gα→A^pG_\alpha\to\hat A_p and R→A^rR\to\hat A_r first and blends P~(A^p)X\tilde P(\hat A_p)X with P~(A^r)X\tilde P(\hat A_r)X in O(nc+nk)O(nc+nk) memory.

2. Algorithmic Workflow (W2, Q2)

Algorithm 1 (Section 3.1): (1) Public Prior: Train fψ(X,YL)→Cf_\psi(X,Y_{\mathcal{L}})\to C; build top-kk row-normalized WW. (2) Client LDP: Node ii clips degree to LL and sends Yi=hi+Lap((L/ϵs)1c)Y_i=h_i+\text{Lap}((L/\epsilon_s)\mathbf{1}_c) and RR row Ri,:R_{i,:} (ϵr\epsilon_r). (3) Server Calibration: Compute H^=[Y]+\hat H=[Y]_+, di=max⁡(1⊤Yi,0)d_i=\max(\mathbf{1}^\top Y_i,0), Qg=Sym(H^ΘC⊤)Q_g=\text{Sym}(\hat H\Theta C^\top), T=γSym(diag(d)W)T=\gamma\text{Sym}(\text{diag}(d)W), Qα=(1−α)Qg+αTQ_\alpha=(1-\alpha)Q_g+\alpha T, and (Gα)ij=1−e−λij(Qα)ij(G_\alpha)_{ij}=1-e^{-\lambda_{ij}(Q_\alpha)_{ij}}. (4) Sparsification & Training: Form A^\hat A via post-RR or pre-RR top-sis_i pooling; train GNN on (A^,X,YL)(\hat A,X,Y_{\mathcal{L}}).

3. Theoretical Intuitions & Proof Sketches (W4, Q3)

  • Theorem 1: By Δ1≤L\Delta_1\le L, composition, and post-processing, (Y,R)(Y,R) is (ϵs+ϵr)(\epsilon_s+\epsilon_r)-edge-LDP.
  • Lemma 1: Pg=Dg−1QgP_g=D_g^{-1}Q_g has rank ≤c\le c and vanishes on ker⁡(C⊤)\ker(C^\top), whereas Pα=Dα−1QαP_\alpha=D_\alpha^{-1}Q_\alpha acts on u∈ker⁡(C⊤)u\in\ker(C^\top) via αDα−1(T−Qg)u\alpha D_\alpha^{-1}(T-Q_g)u, recovering intra-class links from WW.
  • Proposition 1: For S(P)=EE[Fλ(Pij)]−τEEc[Fλ(Pij)]S(P)=\mathbb{E}_E[F_\lambda(P_{ij})]-\tau\mathbb{E}_{E^c}[F_\lambda(P_{ij})], S′(0)=⟨∇S(Qg),T−Qg⟩>0S'(0)=\langle\nabla S(Q_g),T-Q_g\rangle > 0 when 1⊤(T−Qg)1=0\mathbf{1}^\top(T-Q_g)\mathbf{1}=0 and T−QgT-Q_g aligns with intra-group edges, giving S(Qα)>S(Qg)S(Q_\alpha) > S(Q_g) for α∈(0,α0)\alpha\in(0,\alpha_0).
  • Proposition 2: Taylor expansion around dˉi=E[di]\bar d_i=\mathbb{E}[d_i] with Var(di)=2c(L/ϵs)2\text{Var}(d_i)=2c(L/\epsilon_s)^2 and ψ′′<0\psi'' < 0 gives penalty O(α2c(L/ϵs)2∣Wi,:∣22)O(\alpha^2 c(L/\epsilon_s)^2\\|W_{i,:}\\|_2^2) at small ϵs\epsilon_s, motivating moderate α\alpha and degree-normalized propagation.

I thank the authors for their effort to answer our questions and concerns. The response partially addresses my concerns and questions.

I have some following questions for the author regarding their responses:

Regarding the advantage of GLP, by incorporating the similarity of the nodes and the membership CC, GLP can achieve better performance compared to existing work. Then, by observing XX and YY, can the adversary infer AA? Can you provide some analysis to see whether GLP can defend against this type of attack?

Why does the client need to clip the number of neighbors to LL? If it's to reduce the sensitivity of AA, then how does this hyperparameter affect the performance of GLP?

What is ϵ\epsilon in the group operator? Does it contribute to the total privacy budget BB? Can you explain why this process of G(Y,C)G(Y, C) captures the group property?

In Section 2 of your response, you mentioned Algorithm 1 (Section 3.1). But I cannot find any Section 3.1 in the main body. Please clarify whether this algorithm is for the whole process of GLP or just a part of it.

From Section 3 of your response, I agree with the proof of Theorem 1. But it's trivial since it's been established in previous work. Can you further analyze the privacy risk/privacy budget of the group prior and local similarity toward the total privacy budget? For the proofs of Lemma 1 and Proposition 1, can you explain how your response supports the claims in these two lemmas and this proposition?

We thank Reviewer ikry for the follow-up. We clarify the notation and address all five questions below.

1. Can GLP reveal private edges?

In Sec. 3 (Eq. 1) and App. B.1, WW is the top-kk cosine graph of public XX, and CC comes from an MLP trained on public (X,YL)(X,Y_{\mathcal L}). Neither accesses AA or consumes privacy budget. For an adversary who knows the public inputs and all other edges, Theorem 1 (App. A.3) and post-processing bound the likelihood ratio of (Y,R)(Y,R) and any derived GLP output by eBe^B in either direction, where B=2(εs+εr)=2eB=2(\varepsilon_s+\varepsilon_r)=2e. Given this side information, let qq be the prior probability that Aij=1A_{ij}=1 and pp the posterior. Then p1−p≤eBq1−q,p≤eBq1+(eB−1)q.\frac{p}{1-p}\le e^B\frac{q}{1-q},\qquad p\le\frac{e^Bq}{1+(e^B-1)q}. Any link detector also satisfies TPR≤min⁡(1,eBFPR)\mathrm{TPR}\le\min(1,e^B\mathrm{FPR}).

2. What is clipped, and why?

Our earlier reference to client-side neighbor clipping was a notation error. In Eq. 1, toggling i,j\\{i,j\\} changes row ii of ACAC by ±Cj,:\pm C_{j,:} and row jj by ±Ci,:\pm C_{i,:}. Since ∣Cj,:∣1=1\\|C_{j,:}\\|_1=1, row sensitivity is 11 and joint sensitivity is 22, regardless of degree. The mechanism therefore avoids truncation bias from dropping neighbors. The clipping in App. B.2 (Eq. 27) is server-side post-processing: di=clip⁡((Y1)i,1,n)d_i=\operatorname{clip}((Y\mathbf{1})_i,1,n) keeps noisy degrees positive for the group normalization, and Vij=min⁡(bWij,0.99)V_{ij}=\min(bW_{ij},0.99) caps local scores.

3. What does εs\varepsilon_s do in G(Y,C)\mathcal G(Y,C)?

The ε\varepsilon in our earlier normalization was a notation error. The known budget εs=0.1e\varepsilon_s=0.1e enters the variance weights in App. B.2 (Eqs. 28–37). From the released Y=AC+ZY=AC+Z, compute ga=∑iCiag_a=\sum_i C_{ia}, H=C⊤YH=C^\top Y, and va=2ga/εs2v_a=2g_a/\varepsilon_s^2. Then H^ab=Hab/va+Hba/vbva−1+vb−1,U=C⊤diag⁡(d)C,Θ=U−1H^U−1.\widehat H_{ab}=\frac{H_{ab}/v_a+H_{ba}/v_b}{v_a^{-1}+v_b^{-1}},\quad U=C^\top\operatorname{diag}(d)C,\quad \Theta=U^{-1}\widehat H U^{-1}. Finally, (Qg)ij=clip⁡(diCi,:ΘCj,:⊤dj,0,1)(Q_g)_{ij}=\operatorname{clip}(d_i C_{i,:}\Theta C_{j,:}^\top d_j,0,1). Under the degree-corrected block model, E[H]=C⊤AC≈UΘU\mathbb E[H]=C^\top AC\approx U\Theta U, which motivates the normalization for estimating group affinities. These steps are deterministic given (Y,C,εs)(Y,C,\varepsilon_s) and cost no additional privacy budget.

4. Where is Section 3.1, and what does Algorithm 1 cover?

Our reference to “Section 3.1” meant the opening of Sec. 3, which uses unnumbered paragraph headings. Algorithm 1 covers the entire pipeline: build public (C,W)(C,W), collect (Y,R)(Y,R), compute Qg=G(Y,C)Q_g=\mathcal G(Y,C) and M=∑i≠j(Qg)ijM=\sum_{i\ne j}(Q_g)_{ij}, and construct TT (Eqs. 1–3). Then pool Qα=(1−α)Qg+αTQ_\alpha=(1-\alpha)Q_g+\alpha T, update Pij=Fλij((Qα)ij)P_{ij}=F_{\lambda_{ij}}((Q_\alpha)_{ij}) with λij=e2εr(Rij+Rji−1)\lambda_{ij}=e^{2\varepsilon_r(R_{ij}+R_{ji}-1)}, and train with S(P)=D−1/2(P+I)D−1/2S(P)=D^{-1/2}(P+I)D^{-1/2} (Eqs. 4–6).

5. Budget allocation and proofs

Budget. Public (C,W)(C,W) cost 00. The group report YY costs 2εs=0.1B2\varepsilon_s=0.1B for one undirected edge. Computing QgQ_g from YY and building TT from public WW and the inferred mass MM cost 00 additional budget. The two RR reports cost 2εr=0.9B2\varepsilon_r=0.9B, for a total of BB.

Lemma 1 (App. A.1). In Eq. 3, Tij=ρ+a(Vij−vˉ)T_{ij}=\rho+a(V_{ij}-\bar v). For 0<M<K0\lt M\lt K, the capped mass is monotone in bb, so we choose bb with ∑i≠jVij=M\sum_{i\ne j}V_{ij}=M and get Tij=0.9Vij+0.1ρT_{ij}=0.9V_{ij}+0.1\rho. For K≤M<NK\le M\lt N, Vij=u1Wij>0V_{ij}=u\mathbf{1}\\{W_{ij}\gt 0\\}, and a=min⁡0.9,(1−ρ)/(max⁡V−vˉ)a=\min\\{0.9,(1-\rho)/(\max V-\bar v)\\} keeps TijT_{ij} in [0,1][0,1]. Centering VV preserves the total mass MM in both regimes.

Proposition 1 (Sec. 4, Eq. 7; App. A.2). For symmetric zero-diagonal HH with HC=0HC=0, C1=1C\mathbf{1}=\mathbf{1} gives H1=0H\mathbf{1}=0. Thus (A+tH)C=AC(A+tH)C=AC and DA+tH=DAD_{A+tH}=D_A, yet the propagated features can change by tDA−1/2HDA−1/2XtD_A^{-1/2}HD_A^{-1/2}X. This explains why fixing group counts and degrees leaves propagation underdetermined.

We sincerely thank Reviewer ikry for reading our response and additional experiments so carefully. As the discussion period is drawing to a close, if your main concerns have been resolved, we would be deeply grateful if you might consider updating your overall rating to reflect the strengthened manuscript. Thank you again for your constructive feedback and time!

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response to Area Chair and All Reviewers

We sincerely thank the Area Chair and all three reviewers (ikry, AEPy, kvdy) for their constructive, detailed, and insightful feedback. We are encouraged that the reviewers recognized the practical relevance and clarity of our motivation (ikry, AEPy), our zero-extra-privacy-cost postprocessing design and efficiency (ikry, kvdy), our rigorous evaluation protocol with frozen hyperparameters across datasets/splits (AEPy, kvdy), and our diagnostic permutation and component controls (AEPy, kvdy).

Below we summarize how we have addressed all major concerns through new controlled experiments, complete archived reference & runtime tables, and substantial manuscript revisions:

  1. Self-Contained Mathematical Exposition, Step-by-Step Pseudocode, and Proof Roadmaps (Addressing Reviewer ikry W1–W2 & Q1):

    • In Section 3 of the revised manuscript, we have incorporated explicit closed-form definitions for all objects (XX, CC, G(Y,C)\mathcal{G}(Y,C), QgQ_g, WW, VV, TT across all three capacity regimes, and FλF_\lambda) and added a complete step-by-step pseudocode table (Algorithm 1).
    • In Section 4, we expanded the proof intuition and mechanistic roadmaps for Theorem 1, Lemma 1, and Propositions 1–2 while referencing the full step-by-step derivations in Appendix A.
  2. New 40-Run Cora Ablation Decomposing Local Neighborhood Injection vs. Report-Derived Mass Calibration (Uncal vs. GLP) and Comparison with HoGS (Addressing Reviewer AEPy W1, Q1 & Reviewer kvdy W1, Q1–Q2):

    • We conducted a new 40-run controlled GCN ablation on an independent stratified Cora split (seed=20261114, n=5n=5 paired runs per arm) comparing Group-only (QgQ_g), Uncal (0.5Qg+0.5W0.5 Q_g + 0.5 W, uncalibrated cosine similarity without report mass MM), and GLP (0.5Qg+0.5T0.5 Q_g + 0.5 T), alongside zero-privacy-cost (B=0B=0) Public W + GCN and Feature-only MLP references.
    • Key Finding: Injecting the local neighborhood (Uncal vs. Group-only) drives the primary gain at low budget (B=4B=4: +3.28 pp Acc / +4.25 pp Macro-F1), while report-derived mass calibration (GLP vs. Uncal) provides an additional +0.62 pp Acc / +0.50 pp Macro-F1 gain at B=8B=8 where sharp two-endpoint RR likelihood ratios (λij≈1,339\lambda_{ij} \approx 1,339) interact nonlinearly with the prior scale via (Gα)ij(G_\alpha)_{ij} (Proposition 2), and is structurally necessary on denser graphs such as Photo where inferred mass exceeds support capacity (M≥KM \ge K, Table 11 / Table 15).
    • We also added a dedicated comparison with HoGS (Xu et al., 2026) in Section 2 and in our responses below.
  3. Complete Zero-Privacy-Cost (B=0) Public W Baselines Across All Datasets, Backbones, and Splits (Addressing Reviewer kvdy W1, Q1):

    • We added the complete Public W (B=0B=0, GNN trained directly on S(W)S(W) with no private reports) reference rows across all 4 datasets (Cora, CiteSeer, Photo, PubMed), both backbones (GPR, GCN), and both primary and confirmation splits in Tables 1, 4–7, and 8–9.
    • GLP outperforms Public W at all evaluated budgets on Photo (up to +5.05 pp) and PubMed (up to +4.38 pp), and on Cora at B≥6B \ge 6 on the primary split (up to +13.63 pp) and already at B=4B=4 on the confirmatory GCN split (70.43% vs. 69.60%), cleanly delineating when private edge reports improve over public side information alone.
  4. Measured Stage-Level Runtime & Peak GPU Memory Overhead (Addressing Reviewer kvdy W2, Q3):

    • We added the complete stage-by-stage wall-clock runtime and peak GPU memory breakdown on PubMed (n=19,717n=19,717, RTX 5090, Table 12 / tab:pubmed-cost-full), showing that one-time public WW construction takes 1.62 s / 4.76 GiB, shared HPGR+GLP reconstruction takes 5.11 s / 11.61 GiB (lower peak memory than Blink's 13.10 GiB and SL-LPGL's 13.18 GiB), and downstream GNN training time/memory is identical to HPGR (14.20 s vs. 14.18 s at 1.55 GiB for GPR; 3.78 s vs. 3.82 s at 1.51 GiB for GCN). We also detail an exact blockwise O(nBblk+nk)O(n B_{\mathrm{blk}} + nk) memory formulation.
  5. Theoretical Bridge, Heterophilic Graph Analysis, and CiteSeer RR False-Positive / Budget Analysis (Addressing Reviewer AEPy W2–W3, Q2 & Reviewer kvdy Q4):

    • We explicitly connected Propositions 1–2 to our design choices in Section 4, analyzed how GLP's components (QgQ_g, WW, and GPR) behave under heterophily, and provided a quantitative false-positive and budget-allocation analysis explaining the negative RR contribution on ultra-sparse CiteSeer.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.