Beyond Node Degrees: Using Persistent Homology to Reveal the Hidden Structural Loss in Anonymized Social Networks

TL;DR

When we anonymize social networks using Differential Privacy (DP), we often check if the "average degrees" or "clustering" look right. This paper argues that such metrics are too shallow. By using Persistent Homology, the authors demonstrate that current anonymization algorithms (dK-series, HRG) fundamentally "break" the deep topological fabric of social graphs, creating unstable structures that traditional metrics simply cannot detect.

The "Utility" Illusion: Why Traditional Metrics Fail

Privacy-preserving data publishing is a balancing act. We want to hide individual identities while keeping the graph "useful." Currently, researchers use metrics like Degree Distribution or Clustering Coefficients to claim their algorithms preserve utility.

However, the authors point out a critical flaw: these metrics are specific and local. A graph might have the correct average degree but a completely different "skeleton" (topology). For instance, dK-models are great at degree counts but terrible at clustering; HRG models are the opposite. No single traditional metric captures the multi-scale connectivity required for complex tasks like information diffusion or recommendation systems.

Persistent Homology: A Multi-Scale "X-Ray" for Graphs

The paper introduces Persistent Homology—a concept from Algebraic Topology—to provide a comprehensive structural summary through Barcodes.

How it works:

1. Filtration: Imagine growing "circles" around nodes. As the radius (distance $\delta$) increases, nodes connect to form edges, then components, then loops (holes), and finally 3D voids.
2. Distance Metric: In this study, distance is defined as the number of hops in the shortest path.
3. Barcodes: These record the "Birth" and "Death" of topological features.
   • H0: Number of connected components.
   • H1: 1-dimensional cycles (loops).
   • H2: 2-dimensional voids (enclosed clusters).

Fig 1: Example of H0 persistence. As distance increases, components merge into one.

Methodology Comparison

The authors evaluated four heavyweights in the DP-graph field: dK-2, dK-3, HRG, and Local HRG.

Fig 2: Traditional utility metrics show mixed results—most models preserve one aspect but fail another.

The Deep Structural Verdict

The real insight comes from the Barcodes. By comparing the barcodes of original Facebook/ca-HepPh data against anonymized versions, several startling facts emerged:

1. Connectivity Distortion: In the original Facebook graph, the "second longest bar" in H0 (representing the distance needed to connect the whole graph) is length 3. Anonymized graphs shortened this to 1 or 2, making the graph appear more tightly connected than it actually is.
2. The "Hole" Problem (H1 & H2): Real OSNs have very few high-dimensional holes; they are compact. Anonymized graphs, however, were riddled with "H1" and "H2" bars.
   • Implication: Anonymization introduces artificial "voids" and "loops." This means the paths are fragile. If one "linking user" is removed, the communication structure collapses—a catastrophic loss of utility for recommendation algorithms.

Fig 3: Facebook Barcode Comparison. The original graph (top) has a distinct, stable signature, while dKnd HRG results show a chaotic increase in H1/H2 features.

Critical Insight: Real-World Stability is Hard to Mimic

The authors conclude that existing mechanisms fail to preserve persistent homology because they focus on perturbation within a specific model. They ignore the fact that real-world social networks possess a "compact stability."

While Local HRG performed the best among the four, it still couldn't perfectly replicate the topological signature. This suggests that the violation of graph utility is inherent to existing modeling techniques, not just the privacy budget ($ϵ$).

Future Outlook

This paper serves as a wake-up call for the privacy-preserving community. As we move towards more complex applications of social data (like epidemic modeling or decentralized finance), "close enough" statistics are not enough. We need anonymization mechanisms that are topology-aware, ensuring that the "persistent" features of human connection remain intact even under the veil of differential privacy.