- 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
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!
Response to Reviewer kvdy
We thank Reviewer
kvdyfor the insightful review. Below we address all four points with new experiments (Public Wat B=0,Uncalvs.GLP, PubMed profiling, and CiteSeer RR noise analysis) in Sections 3–5.1. Public-Only Baseline (
Public Wat B=0) & Three Privacy-Utility Regimes (W1, Q1)We trained GCN/GPR-GNN on the public top-k graph W at B=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):Public W(0)GLP(4)GLP(6)GLP(8)GLP(12)Original(∞)(Confirmation
Tables 8–9& Supplemental Splitseed=20261114:MLP59.29±0.90%,Public W+GCN69.07±1.10%,GLP66.91% at B=4 / 77.28% at B=8; same ordering.)This reveals three privacy-utility regimes (Section 5.2):
OriginalbeatsPublic Wby +15.2 to +17.0 pp.HPGR+GLPgrows monotonically with B, gaining +9.56 pp (GCN) and +12.35 pp (GPR) overPublic Wand beating all DP baselines by up to +11.6 pp.Originalis +2.1 to +3.1 pp abovePublic W.HPGR+GLP (GCN)beatsPublic Wat all B (+1.41 to +1.69 pp), whileGPRcrosses the RR noise threshold at B=12 (72.05%, +2.74 pp overPublic W).Public Wis within 1.15 to 3.52 pp ofOriginal). While DP baselines drop -4 to -46 pp under RR noise,GLPanchors to W at low B and gains on PubMed GPR (83.55% → 84.20% at B=12).2. HoGS Relationship &
Uncalvs.GLPAblation (W2, Q2)Sections 2, 5.4): HoGS targets subgroup fairness via group counters, whereasHPGR+GLPinjects local prior T on ker(C⊤) with pre-RR pooling, beatingGroup-only(Qg) by +1.25 to +6.21 pp on Cora/CiteSeer (Tables 1, 11, 13, 17).Uncalvs.GLP(Table 11): On Cora GCN,Group-only→Uncal→GLPis 72.24% → 75.52% → 75.47% (B=4) and 74.24% → 77.63% → 78.25% (B=8, +4.01 pp overGroup-only, +0.62 pp overUncal). On denser Photo (Tables 11, 15), where M≥nnz(T0),Uncalsuffers top-M saturation whileGLPpreserves calibration.3. Runtime, Memory, and Complexity on PubMed (W3, Q3)
On PubMed (n=19,717,B=8, RTX 5090,
Table 12): Building W takes 1.62 s (4.76 GiB); sharedHPGR+GLPreconstruction takes 5.11 s (11.61 GiB, belowBlink13.10 GiB/SL13.18 GiB). Sparse A^ gives zero training overhead overOriginal: 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-si over row blocks of size Bblk uses O(nBblk+nk) memory; pre-RR pooling uses QgX=21(H^(Θ(C⊤X))+C(Θ⊤(H^⊤X))) in O(nc+nk) time/memory (Section 3.4).4. Why CiteSeer Gains Are Muted at B∈[4,8] (W4, Q4)
CiteSeer (n=3,327, (2n)≈5.53×106 pairs) has ∣E∣=4,552 undirected edges (dˉ=2.73). Under two-endpoint RR (ϵr=0.3B), false-positive rate p11=(1+eϵr)−2 yields NFP≈(2n)p11 false edges (Section 5.3): 297,000 (65×∣E∣) at B=4, 38,700 (8.5×∣E∣) at B=8, and 3,920 (<∣E∣) at B=12 (where GPR jumps to 72.05%). Our No-RR control (ϵr=0,β=0,
Tables 13, 17) confirms this: removing RR on CiteSeer improves accuracy by +1.52 pp (B=4) and +1.87 pp (B=8), while reallocating ϵr→ϵs cuts degree Laplace variance Var(di)=2c(L/ϵs)2 by >2× (Prop. 2).