Thank you for pointing out the reference. After carefully reviewing [FHO21], we acknowledge that there is indeed a connection between their work and our manuscript, as both address differential privacy (DP) algorithms for subgraph pattern counting within certain families of subgraphs. However, the families of subgraphs considered in the two works differ fundamentally.
[FHO21] focuses on the family of subgraphs corresponding to those present at any given timestamp, whereas our work considers the family of subgraphs induced by vertices/edges whose attributes fall within specific ranges.
Comparison of Problems:
1. Vertex-Attribute Range Subgraph Counting: For this problem, the two families (and hence the two problems) are incomparable.
2. Edge-Attribute Range Subgraph Counting: Interestingly, we found that our problem serves as a strict generalization of the partially dynamic problem addressed in [FHO21].
- Take the incremental graph sequence as an example: if we view the timestamp of an edge as its edge attribute, then a query corresponding to the range $[1, T]$ in our problem is equivalent to the graph at timestamp $T$ in the incremental graph problem.
- In this sense, the partially dynamic problem is a special case of our edge-attribute range subgraph counting problem, with $d=1$ and the edge attribute being its timestamp. Consequently, our Theorem 2 also provides the corresponding DP guarantee for the partially dynamic problem, with an additive error equal to the global sensitivity of subgraph counting.
3. Pattern Graph $H$:
Finally, [FHO21] limits its analysis to specific pattern graphs, such as triangles and $k$-stars, while our work considers arbitrary constant-size pattern graphs $H$, making it more general in this regard.
4. Algorithm: First, our algorithm uses a tree structure to reduce the amount of noise added, which is similar to [FHO21]. The difference lies in addressing our more general problem (for general pattern graph counting), where we need to perform subgraph projection to pre-process. Additionally, during the tree construction process, unlike their method that considers only the temporal dimension, we construct a two-dimensional tree when \(d=1\), even for triangle counting, to achieve our goal. This is because, intuitively, our algorithm not only needs to compute results for linear timestamp (e.g., $t=1, t=2, \dots$) but also needs to calculate results over a range (e.g., within attributes $[i, j]$).
For noise scale: We agree with the point that adding a maximum degree for privacy may help reduce the error in triangle counting, and we greatly appreciate this insight being highlighted.
There are two cases here for triangle counting:
1. The upper bound of the maximum degree of the input graph is known.
2. The upper bound of the maximum degree is unknown.
For the first case, if prior knowledge of the upper bound on the maximum degree of the input graph $D$ is available (e.g., as assumed in [FOH21], Lemma 15), the global sensitivity of triangle counting becomes $D$. In such cases, we can achieve an additive error $\widetilde{O}(D)$ for triangle counting and attain pure differential privacy.
For the second case, we have analyzed it and found that it achieves approximate differential privacy (($\varepsilon$,$\delta$)-DP) while guaranteeing an error bound of $\widetilde{O}(d_{max})$ by [KRSY14] lemma 4.4 where $d_{max}$ is the maximum degree of current input graph. Interestingly, the scale of the added noise approaches the local sensitivity and small in most case. However, it provides strict theoretical guarantees for only a limited number of regular pattern graphs (see [NHSV24], Theorem 3).
For the experiments: In the experiments, we missed providing the setting instructions for $d=1$. We then considered the Gaussian distribution setting to be realistic. First, many real-world vertex attributes, such as height and weight in populations, follow or approximately follow a Gaussian distribution. Secondly, the error is mainly affected by the number of noise terms rather than vertex attributes. The Gaussian distribution of vertex attributes is sufficient from a verification perspective and practical applications. Moreover, the embedding processing of these public graph features, which makes range queries impossible, has also impacted our experiments.
[KRSY14] Karwa, Sofya Raskhodnikova, Adam Smith, Grigory Yaroslavtsev. "Private analysis of graph structure."
Proceedings of the VLDB Endowment 4.11 (2011): 1146-1157.
[NHSV24] Dung Nguyen, Mahantesh Halappanavar, Venkatesh Srinivasan, Anil Vullikanti. "Faster approximate subgraph counts with privacy." Advances in Neural Information Processing Systems 36 (2024).