Authors: Sofya Raskhodnikova, Adam Smith, Connor Wagaman, Anatoly Zavyalov

We initiate an investigation of node differential privacy for graphs in the local model of private data analysis. In our model, dubbed LNDP, each node sees its own edge list and releases the output of a local randomizer on this input. These outputs are aggregated by an untrusted server to obtain a final output. We…