{"id":"86009f47-da42-435a-b8c4-cd4129071757","arxiv_id":"2506.02134","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"ReconXF reconstructs graph structure from public feature explanations and differentially private node features and labels, outperforming prior attacks on Cora and Citeseer.","lead":"This paper introduces a graph reconstruction attack called ReconXF, which uses public feature explanations to recover hidden edges when node features and labels have been privatized with differential privacy. The authors report that the attack outperforms prior methods on several benchmark graphs, suggesting that releasing explanations can undermine privacy protections.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The causal role of public explanations is not isolated: ReconXF's gains may come from its denoised feature-based generator alone, so the claimed explanation-driven DP bypass is untested.","rationale":"The reader's weakest assumption was that connected nodes have correlated explanation patterns, i.e., that the attack depends on homophily and explanation fidelity. My concern is closely related but more specific: the paper never isolates the explanation channel from the denoised feature channel. ReconXF is a two-generator system; its feature generator uses the same denoising autoencoder machinery as the explanation generator. On homophilic datasets with rich features, the feature generator alone could plausibly recover structure from debiased privatized features, especially with h-hop aggregation and RR-label supervision. Slaps is the only feature-only baseline, but it lacks all of these components, so it cannot attribute the improvement to explanations. The row-permutation test is decisive because it destroys the correlation between explanation patterns and node identity while preserving the marginal statistics of E_X and the full training pipeline. If the attack survives permutation, the central claim that public explanations enable reconstruction under DP is false; the attack would instead demonstrate that denoised privatized features leak structure. Given this unresolved causal attribution, the paper remains CONDITIONAL, matching the reader's verdict. I do not see a reason to move to ACCEPT or REJECT: the threat model is plausible, the empirical numbers are suggestive, but the missing ablation and the near-random results on Ogbn-arXiv and Bitcoin-alpha mean the universal statement in the abstract is not yet supported. The reader's call for code, corrected table labels, error bars, and an ablation of the denoising component is appropriate; the permutation test is the sharpest version of that ablation and should be required before the central claim is accepted.","tokens_in":14836,"tokens_out":6788,"duration_ms":67479,"concrete_test":"Run ReconXF on Cora and Citeseer (Grad and Grad-I explainers, epsilon_x = epsilon_y = 0.01) with the rows of E_X randomly permuted among nodes, keeping X', Y', and all hyperparameters fixed. Repeat with 10 random permutations and report mean and std of AUC/AP. Also run the same setting with the explanation generator ablated entirely. If permuted or ablated AUC remains within 0.02 of the reported 0.944/0.982, the explanation matrix is not load-bearing; if AUC drops toward the GSEF-private or Slaps level, the explanation signal is genuinely exploited.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that public explanations are the channel that survives DP privatization of features and labels. But ReconXF (Sec. 5, Eq. 7) jointly trains a feature-based adjacency generator and an explanation-based generator, both through denoising autoencoders, with h-hop-aggregated classification on privatized labels. No ablation removes the explanation generator, and Tables 4-5 report only the full pipelines. Since Cora and Citeseer are homophilic with high feature-to-structure ratios, the feature-based DAE may recover edges from debiased feature similarity alone, making the explanation matrix redundant. The Slaps baseline is not a controlled comparison: it lacks the MB-rectifier, h-hop aggregation, RR-label supervision, and TopK sparsification. Thus the load-bearing premise that 'public explanations combined with denoising' cause the leakage is not established. A row-wise permutation of E_X with X' and Y' fixed would settle whether explanations are the active information channel or whether the method works just as well from privatized features alone.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes ReconXF, a graph reconstruction attack that recovers the adjacency matrix from public feature-level explanations together with differentially private node features and labels. The method combines two adjacency generators (one on privatized features, one on explanations), both built on denoising autoencoders, with h-hop aggregation, an MB-rectifier for debiasing, randomized response on predicted labels, and TopK sparsification. The authors report AUC and AP results across Cora, Citeseer, Bitcoin-alpha, PubMed, and Ogbn-arXiv, and claim 5-15% improvements over state-of-the-art baselines in privatized settings.","tokens_in":15053,"tokens_out":4651,"duration_ms":49227,"significance":"If the central claim holds, the paper identifies a practically important privacy leak: releasing feature explanations can enable graph structure recovery even when node features and labels are DP-privatized. The threat model is novel and relevant to regulatory settings that mandate explanation transparency. The paper also contributes a concrete attack pipeline and evaluates multiple explanation methods and privacy budgets. However, the causal role of explanations is not isolated, and the quantitative support for the headline claims is weakened by inconsistent table placement and missing ablations. The strengths are the timely threat model and the breadth of datasets/explainers considered; the weaknesses are experimental, not foundational to the problem formulation.","major_comments":[{"comment":"The ReconXF and ReconX results are placed in the 'Real AUC'/'Real AP' columns with dashes under 'Private AUC'/'Private AP', even though the attack is designed for and evaluated with privatized features and labels. The text in RQ2 states that the method outperforms state-of-the-art methods on private datasets, but the table as printed compares ReconXF/ReconX against baselines in the 'Real' columns, not against the baselines' private-column values. This undermines the central quantitative claim (e.g., Cora Grad AUC 0.944 vs GSEF private 0.910). The column semantics must be clarified and the results placed in the correct columns, or the comparison is not valid.","section":"Tables 4 and 5"},{"comment":"No ablation removes the explanation-based generator from ReconXF. The total loss L_total = L_DAE^X + L_DAE^EX + L_CE jointly trains a feature-based and an explanation-based generator, both with denoising, h-hop aggregation, RR supervision, and TopK sparsification. Since the baseline Slaps lacks these components, the reported improvements could come entirely from the denoised feature generator, the MB-rectifier, h-hop aggregation, or RR regularization rather than from public explanations. A feature-only variant of ReconXF (with the explanation branch removed but all other components kept) and an explanation-only variant with identical denoising components are needed to establish that explanations are the active information channel.","section":"Section 5, Eq. (7) and Section 6"},{"comment":"The paper does not specify whether the public explanation matrix E_X is generated from a model trained on clean data or on privatized data. The threat model states that explanations are generated post-hoc and remain unprivatized, but if the motivating scenario privatizes features and labels before GNN training, the deployed model would produce explanations based on privatized inputs. If the experiments use clean-data explanations, the attack is evaluated under an assumption that may not match the privacy-protection scenario described. This point should be clarified and, ideally, experiments should include a variant where E_X is computed from privatized features/labels.","section":"Section 4.2.1 and experimental setup"},{"comment":"The claim that ReconXF achieves '5-15% improvements' over state-of-the-art methods is not supported by the tables. For example, Cora Grad AUC 0.944 vs GSEF private 0.910 is a relative improvement of about 3.7%, and Citeseer Grad AUC 0.982 vs 0.959 is about 2.4%. The paper should either report the exact calculation behind the 5-15% figure or temper the claim to match the reported numbers.","section":"Abstract and Section 7"}],"minor_comments":[{"comment":"The subsection is titled 'Reconstruction using only Explanatio'; 'Explanatio' should be 'Explanation'.","section":"Section 5, subsection title"},{"comment":"No standard deviations or error bars are reported, so the reader cannot assess the stability of the reported AUC/AP values, especially for differences that are small (e.g., 0.944 vs 0.910 in Cora Grad).","section":"Tables 4 and 5"},{"comment":"The checkmark/cross notation for the ReconXF row is not self-explanatory; the caption should define what each checkmark means for the proposed method's inputs versus the task columns.","section":"Table 1"},{"comment":"The deviation note for PubMed says 'Our other ReconX has performed best for this setting,' but Table 4 shows ReconX PubMed Grad AUC 0.760 while GSE is 0.738; the sentence should explicitly name ReconX and quantify the margin.","section":"Section 6.2.1"},{"comment":"The FullParam generator initializes the adjacency with a kNN graph, but the value of k in that kNN construction is not listed in the hyperparameter table, so the experimental configuration is incomplete.","section":"Section 3.4.1 and Table 6"}],"recommendation":"major_revision","confidential_remarks":"The self-citation to GraphPrivatizer is contextually appropriate and does not appear to be a novelty concern. The main issue is experimental: the table column placement and missing ablations make the central claim about the causal role of explanations difficult to verify. These are fixable within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This one formalizes a genuinely new threat model — public feature explanations plus DP-privatized features and labels — and adapts GSEF with denoising autoencoders. That is a real contribution, and the paper is worth discussing. But the current empirical presentation does not support the headline claims, and the causal story for why the attack works is untested.\n\nThe good parts: The threat model is realistic and not covered by GSEF or SLAPS, which assume clean auxiliary data. The explanation-only variant (ReconX) performs competitively, sometimes beating the full ReconXF, which suggests explanations carry structural signal. The paper also reports dataset-dependent failures (PubMed, Ogbn-arXiv) rather than hiding them. That is honest.\n\nThe soft spots, in order of severity. First, Tables 4 and 5 are internally inconsistent. Baselines have separate 'Real AUC' and 'Private AUC' columns; ReconXF and ReconX appear only under 'Real AUC' with dashes in the private column. The text compares them to privatized baselines, so either the numbers are mislabeled or the comparison is invalid. This needs a fix before anything else. Second, there is no ablation isolating the explanation generator. The stress-test note is right: because ReconXF jointly trains a feature generator and an explanation generator, we cannot tell whether the explanation is the active channel or the denoised feature generator alone recovers edges. A variant with only the feature branch (same denoising, h-hop, RR supervision) would settle RQ2. ReconX does not substitute for this because it removes the feature branch entirely. Third, no error bars or code, so we cannot assess stability or reproducibility. Fourth, the abstract's 5–15% improvement claim is contradicted by the paper's own numbers on PubMed, where ReconXF is below GSE in several settings. The authors do acknowledge some deviations in Section 6.2.1, but the abstract and conclusion overstate the result. The attack works when homophily is strong and explanations are faithful; on Bitcoin-alpha and Ogbn-arXiv it is near chance.\n\nWho is this for? People working on privacy attacks on GNNs and explanation leakage. It deserves serious referee time, but the revision needs to be more than cosmetic: fix the tables, add the feature-only ablation, release code and error bars, and temper the claims. As it stands, this is a promising draft rather than a finished result.","headline":"A real new threat model and sensible denoising adaptation, undercut by inconsistent tables and a missing ablation that leaves the headline causal claim untested.","tokens_in":15586,"tokens_out":5140,"would_cite":false,"duration_ms":42753,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Feature explanations can be used to reconstruct graph edges even when node features and labels are protected by differential privacy.","keywords":["graph reconstruction attack","feature explanations","differential privacy","graph neural networks","denoising autoencoder","homophily","privacy-preserving machine learning"],"falsifier":"Train the explanation model on privatized features only, or on a graph with no edges, then run ReconXF on the resulting explanations: if AUC stays high, the leakage is not coming from explanations, while a drop to chance confirms the clean-explanation and homophily assumption. A second test is to run the attack on a heterophilic graph whose connected nodes have opposite labels; the paper's mechanism predicts near-random reconstruction.","tokens_in":14592,"feed_emoji":"🕸️","tokens_out":8661,"duration_ms":80185,"temperature":0.7,"pith_summary":"ReconXF claims that releasing feature explanations alongside differentially private node data undoes the privacy protection: an adversary who sees only the public explanation matrix, privatized features, and privatized labels can still reconstruct the graph's edges. The paper shows that existing explanation-based attacks, such as GSEF, lose much of their accuracy when features and labels are DP-noised, and that adding denoising components restores the attack. On Cora and Citeseer the reconstructed adjacency reaches AUC values near 0.94--0.98 even at privacy budgets $\\epsilon_x=\\epsilon_y=0.01$, beating prior methods by 5--15% in AUC and average precision. If true, the result matters because transparency obligations (explanations) and privacy mechanisms can silently combine into a leak that neither protects alone.","feed_headline":"Public explanations let attackers rebuild private graphs","feed_subtitle":"A new attack recovers edges even when features and labels are DP-noised, beating prior methods by 5-15%.","key_machinery":"The machinery is the explanation matrix $E_X$, a binary feature-importance mask, combined with a denoising-autoencoder adjacency generator: two generators (FullParam and MLP-Diag) produce candidate adjacency matrices from explanations and from rectified private features, a Multi-Bit rectifier debiases the privatized features, $h$-hop aggregation propagates information over the estimated graph, and a denoised classification module applies randomized response to predicted labels as a regularizer. The adjacency is optimized jointly to reconstruct features and explanations and to classify nodes under privatized labels, which lets structural signals in explanations compensate for DP noise.","core_discovery":"The paper's central claim is that the structural signal in feature explanations survives differential privacy applied to features and labels, so graph topology can be recovered from the tuple $(E_X, X', Y')$. The authors define an adversary with no access to the true adjacency, model parameters, or clean data, and then construct ReconXF, which feeds the explanation matrix and rectified private features through two adjacency generators, denoises them with autoencoders, and supervises the resulting adjacency with a classification loss on randomized-response labels. Their experiments show that this pipeline outperforms GSEF and SLAPS in the privatized setting, with, for example, Cora Grad AUC of 0.944 and Citeseer Grad AUC of 0.982 at $\\epsilon_x=\\epsilon_y=0.01$, and that gradient-based explanations leak more structure than GLime. The paper concludes that releasing explanations without privatizing them can undermine the protection offered by DP on auxiliary data.","pith_inferences":["Editorial inference: a direct defense this result points to is privatizing or coarsening the explanation matrix itself, since the attack's signal enters through $E_X$.","Editorial inference: because graph-aware gradient explainers embed message passing into their attributions, any such explainer is likely to leak adjacency information no matter how features and labels are protected.","Editorial inference: a testable extension is to run ReconXF on a deliberately heterophilic graph where connected nodes carry opposite labels; the paper's homophily mechanism predicts AUC near chance, which would separate explanation leakage from other signals.","Editorial inference: the 5--15% margins are measured against GSEF and SLAPS at fixed explanation methods; comparing against an attacker with access to clean auxiliary data from a public background graph would bound how much of the recovery is due to denoising versus the homophily assumption."],"forward_implications":["Existing explanation-based reconstruction attacks degrade noticeably when features and labels are privatized; attacks must denoise the private inputs to remain effective.","Releasing unprivatized feature explanations, especially gradient-based ones, can expose graph structure even at $\\epsilon_x=\\epsilon_y=0.01$.","The attack works best on homophilic graphs with high feature-to-structure ratios (Cora, Citeseer) and approaches chance on heterophilic or low-ratio graphs (Bitcoin-alpha, PubMed, Ogbn-arXiv).","GLime explanations preserve the privacy-utility trade-off better than Grad and Grad-Input, but they also carry less structural signal for reconstruction.","Using a top-K subset of the estimated adjacency and tuning the $h$-hop aggregation size improves reconstruction and classification under privacy."],"supporting_citations":[{"why":"GSEF is the prior explanation-based graph-stealing attack that ReconXF adapts; it supplies the attack baseline and the two-generator structure.","marker":"[15]"},{"why":"SLAPS supplies the self-supervised structure-learning baseline and the FullParam/MLP-Diag adjacency generator designs used here.","marker":"[4]"},{"why":"LPGNN supplies the locally private GNN formulation and randomized-response label handling behind the denoised classification module.","marker":"[16]"},{"why":"RGNN establishes graph learning under local differential privacy on features and labels, the setting the threat model extends.","marker":"[2]"},{"why":"Cora, Citeseer, and PubMed come from this citation-network collection and provide the main homophilic evaluation graphs.","marker":"[17]"},{"why":"Ogbn-arXiv provides the large heterophilic dataset used to test whether the attack generalizes beyond homophilic graphs.","marker":"[7]"},{"why":"Bitcoin-alpha supplies the trust-network dataset with weak homophily that shows where reconstruction approaches chance.","marker":"[13]"}],"fun_headline_variants":["Public explanations enable graph reconstruction despite DP noise","ReconXF recovers graph edges from explanations on DP data","Feature explanations bypass differential privacy in GNNs","Graph structure leaks via public explanations and denoising","Attack rebuilds private graphs from explanation outputs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The attack only works if the explanation matrix was generated by a model that saw the true graph and clean features, and if connected nodes tend to have similar feature-importance patterns; when that correlation is weak, the paper's own results on Bitcoin-alpha, PubMed, and Ogbn-arXiv fall to about 0.50--0.62 AUC.","fun_headline_variants_meta":{"raw":{"variants":["Public explanations enable graph reconstruction despite DP noise","ReconXF recovers graph edges from explanations on DP data","Feature explanations bypass differential privacy in GNNs","Graph structure leaks via public explanations and denoising","Attack rebuilds private graphs from explanation outputs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000666,"raw_usage":{"total_tokens":3050,"prompt_tokens":965,"completion_tokens":2085,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":2012}},"tokens_in":581,"tokens_out":2085,"duration_ms":14695,"temperature":1.0,"reasoning_tokens":2012,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:30:07.919862+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train the explanation model on privatized features only, or on a graph with no edges, then run ReconXF on the resulting explanations: if AUC stays high, the leakage is not coming from explanations, while a drop to chance confirms the clean-explanation and homophily assumption. A second test is to run the attack on a heterophilic graph whose connected nodes have opposite labels; the paper's mechanism predicts near-random reconstruction.","supporting_citations":[{"cited_title":"Olatunji, Mandeep Rathee, Thorben Funke, and Megha Khosla","cited_arxiv_id":null,"evidence_quote":"GSEF is the prior explanation-based graph-stealing attack that ReconXF adapts; it supplies the attack baseline and the two-generator structure."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"SLAPS supplies the self-supervised structure-learning baseline and the FullParam/MLP-Diag adjacency generator designs used here."},{"cited_title":"Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach","cited_arxiv_id":"2309.08569","evidence_quote":"RGNN establishes graph learning under local differential privacy on features and labels, the setting the threat model extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bitcoin-alpha supplies the trust-network dataset with weak homophily that shows where reconstruction approaches chance."}],"review_version":1}