# Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts

arXiv: https://arxiv.org/abs/2507.14835 · HTML: https://mlsanity.com/paper/2507.14835/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 55 references that are in the map.
- First posted on arXiv 20 Jul 2025.

## Builds on (most cited first, 18 of 18)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Memory in network flows and its effects on spreading dynamics and community detection](https://mlsanity.com/paper/1305.4807/) (2013)
- [KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey](https://mlsanity.com/paper/2110.01858/) (2021)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Private Graph Data Release: A Survey](https://mlsanity.com/paper/2107.04245/) (2021)
- [Recursive Mechanism: Towards Node Differential Privacy and Unrestricted Joins [Full Version, Draft 0.1]](https://mlsanity.com/paper/1304.4795/) (2013)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Optimal Bounds on Private Graph Approximation](https://mlsanity.com/paper/2309.17330/) (2023)
- [Communication-Efficient Triangle Counting under Local Differential Privacy](https://mlsanity.com/paper/2110.06485/) (2021)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Near-linear Size Hypergraph Cut Sparsifiers](https://mlsanity.com/paper/2009.04992/) (2020)
- [Triangle Counting with Local Edge Differential Privacy](https://mlsanity.com/paper/2305.02263/) (2023)
- [Motif Cut Sparsifiers](https://mlsanity.com/paper/2204.09951/) (2022)
- [How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity](https://mlsanity.com/paper/2210.03831/) (2022)

## Built on by (most cited first, 1 of 1)

- [Differentially Private Range Subgraph Counting](https://mlsanity.com/paper/2606.08179/) (2026)

## Abstract (arXiv)

We study the problem of releasing a differentially private (DP) synthetic graph G' that well approximates the triangle-motif sizes of all cuts of any given graph G, where a motif in general refers to a frequently occurring subgraph within complex networks. Non-private versions of such graphs have found applications in diverse fields such as graph clustering, graph sparsification, and social network analysis. Specifically, we present the first (varepsilon,δ)-DP mechanism that, given an input graph G with n vertices, m edges and local sensitivity of triangles ℓ3(G), generates a synthetic graph G' in polynomial time, approximating the triangle-motif sizes of all cuts (S,Vsetminus S) of the input graph G up to an additive error of tildeO(√mℓ3(G)n/varepsilon3/2). Additionally, we provide a lower bound of Omega(√mnℓ3(G)/varepsilon) on the additive error for any DP algorithm that answers the triangle-motif size queries of all (S,T)-cut of G. Finally, our algorithm generalizes to weighted graphs, and our lower bound extends to any Kh-motif cut for any constant h≥ 2.