Safeguarding Graph Topology and Link Privacy

40 concepts38 papers2 proposals

In graph-structured data, privacy research historically focused on protecting node attributes (such as a user's profile information) or edge weights (such as transaction amounts). However, the topology of the graph—the mere existence of a link between two nodes—is often the most sensitive asset. Social relationships, financial transaction networks, and trust graphs carry deep proprietary or personal secrets.

As Zhao et al. and Jia et al. highlight, protecting this structural topology is uniquely challenging. Many traditional privacy frameworks assume the graph structure is public knowledge while only protecting weights or features. As Ziani demonstrates, this assumption fails to protect against the disclosure of sensitive connections or node identities. When Graph Neural Networks (GNNs) or graph mining algorithms process network data, the adjacency matrix becomes implicitly encoded into the model's representations, creating severe leakage vectors.

How Graph Topology Leaks

To understand why graph topology leaks, one must look at the message-passing mechanism of GNNs. Because GNNs compute node representations by aggregating features from neighboring nodes, a node's final embedding is fundamentally dependent on its local topology.

Inference and Influence Analysis

This structural dependency allows adversaries to reverse-engineer links through black-box queries. Wu et al. exploit this via LinkTeller, an attack demonstrating that an attacker can perturb a single node's features and observe how that perturbation propagates to other nodes' predictions. If a change in Node A strongly influences the output of Node B, the model inadvertently reveals that they are connected. Even with zero knowledge of node attributes or model internals, black-box attacks like the one proposed by He et al. can reconstruct private edges purely from model outputs.

Distributed and Federated Environments

In decentralized settings where multiple clients hold local subgraphs, sharing model parameters, gradients, or raw node embeddings introduces massive risks. As Zhuo et al. and Chen et al. note, these shared outputs act as structural fingerprints. Adversaries can exploit them to reverse-engineer local edge configurations and node degrees, which Pan et al. identify as highly sensitive topological information. Furthermore, data access patterns in secure collaborative protocols can inadvertently expose which users are interacting, violating relationship privacy even if the underlying attributes remain encrypted (Cui et al.).

Global Graph Mining Outputs

The vulnerability is not confined to deep learning models; it extends to classic graph mining algorithms. Algorithms for community detection (Nguyen et al.), densest subgraph extraction (Farhadi et al.), or graph cuts (Dalirrooyfard et al.; Aamand et al.) are highly sensitive to minor topological changes. Because the inclusion or exclusion of a single edge can drastically alter a minimum cut or community boundary, releasing exact structural bottlenecks directly exposes individual relationships.

Mechanisms for Topology Protection

To defend structural privacy, researchers focus on breaking the direct link between the true adjacency matrix and the shared outputs, models, or mining results.

[True Adjacency Matrix] 
          │
          ▼
┌────────────────────────────────────────────────────────┐
│             TOPOLOGY PROTECTION MECHANISM              │
├──────────────────────────────┬─────────────────────────┤
│  Differential Privacy (DP)   │ Cryptographic/Hardware  │
│  - Noisy Cluster Degrees     │  - Homomorphic Encryp.  │
│  - Structural Discriminators │  - Secure Enclaves      │
└──────────────────────────────┴─────────────────────────┘
          │
          ▼
[Privacy-Preserving Downstream Analytics / GNN Inference]

Instead of feeding the exact adjacency matrix into a GNN or mining algorithm, noise can be injected directly into the structural representation. Zhu et al. introduce Blink, a framework that splits the privacy budget between node degrees and adjacency lists, using Bayesian estimation to denoise the resulting graph representations locally.

Similarly, Kolluri et al. replace raw adjacency matrices with "noisy cluster degree vectors," allowing the model to learn macro-level structural patterns without exposing individual connections. For graph generation, Yang et al. utilize a structural discriminator rather than an edge-by-edge reconstruction loss, forcing the generative model to prioritize global topological distributions over memorizing specific links.

Cryptographic and Hardware Isolation

When exact topology is required to maintain inference accuracy, researchers turn to secure computation. Quan et al. and Chen et al. leverage homomorphic encryption and secret sharing to hide the graph's shape entirely during cloud-based inference. Alternatively, Ding et al. split the GNN model, shielding the sensitive adjacency matrix and critical parameters inside a hardware-based Trusted Execution Environment (TEE) on edge devices, thereby thwarting link-stealing attacks with minimal accuracy degradation.

Synthetic Graph Reconstruction

To protect the entire network layout during training, Fu et al. propose Private Graph Reconstruction (PGR). This approach generates a privacy-preserving synthetic graph to train GNNs, completely decoupling the final model from the true underlying connectivity pattern and ensuring that the global structure can be analyzed without sacrificing edge confidentiality.

Key Foundational Work

Differentially Private Learning of Undirected Graphical Models Using Collective Graphical Models (2017) — contributed 1 concept elements to this direction.
Shortest Paths and Distances with Differential Privacy (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_topology_privacy_01c0edba,
  title = {graph topology privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-topology-privacy/rdr_01c0edba4aba4c329b459f685015d0d9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_topology_privacy_01c0edba_v1,
  title = {graph topology privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-topology-privacy/rdr_01c0edba4aba4c329b459f685015d0d9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake