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:
- Graph Convolutional Networks (GCNs)
- Graph Attention Networks (GATs)
- 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.
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