Pith. sign in

REVIEW 4 major objections 4 minor 76 references

Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy

T0 review · 4 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Under edge local differential privacy, per-pair common-neighbor counts in bipartite graphs can be estimated with unbiased estimators whose error is independent of graph size.

desk verdict First edge-LDP per-pair common-neighbor estimator for bipartite graphs, sound core derivations, but MultiR-DS optimality is proven only for an oracle objective; referee-worthy. read the letter →

arxiv 2502.01904 v1 pith:LSNESN4J submitted 2025-02-04 cs.DB

Yizhang He , Kai Wang , Wenjie Zhang , Xuemin Lin , Ying Zhang This is my paper · ORCID
classification cs.DB
keywords commonneighborhoodestimationbipartitegraphsedgelocaldifferentialprivacyrandomizedresponseLaplacemechanismunbiasedL2lossdegreeimbalance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Two users of a platform represented as a bipartite graph often want to know how many contacts, purchases, or page-likes they share, but revealing the shared items also reveals their private edge lists. This paper asks whether that count can be estimated while each vertex only sends locally perturbed data, under edge local differential privacy, and answers yes. The simplest estimator, OneR, debiases randomized response so that overcounting on the dense noisy graph cancels out. A multi-round estimator, MultiR-SS, cuts the candidate pool down to the neighbors of one query vertex, making the error depend on degrees rather than the total number of vertices. A final estimator, MultiR-DS, averages two single-source views with a privacy-budget split tuned per query pair, and the paper proves the optimized average is never worse than either view alone.

What carries the argument

The load-bearing object is the debiased adjacency entry $\varphi(i,j) = (A'[i,j] - p)/(1 - 2p)$, where $A'[i,j]$ is one randomized-response flip of the entry and $p = 1/(1+e^{\varepsilon})$ is the flip probability. Because $E[\varphi(i,j)] = A[i,j]$, summing $\varphi$ over the right index set gives an unbiased estimator for the common-neighbor count. MultiR-SS builds $f_u = \sum_{v \in N(u,G)} \varphi(v,w)$ and adds Laplace noise calibrated to the global sensitivity $(1-p)/(1-2p)$; MultiR-DS forms $f^* = \alpha f_u + (1-\alpha) f_w$ and minimizes the closed-form L2 loss $F(\varepsilon_1, \alpha)$ over the randomized-response budget $\varepsilon_1$ and the weighting $\alpha$ using Newton's method. This machinery converts a privacy problem into a variance-reduction problem over a candidate pool that shrinks from all vertices on the opposite layer to the two query neighborhoods.

What would settle it

Run MultiR-DS and MultiR-SS on a bipartite graph with a query pair whose true degrees are strongly imbalanced, using the paper's default $\varepsilon_0 = 0.05\varepsilon$ over many repetitions; if MultiR-DS's mean absolute error exceeds MultiR-SS's, the degree-estimation round can break the claimed dominance.

Watch

Extended reading notes

Core claim

The paper's central claim is that for two vertices $u$ and $w$ on the same layer of a bipartite graph, the common-neighbor count $C_2(u,w) = |N(u,G) \cap N(w,G)|$ can be estimated under edge LDP without any term in the expected L2 loss that depends on the opposite-layer size. Theorem 3 gives OneR, an unbiased one-round estimator that debiases randomized-response flips. Theorem 6 gives MultiR-SS, whose loss is $O(e^{\varepsilon_1}/(1-e^{\varepsilon_1})^2 (d_u + 2 e^{\varepsilon_1}/\varepsilon_2^2))$. Theorems 8--10 give MultiR-DS, a weighted average $f^* = \alpha f_u + (1-\alpha) f_w$ whose minimized loss is no larger than either single-source loss, and prove the protocol satisfies $\varepsilon$-edge LDP. The paper reports experiments on 15 real bipartite graphs where these multi-round estimators reduce mean absolute error by up to four orders of magnitude relative to the naive noisy-graph count and two orders relative to OneR at $\varepsilon = 2$.

Load-bearing premise

The practical optimality of MultiR-DS rests on the assumption that the optimizer's input, Laplace-noised estimates of the two query degrees, is close enough to the true degrees that the chosen budget split and weighting are near-optimal; the proof of Theorem 9 uses the true degrees.

Editorial extensions

If this is right

  • OneR removes the systematic overcounting of the Naive approach: its expected L2 loss is $O(n_1 e^{2\varepsilon}/(1-e^{\varepsilon})^4)$, compared with $O(n_1^2 e^{4\varepsilon}/(1+e^{\varepsilon})^4)$ for counting on the noisy graph.
  • MultiR-SS achieves expected L2 loss $O(e^{\varepsilon_1}/(1-e^{\varepsilon_1})^2 (d_u + 2 e^{\varepsilon_1}/\varepsilon_2^2))$, so the error no longer grows with the number of vertices on the opposite layer.
  • MultiR-DS's optimized weighted average has minimized L2 loss no larger than either single-source estimator, which keeps the error small even when one query vertex has far more neighbors than the other.
  • All three estimators satisfy $\varepsilon$-edge LDP; MultiR-DS spends its budget in three rounds, allocating $\varepsilon_0$ to degree estimation, $\varepsilon_1$ to noisy graph construction, and the remainder to Laplace noise.
  • Because common-neighbor counts are the atomic statistic behind vertex similarity and biclique counting, the estimators open a path to those tasks under edge LDP.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The debiasing formula $\varphi(i,j)$ applies to any count written as a sum of products of adjacency entries, so the same randomized-response correction could be lifted to Jaccard similarity, clustering coefficients, or wedge-based motif counts on bipartite graphs; the paper does not pursue those extensions.
  • MultiR-DS's degree-estimation round is a hidden cost: a deployment could precompute noisy degrees once and reuse them across many query pairs, amortizing the $\varepsilon_0$ budget, an option the paper does not discuss.
  • A natural stress test is to replace Newton's method with a coarse grid search over $\varepsilon_1$ and $\alpha$; if grid search matches or beats the estimated-degree optimizer on the same datasets, the optimality claim would rest less on accurate degree estimates.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The manuscript studies the problem of estimating the number of common neighbors C2(u,w) of two same-layer vertices in a bipartite graph under edge local differential privacy (edge LDP). It proposes the first edge-LDP estimators for this per-pair query: a one-round estimator OneR that debiases randomized response (Theorem 3, Eq. 2); a two-round single-source estimator MultiR-SS that combines a noisy graph built with randomized response and a Laplace-noised local sum (Theorem 6); and a three-round double-source estimator MultiR-DS that takes a weighted average of the two single-source estimators and adaptively allocates the privacy budget (Theorem 8). The paper also gives a Naive baseline, proves unbiasedness and expected L2-loss bounds, verifies ε-edge LDP by composition, and reports experiments on 15 KONECT datasets with up to 327M edges.

Significance. If the results hold as stated, this is a useful contribution: per-pair common-neighbor queries are basic building blocks for similarity, biclique counting, and motif analysis, and the paper correctly identifies that previous edge-LDP work has not addressed this specific query. The derivations supporting OneR and MultiR-SS are clean and check out: the debiased randomized-response product is unbiased, the sensitivity (1-p)/(1-2p) of the single-source estimator is correct, and the variance formulas in Theorems 6 and 8 follow from the stated independence structure. The paper is also strong on breadth, with experiments over 15 datasets, a 300M-edge graph, and useful ablations (MultiR-DS-Basic, MultiR-DS*, degree-imbalance sweeps). The principal weakness is that the theoretical optimality claim for MultiR-DS is proven for an oracle objective that uses exact degrees and the full privacy budget, whereas Algorithm 4 pays an ε0 = 0.05ε overhead and plugs noisy degree estimates into the optimizer. This gap tempers the paper's strongest claim, but the OneR and MultiR-SS contributions remain solid.

major comments (4)
  1. [Section 4.2, Algorithm 4, Theorem 9] The dominance claim for MultiR-DS is proven for an oracle version of the estimator. Theorem 8's objective F(ε1,α) assumes the budget is split as ε = ε1 + ε2 and uses exact degrees d_u, d_w; Theorem 9 then minimizes that oracle objective. Algorithm 4, however, spends ε0 = 0.05ε on degree estimation (line 1), sets ε2 = ε − ε0 − ε1 (line 13), and plugs Laplace-noised degree estimates from lines 2-5 into the optimization of line 6. Consequently Theorem 9 does not bound the realized L2 loss of Algorithm 4 and does not establish that MultiR-DS beats MultiR-SS. The missing budget shrinks ε2, increasing the Laplacian term in Theorem 8 by roughly 1/(1−ε0/ε)^2, which is already about 10.8% for ε0 = 0.05ε, and the noisy degree estimates can in principle steer the optimizer to parameters whose realized loss exceeds that of MultiR-SS with its default split. The paper should either analyze an objective that includes the ε0 cost and the degree-estimation error, or explicitly reposition MultiR-DS's theoretical claim as heuristic and support it with error-barred experiments.
  2. [Section 4.2, Newton's method paragraph] The assertion that F(ε1,α) reaches its global minimum if and only if its partial derivatives ∂F/∂α and ∂F/∂ε1 vanish is not established; stationarity is only a necessary condition for an interior global minimum, and no convexity or unimodality proof is given. Algorithm 4 line 6 also does not specify the initialization, step size, or termination criterion of Newton's method. Since Theorem 9 is a statement about the global minimum, the current text does not guarantee that the parameters found by Algorithm 4 realize the promised loss. Please provide a proof of global optimality or use a certified optimization procedure (e.g., a coarse grid scan followed by local refinement with a documented stopping rule).
  3. [Theorem 1 and Theorem 4 statements] The theorem statements do not match the proofs and Table 3. Theorem 1 states the expected L2 loss of Naive is O(n1^2/(1+e^ε)^4), but its proof and Table 3 give O(n1^2 e^{4ε}/(1+e^ε)^4). Theorem 4 states the L2 loss of OneR is O(n1 e^ε/(1−e^ε)^4), but its proof and Table 3 give O(n1 e^{2ε}/(1−e^ε)^4). The missing e^{4ε} and e^{2ε} factors make the stated dependence on ε incorrect and should be corrected.
  4. [Algorithm 3, round 1] As printed, the pseudocode of MultiR-SS perturbs only A'[u,j] for j in the opposite layer and never applies randomized response to w's neighbor list, although the surrounding text and Example 3 say both u and w are randomized. Taken literally, the algorithm does not provide ε1-edge LDP for w, and the estimator f_u uses unperturbed values of A[v,w]. The listing needs the missing loop over i ∈ {u,w}; if this is a formatting omission, please correct it in the final version.
minor comments (4)
  1. [Algorithm 4, output] The output line of Algorithm 4 says "return e𝑓𝑢(𝑢,𝑤)", but the algorithm should return the weighted average α e𝑓_u + (1−α) e𝑓_w; fix this typo.
  2. [Section 5.1, experimental reporting] The figures report mean absolute error as a single number for each dataset without error bars or standard errors, despite the fact that the 100 sampled vertex pairs and the algorithm randomness make MAE a random quantity. Please report error bars or a variance measure, particularly for the MultiR-DS versus MultiR-SS comparison.
  3. [Algorithm 4, lines 4-5] Line 4 obtains the average vertex degree d' from noisy degree reports, but the pseudocode does not show the collection of those reports from all vertices in the layer or specify the privacy budget used for them. Please make this explicit so the listing matches Theorem 10 and the communication-cost analysis.
  4. [Table 3] The MultiR-DS L2-loss entry is missing parentheses around the term (α^2 + (1−α)^2)/ε2^2; as printed, the formula is ambiguous. The table title also says "time costs" while the table lists L2 loss and communication cost as well.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the estimators and loss bounds follow algebraically from randomized-response debiasing and Laplace sensitivity, with no fitted constants.

full rationale

The derivation chain is self-contained. OneR inverts the randomized-response bias by solving E(A') = A + p(1-2A), giving phi = (A'-p)/(1-2p) as an unbiased estimator of A, and then sums phi(u,v)phi(v,w) over the opposite layer; Theorems 3 and 4 bound the L2 loss directly as the variance of these shifted Bernoulli variables. MultiR-SS restricts the sum to N(u,G), applies Laplace noise with sensitivity (1-p)/(1-2p), and its L2 loss in Theorem 6 is the sum of the Bernoulli variance du*p(1-p)/(1-2p)^2 and the Laplace variance 2(1-p)^2/((1-2p)^2 eps2^2). MultiR-DS takes a weighted average f* = alpha e_fu + (1-alpha)e_fw; Theorem 8 derives its variance from the independence of the two estimators, and Theorem 9 observes that alpha=1 gives e_fu and alpha=0 gives e_fw, so the minimized loss is no larger than either single-source loss. This is a mathematical special-case inequality, not a fitted input renamed as a prediction: no parameter is tuned to experimental MAE, and the alpha/eps1 optimizer minimizes the analytically derived variance formula, even though Algorithm 4 uses noisy degree estimates and an eps0 = 0.05 eps overhead. The latter is a correctness/robustness gap between the oracle objective and the realized algorithm, not circularity. Citations to randomized response and Laplace mechanisms are standard external foundations; self-citations in related work are contextual and not load-bearing.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

No invented entities. The estimators are assembled from standard randomized-response and Laplace primitives plus the two-round framework of Imola et al. [18], which is credited. The hand-set quantities are the degree-estimation budget eps0 = 0.05 eps (Algorithm 4, line 1), the even eps1 = eps2 split used for the MultiR-SS baseline (Algorithm 3, line 1), and the unspecified Newton settings. The least-supported premise is the global-minimum claim for F(eps1, alpha) and the use of Laplace-noised degrees inside that optimization; both are asserted rather than proven.

free parameters (3)
  • eps0 fraction = 0.05 * eps
    Algorithm 4 line 1: the privacy budget for the degree-estimation round is fixed at 5% of eps by hand; no derivation or sensitivity analysis for this choice is given.
  • eps1 even split for MultiR-SS = eps / 2
    Algorithm 3 line 1: the single-source baseline splits eps evenly between RR and Laplace; the text admits an optimized split would outperform it, so the baseline embeds a hand-chosen split.
  • Newton method settings = unspecified
    Section 4.2: initialization, step count, and stopping criterion for Newton's method on F(eps1, alpha) are not given; results depend on unstated numerical settings.
assumptions (6)
  • standard math Randomized response with flip probability 1/(1+e^eps) satisfies eps-edge LDP.
    Used in all algorithms (Sec. 2.2); standard result credited to Warner 1965 and Imola et al.
  • standard math Sequential and parallel composition of edge-LDP mechanisms, and post-processing immunity.
    Invoked in Theorems 2, 5, 7, 10 (Sec. 2.2 and Sec. 4).
  • standard math Laplace mechanism calibrated by global sensitivity provides eps-LDP.
    Definition 5; used for degree reports and single-source estimator releases.
  • domain assumption The two-round template (RR noisy graph, then Laplace on a local estimator) composes to eps1+eps2 edge-LDP.
    From Imola et al. [18]; the paper applies it to f_u and f_w, with the round-3 argument glossing over that u's RR output appears inside f_w.
  • standard math Bias-variance decomposition for unbiased estimators.
    Used in Theorems 4, 6, 8 to equate L2 loss with variance.
  • ad hoc to paper F(eps1, alpha) attains its global minimum at a stationary point and Newton's method finds it.
    Section 4.2 asserts this; no convexity proof is given, and the optimization runs on Laplace-noised degree estimates.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy." pith.science (2026). https://pith.science/paper/LSNESN4J

@misc{pith2026250201904,
  author       = {Pith},
  title        = {Pith review of: Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LSNESN4J}},
  note         = {Machine review of arXiv:2502.01904}
}
read the original abstract

Bipartite graphs, formed by two vertex layers, arise as a natural fit for modeling the relationships between two groups of entities. In bipartite graphs, common neighborhood computation between two vertices on the same vertex layer is a basic operator, which is easily solvable in general settings. However, it inevitably involves releasing the neighborhood information of vertices, posing a significant privacy risk for users in real-world applications. To protect edge privacy in bipartite graphs, in this paper, we study the problem of estimating the number of common neighbors of two vertices on the same layer under edge local differential privacy (edge LDP). The problem is challenging in the context of edge LDP since each vertex on the opposite layer of the query vertices can potentially be a common neighbor. To obtain efficient and accurate estimates, we propose a multiple-round framework that significantly reduces the candidate pool of common neighbors and enables the query vertices to construct unbiased estimators locally. Furthermore, we improve data utility by incorporating the estimators built from the neighbors of both query vertices and devise privacy budget allocation optimizations. These improve the estimator's robustness and consistency, particularly against query vertices with imbalanced degrees. Extensive experiments on 15 datasets validate the effectiveness and efficiency of our proposed techniques.

Figures

Figures reproduced from arXiv: 2502.01904 by the authors.

Figure 1
Figure 1. A bipartite graph and its corresponding noisy graph [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. The estimate distribution on rmwiki when 𝜀 = 1. To tackle Challenge 3, we propose a double-source algorithm MultiR-DS under the multiple-round framework, which integrates two single-source estimators via a weighted average. In addition, we propose novel privacy budget allocation optimizations that allow MultiR-DS to dynamically adjust its privacy budgets for different rounds and the contribution of each single-sourc… view at source ↗
Figure 3
Figure 3. The left shows the original adjacency matrix and the right [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The construction of 𝑓e𝑢 and 𝑓e𝑤 based on the local neighborhoods of 𝑢1 and 𝑢2 (𝑢 = 𝑢1, 𝑤 = 𝑢2). 4.1 A single-source estimator for C2 (𝑢,𝑤) In this part, we introduce a two-round algorithm for estimating C2 (𝑢,𝑤). First, 𝜀1 is utilized to construct a noisy graph by appl…
Figure 5
Figure 5. Figure 5: Illustration of the L2 loss of 𝑓 ∗ when 𝜀 = 2. a privacy budget of𝜀2 to construct the unbiased estimator 𝑓e𝑢, which satisfies 𝜀2-edge LDP. By the sequential composition property of edge LDP, Algorithm 3 satisfies 𝜀-edge LDP (𝜀 = 𝜀1 + 𝜀2). □ 4.2 A double-source estimato…
Figure 6
Figure 6. Figure 6: Performance on different datasets (𝜖 = 2) Datasets. We use 15 datasets from KONECT (http://konect.cc/) [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 8
Figure 8. Figure 8: Effectiveness of privacy budget allocation optimization. 10 0 10 1 10 2 10 3 κ 10 −1 10 1 10 3 mean absolute error MultiR-SS MultiR-DS-Basic MultiR-DS (a) Team 10 0 10 1 10 2 10 3 κ 10 −1 10 1 10 3 mean absolute error MultiR-SS MultiR-DS-Basic MultiR-DS (b) Bookcrossin…
Figure 9
Figure 9. Figure 9: Effectiveness of MultiR-DS. 1.0 1.5 2.0 2.5 3.0 ε 10 −4 10 −2 10 0 10 2 10 4 communication cost (MB) Naive OneR MultiR-SS MultiR-DS (a) Wiki-En-Cat 1.0 1.5 2.0 2.5 3.0 ε 10 −4 10 −2 10 0 10 2 communication cost (MB) Naive OneR MultiR-SS MultiR-DS (b) Epinions 1.0 1.5 2…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

76 extracted references · 61 canonical work pages

  1. [1]

    Aman Abidi, Lu Chen, Rui Zhou, and Chengfei Liu. 2022. Searching Personalized𝑘 k-Wing in Bipartite Graphs.IEEE Transactions on Knowledge and Data Engineering 35, 8 (2022), 8515–8528

    work page 2022

  2. [2]

    Sinan G Aksoy, Tamara G Kolda, and Ali Pinar. 2017. Measuring and modeling bipartite graphs with community structure. Journal of Complex Networks 5, 4 (2017), 581–603

    2017

  3. [3]

    Remco R Bouckaert. 2008. Practical bias variance decomposition. In AI 2008: Advances in Artificial Intelligence: 21st Australasian Joint Conference on Artificial Intelligence Auckland, New Zealand, December 1-5, 2008. Proceedings 21 . Springer, 247–257

    work page 2008

  4. [4]

    Xiaoshuang Chen, Kai Wang, Xuemin Lin, Wenjie Zhang, Lu Qin, and Ying Zhang. 2021. Efficiently answering reachability and path queries on temporal bipartite graphs. Proceedings of the VLDB Endowment (2021)

    work page 2021

  5. [5]

    Wei-Yen Day, Ninghui Li, and Min Lyu. 2016. Publishing graph degree distribution with node differential privacy. In Proceedings of the 2016 International Conference on Management of Data . 123–138

    work page 2016

  6. [6]

    Laxman Dhulipala, Quanquan C Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, and Shangdi Yu. 2022. Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 754–765

    work page 2022

  7. [7]

    Xiaofeng Ding, Xiaodong Zhang, Zhifeng Bao, and Hai Jin. 2018. Privacy- preserving triangle counting in large graphs. In Proceedings of the 27th ACM international conference on information and knowledge management . 1283–1292

    work page 2018

  8. [8]

    Michael Dinitz, Satyen Kale, Silvio Lattanzi, and Sergei Vassilvitskii. 2023. Im- proved Differentially Private Densest Subgraph: Local and Purely Additive.arXiv preprint arXiv:2308.10316 (2023)

    arXiv 2023

Show all 76 references
  1. [9]

    Zheng Dong, Xin Huang, Guorui Yuan, Hengshu Zhu, and Hui Xiong

  2. [10]

    Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differ- ential privacy. Foundations and Trends® in Theoretical Computer Science 9, 3–4 (2014), 211–407

    2014

  3. [11]

    Talya Eden, Quanquan C Liu, Sofya Raskhodnikova, and Adam Smith. 2023. Trian- gle Counting with Local Edge Differential Privacy.arXiv preprint arXiv:2305.02263 (2023)

    2023 arXiv

  4. [12]

    Aurel Galántai. 2000. The theory of Newton’s method. J. Comput. Appl. Math. 124, 1-2 (2000), 25–44

    2000

  5. [13]

    Tianchong Gao, Feng Li, Yu Chen, and XuKai Zou. 2018. Local differential privately anonymizing online social networks under hrg-based model. IEEE Transactions on Computational Social Systems 5, 4 (2018), 1009–1020

    2018

  6. [14]

    Michael Hay, Chao Li, Gerome Miklau, and David Jensen. 2009. Accurate es- timation of the degree distribution of private networks. In 2009 Ninth IEEE International Conference on Data Mining . IEEE, 169–178

    2009

  7. [15]

    Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. 2009. Boosting the accuracy of differentially-private histograms through consistency. arXiv preprint arXiv:0904.0942 (2009)

    2009 arXiv

  8. [16]

    Lihe Hou, Weiwei Ni, Sen Zhang, Nan Fu, and Dongyue Zhang. 2023. PPDU: dynamic graph publication with local differential privacy. Knowledge and Infor- mation Systems 65, 7 (2023), 2965–2989

    2023

  9. [17]

    Zan Huang. 2010. Link prediction based on graph topology: The predictive value of generalized clustering coefficient. A vailable at SSRN 1634014 (2010)

    2010

  10. [18]

    Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally Differ- entially Private Analysis of Graph Statistics.. In USENIX Security Symposium . 983–1000

    2021

  11. [19]

    Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022. Communication- Efficient Triangle Counting under Local Differential Privacy. In 31st USENIX Security Symposium (USENIX Security 22) . 537–554

    2022

  12. [20]

    Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2022. Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security . 1505–1519

    2022

  13. [21]

    Honglu Jiang, Jian Pei, Dongxiao Yu, Jiguo Yu, Bei Gong, and Xiuzhen Cheng

  14. [22]

    Xin Ju, Xiaofeng Zhang, and William K Cheung. 2019. Generating synthetic graphs for large sensitive and correlated social networks. In 2019 IEEE 35th international conference on data engineering workshops (ICDEW) . IEEE, 286–293

    2019

  15. [23]

    IEEE Transactions on Knowledge and Data Engineering 35, 1 (2021), 108–127

    Applications of differential privacy in social network analysis: A survey. IEEE Transactions on Knowledge and Data Engineering 35, 1 (2021), 108–127

    2021

  16. [24]

    Elizabeth A Leicht, Petter Holme, and Mark EJ Newman. 2006. Vertex similarity in networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 73, 2 (2006), 026120

    2006

  17. [25]

    Vishesh Karwa, Sofya Raskhodnikova, Adam Smith, and Grigory Yaroslavtsev

  18. [26]

    Wanyu Lin, Baochun Li, and Cong Wang. 2022. Towards private learning on decentralized graphs with local differential privacy. IEEE Transactions on Infor- mation Forensics and Security 17 (2022), 2936–2946

    2022

  19. [27]

    Shang Liu, Yang Cao, Takao Murakami, Jinfei Liu, and Masatoshi Yoshikawa

  20. [28]

    Zhao Li, Xin Shen, Yuhang Jiao, Xuming Pan, Pengcheng Zou, Xianling Meng, Chengwei Yao, and Jiajun Bu. 2020. Hierarchical bipartite graph neural networks: Towards large-scale e-commerce applications. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) . IEEE,...

    2020

  21. [29]

    Zichun Liu, Liusheng Huang, Hongli Xu, Wei Yang, and Shaowei Wang. 2020. PrivAG: Analyzing attributed graph data with local differential privacy. In 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS) . IEEE, 422–429

    2020

  22. [30]

    Chaojie Lv, Xiaokui Xiao, Lan Zhang, and Ting Yu. 2024. Publishing Common Neighbors Histograms of Social Networks under Edge Differential Privacy. In Proceedings of the 19th ACM Asia Conference on Computer and Communications Security. 1099–1113

    2024

  23. [31]

    Tianzi Lv, Huanzhou Li, Zhangguo Tang, Fangzhou Fu, Jian Cao, and Jian Zhang

  24. [32]

    Yuhan Liu, Suyun Zhao, Yixuan Liu, Dan Zhao, Hong Chen, and Cuiping Li

  25. [33]

    Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2007. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing . 75–84

    2007

  26. [34]

    Clare M O’Connor, Jill U Adams, and Jennifer Fairman. 2010. Essentials of cell biology. Cambridge, MA: NPG Education 1 (2010), 54

    2010

  27. [35]

    Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. [n.d.]. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (2017). 425–438

    2017

  28. [36]

    Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. 2017. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 425–438

    2017

  29. [37]

    Security and Communication Networks 2021 (2021), 1–16

    Publishing Triangle Counting Histogram in Social Networks Based on Differential Privacy. Security and Communication Networks 2021 (2021), 1–16

    2021

  30. [38]

    Kamalkumar R Macwan and Sankita J Patel. 2018. Node differential privacy in social graph degree publishing. Procedia computer science 143 (2018), 786–793

    2018

  31. [39]

    John G Saw, Mark CK Yang, and Tse Chin Mo. 1984. Chebyshev inequality with estimated mean and variance. The American Statistician 38, 2 (1984), 130–132

    1984

  32. [40]

    Marija Stankova, Stiene Praet, David Martens, and Foster Provost. 2021. Node classification over bipartite graphs through projection. Machine Learning 110 (2021), 37–87

    2021

  33. [41]

    Henan Sun, Zhengyu Wu, Rong-Hua Li, Guoren Wang, and Zening Li. 2024. K-stars LDP: A Novel Framework for (p, q)-clique Enumeration under Local Differential Privacy. arXiv preprint arXiv:2403.01788 (2024)

    2024 arXiv

  34. [42]

    Haipei Sun, Xiaokui Xiao, Issa Khalil, Yin Yang, Zhan Qin, Hui Wang, and Ting Yu. 2019. Analyzing subgraph statistics from extended local views with decen- tralized differential privacy. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security . 703–717

    2019

  35. [43]

    Linshan Qiu, Zhonggen Li, Xiangyu Ke, Lu Chen, and Yunjun Gao. 2024. Accel- erating Biclique Counting on GPU. arXiv preprint arXiv:2403.07858 (2024)

    2024 arXiv

  36. [44]

    Sina Sajadmanesh and Daniel Gatica-Perez. 2021. Locally private graph neural networks. In Proceedings of the 2021 ACM SIGSAC conference on computer and communications security. 2130–2145

    2021

  37. [45]

    Jun Wang, Arjen P De Vries, and Marcel JT Reinders. 2006. Unifying user- based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29th annual international ACM SIGIR conference on Research 14 and development in information retrieval ....

    2006

  38. [46]

    Jianwei Wang, Kai Wang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2024. Efficient Unsupervised Community Search with Pre-trained Graph Transformer. Proc. VLDB Endow. 17, 9 (2024), 2227–2240. https://www.vldb.org/pvldb/vol17/ p2227-wang.pdf

    2024

  39. [47]

    Zhibin Wang, Longbin Lai, Yixue Liu, Bing Shui, Chen Tian, and Sheng Zhong

  40. [48]

    Stanley L Warner. 1965. Randomized response: A survey technique for eliminating evasive answer bias. J. Amer. Statist. Assoc. 60, 309 (1965), 63–69

    1965

  41. [49]

    Jimeng Sun, Huiming Qu, Deepayan Chakrabarti, and Christos Faloutsos. 2005. Neighborhood formation and anomaly detection in bipartite graphs. InFifth IEEE international conference on data mining (ICDM’05) . IEEE, 8–pp

    2005

  42. [50]

    Charalampos E Tsourakakis. 2014. Toward quantifying vertex similarity in networks. Internet Mathematics 10, 3-4 (2014), 263–286

    2014

  43. [51]

    Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. 2022. Linkteller: Recovering private edges from graph neural networks via influence analysis. In 2022 ieee symposium on security and privacy (sp) . IEEE, 2005–2024

    2022

  44. [52]

    Tian Xie, Chaoyang He, Xiang Ren, Cyrus Shahabi, and C-C Jay Kuo. 2022. L- bgnn: Layerwise trained bipartite graph neural networks. IEEE Transactions on Neural Networks and Learning Systems (2022)

    2022

  45. [53]

    Qingyu Xu, Feng Zhang, Zhiming Yao, Lv Lu, Xiaoyong Du, Dong Deng, and Bing- sheng He. 2022. Efficient load-balanced butterfly counting on GPU. Proceedings of the VLDB Endowment 15, 11 (2022), 2450–2462

    2022

  46. [54]

    Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27

    I/O-Efficient Butterfly Counting at Scale. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27

    2023

  47. [55]

    Jianye Yang, Yun Peng, and Wenjie Zhang. 2021. (p, q)-biclique counting and enumeration for large sparse bipartite graphs.Proceedings of the VLDB Endowment 15, 2 (2021), 141–153

    2021

  48. [56]

    Chengkun Wei, Shouling Ji, Changchang Liu, Wenzhi Chen, and Ting Wang

  49. [57]

    Renchi Yang. 2022. Efficient and Effective Similarity Search over Bipartite Graphs. In Proceedings of the ACM Web Conference 2022 . 308–318

    2022

  50. [58]

    Yuecen Wei, Haonan Yuan, Xingcheng Fu, Qingyun Sun, Hao Peng, Xianxian Li, and Chunming Hu. 2024. Poincaré Differential Privacy for Hierarchy-aware Graph Embedding. In Proceedings of the AAAI Conference on Artificial Intelligence , Vol. 38. 9160–9168

    2024

  51. [59]

    Renchi Yang, Jieming Shi, Keke Huang, and Xiaokui Xiao. 2022. Scalable and effective bipartite network embedding. In Proceedings of the 2022 International Conference on Management of Data . 1977–1991

    2022

  52. [60]

    Qingqing Ye, Haibo Hu, Man Ho Au, Xiaofeng Meng, and Xiaokui Xiao. 2020. LF- GDPR: A framework for estimating graph metrics with local differential privacy. IEEE Transactions on Knowledge and Data Engineering 34, 10 (2020), 4905–4920

    2020

  53. [61]

    Xiaowei Ye, Rong-Hua Li, Qiangqiang Dai, Hongchao Qin, and Guoren Wang

  54. [62]

    Jianye Yang, Yun Peng, Dian Ouyang, Wenjie Zhang, Xuemin Lin, and Xiang Zhao. 2023. (p, q)-biclique counting and enumeration for large sparse bipartite graphs. The VLDB Journal (2023), 1–25

    2023

  55. [63]

    Xianhang Zhang, Hanchen Wang, Jianke Yu, Chen Chen, Xiaoyang Wang, and Wenjie Zhang. 2022. Polarity-based graph neural network for sign prediction in signed bipartite graphs. World Wide Web 25, 2 (2022), 471–487

    2022

  56. [64]

    Mengmeng Yang, Taolin Guo, Tianqing Zhu, Ivan Tjuawinata, Jun Zhao, and Kwok-Yan Lam. 2023. Local differential privacy and its applications: A compre- hensive survey. Computer Standards & Interfaces (2023), 103827

    2023

  57. [65]

    Yuxuan Zhang, Jianghong Wei, Xiaojian Zhang, Xuexian Hu, and Wenfen Liu

  58. [66]

    Renchi Yang and Jieming Shi. 2023. Efficient High-Quality Clustering for Large Bipartite Graphs. arXiv preprint arXiv:2312.16926 (2023)

    2023 arXiv

  59. [70]

    Proceedings of the ACM on Management of Data 1, 1 (2023), 1–26

    Efficient Biclique Counting in Large Bipartite Graphs. Proceedings of the ACM on Management of Data 1, 1 (2023), 1–26

    2023

  60. [71]

    Jun Zhang, Graham Cormode, Cecilia M Procopiuc, Divesh Srivastava, and Xi- aokui Xiao. 2015. Private release of graph statistics using ladder functions. In Proceedings of the 2015 ACM SIGMOD international conference on management of data. 731–745

    2015

  61. [73]

    Xianhang Zhang, Hanchen Wang, Jianke Yu, Chen Chen, Xiaoyang Wang, and Wenjie Zhang. 2023. Bipartite graph capsule network. World Wide Web 26, 1 (2023), 421–440

    2023

  62. [76]

    Xiaochen Zhu, Vincent YF Tan, and Xiaokui Xiao. 2023. Blink: Link Local Differ- ential Privacy in Graph Neural Networks via Bayesian Estimation. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security . 2651–2664. 15

    2023

  63. [2011]

    Proceedings of the VLDB Endowment 4, 11 (2011), 1146–1157

    Private analysis of graph structure. Proceedings of the VLDB Endowment 4, 11 (2011), 1146–1157

    2011

  64. [2018]

    In Proceedings of the 8th International Conference on Communication and Network Security

    A two-phase algorithm for generating synthetic graph under local differen- tial privacy. In Proceedings of the 8th International Conference on Communication and Network Security. 84–89

  65. [2020]

    IEEE Transactions on Information Forensics and Security 15 (2020), 3239–3254

    AsgLDP: Collecting and generating decentralized attributed graphs with local differential privacy. IEEE Transactions on Information Forensics and Security 15 (2020), 3239–3254

    2020

  66. [2021]

    arXiv preprint arXiv:2105.08628 (2021)

    Butterfly-core community search over labeled graphs. arXiv preprint arXiv:2105.08628 (2021)

    2021 arXiv

  67. [2022]

    In 2022 IEEE 38th International Conference on Data Engineering (ICDE)

    Collecting triangle counts with edge relationship local differential privacy. In 2022 IEEE 38th International Conference on Data Engineering (ICDE) . IEEE, 2008–2020

    2022

  68. [2023]

    arXiv preprint arXiv:2312.12938 (2023)

    CARGO: Crypto-Assisted Differentially Private Triangle Counting without Trusted Servers. arXiv preprint arXiv:2312.12938 (2023)

    2023 arXiv

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.