5 papers · 1 filter
The Power of Interaction in Locally Edge-Private Subgraph Counting
Xian Chen, Pan Peng
We study (non-induced) subgraph counting under interactive local edge differential privacy (LEDP). Given a fixed pattern graph with vertices, edges, and conn…
Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds
Pan Peng, Ranran Shen
Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is r…
Differentially Private Range Subgraph Counting
Xian Chen, Ruobing Bai, Pan Peng
Subgraph counting is a fundamental problem in graph analysis. Motivated by practical scenarios where graph analytics are performed on subgraphs induced by selected vertices -- rath…
A Differentially Private Clustering Algorithm for Well-Clustered Graphs
Weiqiang He, Hendrik Fichtenberger, Pan Peng
We study differentially private (DP) algorithms for recovering clusters in well-clustered graphs, which are graphs whose vertex set can be partitioned into a small number of sets,…
A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time
Ranran Shen, Pan Peng
We address the problem of designing a sublinear-time spectral clustering oracle for graphs that exhibit strong clusterability. Such graphs contain latent clusters, each charact…