{"id":"ced7ae2b-5ff6-490a-806a-20cb14cd2595","arxiv_id":"2411.19440","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"GLG reconstructs node features and graph structure from GNN gradients in federated learning, achieving near-perfect recovery for GraphSAGE and high accuracy for GCN under per-node gradient threat models.","lead":"The paper shows that an honest-but-curious server in federated graph learning can reconstruct both node features and the graph structure from the gradients of GNN models, and proposes an attack called GLG. It matters because it demonstrates that exchanging gradients in federated graph learning can leak private graph data, urging caution in privacy-sensitive applications.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5 omits the full row-rank condition on X; its reconstruction formula \\tilde{A}=Xagg X† fails when N > D, so the central theoretical claim is not valid as stated.","rationale":"The reader's weakest assumption is that Node Attacker 2 requires per-node gradients, which the federated averaging protocol in Eq. (9) does not provide. That is a serious scope limitation. However, the single most load-bearing issue for the paper's central claim—Proposition 5—is an internal mathematical flaw: the closed-form reconstruction of \\tilde{A} as Xagg X† silently requires X to be full row rank. This condition is stated in Proposition 3 but omitted from Proposition 5. Without it, the proof does not go through whenever N > D, a common regime for real-world subgraphs. Since this is the main theoretical guarantee behind the headline result that both node features and graph structure can be reconstructed from gradients alone, the claim is unsupported as written. The empirical attack may still be effective, as Table 6 shows, so the paper is not necessarily worthless; it needs a corrected proposition with the rank condition stated, or a weakened claim, plus a disclosure of when the closed-form recovery applies. The threat-model mismatch identified by the reader is also valid and should be disclosed. Therefore the verdict remains CONDITIONAL: the paper requires major revisions but the empirical contribution and other propositions may be salvageable. We partly agree with the reader because both concerns target Proposition 5, but we identify a distinct, more direct correctness risk.","tokens_in":25485,"tokens_out":8244,"duration_ms":71793,"concrete_test":"Construct a minimal GraphSAGE layer with N=3 nodes and D=2 features, e.g., X = [[1,0],[0,1],[1,1]] (rank 2, not full row rank), a normalized adjacency \\tilde{A}=D^{-1}A for a simple path graph, and random weights W1, W2, b. For each node v, compute the first-layer gradients of a cross-entropy loss analytically, recover each x_v via Proposition 2 and each x_agg,v via Proposition 1, form X and Xagg, and compute \\hat{A}=Xagg X†. If \\hat{A} differs from the true \\tilde{A} (compare all entries), Proposition 5 is false without the full row-rank condition. Repeat with N=2, D=3 to confirm the formula works when X is full row rank.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest theoretical result, Proposition 5, claims that Node Attacker 2-GN can reconstruct both X and \\tilde{A} from only first-layer per-node gradients. The proof recovers X via Proposition 2 and Xagg via Proposition 1, then sets \\tilde{A} = Xagg X†. This step is only valid when X has full row rank, so that X X† = I. Proposition 3, the analogous result for GCN, explicitly includes this assumption, but Proposition 5 omits it. When the subgraph has more nodes than feature dimensions (N > D), X is not full row rank, and infinitely many matrices A satisfy Xagg = A X; the closed-form Xagg X† will generally not equal the true \\tilde{A}. In the experiments, 3-hop subgraphs from Facebook and GitHub can easily have N > D, so the claimed exact, prior-free reconstruction of A is not justified by the proof. The empirical success of Algorithm 2 in Table 6 does not repair the proposition, because that algorithm is a regularized optimization procedure, not the closed-form recovery used in the proof. This is a concrete correctness defect in the central claim, independent of the threat-model concern about per-node gradients.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies gradient inversion attacks in federated graph learning for GNNs (GCN and GraphSAGE). It introduces a taxonomy of attackers (Node Attacker 1, Node Attacker 2-G/N/GN, and Graph Attacker-G/N/GN), proposes an attack called GLG that combines dummy-gradient matching with feature-smoothness and sparsity regularizers, and gives analytic propositions for exact reconstruction in several settings. Experiments on Facebook, GitHub, synthetic graphs, and molecular datasets compare GLG against DLG and, on Tox21, against the graph-specific baseline GRAIN, reporting near-perfect reconstruction in several GraphSAGE settings and competitive structure recovery for GCN.","tokens_in":25700,"tokens_out":11499,"duration_ms":95428,"significance":"If the claims hold, the paper would be a valuable contribution to the privacy analysis of federated graph learning: it identifies which gradient information can leak node features and graph topology, and it provides a systematic threat-model taxonomy. The analytic propositions are self-contained linear-algebra derivations with no fitted parameters in the theorems, and the empirical study is broad, including a comparison with the only other graph-specific attack (GRAIN). The observation that GraphSAGE's separate W1/W2 transforms allow individual recovery of aggregated and target-node features (Propositions 1 and 2) is a useful and nontrivial insight. However, the strongest claims are currently not supported because (i) the actual federated protocol in Eq. (9) shares averaged gradients rather than per-node gradients, and (ii) Proposition 5 omits a rank condition needed for the closed-form reconstruction of the adjacency matrix; these issues affect the paper's central node-classification conclusions.","major_comments":[{"comment":"The threat model used for the paper's main node-classification results does not match the federated protocol defined in Eq. (9): the server receives the gradient averaged over the client's batch, while Node Attacker 2 and Propositions 2–5 assume that the attacker receives the gradient of the loss for each node in the subgraph separately. Because the reconstruction formulas in Proposition 2 are ratios of per-sample gradients, they do not survive averaging, and the batched experiments in Appendix F.2 cover only Node Attacker 1 and Graph Attacker-N, not Node Attacker 2. The paper therefore does not establish that the proposed node-classification attacks work in the federated setting it itself defines.","section":"§3.2, §4.1, §5.1"},{"comment":"Proposition 5 is not valid as stated because the reconstruction step \\tilde{A}=X_agg X† requires X to have full row rank so that X X† = I; Proposition 3 explicitly includes this assumption, but Proposition 5 omits it. When the subgraph has more nodes than feature dimensions (N > D), X is not full row-rank, infinitely many matrices A satisfy X_agg = A X, and the closed-form X_agg X† generally does not recover the true \\tilde{A}. The near-perfect results in Table 6 come from Algorithm 2, a regularized optimization procedure, rather than from the closed-form formula used in the proof, so the theoretical claim of exact, prior-free reconstruction of A is not established.","section":"§5.1, Proposition 5"},{"comment":"The proof of Proposition 6 has an algebraic gap: Eq. (43) sets ∇\\tilde{H}L = (X^T)† ∇W2 L^T, but this is only the minimum-norm solution of the underdetermined system in Eq. (41); the true ∇\\tilde{H}L need not lie in the column space of X^T. Consequently, the closed form \\tilde{A} = X(∇W2 L)†(∇W1 L)X† does not follow from the stated assumptions alone. A concrete counterexample (N=D=2, X=I, \\tilde{A}=[[0,1],[1,0]], ∇\\tilde{H}L=diag(1,0)) satisfies X full row-rank but gives a different matrix from the formula. Since Proposition 6 is used to justify the Graph Attacker-G results, this is a load-bearing gap in the theoretical analysis.","section":"§5.2, Proposition 6 and Appendix E"}],"minor_comments":[{"comment":"There is a typo in the phrase 'categorize the attacker furhter'; it should be 'further'.","section":"§4.1"},{"comment":"The expression for the feature-smoothness regularizer is written as a sum of vector differences, but it should be a sum of squared norms (with a factor of 1/2) to equal tr(X L X^T); please clarify the notation.","section":"Eq. (13)"},{"comment":"The symbols used in Table 1 ('!' and '%') are not defined in the caption or text; the reader cannot tell which columns indicate successful reconstruction.","section":"Table 1"},{"comment":"The conclusion states that 'even in batches of size 50, the private data can be reconstructed with high accuracy', but Table 11 reports mean RNMSE of 132±83 (×10^{-2}) for GitHub at B=50, which does not support 'high accuracy' for that dataset; please qualify the claim.","section":"§7"},{"comment":"Some entries in Table 18 contain formatting errors, for example '1.54 ±0.1.48' in the GCN section; these should be corrected for readability.","section":"Appendix G, Table 18"}],"recommendation":"major_revision","confidential_remarks":"The two main concerns are load-bearing: the per-node-gradient assumption in the node-attacker analysis is inconsistent with the averaged-gradient protocol in Eq. (9), and Proposition 5 omits the rank condition that Proposition 3 includes. The third major comment about Proposition 6 is also a correctness issue, though it affects the graph-classification side. The empirical evidence is strong enough that a revision that either (a) revises the threat model to match per-node gradient availability, (b) adds the missing rank conditions and qualifies the theoretical claims, or (c) explicitly restricts the claims to settings where per-node gradients are available, would likely be publishable. The paper header indicates a TMLR publication in 06/2025; if this is a post-publication review, the editor should consider whether an erratum or a follow-up is the appropriate venue for the needed corrections."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this is a serious paper worth engaging, but the headline claim—exact reconstruction of both features and adjacency from per-node gradients—has two holes. First, the federated protocol in Eq. (9) shares averaged gradients, while Node Attacker 2 and Propositions 3-5 assume per-node gradients for each node in the subgraph. Those are different threat models, and the paper's own setup does not deliver the per-node gradients. Second, Proposition 5's reconstruction \\tilde{A}=Xagg X† requires X to have full row rank, and that condition is omitted. When N>D, X is rank-deficient and infinitely many adjacency matrices give the same Xagg; the closed-form equality does not follow. The appendix experiments use 3-hop subgraphs from Facebook/GitHub, where N>D is plausible, so the exactness claim in the main text is not justified by the proof. The empirical Algorithm 2 is a regularized optimization; it doesn't repair the proposition.\n\nWhat is actually new: the paper is among the first to do gradient inversion for GNNs with explicit graph-structure reconstruction, and it gives a systematic taxonomy of threat models for node and graph classification. The analytic results for Node Attacker 1 (Propositions 1-2) and for the known-features/known-structure cases (Propositions 3-4) are correct under their stated rank conditions. The graph classification experiments, especially the Graph Attacker-G results where GraphSAGE is recovered perfectly, are solid. The comparison with GRAIN in Appendix H is useful and goes beyond what most papers do.\n\nThe soft spots are the two above, plus: the regularizers \\alpha,\\beta are grid-searched on the test tasks, and in the no-prior-knowledge TU dataset experiments the dummy initialization is chosen after inspecting results. That doesn't invalidate the empirical attack, but it lowers the evidential value of the GN numbers. No code is released, which matters for a paper whose empirical claims depend on many hyperparameters.\n\nBottom line: this deserves a serious referee and a conditional accept. The threat-model mismatch should be disclosed prominently, the statement of Proposition 5 should be corrected with the rank condition, and the averaged-gradient case should either be attacked directly or explicitly scoped out. If those fixes land, this would be a citable contribution. As it stands, the strongest claims are overstated.","headline":"Worth engaging, but the flagship exact-reconstruction claim conflates per-node with averaged gradients and omits a rank condition.","tokens_in":26255,"tokens_out":1883,"would_cite":false,"duration_ms":15800,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that in federated learning with Graph Neural Networks, a curious server can reconstruct both private node features and graph structure from gradients alone, and proves exact recovery for GraphSAGE when per-node gradients…","keywords":["gradient inversion attack","federated graph learning","graph neural network privacy","GraphSAGE","GCN","node feature reconstruction","graph structure reconstruction","GLG"],"falsifier":"Run Algorithm 2 against a standard federated round where the server sees only the batch-averaged gradient of Eq. (9) with batch size $B \\ge 2$: if neither node features nor adjacency are recovered with near-zero error, Proposition 5's per-node-gradient premise is essential and the claim does not hold under the protocol the paper itself defines.","tokens_in":25264,"feed_emoji":"🔓","tokens_out":8704,"duration_ms":62497,"temperature":0.7,"pith_summary":"Federated learning protects data by sharing only gradients, and this paper asks whether that protection holds for graph data. It argues it does not: a curious server that sees the gradients of a GNN can reconstruct the private node-feature matrix and the adjacency (graph structure) matrix. The paper proves that for GraphSAGE with mean aggregation, per-node first-layer gradients determine both $X$ and the normalized adjacency matrix exactly, with no prior information; for GCN, the same analytic reconstruction works if either the features or the structure is already known and the relevant matrix has full rank. It then proposes GLG, a gradient-matching attack with feature-smoothness and sparsity regularizers, and shows near-perfect reconstruction on social-network, citation, and molecular datasets. If correct, the result undermines the assumption that gradient exchange alone is a safe privacy boundary for federated graph learning.","feed_headline":"GNN gradients leak both node features and graph structure","feed_subtitle":"First-layer gradients alone let a curious server rebuild private GraphSAGE node features and edges.","key_machinery":"The machinery is the ratio identity between weight-gradient and bias-gradient at the first GNN layer. Because the activation is applied elementwise after an affine map, $\\nabla_{(W_1)_i}\\mathcal{L}_v = \\nabla_{b_i}\\mathcal{L}_v \\cdot x_{\\text{agg},v}$ (and similarly for $W_2$ with $x_v$), so the unknown input appears as a ratio of two gradients; this identity is what turns gradient access into exact input recovery. The second piece is the pseudoinverse step $\\tilde{A} = X_{\\text{agg}} X^\\dagger$ (or $X = X_{\\text{agg}} \\tilde{A}^\\dagger$), which reconstructs the missing one of the pair $\\{X, \\tilde{A}\\}$ when the other is known and full rank. For settings without an analytic guarantee, GLG closes the gap with a cosine-similarity gradient-matching loss plus a feature-smoothness regularizer $\\operatorname{tr}(X L X^\\top)$ and a Frobenius sparsity penalty on $A$.","core_discovery":"The central claim is that the first layer of a GNN linearizes the attack: for a GraphSAGE layer with pre-activation $\\tilde{h}_v = x_{\\text{agg},v} W_1^\\top + x_v W_2^\\top + b$, the elementwise nonlinearity makes the gradient with respect to a weight row proportional to the gradient with respect to the corresponding bias entry times the input, so $x_{\\text{agg},v}$ and $x_v$ are recovered by dividing those gradients (Propositions 1 and 2). With per-node gradients for every node in a subgraph, this yields the full matrices $X_{\\text{agg}}$ and $X$, and the normalized adjacency matrix follows as $\\tilde{A} = X_{\\text{agg}} X^\\dagger$ (Proposition 5), so no prior graph knowledge is needed for GraphSAGE. For GCN, the paper proves $\\tilde{A} = X_{\\text{agg}} X^\\dagger$ when $X$ is full row-rank and $X = X_{\\text{agg}} \\tilde{A}^\\dagger$ when $\\tilde{A}$ is full column-rank (Propositions 3 and 4), and for graph classification it proves $\\tilde{A} = X(\\nabla_{W_2}\\mathcal{L})^\\dagger (\\nabla_{W_1}\\mathcal{L}) X^\\dagger$ when $X$ is known and full row-rank (Proposition 6). Empirically, GLG reconstructs node features with RNMSE near $10^{-3}$ and the adjacency matrix with AUC and AP near $1.0$ on Facebook and GitHub for GraphSAGE, and recovers graph structure well for GCN even without a theoretical guarantee.","pith_inferences":["Any privacy-preserving mechanism for federated graph learning must break the per-node gradient structure (e.g., secure aggregation, shuffling, or gradient corruption that destroys the weight-bias ratio) rather than merely adding noise that preserves linearity.","The weight-gradient/bias-gradient ratio is a general probe: any GNN layer with an elementwise, monotone nonlinearity and a linear pre-activation exposes its input through this ratio, so other message-passing designs may inherit the vulnerability.","Proposition 5 requires $X^\\dagger$; when the feature dimension is much smaller than the number of nodes, the recovered $\\tilde{A}$ will be low-rank, so exact topology recovery should degrade as the graph grows—this gives a testable scaling boundary the paper does not explore.","The authors use the term honest-but-curious, but the same formulas would work for a fully malicious server that manipulates weights, so these results likely transfer to stronger threat models."],"forward_implications":["A honest-but-curious server in federated graph learning can fully reconstruct a GraphSAGE client's private node features and graph edges from first-layer per-node gradients, with no prior graph knowledge.","For GCN, the same reconstruction is exact when the attacker has either the features or the structure plus a full-rank condition, so GraphSAGE is not the only vulnerable architecture.","The paper's batched experiments show that larger batch sizes (up to 50) do not by themselves stop feature leakage, so batch-size-based defenses alone are insufficient.","The regularizers are load-bearing: without $L_s$ and $\\|A\\|_F^2$, adjacency reconstruction for GCN drops, indicating that graph-specific priors (smoothness, sparsity) are what make empirical recovery work.","The attack transfers to graph classification and molecular datasets, where structure recovery succeeds when the feature matrix is full row-rank, as Proposition 6 predicts."],"supporting_citations":[{"why":"supplies the dummy-gradient matching objective (DLG) that GLG builds on.","marker":"Zhu et al. (2019)"},{"why":"provides the cosine-similarity loss used in GLG's objective.","marker":"Geiping et al. (2020)"},{"why":"shows ground-truth labels can be inferred from gradients, which the attack assumes.","marker":"Zhao et al. (2020a)"},{"why":"defines the GraphSAGE layer and mean aggregation that Propositions 1, 2, and 5 analyze.","marker":"Hamilton et al. (2017)"},{"why":"defines the GCN layer whose gradients Propositions 1, 3, and 4 analyze.","marker":"Kipf & Welling (2016)"},{"why":"supplies the feature-smoothness regularizer tr(XLX^T) used in the GLG objective.","marker":"Zhang et al. (2022)"},{"why":"GRAIN, the concurrent graph-specific attack compared against in Appendix H.","marker":"Drencheva et al. (2025)"}],"fun_headline_variants":["GLG attack reconstructs node features and graph structure","GNN gradients leak node features and adjacency matrix","First-layer GNN gradients reveal full graph topology","Gradient inversion rebuilds GNN private graph data","GLG: steal graph and node data from GNN gradients"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the attacker receives gradients computed separately for each node in the subgraph; the federated averaging rule in the paper gives the server only one gradient summed over the client's whole batch, and without per-node gradients the exact reconstruction formulas do not apply.","fun_headline_variants_meta":{"raw":{"variants":["GLG attack reconstructs node features and graph structure","GNN gradients leak node features and adjacency matrix","First-layer GNN gradients reveal full graph topology","Gradient inversion rebuilds GNN private graph data","GLG: steal graph and node data from GNN gradients"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000459,"raw_usage":{"total_tokens":2365,"prompt_tokens":1076,"completion_tokens":1289,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":692,"completion_tokens_details":{"reasoning_tokens":1213}},"tokens_in":692,"tokens_out":1289,"duration_ms":8368,"temperature":1.0,"reasoning_tokens":1213,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:11:48.932527+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 against a standard federated round where the server sees only the batch-averaged gradient of Eq. (9) with batch size $B \\ge 2$: if neither node features nor adjacency are recovered with near-zero error, Proposition 5's per-node-gradient premise is essential and the claim does not hold under the protocol the paper itself defines.","supporting_citations":[],"review_version":1}