BARC talk by Quentin Hillebrand

Tuesday, March 11, 2025, Quentin Hillebrand, PhD student at the University of Tokyo, Japan, will give a talk on "Private Cycle Counting for Degeneracy-bounded Graphs".

Abstract:

Differential privacy has emerged as the gold standard for protecting individual data while enabling meaningful analysis, with increasing attention given to privacy-preserving computations on graph data. Edge local differential privacy (LDP) ensures that each user’s connections remain private by introducing noise before data is shared. While previous research has focused on counting subgraphs, particularly triangles, under LDP, existing methods suffer from high error rates, making them impractical for large-scale graphs such as social networks. 

In this talk, Quentin addresses the challenge of cycle counting under edge LDP, with a focus on degeneracy-bounded graphs—common in real-world networks. He presents a novel algorithm that significantly reduces error compared to prior work. His approach introduces a preprocessing step where nodes estimate and privately share noisy versions of their degrees, allowing for an approximate vertex ordering. This ordering enables more structured subgraph counting, reducing variance and improving accuracy. Specifically, this method achieves an expected l2-error of 

O(n^{k-1 / 2}) for counting cycles of length k, outperforming previous techniques that scale as O(n^{k-1}) or worse. 

The talk is structured into two parts. First, Quentin will provide an overview of subgraph counting under edge LDP, reviewing existing results and their limitations. Then, he will delve into the details of our recent work, explaining the theoretical foundations, algorithmic innovations, and experimental results. The findings demonstrate significant accuracy improvements for practical graph settings, making LDP-based subgraph counting more feasible.

Bio:
Quentin Hillebrand is a PhD student at The University of Tokyo, specializing in graph differential privacy. After obtaining his Master’s degree in computer science in France, he started his PhD on subgraph counting under local differential privacy. The proposed methods aims at addressing common shortcomings such as bias, high communication cost and poor accuracy.

Host:
Jacob John Imola