On provable privacy vulnerabilities of graph representations
Authors: Ruofan Wu
Guanhua Fang
Mingyang Zhang
Qiying Pan
Tengfei LIU
Weiqiang Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: privacy
graph representation learning
non-asymptotic analysis
privacy attacks
Primary area: privacy

Abstract: Graph representation learning (GRL) is critical for extracting insights from complex network structures, but it also raises security concerns due to potential privacy vulnerabilities in these representations. This paper investigates the structural vulnerabilities in graph neural models where sensitive topological information can be inferred through edge reconstruction attacks. Our research primarily addresses the theoretical underpinnings of similarity-based edge reconstruction attacks (SERA), furnishing a non-asymptotic analysis of their reconstruction capacities. Moreover, we present empirical corroboration indicating that such attacks can perfectly reconstruct sparse graphs as graph size increases. Conversely, we establish that sparsity is a critical factor for SERA's effectiveness, as demonstrated through analysis and experiments on (dense) stochastic block models. Finally, we explore the resilience of private graph representations produced via noisy aggregation (NAG) mechanism against SERA. Through theoretical analysis and empirical assessments, we affirm the mitigation of SERA using NAG . In parallel, we also empirically delineate instances wherein SERA demonstrates both efficacy and deficiency in its capacity to function as an instrument for elucidating the trade-off between privacy and utility.

On provable privacy vulnerabilities of graph representations
Ruofan Wu
Guanhua Fang"
Mingyang Z Qiying Pan
Tengfei Liušt, and Weiqiang Wang
Ant Group
Fudan University
Shanghai Jiao Tong University
(ruofan. wrf, zhangmingyang. zmy, aaron.ltf, weigiang.wa./banttgnnn wwg.bantgroup..com
fangghOfudan hwwp:/fuuanndduu...ommo enu.cn, ain10_ariyy@ajtu. edu.e cn
Abstract
Graph representation learning (GRL) is critical for extracting insights from com- plex network structures, but it also raises security concerns due to potential privacy vulnerabilities these representations. This paper investigates the structural vul- nerabilities in graph neural models where sensitive topological information can be inferred through edge reconstruction attacks. Our research primarily addresses the theoretical underpinnings of similarity-baze edge reconstruction attacks (SERA), furnishing a non-asymptotic analysis of their reconstruction capacities. Moreover, we present empirical corroboration indicating that such attacks can (almost) per- fectly reconstruct sparse graphs as graph size increases. Conversely, we establish that sparsity is a critical factor for SERA's effectiveness, as demonstrated through analysis and experiments on (dense) stochastic block models. Finally, we explore the resilience of private graph representations produced via noisy aggregation (NAG) mechanism against SERA. Through thcoretical analysis and empirical assessments, affirm the mitigation of SERA using NAG. In parallel, we also empirically delineate instances wherein SERA demonstrates both efficacy and deficiency in its capacity to function instrument for elucidating the trade-off between privacy and utility.
Introduction
With the surging developments of graph representation learning (GRL) [15], there has been growing apprehensions concerning the security challenges associated with the deployment of graph neural models in real-world scenarios [10]. GRL models harness the topological information of the un- derlying graph for producing high-quality predictions or graph representations. Mcanwhile, these models bear the risk of inadvertently divulging the same topological information through the graph representations they produce. Such kind of security risks have been empirically validated through the examination of the attacking performance of edge reconstruction algorithms [11, 17, 34, 46), among which simple form of attack based solely the representation similarity of node pairs is shown achieve strikingly strong performance, without the requirement of additional knowledge like encoder architecture or auxiliary datasets [17].
'Equal contribution
Corresponndng author: aaron. wwtttanttrroup..ommmm
"ode available htttp://ggithee httpaaa...oo..eeeccccaceeeeeeaee htwp:///nann...a..iaaraaaa.aaaaa
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Despite the empirical evidence of topological vulnerabilities of graph representations, theoretical explanations delineating the effectiveness of such attacks remain largely unexplored: As demonstrated in previous studies [11, 17], similarity-basee attacks are remarkably effective against sparse graphs that exhibit a generalized homophily pattern, i.e., there exists a significant correlation between the similarity of node features and edge adjacency information. This phenomenon posits that feature similarity may serve as a confounding factor, potentially impacting the efficacy of similarity-bas attacks. It is therefore valuable to understand the influence of graph properties, such as feature similarity and sparsity, on the edge reconstruction process of the attacking procedures.
Beyond their capability in characterizing the vulnerabilities of representations, attacking algorithms may also function as empirical attestations of Srivacy-preserviie inference protocols that fulfill formal privacy guarantees such as differential privacy [9, Section 4J. As an illustrative case. membership inference attacks can be employed for auditing differential privacy [31]. Since edge reconstruction equívalent to edge membership inference on graphs [43], it is thus pertinent to explore the performance of similarity- -based attacks when confronted with
graph representations [30, 36).
In this paper, we take initial steps toward a principled understanding of structural vulnerabilities of graph representations under the similarity-based edge reconstruction attack (hereafter abbreviated as SERA) which forms realistic threat in many practical scenarios such as vertical federated learning [36]. In particular, we establish the following theoretical as well as empirical findings:
(i) Success modes of SERA Through applying SERA to sparse random graphs equipped with independent random node features, we show that SERA provably reconstructs the input graph via non-asymptotic analysis. The result indicates that feature similarity is not necessary for SERA to succeed. We conduct both synthetic experiments as well as real-world data evaluations to empirically validate theory.
(ii) Failure modes of SERA We show, through theoretical analysis and corroborative synthetic experiments, performance lower bounds when applying SERA stochastie block models (SBM) with independent random node features: When the underlying SBM has (11) intra-group connection probability, edge recovery through graph representations becomes provably hard.
(iii) Mitigation of SERA We assess the resilience of SERA using noisy aggregation (NAG) as the privacy protection mechanism. Theoretical guarantees of NAG are established which further extends previous results, accompanied by extensive empirical evaluations to corroborate our theoretical assertions. Intriguingly, our findings reveal instances wherein NAG provides significant resistance to SERA, even under some scenarios where it only guarantees very weak privacy. Such discoveries delineate the cireumstances that elucidate both the strengths and limitations of SERA as a privacy auditing tool.
2 Related works
Typically, there exist two categories of private information that may potentially be compromised during the training or deployment phases of graph neural network models: The (sensitive) node attributes and the adjacency relation between nodes. In this paper we focus on the later category since edge adjacency relations are less informative, i.e., for each pair of nodes, the existence of an edge constitutes only single bit of information.
2.1 Edge reconstruction attacks on graph-structut data
Contemporary developments on edge reconstruction attacks differ significantly in their conceptu- alization of adversaries, particularly in terms of their capabilities [45, 44] and the extent of prior knowledge they possess about the GRL model and the underlying graph dataset [17]. The mechanism of SERA was first proposed in [11] and later studies in [17]. Empirical evidences suggest that with only black-box access to node representations, the SERA mechanism obtains high success rate (AUC > 0.9 for the Citeseer dataset). Subsequent developments have explored stronger attacks under more powrful adversaries. In [17] the authors investigated the impact an adversary's prior knowledge, including the possession of node features, partial graph structure, and access to shadow dataset, on the success rate of corresponding attack strategies. Inspire by information bottleneck, [46] improves SERA via carefully exploiting intermediate representations produced by GNNs. Notably,

---

despite the adversaries in [17, 46] being equipped with substantially more information compared to SERA, the resulting enhancement in attack performance exhibited by these adversaries demonstrates only marginal improvements relative to SERA. The GraphMI attack [45] disables the adversary from being able to acquire node representations but instead requires access to node features and labels, as well as white-box access to the GNN model. Recent works explored influence based attacking schemes, wherein the adversary is allowed to alter the graph information: The LinkTeller attack [34] manipulates node features while [23] infiltrates the underlying graph with malicious nodes.
2.2 Theoretical explorations in graph recovery from neural representations
In [6]. the authors proposed an algorithm that provably recovers graph structure based on repre- sentations generated via DeepWalk, which is
iitooiizaton-basee procedure and different from GNN-produced representations. In [43] the authors showed that when block structure exists in the underlying graph, the performance of SERA is uneven across node in different blocks. In [46], the authors use information-theoree
arguments to construct more powerful attacks than SERA. Nevertheless, the aforementioned studies did not provide a theoretical rationale for the practical vulnerabilities manifested as a result of the SERA, In a contemporary work [8], the authors derived generalization bounds of linear GNN under the link prediction context assuming the underlying graph generated by a moderately sparse graphon model.
2.3 Privacy protection against edge reconstruction attacks
Edge differential privacy (EDP) [26] is the most popular privacy notion that offers a formal protection against edge reconstruction attacks. Standard private training algorithms like DPSGD [1] may produce GNN models that is provably private in the sense that membership information of any individual training sample limitly disclosed." 2 However, such approaches do not provide privacy during inference time [7]. Protection mechanisms against inference-time adversaries are mostly based on noisy version of GNN encoding such as edge-wise randomized response [34] that provides very strong privacy protection yet being overly destructive to model utility. Noisy aggregation (NÁG) mechansims [30, 36, 7] are recently proposed that empirically achieves better privacy-utility trade-offs. Inspired by the information bottleneck principle, [33, 46] proposed to regularization or saddle-point optimization techniques to control privacy leakage. Yet these proposals are not principled in theory.
3 Preliminaries
Setup and notations Consider an undirected graph G = EV with n |V| nodes associated with node features X E Randd Denote A as the corresponding adjacency matrix and D as the diagonal matrix with the v-th diagonal entry being the degree of node In this paper, we will study victim models taking forms of graph neural encoders. Our vulnerability analysis predominantly centers on the linear graph neural network [35] architecture which has been widely adopted in previous theoretical studies on graph neural networks [3, 39, 37, 8J. Specifically, the node representation matrix of an L-layer linear GNN computed as:
H(L) = -0D+
xW,
where the identity matrix is added for ensuring self-loops, and W E Rdxd the weight matrix. Throughout this paper, we will assume the node feature dimension and the hidden dimension to be equal to d and refer to this as the feature dimension, as otherwise we may add an extra input projection to fulfill this requisite. We further denote || and x(W) as the operator norm (i.e., largest singular value) and condition number (i.e., the ratio of largest and smallest singular value) of matrix W.
Threat model We assume the adversary knows the node set V and is able inquire node rep- resentations of an arbitrary node subset Vvictim C V. Hereafter we will refer to the subgraph induced via Viisiim as the victim subgraph Gvietim = (Vvictim E. The goal of the adver- sary is to recover an arbitrary fraction of Evictim based on the acquired node representations
Note that this require careful sensitivity analysis with respect the correct privacy model like EDP.
3

---

victim - -1,4 n E Vvictmm, L 0. We identify two representative scenarios that underscore the potential threat by such adversaries: The first scenario is API-style deployments of graph rep- resentations [34], wherein adversary might query the node representations for set of nodes using their node identifiers, with this particular subset of nodes constituting the victim nodes. The second scenario pertains to a two-party vertical federated learning (VFL) context [36], wherein the graph topology retained by party A is deemed confidential. Under such a setup, the privacy threat materializes as party B might adhere the VFL protocol while simultaneously being curious about the topology. Note that the capabilities of the adversaries posited herein are intentionally constrained by denying them access both the raw node features X and the model parameters. Additionally, the objectives of the adversary are decidedly ambitious, aiming at the potential recovery of the entire suite of edges within the victim subgraph. A more in-depth discussion regarding the threat model and the potent capabilities of the adversary is deferred to appendix B.I.
H
The SERA is based on similarity measure sim, with the adjacence relation between node u and node v inferred as
ASERA (T) 1 (iim (n n(()) 2 7)
where we denote 1(.) as the indicator function. In this paper we will be primarily interested in two similairty measures: The cosine similarity cos(x, y) (x, v) /[|==]/] ||v|l2) and correlation similarity corr(z, 1) = (xr E, y - 9)
#122 fl - Ø112). which is essentially a centered version of cosine similarity (æ, are coordinate-we wise averages of x and y) defined for node representations with dimension greater than 1. The cutoff threshold r is allowed to depend on the embedding set vietm but is uniform across all edge decisions. Hereafter without misunderstandinggs we will drop the superscript and denote A(T) as the reconstructed adjacency matrix under threshold To measure the performance of the attack, we use false positive rate (FPR) and false negative rate (FNR) defined
as
FPR, A (T) Eu.o 1 (Au)(t)=1)44 (Auu = 0)
=
FNR, (7) = E., 1 (Auu(T) = 0) (Auu = 1)
(3)
En, (Aue 0)
Σn, 1 (Auv = 1)
We further define the error rate ERR as the summation of FPR and FNR. Employing these metrics facilitates more nuanced characterization of attack performance, particularly when the underlying graph is sparse. An alternate metric that is often used in practice [17] is the area under the receiver operating characteristic curve (AUROC) metric
AUROC Ā = /'' (1 FNR (FPR A (s)) ds
which quantifies the aggregate performance of A by integrating the trade-off between the false positive rate and the false negative rate across different thresholds.
Intuitively, the success of SERA is determined by the correlation between node representation similarity and edge presence. Previous empirical observations demonstrate the effectiveness of SERA against graphs that exhibit strong correlations between node feature similarity and edge presence [17]. We will refer to such kinds of graphs as being homophilous in generalized sense [18, 22]. We defer a more formal introduction to homophily measrues to appendix B.2. Due to the gressage-passing nature of GNN encoders, it is intuitively reasonable that recursive aggregation of node representations strengthens the correlation and results successful edge reconstructions. However, it is non-trivial
whether SERA mechanism may succeed in the absence of the aforementioned generalized homophily pattern, which motivates our first analysis.
SERA against sparse random graphs
In this section, we study the behavior of SERA with the underlying (victim) graph generated according to a sparse random graph. Here, the adjacency matrix is generated such that each entry is independently distributed (up to symmetric constraints Aue = Avw) following a Bernoulli distribution Am Ber(pw.). We focus on the sparse regime and allow puv to depend on X,, and X,, We further assume that the node features X, 's are generated i.i.d. according to isotropic Gaussian distribution X, (O, Ia). It follows that the correlation of node feature similarity and edge presence zero. The following theorem characterizes the effectiveness of SERA under the sparse random graph setup.

---

Theorem 4.1. Let C1. C2 be universal constants, Assume the following:
(i) The graph generation mechanism satisfies EvEV Puv < C1 log holds for all E V.
(ii) The depth of GNN encoder L and the feature dimension satisfies
(C2 (C)logn) 6T,42 logn.
(iii) The condition number of the GNN encoder weight satisfies
d
(k(W))² 2 8(C2 log n)82
(5)
logn'
Then there exists threshold T = θ (C2 (T22Togn)T such that with probability at least 1 - n the
2
following holds for SERA with the similarity measure chosen either as COS or corr:
FNR a (T) = O, (PRA(T) (C2 (C2logn)2r
(6)
(Ca log n)
Consequently, on the above of events we have AUROCA 2
Theorem 4.1 implies that, even when SERA can not borrow strength from the homophily nature of the underlying graph, able to produce accurate reconstructions when the graph is sufficiently large and sparse, with the sparsity defined in the sense that each node has at most Ollog n) neighbors on average. An additional intriguing implication from theorem 4.1 pertains to the dependence of reconstruction performance on the GNN encoder depth L: Provided that the node feature dimension sufficiently large, the reconstruction performance degrades when the depth of the encoder increases, which is related to the renowned phenomenon of oversmoothing in GNN literature [37]. Intuitively, as the depth GNN encoders increases, the resulting node representations tend to converge [27], becoming less distinct from one another. This convergence diminishes the discriminative capacity of similarity metrics, thereby affecting the attack performance.
Remark 4.2 (Practicality). Theorem 4.1 requires the node feature dimension to grow in a polylog(n) rate, condition which may not consistently align with practical scenarios. At present, this require- ment is a byproduct of our proof strategy. In section 7.1 we will further examine the implications of feature dimensionality. The existence of threshold that theorem 4.1 manifests might not guide the choice of threshold in practice. Instead, we may rely on heuristics or side-information [17] to determine the threshold. Furthermore, Theorem 4.1 posits that the efficacy of SERA is contingent upon reasonable conditioned weight matrix W. We will empirical validate this claim in section wherein we demonstrate robust reconstruction capabilities of the SERA across diverse scenarios including when the weight matrix W is fixed entity, when it is subject to random initialization, or when has undergone extensive training iterations utilizing datasets from real-world supervised learning contexts.
5 SERA against dense SBMs
In this section, we reveal the limitation of SERA by constructing a reconstruction problem that is provably hard. We consider the following stochastic block model (SBM) [2], where each node is assigned a community membership from one of K groups k(v) E [K]. The (u, w)-th entry of the adjacency matrix is generated as
Ber(p), k() = k(v) Ber(g): otherwise
Aue
(7)
For ease of presentation, we further assume that the groups share the same size, i.e., n a multiple of K. Denote the generation mechanism as G Grom (n., K, K,p.O 9). We have the following result:
Theorem 5.1. Let G ~ Gatmm (n, K, p. 9) and p = (1). Assume the GNN encoder to be of depth L and feature dimension d > max (log n/pp, 12l'g n} with the weight matrix being the identity matrix. Then with probability at least 1 - 1/nn2, for any fixed T E (0, 1), one of the following three statements must hold for SERA with similarity measure chosen either as COS Corr:
5

---

(i) FPR (T) 2 2K
1 and 2
A (T) 2 2'
(ii) FPR (T) 2
1-
+
1-a
2k
(iii) FNR: A (T) 2 E +
According to theorem 5. given any cutoff threshold if the within-group connection probability is of the order (1)) and the number of groups K does not diverge (Otherwise, we will return to the sparse regime section 4) , the performance of SERA measured by error rate ERR is lower bounded by non-vanishing constants when the feature dimension is sufficiently large. The theorem characterizes the inherent limitations of SERA when the underlying graph is dense, As K gets large, the lower bound of false positive/negative rate decreases. It indicates that SERA is more successful when the graph less connected.
Remark 5.2. Alternatively, we may interpret theorem 5.1 as unveiling instances where SERA is constrained to revealing only population-level relational informationnSttte as the affiliation of two nodes to a common group-rather rather than identifying the existence of specific edges when the underlying graph is dense and admits certain group structures.
6 Defense by noisy aggregation: From theory to practice
Having demonstrated the susceptibility of GNN representations to SERA, it becomes an intriguing research question examine the behavior of SERA within the context of privacy-pressevvee GRL: In this section, we explore the defensive efficacy of noisy aggregation (NAG), which has been proposed recently provably privacy- sewacc-preserving algorithm [30, 36] under the edge differential privacy model [26]. Concretely, we study an L-layer noisy GNN with the 1-th layer computed recursively as:
0 = Act (AGG (Wi
H
u N(w) + +c) c N(O,
(8)
2
where N(v) == (w) U (b) denotes node e's extended neighborhood and H denotes the repre- sentation of node at the 1-th layer. The aggregation mechanism AGG is permutation invariant function that defines the message-passing process and Act is some (possibly) non-linear transform. Intuitively, the NAG methodology can be understood a privatization protocol that incorporates both normalization step and an additive Gaussian perturbation phase into the conventional message- passing framework, which typically forms the backbone of GNN. In this paper, we consider representative GNN architectures that allows NAG privatization: GCN [20], GAT [32]. SAGE [14] with mean or max pooling, and GIN [38] with their formal definition deferred appendix B.3. The following theorem characterizes the defensive capability of NAG:
Theorem 6.1. For any graph G and SERA under any type of similarity measures, the inference error regarding any specific edge is lower bounded by:
min WEV.eV [P (A(Au 1|Auc -) + P +P(Au = -. Auv = -1)m===]]]] 1)]21-1 1-111 exp (-oZier I
Here the constant deperals on the AGG mechanism of the GNN. In particular, for some standard GNN architectures we have: CGex = CMEAN = CGN 1 and GGAT = CMAA-SNGE 4.
Theorem 6.1 augments existing literature in the sense that it extrapolates upon prior analyses [30, 36] by generalizing to broader range of aggregation mechanisms, thereby encompassing the vast majority of foundational components integral to modern GNN models. Theorem 6. indicates that for any node pairs in any graph, the summation of type-I error and type-II error (in the language of binary hypothesis testing [21]) incurred by any SERA adversary is lower bounded by a constant, which will be significantly above zero when the noise scale is of the same order to the operator norms of the weight matrices of the GNN encoder. In fact, theorem 6.1 holds against a much stronger family of adversaries, which discuss in appendix C.3.
Empirical proctection of NAG implementing NAG with a large noise scale according to theorem 6.1 may seriously degrade model efficacy. Contemporary insights [5] suggest that strict adherence to theoretical prescripts may not always be necessary, especially the face of empirical adversaries whose capabilities may not rise to the level presumed by the defense mechanisms postulated. In this

---

paper we conduct a careful empirical investigation to assess the privacy-utility trade-off of NAG, with privacy evaluated by the SERA adversary. This investigation could also provide empirical evidence of the SERA's s viability as tool for auditing private GRL algorithms [9]. Furthermore, theorem 6.1 identifies a key determinant of the theoretical privacy bound for NAG -the relative scale of the weight norms regarding the noise intensity. In light of this observation, we propose two distinct noise-infused training paradigms:
Unconstrained scheme We choose a fixed noise scale a during both training and inference no constraints over the weights. The resulting model might not produce meaningful privacy guarantees in the sense of theorem 6.1 as the operator norms of weights are determined by the training dynamics.
Constrained scheme We choose fixed noise scale during both training and inference and use normalization techniques [25] to provide a priori control of model weights, thereby providing tighter control of formal privacy level according to theorem 6.1.
We will empirically inspect the protection of NAG representations trained via both unconstrained and constrained schemes against SERA in section 7.3.
Remark 6.2 (Altemaativ defenses). Beyond the scope of NAG, alternative defense mechanisms offer demonstrable protection assurances, one notable example being edge-wise randomized response (EdgeRR). A comparison with such alternatives is reported in appendix D.5. Preliminary experimen- tal comparisons indicate that NAG customarily realizes more favorable balance between privacy and utility.
Remark 6.3 (Impact of depth L). Theorem 6.1 posits that the privacy guarantees furnished by NAG diminishes with an increment in model depth, which is underpinned by the composition theorems of privacy analysis [12, 24]. An extensive discussion concerning the implications of GNN architectural design on the privacy-utility trade-off, particularly as it pertains to the depth of GNN models trained with NAG, will be provided in appendix E.
7 Experiments
In this section, comprehensive empirical studies are conducted evaluate the effectiveness of SERA against both non-private and private node representations. By default, COS is employed as the standard measure of similarity across all experiments. The results corresponding to the use of corr as metric were found to align with those obtained from COS, concurrence that aligns with observations from [17]. This investigation oriented around three core research questions:
RQ1 (Efficacy of SERA on Sparse Graphs): We evaluate SERA on synthetic datasets generated according theorem 4.1, in addition to 8 real-world datasets to substantiate the effectiveness of SERA.
RQ2 (Deficiency of SERA on Dense Graphs): We evaluate SERA synthetic stochastic block models to corroborate the theoretical assertions theorem 5.1.
We evaluate SERA on privacy-enhanced node rep- resentations across three benchmark datasets generated using NAG with varied levels of noise. The outcomes affirm NAG's capacity for privacy preservation while concurrently delincating the limitations of SERA as tool for privacy auditing.
RQ3 (Mitigation of SERA through NAG):
Evaluation Metrics:
Predominantly, this section documents the performance of attacks using the AUROC metric. A more expansive presentation of the results, inclusive of both AUROC and ERR, is postponed to appendix D.
7.1 Efficacy of SERA on sparse graphs
Erdös-Rényi experiments In our first experiment, we test SERA on graph representations produced by (1) over Erdös-Rént graphs with edge probability p log n with graph size E {100,, 500, 1000). which representative random graph model with controllable sparsity level. We set the weight to be the identity matrix and further present results under random weights in appendix D. We vary the feature dimension d E (2), 2 < S 11} and network depth 1 1 L S 10 in order to obtain fine-grained assessment of SERA. We present the evaluations in figure 4. The results corroborate with our theoretical developments: We demonstrate that SERA able to achieve near near-perfect reconstruction of all edges only in the "large d, small L" regime. Notably, find
7

---

Table 1: Performances SERA on eight datasets measured by AUROC metric (%). The feature homophily Hreatrr (G, X)
TET ((.,)E cos (X,::,)) X,) is an alternate measure of correlation
between feature similarity and edge presence. For each setup, the results (in the form of mean are obtained via 5 random trials.
Squirrel
Chameleon
Actor
Cora
Citeseer
Pubmed
Products
Reddit
Hitaoo
0.01
0.01
0.16
0.17
0.19
0.27
0.01
0.12
Ars
46.2
55.2
44.7
80.3
87.4
87.6
52.0
95.9
Victim model
ASERA, non-trained
LIN(L 2)
72.8
76.1=0.2
73.1
93.1
92.5=0.9
93.9+1.2
97.2+0.3
96.4+o.1
LIN(L 5)
72.620.0
76.0_o.s
73.0
95.920.6
93.820.4
96 06.0
99.2+0.1
95.440.1
GCN(L 2)
8..
87.1.0.6
99.8
99.910.0
99.7....0
99.610.0
97.310.1
GCN(L 82.1
84.3
84.1
99.4
99.9+..0
99.5+a..1
99.2+o.1
96. 96.1+0.2
Victim model
ASERA, trained
LIN(L 2)
74.6go.
75.0
59.9
94.6g0.1
93.720.1
89.0go.1
91.61o.2
94.7
LIN(L 5)
74.1=0.8
76.9=0.2
61.640.7
94.8+0.3
93.3+0.3
88.4g0.9
98.6+0.1
92.3+0.2
GCN(L = 2)
79.420.4
82.3.o.3
78.520.8
97.8g0.1
99.0go.0
89.2ga.3
94.5ga.1
95.1
GCN(L= 5)
77.4=0.6
80.6
78.4
97.4+0.3
98.7+0.2
92.6+0.4
98.4+0.1
95.0+o.1
SERA to be less successful under relatively deep network architectures (i.e., L 2 5) when the feature dimension is sufficiently large. Yet the behaviors in small d regimes appear to be less predictable. 3 Furthermore, the influence of the feature dimension appears to be more pronounced than that of the network depth. This suggests that a greater number of features, despite their independence from graph topology. lead to potentially more privacy risks as transmitted through GNN representations. Conversely, augmenting the network depth does not necessarily correlate with an elevation in the success rate of SERA.
Real-world data experiments Given that the Erdós Rényi model may not sufficiently capture the complexity of real-world graph structures, we evaluated the SERA algorithm on 8 diverse real-world graph datasets that exhibit contrasting patterss of feature similarity and edge formation. The analysis comprises the well-known Planetoid datasets [41], which are distinguished by their high homophily; the heterophilic datasets Squirel, Chameleon, and Actor [29], which demonstrate a weak feature-edge correlation; and two larger-scale datasets, namely Amazon-Produce [42] and Reddit [14]. Dataset statisties are comprehensively detailed in appendix B.2. Half of the datasets analyzed manifest strong positive correlation of feature similarity and edge presence, which is measured via the AUROC of the estimator A (T) 1 (cos(X.., X.) 2 T), while the other half show negligible correlations, an observation underscored in the baseline FAF row of table 1. In all evaluations, we standardize the hidden dimension to d = 128, with the number of GNN layers adjusted to L E 2, 5. Our analysis extends beyond the linear aggregation scheme (1) to encompass four additional prominent GNN architectures: GCN [20]. GAT [32], GIN [38], and SAGE [14]. To discern the effect of training dynamics on the potency of attacks, we delineate results for both pre-training (i.e., random initialization) and post-training stages. A precise account of training methodologies can be found in appendix D.2. Results pertaining to the linear GNN (LIN) and GCN are presented in table with a comprchensive evaluation reserved for appendix D.2. We have the following observations:
Homophily is not necessary for SERA to succeed: The efficacy of SERA on the Planetoid datasets aligns with expectations. However, the outcomes from 4 heterophilic datasets illuminate significant privacy risks, despite a vacuous association between feature resemblance and edge formation. Notably, the Squirrel and Actor datasets, which demonstrate a mild negative feature-edge correlation, are still subject to substantial privacy breach, particularly with nonlinear models. These empirical findings support our theoretical assertion that a graph's 's sparsity plays a more pivotal role in its susceptibility to edge reconstruction attacks than the degree of homophily it exhibits. Moreover, in instances of
"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.
8

---

-00
000
97
9
6 long c
5
10ng 4 0.3
10
16
5
10
(a) Erdós-Rény
(b) SBM
Figure 1: Attacking efficacy of SERA over sparse Erdós Erdös-Rényi graphs and dense SBM graphs, with performance measured in AUROC metric averaged over 5 random trials for each configuration.
comparatively denser networks, such as the Reddit dataset, the homophily of features can be exploited to mount more sophisticated attacks,
Efficacy of Linear GNNs as Proxies for Nonlinear Counterparts: Evidence presented in table 1 suggests that the trends exhibited by linear GNN models are broadly reflective those displayed by their nonlinear, GCN equivalents. It is typically observed that the attack efficacy is modestly reduced in the linear GNN setting, with further details deferred to Appendix D.2.
Influence of Network Depth and Training Dynamics: Table 1 indicates that the post-training performance SERA is frequently less effective compared to the scenarios with randomly initialized weights. This observation may be attributed to the notion that supervised training tends to adversely affect the conditioning weight matrices relative to their initialized state. Additionally, augmenting model depth does not correspond with enhanced attack efficacy, outcome that is in alignment with our theoretical predictions.
7.2 Deficiency of SERA on dense graphs
SBM experiments In this section, we test SERA graph representations over SBM graphs with K = 3.p 0.3.q = 0.05, with the rest of the experimental setups analogous to that in the Erdós Erdós-Rényi experiments. The evaluations are presented figure 7. The results reveal the presence of pronounced barrier that hinders the success of the attack across wide range of configurations corresponding to different network depths and feature dimensions. Furthermore, we observe that the results tend to stabilize the size of the graph increases. We provide further study on the impact of SBM structure in appendix D.I.
7.3 Mitigation of SERA through NAG
In this section, we empirically study the defensive performance of noisy aggregation (8) against SERA We will use the Planetoid datasets [41] for evaluation. We consider a transductive node classification setting and use the standard train-test splits. The GNN models are trained using the training labels and evaluated on the test nodes. The performances of SERA are evaluated on the subgraphs induced by the test nodes. We report the configuration of GNN encoding, as well as the attacking pipeline and training hyperparameters in appendix D.3.1. Due to space limits, we report results on the Cora dataset under GCN and GAT in the main text and postpone the complete report in appendix D.3. We use the following two types of training configurations as proposed in section 6:
Under the unconstrained scheme, scale range E 1,2,4, with a = 0 indicating no protection, and d E (2',5 S 13).
aggressive perturbation plans by applying noise with
Under the constrained scheme, adopt the spectral normalization technique [25] to control the spectral norm of each layer at approximately (with relative error < 10%). We use conservative perturbation plans by applying noise with scale range E {0, 0.01, 0.05, 0.1, 0.5, 1}, and d e 5 5 < 13). Note that with o = 1, we obtain a non- vacuous lower bound according to (9). We observations and findings as follows:
present the evaluations in figure 2 and summarize
SERA empirically elicits privacy-utility trade-off under the constrained scheme When the noise level is moderate, i.e., E {0.01, 0.05). The result demonstrates that privacy and utility are, at least some extent, at odds: Under lower noise level, SERA is able achieve non-trivial success especially when d is small. Furthermore, raising the feature dimension d results in both decrease

---

GCN(Cosstrabee))
(Constttr)))
GCN(Unoosrrsdeed
AUROC
c.00
AUROC
-100
(a) SERA performance
(b) SERA performance
SERA performance
(d) SERA performance
(Cnetttii))))))
GAT/Uacastraine)
06
3.5
06
0.5
02
32
02
02
(c) model performance
model performance
g model performance
(h) model performance
Figure 2: Privacy and utility assessments on the Cora dataset with underlying model of NAG being GCN and GAT. The first row contains attack performances SERA measured using AUROC metric under both constrained and unconstrained training scheme. The second row presents corresponding model performances.
in utility well as increase in privacy. This is actually predictable: Since we explicitly control the operator norm to be around 1, a larger d implies a smaller "signal-to-noise ratio" with the signal being (loosely) defined as the magnitude of the aggregated node representations.
SERA losses power against NAG using larger ds in the unconstrained scheme A surprising evidence according to figure 2 is that when the feature dimension d is sufficiently raised, i.e., > 1024, the attacking performances degrade. Consequently, we are able to achieve decent protection against SERA (AUROC < 0.6) while at the same time incurring slight degradation in model utility (> 0.7 Accuracy in Cora) Moreover, the phenomenon is more evident for higher noise levels. While the outcome seems favorable insofar as we have identified GNN solutions that manifest both high performance and a degree of privacy since the training procedure is unrelated to the attacking mechanism, these solutions may exhibit diminished robustness, the corresponding Lipschitz constants are likely to be inadequately regulated [40]. Due to space limits, we postpone a more detailed discussion appendix D.4.
8 Discussion and conclusion
In this paper, we have studied the behavior of the SERA adversary by characterizing its performance against different kinds of underlying graph structures as well as encoding mechanisms. Theoretically, we first identify sparse random graphs where SERA provably reconstructs the input graph, which ascertains the empirical findings of previous works. We then reveal limitations of SERÀ by showing its performance lower bounds when the input graph follows a dense SBM. Additionally, we discuss protection mechanisms to SERA by exploiting both theoretically and empirically the defensive capa- bility of NAG. Empirical investigations corroborate with our theoretical findings, while suggesting intriguing phenomenons that questions the viability of SERA as formal privacy auditing procedure for private graph representations. Notwithstanding, several research problems warrant further study, which we discuss in appendix alongside with the limitations of this paper.
10

---

9 Acknowledgements
The authors from Ant Group are supported by the Leading Innovative and Entrepreneur Team Introduction Program of Hangzhou (Grant No.TD2022005) Guanhua Fang is partly supported by the National Natural Science Foundation of China (nos. 12301376).
References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] E. Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018.
[3] Awasthi, A. Das, and S. Gollapudi. A convergence analysis of gradient descent on graph neural networks. Advances in Neural Information Processing Systems, 34:20385- 2021.
[4] C. L. Canonne. A short note on inequality between kl and tv. arXiv preprint arXiv:2202.07199. 2022.
[5] N. Carlini, C. Liu, U. Erlingsson, J. Kos, and D. Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In 28th USENIX Security Symposium (USENIX Security 19), pages 267-284, 2019.
[6] S. Chanpuriya, C. Musco, K. Sotiropoulos, and C. Tsourakakis. Deepwalking backwards: from embeddings back to graphs. In International Conference on Machine Learning, pages 1473-1483. PMLR, 2021.
[7] E. Chien, W.-. Chen, C. Pan, P. Li, Ozgur, and O. Milenkovic. Differentially private decou- pled graph convolutions for multigranular topology protection. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[8] A. Chung, A. Saberi, and M. Austem. Statistical guarantees for link prediction using graph neural networks. arXiv preprint arXiv:2402.02692, 2024.
[9] R. Cummings, D. Desfontaines, D. Evans, R. Geambasu, M. Jagielski, Y. Huang, P. Kairouz,
G. Kamath, S. Oh, O. Ohrimenko, al. Challenges towards the next frontier in privacy. arXiv preprint arXiv:2304.06992, 2023.
[10] E. Dai, T. Zhao, H. Zhu, J. Xu, Z. Guo, H. Liu, J. Tang, and Wang. A comprehensive survey trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. arXiv preprint 2rXiv:2204.08577 2022.
[11] V. Duddu, A. Boutet, and V. Shejwalkar. Quantifying privacy leakage in graph embedding. In MobiQuitous 2020-17th EAI International Conference on Mobile and Ubiquitous Systems: Computing, Nenworking and Services, pages 76-85, 2020.
[12] C. Dwork, A. Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theorelical Computer Science, 933-4)211-407 2014.
[13] M. Fey and J. E. Lenssen. Fast graph representation learning with PoTcc Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[14] W. Hamilton, Z. Ying, and Leskovec. Inductive representation learning on large graphs Advances in neural information processing systems, 30, 2017.
[15] W. L. Hamilton, R. Ying, and J. Leskovec. Representation learning on graphs: Methods and applications. arXiv preprini 170900700005584 2017.
[16] K. He, X. Zhang, S. Ren, and J. Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In 2015 IEÉE International Conference on Computer Vision (ICCV), pages 1026-17 1034, 2015.
[17] X. He, J. Jia, M. Backes, N. Z. Gong, and Y. Zhang. Stealing links from graph neural networks. In 30th USENIX Security Symposium (USENIX Security 21), pages 2669-2688 2021.
[18) D. Jin, R. Wang, M. Ge, D. He, X. Li, Lin, and W. Zhang. Raw-gnn: Random walk aggregation based graph neural network. arXiv preprint 22..v 2022.
11

---

[19] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhoddiikoa,, and A. Smith. What can we learn privately? SIAM Journal on Computing. 40(3):793-826, 2011.
[20] T. N. Kipf and M. Welling. Semi-super classification with graph convolutional networks. arXiv preprint Xrviv: I 609.02907, 2016.
[21] E. L. Lehmann, J. P. Romano, and G. Casella. Testing statistical hypotheses, volume 3. Springer,
1986.
[22] S. Luan, C. Hua, M. Xu, Q. Lu, Zhu, X.-W. Chang, J. Fu, J. Leskovec, and D. Precup. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[23] L. Meng, Y. Bai, Y. Chen, Y. Hu, W. Xu, and H. Weng. Devil in disguise: Breaching graph neural networks privacy through infiltration. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 1153-1167, 2023.
[24] Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF), pages 263-275. IEEE, 2017.
[25] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:
2018.
[26] K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75- 84, 2007.
[27] K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint 1905. 2019.
[28] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Köpf, E. Z. Yang, Z. Veiito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, pages 8024-8035, 2019.
[29] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.00 05207, 2020.
[30] S. Sajadmanesh, A. S. Shamsabadi, A. Bellet, and D. Gatica-Perez. Gap: Differentially private graph neural networks with aggregation perturbation. In USENIX Security 2023-32nd USENIX Security Symposium, 2023.
[31] F. Tramer, A. Terzis, T. Steinke, S. Song, M. Jagielski, and N. Carlini. Debugging differential privacy: A case study for privacy auditing, 2022.
[32] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[33] B. Wang, J. Guo, A. Li, Y. Chen, and H. Li. Privacy-pressrvee
representation learning on graphs: A mutual information perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1667-1676 2021.
[34] F. Wu, Y. Long, C. Zhang, and B. Li. Linkteller: Recovering private edges from graph neural networks via influence analysis. In 2022 IEEE Symposium on Security and Privacy (SP), pages 2005-2024. IEEE, 2022.
[35] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6877 PMLR, 2019.
[36] R. Wu, M. Zhang, L. Lyu, X. Xu, X. Hao, X. Fu, T. Liu, T. Zhang, and W. Wang. Privacy- preserving design of graph neural networks with applications to vertical federated learning. 2023.
arXiv preprint arXiv:2310.200:
[37] X. Wu, Z. Chen, W. Wang, and A. Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. arXiv preprint arXiv:2212.1070) 2022.
[38] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint
008000 2018
[39] K. Xu, M. Zhang, S. Jegelka, and K. Kawaguchi. Optimization of graph neural networks: Implicit acceleration by skip connections and more depth. In International Conference on Machine Learning, pages 11592-11602. PMLR, 2021.
12

---

[40] Y.-Y. Yang, C. Rashtchian, H. Zhang, R. R. Salakhutdinov, and K. Chaudhuri. A closer look at accuracy vs. robustmess. Advances in neural information processing systems, 33:8588-888 8601,, 2020.
[41] Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference machine learning, pages 40-48. PMLR, 2016.
[42] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint 1rXiv 00090, 2019.
[43] H. Zhang, B. Wu, Wang, X. Yang, M. Xue, Pan, and X. Yuan. Demystifying uneven vulnerability of link stealing attacks against graph neural networks. In International Conference on Machine Learning, pages 41 737-44155. PMIR, 2023.
[44] Z. Zhang, Q. Liu, Z. Huang. H. Wang, C.-K. Lee, and E. Chen. Model inversion attacks against graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 2022.
[45] Z. Zhang, Q. Liu, Z. Huang, H. Wang, C. Lu, C. Liu, and E. Chen. Graphmi: Extracting private graph data from graph neural networks. arXiv preprint arXiv:2106.02888 0220000 2021.
[46] 7. Zhou, C. Zhou, X. Li, J. Yao, Q. Yao, and B. Han. On strengthening and defending graph reconstruction attack with markov chain approximation. arXiv preprint arXiv:2306.09) 2023.
13

---

Appendix
Table of Contents
A Broader impacts
14
B Additional backgrounds
15
B.1 VFL and the SERA adversary
15
Measures of homophily
Representative GNNs and their corresponding aggregations rules
C Proofs of Theorems
16
C.I Proof of theorem 4.1
16
C.2 Proof of theorem 5.1
20
C.3 Proof of theorem 6.1
25
D Further experiments
26
D.1 Synthetic experiments
26
D.2 A complete report of attack performance real- world datasets
28
D.3 A complete report of privacy-utility assessments Planetoid datasets
28
D.4 Spectrum study of GNN solutions obtained under the unconstrained scheme
33
D.5 Privacy-utility trade-off comparisons: NAG vs EdgeRR
33
E Discussions and Limitations
35
E.1 On the impact depth for NAG
35
E.2 Stronger adversary for dense graphs or deep encoders
36
E.3 Extension to more complicated victim GNN models
36
E,4 Quantifying the advantage of adversaries with more knowledge
36
A Broader impacts
The pervasive integration of graph representation learning (GRL) into various sectors, from social networks to bioinformatics, underscores the necessity of addressing the security and privacy risks inherent in these technologies. This paper contributes to the understanding of such risks by dissecting the structural vulnerabilities graph representations under siiiieesmillartt-baaaee baased edge reconstruc- tion attacks (SERA). Our work has significant ethical implications and societal consequences, aim to balance the need for advanced data analytics with the imperative safeguarding individual and community privacy.
Theoretically articulating the success and failure modes SERA, our research offers a framework for evaluating GRL models against potential privacy breaches. The insights gained can guide the development of more secure algorithms that resist inadvertent information disclosure. By highlighting the efficacy of SERA in various settings, this paper also underscores the potential for such attacks to serve as auditing tools for privacy-preservine preserving mechanisms, thereby fostering the creation more trustworthy GRL systems.
As GRL technologies continue evolve, our work calls attention to the importance of proactive privacy research in the field. It encourages the industry to adopt bewacc-bby-esiieee principles and serves as reminder to policymakers to consider the implications of GRL in legislation around data protection. Future societal consequences hinge our ability to reconcile the benefits of GRL with the privacy rights of individuals, necessitating ongoing research, transparent practices, and informed governance to navigate this complex landscape.
14

---

B Additional backgrounds
B.1 VFL and the SERA adversary
Party
Party B
embeddings gradients
node Feature
eacoder
GKN
decoder
loss
label
sampler
graph C
Figure 3: Illustration of typical vertically federated graph representation learning scenario, the figure is adapted from [36].
We describe the scenario of vertically federated graph representation learning mentioned in section 1 in more detail, with the system architecture illustrated in figure
VFL setup Under this scenario, we assume that party A (on the left side of figure 3 holds the graph as well as the node features, and party (on the right side of figure holds the node labels. Such kind of scenarios are encountered in applications like financial risk management [36]. Under VFL protocols, party A and party B iteratively exchange intermediate outputs to facilitate collaborative learning. The most representative method is split learning [36], where in each step, party A sends the node representations whose parameters stored at party A. We call this operation the forward transmission step and highlighted in figure as the red arrow.
possibly sampled subgraph encoded using a graph neural network
SERA adversary We assume that party B is honest-but-curious in the sense that party B strictly follows the VFL protocol but tries infer the graph structure belonged party A, both during training and during inference, as the forward step is required for both stages. The attack requires nothing more than the VFL protocol: In each step. the two parties agree on list of node indices that participates in this step (typically carried out using some cryptographically secure primitives), which constitutes the potential victim nodes Vvietim- Upon receiving the node embeddings from party A, party B is then free to conduct SERA that targets the topological structure of Gvectim- Furthermore, party B can even target a larger subgraph via storing multiple batches of embeddings and conduct attacks based the unioned collections. Note that the adversary does not have access to GNN model parameters as they are kept locally at party A, which manifests the practicality of the proposed SERA adversary.
B.2 Measures of homophily
The homophily metric way to describe the relationship between node properties and graph structure. Depending on the intrinsic nature of the property, we use two types of homophily measures: The label homophily (or edge homophily)
Hiaeel ( (G, ()YY==
Σ
(10)
(a.e)EE
which measures the averaged agreement of adjacent nodes' labels and the feature homophily (or generalized homophily [18, 221)
H feature (G,X)
Σ
cos (X.:
(11)
E
(a,e)EE
which replaces the agreement measure in the definition of label homophily with the cosine similarity between adjacent nodes' features. Another important metric we use in the experiments is the AUROC of guessing edge presence using feature similarities, i.e., AFS(T)
(oos(ra.. I.) 2 r). Note that
Hrteaure might be related to but not always correlate well with the AUROC of AFS as Hizature ignores the feature similarity of non-edges.
The feature homophily metric is sometimes related to, but not always correlated with the
15

---

B.3 Representative GNNs and their corresponding aggregations rules
Here briefly review GNN architectures that are involved in theorem 6.1 in the pessage-passiiggg form as in (8):
Mean pooling [14] This is the standard form of message passing GNN. With the un-normalized and un un-perturbed version analyzed in section 4 and 5:
Wi 11-
H ReLU
1
+C
#SAGE-meanpond
de +1
wEN(r)Ufe)
Summation pooling [38] This is simplified version of the GIN model which is also analyzed in [36]:
WiH
H ReLU
+
(GIN)
H (1-11
(EN()JU())
Max pooling [14] In its un-normalized and un un-perturbed version, this corresponds to the mostly used SAGE model:
WH (1-1) H
H ReLU
max (EN())U(u)
+e
(SAGE-maxpool)
2
GCN pooling [20] The GCN pooling takes the form
WiH (1-1)
1 ReLU
Σ
(GCN)
Vd +
uEN())ufo) dd, +
H
1-11)
Attentive pooling [32] This is also know the GAT model. To simplify notations, let H (/ ( then the GAT model is recursively defined as
H ReLU
Σ
Wi +
WEN(())((+)
(GAT)
(LeakyReLU (3mc, WiA (Bas. W 1)) exp
Ouv
Σ [oEN())u(o)) exp LeeayRRLLU (Bes W. + (Bess: Wi Wi (/!!-11))
where Bae, Bas E IRd are learnable vector parameters.
C Proofs of Theorems
C.1 Proof of theorem 4.1
In the proof, for notational simplicity, we abuse notation by treating A A and D +
(i.e., self-edge is included in the edge graph). We then define A(4) A I. times
A and pij (L)
((--A)))ss-
Proof of the theorem. For any pair of two nodes and j. next recall the formula of cosine similarity, cos 0 (((), H(()),
(H!"), H1l0)
cos (HH(( -1(0)
(12)
(H H1 (11 (1)))
16

---

which will be used recurrently in the following main proof.
According to the generation mechanism of node features (i.e., isotropic Gaussian assumption), have that
1 11 11 3V d d 1|,111==
log n and 1 (X s 3v d
log n
(13)
for all j.j with probability at least 1 - 1/n2.
Case I: without considering the learnable weight matrix W. For the numerator in cos 0 ( (1) H (! when i and 2 are truly connected, we have
( (1) H
I EODOBINNI
+
Σ
(X,, Xy)
(1)
Pin
(D) ( || 12 Σ
Pin
(L)
(X,, Xx)
IV
||x;, 112
Pis Pias (x)
W Wh (
(C2 log - 3/
log
(use the fact that
PinpPis 1)
(L) (2)
d
2 1
(14)
3 (C2 (o)
when d > 9(2 log n) 47,42 logn. n. On the other hand, when i1 and ig are not connected, by Lemma C.2, we know that, with high probability, there are at most (C2 log
-n(n 1)/2 pairs of i1, d2 such that Ej A3 A (()) 2 1 which is equivalent Poy Piaj > O. For the rest of pairs, we have
(L) "
(H (L) !1)) = Σ
Pijj Pigf X,))
(L) (L)
jtt
log
< 3/ d
< 3
(C2logn)3L+1
(15)
when d > 9C2 log n) 6L+22 logg n.
For the denominator (I) [T (11)) |1 1/, we give the upper and lower bounds of || (1 We can compute
(1) (H(",H(1))
= Σ Po Pis 12, +
Σ
Pij Pij Pis Xz)
(1) (1)
341
logn
< 1 1+31
1
< 1 1+
(16)
3
(C2 log T
where we use the fact that Pi Pij
(1. (L)
< Conversely, we have
11 (1 = Σ
(L)
|X,1 + Σns
Paj (X,,x,
Púj Pij
343
logn
I A
- 3/
C2 logn)
d
(17)
CC lo (C, loogg))2+
17

---

where we use the fact that Σ, Pij Pig 2 1/(C2 logn)* when |,(40) S (C2 log
(4) (2), (2) (2)
To sum up, cos ( 11 (1)
()))) is at least
(1))
2
(C2 lognn) (1
(18)
3
3(C2 log n) n)22+1 (C2 log l)g
when node i and 22 connected. On the other hand, cos 0(H ( is at most
(L)
3 (C2 1ogg))3++1 /(
(19)
(C2 log 3 (C2 (C2logn)24+4 2 (C2
for all pairs (except most (C2 logn) n(n 1)/2 pairs) of disconnected nodes i and in. By choosing the cutoff negative is zero and the false positive is (C, (Cglogn) n)
(Ca log with probability least 1 2/n have the false
Case 2: with considering the learnable weight matrix W. Additionally, if the learnable weight W is taken into account, we can derive the following results. We define K1 and K2 to be the largest and smallest positive constants such that
K1 xx, & (WX, S xx(
holds. It is easy to see that K2/K1 = (x(W))² Then the parallel version of (14) becomes
(H (1.) ( 2 A4
2
(20)
(C2 log n)
The parallel version of (15) becomes
(H! H(l)) I 3k2
log n
(21)
d
The parallel version of (16) becomes
log n
(H(4), H(!)) I n2(1 +3/
(22)
d
The parallel version of (17) becomes
( m!! 2 Ki
3/
log n
(23)
(C2 l)g
d
Combining above results, we have that cos ( (1) 2
K1 3 (C's log
2
1
<2(1 + 3 logn
K1
=: cut (L)
(24)
2x² (C2 log n)2t
when i,, in are connected and > log" n and
3k2
log
cos 0 0(H (1) ( x
d
K1 (C2 log n2
3/
log
Ing
4x2
d
(ut)(L)
(25)
K1
CCss Jugnj
when i1, i2 are not connected and >> (C2 log n)
62+2 log n.
Therefore as long as d > (C² log n) 05.+2 log n and
log d
8(C2 log 3)33.
(26)
K2
holds, we can choose any cutoff between cut, (L) and cutz(L) so that false negative rate is zero and false positive rate is no larger than (C2 log n2 /n. This completes the proof regarding FPR and FNR. For the implications AUROC, the result follows immediately by noting the discoveries are montone in т.
18

---

Supporting Lemma of Theorem 4.1 The following Lemmas are used for controlling the number of pairs of nodes (u, v\'s which satisfy Ej A A
An 21.
Lemma C.1. Let p) denote the binomial distribution with probability p and size n.
1. Suppose X dominates B(n, p). For any a > 0, we have
P(X < up a) S expl /2mp))
(27)
2. Suppose X is dominated by B(n,p) p). For any a 0, we have
a²
P(X > up + a) S min(exp(-a' /2mp + a² (mp))))p))))))))))))))) expl 2mp + 2a/3 }}
(28)
Proof of Lemma C.1 is standard and we omit it here. The consequences of this Lemma is that C.
2 log $ Ej Aij I 2
3C1 log with high probability at least 1/2² for all node i E [n].
Lemma C.2. Given graph with edge probability p (p S Ci
logn then
(C2 (C2logn
P Σ
1 21)
(29)
n -
where i1, i2 two nodes uniformly randomly sampled from the graph.
Proof of Lemma C.2. By recalling the definition A that A! equals one only when node and node j can be connected within path of length L. Therefore, with probability at least 1 1/n2, holds [N < (3C) (3C 1o yr, where Ao {i A/ 1}
2
Note that, given fixed A,, is greater than 0 only if i1 E NN, By the symmetry,
know that this happens with probability most -1 sampled. Therefore, by union bound, we have
when é i2 are uniformly randomly
m(n-1)
W 1(179)) -1)
P
(D) 12f
1)
<
n(n 1)
(1.5C) log 1)2
(30)
n
which concludes the proof.
The implication of this lemma is that there are at most (L) (L)
(C2 log 2) pairs of (u, such that
Σ, (L) A!L > 1.
Extension to different similarities For example, we can use correlation similarity, i.e..
The cosine similarity can be replaced by other similarity metrics.
(H(") H!!)) (L) H H(() (1)))
(H 11) =-:=
VIH - H. H. -H(") (H))) -F H.!") H(()))
where (1) is d-dimensional vector whose elements are equal the mean of ((()) By treating X, X, X, (j E [n)). where X, is d-dimensional vector whose elements equal to the mean of X,, (13) changes to
1 log n and 1 (X,, X
log n
- 1x,1 11 < 4v
< 4
d
Therefore, the above proof still holds by adjusting the constant accordingly.
19

---

C.2
Proof of theorem 5.1
To prove the desired result, we first need the following lemmas. In the rest of proof, we abuse the notation by treating p as Po and as go-
By applying the Hoeffding's 's inequality, we can obtain the following two lemmas.
Lemma C.3. It holds
Ejihh in the some group Asj- K pol - 3 log n c1 for all i with probability
at least 1111/a 1/nn..
Lemma C.4. Suppose is in group k, it holds Ejas in the group 1 k) Ais n gol S min 1 n
K
qo, 3 Blogn] ] =: e2 for all with probability at least 1 - 1/n².
Combining Lemma C.3 and Lemma C.4, we have the following lemma.
Lemma C.5. It holds ES ( Po (n- x q0)l S c1 + (K 1)ez with probability at least 1 - 2/n2.
In summary, with high probability confidence, Lemma C.5 gives the characterization of degree (i.e. number of neighbours) of every node i.
(L)
We then make step forward and characterize the normalized degree Pij for L 2 2 in the following lemmas.
Lemma C.6. With probability at least 1 - 11/n?, it holds that
[ (2 + (n n/K)gopo)l s llgg n-+ 2 K for J. from the same group and [A]]) - Podo + (aa-n/K)a k) S min ( 1 Pogo+
(n n/ K ()6)) 3(K K 1) log n for i from different groups.
(L) and a an) such that |A a
a (1)) S c
Lemma C.7. For L 2 2, suppose there exist constants aj
when i,j are in the same group and |A! d2 holds that
(1) S E2
(L) when i,j are not in the same group.
14!(+1) 01
(1+1)
(L)
S 6
i,j in the same group
|A!
02
/
< c2
(L)
i,j not in the same group,
(31)
with
a (2+1) (L)
K Po + 02 (n n (//K)ug K))o),
(L)
(1+1) = di
(L)
(L)
(L) (n -2n/ K)90
02
K q0 a2
Po + 02
K
G (L+)) = G K
(L)
(L)
+Gq + 62 (n- n/K]go (K -1)caa2 (L) + +(K- -1)c2(2 (L)
(L)
Pu a
(l+1) (L)
(L) c2c (t)
(L) Pu ca, + tach + + (0 -2n/ K)g0
2 1 K
qu + c201
+ 2 k
+ (K 2)22a (1) (K 2)e2t (L)
Proof of Lemma C.6 is special case of that of Lemma C.7. In the following, we prove Lemma C.7.
Proof of Lemma C.7. By the definition, we know A! (1++1) = Ex (L) Ayi-
When j are from the same class (w.l.o.g, we denote it as class 1), then holds
144--) (a) n1
K P + 02 (n n\/K)o)1
(L)
= 1 A Ay - (a1
(L) n
K R + d2
(L)
(n - K))K))
< Σ
13 Ayj - di K
(L)
Pol +
Σ
1 Ayj - 02
(L) (n - n/ K K)gol
5r in class
not in class 1
1 K
(L) N
Po + c1
(1)
+ t
(1)
+ 62
(L)
(n
n R/KK go + (K-
1)c2a (1) + (K 1)e2ch (20 (32)
20

---

Therefore, we can let a
(L) (1+1) (a} Po + d2 (n -n/K)uo and 6j (4+1) : e RPo t2 + ( (() + (n (n nnoKn/KKuuu + (K 1)2222 (L)
(1)
+ (K - 1)
When i, are not from the same class (w.l.o.g. assume is from class 1 and j is from class 2). then it holds
14 (1++1) (L) n
(a)
90 + d2
(L) n
K po + 02 (n - 22n/ 13 K)4o)l
(L)
K
Σ 1 Ago (a]
n
qu +
a2
(L)
Po + 02 (n 2n/ g)
(L)
K
K
Σ
1 Ays
ai
( n
Σ
1 Ayj 02
K KPoll
n
Pol
k
8' in class
5' class 2
+|
Σ
1 Aps - 02
(L)
(n - 2n/ K) K)
1' not in class
&
C K 90 c2a (L)
(L) n1
c2c (1)
(L) n
(1) (L)
+ C2 K Po + c102 c162
+62 (n 2n/ K K) + (K - 2)2202 + (K 22)222 (L)
(b)
(L)
(33)
Therefore, we can let (1+1)
02 = af K + 02
(1) n pa (1) (n 2n/nn yo and 62 (1+1) = (L) m
K 90
E2a] (1) tezel (1) (1) a
+c2 K po +e1e2 tE2 12n22m115000 K 900 + (K 2)22a2 +(K ((K-2)/ ((K-2)e22 E26
(f.)
(1) (1)
(1))
By above induction, it can be seen that, for any fixed L, /a Op( logg) (p( 62 /a(
(1) (1)
Opl logn ). It also holds 02 (I.) /ai (T.)
Op( (""g") when true edge probability satisfies Op log
and (L) ja2 Opl log
when go >> lng
Recall the definition that PG = ((D-1A)4 therefore pig (4) x A for any fixed i. In other words, for fixed L 2 2, we have
Pij = Pij + +pl
(L) (L)
log n n2
(L)
+Op
k log n n²
), i,j in the same group,
K
a
+ (n
K
02
())
=pp
(1)
Pij
(L) (1) + +Opl
kloogg n n²
42
(L)
+Op
k log nt n
i, not in the same group.
K di
(L)
(n
K
02
(1)
= =:2
(34)
Here, very high level, can treat Poj the population version of ((D-)A)))s When i,j in (L) (L)
(L)
(T) (D) With above preparations, we ready to
the same group, then P.j. = Pi Otherwise, Ptj p2 prove the theorem as follows.
Proof of the theorem. We need to consider the case L >>> 2 and L separately.
21

---

Case 1: 1 2-2 2. We define x== Eie group X, and ,((4) == a24 /af For the numerator in
cos 0 (1, (1) H!!)), ), when in and ig are in the same group (w.l.o.g, suppose it is group 1); we have
(H L) ( - Σ P 12 + Σ
Piss Xy)
(1) (2)
341
Σ
P ||, + Σ
Pii Pinj (X, Xy) error
(L) (L)
(35)
if1'
= pl Pi (x,, X1) + (L) (1) (X1, X1) + Σ
(
(1) (1)
(8x, Xx)
P2
P2 P2
P2
1
1#1
Σ
(L) (L) (Xx, Xxx) + error
P2 P2
k#
= Pi P1 K
(1) (L) n
+ (K -1)p2 P2 K
(1) (L) n2
+ +Op((K 1)pp
P2
(2) 12
K vd
(36)
+ (K- - ()
- 22)p P2 K
(1) (L) n
+ error,
Vd
where (36) uses the property of node feature generation mechanism that (N,, X2) = R (1+ VI/a)
for any le and (Xx, Xxx) = Opl Rvaa) for k + K. Here the error term in (36) is error (1) (1)
Σj= (Z) (T)
PPij Piaj Pajpiss |13,| +I Ejg (Paj Pies" P. Xy), which can be con-
(1) (2)
trolled as follows.
lerror| =
Σ
(P Peaj
(L)
- R. ,|, 2 + Σe
- - 10 PX Xyyl Paj
j=l
343
(Pizi Pizi
(1)
- Piyi Piai
(1)
|| +
Σ (1)
- (X, X,,|
34.1
k log n n
klog n n
logn d
C
k log n
logn
log n
= Opl(
(37)
n²
n
d
where (37) utilizes the fact that Σ, Pu = for any and (34) by adjusting the constant.
When in, i2 are not in the same group (w.l.o.g, suppose in in group 1 and i2 in group 2), we have
a
(H , H(l)
(L)
X,, 1 + Σ
Pippisj X,)
PajPiss
Paj X,,| 12 + Σ
Piij Pij (X,, X,)) + error
=
Pi P2 ((x1, + (X2, X2)) + (p1 P1 + P2 XX X2)
(L)
(1) (L) (L) (L)
+(0l P2
(L) (L) (L) (L)
+ +P2 p2
Σ (8 + X2, Xx) + Σ 12 P2 (XE, X1)
(L) (L)
k11.2
kA12
+
P2 P2 (Xx, Xx) error
1
(L)
11,
2p P2 K
(L) (L)
(K- 2)p2 P2 K
(L) (L)
(L) (L) n1 T
+0p((p) Pi
(1)
(L)_(L) (1)
+ Kpi P2
(1) (L)
K2
P2
P2
K d
+ error.
(38)
22

---

To sum up, if 81, ig are in the same group, cos ((H ) satisfies
cos 011 (
( (!!
V (H!!) (. (H ( !
pi Pi Pi
(L) n + (K 1)p2 (2) (L) (1)
P2
Pi Pi R
(L) (L) n + (K- 1)p2 (1) (L)
P2 R C pi P2 + K2 (2)
(L) (1)
Kvd + +pp
K Klogn L
V
log
= 1 (1)
(39)
cut) (L)
as long as d >> k22 log" n/b².
If i is are not in the same group, cos 0 (H (1) ! satisfies
011 (L) (1!
(1 (1!
V ( !! (H (1) !
2p1 P2 K
(L) (D) a + (K 2)p² (L) (L) n + C(KP)
P2 K
(L) (L)
p2 + K2P2 (L)2
Kvd + Op(
K
log
1 +
log
Pi K
(L) L n
+ (K 1) 1)p P2 K
(L) (L)
(L) + (K- - (1)2
1+ (K - 1)r(2/2 (1,
(40)
(L)
Remark. As L + 00, p(L) will converge to 1. Therefore, cutz(L) will eventually equal 1 = cuty (L).
Case 2: L ==1 1. For notational convenience, we define k Ene group b b X, where 6(0 's are i.i.d. Bernoulli random variables with success probability po and x(0 = Eie group & 6,2,, where (()) 's are i.i.d. Bernoulli random variables with success probability go-
Then it is straightforward to calculate that, if in, i2 are in the same group 1, it holds
(H H =d
1
((X(1)
(XL
Σ
(1) [x
222
x11
D D.
Righ
(1a))
+
k22
k22
k2 2.2)
k
ke k
1
nvllon
nylog
Po + (K
2
1) K
O (po
/Pogo
Di, Dig
K Kdd
Vd
n Vlg
+ +Ko
(41)
Vd
23

---

Similarly, if i1, dp are not in the same group (w.l.o.g, they are in group and 2 respectively). it holds
( ( (H))
(H, H =d
(
( 1,1 [1
+
(
((ta))
+ (X (1 x (1) 2,2 x
D2 D2 12
Σ (x
(())
x + x
R22
1,2
1,2
(12)
(6) (12)) W2
k22
k2
k.2
1
(2 n
Poqu + +KK - 2) n
2/2
+ (p0
nVVog
ny log n Kvd
+ Pogu
ny log
D,, D22
K
vd
ny MVVlog nh
+o
(42)
Vd
Moreover, if = i2, it holds
n H
1
((77.)) F6ii)
+ Σ (T x
Dr,
D,
lep
(11)
(01)
22 k22
k,k'
D,, D2
1
1/
n2
k
Po + (K--)
- 1)
K
90
+ Op
n logo n KVd
+ /po90
n log
vd
avVlog
+ Kgg 90
(43)
Vd
To sum up, arrive
cos (HH (1) H()))
i1 in
(H (1) H (1))
V (H H())
(HL)) H
is
Fd + (K - 1) 2 40
EPo + (K - 1 + +pp(po
nylogn
Kvd + /P000
Vogg
+ Kgn %0
avlog
Vd
vd
E + (K - 1) 2 +1p(1)
(44)
Po + (K 1) go
cut cut)(1)
for i1, 12 from the same group, when >> logn. Similarly, we have cos (11 ()) !
(H (1)
Vun _1 (1 (1) ,1!
Frl (K 1) k vb Op
aw/og
KVá /Po00
Bylog Ja
+ go
ay/log
/d
p + (K 1) 90
Po90 + (K 2) 9
=
Po + (K - 1) R 90
(1)
(45)
c1)g(1)
for in, 12 from different groups, when d > logn/rö
Therefore, for any fixed 2 and any fixed cutoff 2 cut, (T.), then SERA will predict at least
pK K ( - 1)/2 + qK(K- 1)/2 n K truly connected pairs as dis-connected. In other words,
24

---

we have the false negative rate is at least p/
+ +/2.. If the cutoff r is between cutz(L) and cut (L), then SERA will predict least (1 p) ă ( 1-)-1,,, 12 truly dis-connected pairs as connected and K K truly connected pairs as dis-connected. That is, false positive rate is least (1 (1-p) (2k) and false negative rate
predict at least ( 12 2
least (1 - g)/2. If the cutoff T is less than cutz(T.), then SERA will predict at least (1 p) K R [R 1)/2 + (1 ②) K 1) 1)/2 / R
truly connected pairs as dis-connected. That is, false positive rate is at least (1 (2k) (1-9)
This completes the proof.
C.3 Proof of theorem 6.1
As mentioned in section NAG actually protects against a much stronger class of adversaries. Specifically, let H (H JuSISL denote all the intermediate representations produced by the underlying GNN with weights W = [Wihe The following theorem is stronger version of theorem 6.1:
Theorem C.8. Assume the adversary A has access to H and W, and outputs an estimate of graph adjacencies Å = AHH, W). Then for any graph G and any such adversary A, we have the lower bound:
[P (PAue-1|Au 1|Auu 0) + (Āwv OlAue - -1)] 2 21- 1-exp exp ( (C
min NEV.EV
1xepp
(46)
Here the constant C depends the mechanism of the GNN. In particular, for some standard GNN architectures we have: CGCN = CMEAN-SAGE = CGIN = and CGAT = CMAX-SAGE
The theorem is a consequence of the following lemma:
Lemma C.9. Fix arbitrary node pair (u, v). Let Hi and Ho be the collection of node represen- tations generated under Auv 1 and Aue = 0, respectively. It follows that the Kullback-Leibler divergence between H1 and Hg bounded:
DKL (Hz Ho) Eie(o [WiP
(47)
Here the constant = for (SAGE-mcanpool) (GIN) and (GCN); and = f.r (SAGE-maxpool) and (GAT).
Proof of lemma C.9. The proof is essentially a proof of Rényi differential privacy similar to that in [36]. First we single I-th layer of GNN defined in (8). We rewrite (8) as:
W 1)
H Act AGG
a (() +e == Act (H! (1 +()
(48)
H
11
Let the corresponding representation matrix be H(") for Aue and H!!) for Aue for any 1 E [T.] Further denote H7 [A!!) Joev the intermediate representation defined as in (48) with
Aue = a, a E 13. Then by standard results on Rényi divergence [24], we have
7
DKL (H'
Hb)
(49)
202
For some input H It follows that given all the other edges, the only terms that contributes to
7 7 are [
H
and i
(1) 2 Next give the derivation of various
GNN architectures:
25

---

The case of (SAGE-meanpool) We let de to be the degree of v assuming Aue 1. Further let
90
We have:
4,0
2
dy
+
Je
Q-11)
du
1
(1-1) meN(r))(r)
E
Du
(50)
11
(1-1)
13
+ 1
Σ
0 08-
(51)
2
du
MEN(o)(eo)
[Willop +
1
Σ
(52)
2
wEN(vllEo)
|Willop
(53)
Analogously we have [.
(1 0.0
- [Will and thus DRL.
(
H!"
|
The result
follows from adaptive composition as in [24, Proposition 1J.
The case (GIN) This follows by combining the preceding argument with [36, Proposition 1J.
The case of (GCN) This follows by combining the preceding argument with [36, Proposition 2].
The of (SAGE-maxpool) The result follows from the following fact that mmxx (e In max uaN 9u attains its maximum when I. -ua Vu E NV since all the gu8 are unit vectors.
Proof of theorem 6.1. We view the reconstruction problem regarding Aue as a binary hypothesis testing problem
Ho Aue = V.S.
H1 : Auv = 1.
(54)
Then according to hypothesis testing theory [21], we have
IP (Aw. 1/Auo = =) + P. Amn = AlAuu = 1)] 2
inf Á
drv (H1,
(55)
where we use drv (H) denote the total variation distance of distributions induced by H and
Ho respectively. By the Heetagnolle-Huber bound [4, Theorem 1J, we have
div (H1, Ho) S /I exp DDDL (H₃ Ho)) The result then follows by combining (55), (56) and lemma C.9.
(56)
D Further experiments
D.1 Synthetic experiments
Grdös-Réény experiments with random GNN weights The experimental setup in this section is basically the same as that section 7.1, except that the model weights are generated by the following process: For L-layer Linear GNN, we generate the weight matrix as:
W = W1 x WL.
(57)
Here each Wi, < S 10 is random matrix generated using the initialization method proposed in [16]. The evaluations shown in figure 5.
The results exhibit a similar pattern to figure where weight matrix set to identity. However, the attacking performance differs between the two scenarios: When the matrix W is poorly conditioned (a consequence of the construction (57)), the attacking performance degrades especially when the feature dimension d is not sufficiently large.
26

---

(a) Measured AUROC metric, darker color implies higher attacking perfor-
mance
60
(b) Measured ERR metric, lighter color implies higher attacking perfor- mance
Figure 4: Attacking efficacy of SERA sparse Brdōs-Rényí graphs, with each grid's value indicating SERA's performance measured in either AUROC (first row) or ERR (second row) metric.
00
-04
(a) Measured AUROC metric, darker color implies higher attacking perfor- mance
60
403
(b) Measured ERR metric, lighter color implies higher attacking perfor- mance
Figure 5: Attacking efficacy of SERA sparse Erdös Erdos-Rényi Rényi graphs. with each grid's value indicating SERA's performance measured in either AUROC (first row) or ERR (second row) metric.
27

---

100, 7 1, 2048, 0.05
100, L
1, 2045, 0.05
1.0
= 0.1
0.3
0.6
P = 0.5
AUROC
ERR
p
0.8
P
0.2
0.7
0.5
0.7
15
15
13 15
19
K
K
Figure Performance of SERA on SBM with varying K and p. All plots are based on independent trials with shades indicating one standard deviation.
Table 2: Summary of dataset characteristics
Squirrel
Chameleon
Actor
Cora
Citeseer
Pubmed
Products
Reddit
# nodes
5201
2277
7600
2708
3327
19717
1569960
232965
edges
36101
217073
30019
10556
9104
88648
264339468
114615892
# features
2089
2325
932
1433
3703
500
200
602
# classes 5
7
6
107
41
Impact of SBM structure To investigate the impact of SBM structure on the performance of SERA, fix the GNN architecture at L, 1 and evaluate a graph with 100 nodes and node feature dimension d = 2048. Note that we choose a relatively large node feature dimension to ensure that the assumption listed in theorem 5.1 is approximately met. We vary the SBM within- within-group group probability according to E {0.1, 0.3, 0.5, 0.7} and the number of groups according to < K < 20. The results, plotted in figure 6, suggest that in general, the attacking performance positively correlated with the number of groups K since more groups yield stronger sparsity according to the SBM generation law. This phenomenon also in accordance with theorem 5.1.
D.2 complete report attack performance on real-world datasets
Dataset characteristics
We report a brief summary of datasets used in table 2.
128 with number of GNN layers adjusted to L E 52, We use Adam optimizer with learning rate 0.001 and train for 1000 epochs on the relatively small datasets, and train for epochs on and Reddit datasets, using stochastic training strategy that samples up 20 neighbors per node in each layer.
Training configurations Across all experiments we use hidden dimension
Results We present full list of results in table 3. A comprehensive tabulation of outcomes is furnished in Table 3. Consistent with the findings explicated in section 7, SERA demonstrates proficient reconstruction capabilities irrespective of graph properties such as homophily. Additionally, the reconstruction potency resilient across a spectrum of GNN architectures. These results imply that prevalent GNN architectures are likely to engender models that are vulnerable exploitation by SERA adversaries.
D.3
A complete report of privacy-utilit assessments on Planetoid datasets
D.3.1
Training configurations and attacking pipeline
Network design For node with label ye, the prediction is defined as
je arg max dec (enc (G, W) [v]) [c], cE
(58)
where we use [] to denote the operation of vector index. Here the encoder enc designed via stacking L noisy GNN layers (in the sense of NAG) with aggregation mechanism AGG
28

---

Table Performances of SERA on eight datasets measured by AUROC metric (%). For each setup, the results (in the form of tean are obtained via 5 random trials.
Squirrel
Chamelcon
Actor
Cora
Citesecr
Pubmed
Products
Reddit
Husel Mamue
0.22
0.23
0.22
0.81
0.74
0.8
0.09
0.76
0.01
0.01
0.16
0.17
0.19
0.27
0.01
0.12
46.2
55.2
44.7
80.3
87.4
87.6
52.0
95.9
Victim model
ABERA, non-trained
LIN(L 2)
72.810.0
76.1
73.1
93.110.4
92.510.
93.911.2
97.210.3
96.4
LIN(L. 5)
72.6=0.0
76.0+0.3
73.0=0.2
95.9+0.6
93.8+0.4
96.0+0.6
99.2+0.1
95.4=0.1
GCN(L 2)
87.3
87.940.4
87.1+0.6
99.8+0.1
99.940.0
99.7+0.0
99.6+0.0
97.3=0.1
GCN(L 5)
82.1+0.a
84.3+0.9
84.1
99.4+0.2
99.9+0.0
99.5+0.1
99.2+a.1
96.1+0.2
GAT(L = 2)
86.210.5
87.910.
86.710.e
99.810.1
99.9
99.7
79.817.7
88.5
GAT(L = =5]
82.0=0.9
84.320.4
82.9.0.7
99.5.0.1
99.940.0
99.440.0
91.3+5.9
93.7=1.7
GIN(L 2)
72.8+0.0
76.1+0.2
73.5
92.1
91.3+o.9
96.640.6
98.8+0.1
96.4=0.1
GIN(L 5)
72.2+0.0
75.9+0.4
74.4+0.0
93.0+o.3
89.9+0.7
94.240.5
97.6+0.1
89.2=a.6
SAGE(L 2)
72.6
75.510.1
74.1
87.610.3
87.010.
93.7
99.21..0
94.2
SAGE(I. 71.420.2
74.2+0.1
72.420.6
88.4
85.6+0.3
88.4+1.0
97.6+0.1
93.420.6
Victim model
ASERA,
trained
LIN(L 2)
74.6=0.0
75.0+0.a
59.940.7
94.6+0.1
93.7+0.1
89.0+0.1
91.6+0.2
94.7=0.1
LIN(L 5)
74.1+0.3
76.9+0.2
61.640.7
94.8+0.3
93.3+0.3
88 88.4+0.9
98.6+0.1
92.3=0.2
GCN(L 2)
79.410.4
82.3103
78.5
97.8
99.010.
89.2 89.210.3
94.510.1
95.1
GCN(L 5)
77.420.6
80.620.6
78.420.6
97.4g0.3
98.720.2
92.640.4
98.4g0.1
95.0=a.1
GAT(L = 2)
73.3
74.3+10
66.4+o.6
95.2+0.2
96.2+0.1
89.340.4
98.2+0.6
95.7=0.22
GAT(L = 5)
79.2#0.6
77.2+1.a
75.0+2.1
95.640.2
95.9+0.6
91.640.5
84.3+10.1
88.5+4.6
GIN(L
73.310.5
77.210.5
71.510.3
94.210.3
95.310.1
91.0101
99.01..1
95.5
GIN = 5)
73.2=0.3
77.0=0.6
74.1
99.8+0.1
94.1
92.7+1.5
97.7+0.1
92.420.3
SAGELL 71.620.1
71.7+1.
67.840.7
91.110.2
93.3+0.1
87.040.2
96.2+0.4
95.4=0.1
SAGELL 71.6.0.1
74.5+0.2
71.2+0.6
93.6+0.s
93.4+0.8
85.5+1.0
96.6+a.8
87.5=1.7
(MEAN, SUM, GCN, ATTENTION, MAX} as defined above. Note that the encoder maps input node features into node representations of dimension d, which might be larger than the number of classes C. The decoder dec is a linear map that maps node representations to predictions.
Attacking paradigm The attacking procedure of SERA will be based on the node representations produced by the GNN encoder enc under dimension of d. The attack is conducted over the node representations corresponding to the test subset, i.e., the victim subgraph is the subgraph induced by the nodes.
Training configurations Across all the experiments, we fix the GNN model to be of depth 2 and use full-batch training for 1000 steps(epochs) using the Adam optimizer with a learning rate of 0.001.
D.3.2 Unconstrained scheme
We plot the full experimental results under the unconstrained scheme for the Cora, Citeseer and Pubmed datasets in figure 8, figure and figure 10, respectively, where we evaluate the performance of SERA under both ERR and AUROC metrics. The result is consistent with those findings listed in section 7.3.
D.3.3 Constrained scheme
We plot the full experimental results under the constrained scheme for the Cora, Citeseer and Pubmed datasets in figure 11, figure 12 and figure 13, respectively, where we evaluate the performance of SERA under both ERR and AUROC metrics. The result is consistent with those findings listed in section 7.3.
Impact of different AGG mechanisms According to figure 11, 8, 12, 9, 13, 10, the previously discovered phenomenons are present for all the 5 aggregation types. Nevertheless, the degree to which these phenomena exhibit varies with the specific type of aggregation employed. Notably, the
29

---

-03
(a) Measured AUROC metric, darker color implics higher attacking perfor-
mance
64
(b) Measured ERR metric, lighter color implies higher attacking perfor- mance
Figure 7: Attacking efficacy of SERA over dense SBM graphs, with each grid's value indicating SERA's performance measured in either AUROC (first row) or ERR (second row) metric.
CS
kg
(a) GNN model performance over Cora dataset under 5 different aggregation types.
kgy
(b) Attacking performance SERA over Cora dataset (measured by ERR) under 5 different
aggregation types.
(c) Attacking performance of SERA over Cora dataset (measured by AUROC) under 5 different aggregation types.
Figure 8: Privacy-utio uutiliyy trade-off on Cora dataset using the unconstrained training scheme. The horizontal axes measure feature dimension in log, scale and the vertical axes stands for performance measures All plots are based on 5 independent trials with shades indicating one standard deviation.
30

---

03
1gg
(a) GNN model performance over Citescer dataset under 5 different aggregation types.
ATTEKTION Cheoee
SUM Chose
Chiwwe
Cheese
MEAK,
Hayd
(b) Attacking performance SERA over Citeseer datasct (measured by ERR) under different aggregation types.
034
kmp
(c) Attacking performance of SERA over Citeseer dataset (measured by AUROC) under 5 different aggregation types.
Figure 9: Privacy-utility trade-off on Citeseer dataset using the unconstrained training scheme. The horizontal axes measure feature dimension d in loga scale and the vertical axes stands for performance measures All plots are based on 5 independent trials with shades indicating one standard deviation.
654
26
(a) GNN model performance over Pubmed dataset under 5 different aggregation types.
ATTENTION, Phtrns
SUM Prteoeed
GEN Phhens
MXX Paleoed
MEAN, PN0rss
kgg
(b) Attacking performance SERA over Pubmed dataset (measured by ERR) under different aggregation types.
100002
(c) Attacking performance of SERA over Pubmed dataset (measured by AUROC) under 5 different aggregation types.
Figure 10: Privacy-utility trade-off on Pubmed dataset using the unconstrained training scheme. The horizontal axes measure feature dimension d in log, scale and the vertical axes stands for performance measures All plots are based on 5 independent trials with shades indicating one standard deviation.
31

---

65
04
64
(a) GNN model performance over Cora dataset under 5 different aggregation types.
ATTENTIONN Cun
SUM
MAX
MEAN
Hay
kgy
(b) Attacking performance SERA over Cora datasct (measured by ERR) under 5 different aggregation types.
(c) Attacking performance of SERA over Cora dataset (measured by AUROC) under 5 different aggregation types.
Figure 11: Privacy-utility trade-off on Cora dataset using the constrained training scheme. The horizontal axes measure feature dimension d in loga scale and the vertical axes stands for performance measures All plots are based on 5 independent trials with shades indicating one standard deviation.
32
65-
26.
(a) GNN model performance over Citeseer dataset under 5 different aggregation types.
ATTEbUTION DThener
SUM Chioswr
GCN, Chiwwer
MAX, C3tesee
MEAN Ctowwer
1
kgg
kgg
(b) Attacking performance SERA over Citeseer dataset (measured by ERR) under different aggregation types.
14100
(c) Attacking performance of SERA over Citeseer dataset (measured by AUROC) under 5 different aggregation types.
Figure 12: Privacy-utility trade-off on Citeseer dataset using the constrained training scheme. The horizontal axes measure feature dimension d in log, scale and the vertical axes stands for performance measures All plots are based on 5 independent trials with shades indicating one standard deviation.
32

---

ATTENTION Potire
SUM Pilnee
CCN Putres
NAX Patered
MFAN, Potass
100
(a) GNN model performance over Pubmed dataset under different aggregation types.
A1TEN KON, Piieedd
SUM Pilleed
GCN, Niieed
NAL Pelezed
620
07
10
11 10
(b) Attacking performance of SERA over Pubmed dataset (measured by ERR) under different aggregation types.
ATTENTION Pitroedd
SUM Peiree!
GCN NNiees
NAX Palroed
HIT ANAN Prtrasd
(c) Attacking performance of SERA over Puhmed dataset (measured by AUROC) under 5 different aggregation types.
Figure 13: Privacy-utility trade-off Pubmed dataset using the constrained training scheme. The horizontal axes measure feature dimension in log, scale and the vertical axes stands for performance measures All plots are based on 5 independent trials with shades indicating one standard deviation.
behaviors of ATTENTION, MEAN, and GCN pooling display similarities attributable to their shared mechanism in (weighted) average aggregation. Conversely, the efficacy the SERA against Noisy Aggregation (NAG) when SUM and MAX pooling are utilized appears less susceptible to changes in d.
D.4 Spectrum study of GNN solutions obtained under the unconstrained scheme
closer look at GNN solutions obtained via NAG in the unconstrained scheme As SERA is just one form of attack mechanism under a weak adversary, protecting against SERA does not necessarily imply strict notions of privacy. Motivated by theorem 6.1, we conduct spectrum study regarding the GNN solutions obtained via NAG in the unconstrained scheme. Specifically, we plot the operator norm of the weight matrices corresponding to the GNN layers across all scenarios and report them in the last column in figure 14 in appendix D.4. The results exhibit a rapidly growing trend of weights' operator norms regarding the increase of both feature dimension d and noise level a. For GNN models trained using noisy aggregation under large ds, the corresponding bounds according to (8) become vacuous, i.e., practically zero. Additionally, these solutions may exhibit diminished robustness, as the corresponding Lipschitz constants are likely to be inadequately regulated [40]. To conclude, we have found successful empirical defenses against SERA without satisfying strict notions of privacy, suggesting that SERA has limitations as tool for auditing private GRL training procedures.
D.5 Privacy-utility trade-off comparisons: NAG EdgeRR
In this section we provide preliminary comparisons between NAG and EdgeRR regarding their privacy-utility trade-offs. particular, for a graph with n nodes, the EdgeRR with budget e implemented as graph-level transform that perturbs the adjacency matrix EdgeRR(A) g3*x
33

---

Cora
Cara
20
11V
(a) Spectrum study on the Cora dataset under different aggregation types.
14.4
14.4
3G.4
AT ATTEKTION, Chocrr
SUM Clooes
CCN Clucker
MAX Clioe
MEAN, Ciocsr
1913
1gg
(b) Spectrum study on the Citeseer dataset under different aggregation types.
ATTENTION, Puhired
SUM Poleent
GCM Thlinee
MAX, Palenal
MFAM Priveed
(c) Spectrum study on the Pubmed dataset under different aggregation types.
Figure 14: Spectrum study on the Planetoid datasets under the unconstrained training scheme. The horizontal axes measure feature dimension d in log, scale and the vertical axes measures the operator norm the projection weights of the GNN. All plots are based on 5 independent trials with shades indicating standard deviation.
34

---

Cors: Priceryttitty tradi-off comparionn
Gimzer: Priorgatiiey tradentf comparicn
Puhmed: Pricrrattiitt trddwalf comperienn
25
05
Figure 15: Comparison of privacy-utility trade-off between NAG and EdgeRR
with each of its entries defined as:
{ AAu {1 Au,
With probability Itfe
(d)e)R(A)u,.r
(59)
Otherwise
then follows from the theory of local differential privacy [19] that for any (u, v) the perturbed entry is e-LDP view of the underlying true adjacency. Combining the property of max-divergence along with the proof techique in section C.3 we have the following performance lower bound of any adversary A:
inf min A WEV.EV
[P (A.... 1|A = =0) (Awo 0|Auw - -1))21--vv----
V1 V1- (60)
While EdgeRR has very strong privacy protection guarantee, it is also criticized for low utility. We provide a comparison using a two-layer GCN as the backbone under the embedding dimension d = 128 on the Planetoid datasets. The results, which can be viewed at figure 15, suggest that when considering SERA as the basis for evaluating privacy, NAG achieves a Pareto-dominant privacy-utility trade-off curve relative to EdgeRR.
Software and hardware infrastructures. Our framework is built upon PyTorch [28] and PyTorch Geometric [13]. which are open-source software released under BSD-style 4 and MIT license, respectively. All datasets used throughout experiments are publicly available. All experiments are done on single NVIDIA A100 GPU (with 80GB memory).
E Discussions and Limitations
E.1 On the impact of depth L for NAG
As elucidated in theorem 6. the privacy assurances provided by NAG are inclined diminish as the depth parameter L increases, a phenomenon attributable to the compositional nature of (differential) privacy mechanisms [12, 24]. However, this same compositional principle enables NAG to disseminate all intermediate node representations H ,..., HL) while preserving the identical level of privacy would be the case if only (4) were released. Consequently, this framework permits the design of superior privacy-preserving GNN architectures by leveraging a blend H' (E(L) through inter-layer aggregation techniques, sometimes termed residual connections in GRL [39]. Probing the resilience SERA against such intricate GNN configurations poses considerable challenges and falls outside the purview of this paper. Nonetheless, preliminary evaluations have been executed to discern the ramifications of the depth parameter L on the privacy-utility compromises of NAG, absent residual connections, with privacy quantified via SERA. The inquiries, undertaken using the Planetoid datasets with a fixed noise magnitude of a = 0.05 and hidden dimensionality 128, are visually synthesized in Figure 16. Findings reveal that optimal defensive utility typically transpires at L = 1, while greater GNN depths, notably those with L >> 5, tend to undermine the model's utility. Moreover, the apex of attack performance generally materializes at relatively incipient
35

---

Cora: Prizryaaiity Indeati 1.5 U.S. 10
Ghewer Pooryyatitt tradesaf L
Puhmed Priacystilty traeedf 1-57/110
6.7
6.45
Figure 16: Privacy-utilltty trade-off on Planetoid regarding different model depths
layers, confirmation of our theoretical insights set forth in theorem 4.1. Finally, postulate that incorporating residual connections might proffer an enhanced Pareto frontier for the model. Exploration of this hypothesis is deferred to subsequent research endeavors.
E.2 Stronger adversary for dense graphs deep encoders
We have shown the limitations SERA over dense SBM graphs as well as deep GNN encoders. As analysis applies to the specific SERA adversary, it is thus of interest ask whether there exists stronger attacking paradigms that is provably effective against dense graphs or deep GNN encoders. On the flipside, it is also valuable to understand whether the phenomenon of oversmoothing may fundamentally affect the performance of any black-box adversary.
E.3
Extension to more complicated victim GNN models
The theoreical analysis presented in section 4 and section 5 is dedicated to graph neural networks employing mean aggregation without nonlinear activation functions. Prospects exist for augmenting theoretical framework to encompass alternative aggregation schemes, such as summation [38] and attention- based aggregation [32], conditional upon the satisfaction of specific prerequisites-nan namely, some lower bound of attention coefficients. A more challenging task lies in the extension of our analysis to graph neural networks (GNNs) that incorporate nonlinear activations between their layers. This inclusion significantly complicates the straightforward application of our non-asymptotic analysis in cohesive end-to-eun end-to-end manner. Acknowledging the complexity of this endeavor, we left a thorough investigation for future research initiatives.
E.4 Quantifying the advantage of adversaries with more knowledge
Despite its effectiveness, the knowledge available to SERA is rather limited. Although previous study [17] has shown empirical evidences that equipping the adversary with more capability may results in stronger attacking algorithms, theoretical explication of these enhancements has yet to articulated. In particular, it is of interest quantify the amplification of adversarial capacity afforded by scenarios which the adversary granted white-box access to the model weights or node features.
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All our contributions are concisely represented in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in section E
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
37

---

Justification: The assumptions are listed in the theory statements in the main text, and proofs are presented in section C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental details are presented in the main text and in section the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
38

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Codes for reproducing experiments included in the supplementary material. All the data used in this paper are open-sourced.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
htt.esummsssiioooosiioooo onPolicyl icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cccpublic//aeeccccccccccccc htppllicggiieeee http//uudes/eeeeee /Code//dmdSSbiii setbbbmmssionP ssionPolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The details are contained in the main text and section D in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: All plots in this paper are presented with error bars indicating one standard deviation based on 5 random trials. All numbers reported in each tables are also accompanied by one standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We provide hardware configurations used in our experiments in section D in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that NeurlPS Code of Ethics https: htttps:///eurre http://eeeripp.eeeee httppp/se/aarrrss.cc///b////ccct httppp/blit/Bhhhcccciiee.ee.lee
didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer:
[Yes]
Justification:
We conform in every aspect the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the broader impacts of this paper in section A.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
40

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All the lisence information of the codes released in this paper are detailed in section
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
41

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
42

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "zRBwB3eytT", "reviewer": "Reviewer_M6Kg", "summary": "The paper studies to which degree graph representations are vulnerable to similarity-based edge reconstruction attacks (SERA).\nSERAs encompass a variety of attacks used to recover the structure of a graph, where a SERA guesses that an edge exists between pairs of nodes that have similar embeddings.\nThe paper considers linear GNNs and highlights how SERAs are particularly successful in reconstructing large and sparse graphs.\nOn the other hand, the authors show that edge recovery is less successful when considering graphs generated from a stochastic block model. \nAdditionally, the paper presents an analysis and discussion of noisy aggregation as a mitigation technique against SERAs.", "questions": "* In Remark 4.2 you state that the requirement of plolylogarithmic growth of the feature dimension is a byproduct of your proof. Can then this requirement be removed? How?\n* In your theoretical investigation you do not use homophily to derive your results. While this is an interesting perspective as you bound the attack performance if homophily is not an assumption, what can you say when homophily _is_ an assumption?", "limitations": "The paper discusses limitations in the appendix.\nIt would preferable to expand the discussion of limitations in the main body of the paper.\nThe discussion of future work is completely deferred to the appendix, and would benefit as well from a dedicated paragraph in the main body of the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The paper presents an interesting overview of the strengths and limitations of edge reconstruction attacks based on similarity.\nThe motivation is clear and the paper is generally well structured.\nThe results on the theoretical performance of SERAs on both sparse and dense synthetic graphs are accompanied by an empirical evaluation.", "weaknesses": "**Assumptions**\n\nThe assumptions in Theorem 4.1 require further discussion.\nWhile the authors mention in Remark 4.2 that the assumptions may not \"consistently align with practical scenarios\", it is unclear in which cases they may align at all with a practical scenario.\nIn section 7.1, you state that the linear model you analyse theoretically can be used as a proxy for a non-linear counterpart.\nI therefore wonder: to which degree do the assumptions in Theorem 4.1 hold on real datasets?\n\n\n\n**Empirical evaluation**\n\nThe readability of the he empirical results in Section 7 could be improved.\nSpecifically, the plots in Figure 1 and Figure 2 are very small, and the labels too tiny.\n$\\hat{A}^\\text{SERA}$ in Table 1 is not defined, and so is the expression \"trained\" and \"non-trained\", in this context.\nWith respect to the results themselves, in Section 7.1 you claim that \"SERA is able to achieve near-perfect reconstruction of all edges only in the 'large $d$, small $L$' regime\".\nFigure 1a, however, seems to show that for large $d$ the attack AUROC is high for all depths $L$.\nThese results would benefit from further comments and a better visualization of the results, as it is at the moment not easy to infer numerical values form the colour gradients in Figure 1.\n  \n\n**Language clarity**\n\nThe language is at times excessively verbose and difficult to parse.\nFor instance, in the description of the threat model in line 116, the \"objectives ascribed to the adversary\" are described as \"decidedly audacious\", as they aim at the \"potential elucidation of the entire suite of edges\" of an attacked graph.\nThese sentences are not only difficult to read, but also vague.\nI would strongly recommend a more dry writing style which is better suited to convey technical content as, despite the good general organization of the paper, the current style hinders ease of read and is the main motivation for my low presentation score.\n\n\n\n**Other comments**\n* The brackets used for citations should, generally, not be interpreted as part of the sentence. So, e.g., in line 68, \"proposed by [10]\" -> \"proposed by Duddu et al. [10]\".\n* Line 80, \"don't\" -> \"do not\".\n* Line 152. \"be a universal\" -> \"be universal\".\n* \"related works\" -> \"related work\".\n* References to theorems, sections, etc., are inconsistently reported with both lower-case or upper-case initials.\n* Several equations, particularly in the appendix, should be better typeset to help readability. Specifically, several parenthesis are not adjusted for the size of the expressions they contain.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n## Q1: Practicality of assumptions in theorem 4.1\nAccording 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$.  \nRegarding 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.  \n\n## Q2: Clarifications of empirical evaluations\nWe 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.  \nRegarding 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.\n\n## Q3: Possiblity of incorporating homophily into our theory\nThis 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DkP7Ba2bhv", "reviewer": "Reviewer_VCKp", "summary": "The paper studies the performance of similarity-based edge reconstruction attacks (SERA) for graph representations, considering two particular similarity measures (cosine and correlation).\n\nThe main contributions are presented in Theorem 4.1 and Theorem 5.1, which analyze the performance of SERA on graph representations (without privacy-preservation techniques applied), and in Theorem 6.1, which considers noise aggregation (NAG) for privacy-preservation.", "questions": "Lines 109-118: The description of the two-party attack model is confusing. I had to read the model description in the Appendix to understand it. Please keep the writing concise and precise to improve readability.\n\nLines 31-36: Can you explain how \"feature similarity may serve as a confounding factor, potentially impacting the efficacy of similarity-based attacks\"? This statement contradicts the previous sentence.\n\nLine 156: $\\Theta$ is not defined.", "limitations": "The authors adequately addressed the limitations in the Appendix.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "See my comments in Weaknesses", "weaknesses": "My concerns are as follows:\n\nWhile I appreciate the efforts in deriving generalization bounds for this specific attack model, the implications of this paper remain insignificant to me. The results in Theorem 4.1 and Theorem 5.1 seem too straightforward, as they can be immediately inferred from the perspective of detection theory. For instance, focusing on the linear graph neural network in Equation (1), Theorem 4.1 essentially states that the accuracy of correlation detection grows with increasing samples. There are certainly existing works that have already characterized the statistical performance of link prediction in more general and profound ways, rather than fixing the detection method and linear aggregation as assumed in Theorems 4.1 and 5.1. Please refer to the papers \"Revisiting Link Prediction: A Data Perspective\" and \"Statistical Guarantees for Link Prediction using Graph Neural Networks.\"\n\nTheorem 5.1 also appears trivial. For example, the paper \"GAP: Differentially Private Graph Neural Networks with Aggregation Perturbation\" had already characterized the level of differential privacy for edge prediction. There is extensive literature connecting detection accuracy with differential privacy. For example, you can derive mutual information and then obtain the detection error bound by applying Fano's inequality (assuming the prior distribution of the graph representations, as stated in your paper). My question is, what is the new observation from Theorem 6.1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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:\n\n## In theory, link prediction is related to, but different from edge reconstruction\nTheoretically 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.  \n\nNext we address your questions in detail:\n## Q1: Are theorem 4.1 and 5.1 trivial, based on recent developments on link prediction?\nNow 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:\n- 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.\n- 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.\n\n  \nRegarding 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.\n\n## Q2: On theorem 6.1 and experiments\nTheorem 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.  \n\nHopefully 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.\n\n[1] Mao, Haitao, et al. \"Revisiting link prediction: A data perspective.\" arXiv preprint arXiv:2310.00793 (2023).  \n[2] Chung, Alan, Amin Saberi, and Morgane Austern. \"Statistical Guarantees for Link Prediction using Graph Neural Networks.\" arXiv preprint arXiv:2402.02692 (2024).  \n[3] Sajadmanesh, Sina, et al. \"{GAP}: Differentially Private Graph Neural Networks with Aggregation Perturbation.\" 32nd USENIX Security Symposium (USENIX Security 23). 2023.  \n[4] Nasr, Milad, et al. \"Adversary instantiation: Lower bounds for differentially private machine learning.\" 2021 IEEE Symposium on security and privacy (SP). IEEE, 2021.  \n[5] Xu, Jiaming. \"Rates of convergence of spectral methods for graphon estimation.\" International Conference on Machine Learning. PMLR, 2018.  \n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4JmX7hJUd4", "reviewer": "Reviewer_w4Le", "summary": "This paper investigates the ability of the similarity-based edge reconstruction attack (SERA) on attacking both sparse and dense networks, under various configurations of graph neural network (GNN) structures. The authors demonstrate, through both theoretical analysis and experimental results, that SERA performs well on sparse networks but poorly on dense networks. Additionally, they demonstrate the effectiveness of the noisy aggregation (NAG) technique on the resilience of SERA.", "questions": "(1) In line 286, it is stated, \"Yet the behaviors in small d regimes appear to be less predictable, a phenomenon we hypothesize may be attributable to an inadequate concentration of inner products in instances where the feature dimension is relatively small.\" Can the authors explain in detail what this means?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This is a initial work to take a step towards a principled theoretical understanding of the effectiveness of SERA over sparse/dense features and different configurations of linear GNN. The theoretical results are presented in a clear and sound way. The proof is rigorous and clearly demonstrated. The explainations following each theorem give good supplements to the theory.", "weaknesses": "1. Writing Quality: The writing in this paper needs improvement. The authors have used many unnecessarily complex words and sentences, making the paper harder to read and understand. Additionally, there are numerous typos and grammatical errors that need to be corrected.\n\n2. Theoretical Analysis Limitation: The theoretical analysis focuses on linear GNNs rather than non-linear GNNs. While the authors have shown experimentally that results for linear GNNs can serve as proxies for those of non-linear GNNs, the guarantee of this is unclear to me.\n\n3. Rationale for Studying SERA: In section 2.1, the authors mention that there are attacks more powerful than SERA. This raises the question of why they chose to study SERA in the first place.\n\n4. Accuracy of Statistic in experiment: In Table 1, the authors measure the similarity between feature similarity and edge presence using a statistic $\\mathcal{H}$, which only evaluates the similarity of features between nodes with an edge. It does not consider nodes without an edge, leading me to question the accuracy of the statistic to measure similarity and thus the results analysis. In my opinion, it should also capture the dissimilarity of features between nodes without an edge.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments, we will integrate your suggestions into revised versions of our paper. Below we address some specific points:\n\n## Q1: About the writing style\nThank you for the advice and we will polish our writing to improve clarity and conciseness.\n\n## Q2: On the limitations of study linear GNNs\nPlease 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. \n\n## Q3: Rationale of studying SERA\nWe 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.\n\n## Q4: Accuracy of experiment\nWe 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\n\n## Q5: Explaination of the statement in line 286\nWe 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:\n- 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\\\\%$).\n- 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.\n\n[1] He, Xinlei, et al. \"Stealing links from graph neural networks.\" 30th USENIX security symposium (USENIX security 21). 2021.  \n[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).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their thought-provoking comments. We believe these valuable comments will lead to improvements of our paper. As we noticed some common concerns among the reviews, we provide some clarifications below:

## About our analysis on linear GNN
In appendix F.3 of our paper, we acknowledge that our analysis under linear GNN is a limitation of our work. The mathematical challenge in extending our analysis to nonlinear GNN stems from the relationships between node representations $h_v^{(L)}$'s and node features $x_v$'s. Under nonlinear GNNs, it becomes prohibitively hard to compute the non-trivial upper or lower bounds for the correlations between $h_u^{(L)}$ and $h_v^{(L)}$ for either $u \neq v$ or $u = v$.  
Additionally, so far as we have noticed, many previous non-asymptotic theoretical developments on multi-layer GNNs are based on the linear GNN model [1, 2].  
While theoretically analyzing nonlinear GNNs is challenging, we provide empirical evidences in section 7 (and more specifically in Appendix E.2) that systematically compare the performances of linear GNN and 4 prevailing nonlinear GNNs (GCN, SAGE, GAT and GIN) over 8 benchmark datasets with varying homophily level (See table 3 for a detailed report). The attack performances exhibit strong correlation between linear GNN and nonlinear GNNs across datasets. Besides, we observe from experimental results that *linear GNN often exhibits slightly weaker attack performance than nonlinear GNNs*. As we have shown that edge information is provably vulnerable even under linear GNN, we believe an analogue with nonlinear GNNs should hold and we left these developments to future explorations.

## Some clarifications of tables and figures
We thank the reviewers for pointing out illustration issues in figure 1 and table 1 of the paper. We provide some clarifications below:
1. [**Figure 1**] We present a detailed list of attack performance numbers in the attached pdf for $d \in \\{512, 1024, 2048\\}$ (corresponding to figure 1(a)). We will include a number-marked grid in revisions of the paper for improved illustrations.
2. [**Table 1**] The rationale behind the design of table 1 is that we want to verify the effectiveness as well as the robustness of SERA against varying *dataset characteristics* as well as *training dynamics*. To measure dataset characteristics (regarding homophily level), we use the feature homophily metric as well as the AUROC of feature similarity against edge existence, which we denote as $\widehat{A}^\text{FS}$. To systematically investigate the impact of traning dynamics, we conduct two set of experiments where the GNN weights are obtained either via random initializations (non-trained in table 1 and table 3), or via a standard training procedure (trained in table 1 and table 3) which we detail in appendix E.2 of the paper.

## About the writing style
We thank the reviewers for advices on our writing style and we will carefully polish our writing by enhancing clairty and conciseness.

[1] Wu, Xinyi, et al. "A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks." The Eleventh International Conference on Learning Representations.  
[2] Chung, Alan, Amin Saberi, and Morgane Austern. "Statistical Guarantees for Link Prediction using Graph Neural Networks." arXiv preprint arXiv:2402.02692 (2024).

Meta-review: The paper discusses the ability to reconstruct a graph from representations learned by GRL techniques, theoretically and empirically.  The reviewers appreciated the analysis and results, but also highlighted the significant limitation that the theoretical results assume linearity (although empirical results do not).
Decision: Accept (poster)