Abstract
Hierarchical structures are prevalent in graph data, yet Graph Neural Networks (GNNs) often struggle to protect sensitive positional information within these hierarchies. This paper introduces PoinDP, a framework that leverages hyperbolic geometry—specifically the Poincaré ball—to implement Differential Privacy (DP) for hierarchical graph embeddings. By utilizing a novel Hyperbolic Gaussian Mechanism and personalized sensitivity measures, PoinDP effectively shields structural positions from inference attacks while maintaining high utility for downstream classification tasks.
Introduction
From corporate organizations to medical department structures, hierarchies are a fundamental characteristic of many real-world graphs. While Graph Neural Networks (GNNs) excel at analyzing these structures, they face a significant privacy challenge: the more effectively a model captures a hierarchy, the more vulnerable it becomes to leaking sensitive information about a node's specific position.
Existing Differential Privacy (DP) methods, primarily designed for Euclidean space, often fail when applied to hierarchical data. Adding "flat" noise to a "curved" hierarchy typically results in either insufficient protection or a total loss of model utility. PoinDP addresses this by operating directly within the unique geometry of hyperbolic space.
The Challenge of Hierarchical Privacy
Most graph data possesses a latent tree-like structure where nodes represent different levels of a hierarchy. Hyperbolic geometry, particularly the Poincaré ball, is mathematically suited for representing these hierarchies because its volume grows exponentially with radius, mirroring the branching nature of trees.
However, this structural clarity is a privacy risk. If an attacker can identify a node's position in a specific "leaf" of a medical hierarchy, they can infer sensitive details, such as a patient's presence in an infectious disease wing. Standard DP methods struggle because they do not account for the non-Euclidean distance metrics inherent in these hierarchies.
Methodology: The PoinDP Framework
The PoinDP framework employs a three-step pipeline to secure hierarchical embeddings:
- Poincaré Embedding: The graph is mapped into a Poincaré ball where a node's radius represents its hierarchical depth (center nodes are higher-level) and its angle represents its community or type.
- Personalized Hierarchy-aware Sensitivity (PHS): Sensitivity is calculated based on the hierarchy, splitting the privacy budget between protecting the radius (inter-hierarchy) and the angle (intra-hierarchy).
- Hyperbolic Gaussian Mechanism (HGM): The core innovation is the extension of the Gaussian mechanism to hyperbolic space using the Wrapped Gaussian Distribution. This allows for the injection of "curved" noise that respects the hyperbolic metric, ensuring privacy guarantees hold in non-Euclidean space.
Key Insights and Results
Hierarchy as an Attack Vector
The researchers demonstrate that hierarchical information acts as a bias that attackers can exploit. Hierarchy-aware models are actually more vulnerable to Membership Inference Attacks (MIA) than standard GNNs. PoinDP counters this by using an attention mechanism to adaptively allocate the privacy budget, protecting specific departments (angles) more heavily than general seniority levels (radii).
Performance and Defense
The framework was evaluated on five real-world benchmarks, including citation networks (Cora, PubMed) and e-commerce networks (Amazon Computers, Amazon Photo).
- Utility: PoinDP achieved superior performance compared to Euclidean DP models. On PubMed, it reached a Weighted-F1 score of 83.8%, significantly higher than Euclidean methods like VANPD (61.8%).
- Defense: In Membership Inference Attacks on the Amazon Photo dataset, PoinDP reduced the attacker's AUC to 37.4%, down from over 82% in non-private models.
- Hyperbolicity: The more "tree-like" a graph is (measured by Gromov’s $\delta$-hyperbolicity), the more it benefits from PoinDP’s specialized hyperbolic noise.
Conclusion and Future Work
PoinDP represents a major advancement in protecting hierarchical graph data. While highly effective for node classification, future research may explore its application to link prediction and its performance on "messy" hierarchies where nodes may have multiple parents. Additionally, reducing the computational overhead of mapping between tangent spaces and hyperbolic manifolds remains a goal for scaling to massive graphs.
Summary updated