REVIEW 3 major objections 5 minor 30 references
GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data
T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read An adversary who sees only the common-neighbors matrix of an undirected graph can rebuild its adjacency matrix, up to co-squareness, and the GRAND pipeline does this exactly on real data.
desk verdict A promising high-level idea for reconstructing graphs from common-neighbor data, but the central topological algorithms as written are unsound, so the reported results do not follow from the presented methods. 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 central object is the common-neighbors matrix $G^2$, the square of the adjacency matrix, whose diagonal contains vertex degrees and whose off-diagonal entries count length-2 paths. The topological attacks rest on propositions linking row sums of $G^2$ to sums of neighbor degrees and linking matched degrees or common-neighbor counts to forced edge absences or presences; these run iteratively until no entry changes. The spectral attack then uses the fact that the eigenvalues of $G^2$ are the squares of the eigenvalues of $G$, so reconstruction reduces to fixing a sign for each square root, with the greedy choice guided by the Frobenius distance to a binary matrix and to known edges, applying the best low-rank approximation theorem. The introduced equivalence notion, co-squareness, identifies when two graphs share the same $G^2$ and thereby marks the unavoidable ambiguity of the problem.
What would settle it
Run the GRAND pipeline on the Polblogs dataset with the diagonal of $G^2$ treated as unknown and measure the reconstruction error: if the relative absolute error or the common-neighbors error rises, the diagonal of $G^2$ is load-bearing for the claimed attack.
Extended reading notes
Core claim
The paper claims that the common-neighbors matrix $G^2 = A^2$ of an undirected graph $G$ is, in practice, a near-complete blueprint of the adjacency matrix $A$. GRAND combines deterministic topological inferences — such as matching the degree implied by the diagonal of $G^2$ to the reconstructed neighborhood, or matching common-neighbor counts to infer absent edges — with a spectral heuristic that assigns the sign of each eigenvalue of $G^2$ (whose squares are the eigenvalues of $A$) so that the reconstructed matrix is binary and close to any partially known entries. The resulting pipeline recovers $A$ exactly on the Polblogs dataset and produces graphs whose square equals $G^2$ (zero common-neighbors error) on Netscience, Bio-diseasome and Polblogs without any prior knowledge. Because two co-square graphs can never be told apart from $G^2$ alone, the paper argues this is the theoretical ceiling for any reconstruction method.
Load-bearing premise
The attacker is assumed to have the exact, complete common-neighbors matrix $G^2$ including its diagonal, which reveals every vertex's degree; the paper explicitly leaves aside the scenario where the diagonal is unavailable.
Editorial extensions
If this is right
- A protocol that privately outputs the common-neighbors matrix exposes the input graph: secure multiparty computation alone is not a sufficient privacy safeguard for graph data.
- Without prior knowledge, no reconstruction algorithm can beat GRAND's zero common-neighbors error, because co-square graphs are indistinguishable by definition from $G^2$ alone.
- Partial knowledge of existing and non-existing edges monotonically improves reconstruction, with relative error decreasing as the proportion of known entries grows on all four datasets.
- Exact adjacency reconstruction is achievable on at least one real network (Polblogs) with no prior knowledge, so the threat is practical, not merely theoretical.
Reading between the lines
- If the diagonal of $G^2$ were withheld or perturbed (e.g., by differential privacy), the degree-based topological attacks lose their main input; a plausible countermeasure is to protect the diagonal, and a version of GRAND that works from off-diagonal entries alone is a natural test.
- The co-square equivalence class is a privacy ceiling: an ideal defense would randomize within the class so the attacker cannot know which co-square graph is real.
- Because the spectral step is essentially a constrained sign-assignment problem, the success of the greedy heuristic suggests that the suspected NP-hardness may be concentrated in the sign choices, pointing toward approximation algorithms for larger graphs.
- The same reconstruction logic likely transfers to directed graphs by counting common in-, out- or combined neighbors, which would extend the attack to a broader class of relational data.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the problem of reconstructing an undirected graph G from its common-neighbors matrix G2, possibly combined with partial knowledge E0/E1. It introduces GRAND, a pipeline that first applies deterministic “topological attacks” derived from propositions about row sums and neighborhoods, then a spectral sign-assignment heuristic based on the SVD of G2, then a targeted error-forgetting step and a co-square instantiation. The paper also defines co-square equivalence and the Common Neighbors Error metric. It reports experiments on four datasets, claiming exact reconstruction on Polblogs and zero CNE on three datasets for an unknowledgeable adversary.
Significance. If the results held, GRAND would be a strong demonstration that secure multiparty protocols that release a common-neighbors matrix leak the graph structure, and the co-squareness notion would be a useful conceptual tool for graph equivalence. The topological propositions are simple and partially correct, and the decision to evaluate success against the square matrix (CNE) is methodologically appropriate. However, the two core deterministic attacks contain concrete errors (Algorithm 1 deletes true edges; Algorithm 5 does not implement Proposition 3), and the experimental claims are not backed by code, data, or variance information. The paper's main privacy conclusion is therefore not supported as written.
major comments (3)
- [Section 5.1, Algorithm 1 (lines 6 and 21–23)] The degree-combination rule is unsound. From Proposition 1, s = Σ_v G2(u,v) = Σ_{w∈Γ(u)} |Γ(w)|, hence s−d = Σ_{w∈Γ(u)}(|Γ(w)|−1). A neighbor of u can therefore have degree up to s−d+1, but the test G2(v,v) < s−d classifies every such neighbor as a non-candidate and line 22 sets the true edge to 0. In the graph consisting of a single edge (u,v), s=d=1, so s−d=0 and the true edge is deleted. More generally, every edge incident to a leaf is erased. This invalidates the claim in Section 5.1 that the topological attacks “recover G in an exact manner w.r.t. G2”.
- [Section 5.1, Algorithm 5] The pseudocode does not implement Proposition 3. The common-neighborhood part of Proposition 3 requires G2(u,v) − |Γ⋆(u)∩Γ⋆(v)| = |U|, where U is the set of unknown edges incident to u. Algorithm 5 instead tests G2(u,v) = |Γ⋆(u)|+|U| (and the symmetric test with v). These conditions are not equivalent; moreover, U as defined includes v itself when (u,v) is unknown, so the test is not the one stated in Proposition 3 and will fail to fire in many cases where the proposition applies. The NeighborCompletionAttack as written is therefore not the algorithm behind the reported completions.
- [Section 6 and Figures 11–13] The empirical claims (exact reconstruction of Polblogs, zero CNE on Netscience/Polblogs/Bio-diseasome) are averages over 10 runs but no standard deviations are reported, and no code or data are supplied. In view of the errors in Algorithms 1 and 5, the reported numbers cannot be attributed to the algorithm as described. A revision should provide the artifact and corrected algorithms, or substantially weaken the claims.
minor comments (5)
- [Section 3, paragraph 3] The sentence “This problem is more general than the one we solved in this paper, since we have more information” is unclear; additional information makes a problem easier, not more general.
- [Algorithm 5] The variable V is reused as both the set of all vertices and the local set of unknown neighbors of v; rename the local set to avoid confusion.
- [Conclusion, page 20] “Co-squarity” should be “co-squareness”.
- [References] References [14] and [15] are the same Motwani and Sudan paper; one duplicate should be removed.
- [Table 1] Γ2(x) is defined in the notation table but never used in the paper.
Circularity Check
No significant circularity: the CNE metric is the intended success criterion for the co-square reconstruction goal, and the exact Polblogs adjacency claim is evaluated against ground truth rather than against the method's own fitted values.
full rationale
The reconstruction task is explicitly defined as recovering G from the common-neighbors matrix G2 up to co-square equivalence; the CNE metric measures agreement between the reconstructed square G-hat^2 and the input G2, which is the correct objective for that task rather than a circular validation. The stronger experimental claim, exact adjacency reconstruction on Polblogs, is scored with FPR, FNR, and RAE against the original graph, so it is not forced by construction from G2. The spectral-attack weights alpha and beta and the binarization threshold t are manually chosen (beta from known-entry fraction, alpha as its complement, t from the prior work of Erdős et al.), not fitted to a held-out target, so no fitted parameter is renamed as a prediction. The only self-citation, Crypto'Graph [1], is used for motivating the protocol setting and is not load-bearing in the reconstruction derivation. The paper also explicitly flags the assumption that the diagonal of G2 is available and states that the missing-diagonal scenario is not studied; this is a data-availability limitation, not a circular step. Algorithmic soundness concerns raised against Algorithms 1 and 5 are correctness issues, not circularity, and are therefore outside this pass. Overall, the derivation chain is self-contained with respect to circularity.
Assumptions & free parameters
free parameters (2)
- binarization threshold t =
0.5
- spectral weights alpha, beta =
beta = 2*|E*|/|V|^2, alpha = 1 - beta
assumptions (6)
- domain assumption Graph G is undirected, simple, and has no self-loops.
- domain assumption The attacker obtains the exact full common neighbors matrix G2, including its diagonal (degrees).
- domain assumption Prior edge knowledge E0 and E1 is correct.
- standard math Since G is symmetric, G2 shares the same eigenvectors as G, with squared eigenvalues.
- standard math Eckart-Young theorem gives the best rank-k Frobenius approximation.
- ad hoc to paper The greedy sign assignment with the chosen alpha/beta objective finds the true eigenvalues of G.
Cite this review
Pith. "Pith review of GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data." pith.science (2026). https://pith.science/paper/7C22VQ6B
@misc{pith2026241202329,
author = {Pith},
title = {Pith review of: GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data},
year = {2026},
howpublished = {\url{https://pith.science/paper/7C22VQ6B}},
note = {Machine review of arXiv:2412.02329}
}
read the original abstract
Cryptographic approaches, such as secure multiparty computation, can be used to compute in a secure manner the function of a distributed graph without centralizing the data of each participant. However, the output of the protocol itself can leak sensitive information about the structure of the original graph. In particular, in this work we propose an approach by which an adversary observing the result of a private protocol for the computation of the number of common neighbors between all pairs of vertices, can reconstruct the adjacency matrix of the graph. In fact, this can only be done up to co-squareness, a notion we introduce, as two different graphs can have the same matrix of common neighbors. We consider two models of adversary, one who observes the common neighbors matrix only, and a knowledgeable one, that has a partial knowledge of the original graph. Our results demonstrate that secure multiparty protocols are not enough for privacy protection, especially in the context of highly structured data such as graphs. The reconstruction that we propose is interesting in itself from the point of view of graph theory.
Figures
Figures from the paper (11 more)
Reference graph
Works this paper leans on
-
[8]
Reconstructing graphs from neighborhood data
D´ ora Erd¨ os, Rainer Gemulla, and Evimaria Terzi. Reconstructing graphs from neighborhood data. In 2012 IEEE 12th International Conference on Data Mining , pages 231–240, 2012. doi:10.1109/ICDM.2012.154
-
[1]
Sofiane Azogagh, Zelma Aubin Birba, S´ ebastien Gambs, and Marc-Olivier Killijian. Crypto’graph: Leveraging privacy-preserving distributed link prediction for robust graph learn- 20 ing. 2024
work page 2024
-
[2]
Characterizing and recog- nizing exact-distance squares of graphs
Yandong Bai, Pedro P Cort´ es, Reza Naserasr, and Daniel A Quiroz. Characterizing and recog- nizing exact-distance squares of graphs. Discrete Mathematics, 347(8):113493, 2024
work page 2024
- [3]
-
[4]
Fast sequential creation of random realizations of degree sequences
Brian Cloteaux. Fast sequential creation of random realizations of degree sequences. Internet Mathematics, 12(3):205–219, 2016
work page 2016
-
[5]
Applications of link prediction in social networks: A review
Nur Nasuha Daud, Siti Hafizah Ab Hamid, Muntadher Saadoon, Firdaus Sahran, and Nor Badrul Anuar. Applications of link prediction in social networks: A review. Journal of Network and Computer Applications , 166:102716, 2020
work page 2020
-
[6]
Privacy-preserving link prediction
Didem Demirag, Mina Namazi, Erman Ayday, and Jeremy Clark. Privacy-preserving link prediction. In Joaquin Garcia-Alfaro, Guillermo Navarro-Arribas, and Nicola Dragoni, editors, Data Privacy Management, Cryptocurrencies and Blockchain Technology , pages 35–50, Cham,
-
[7]
The approximation of one matrix by another of lower rank
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211–218, 1936
1936
Show all 30 references
-
[9]
A survey of link prediction in social networks
Mohammad Al Hasan and Mohammed J Zaki. A survey of link prediction in social networks. Social network data analytics , pages 243–275, 2011
2011
-
[10]
Matrix analysis
Roger A Horn and Charles R Johnson. Matrix analysis . Cambridge university press, 2012
2012
-
[11]
Recognizing graphic degree sequences and generating all realizations
Zolt´ an Kir´ aly. Recognizing graphic degree sequences and generating all realizations. E¨ otv¨ os Lor´ and University, Tech. Rep. Egres TR-2011-11, 2012
2011
-
[12]
Deeprobust: A pytorch library for adversarial attacks and defenses
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses. arXiv preprint arXiv:2005.06149 , 2020
2005 arXiv
-
[13]
The structural analysis of criminal networks
Duncan McAndrew. The structural analysis of criminal networks. The Social Psychology of Crime, 2021
2021
-
[14]
Computing roots of graphs is hard
Rajeev Motwani and Madhu Sudan. Computing roots of graphs is hard. Discrete Applied Mathematics, 54(1):81–88, 1994
1994
-
[15]
Computing roots of graphs is hard
Rajeev Motwani and Madhu Sudan. Computing roots of graphs is hard. Discrete Applied Mathematics, 54(1):81–88, 1994. URL: https://www.sciencedirect.com/science/article/ pii/0166218X94000239, doi:10.1016/0166-218X(94)00023-9
1994
-
[16]
Biological network analysis with deep learning
Giulia Muzio, Leslie O’Bray, and Karsten Borgwardt. Biological network analysis with deep learning. Briefings in bioinformatics , 22(2):1515–1530, 2021
2021
-
[17]
Using graph theory to analyze biological networks
Georgios A Pavlopoulos, Maria Secrier, Charalampos N Moschopoulos, Theodoros G Soldatos, Sophia Kossida, Jan Aerts, Reinhard Schneider, and Pantelis G Bagos. Using graph theory to analyze biological networks. BioData mining , 4:1–27, 2011
2011
-
[18]
Rossi and Nesreen K
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL: https://networkrepository.com
2015
-
[19]
Silva, Ing-Ren Tsang, George D
Nitai B. Silva, Ing-Ren Tsang, George D. C. Cavalcanti, and Ing-Jyh Tsang. A graph-based friend recommendation system using genetic algorithm. In IEEE Congress on Evolutionary Computation, pages 1–7, 2010
2010
-
[20]
van Dam and Willem H
Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spec- trum? Linear Algebra and its Applications , 373:241–272, 2003. Combinatorial Matrix Theory Conference (Pohang, 2002). URL: https://www.sciencedirect.com/science/article/pii/ S002437950300483X, d...
2003 doi
-
[21]
Graph spectra for complex networks
Piet Van Mieghem. Graph spectra for complex networks . Cambridge university press, 2023
2023
-
[22]
Co-eigenvector graphs
Piet Van Mieghem and Ivan Joki´ c. Co-eigenvector graphs. Linear Algebra and its Appli- cations, 689:34–59, 2024. URL: https://www.sciencedirect.com/science/article/pii/ S0024379524000521, doi:10.1016/j.laa.2024.02.008
2024 doi
-
[23]
Detection of drug-drug interactions by modeling interaction profile fingerprints
Santiago Vilar, Eugenio Uriarte, Lourdes Santana, Nicholas P Tatonetti, and Carol Friedman. Detection of drug-drug interactions by modeling interaction profile fingerprints. PloS one , 8(3):e58321, 2013
2013
-
[24]
Puttaswamy, and Ben Y
Christo Wilson, Bryce Boe, Alessandra Sala, Krishna P.N. Puttaswamy, and Ben Y. Zhao. User interactions in social networks and their implications. In Proceedings of the 4th ACM European Conference on Computer Systems , EuroSys ’09, page 205–218, New York, NY, USA, 2009. Associ...
2009
-
[25]
Ad- versarial examples for graph data: Deep insights into attack and defense
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Ad- versarial examples for graph data: Deep insights into attack and defense. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19 , pages 4816–4...
2019 doi
-
[26]
Gunter, and Bo Li
Xiaojun Xu, Hanzhang Wang, Alok Lal, Carl A. Gunter, and Bo Li. Edog: Adversarial edge detection for graph neural networks. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) , pages 291–305, 2023. doi:10.1109/SaTML54575.2023.00027
2023
-
[27]
Predicting potential drug-drug interactions by integrating chemical, biological, phenotypic and network data
Wen Zhang, Yanlin Chen, Feng Liu, Fei Luo, Gang Tian, and Xiaohong Li. Predicting potential drug-drug interactions by integrating chemical, biological, phenotypic and network data. BMC bioinformatics, 18:1–12, 2017
2017
-
[28]
Adversarial attacks on neural networks for graph data
Daniel Z¨ ugner, Amir Akbarnejad, and Stephan G¨ unnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , KDD ’18, page 2847–2856, New York, NY, USA, 2018. Association...
2018
-
[1980]
URL: https://www.sciencedirect.com/science/article/pii/S0167506008708835, doi:10.1016/S0167-5060(08)70883-5
-
[2023]
Springer International Publishing
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.