Measuring the Privacy Leakage via Graph Reconstruction Attacks on Simplicial Neural Networks (Student Abstract)

Huixin Zhan, Kun Zhang, Keyi Lu, Victor S. Sheng

Abstract

In this paper, we measure the privacy leakage via studying whether graph representations can be inverted to recover the graph used to generate them via graph reconstruction attack (GRA). We propose a GRA that recovers a graph's adjacency matrix from the representations via a graph decoder that minimizes the reconstruction loss between the partial graph and the reconstructed graph. We study three types of representations that are trained on the graph, i.e., representations output from graph convolutional network (GCN), graph attention network (GAT), and our proposed simplicial neural network (SNN) via a higher-order combinatorial Laplacian. Unlike the first two types of representations that only encode pairwise relationships, the third type of representation, i.e., SNN outputs, encodes higher-order interactions (e.g., homological features) between nodes. We find that the SNN outputs reveal the lowest privacy-preserving ability to defend the GRA, followed by those of GATs and GCNs, which indicates the importance of building more private representations with higher-order node information that could defend the potential threats, such as GRAs.

Introduction

As Graph Neural Networks (GNNs) become standard for processing relational data, a critical question emerges: do the resulting node representations leak sensitive structural information? In many real-world applications, graph edges represent sensitive information, such as private friend lists in social networks or confidential transactions in finance. When a user's device computes a node representation (an embedding) and sends it to a server, an adversary might intercept these embeddings to "invert" them and recover the original graph's adjacency matrix.

This study investigates Graph Reconstruction Attacks (GRAs) specifically targeting Simplicial Neural Networks (SNNs). While traditional GCNs and GATs handle pairwise edges, SNNs capture "homological features"—complex, multi-node relationships. We explore whether this richer structural information makes SNNs a greater liability for privacy.

Methodology

The proposed GRA framework utilizes a graph decoder approach. The adversary is assumed to have access to target node representations ($H$) and a "partial graph" ($A^*$) of non-confidential edges. The decoder ($f_{dec}$) reconstructs the adjacency matrix by minimizing the loss between the known partial graph and the reconstructed version. The reconstruction is calculated as: $$A_{rec} = \sigma((\tilde{A}^* H W_a)(\tilde{A}^* H W_a)^T)$$

We compare the reconstruction accuracy across three architectures:

  1. Graph Convolutional Networks (GCNs)
  2. Graph Attention Networks (GATs)
  3. Simplicial Neural Networks (SNNs): Implemented using a higher-order combinatorial Laplacian to perform convolutions on simplicial complexes.

Experimental Setup

The attack performance was evaluated on five benchmark datasets:

  • Citation Networks: CiteSeer, Cora, and PubMed.
  • E-commerce Networks: Amazon Computers and Amazon Photo.

Key Results

The performance of the reconstruction attack was measured using the Area Under the ROC Curve (AUC). A higher AUC indicates a more successful attack and greater privacy leakage.

Table 1: AUC performance of graph reconstruction attacks across different datasets and model architectures.

As shown in Table 1, SNNs consistently exhibited the highest leakage across all datasets. For instance, on the CiteSeer dataset, the GRA achieved an AUC of 98.33% against SNN representations, significantly higher than the 92.24% for GATs and 88.32% for GCNs. Our proposed GRA also outperformed the state-of-the-art baseline (Attack-6) when targeting SNNs and GATs.

Discussion and Conclusion

The results reveal a stark expressivity-privacy trade-off. The features that make SNNs powerful—their ability to encode higher-order topological structures—are exactly what makes them easier to reconstruct. Because the embeddings contain "homological" signatures, the decoder has a clearer roadmap to recover the original edges.

We observed a consistent hierarchy of leakage: SNNs are the most vulnerable, followed by GATs, with GCNs being the most resilient. GATs likely leak more than GCNs because their attention mechanisms explicitly learn to weight specific neighbors, embedding more granular edge-level information.

Future work should investigate higher-order simplices (e.g., triangles) and explore defense mechanisms like Differential Privacy or adversarial training to mask these higher-order signatures without compromising model utility.

Summary updated

Abstract

In this paper, we measure the privacy leakage via studying whether graph representations can be inverted to recover the graph used to generate them via graph reconstruction attack (GRA). We propose a GRA that recovers a graph's adjacency matrix from the representations via a graph decoder that minimizes the reconstruction loss between the partial graph and the reconstructed graph. We study three types of representations that are trained on the graph, i.e., representations output from graph convolutional network (GCN), graph attention network (GAT), and our proposed simplicial neural network (SNN) via a higher-order combinatorial Laplacian. Unlike the first two types of representations that only encode pairwise relationships, the third type of representation, i.e., SNN outputs, encodes higher-order interactions (e.g., homological features) between nodes. We find that the SNN outputs reveal the lowest privacy-preserving ability to defend the GRA, followed by those of GATs and GCNs, which indicates the importance of building more private representations with higher-order node information that could defend the potential threats, such as GRAs.
BibTeX
@inproceedings{zhan2023measuring,
  author = {Huixin Zhan and Kun Zhang and Keyi Lu and Victor S. Sheng},
  title = {{Measuring the Privacy Leakage via Graph Reconstruction Attacks on Simplicial Neural Networks (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i13.27050},
}

Loading related content...

Figure