PaperlayerView exact revision on arXiv

Source-linked AI summary

Inference Attacks Against Graph Neural Networks

Zhikun Zhang, Min Chen, Michael Backes, Yun Shen, Yang Zhang

arXiv:2110.02631v1cs.CRcs.LGstat.ML

TL;DR

Because graph embeddings are shared for downstream analysis while their privacy implications remain unresolved, this paper investigates what information they reveal. It develops three inference attacks and an embedding-perturbation defense, reporting successful inference and reconstruction alongside mitigation without noticeable graph-classification performance degradation.

  • Problem

    The paper asks whether graph embeddings shared for downstream analysis leak sensitive structural information about their source graphs.

    Source: §3.1 · p. 3

  • Method

    The paper develops attacks for property inference, subgraph membership inference, and graph reconstruction, and perturbs shared embeddings with Laplace noise as a defense.

    Source: §1 · p. 2, §8 · p. 11

  • Results

    The attacks infer graph properties and subgraph membership and reconstruct structurally similar graphs; examples reach 0.89 attack accuracy on the DD dataset and 0.98 attack AUC on the DD dataset.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Embedding perturbation mitigates the three inference attacks without noticeable performance degradation for graph classification tasks.

    Source: §1 · p. 2, §10 · p. 13

    The threat model assumes black-box access and an auxiliary dataset from the target graph's distribution, although attacks are also reported effective across distributions.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

Graph is an important data representation ubiquitously existing in the real world. However, analyzing the graph data is computationally difficult due to its non-Euclidean nature. Graph embedding is a powerful tool to solve the graph analytics problem by transforming the graph data into low-dimensional vectors. These vectors could also be shared with third parties to gain additional insights of what is behind the data. While sharing graph embedding is intriguing, the associated privacy risks are unexplored. In this paper, we systematically investigate the information leakage of the graph embedding by mounting three inference attacks. First, we can successfully infer basic graph properties, such as the number of nodes, the number of edges, and graph density, of the target graph with up to 0.89 accuracy. Second, given a subgraph of interest and the graph embedding, we can determine with high confidence that whether the subgraph is contained in the target graph. For instance, we achieve 0.98 attack AUC on the DD dataset. Third, we propose a novel graph reconstruction attack that can reconstruct a graph that has similar graph structural statistics to the target graph. We further propose an effective defense mechanism based on graph embedding perturbation to mitigate the inference attacks without noticeable performance degradation for graph classification tasks. Our code is available at https://github.com/Zhangzhk0819/GNN-Embedding-Leaks.

1 Introduction

Graph embeddings are shared for downstream analysis, but their privacy implications were unresolved. The paper investigates three attacks that infer graph properties, test subgraph membership, and reconstruct similar graphs, then evaluates an embedding-perturbation defense.

1 Introduction

  • Graph neural networks aggregate neighborhood information into node embeddings and then form graph embeddings that are shared for downstream tasks, although their privacy implications remain unanswered.The introduction notes that graph embeddings are empirically considered sanitized because they compress the whole graph to a single vector.Source: §1 · p. 1
  • The paper investigates property inference, subgraph membership inference, and reconstruction of graphs with structural properties similar to the target.The subgraph attack addresses the challenge of comparing a graph embedding vector with a graph-shaped query.Source: §1 · pp. 1–2
  • 0.89 attack accuracy on the DD dataset and 0.98 attack AUC on the DD dataset demonstrate property- and subgraph-inference effectiveness; local clustering coefficient distribution cosine similarity reaches 0.99.The proposed defense mitigates all three attacks without noticeable performance degradation for graph classification tasks.Source: §1 · p. 2
  • The proposed defense adds well-calibrated Laplace noise to graph embeddings before sharing them with third parties.Experiments report mitigation of all three attacks without noticeable graph-classification performance degradation.Source: §1 · p. 2

2 Preliminaries

The preliminaries define graph and embedding notation, then explain how GNNs construct node and graph representations. They describe message passing and graph pooling, including global and hierarchical pooling approaches.

2.1 Notations

  • A graph is denoted G = ⟨V,A,X⟩, with nodes V, adjacency matrix A, and attributes matrix X; H_u and H_G denote node and whole-graph embeddings.Graph classification uses the whole-graph embedding to determine a graph label, while node classification uses node embeddings.Source: §2.1 · p. 2, §2.2 · p. 2

2.2 Graph Neural Network

  • GNNs learn graph representations by aggregating information from neighboring nodes, and graph embeddings support tasks such as graph classification.For graph classification, node embeddings are further transformed into a whole-graph embedding to predict the graph label.Source: §2.2 · p. 2

2.2.1 Message Passing

  • Message passing initializes node embeddings from attributes, aggregates neighborhood messages, and updates each node so that K steps incorporate information from K-hop neighbors.Aggregation can use sum, mean, symmetric normalization, or attention; update operations include weighted combination, concatenation, and interpolation.Source: §2.2.1 · pp. 2–3

2.2.2 Graph Pooling

  • Graph pooling aggregates node embeddings into a graph embedding; hierarchical pooling instead clusters nodes iteratively to retain structural information.DiffPool adds link-prediction and assignment-entropy objectives, while MinCutPool uses a minimum-cut objective; hierarchical models incorporate pooling losses during training.Source: §2.2.2 · p. 3

3 Threat Model and Attack Taxonomy

The paper asks whether shared whole-graph embeddings leak sensitive structural information. Its threat model gives an adversary an embedding and auxiliary graphs, and its taxonomy distinguishes three inference goals.

3.1 Motivation

  • Graph embeddings are shared in settings such as embedding services, pretrained systems, and model partitioning, while their security and privacy implications remain unanswered.The motivating question is whether embeddings designed to preserve graph-level similarity also leak structural information about the source graph.Source: §3.1 · p. 3

3.2 Threat Model

  • The adversary obtains a whole-graph embedding and is assumed to have same-distribution auxiliary graphs and black-box access to the target embedding model.The paper also reports that attacks remain effective when auxiliary data comes from a different distribution.Source: §3.2 · p. 4

3.3 Attack Taxonomy

  • The taxonomy covers inferring basic graph properties, determining whether a major subgraph is contained in the target, and reconstructing a graph with similar structural statistics.Small subgraphs such as triangles or stars are excluded from the membership attack because they occur in almost all graphs.Source: §3.3 · p. 4, Figure 1 · p. 4

4 Property Inference Attack

The property inference attack uses a target graph embedding to predict graph properties such as node count, edge count, and density. FAP shares a feature extractor across property-specific prediction layers and is trained on labeled auxiliary embeddings.

4.1 Attack Overview

  • FAP takes the target graph embedding as input and predicts the graph’s properties, including node count, edge count, and density.Source: §4.1 · pp. 4–5

4.2 Attack Model FAP

  • FAP uses a feature extractor with shared parameters and parallel prediction layers, each responsible for one graph property.Source: §4.2 · p. 5, Figure 2 · p. 5
  • Training uses embeddings from auxiliary graphs labeled with their properties, with continuous property values bucketized into classes such as five density bins.Source: §4.2 · p. 5

5 Subgraph Inference Attack

The subgraph inference attack predicts whether a subgraph of interest is contained in the target graph, assuming it constitutes a major part of that graph. FAS embeds the subgraph, combines it with the target embedding, and classifies containment.

5.1 Attack Overview

  • The attack tests whether a subgraph of interest is contained in the target graph and focuses on subgraphs constituting a major part, rather than small common patterns.Source: §5.1 · p. 5
  • FAS transforms the subgraph into an embedding, aggregates it with the target embedding, and sends the result to a binary classifier.Source: Figure 3 · p. 5, §5.1 · p. 5, §5.2 · p. 6

5.2 Attack Model FAS

  • Training pairs target-embedding inputs with positive subgraphs sampled from an auxiliary graph and negative subgraphs sampled from another auxiliary graph.Source: §5.2 · pp. 5–6
  • The attack feature vector can combine the embeddings through concatenation, element-wise difference, or Euclidean distance before classification.Source: §5.2 · p. 6

6 Graph Reconstruction Attack

The graph reconstruction attack decodes the target embedding into a graph intended to have similar structural statistics, such as degree distribution and local clustering coefficient. FAR uses a graph auto-encoder with graph matching to train and fine-tune its decoder.

6.1 Attack Overview

  • FAR decodes the target graph embedding into a reconstructed graph with similar structural statistics, such as degree distribution and local clustering coefficient.Source: §6.1 · p. 6, Figure 4 · p. 6

6.2 Attack Model FAR

  • The graph auto-encoder adds graph matching to align node orderings before comparing auxiliary and reconstructed adjacency matrices.Source: §6.2 · p. 6
  • The attack’s graph matching has O(n^4) time and space complexity, limiting its application to graphs with tens of nodes; it currently reconstructs structure, not node features.Source: §6.2 · p. 7

7 Evaluation

The evaluation tests property inference, subgraph inference, and graph reconstruction on real-world graph datasets using several graph embedding models. Across these attacks, the reported results show substantial leakage of graph properties and structure.

7.1 Experimental Setup

  • Experiments use five TUDataset graph collections and three graph embedding models, with a 3-layer SAGE node-embedding module.The target, auxiliary training, and attack testing splits use 40%, 30%, and 30% of each dataset, respectively.Source: §7.1 · p. 7

7.2 Property Inference Attack

  • 0.904 attack accuracy on DD/number of nodes/DiffPool (k=2), versus 0.500 Random and 0.541 auxiliary-summary baseline; the attack beats baselines in most settings.Larger bucketization schemes generally lower accuracy; MeanPool is often weaker, which the authors attribute to loss of graph structural information.Source: Figure 5 · p. 8, §7.2 · p. 8
  • Property inference remains effective when auxiliary and target graphs come from different distributions in the tested OVCAR-8H/MOLT-4H and NCI1/PC3 transfers.These tests use MinCutPool with k=2.Source: Figure 6 · p. 8, §7.2 · p. 9

7.3 Subgraph Inference Attack

  • 0.982 attack AUC on DD/MeanPool/FireForest at ratio 0.8; at ratio 0.2, ENSYMES/MeanPool/Snowball still reaches 0.859.AUC generally falls as sampling ratios shrink, as positive and negative subgraphs become more similar.Source: Figure 7 · p. 9, §7.3 · pp. 9–10
  • Across subgraph-inference transfer tests, sampling-method changes usually have no significant impact, while model mismatch slightly reduces performance but retains at least 0.773 AUC.Dataset transfer also remains effective.Source: Figure 8 · p. 9, Figure 9 · p. 10, §7.3 · p. 10
  • Element-wise difference performs best for feature construction, while concatenation is near random guessing and Euclidean distance compresses discrepancy information to one scalar.The authors report that element-wise difference preserves richer discrepancy information between graph embeddings.Source: Table 2 · p. 10, §7.3 · p. 10

7.4 Graph Reconstruction Attack

  • Reconstruction achieves a 0.875 WL graph kernel on AIDS/DiffPool; betweenness-distribution cosine exceeds 0.85 in all settings, and LCC cosine reaches 0.99 on AIDS and NCI1.Degree and closeness centrality distribution results are weaker, but cosine similarity remains at or near 0.5.Source: Table 3 · p. 11, §7.4 · p. 11

8 Defenses

The defense adds Laplace noise to shared graph embeddings to reduce inference attacks, while requiring a noise level that preserves normal graph-classification utility.

8 Defenses

  • The owner shares a perturbed embedding, H̃_G = H_G + Lap(β), with Lap(β) sampled from a Laplace distribution of scale β.Larger β means more noise; the defense evaluation uses DD and ENZYMES, with graph density for property inference and RandomWalk sampling at ratio 0.8 for subgraph inference.Source: §8 · p. 11
  • Figure 11 plots attack performance and graph-classification accuracy against β, with separate rows for DD and ENZYMES.The first two columns show property and subgraph inference; the last shows classification accuracy.Source: Figure 11 · p. 12
  • At Laplace-noise standard deviation 2, subgraph-inference performance drops significantly while graph-classification accuracy decreases only slightly.Increasing noise also reduces property-inference performance, but decreases classification accuracy.Source: §8 · p. 12

9 Related Work

Related work distinguishes attacks that alter GNN training from exploratory attacks that query models, and describes defenses chiefly developed for causative attacks. The paper positions its graph-embedding attacks as exploratory and its reconstruction task as distinct from prior node-embedding reconstruction.

Causative Attacks on GNNs

  • Causative GNN attacks manipulate training data to change model parameters, whereas this paper’s attacks do not tamper with that data.Prior approaches target objectives including node classification, link prediction, and graph classification.Source: §9 · p. 12

Exploratory Attacks on GNNs

  • Exploratory attacks query a model with crafted inputs; prior GNN examples include link stealing, model extraction, and node-embedding reconstruction.The paper instead infers information from a graph embedding, including reconstructing a graph from one graph-level vector rather than all node embeddings.Source: §9 · pp. 12–13
  • Prior graph-reconstruction work targets node embeddings from Deepwalk or node2vec and uses a nonlearnable dot-product decoder, unlike this paper’s GNN-focused, learnable-decoder approach.The authors characterize their threat model as requiring less background knowledge and say the decoder can be fine-tuned.Source: §9 · p. 13

Defense of Adversarial Attacks on GNNs

  • Existing defenses such as graph sanitization, adversarial training, and robustness certification are described as targeting causative rather than exploratory GNN attacks.The cited adversarial-training work reduces sensitivity to structure or attribute perturbations.Source: §9 · p. 13

10 Conclusion

The paper concludes that graph embeddings leak graph properties and subgraph membership, and can support reconstruction of graphs with similar statistics. It also proposes embedding perturbation to mitigate these attacks, while Appendix A points readers to a notation summary.

10 Conclusion

  • The paper presents three graph-embedding inference attacks: property inference, subgraph-membership inference, and graph reconstruction with similar graph statistics.It also proposes embedding perturbation to mitigate the attacks without noticeable graph-classification accuracy degradation.Source: §10 · p. 13

A Notations

  • Appendix A directs readers to Table 5 for a summary of frequently used notation.The paper denotes an undirected, unweighted, attributed graph as G = ⟨V, A, X⟩, with V the nodes, A the adjacency matrix, and X the attributes matrix.Source: A Notations · p. 16, Table 5 · p. 16

B.1 Graph Sampling Methods

The appendix describes graph-sampling procedures and graph statistics used in the study, then reports additional property- and subgraph-inference results across settings.

B.1 Graph Sampling Methods

  • RandomWalk follows a randomly chosen starting node; Snowball expands from randomly selected seeds to neighboring nodes, while Forest Fire recursively samples burned edges and their endpoints.Each method continues until the desired number of nodes is obtained.Source: §B.1 · p. 16

B.2 Macro-level Graph Statistics

  • Degree distribution, local clustering coefficient, betweenness centrality, and closeness centrality are listed as macro-level graph statistics.The passages define them respectively through node degrees, neighbor clustering, shortest paths through a node, and reciprocal summed shortest-path lengths.Source: §B.2 · p. 16

C.1 Property Inference Attack

  • The attack remains effective on graph diameter and radius in most settings, with conclusions consistent with Section 7.2.Figure 12 organizes attack accuracy by dataset and property, with embedding models and bucketization schemes distinguished in each plot.Source: §C.1 · p. 16, Figure 12 · p. 17

C.2 Subgraph Inference Attack

  • Additional comparisons cover subgraph-inference AUC across datasets, sampling methods, embedding models, and sampling ratios; results on NCI1 and OVCAR-8H are consistent with Section 7.3.Figure 14 concerns the impact of graph auto-encoder quality on AIDS, but the supplied passages do not state its outcome.Source: §C.2 · p. 16, Figure 13 · p. 17, Figure 14 · p. 17

C.3 Graph Reconstruction Attack

The graph reconstruction attack preserves macro-level graph statistics, with small Wasserstein distances and JS divergences for most settings and a visualization showing effective preservation. The supplementary results also report defense effectiveness across datasets and attack types, and similar subgraph-inference performance with and without node features.

C.3 Graph Reconstruction Attack

  • Small Wasserstein distances and JS divergences for most settings indicate that graph reconstruction effectively preserves macro-level graph statistics.The reported metrics are measured in Tables 6 and 7, respectively.Source: §C.3 · p. 17, Table 6 · p. 18, Table 7 · p. 18
  • The AIDS-dataset visualization shows effective preservation of macro-level graph statistics using MinCutPool.The graph auto-encoder attack performance increases with training epochs, then remains unchanged for most settings beyond 10 epochs; experiments therefore use 10 epochs.Source: §C.3 · pp. 17–18, Figure 15 · p. 18

C.4 Defense

  • The defense remains effective on the ADIS and OVCAR-8H datasets for property and subgraph inference, and against graph reconstruction.Figure 16 covers property and subgraph inference; Figure 17 covers graph reconstruction.Source: §C.4 · p. 18, Figure 16 · p. 19, Figure 17 · p. 19

D Impact of Node Features

  • Subgraph-inference attack performance is similar for graphs with and without node features in most settings.The featureless setting replaces original features with one-hot encodings of node degrees.Source: D Impact of Node Features · p. 18, Figure 18 · p. 19

Related papers

Loading 2110.02631v1…