Pith. sign in

REVIEW 4 major objections 5 minor 21 references

ReconXF: Graph Reconstruction Attack via Public Feature Explanations on Privatized Node Features and Labels

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Feature explanations can be used to reconstruct graph edges even when node features and labels are protected by differential privacy.

desk verdict A real new threat model and sensible denoising adaptation, undercut by inconsistent tables and a missing ablation that leaves the headline causal claim untested. read the letter →

arxiv 2506.02134 v1 pith:ZBWX2OUT submitted 2025-06-02 cs.LG

Rishi Raj Sahoo , Rucha Bhalchandra Joshi , Subhankar Mishra This is my paper
classification cs.LG
keywords graphreconstructionattackfeatureexplanationsdifferentialprivacyneuralnetworksdenoisingautoencoderhomophilyprivacy-preservingmachinelearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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.

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 (4)
  1. [Tables 4 and 5] 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.
  2. [Section 5, Eq. (7) and Section 6] 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.
  3. [Section 4.2.1 and experimental setup] 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.
  4. [Abstract and Section 7] 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.
minor comments (5)
  1. [Section 5, subsection title] The subsection is titled 'Reconstruction using only Explanatio'; 'Explanatio' should be 'Explanation'.
  2. [Tables 4 and 5] 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).
  3. [Table 1] 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.
  4. [Section 6.2.1] 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.
  5. [Section 3.4.1 and Table 6] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the reconstruction objective is external and evaluation is against the ground-truth adjacency matrix.

full rationale

I find no circularity in the paper's derivation chain. The total training loss (Eq. 7) is L_total = L_DAE_X + L_DAE_EX + L_CE, i.e., two denoising-autoencoder reconstruction losses over privatized features and public explanations plus a cross-entropy classification loss on privatized labels. None of these terms is a function of the target adjacency matrix A, and the reported AUC and AP metrics are computed against the true adjacency matrix as an external ground truth (Section 4.3, Evaluation Metrics). The adversary's inputs (E_X, X', Y') are not defined in terms of the estimated adjacency; E_X is produced by a GNN trained on the original graph, which is a side-channel that can carry structural information, but exploiting that side-channel is the attack premise, not a definitional loop. The self-citations to GraphPrivatizer [9] and related prior work [10] appear only as background references and are not load-bearing for the central reconstruction claim; the denoised classification module is explicitly attributed to LPGNN [16], an external work. The absence of an ablation that removes the explanation-based generator weakens the causal attribution that explanations are the active channel, but this is a limitation in experimental isolation, not circularity: the objective does not by construction force the estimated adjacency to match A, as evidenced by the paper's own weak results on Bitcoin-alpha, PubMed, and Ogbn-arXiv (Tables 4 and 5). The evaluation is self-contained against external benchmarks, so the appropriate finding is no significant circularity.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claim depends on several unverified premises: explanations are computed on clean data, homophily makes them informative, the MB rectifier removes LDP bias, RR on predictions is a helpful regularizer, and the denoising autoencoder retains structural signal. These are empirical modeling choices rather than proven facts, and the paper provides no separate validation for any of them.

free parameters (5)
  • hx (feature aggregation hops) = 0, 2, 4, 8, 16
    Chosen per dataset in Appendix A; controls how far features propagate through the reconstructed graph and affects AUC as shown in Figure 8.
  • hy (label aggregation hops) = 0, 2
    Chosen per dataset; affects label-based supervision in Denoised Classification.
  • top-k sparsity ratio = 0.2, 0.4, 0.6, 0.8
    Threshold for keeping the most confident estimated edges in Algorithm 2; selected per dataset and shown to change AUC in Figure 7.
  • k in kNN adjacency initialization = not reported
    FullParam generator is initialized from a kNN graph in Section 3.4.1; k is not specified, and the initialization influences the optimized adjacency.
  • loss weights for L_DAE^X, L_DAE^EX, L_CE = not reported
    Total loss in Equation (7) is a sum with no weights; how the terms are balanced is unstated.
assumptions (6)
  • domain assumption The feature explanation matrix E_X is generated from a GNN trained on the original graph and clean features, then released unprivatized.
    Section 4.2.1 defines the adversary's capabilities; if explanations were generated from privatized data, the structural signal would be weaker.
  • domain assumption Connected nodes have correlated feature-importance patterns (homophily), so explanations carry edge information.
    Section 4.2.4 explicitly bases the attack on 'correlations between explanation patterns and graph topology, particularly in homophilic networks'.
  • domain assumption MB encoding and randomized response are the known privatization mechanisms, and the adversary can debias them.
    Section 3.2 and Figure 3; the MB rectifier assumes knowledge of the encoder's bias.
  • ad hoc to paper Adding randomized response to the model's own predicted labels improves reconstruction by acting as a regularizer.
    Section 5.4 gives an intuitive argument but no derivation or ablation isolating this component.
  • ad hoc to paper The denoising autoencoder can recover enough structural signal from privatized features and explanations to train the adjacency generator.
    This is the core mechanism of ReconXF in Section 5; no theoretical guarantee or isolated ablation is provided.
  • standard math Standard definitions such as GNN message passing (Equation 1) and epsilon-differential privacy (Equation 3).
    Background from Sections 3.1 and 3.2; these are standard and not contested.

how reviews work

0 comments
Cite this review

Pith. "Pith review of ReconXF: Graph Reconstruction Attack via Public Feature Explanations on Privatized Node Features and Labels." pith.science (2026). https://pith.science/paper/ZBWX2OUT

@misc{pith2026250602134,
  author       = {Pith},
  title        = {Pith review of: ReconXF: Graph Reconstruction Attack via Public Feature Explanations on Privatized Node Features and Labels},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZBWX2OUT}},
  note         = {Machine review of arXiv:2506.02134}
}
read the original abstract

Graph Neural Networks (GNNs) achieve high performance across many applications but function as black-box models, limiting their use in critical domains like healthcare and criminal justice. Explainability methods address this by providing feature-level explanations that identify important node attributes for predictions. These explanations create privacy risks. Combined with auxiliary information, feature explanations can enable adversaries to reconstruct graph structure, exposing sensitive relationships. Existing graph reconstruction attacks assume access to original auxiliary data, but practical systems use differential privacy to protect node features and labels while providing explanations for transparency. We study a threat model where adversaries access public feature explanations along with privatized node features and labels. We show that existing explanation-based attacks like GSEF perform poorly with privatized data due to noise from differential privacy mechanisms. We propose ReconXF, a graph reconstruction attack for scenarios with public explanations and privatized auxiliary data. Our method adapts explanation-based frameworks by incorporating denoising mechanisms that handle differential privacy noise while exploiting structural signals in explanations. Experiments across multiple datasets show ReconXF outperforms SoTA methods in privatized settings, with improvements in AUC and average precision. Results indicate that public explanations combined with denoising enable graph structure recovery even under the privacy protection of auxiliary data. Code is available at (link to be made public after acceptance).

Figures

Figures reproduced from arXiv: 2506.02134 by the authors.

Figure 1
Figure 1. ReconXF- Graph Reconstructions Attack via public feature explanations on privatized node features and labels. The red color represents perturbed values via privatization. Graph Neural Networks (GNNs) achieve high performance across many applications but function as black-box models, limiting their use in critical domains like healthcare and criminal justice. Explainability methods address this by providing feature-l… view at source ↗
Figure 2
Figure 2. Adjacency Generator: This generates the estimated adjacency through denoising autoencoder. This takes explanations or [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. ReconXF: This presents the architecture of a privacy-preserving and denoising framework for graph learning. At the user end, the original node features 𝑋 are processed through a MultiBit (MB) encoder, while the labels (𝑌) undergo Randomized Response (RR) to produce privatized versions, 𝑋 ′ and 𝑌 ′ , respectively. The adjacency generator module takes feature explanations 𝐸𝑋 or privatized features 𝑋 ′ , and generates … view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Denoised Classification: This module is used for downstream tasks like node classification to optimize the estimated adjacency. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: AUC vs (𝜖𝑥 , 𝜖𝑦 ) for different explanations for ReconXF and GSEF. The dotted lines denote ReconXF and the solid lines denote GSEF. This demonstrates the effect of explanations in the reconstruction. The reconstruction is guided by maximizing classification performance…
Figure 6
Figure 6. Figure 6: AUC vs (𝜖𝑥 , 𝜖𝑦 ) on given explanation method. The blue dots denote 𝜖𝑦 = 0.01, orange squares denote 𝜖𝑦 = 3.0 and green stars denote 𝜖𝑦 = 8.0. This shows the effect of the privacy budget on the explanation methods along with the datasets. 0.01 3.0 8.0 x 0.54 0.57 0.59 …
Figure 7
Figure 7. Figure 7: Effect of TopK Sparsification. This indicates that with a small portion of the estimated adjacency, we can also perform [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Effect of ℎ-hop. This plot illustrates the difference (Δ𝐴𝑈 𝐶 ) between the values of AUC with and without ℎ-hop aggregation. The ℎ𝑥 and ℎ𝑦 sizes are mentioned inside the bar. provide sufficient protection against explanation-based reconstruction attacks [PITH_FULL_IMA…
Figure 9
Figure 9. Figure 9: ReconXF with TopK: In this framework, TopK Sparsify is used on [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

21 extracted references · 13 canonical work pages

  1. [1]

    David Ahmedt-Aristizabal, Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson. 2021. Graph-Based Deep Learning for Medical Diagnosis and Analysis: Past, Present and Future. Sensors 21, 14 (July 2021), 4758. https://doi.org/10.3390/s21144758

    doi:10.3390/s21144758 2021

  2. [2]

    Karuna Bhaila, Wen Huang, Yongkai Wu, and Xintao Wu. 2024. Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach. arXiv:2309.08569 [cs.LG] https://arxiv.org/abs/2309.08569

    work page Pith review arXiv 2024

  3. [3]

    Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. 2019. Graph neural networks for social recommendation. InThe World Wide Web Conference. 417–426

    work page 2019

  4. [4]

    Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. 2021. SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks. Advances in Neural Information Processing Systems 34 (2021)

    work page 2021

  5. [5]

    Hamilton, Rex Ying, and Jure Leskovec

    William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In NIPS

    work page 2017

  6. [6]

    Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. 2021. Stealing links from graph neural networks. In 30th USENIX Security Symposium (USENIX Security 21). 2669–2686

    work page 2021

  7. [7]

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2021. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv:2005.00687 [cs.LG] https://arxiv.org/abs/2005.00687

    arXiv 2021

  8. [8]

    Jaehyeong Jo, Dongki Kim, and Sung Ju Hwang. 2024. Graph Generation with Diffusion Mixture. arXiv:2302.03596 (2024). https://arxiv.org/abs/ 2302.03596

    arXiv 2024

Show all 21 references
  1. [9]

    Rucha Bhalchandra Joshi, Patrick Indri, and Subhankar Mishra. 2024. GraphPrivatizer: Improved Structural Differential Privacy for Graph Neural Networks. Transactions on Machine Learning Research (2024). https://openreview.net/forum?id=lcPtUhoGYc

    2024

  2. [10]

    Rucha Bhalchandra Joshi and Subhankar Mishra. 2024. Locally and structurally private graph neural networks. Digital Threats: Research and Practice 5, 1 (2024), 1–23

    2024

  3. [11]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR)

    2017

  4. [12]

    Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Medya, and Sayan Ranu. 2024. GNNX-BENCH: Unravelling the Utility of Perturbation-based GNN Explainers through In-depth Benchmarking. arXiv:2310.01794 [cs.LG] https://arxiv.org/abs/2310.01794

    2024 arXiv

  5. [13]

    Srijan Kumar, Francesca Spezzano, V. S. Subrahmanian, and Christos Faloutsos. 2016. Edge Weight Prediction in Weighted Signed Networks. 2016 IEEE 16th International Conference on Data Mining (ICDM) (2016), 221–230. https://api.semanticscholar.org/CorpusID:14025076

    2016

  6. [14]

    Vinod Nair and Geoffrey E Hinton. 2010. Rectified linear units improve restricted boltzmann machines. In ICML 2010. 807–814

    2010

  7. [15]

    Olatunji, Mandeep Rathee, Thorben Funke, and Megha Khosla

    Iyiola E. Olatunji, Mandeep Rathee, Thorben Funke, and Megha Khosla. 2023. Private Graph Extraction via Feature Explanations. Proceedings on Privacy Enhancing Technologies 2023, 2 (April 2023), 59–78. https://doi.org/10.56553/popets-2023-0041

    2023 doi

  8. [16]

    Sina Sajadmanesh and Daniel Gatica-Perez. 2021. Locally Private Graph Neural Networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security (CCS ’21). Association for Computing Machinery, 2130–2145. https://doi.org/10.1145/3460120.3484565

    2021

  9. [17]

    Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93–93

    2008

  10. [18]

    Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. International Conference on Learning Representations (2018)

    2018

  11. [19]

    Hao Wang, Tong Xu, Qi Liu, Defu Lian, Enhong Chen, Dongfang Du, Han Wu, and Wen Su. 2019. MCNE: An End-to-End Framework for Learning Multiple Conditional Network Representations of Social Network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Disc...

    2019

  12. [20]

    Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2020. Explainability in graph neural networks: A taxonomic survey. arXiv preprint arXiv:2012.15445 (2020)

    2020 arXiv

  13. [21]

    Zaixi Zhang, Qi Liu, Zhenya Huang, Hao Wang, Chengqiang Lu, Chuanren Liu, and Enhong Chen. 2021. GraphMI: Extracting Private Graph Data from Graph Neural Networks. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, Zhi-Hua Zhou...

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.