Summary
The authors introduce a new model for Graph Differential Privacy (GDP) that ensures a parametric level of topological privacy through decoupling of the graph convolution mechanism (i.e., preventing direct neighborhood aggregation of features = standard $AXW$ aggregation). The key definition is that up to $k$ in- and out-neighbours of a randomly selected single node $r$ can be modified to create a new adjacency matrix. This makes this a hybrid between edge ($k=1) and node ($k=n) GDP, the parameter $k$ allows a tradeoff between topology privacy and accuracy. All GNN training is done using this modified graph $D’$ to create the model parameters for inference. The main contribution of the paper is three-fold 1) proving theoretical bounds on the Differential Privacy (DP) state of the art DPGNN called GAP [19] 2) Intuitions from analyzing the DP weakness of GAP to develop a novel Differentially Private Decoupled Graph Convolution (DPDGC) model, which benefits from decoupling graph convolution while providing GDP guarantees 3) theoretical bounds on the DP of their proposed DPDGC. The key intuition is that GAP has greater privacy leakage because they compute $A'H'$ where both adjacency matrix and features change. Motivated by this the authors propose DPDGC in which the $A'H'$ product is avoided thus providing more privacy than GAP.
Strengths
Sound theoretical analysis of the two GDP models
Theoretical analysis of GAP i.e., the presence of the $A'H'$ product which is shown from Theorem 1 to be a contributing factor to the DP limitation of GAP. This leads to their derivation of DPGDC which applies a DP-MLP to adjacency matrix A using a non-linear operation on $AW^{(A)}$ to create the adjacency matrix embedding $Z$, where $W_A$ are fixed model weights. This is opposed to GAP which computes $AH$ for the $Z$ embeddings. By ensuring $W^{(A)}$ is DP, they only need to look at $A'W^{(A)}$ versus $A'H'$ in GAP.
Weaknesses
A big portion of the paper is spent defining the problem and setting up conventions for future Differential Privacy studies to be more suitable to the GNN field/setting.
The novelty of the decoupling method is not very convincing. The idea of decoupling is previously found in this paper [1]"Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods", D. Lim, F. Hohme et. al, Neurips 2021, which defines a method called LINKX for non-homophilous graphs. LINKX separately embeds the adjacency $A$ to $h^A$ and the features $X$ into $h^X$ before mixing adjacency and feature information. The decoupling method proposed here seems to be a modification of the LINKX strategy.
From Table 3, the proposed DPDGC model works well compared to the other differential privacy models when the graphs are heterophilic. This is not surprising because the decoupling idea is known to be beneficial for heterophilic graphs [1]. However, the other baseline methods work better in a homophily setting (columns in the right side of the table) because they are not specifically designed for that kind of setting. I would expect a more adaptive method that works in both settings to be more convinced about the utility of this method.
Also from Table 3, simple MLP outperforms DPDGC in accuracy for higher $k$ on many datasets, especially homophilic ones. As pointed out by the authors themselves, protecting the graph information (higher privacy requirements) quite drastically reduces the utility of these decoupling methods. So the practical utility of this seems questionable.
Questions
What is the practical meaning of high-$k$ topology protection? in other words what are the additional security benefits obtained by going from $k$ to $k+1$. Its not clear to what is the marginal utility of increasing $k$ in terms of the increasing cost to an adversary who wants to break privacy. This is an important question as varying $k$ is the major difference between this work and GAP.
How well will the decoupling method DPDGC work on large scale homophilous graphs with moderately high privacy budgets. I would like to see more extensive experimental results to justify the cost of decoupling versus simple MLP methods.
Fig 1 is hard to understand (contextualize) with a lot of undefined terms (e.g., k-neighbor level adjacency) especially as it comes so early in the paper. Consider moving to later or defining better in-text.
Def 4.3 seems ambiguous: $k$ entries of $A_{rj}$ and $A_{lj}$ are modified but what is the size of $ j + l $( Is $j+l=k$ or $2k$?). Text only says “some” $j$ and $l$.
There are multiple variations of row normalization, are you doing Euclidean norm normalization of each row, it is not clear from the text and obviously it makes a big difference in the proof as it is known that Euclidean row normalization dampens the effect of outliers [1] “Sign and rank covariance matrices” J. of Statistical Planning and Inference, Dec. 2000.
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The authors have addressed the limitations of this work in the appendix. "we do not believe that the current DPDGC model is the ultimate solution for GDP-aware graph learning methods. To support this claim, we note that the nonprivate state of-the-art performance for learning on large-scale homophilic graphs is achieved by standard graph convolution models [47, 48].
The authors have stated that the proposed topic doesn't have any negative societal impacts, instead GDP can potentially protect user data and is beneficial. However this is a generic statement and needs to be proved (to what extent will breaking GDP of a graph impact individual users?)