REVIEW 4 major objections 5 minor 60 references
Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix
T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Powers of a noisy adjacency matrix give unbiased, edge-private subgraph counts, including the first pure edge-LDP quadrangle algorithm.
desk verdict The NAM matrix-power idea is sound and QuaTR is a real first, but the second-round privacy proofs undercount sensitivity by a factor of d_u, so TriTR and QuaTR don't yet have the claimed edge-LDP guarantee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The Noisy Adjacency Matrix (NAM) is a symmetric $n\times n$ matrix $\hat{A}$ with $E[\hat{A}]=A$, zero diagonal, and mutually independent off-diagonal entries; its key property (Theorem 1) is that the expectation of the diagonal of $\hat{A}^3$ equals the diagonal of $A^3$, and the off-diagonal entries of $\hat{A}^2$ are unbiased for $A^2$. The machinery is the vanishing of the cross terms in $(A+X)^3$ under symmetry, independence, and $E[X]=0$, together with the debiasing built into GNAM: each node reports its randomized adjacency list with entries for higher-index nodes blanked so that each edge is uploaded exactly once, and each reported bit is rescaled (e.g., $y = (x(e^{\varepsilon}+1)-1)/(e^{\varepsilon}-1)$ under randomized response) so the estimator is unbiased. These two pieces — the power identity and the one-upload debiasing — carry every counting algorithm in the paper.
What would settle it
Fix the parameters used in the experiments ($\varepsilon$, $\beta=0.01$) on a real social network, generate $\hat{A}$ through GNAM, and directly measure the change in the clamped sums of Algorithms 7–9 when a single neighbor is added to or removed from a user's list; if the fraction of users whose change exceeds $\Delta f_u$ is comparable to $\beta$ or larger, the pure edge-LDP step in Theorems 12–14 fails.
Extended reading notes
Core claim
The discovery is that the expected value of products of independent zero-mean symmetric edge noises vanishes in exactly the terms that matter: writing $\hat{A} = A + X$ with $E[X]=0$, $X$ symmetric, independent off-diagonal entries, and zero diagonal, the cross terms — $E[(AX)_{ii}]$, $E[(XAX)_{ii}]$, and so on — all vanish, leaving $E[(\hat{A}^3)_{ii}] = (A^3)_{ii}$ and, for $i \neq j$, $E[(\hat{A}^2)_{ij}] = (A^2)_{ij}$. These identities make $\mathrm{tr}(\hat{A}^3)/6$ an unbiased estimator of the number of triangles, make $\hat{A}^2$ an unbiased estimator of two-step path counts, and consequently allow quadrangle counts by subtracting the single 'return path' term $\hat{b}_{ij} - 1$; the divisors 6 and 8 correct for the orientation multiplicities of triangles and quadrangles. The construction that generates $\hat{A}$ (GNAM) lets each node randomize its own adjacency list once, blanks entries above its own index so that every edge is reported by exactly one endpoint, and the collector debiases the reports, which yields $\varepsilon$-edge LDP. On this basis the paper claims its five algorithms improve on prior one-round and two-round triangle counters in accuracy or communication, and that QuaTR is the first quadrangle counter under pure edge-LDP.
Load-bearing premise
The paper bets that a user's rounded-up contribution can be bounded by a number computed from a normal approximation; if that number is wrong, the second-round noise is too small to deliver the promised privacy.
Editorial extensions
If this is right
- Triangle counting becomes a one-round matrix-power computation with collector-side time $O(n^{2.371866})$ via fast matrix multiplication, replacing the $O(n^3)$ triplet enumeration of earlier one-round edge-LDP algorithms.
- Two-round triangle counting reaches MSE $O(nd_{\max}^3)$ (TriTR) or $O(nd_{\max}^3 + n^2 d_{\max})$ with download cost $O(n)$ (TriMTR), so accuracy and communication can be traded off.
- QuaTR is the first quadrangle-counting algorithm under pure edge-LDP, with MSE $O(nd_{\max}^5 + n^2 d_{\max}^3)$, a gap left open by prior shuffle-model methods.
- A single two-round pipeline yields simultaneous unbiased estimates of triangle, quadrangle, and 2-star counts, with 2STAR reaching relative error $O(1/\sqrt{\#2\text{-star}})$.
- Because the NAM proof does not depend on a specific mechanism or on undirectedness, the framework transfers to directed graphs, weighted graphs, and to f-DP or $(\varepsilon,\delta)$-DP by swapping the local randomizer.
Reading between the lines
- The same power identity should generalize: any subgraph count that is a linear combination of entries of $A^k$ can be estimated by the same combination of $\hat{A}^k$, so longer cycles, paths, and other motifs could inherit the one-round or two-round scheme without new per-motif privacy analyses.
- The probabilistic sensitivity bound in Section 6 is the step most likely to need a privacy patch; a rigorous version would either state the guarantee as $(\varepsilon,\delta)$-DP with $\delta$ tied to $\beta$, or replace the central-limit quantile with a deterministic bound that holds for every input.
- Because GNAM is deliberately mechanism-agnostic, the framework can be instantiated with other unbiased DP mechanisms; the variance and privacy trade-offs of, say, a Gaussian or Hadamard-response instantiation follow from the same proof template but are not analyzed in the paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a Noisy Adjacency Matrix (NAM) framework for subgraph counting under edge local differential privacy. It proves that powers of an unbiased, symmetric, independently perturbed adjacency matrix give unbiased estimates of path counts (Theorem 1), and then derives five algorithms: TriOR (one-round triangle counting), TriTR and TriMTR (two-round triangle counting), QuaTR (two-round quadrangle counting), and 2STAR (2-star counting from a private degree-projection step). The paper claims pure edge-LDP guarantees for the one-round algorithm and (ε0+ε1+ε2)-edge LDP for the two-round algorithms, together with MSE bounds and experimental comparisons. The algebraic unbiasedness result is clean, but the privacy analysis of the second-round randomizers in Algorithms 7 and 9 is based on an incorrect sensitivity computation, and the stated total-MSE bounds omit bias from clamping and GraphProjection.
Significance. The NAM construction is an elegant idea and Theorem 1 is a genuinely useful observation: it provides a modular way to turn unbiased private edge perturbations into unbiased subgraph-count estimates via matrix powers. The one-round TriOR result, with time O(n^2.371866) and MSE O(nd_max^3+n^3), is a plausible contribution. However, the two-round algorithms are the main claimed advances, especially QuaTR as the first quadrangle counter under pure edge-LDP, and their privacy guarantee is not established. The 2STAR theoretical analysis also does not match the implemented estimator. If the sensitivity issue were repaired, the required noise scale and the accuracy bounds would change substantially, so the current theoretical and experimental comparisons do not support the headline claims.
major comments (4)
- [§5.2, Algorithm 7; Appendix E.14] The sensitivity analysis for the second-round randomizer in Algorithm 7 is incorrect. In line 2, sumu = Σ_{i∈Neiu} clamp(Σ_{j∈Neiu,j<i} â_ij, Δf_u). If a neighbor k is added, then for each existing neighbor i with i>k the i-th inner sum gains the term â_ik, and a new clamped term appears for i=k. The proof in E.14 correctly identifies Σ_{j∈Neiu} â_kj as the change in the unclamped sum, but it then incorrectly concludes that clamping each inner sum bounds the total change by Δf_u. Because clamping is 1-Lipschitz, each of the d_u affected inner sums can change by up to Δf_u, so the total change can be as large as d_u·Δf_u, not Δf_u. Consequently, the Laplace noise Lap(Δf_u/ε2) is too small by up to a factor of d_u, and the claimed ε2-edge LDP guarantee in Theorems 5 and 12 does not hold. Algorithm 9 and Theorem 14 have the identical structure and the same flaw. This is a deterministic sensitivity undercount, independent of the CLT approximation in Theorem 11.
- [Appendix E.13, Theorem 11, Algorithm 6] The probabilistic bound that calibrates the clamp range Δf_u is not established. Theorem 11 is stated only as an approximation via the CLT, yet the subsequent accuracy claims treat it as a rigorous β-quantile guarantee. Moreover, the proof asserts that 'After Graph Projection on graph G, for any vertex u ∈ [n], we have ˆdu ≥ du,' which is false: Algorithm 6 sets ˆdu = ⌊α + max{du + Lap(1/ε0), 0}⌋, and if the Laplace noise is sufficiently negative, ˆdu < du and edges are then removed. Thus Δf_u can be too small, and even the approximate probability bound Pr[λu > Δf_u] < β is unsupported. Since the total-MSE bounds in Theorems 12–14 depend on the clamping error being bounded by a β-fraction of data, this is a load-bearing gap in the accuracy analysis.
- [Theorems 12–14, Appendix E.14–E.16] The claimed total-MSE upper bounds in Theorems 12–14 are not proven. The proofs state that the total MSE has four components—GraphProjection error, clamping error, the variance of the unclamped sum, and the variance of the second-round Laplace noise—but then they bound only the last two components and assert that the first two have 'relatively small impact' without any quantitative estimate. Because clamping introduces bias and GraphProjection removes edges, the clamped estimator is not unbiased, and the displayed O(·) expressions are not valid upper bounds on the total MSE. The relative-error results in Theorem 15 inherit this problem, as they are derived from these MSE bounds.
- [§7.2, Theorem 16 vs. Algorithm 10] The theoretical guarantees for 2STAR do not apply to the algorithm as written. Theorem 16 analyzes the idealized estimator Σ_u[(du+Yu)(du-1+Yu)-2/ε0^2] with Yu ~ Lap(1/ε0), whereas Algorithm 10 uses the GraphProjection output (˜du-α)(˜du-α-1)-2/ε0^2, where ˜du is truncated, rounded, and followed by edge removal when ˜du<du. The paper acknowledges the discrepancy but provides no bias bound. The claims that 2STAR is unbiased and achieves RE=O(1/√#2-star) are therefore unsupported.
minor comments (5)
- [§5.3] The sentence immediately before Theorem 7 reads 'TriTR holds the following guarantees,' but the surrounding algorithm is TriMTR; the label should be corrected.
- [Appendix E.11] In the proof of Theorem 9, the name 'QuaMTR' is used; it should be 'QuaTR'.
- [Eq. (22)] The third term in the TriMTR relative-error bound is printed as '1/(ε2_1 d_avg^{3/2})'; based on the derivation in E.17 and the analogous term in Eq. (21), this should be '1/(ε1^2 d_avg^{3/2})'.
- [Figure 2 caption] The caption is confusing: it says the solid and dashed blue lines correspond to 'the variance obtained with the Laplace mechanism and the curve obtained by doubling the variance,' but the red line is labeled as the Laplace variance in the text; the intended comparison between RR and Laplace should be restated clearly.
- [§8.1] The experimental section reports results averaged over 20 runs but provides no error bars or standard deviations. Given that several comparisons (e.g., Figure 8) are visually close, the reported accuracy differences would be more convincing with variance information.
Circularity Check
No significant circularity: all estimators are derived from the NAM moment identities and standard DP mechanisms, with no fitted parameter renamed as a prediction.
full rationale
After walking the derivation chain, no circular step is present. Definition 3 fixes only E[Â]=A, symmetry, zero diagonal, and independence of off-diagonal entries; Theorem 1 then follows by expanding (A+X)^2 and (A+X)^3 in Appendix E.1 and using E[X]=0 together with the fact that products vanish when indices coincide. TriOR, TriTR, TriMTR, and QuaTR evaluate these unbiased moments with fixed symmetry constants (division by 6, 6, 6, and 8), and the MSE formulas in Theorems 4, 6, 8, and 10 are variance expansions built on Lemma 1; none of these derivations assumes the target count f△ or f□ as an input. 2STAR is a debiased moment estimator of Σ d_u(d_u−1), with the −2/ε0² term computed from the Laplace variance. The hyperparameters α, β, and the ε0/ε1/ε2 split are fixed in advance and validated against two real datasets, so no fitted value is relabeled as a prediction. The paper itself flags a genuine limitation: Theorem 11 is only approximate because of the CLT, and the two-round privacy claims in Theorems 12–14 inherit that approximation. This is a load-bearing correctness risk, but it is not circularity: the privacy conclusion does not reduce to the data or to a self-citation. There are no self-citations by the present authors and no uniqueness theorem imported from the authors' prior work. The derivation is self-contained against external benchmarks, so the appropriate circularity score is 0.
Assumptions & free parameters
free parameters (3)
- alpha =
20 (experiments)
- beta =
0.01 (experiments)
- epsilon0, epsilon1, epsilon2 (budget split) =
0.1*epsilon, 0.8*epsilon, 0.1*epsilon (experiments)
assumptions (5)
- domain assumption The noisy adjacency matrix entries are mutually independent and unbiased (Definition 3).
- ad hoc to paper Central Limit Theorem approximations for sums of noisy matrix entries (Theorem 11 proof).
- standard math Sequential composition of edge-LDP (Proposition 1).
- domain assumption Clustering coefficient exists and is constant (Theorem 15).
- domain assumption GraphProjection provides epsilon0-edge LDP.
Cite this review
Pith. "Pith review of Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix." pith.science (2026). https://pith.science/paper/YL5A3VFO
@misc{pith2026250706508,
author = {Pith},
title = {Pith review of: Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix},
year = {2026},
howpublished = {\url{https://pith.science/paper/YL5A3VFO}},
note = {Machine review of arXiv:2507.06508}
}
read the original abstract
When analyzing connection patterns within graphs, subgraph counting serves as an effective and fundamental approach. Edge-local differential privacy (edge-LDP) and shuffle model have been employed to achieve subgraph counting under a privacy-preserving situation. Existing algorithms are plagued by high time complexity, excessive download costs, low accuracy, or dependence on trusted third parties. To address the aforementioned challenges, we propose the Noisy Adjacency Matrix (NAM), which combines differential privacy with the adjacency matrix of the graph. NAM offers strong versatility and scalability, making it applicable to a wider range of DP variants, DP mechanisms, and graph types. Based on NAM, we designed five algorithms (TriOR, TriTR, TriMTR, QuaTR, and 2STAR) to count three types of subgraphs: triangles, quadrangles, and 2-stars. Theoretical and experimental results demonstrate that in triangle counting, TriOR maximizes accuracy with reduced time complexity among one-round algorithms, TriTR achieves optimal accuracy, TriMTR achieves the highest accuracy under low download costs, and QuaTR stands as the first quadrangle counting algorithm under pure edge-LDP. We implement edge-LDP for noisy data via a confidence interval-inspired method, providing DP guarantees on randomized data. Our 2STAR algorithm achieves the highest accuracy in 2-star counting and can be derived as a byproduct of two-round triangle or quadrangle counting algorithms, enabling efficient joint estimation of triangle, quadrangle, and 2-star counts within two query rounds.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
Hadamard response: Estimating distributions privately, efficiently, and with little communication
ACHARYA , J., S UN, Z., AND ZHANG , H. Hadamard response: Estimating distributions privately, efficiently, and with little communication. In The 22nd Interna- tional Conference on Artificial Intelligence and Statis- tics (2019), PMLR, pp. 1120–1129
work page 2019
-
[2]
S., G OULEAKIS , T., PEEBLES , J., R UBINFELD , R., AND YODPINYANEE , A
ALIAKBARPOUR , M., B ISWAS , A. S., G OULEAKIS , T., PEEBLES , J., R UBINFELD , R., AND YODPINYANEE , A. Sublinear-time algorithms for counting star subgraphs via edge sampling. Algorithmica 80 (2018), 668–697
work page 2018
-
[3]
Counting triangles in large graphs using ran- domized matrix trace estimation
AVRON , H. Counting triangles in large graphs using ran- domized matrix trace estimation. In Workshop on Large- scale Data Mining: Theory and Applications (2010), vol. 10, p. 9
work page 2010
-
[4]
The privacy blanket of the shuffle model
BALLE , B., B ELL , J., G ASCÓN , A., AND NISSIM , K. The privacy blanket of the shuffle model. In Advances in Cryptology–CRYPTO 2019: 39th Annual Interna- tional Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II 39 (2019), Springer, pp. 638–667
work page 2019
-
[5]
BERA , S. K., AND SESHADHRI , C. How the degen- eracy helps for triangle counting in graph streams. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (2020), pp. 457–467
work page 2020
-
[6]
W., SCHNEIDER , S., AND KERSCHBAUM , F
BERNAU , D., R OBL , J., G RASSAL , P. W., SCHNEIDER , S., AND KERSCHBAUM , F. Comparing local and central differential privacy using membership inference attacks. In IFIP Annual Conference on Data and Applications Security and Privacy (2021), Springer, pp. 22–42
work page 2021
-
[7]
A privacy- preserving mechanism based on local differential pri- vacy in edge computing
BI, M., WANG , Y., CAI, Z., AND TONG , X. A privacy- preserving mechanism based on local differential pri- vacy in edge computing. China Communications 17, 9 (2020), 50–65
work page 2020
-
[8]
Approximate counting of k-paths: Deterministic and in polynomial space
BJÖRKLUND , A., L OKSHTANOV , D., S AURABH , S., AND ZEHAVI , M. Approximate counting of k-paths: Deterministic and in polynomial space. In 46th In- ternational Colloquium on Automata, Languages, and Programming (ICALP 2019) (2019), Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik
work page 2019
Show all 60 references
-
[9]
Distributed differential privacy via shuf- fling
CHEU , A., S MITH , A., U LLMAN , J., Z EBER , D., AND ZHILYAEV, M. Distributed differential privacy via shuf- fling. In Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darm- stadt, Germany...
2019
-
[10]
Arboricity and sub- graph listing algorithms
CHIBA , N., AND NISHIZEKI , T. Arboricity and sub- graph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210–223
1985
-
[11]
Matrix mul- tiplication via arithmetic progressions
COPPERSMITH , D., AND WINOGRAD , S. Matrix mul- tiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (1987), pp. 1–6
1987
-
[12]
DONG , J., R OTH, A., AND SU, W. J. Gaussian differ- ential privacy. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 84, 1 (2022), 3–37
2022
-
[13]
Faster matrix mul- tiplication via asymmetric hashing
DUAN, R., W U, H., AND ZHOU , R. Faster matrix mul- tiplication via asymmetric hashing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) (2023), IEEE, pp. 2129–2138
2023
-
[14]
Differential privacy
DWORK , C. Differential privacy. In International colloquium on automata, languages, and programming (2006), Springer, pp. 1–12. 14
2006
-
[15]
Calibrating noise to sensitivity in private data anal- ysis
DWORK , C., M CSHERRY, F., NISSIM , K., AND SMITH , A. Calibrating noise to sensitivity in private data anal- ysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 (2006), Springer, pp. 265–284
2006
-
[16]
The algorithmic founda- tions of differential privacy
DWORK , C., ROTH, A., ET AL . The algorithmic founda- tions of differential privacy. Foundations and Trends® in Theoretical Computer Science 9 , 3–4 (2014), 211– 407
2014
-
[17]
Approximately counting triangles in sublinear time
EDEN , T., L EVI , A., R ON, D., AND SESHADHRI , C. Approximately counting triangles in sublinear time. SIAM Journal on Computing 46, 5 (2017), 1603–1646
2017
-
[18]
C., R ASKHODNIKOVA , S., AND SMITH , A
EDEN , T., L IU, Q. C., R ASKHODNIKOVA , S., AND SMITH , A. Triangle counting with local edge differen- tial privacy. arXiv preprint arXiv:2305.02263 (2023)
2023 arXiv
-
[19]
Amplification by shuffling: From local to central differential privacy via anonymity
ERLINGSSON , Ú., F ELDMAN , V., M IRONOV, I., RAGHUNATHAN , A., T ALWAR, K., AND THAKURTA , A. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (2019), SIAM, p...
2019
-
[20]
Hiding among the clones: A simple and nearly opti- mal analysis of privacy amplification by shuffling
FELDMAN , V., M CMILLAN , A., AND TALWAR, K. Hiding among the clones: A simple and nearly opti- mal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2022), IEEE, pp. 954–964
2022
-
[21]
Counting stars and other small subgraphs in sublinear-time
GONEN , M., R ON, D., AND SHAVITT , Y. Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Mathematics 25, 3 (2011), 1365– 1411
2011
-
[22]
Lo- cally differentially private analysis of graph statistics
IMOLA , J., M URAKAMI , T., AND CHAUDHURI , K. Lo- cally differentially private analysis of graph statistics. In 30th USENIX security symposium (USENIX Security
-
[23]
983–1000
(2021), pp. 983–1000
2021
-
[24]
{Communication-Efficient} triangle counting under lo- cal differential privacy
IMOLA , J., M URAKAMI , T., AND CHAUDHURI , K. {Communication-Efficient} triangle counting under lo- cal differential privacy. In 31st USENIX security sympo- sium (USENIX Security 22) (2022), pp. 537–554
2022
-
[25]
Dif- ferentially private triangle and 4-cycle counting in the shuffle model
IMOLA , J., M URAKAMI , T., AND CHAUDHURI , K. Dif- ferentially private triangle and 4-cycle counting in the shuffle model. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (2022), pp. 1505–1519
2022
-
[26]
Publishing graphs under node differential privacy
JIAN , X., WANG , Y., AND CHEN , L. Publishing graphs under node differential privacy. IEEE Transactions on Knowledge and Data Engineering 35, 4 (2021), 4164– 4177
2021
-
[27]
Dis- crete distribution estimation under local privacy
KAIROUZ , P., B ONAWITZ , K., AND RAMAGE , D. Dis- crete distribution estimation under local privacy. In International Conference on Machine Learning (2016), PMLR, pp. 2436–2444
2016
-
[28]
The complexity of counting cycles in the adjacency list streaming model
KALLAUGHER , J., M CGREGOR , A., P RICE , E., AND VOROTNIKOVA , S. The complexity of counting cycles in the adjacency list streaming model. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (2019), pp. 119–133
2019
-
[29]
P., AND KIM, S
KARTUN -G ILES , A. P., AND KIM, S. Counting k-hop paths in the random connection model. IEEE Transac- tions on Wireless Communications 17, 5 (2018), 3201– 3210
2018
-
[30]
P., N ISSIM , K., R ASKHOD - NIKOVA , S., AND SMITH , A
KASIVISWANATHAN , S. P., N ISSIM , K., R ASKHOD - NIKOVA , S., AND SMITH , A. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings (2013), Springer, pp. 457–476
2013
-
[31]
N., M ILLER , G
KOLOUNTZAKIS , M. N., M ILLER , G. L., P ENG , R., AND TSOURAKAKIS , C. E. Efficient triangle count- ing in large graphs via degree-based vertex partitioning. Internet Mathematics 8, 1-2 (2012), 161–185
2012
-
[32]
Powers of tensors and fast matrix multi- plication
LE GALL , F. Powers of tensors and fast matrix multi- plication. In Proceedings of the 39th international sym- posium on symbolic and algebraic computation (2014), pp. 296–303
2014
-
[33]
Graph evolution: Densification and shrinking diameters
LESKOVEC , J., K LEINBERG , J., AND FALOUTSOS , C. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD) 1, 1 (2007), 2–es
2007
-
[34]
SNAP Datasets: Stan- ford large network dataset collection
LESKOVEC , J., AND KREVL , A. SNAP Datasets: Stan- ford large network dataset collection. http://snap. stanford.edu/data, June 2014
2014
-
[35]
Learning to dis- cover social circles in ego networks
LESKOVEC , J., AND MCAULEY , J. Learning to dis- cover social circles in ego networks. Advances in neural information processing systems 25 (2012)
2012
-
[36]
Collecting triangle counts with edge relationship local differential privacy
LIU, Y., ZHAO, S., L IU, Y., ZHAO, D., C HEN , H., AND LI, C. Collecting triangle counts with edge relationship local differential privacy. In 2022 IEEE 38th Interna- tional Conference on Data Engineering (ICDE) (2022), IEEE, pp. 2008–2020
2022
-
[37]
Approximate counting of cycles in streams
MANJUNATH , M., M EHLHORN , K., P ANAGIOTOU , K., AND SUN, H. Approximate counting of cycles in streams. In Algorithms–ESA 2011: 19th Annual Eu- ropean Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings 19 (2011), Springer, pp. 677– 688. 15
2011
-
[38]
Triangle and four cycle counting in the data stream model
MCGREGOR , A., AND VOROTNIKOVA , S. Triangle and four cycle counting in the data stream model. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (2020), pp. 445–456
2020
-
[39]
MCSHERRY, F. D. Privacy integrated queries: an exten- sible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data (2009), pp. 19–30
2009
-
[40]
The number of data breaches in 2021 has already surpassed last year’s total, 2021
M ORRIS , C. The number of data breaches in 2021 has already surpassed last year’s total, 2021
2021
-
[41]
{Utility- optimized} local differential privacy mechanisms for distribution estimation
MURAKAMI , T., AND KAWAMOTO , Y. {Utility- optimized} local differential privacy mechanisms for distribution estimation. In 28th USENIX Security Sym- posium (USENIX Security 19) (2019), pp. 1877–1894
2019
-
[42]
Local and central differential privacy for robustness and privacy in federated learning
NASERI , M., H AYES, J., AND DE CRISTOFARO , E. Local and central differential privacy for robustness and privacy in federated learning. arXiv preprint arXiv:2009.03561 (2020)
2020 arXiv
-
[43]
Faster approximate subgraph counts with privacy
NGUYEN , D., H ALAPPANAVAR , M., S RINIVASAN , V., AND VULLIKANTI , A. Faster approximate subgraph counts with privacy. Advances in Neural Information Processing Systems 36 (2024)
2024
-
[44]
Smooth sensitivity and sampling in private data anal- ysis
NISSIM , K., R ASKHODNIKOVA , S., AND SMITH , A. Smooth sensitivity and sampling in private data anal- ysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (2007), pp. 75–84
2007
-
[45]
Triangle listing al- gorithms: Back from the diversion
ORTMANN , M., AND BRANDES , U. Triangle listing al- gorithms: Back from the diversion. In2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (2014), SIAM, pp. 1–8
2014
-
[46]
Generating synthetic decentralized social graphs with local differential privacy
QIN, Z., Y U, T., Y ANG , Y., K HALIL , I., X IAO, X., AND REN, K. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC conference on computer and communications security (2017), pp. 425–438
2017
-
[47]
Differentially private analysis of graphs
RASKHODNIKOVA , S., AND SMITH , A. Differentially private analysis of graphs. Encyclopedia of Algorithms (2016)
2016
-
[48]
E., A PARICIO , D., AND SILVA, F
RIBEIRO , P., PAREDES , P., S ILVA, M. E., A PARICIO , D., AND SILVA, F. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR) 54, 2 (2021), 1–36
2021
-
[49]
SATISH , N., S UNDARAM , N., P ATWARY, M. M. A., SEO, J., P ARK , J., H ASSAAN , M. A., S ENGUPTA , S., YIN, Z., AND DUBEY, P. Navigating the maze of graph analytics frameworks using massive graph datasets. In Proceedings of the 2014 ACM SIGMOD international conference on Mana...
2014
-
[50]
SESHADHRI , C., P INAR , A., AND KOLDA , T. G. Tri- adic measures on graphs: The power of wedge sampling. In Proceedings of the 2013 SIAM international confer- ence on data mining (2013), SIAM, pp. 10–18
2013
-
[51]
STOTHERS , A. J. On the complexity of matrix multipli- cation
-
[52]
Gaussian elimination is not optimal
STRASSEN , V. Gaussian elimination is not optimal. Numerische mathematik 13, 4 (1969), 354–356
1969
-
[53]
E., K ANG , U., M ILLER , G
TSOURAKAKIS , C. E., K ANG , U., M ILLER , G. L., AND FALOUTSOS , C. Doulion: counting triangles in massive graphs with a coin. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (2009), pp. 837–846
2009
-
[54]
WANG , N., Z HANG , J., TAN, K.-L., AND TUNG , A. K. On triangulation-based dense neighborhood graph dis- covery. Proceedings of the VLDB Endowment 4 , 2 (2010), 58–68
2010
-
[55]
Locally differentially private protocols for frequency estimation
WANG , T., B LOCKI , J., L I, N., AND JHA, S. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security
-
[56]
Edge-based differential privacy comput- ing for sensor–cloud systems
WANG , T., M EI, Y., J IA, W., Z HENG , X., W ANG , G., AND XIE, M. Edge-based differential privacy comput- ing for sensor–cloud systems. Journal of Parallel and Distributed computing 136 (2020), 75–85
2020
-
[57]
Using randomized response for differential privacy preserving data col- lection
WANG , Y., W U, X., AND HU, D. Using randomized response for differential privacy preserving data col- lection. In EDBT/ICDT Workshops (2016), vol. 1558, pp. 0090–6778
2016
-
[58]
WARNER , S. L. Randomized response: A survey tech- nique for eliminating evasive answer bias.Journal of the American Statistical Association 60, 309 (1965), 63–69
1965
-
[59]
WILLIAMS , V. V. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the forty- fourth annual ACM symposium on Theory of computing (2012), pp. 887–898
2012
-
[60]
n1 ∏ i=1 Zki αi #2 + E
YANG , M., G UO, T., ZHU, T., TJUAWINATA , I., Z HAO, J., AND LAM, K.-Y. Local differential privacy and its applications: A comprehensive survey. Computer Standards & Interfaces 89 (2024), 103827. 16 A Directed Graph Application In the main text, we mentioned that our algorith...
2024
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.