Acyclic Graph Pattern Counting under Local Differential Privacy

1. Problem Statement

The paper addresses the challenge of counting acyclic graph patterns (e.g., paths, trees, stars) in a decentralized setting under Edge-Local Differential Privacy (Edge-LDP).

• Context: In Edge-LDP, each node in a graph holds its own incident edges and must privatize this data locally before sending it to an untrusted analyzer. The goal is to estimate the total count of specific subgraphs (patterns) without revealing sensitive edge information.
• Gap: Existing LDP solutions are largely ad-hoc, focusing only on simple structures like stars or triangles. There is no general mechanism for arbitrary acyclic patterns.
• Challenges:
  1. Generalization: Constructing complex patterns from distributed data without relying on structure-specific assumptions.
  2. Node Duplication: Ensuring that nodes in a pattern instance are distinct (no cycles). In decentralized LDP, a single node cannot easily detect if a distant node in the pattern has already been visited, making it hard to prevent duplicates.
• Baseline Limitation: A naive approach using Warner's Randomized Response (RR) to reconstruct a noisy global graph results in poor utility, with an error bound of $O(N^k)$ (where $N$ is the number of nodes and $k$ is the pattern size), which is exponentially worse than the true count scale of $O(N \cdot d(G)^k)$.

2. Methodology

The authors propose a general framework that combines recursive subpattern counting with a random marking technique. The solution is developed in three progressive stages:

A. Foundation: $k$-Line Walk Counting

Before tackling paths, the authors first solve for $k$-line walks (sequences of edges where nodes can repeat).

• Mechanism: A multi-round aggregation approach.
  • Initialization: Each node starts with a count of 1 (representing a 0-length walk).
  • Recursive Aggregation: In round $\ell$, each node aggregates the counts of $(\ell-1)$-length walks from its neighbors, adds Laplace noise scaled to the maximum count from the previous round, and broadcasts the result.
  • Privacy: The privacy budget $\epsilon$ is divided across $k$ rounds ($\epsilon/k$ per round).
• Optimization:
  • Round Reduction: The process can be completed in $k-1$ rounds by having the second-to-last node compute the final step locally.
  • Communication: Nodes only communicate with neighbors (cost $O(M)$) rather than broadcasting to all nodes, reducing total communication from $O(N^2)$ to $O(M+N)$.
• Result: Achieves an additive error of $\tilde{O}(\sqrt{N} d(G)^{k-1})$.

B. Extension: $k$-Line Path Counting

To convert walks into paths (where nodes must be distinct), the authors introduce Random Marking.

• Concept: Inspired by color-coding, each node is assigned a random "mark" (an integer from $0$ to $k$).
• Constraint: A node is only allowed to participate in the specific round corresponding to its mark. For example, a node with mark $r$ only processes data for the $(r+1)$-th position in the path.
• Effect: This enforces that a valid path instance must have distinct marks for all its nodes, effectively preventing node duplication without requiring global visibility.
• Estimation: Since the probability of a specific path receiving the correct sequence of marks is $(k+1)^{-(k+1)}$, the final aggregated count is rescaled by $(k+1)^{k+1}$ to provide an unbiased estimate.
• Privacy: The marks are independent of the graph structure, so publishing them incurs no privacy loss. The Laplace noise is added only to the aggregation steps.

C. Generalization: Arbitrary Acyclic Pattern Counting

The framework is extended to any acyclic pattern (e.g., complex trees) by treating the pattern as a rooted tree.

• Tree Formulation: The pattern is pre-processed into a tree structure with a defined vertex ordering (bottom-up from leaves to root).
• Recursive Subtree Counting:
  • Nodes with marks corresponding to leaf vertices initialize counts to 1.
  • Nodes with marks corresponding to internal vertices aggregate counts from their children (in the tree structure) from neighbors with the appropriate marks.
  • The counts are multiplied (for branching) rather than just summed.
• Result: The mechanism maintains the same asymptotic error bounds and communication efficiency as the path counting mechanism.

3. Key Contributions

1. First General Solution: The paper presents the first general LDP mechanism capable of counting arbitrary acyclic graph patterns, moving beyond specific cases like stars or triangles.
2. Novel Techniques:
   • Recursive Subpattern Counting: An LDP-tailored framework that incrementally builds patterns across communication rounds.
   • Random Marking for LDP: A technique adapted from non-private algorithms to solve the "node duplication" problem in decentralized settings by restricting nodes to specific positions in the pattern.
3. Theoretical Guarantees:
   • Error Bound: For any acyclic pattern with $k$ edges, the mechanism achieves an additive error of $\tilde{O}(\sqrt{N} d(G)^k)$. This is a significant improvement over the $O(N^k)$ error of baseline RR methods.
   • Unbiasedness: The estimators are proven to be unbiased.
   • Complexity: The mechanism runs in $O(k)$ rounds with a total communication cost of $O(M+N)$ and local computation of $O(d(G))$.
4. Specialized Optimization for Stars: A dedicated one-round mechanism for $k$-star counting that achieves state-of-the-art utility without needing random marking.

4. Experimental Results

The authors evaluated their mechanisms on six real-world datasets (e.g., Twitter, Enron, AstroPh) against baseline methods (RR-based enumeration and clipping-based walk counting).

• Utility Improvement:
  • Walk Counting: Up to 110$\times$ reduction in relative error compared to baselines.
  • Path Counting: Up to 2,600$\times$ improvement in utility.
  • Acyclic Pattern Counting: Up to 46$\times$ improvement in utility.
  • Star Counting: Up to 710$\times$ error reduction with relative errors consistently below 0.5%.
• Communication Efficiency:
  • Achieved 300$\times$ to 650$\times$ reduction in communication costs compared to RR-based baselines (which often require $O(N^2)$ communication).
  • The proposed method's communication cost scales linearly with the number of edges ($O(M)$), making it scalable for large graphs.
• Error Analysis: Experiments confirmed that while theoretical analysis suggests sampling error dominates, in practice, the gap between sampling error and DP noise is small. A strategy of averaging multiple runs with reduced privacy budgets per run was shown to further optimize total error.

5. Significance

This work bridges a critical gap in privacy-preserving graph analytics. By providing a general, efficient, and theoretically sound solution for acyclic pattern counting under LDP, it enables the analysis of complex network structures (such as community detection, fraud rings, and information diffusion) in decentralized environments (like social networks) without compromising user privacy. The shift from $O(N^k)$ to $\tilde{O}(\sqrt{N} d(G)^k)$ error represents a fundamental leap in the feasibility of private graph mining for real-world applications.