Differentially Private Frequent Subgraph Mining.

Area of Science:

• Data Mining
• Privacy-Preserving Technologies
• Graph Analytics

Background:

• Frequent subgraph mining (FGM) is crucial for analyzing graph data.
• Releasing frequent subgraphs from sensitive datasets poses significant privacy risks.
• Existing FGM methods often lack robust privacy guarantees.

Purpose of the Study:

• To develop a novel algorithm for frequent subgraph mining (FGM) that adheres to differential privacy.
• To address the privacy concerns associated with mining sensitive graph data.
• To enhance the utility of frequent subgraph identification while maintaining rigorous privacy.

Main Methods:

• Introduced a novel differentially private FGM algorithm named DFG.
• Implemented a private frequent subgraph identification approach with candidate pruning.
• Devised a lattice-based noisy support derivation method for improved accuracy.
• Conducted formal privacy analysis to prove epsilon-differential privacy.

Main Results:

• The DFG algorithm successfully identifies frequent subgraphs under differential privacy.
• The candidate pruning technique improves the utility of subgraph identification.
• The lattice-based approach enhances the accuracy of noisy support computation.
• Experimental results demonstrate high data utility on real-world datasets.

Conclusions:

• The DFG algorithm offers a privacy-preserving solution for frequent subgraph mining.
• The method effectively balances data privacy with the utility of mining results.
• DFG provides a robust framework for analyzing sensitive graph data.