Differential Privacy on Graphs

The granularity of the privacy guarantee is a fundamental distinction.

• Edge-Level Differential Privacy: Protects the presence or absence of any single edge. This is analogous to the standard DP definition applied to database rows. An algorithm satisfies ε-edge-DP if its output distribution is nearly identical for any two graphs that differ by a single edge.
• Node-Level Differential Privacy: A stronger guarantee that protects all edges incident to a single node. Two graphs are considered neighbors if one can be obtained by adding or removing a node and all its connecting edges. This is significantly more challenging to achieve as changing a node alters the graph structure more drastically.

Most real-world social network applications require node-level privacy, as an individual's entire set of connections is sensitive.

Applying differential privacy requires bounding how much a single individual's data can change the output of a query, known as global sensitivity. For graphs, calculating this is non-trivial.

• For Edge Count: The global sensitivity is 1 (adding/removing one edge changes the count by at most 1).
• For Subgraph Counts (e.g., triangles): Sensitivity explodes. Adding one node connected to k others can create up to C(k, 2) new triangles. Using the global sensitivity directly would add excessive noise, destroying utility.
• Local Sensitivity & Smooth Sensitivity: Advanced techniques like smooth sensitivity calculate a data-dependent, noise-calibrated bound that is much lower than the worst-case global sensitivity, enabling practical privacy for complex graph statistics.

These are the core randomized algorithms for achieving differential privacy on numeric and categorical graph outputs.

• Laplace Mechanism: Used for releasing numeric queries (e.g., degree distribution, subgraph counts). It adds noise drawn from a Laplace distribution scaled to the query's sensitivity (Δf) and privacy budget (ε): Noise ~ Lap(Δf/ε).
• Exponential Mechanism: Used for selecting a discrete output (e.g., choosing the best graph model from a set, or a synthetic graph from a candidate set). It assigns a probability to each possible output proportional to exp(ε * Utility(output, data) / (2ΔUtility)), where Utility is a quality score function. This privately selects a high-utility output.

Both mechanisms are applied to graph statistics or generation processes to guarantee the formal privacy definition.

A direct application is releasing aggregate statistics about a private graph. The process is:

1. Define the target statistic (e.g., degree sequence, clustering coefficient, eigenvalue spectrum).
2. Compute or bound its global (or smooth) sensitivity.
3. Apply the Laplace or Exponential mechanism to release a noisy version of the statistic.

Key Challenge: Graph statistics are highly interdependent. Releasing multiple statistics requires careful composition of the privacy budget (ε) across all releases. Advanced composition theorems or the sparse vector technique can be used to manage this budget efficiently when answering many queries.

Instead of releasing noisy statistics, a more flexible approach is to generate and release a differentially private synthetic graph that preserves the macro-properties of the original.

Common methodologies include:

• Privately Fitting a Generative Model: Use the exponential mechanism to privately select parameters for a model like the Stochastic Block Model (SBM) or Erdős–Rényi model that best fits the private data. Then sample a synthetic graph from the fitted model.
• Noisy Graph Modification: Start with an empty graph or a noisy skeleton. Use a series of private decisions (via the exponential mechanism) to add edges that match privately computed degree distributions or connection probabilities.
• Projection onto Public Graphs: Map the private graph to the nearest graph within a set of public, non-sensitive graphs (e.g., from a different domain) in a differentially private manner.

In the local model, each user (node) perturbs their own data before sending it to a central aggregator. This is stronger than the central model as the aggregator never sees raw data.

For graphs, this is implemented via randomized response on adjacency lists:

1. Each user (node) has a list of their neighbors.
2. For each potential neighbor, they flip a coin: with probability p = e^ε/(1+e^ε), they report the true connection status; with probability 1-p, they report a random false status.
3. The aggregator collects all noisy reports and uses statistical estimation to reconstruct global graph properties.

This model is highly robust but requires sophisticated estimation techniques to correct for the introduced noise and can have high sample complexity.

Enables the study of community structure, influence propagation, and network dynamics in platforms like Facebook or LinkedIn without exposing individual user connections or attributes.

• Key Mechanism: Applying edge-level or node-level differential privacy to adjacency matrices or aggregated statistics (e.g., degree distribution).
• Example: Releasing a differentially private version of a friendship graph to researchers studying pandemic spread models, ensuring no single user's social links can be inferred.

Allows banks and payment processors to collaboratively train anomaly detection models on transaction networks (a graph of accounts and payments) without sharing sensitive customer data.

• Key Mechanism: Using local differential privacy where noise is added to individual node's transaction vectors before aggregation, or federated learning with DP-SGD on graph neural networks.
• Benefit: Identifies sophisticated, multi-account fraud rings while providing a cryptographically rigorous privacy guarantee to all involved entities.

Facilitates research on patient interaction networks (disease transmission) or biological networks (protein-protein interactions) derived from sensitive health records.

• Key Application: Analyzing contact-tracing graphs during an epidemic to model spread while preventing re-identification of patient zero or specific exposure events.
• Technical Challenge: Medical graphs often have highly sensitive node attributes (e.g., diagnosis) and very sparse but revealing edge structures (e.g., rare disease co-occurrence), requiring careful budget allocation between edge and attribute privacy.

Protects user-item interaction histories (a bipartite graph) when releasing aggregate data for model training or A/B testing. Prevents inferring a user's private preferences or ratings.

• Common Approach: Generating a differentially private synthetic interaction graph that mimics the global co-occurrence statistics (e.g., "users who liked X also liked Y") without leaking individual user histories.
• Utility Goal: The synthetic graph must preserve enough topological signal (e.g., item-item similarity) to train effective collaborative filtering models like Graph Convolutional Networks (GCNs) for recommendations.

Enables companies to publish subsets of their proprietary knowledge graphs (e.g., product ontologies, enterprise IT asset relationships) for partner integration or public research without revealing competitively sensitive entity relationships.

• Mechanism: Applying edge differential privacy during the subgraph extraction or graph summary generation process. This ensures the presence or absence of any single (head, relation, tail) triple is protected.
• Example: A pharmaceutical company releasing a privacy-aware version of a drug-target interaction graph to accelerate external research, with guarantees that specific, unpublished trial results cannot be reverse-engineered.

Allows organizations to share telemetry about attack graphs (e.g., lateral movement paths within a compromised network) with industry threat intelligence centers without exposing internal network topology or specific breached hosts.

• Process: A central aggregator (e.g., ISAC) applies a differentially private mechanism to a contributed graph of attack patterns before disseminating a sanitized, aggregated threat model back to members.
• Critical Balance: The privacy mechanism must preserve enough structural fidelity (e.g., common attack sequences) to be useful for defensive ML models while adding sufficient noise to mask any single organization's unique incident details.