🤖 machine learning

Beyond Membership: Limitations of Add/Remove Adjacency in Differential Privacy

This paper demonstrates that using the standard add/remove adjacency relation for differential privacy accounting significantly overstates the protection of individual record attributes compared to the substitute adjacency relation, revealing a critical gap between reported guarantees and actual security against attribute inference attacks.

Original authors: Gauri Pradhan, Joonas Jälkö, Santiago Zanella-Béguelin, Antti Honkela

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gauri Pradhan, Joonas Jälkö, Santiago Zanella-Béguelin, Antti Honkela

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Privacy Promise" vs. Reality

Imagine you are baking a cake for a party, but you want to keep your secret family recipe safe. You decide to use a special "privacy shield" (called Differential Privacy or DP) that promises to hide your ingredients.

For years, the standard way to test this shield has been to ask: "If I swap one ingredient (like sugar) with nothing at all, can anyone tell the difference?" This is called the Add/Remove test. If the cake tastes the same whether you added a pinch of sugar or took it away, the shield is working.

The Problem: This paper argues that this test is too easy. In the real world, people don't just want to know if you used sugar; they want to know what kind of sugar you used (e.g., "Is it organic cane sugar or cheap corn syrup?").

The authors show that while the "Add/Remove" shield is great at hiding who was in the kitchen, it is surprisingly bad at hiding what specific ingredients (attributes) those people contributed.

The Core Concept: Three Ways to Compare Datasets

To understand the paper, we need to look at how we compare two versions of a dataset (the "ingredients list"):

Add/Remove (The Standard):
- Analogy: You have a soup. You compare the soup with a carrot to the soup without a carrot.
- Goal: Protects against someone asking, "Was Bob in the kitchen?"
- Current Status: This is what most AI tools use today.
Substitute (The Real Threat):
- Analogy: You have a soup. You compare the soup with a carrot to the soup with a parsnip.
- Goal: Protects against someone asking, "Did Bob use a carrot or a parsnip?"
- The Issue: The paper shows that the "Add/Remove" shield is weak against this. If you swap a carrot for a parsnip, the AI model might change its taste significantly, revealing the specific ingredient used.
Zero-Out (A Special Case):
- Analogy: Replacing a carrot with an empty spoon. (Mathematically similar to Add/Remove).

The Experiment: The "Canary in the Coal Mine"

To prove their point, the researchers built a "trap" to see if the privacy shield actually works against the Substitute attack.

The Canary: They created a special, fake data point (a "canary") that acts like a spy.
The Setup: They trained two AI models:
- Model A: Trained with the Canary (e.g., a picture of a cat labeled "Dog").
- Model B: Trained with a different Canary (e.g., a picture of a cat labeled "Bird").
The Test: They asked an adversary (a hacker) to look at the final AI model and guess: "Did you train on the 'Dog' label or the 'Bird' label?"

The Result:
The AI models were surprisingly good at revealing which label was used. Even though the privacy math (based on Add/Remove) said the risk should be tiny, the actual risk was much higher. The "Add/Remove" math was overestimating the safety.

Why Does This Happen? (The "Group Privacy" Trap)

The paper explains that many privacy tools try to be clever. They think: "If I can protect against adding a record, and I can protect against removing a record, then I must automatically protect against swapping one for another."

They use a mathematical shortcut called Group Privacy to make this guess.

The Analogy: It's like saying, "If I can lock the front door and the back door, I must be safe from someone breaking a window."
The Reality: The math shows that this shortcut is too loose. It assumes the worst-case scenario is much worse than it actually is, or conversely, that the protection is much stronger than it is. In this case, the shortcut made the privacy guarantee look much stronger than it really was.

The Real-World Impact

Why should you care?

False Security: If a company uses standard AI tools (like Opacus) to train a model on sensitive data (like medical records), they might think they are safe because the "Add/Remove" math says so.
The Leak: If a hacker knows a specific patient was in the dataset, they might be able to figure out that patient's specific diagnosis (e.g., "Patient X has Disease Y") even though the company thought they were protected.
Fine-Tuning is Risky: The paper found that this problem is especially bad when companies take a pre-trained AI (like a chatbot) and "fine-tune" it on their private data. The "Add/Remove" shield fails to protect the specific labels added during this fine-tuning.

The Solution Proposed

The authors aren't saying "Don't use Differential Privacy." They are saying: "Stop using the wrong ruler."

Don't just measure privacy by asking "Can you tell if a record was added?"
Do measure privacy by asking "Can you tell if a record was swapped for a different one?"

They provide new tools (algorithms) to measure this "Substitute" privacy accurately. They show that if you use these new tools, the privacy numbers drop (meaning the protection is weaker than we thought), but at least you know the real truth.

Summary in One Sentence

Current privacy tools are like a lock that stops people from knowing if you were in the room, but it fails to stop them from knowing what you were doing in there; this paper proves we need a stronger lock that protects the specific details of your actions, not just your presence.

1. Problem Statement

Differential Privacy (DP) is the standard framework for protecting sensitive data in machine learning. However, the strength of DP guarantees depends heavily on the chosen adjacency relation between datasets:

Add/Remove Adjacency ( $\sim_{AR}$ ): Two datasets are adjacent if one can be obtained by adding or removing a single record. This is the standard used in most DP libraries (e.g., Opacus) and protects against membership inference attacks (determining if a specific individual was in the training set).
Substitute Adjacency ( $\sim_{S}$ ): Two datasets are adjacent if one record in a dataset is replaced by another record. This protects against attribute inference attacks (determining the specific attributes or labels of an individual known to be in the dataset).

The Core Issue: The authors argue that practitioners relying on standard DP libraries often assume that the privacy budget ( $\epsilon$ ) calculated under add/remove adjacency provides sufficient protection for attribute privacy. The paper demonstrates that this is a critical misconception: Add/remove bounds significantly overstate the protection against attribute inference. An adversary can distinguish between two datasets differing only by a substituted record with much higher confidence than the add/remove $\epsilon$ suggests, effectively breaking the privacy guarantees for attributes.

2. Methodology

To quantify this gap, the authors developed a comprehensive privacy auditing framework tailored specifically for substitute adjacency.

A. Auditing Framework

The authors define a threat model where an adversary attempts to distinguish between two neighboring datasets, $D$ and $D'$ , where $D'$ is formed by replacing a target record $z \in D$ with a "canary" record $z'$ . The adversary has access to the final trained model (Hidden-State setting) or intermediate gradients (Visible-State setting).

They propose five specific canary crafting scenarios (Table 1 in the paper) to maximize the distinguishability between $D$ and $D'$ :

S1 (Gradient Space, Worst-Case): Crafting $D$ and $D'$ such that $z$ and $z'$ produce gradients of equal magnitude ( $C$ ) but opposite directions. This provides a theoretical lower bound.
S2 (Gradient Space, Natural Data): Crafting gradient canaries ( $g_z, g_{z'}$ ) that target the model parameter changing the least during training, ensuring consistent signal injection.
S3 (Input Space, Crafted Input): Generating an adversarial input $x'$ with the correct label $y$ that minimizes cosine similarity with the target sample's gradient.
S4 (Input Space, Mislabeled): Generating an input $x$ with a wrong label $y'$ that minimizes gradient similarity.
S5 (Input Space, Adversarial Natural): Selecting a natural sample from an auxiliary dataset that is maximally dissimilar to the target in gradient space.

B. Privacy Accounting

The authors compare three metrics:

$\epsilon_{AR}$ (Accounting): The theoretical bound calculated using standard add/remove accountants.
$\epsilon_{S}$ (Accounting): The theoretical bound calculated using a substitute accountant (specifically adapted for Poisson subsampling).
$\epsilon_{S}$ (Group Privacy): An approximation derived by treating substitution as one add + one remove operation (using Theorem 4.1).
$\epsilon$ (Auditing): The empirical lower bound on privacy loss derived from the success rate of the canary attacks.

They utilize Gaussian Differential Privacy (GDP) and the $\mu$ -GDP framework to convert empirical False Positive/Negative rates into a lower bound on $\epsilon$ .

3. Key Contributions

Novel Auditing Algorithms: The paper introduces algorithms (Algorithms 2–5) for crafting worst-case canaries specifically for substitute adjacency in both gradient space and input space.
Empirical Gap Demonstration: They provide empirical evidence showing that the privacy leakage ( $\epsilon$ ) observed under substitute attacks exceeds the guarantees provided by add/remove accountants ( $\epsilon_{AR}$ ).
Validation of Substitute Accounting: The empirical results closely track the theoretical bounds predicted by substitute accountants ( $\epsilon_{S}$ ), proving that substitute accounting is the correct metric for attribute privacy.
Critique of Group Privacy Approximation: They show that approximating substitute adjacency via group privacy (Theorem 4.1) yields suboptimal (looser) upper bounds compared to direct numerical accounting for substitute adjacency.

4. Key Results

The experiments were conducted on:

Image Classification: ViT-B-16 fine-tuned on CIFAR-10.
Text Classification: Sentence-BERT fine-tuned on SST-2.
From-Scratch Training: MLP trained on Purchase100.

Findings:

Add/Remove Overestimation: In all fine-tuning scenarios (natural datasets), the empirical privacy leakage ( $\epsilon$ ) violated the add/remove bounds ( $\epsilon_{AR}$ ). For example, with a subsampling rate $q=0.25$ , the empirical leakage was significantly higher than $\epsilon_{AR}$ but aligned with $\epsilon_{S}$ .
Gradient vs. Input Canaries:
- Gradient-space canaries (S2) provided the tightest audits, consistently violating $\epsilon_{AR}$ and matching $\epsilon_{S}$ .
- Input-space canaries (S3–S5) were less robust, particularly in non-convex settings (training from scratch) or with low subsampling rates. However, in fine-tuning scenarios, they still demonstrated leakage exceeding $\epsilon_{AR}$ .
Fine-Tuning Vulnerability: Fine-tuned models were found to be more vulnerable to input-space canary attacks than models trained from scratch, likely due to the stability of the pre-trained features.
Subsampling Impact: As the subsampling rate ( $q$ ) decreases, the efficacy of input-space canaries diminishes, but gradient-space canaries remain robust.

5. Significance and Implications

Re-evaluating DP Guarantees: The paper fundamentally challenges the assumption that standard DP implementations (using add/remove accounting) protect individual attributes. If the goal is to protect labels or attributes (e.g., in supervised fine-tuning), relying on $\epsilon_{AR}$ is dangerous.
Library Limitations: Most current DP libraries (like Opacus) default to add/remove accounting. Practitioners using these tools for attribute protection are likely overestimating their privacy by a significant margin.
Recommendation: The authors advocate for the use of substitute adjacency accounting when the threat model involves attribute inference. They provide the necessary tools (auditing scripts and accountants) to verify these tighter bounds.
Future Directions: The work highlights the need for robust input-space canaries that work well in non-convex optimization settings and suggests that future DP mechanisms for label privacy should be evaluated under the substitute adjacency framework.

In conclusion, the paper establishes that add/remove adjacency is insufficient for attribute privacy. To ensure rigorous protection against attribute inference, the community must shift toward substitute adjacency accounting and auditing.