On provable privacy vulnerabilities of graph representations

Thank you for your valuable comments, we will integrate your suggestions into revised versions of our paper. Below we address some specific points:

Q1: About the writing style

Thank you for the advice and we will polish our writing to improve clarity and conciseness.

Q2: On the limitations of study linear GNNs

Please kindly refer to the first point in our global response. Firstly, it is quite challenging to directly analyze the performance of nonlinear GNNs, especially when the underlying GNNs are with more than 1 layers and the dependence on network depth is a critical factor of the study. Secondly, linear GNNs such as SGC constitute an important type of GNN architecture in practice. By characterizing the provable privacy vulneratbilities of such kind of GNNs, we reveal the threats that can potentially break the privacy of linear graph representations. Lastly, it remains to investigate that whether the inclusion of nonlinearity can mitigate the threat. While answering this question is hard in theory, we conducted extensive experiments demonstrating that nonlinear GNNs are often more vulnerable than linear GNNs.

Q3: Rationale of studying SERA

We chose SERA as the object of our analysis because of it is training-free, and requires a moderate level of adversary knowledge (node embeddings). There exists attacks with higher empirical attacking performance than SERA that utilizes additional knowledge (i.e., a certain part of input graph has already been compromised [1]) and a more sophisticated attacking procedure (i.e., training a shadow model [1]). In this paper, we take a first step toward establishing the vulnerabilities of graph representations in a theoretically principled way by studying the performance of SERA. For those attacks that are more sophisticated than SERA, it is an interesting question to study the improvement of attacking performance by quantitatively characterize the advantage of side information or auxiliary training, which is beyond the scope of our paper and we leave them for future explorations.

Q4: Accuracy of experiment

We agree with you that the definition of feature homophily is not suitable as a proper metric for describing the correlation between edge existence and node feature similarity. We include this metric primarily because this one is defined in previous works [2] and we list it mainly for completeness. The metric that indeed reflect the correlation is the $\widehat{A}^{\text{FS}}$ in table 1, which stands for tha AUC score between feature similarity and edge existence, that takes both edges and non-edges into account. We base most of our empirical findings regarding table 1 on the $\widehat{A}^{\text{FS}}$ metric. Please kindly refer to the experimental observations in section 7.1

Q5: Explaination of the statement in line 286

We appologize for making the statement too difficult to parse, and we shall restate the claim in revisions of our paper. By this statement, we want to express the following:

• When $d$ is small (so that the assumptions in theorem 4.1 no longer holds), the claims in theorem 4.1 no longer holds empirically, as the attacking performances are limited (i.e., AUC score $\le 80\\%$).
• We further explain why the phenomenon of limited attacking performance in small $d$ regime stems from: In our analysis, one primary mathematical tool is the concentration of inner products of two Gaussian vectors, which is highly dependent on the dimension of the two vectors (i.e., the feature dimension). When the concentration is insufficient (a consequence of small $d$), our analysis would then be no longer correct and this partly explains why the attacking performance is limited in small $d$ regimes.

[1] He, Xinlei, et al. "Stealing links from graph neural networks." 30th USENIX security symposium (USENIX security 21). 2021.
[2] Luan, Sitao, et al. "When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability." Advances in Neural Information Processing Systems 36 (2023).

Thank you for your valuable comments. We appreciate your mentioning the two related works and we will include them in the related works of our paper with careful discusssions. As both of them focus on link prediction, we would like to make the following clarification first:

In theory, link prediction is related to, but different from edge reconstruction

Theoretically speaking, the problem of link prediction is formulated as the design of some algorithm $\mathcal{A}$ that takes input a known graph topology $A$ and some auxiliary features $X$ and output a predictor that is able to infer either missing edges in the training graph or generalizes to unseen graphs. Speaking in the context of statistical learning, the goal of link prediction is generalization. However, edge reconstruction is understood as an inverse problem[6] that is formulated as the design of some algorithm $\mathcal{A}$ that takes input a graph embedding with some knowledge on its generation process, and outputs an estimated topology that most possibly yields the graph embedding. The goal of edge reconstruction is not generalization as it recovers input graph in an instance-wise fashion (therefore, we think you probably misunderstood the type of our analysis by refering to it as generalization bounds). The difference here is somewhat reminiscent of that between the study of regression and compressive sensing: The techniques required in the analysis may have overlaps, but the two problems are different and require different types of analysis.

Next we address your questions in detail:

Q1: Are theorem 4.1 and 5.1 trivial, based on recent developments on link prediction?

Now that we have explained the difference between link prediction and edge reconstruction, we state here why the theoretical developments in the two related works do not imply our establishments:

• In [1], the authors focused on dataset properties that may influence the performance of link prediction. The analysis therein is conducted on certain types of random graphs, but the guarantees do not involve any specific algorithms or performance measures. Therefore we do not see any implications of [1] regarding our theoretical interest.
• In [2], the authors derived generalization bounds of linear GNN under a moderately sparse graphon model, i.e., the edge density is of the order $\Omega(\log n / n)$. As we have previously mentioned, the generalization bounds of link prediciton is very different from edge recovery error bounds which is basically an inverse problem. Meanwhile, theorem 4.1 applies to graphs that are potentially much more sparse than those considered in [2] (please refer to assumption (i) in theorem 4.1. Besides, analyzing graphon models in sparse regimes as in our paper, i.e., $p_{uv} = o(\log n / n)$ is highly nontrivial [5]). Therefore, both the analytical setup and goal are different between [2] and our paper.

Regarding your comment that theorem 4.1 "essentially states that the accuracy of correlation detection grows with increasing samples", it is worth mentioning that in most of the theory developments in machine learning we need some sort of complexity that decreases with sample size and this should not be considered as essential implications of theory. Indeed, an important message of theorem 4.1 and 5.1 is that sparsity plays a key role of edge recovery and we are not aware of any previous works that noticed this factor.

Q2: On theorem 6.1 and experiments

Theorem 6.1 is mainly used as a statement that ascertains the protection guarantee of NAG against a wide range of adversaries, it slightly improves previous results [3] by allowing a more flexible choice of victim GNNs. ([3] only considers parameter-free GNN with summation pooling). Theorem 6.1 is indeed much easier to prove than theorem 4.1 and 5.1, and we do not consider theorem 6.1 to be our main theoretical contribution. However, we are interested in whether SERA can be utilized as a privacy auditing tool that empirically elicits the privacy level of NAG which are guaranteed by theorem 6.1------Such kind of empirical investigation is often considered as important research problems: For example, there has been considerable effort in designing MIA to audit DPSGD[4], and in such kind of study, we would need a theoretical privacy guarantee in the first place, which is what theorem 6.1 does.(We will include a more detailed discussion on privacy auditing in our revisions) According to our empirical findings, there are cases when SERA is ineffective but the theoretical privacy level according to theorem 6.1 is vacuous, thereby implying the limitations of SERA as a privacy auditing tool. In section 6, theorem 6.1 also serves as the motivation of our experiments.

Hopefully we have addressed your theoretical concerns, and we would like to have an in-depth discussion with you. Please kindly let us know if you still have any questions regarding our theoretical contributions.

[1] Mao, Haitao, et al. "Revisiting link prediction: A data perspective." arXiv preprint arXiv:2310.00793 (2023).
[2] Chung, Alan, Amin Saberi, and Morgane Austern. "Statistical Guarantees for Link Prediction using Graph Neural Networks." arXiv preprint arXiv:2402.02692 (2024).
[3] Sajadmanesh, Sina, et al. "{GAP}: Differentially Private Graph Neural Networks with Aggregation Perturbation." 32nd USENIX Security Symposium (USENIX Security 23). 2023.
[4] Nasr, Milad, et al. "Adversary instantiation: Lower bounds for differentially private machine learning." 2021 IEEE Symposium on security and privacy (SP). IEEE, 2021.
[5] Xu, Jiaming. "Rates of convergence of spectral methods for graphon estimation." International Conference on Machine Learning. PMLR, 2018.
[6] Pasdeloup, Bastien, et al. "Graph reconstruction from the observation of diffused signals." 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2015.

Thank you for your valuable comments and advices, we will integrate your suggestions into revised versions of our paper. Below we address some specific points:

Q1: Practicality of assumptions in theorem 4.1

According to our understanding, the primary concern is to what extent the assumption $d = \Omega(\text{polylog}(n))$ holds in practice. In our real-world experiments, the Cora and Citeseer datasets could be loosely regarded to satisty the assumption (Cora: $n=2708, d=1433$, Citeseer: $n=3327, d=3703$). Yet satisfiability of this polylog dimension relation seems not to be a necessary condition for SERA to succeed (at least empirically): For example, the Amazon Products and Reddit dataset are much larger in scale with much fewer features, yet the performance of SERA are fairly strong even for $L=5$.
Regarding your question about whether the polylog factor can be removed, we think that the lower bound on $d$ can be improved to have a smaller exponent over $\log n$ (regarding the $6L+2$ in our paper) via a better handling of probabilistic arguments. But currently we do not know how to avoid the $(\log n)^{O(L)}$ dependence, which is an exciting future direction.

Q2: Clarifications of empirical evaluations

We will revise our graphical presentation in figure 1 in revised versions of the paper by adding visible score marks for a better illustration. Regarding your concern about the correctness of our claim in "Large $d$, small $L$" regimes, please kindly refer to our attached pdf file which shows the numerical values of SERA on Erdos Renyi graph with feature dimensions $d \in \\{512, 1024, 2048\\}$. The results demonstrates that the performance peaks at $L=3$ and reduces significantly for $L \ge 8$ across all the setups. It is true that the attack AUROC may still be as large as $95\\%$ when $n$ is large, but the performance drop is also statistically significant as opposed to near $100\\%$ AUROC for $L=3$. Therefore the empircal observations align with our theory findings.
Regarding the missing defnitions in table 1, please kindly refer to our global response for an overview of the design of this table. Specifically, $\widehat{A}^{\text{SERA}}$ denotes the reconstruction is based on SERA over graph representations (we will change it to SERA for clarity in revisions), and the term trained and non-trained are used to indicate how the weight of the underlying victim GNN is obtained, either via random initialization or well-trained.

Q3: Possiblity of incorporating homophily into our theory

This is a very interesting question. In the setup of theorem 4.1 in our paper, we allow the edge generation probability $p_{uv}$ to depend on features $x_u$ and $x_v$ in an arbitrary fashion, which naturally includes the case of homophily. According to our understanding of your question, you might be suggesting the exploration of shaper reconstruction bounds that quantitatively incorporate a homophily measure into the bound that drastically change the complexity. This is a rather challenging task as a good quantitative characterization of homophily in this setup is non-trivial in the first place. While this question is beyond the scope of our paper, it warrants a careful study in the future.