A Two-Phase Algorithm for Differentially Private Frequent Subgraph Mining.

Area of Science:

• Data Mining
• Graph Analytics
• Privacy-Preserving Technologies

Background:

• Frequent subgraph mining (FSM) is crucial for analyzing graph data but raises privacy concerns when datasets contain sensitive information.
• Releasing discovered frequent subgraphs can inadvertently expose private details within the original graphs.
• Existing methods lack robust privacy guarantees for FSM, necessitating new approaches.

Purpose of the Study:

• To develop a privacy-preserving algorithm for frequent subgraph mining (FSM) that adheres to the rigorous differential privacy model.
• To address the privacy risks associated with releasing frequent subgraphs from sensitive graph datasets.
• To enhance the accuracy of private FSM by improving subgraph identification and noisy support computation.

Main Methods:

• A two-phase algorithm, termed DFG (Differentially private Frequent subgraph mining using Graph pruning and lattice-based noisy support), is proposed.
• Phase 1: Private identification of frequent subgraphs using a novel candidate pruning approach for improved accuracy.
• Phase 2: Computation of noisy supports leveraging a lattice-based method that utilizes inclusion relations between subgraphs.

Main Results:

• The DFG algorithm is formally proven to satisfy epsilon-differential privacy (ϵ-differential privacy).
• Experimental results demonstrate that DFG effectively identifies frequent subgraphs with strong privacy guarantees.
• The proposed methods achieve high data utility, balancing privacy protection with the accuracy of discovered subgraphs.

Conclusions:

• DFG offers a robust solution for privacy-preserving frequent subgraph mining.
• The algorithm successfully mitigates privacy threats in graph data analysis.
• DFG provides a practical approach for extracting valuable insights from sensitive graph datasets without compromising privacy.