{"id":"2bb9c581-12e5-4bd7-b66a-78c4cf74117d","arxiv_id":"2412.02329","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"An attacker given only the common-neighbors matrix of a graph can rebuild the graph up to co-square equivalence, and knowing a few edges makes the rebuild more accurate.","lead":"This paper presents GRAND, an attack that reconstructs an undirected graph from the matrix of common neighbors between all vertex pairs, up to a new equivalence they call co-squareness. The authors show that even without any prior knowledge, the reconstruction can be near perfect on some real networks, and partial edge knowledge improves it.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's degree-combination rule provably deletes true edges, and Algorithm 5's condition contradicts Proposition 3; the GRAND pipeline as published cannot produce the claimed exact reconstructions.","rationale":"The paper's central claim is that GRAND can reconstruct G, or a co-square graph, from G2 alone, with exact recovery on Polblogs and zero common-neighbors error on three of four datasets. The deterministic topological attacks are the only certified part of the pipeline; if they are unsound, the heuristic spectral stage is bootstrapped from incorrect information and the empirical results are unexplained. Algorithm 1's single-edge and degree-1 counterexamples are not corner cases: the experimental datasets are sparse and contain many degree-1 vertices, so running the published algorithm would erase true edges. Algorithm 5 is not a one-character typo: the prose and Proposition 3 describe a different condition from the pseudocode, so an implementer cannot know which behavior was actually evaluated. No code or data are released, so the reported RAE and CNE numbers cannot be checked against a corrected implementation. This is an internal correctness failure, not a disagreement with consensus, and it does not depend on the availability of the diagonal of G2; it would invalidate the empirical claims even under the authors' own adversary model. The reader's weakest_assumption about diagonal availability is a real scope limitation, but the algorithmic unsoundness is more load-bearing because it breaks the described method under the paper's own assumptions. I therefore keep the reader's REJECT verdict: the claim as written is unsupported, though a corrected re-submission with code and an audit of the topological attacks could justify reconsideration.","tokens_in":16314,"tokens_out":15500,"duration_ms":175310,"concrete_test":"Implement Algorithms 1, 5, and 8 exactly as printed. (1) Run Algorithm 1 on a single edge (1,2) and on a path of length 2 (vertices 1-2-3). If it outputs a 0 on any verified edge, the attack is unsound. (2) Run Algorithm 5 on the graph with V={u,v,a,b,c}, true edges (u,a),(u,b),(v,b),(v,c), with E1={(u,a),(v,b),(v,c)} and E0 containing all other non-edges except (u,b). Here Proposition 3 requires inferring (u,b) and (v,b), but the printed condition G2(u,v)=|Γ⋆(u)|+|U| evaluates 1≠2 and does not fire. (3) If either check reproduces the error, re-run the full GRAND pipeline on Polblogs with corrected algorithms and released code, and recompute the reported RAE and CNE values.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is in the deterministic topological attacks, which are the core of the pipeline (Algorithm 8) and are claimed to reconstruct G exactly before the spectral step. Algorithm 1 is unsound as written. For a vertex u it computes s = Σ_v G2(u,v) and d = G2(u,u), puts v in candidate only if G2(v,v) < s−d, and then sets G⋆(u,v) ← 0 for every non-candidate. On a graph consisting of the single edge (u,v), s=1, d=1, s−d=0, so v is non-candidate and the true edge is erased. More generally, if u has degree 1, then its only neighbor v has degree d_v, the row sum is d_v, and s−d = d_v−1; since d_v ≥ d_v−1, v is always non-candidate, so every edge incident to a degree-1 vertex is marked non-existent. The prose justification is also wrong: a neighbor v contributes d_v−1 to the off-diagonal row sum, not d_v. Algorithm 5 is internally inconsistent with its own Proposition 3: the proposition and the surrounding prose require the condition G2(u,v) − |Γ⋆(u) ∩ Γ⋆(v)| = |U|, where U is the set of unknown edges of u, but the pseudocode tests G2(u,v) = |Γ⋆(u)| + |U|. This makes the algorithm fail to fire in cases where Proposition 3's precondition holds. Since no code or data are provided, the reported perfect reconstruction on Polblogs and the zero-CNE results on three datasets cannot be attributed to the algorithm as described.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16709,"tokens_out":14149,"duration_ms":146425,"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":[{"comment":"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":"Section 5.1, Algorithm 1 (lines 6 and 21–23)"},{"comment":"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":"Section 5.1, Algorithm 5"},{"comment":"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.","section":"Section 6 and Figures 11–13"}],"minor_comments":[{"comment":"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.","section":"Section 3, paragraph 3"},{"comment":"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.","section":"Algorithm 5"},{"comment":"“Co-squarity” should be “co-squareness”.","section":"Conclusion, page 20"},{"comment":"References [14] and [15] are the same Motwani and Sudan paper; one duplicate should be removed.","section":"References"},{"comment":"Γ2(x) is defined in the notation table but never used in the paper.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript addresses a relevant privacy question, but the current version has load-bearing algorithmic errors and no reproducibility artifacts. I recommend major revision rather than rejection because the co-squareness framework and the general idea of combining topological and spectral attacks are salvageable; however, the revision must include corrected pseudocode, a proof or counterexample analysis for each topological inference, and a public code/data artifact before the empirical claims can be evaluated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper has a promising high-level idea, but the topological attacks that carry the pipeline are not sound as written, and without code the reported perfect reconstructions cannot be credited. Even so, the new definitions and the attack model are worth a serious look.\n\nWhat is actually new: the paper introduces co-square equivalence (two graphs with the same common-neighbors matrix, without vertex relabeling), which is a useful lens for reconstruction ambiguity. The knowledgeable-adversary model, where the attacker has partial edge knowledge (E0, E1), is a natural extension of the spectral attack from Erdős et al. [8]. The CNE metric, measuring error in the common-neighbors matrix rather than the adjacency matrix, is the right success criterion for an attack that can at best recover a co-square graph. The general architecture — deterministic topological inferences to seed a spectral sign-assignment heuristic — is sensible in principle.\n\nThe soft spots are real. Algorithm 1 (DegreeCombinationAttack) uses the condition G2(v,v) < s-d to label v a non-neighbor of u, but for an actual neighbor v, the off-diagonal row sum s-d equals the sum of (deg(w)-1) over neighbors w of u. A neighbor can therefore have degree as large as s-d+1, so the inequality should be '> s-d+1', not '< s-d'. On a simple path u-a-b, the rule deletes the genuine edge (u,a). This is not cosmetic; Algorithm 1 is the first step in the topological loop, so it corrupts every subsequent algorithm. Algorithm 5's pseudocode tests G2(u,v) = |Γ*(u)| + |U|, whereas Proposition 3 requires an equality involving the missing common neighbors, making the test fail to fire in cases the proposition covers. There is also no released code or data, so the reported exact reconstruction on Polblogs and zero-CNE on three datasets cannot be checked. The reliance on the exact diagonal of G2 is noted by the authors as a scenario they do not study, but it is a strong assumption for an 'unknowledgeable' adversary. The abstract's claim that MPC is not enough for privacy protection is broader than what the demonstrated setting supports.\n\nBottom line: the paper is a good seed, but as published it is not sound. I would not cite its results, but I would send it to peer review because the flaws are concrete, fixable, and the novel parts could survive careful revision. A referee could demand corrected algorithms and a reproducibility package.","headline":"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.","tokens_in":17206,"tokens_out":6225,"would_cite":false,"duration_ms":62704,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["graph reconstruction","common neighbors matrix","adjacency matrix","privacy attack","secure multiparty computation","co-squareness","spectral graph reconstruction","topological attack"],"falsifier":"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.","tokens_in":16161,"feed_emoji":"🕵️","tokens_out":6684,"duration_ms":63787,"temperature":0.7,"pith_summary":"GRAND is a graph-reconstruction attack: given the matrix that counts common neighbors for every pair of vertices of an undirected graph, it rebuilds the graph's adjacency matrix. The paper proves that this is possible only up to a newly introduced equivalence, co-squareness, because distinct graphs can share exactly the same common-neighbors matrix. On real datasets the pipeline reconstructs the adjacency matrix exactly on Polblogs and achieves zero common-neighbors error on three of four networks even with no prior knowledge. The upshot is that a secure multiparty protocol computing this matrix leaks the underlying graph structure, since the output alone is enough to reproduce it.","feed_headline":"Common-neighbor counts leak the whole graph","feed_subtitle":"A reconstruction attack shows that secure multiparty computation alone cannot protect graph structure.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the baseline spectral reconstruction method and the greedy sign-assignment strategy that GRAND extends and improves.","marker":"[8]"},{"why":"Provides the best low-rank approximation theorem used in the greedy spectral sign choice.","marker":"[7]"},{"why":"Network data repository that supplies the Netscience and Bio-diseasome datasets used in the experiments.","marker":"[18]"},{"why":"Source of the Polblogs and Cora datasets used in the experiments.","marker":"[12]"},{"why":"Documents co-spectral graphs, motivating why spectral information alone cannot uniquely determine a graph and prompting the co-squareness notion.","marker":"[20]"},{"why":"Gives the uniqueness theorem for positive semidefinite square roots, showing that the linear-algebraic solution is not the binary adjacency matrix sought.","marker":"[10]"},{"why":"Identifies the Intersection Pattern problem, one of the known hard problems the reconstruction problem is suspected to reduce to.","marker":"[3]"},{"why":"Identifies the Square Root Graph problem, another NP-hardness anchor for the suspected complexity of the reconstruction.","marker":"[14]"}],"fun_headline_variants":["Common neighbors reveal graphs despite secure multiparty computation","Graph reconstruction from neighbor counts defeats MPC privacy","Co-square ambiguity is the only shield for graph privacy","A^2 leaks adjacency: practical graph reconstruction attack"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Common neighbors reveal graphs despite secure multiparty computation","Graph reconstruction from neighbor counts defeats MPC privacy","Co-square ambiguity is the only shield for graph privacy","A^2 leaks adjacency: practical graph reconstruction attack"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000436,"raw_usage":{"total_tokens":2201,"prompt_tokens":910,"completion_tokens":1291,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":1231}},"tokens_in":526,"tokens_out":1291,"duration_ms":10834,"temperature":1.0,"reasoning_tokens":1231,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:36:33.033099+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Reconstructing graphs from neighborhood data","cited_arxiv_id":null,"evidence_quote":"Supplies the baseline spectral reconstruction method and the greedy sign-assignment strategy that GRAND extends and improves."},{"cited_title":"Rossi and Nesreen K","cited_arxiv_id":null,"evidence_quote":"Network data repository that supplies the Netscience and Bio-diseasome datasets used in the experiments."},{"cited_title":"Chv´ etal","cited_arxiv_id":null,"evidence_quote":"Identifies the Intersection Pattern problem, one of the known hard problems the reconstruction problem is suspected to reduce to."},{"cited_title":"Computing roots of graphs is hard","cited_arxiv_id":null,"evidence_quote":"Identifies the Square Root Graph problem, another NP-hardness anchor for the suspected complexity of the reconstruction."}],"review_version":1}