SoK: Differential Privacy on Graph-Structured Data
  In this work, we study the applications of differential privacy (DP) in the
context of graph-structured data. We discuss the formulations of DP applicable
to the publication of graphs and their associated statistics as well as machine
learning on graph-based data, including graph neural networks (GNNs). The
formulation of DP in the context of graph-structured data is difficult, as
individual data points are interconnected (often non-linearly or sparsely).
This connectivity complicates the computation of individual privacy loss in
differentially private learning. The problem is exacerbated by an absence of a
single, well-established formulation of DP in graph settings. This issue
extends to the domain of GNNs, rendering private machine learning on
graph-structured data a challenging task. A lack of prior systematisation work
motivated us to study graph-based learning from a privacy perspective. In this
work, we systematise different formulations of DP on graphs, discuss challenges
and promising applications, including the GNN domain. We compare and separate
works into graph analysis tasks and graph learning tasks with GNNs. Finally, we
conclude our work with a discussion of open questions and potential directions
for further research in this area.
