PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantifying Privacy Leakage in Graph Embedding

Vasisht Duddu, Antoine Boutet, Virat Shejwalkar

arXiv:2010.00906v2cs.CR

TL;DR

Graph embeddings trained on private graph data may leak information about users, graph structure, and sensitive attributes. This paper evaluates membership, graph reconstruction, and attribute inference attacks under blackbox and whitebox settings, finding substantial leakage across all three tasks. The authors also discuss mitigation strategies, but leave their efficacy for future work.

  • Problem

    Graph embeddings can be trained on private graph data, creating a need to quantify whether released representations leak user membership, graph structure, or sensitive attributes.

  • Method

    The paper evaluates membership inference from GNN outputs or embeddings, graph reconstruction from node embeddings, and attribute inference from released embeddings.

  • Results

    The attacks achieve substantial leakage: 70% average whitebox membership accuracy, 80% average link-inference accuracy versus 50% random guess, and attribute-inference F1 scores up to 0.83.

  • Takeaways & Limitations

    Graph embeddings retain information that can expose training membership, reconstruct sensitive graph relationships, and reveal attributes such as gender or location.

  • Takeaways & Limitations

    The efficacy of proposed privacy mitigations, including rounding, adversarial noise, adversarial training, and differential privacy, is left for future work.

Abstract

from arXiv · show

Graph embeddings have been proposed to map graph data to low dimensional space for downstream processing (e.g., node classification or link prediction). With the increasing collection of personal data, graph embeddings can be trained on private and sensitive data. For the first time, we quantify the privacy leakage in graph embeddings through three inference attacks targeting Graph Neural Networks. We propose a membership inference attack to infer whether a graph node corresponding to individual user's data was member of the model's training or not. We consider a blackbox setting where the adversary exploits the output prediction scores, and a whitebox setting where the adversary has also access to the released node embeddings. This attack provides an accuracy up to 28% (blackbox) 36% (whitebox) beyond random guess by exploiting the distinguishable footprint between train and test data records left by the graph embedding. We propose a Graph Reconstruction attack where the adversary aims to reconstruct the target graph given the corresponding graph embeddings. Here, the adversary can reconstruct the graph with more than 80% of accuracy and link inference between two nodes around 30% more confidence than a random guess. We then propose an attribute inference attack where the adversary aims to infer a sensitive attribute. We show that graph embeddings are strongly correlated to node attributes letting the adversary inferring sensitive information (e.g., gender or location).

1 INTRODUCTION

This section motivates privacy analysis for graph embeddings and presents three attacks that quantify leakage from publicly released embeddings trained on private graph data. The attacks target membership, graph structure, and sensitive attributes across blackbox and whitebox settings.

  • Motivation: Graph embeddings compress high-dimensional graph data into low-dimensional representations used for downstream machine-learning tasks.Graph data support tasks such as node classification and link prediction, but the representations may be released publicly.
  • Threats: Privacy leakage can reveal whether a user’s node was in the training graph, reconstruct the input graph, or expose sensitive node attributes.These risks arise because embeddings and model outputs can retain information about private graph records.
  • Approach: The paper proposes a comprehensive analysis using membership inference, graph reconstruction, and attribute inference attacks under different adversary assumptions.Membership attacks use either output predictions or released graph embeddings.
  • Membership inference: 70% average accuracy was achieved for whitebox membership inference across three datasets using released node embeddings.Blackbox attacks also achieved dataset-specific accuracies ranging from 55% to 78%, depending on the attack and dataset.
  • Graph reconstruction: 80% average link-inference accuracy was achieved for graph reconstruction, compared with a 50% random-guess baseline.Graph reconstruction precision was 0.722 for Cora, 0.778 for Citeseer, and 0.95 for Pubmed.
  • Attribute inference: Attribute inference reached F1 scores as high as 0.65 for DeepWalk and 0.83 for Node2Vec on LastFM, with corresponding Facebook results of 0.59 and 0.61.The attacks targeted gender on Facebook and location on LastFM.

2 BACKGROUND

Graph embeddings represent graph nodes in low-dimensional spaces while retaining properties of the original graph. GNNs generate these representations through message passing over node features and graph structure, enabling downstream prediction tasks.

  • Graph embedding algorithms: Graph embedding algorithms map each node to a d-dimensional vector that captures properties of the original graph.The representation is intended to reduce the space and computation required for downstream graph processing.
  • Graph embedding algorithms: Random-walk embeddings sample graph walks and pass them to SkipGram to obtain node features.Deep learning-based embeddings instead use node features and the adjacency matrix to generate low-dimensional node representations.
  • Graph neural networks: GNN layers take node features and an adjacency matrix as input and produce matrix representations of node features.The initial layers generate embeddings that can support node classification and link prediction through an attached classifier network.
  • Graph neural networks: GNN training uses weighted aggregation of neighboring-node features to compute each node’s representation.The layer computation is H^(l+1) = f_agg(H^(l), A), with H^(0) = X and H^(L) = Z.

3 THREAT MODELS

The paper models privacy threats against graph embeddings through membership inference, graph reconstruction, link inference, and attribute inference attacks under distinct adversary access assumptions.

  • Membership Inference Attacks: Membership inference distinguishes training-graph members from non-members using output predictions in blackbox settings and intermediate embeddings in whitebox settings.Blackbox adversaries may use shadow models or confidence scores; whitebox adversaries observe node embeddings.
  • Blackbox: Inference using Output Predictions: Blackbox membership attacks exploit different prediction-confidence distributions for training and test nodes, including non-overlapping regions caused by overfitting.The shadow attack uses an auxiliary graph and substitute model, whereas the confidence attack avoids prior knowledge of the data distribution and target architecture.
  • Whitebox Membership Inference: Whitebox membership attacks exploit distinguishable intermediate embeddings produced for training and test nodes.The attack maps embeddings to membership values with an unsupervised encoder-decoder and clusters the resulting values into members and non-members.
  • Graph Reconstruction Attack: Graph reconstruction maps released target-node embeddings to the target adjacency matrix, exposing graph structure and connections.The adversary trains an encoder-decoder on an auxiliary graph and applies its decoder to released target embeddings.
  • Link Inference: Link inference derives from graph reconstruction by querying the reconstructed adjacency matrix to determine whether two nodes are connected.The inferred links can represent relationships such as whether two people know each other.
  • Attribute Inference Attack: Attribute inference targets sensitive node features by learning from embeddings paired with attributes publicly available for auxiliary users.The target attributes may include private information such as gender or location.

4 EXPERIMENT SETUP

The experiments evaluate privacy attacks across benchmark graph datasets, embedding architectures, and task-specific metrics in an inductive training setting without intentionally forced overfitting.

  • Datasets: The experiments use Pubmed, Citeseer, and Cora for membership inference and graph reconstruction, and Facebook and LastFM for attribute inference.The datasets cover citation networks and social-network graphs with user attributes.
  • Embedding Algorithms: The evaluated embedding methods include GCN, GraphSAGE, GAT, TAGCN, Node2Vec, and DeepWalk.GNN architectures support membership and reconstruction experiments, while Node2Vec and DeepWalk support attribute inference.
  • Evaluation Metrics: Membership and link inference use accuracy, where 50% is the random-guess baseline, while attribute inference uses F1 score.Accuracy measures binary membership or link classification; F1 balances precision and recall for attribute prediction.
  • Training Setting: The study focuses on inductive GNN training, sampling a training subgraph and evaluating on held-out nodes from the full graph.Test nodes are not seen during training, unlike the transductive setting.
  • Training Setting: The models were not intentionally overfitted, so the reported leakage reflects natural behavior of the selected architectures and training procedures.The authors use state-of-the-art architectures, libraries, and training details from the original papers.

5 EVALUATION

The evaluation measures privacy leakage through membership, reconstruction, link, and attribute inference attacks. Results show that graph embeddings expose train–test distinctions, graph structure, and sensitive attributes, while attack performance varies with architecture, dataset, adversary knowledge, and message-passing depth.

  • Membership Inference from Output Predictions: 78.28% confidence-inference accuracy on Cora, 63.75% on Citeseer, and 60.89% on Pubmed reveal membership leakage from output predictions.The corresponding adversary advantages are 27.48%, 56.56%, and 21.78%, respectively.
  • Membership Inference from Output Predictions: 8% lower inference accuracy follows increasing GCN layers from 2 to 6, while models with more than 8 layers lose predictive power completely.Inference and prediction accuracy generally decrease as message passing expands from 2 to 16 layers.
  • Membership Inference from Graph Embeddings: 20%–36% whitebox membership advantage occurs on PubMed, compared with 7%–17% on Citeseer and 4%–7% on Cora.The stronger PubMed leakage is associated with more distinguishable train and test embeddings.
  • Graph Reconstruction Attack: 0.722, 0.778, and 0.95 average precision are achieved for graph reconstruction on Cora, Citeseer, and Pubmed, respectively.With 50% target-graph knowledge, Cora average precision rises to 0.81 and Citeseer to 0.828; Pubmed rises to 0.96.
  • Link Inference Attack: 93.39% Citeseer, 90.73% Cora, and 57.28% Pubmed link-inference accuracy yield adversary advantages of 86.78%, 81.06%, and 14.56%.The attack infers links by querying the reconstructed adjacency matrix.
  • Attribute Inference Attack: 0.80, 0.83, and 0.83 F1 scores for Node2Vec on LastFM show sensitive-attribute inference across neural-network, random-forest, and SVM attackers.DeepWalk reaches 0.61, 0.62, and 0.65; increasing auxiliary knowledge raises Node2Vec scores to 0.83, 0.84, and 0.86.

6 RELATED WORK

Related work establishes privacy attacks and defenses for traditional and graph-based machine learning. Existing defenses include output perturbation, distillation, regularization, and differential privacy, but their effectiveness against the proposed graph-embedding attacks remains unexplored.

  • Privacy Attacks: Prior work studies membership inference in blackbox and whitebox settings, alongside reconstruction, hyperparameter extraction, and model reverse-engineering attacks.These attacks have been extended to collaborative learning, generative models, and Graph Neural Networks.
  • Graph Privacy Risks: Graph Neural Network privacy risks include inferring whether two nodes are linked from the distance between their node features.The paper positions its attack methodology as more generic than this manual-threshold approach.
  • Defenses: Existing defenses use crafted output noise, knowledge distillation, adversarial regularization, ensemble training, dropout, L2-regularization, or differential privacy.Differential privacy offers theoretical guarantees through gradient noise but faces a privacy–accuracy trade-off.
  • Open Question: Differential-privacy frameworks have been explored for graph and text embeddings, but their efficacy against the proposed attacks remains unexplored.

7 DISCUSSIONS AND CONCLUSIONS

The paper identifies privacy risks from graph embeddings across membership inference, graph reconstruction, link inference, and sensitive-attribute inference. It also outlines possible mitigations, while leaving their effectiveness for future work.

  • Privacy risks: Graph embeddings expose three major privacy risks: membership inference, graph reconstruction with link inference, and sensitive-attribute inference.The attacks target whether a node was in training data, recovery of graph structure and links, and hidden attributes such as gender and location.
  • Privacy risks: Released node embeddings can be inverted to reconstruct sensitive input graphs and infer whether links exist between nodes.Graph reconstruction further enables link inference on the sensitive graph data.
  • Privacy risks: An adversary can infer hidden user attributes such as gender and location from graph embeddings.
  • Mitigation strategies: Potential mitigations include rounding embedding vectors, adding adversarial noise, and jointly training models against inference attacks.Differential Privacy is also proposed to provide a theoretical bound on privacy leakage.
  • Mitigation strategies: The efficacy of these potential mitigation strategies is left for future work.
Loading 2010.00906v2…