GraphPrivatizer: Improved Structural Differential Privacy for Graph Neural Networks
Authors: Rucha Bhalchandra Joshi
Patrick Indri
Subhankar Mishra
Venue: Accepted by TMLR ()

Abstract: Graph privacy is crucial in systems that present a graph structure where the confidentiality and privacy of participants play a significant role in the integrity of the system itself. For instance, it is necessary to ensure the integrity of banking systems and transaction networks, protecting the privacy of customers' financial information and transaction details. We propose a method called GraphPrivatizer that privatizes the structure of a graph and protects it under Differential Privacy. GraphPrivatizer performs a controlled perturbation of the graph structure by randomly replacing the neighbors of a node with other similar neighbors, according to some similarity metric. With regard to neighbor perturbation, we find that aggregating features to compute similarities and imposing a minimum similarity score between the original and the replaced nodes provides the best privacy-utility trade-off. We use our method to train a Graph Neural Network server-side without disclosing users' private information to the server. We conduct experiments on real-world graph datasets and empirically evaluate the privacy of our models against privacy attacks.

Published in Transactions on Machine Learning Research (09/2024)
GraphPrivatizer: Improved Structural Differential Privacy for Graph Neural Networks
Rucha Bhalchandra Joshi"
rucha.joshiimiiser.cc..
National Institute of Science Education and Research, Bhubeneswar Homi Bhabha National Institute, Mumbai
Patrick Indri"
intrick.indriStunne
Research Unit Machine Learning TU Wien, Vienno
Subhankar Mishra
smishra@niser..a
National Institute of Science Education and Research, Blubaneswar Homá Bhabha National Instätute, Mumbai
Reviewed on OpenReview: https: openreviee. net/ formmo lcPtUhoGYe
Abstract
Graph privacy is crucial in systems that present graph structure where the confidentiality and privacy of participants play significant role in the integrity of the system itself. For instance, it is necessary to ensure the integrity of banking systems and transaction net- works, protecting the privacy of customers' financial information and transaction details. We propose a method called GraphPrivatizer that privatizes the structure of a graph and protects it under Differential ial Privacy. GraphPrivatizer performs controlled perturbation of the graph structure by randomly replacing the neighbors of node with other similar neighbors, according to some similarity metric. With regard to neighbor perturbation, we find that aggregating features to compute similarities and imposing minimum similarity score between the original and the replaced nodes provides the best privacy-utility trade-off. We use our method to train a Graph Neural Network server-side without disclosing users' private information to the server. We conduct experiments on real-world graph datasets and empirically evaluate the privacy of our models against privacy attacks.
1 Introduction
In recent years, many research efforts have boen made to effectively learn from graph-structured data. Graph- based approaches have been successful in variely of lasks such as fake news detection in social networks (Benamira et al. 2019) and drug discovery (Gaudelet et al. 2021). Graphs can incorporate both information about individual data points and about their interactions: Graph Neural Networks (GNNs, Scarselli et al. 2008) have been in capturing this information and learning over graph-structured data. Both the information about the individual data points and the relational information can be, however, of sensitive nature and must, therefore, be protected. Large scale machine learning models may require sending information to a server where the training is performed, which poses a privacy risk. Efforts have thus been recently made to address privacy attacks on graphs (Zhang al.) 2021 2022). One possibility protect private information the formal privacy guarantees offered by Differential Privacy (DP, Dwork 2006), whose graph-structured data has been recently expanding (Mueller et al. 2022b). DP has
graphs is range of applications
been used both in centralized settings where server has graph-wide access to information (Olaunji et al.
2023
Wu et al. 2022 Sajadmanesh et al. 2023) and in local settings (Sajadmanesh & Gatica-Perez 2021
1 'Equal contribution.

---

Published in Transactions on Machine Learning Research (09/2024)
In centralized privacy setting, trusted entity is allowed to gather the private data and learn on it, while promising to release model from which private information cannot be inferred. In this setting, the training procedure itself must therefore be DP (Abadi et al.) 2016). A local privacy setting is instead desirable when no entity is trusted to gather all the private information: in this case, data must be privatized locally before it is made available to a central entity where the training is performed. The local privacy setting is therefore crucial in cases where no central entity trusted to be willing and capable to keep private data secure. Once the data has been locally privatized, the central server is not able to infer private data and the training procedure itself does not need to be DP [Mueller et al. 2022b). Despite these advantages, a local privacy setting often results in reduced performance if compared to the centralized one (Cormode et al. 2018 Yang et al. 2023 due to the large amount of noise that the local privatization entails.
While recent efforts have been made towards improving the ciiaacy-utllity trade-off in a local privacy setting
(Yang et al. 2023 little investigation on locally privatizing the edges of graph which then trained on a
central entity (e.g.: a server) has been previously performed. Motivated by rcal-world applications such as private learning on social network data, we therefore focus on protecting the relational information contained in graphs by means of local privatization techniques that act on the individual users' side.
To address this problem, we propose GraphPrivatizer, a method to locally privatize a graph's structure that does not rely on graph-wide information, and which protects the privacy of features and labels as well. In particular: (i) We introduce a definition of edge LDP for our local privacy settings; (ii) We propose GraphPrivatizer, a method that locally privatizes the structure of a graph while preserving the out-degree of nodes by construction and keeping labels and features private too; (iii) Taking advantage of the notion of message passing in GNNs, we parametrize the perturbations of node's neighborhood which allows to only replace neighbors with other similar nodes to improve utility while preserving privacy; and (iv) We evaluate our proposal on different real-world datasets to investigate its privacy-utility trade-off, empirically assessing its privacy guarantees using privacy attacks that try to recover the private structure of the graph.
2 Related Work
GNNs have gained increasing popularity as the framework of choice to solve graph-based learning tasks in recent years. The efficacy of GNNs in graph representation learning has motivated the proposal of several GNN variants such as Graph Convolutional Networks (Zhang et al. 2019). : Graph Attention Networks VVelickovéć et al., 2018), and GraphSAGE (Hamilton al.] (017)) as well as architectures for large multi-
relation graphs (Iyer et al.) 2021 Wang et al.
2019). Recent rescarch efforts have also been made to address privacy allacks on graphs (Zhang et al. 2021 2022). Privacy allacks can be categorized graph properlies attacks (inferring, e.g., the number of nodes), membership attacks (inferring, e.g., whether subgraph is
part of a graph), and graph reconstruction attacks (Zhang et al. 2022) Specifically, the existence of an edge between two nodes is often sensitive in nature (Mueller et al.
2022b and should be kept private.
Differential Privacy (DP, Dwork 2006) offers formal privacy guarantees to protect information about in- dividual training points, and has been used to provide privacy guarantecs in GNNs as well. DP has been utilized in centralized settings where a server has access to information the entire graph (Olatunji et al. 2021 Joshi & Mishra 2022 2023). Different formulations of DP on graphs aim at protecting the relationship
2023 Wu et al.] 2022
Sajadmanesh et al., 2023). and in local settings (Sajadmanesh & Gatica-
between nodes edge-level DP) (Raskhodnikova & Smith 2016 Hidano & Murakami] 2022), the individual
nodes themselves (node-level DP) (Raskhodnikova & Smith 2016 Ayle et al.) 2002 Kasiviswanathan et al. 2013 Olatunji et al.) 2003),, or the entire graph as a single entity (graph-level DP) (Mueller ct al. 2022a For survey on recent advances in DP approaches on structured data, refer to Mueller et al. (2022b).
In this work, we focus on protecting the structure of the graph, i.e. hiding its edges. Previous work has addressed structural privacy using central (Sajadmanesh et al. 2023 Olatunji ct al. 2023 or local (Joshi & Mishra 2022 2023 Hidano & Murakami] 2022) DP; these approaches require however some entity to have
access to the entire noiseless adjacency matrix of the graph (Sajadmanesh et al. 2023 Joshi & Mishra 2022) or to part of it (Joshi & Mishral 2023 Hidano & Murakami (022) in order to privatize the graph structure.
Such approaches may thus pose privacy concerns or depend on the availability of public data (Olatunji et al.,
2023). Additionally, approaches such as (Sajadmanesh et al. 2023) require the introduction of custom
2

---

Published in Transactions on Machine Learning Research (09/2024)
architecture. Hidano & Murakami (2022) propose begree-preserving randomized response algorithm for graph classification on unattributed graphs where they empirically show the benefit of preserving the degree of nodes after graph perturbations. Besides the different learning task they consider, as we will focus on node classification for graphs with node features and labels, Hidano & Murakami (2022) roquire nonetheless that each node aware of how many nodes the graph contains. Joshi & Mishra (2023) is, to the best of our knowledge, the closest existing approach that guarantees edge-level local DP: their approach requires however that each node has noiseless access to portions of the adjaceney matrix and comes a substantial reduction in model performance if compared to non-private model. Additionally, IJoshi & Mishra (0233 do not test against privacy attacks that try to recover the edges of the graph. In comparison, our approach can be used with any conventional GNN architecture and we do not rely on public data: we adopt a local privacy setting where the individual nodes have noise-free free access only to their own edges, features, and labels, and where no entity has access to the complete adjacency matrix of the graph.
3 Preliminaries and Problem Statement
In this section we recall the definitions of Graph Neural Network (GNN, Scarselli al. 2008) and Local Differential Privacy (LDP, Dwork 2006 Yang et al., 2020). Then, briefly discuss randomized response (RR,, Warner 1965) and edge privacy in graphs, well as LinkTeller (Wu et al. 2022) the privacy attack we use to validate our approach. Finally, we describe our local privacy setting and problem statement.
3.1 Graph Neural Networks
Consider an unweighted graph defined as a tuple = (V,,,,,, where V = Vv the set union of labeled nodes VE and unlabelled nodes Ve, E the set of edges, X E RIVixd is a feature matrix consisting of d-dimensional feature vectors, one for each node v E V, and Y is the set of labels. Let .V(v) denote the neighborhood of ve that is, the set of nodes which are adjacent. u. Let deg(v) v) denote the degree of v, that is, the size of its neighborhood. Graph Neural Networks (GNNs, Scarselli et al. 2008) are a class of models that have been effective in lcarning over graph-structured data. À typical GNN consists of L layers where the embeddings of the nodes in a certain layer are obtained from the previous layer by means of an aggregation and an update function. Specifically, the embedding h² for a node v in layer is obtained by aggregating the embeddings of its neighbors N(v) from layer - and passing the resulting aggregated message m through the update function. The aggregation function is a permutation invariant and differentiable function, while the update function is trainable and non-linear function:
m AGGREGATE((M1 (
(1)
11 = UPDATE((M)) ,,
(2)
Common choices for the AGGREGATE function are the sum or the mcan, while the UPDATE function can be. for instance, a neural network.
3.2 Differential Privacy
Differential Privacy (DP, Dwork 2006) a formal definition of privacy that protects individual training points. As originally introduced by Dwork (2006), central or global DP, simply referred to as DP, was designed for centralized setting where trusted entity gathers all user data and guarantees to process it and produce output while preserving the privacy of users. More formally, DP guarantees that an attacker cannot confidently infer whether the output of a DP mechanism M was obtained from a database D or from a database D', where D and D' differ in single record and are thus said to be adjacent datasels. In a local privacy setting no trusted entity can process the private data of users. In this more restrictive case each user perturbs data locally and provides the central entity with a noisy version of its data only. In a local privacy setting the datasets D thus consist of data from individual users which then protected under Local Differential Privacy (LDPP, Yang et al. 2020
3

---

Published in Transactions on Machine Learning Research (09/2024)
Definition 3.1 (c LDP). Let E > O. Consider randomized mechanism M D - R and probabilities Pr laken over the coin losses of M. M salisfies local differential privacy i, for any possible pairs of user's ' private data points T, x' E 'D and for any possible outputs S R.:
Pr[M(z) E S PH[M(z')
We refer to c as the privacy budget of the algorithm. In particular, c = 0 indicates that the randomized mechanism is perfectly private and implies that the output of the mechanism is independent of the input. On the other hand, 0o provides no privacy guarantee. The choice of e is both problem and data dependent (Tee & Clifton 2011), with common ranges often considering values c E (0, 10] (Wu et al. 2022 Sajadmanesh & Gatica-Peren 2021 For given deterministic function, DP can be achieved by adding random noise to the output of the function to hide the contribution of individual training points, where the amount of noise added depends on the choice of privacy budget e (Dwork et al. 2014). As no single entity is trusted with all the users' private data, LDP is generally a stronger privacy model than DP. However, the lack of such trusted central entity and thus the need to add noise to the local data of each user before communicating it to the central entity entails greater total noise which can negatively affect model performance (Cormode) et al., 2018). This, in turn, enhances the importance of novel approaches that can provide LDP with good accuracy which are thus our focus.
3.3 DP and privacy attacks in GNNs
DP can be applied to graph context by defining a notion of adjacency for graphs. Cousidering the (central- ized) DP setting first, we say two graphs G and G' are edge adjacent if they differ exactly in one edge, that is, if G' can be obtained from G by adding or removing a single edge. Similarly, G and G' are node adjacent if they differ in exactly one node, that is, if G' can be obtained from G by adding or removing a single node and its edges. In our local privacy setting we consider LDP which can guarantee privacy on graphs in the sense of Definition 3.1 on any pair of adjacent user inputs. Focusing here on edge privacy, one can define a notion of edge adjacency to protect a user's edges. A common dcfinition of edge LDP considers a user's v neighbor list as represented by [Vl-dimensional bit vector b(v1), where b1,=11,--VV1 1 if and only if there is an edge between node and node Us, and 6; 0 otherwise.
Definition 3.2 (e-edge LDP, (Qin et al. 2017)). Let > O. A randomized mechanism M D: - R satisfies c-edge local differential privacy if, for any possible pairs of user's 's neighbor lists b, V differing by one bit, and for any possible outpulss S C R, it holds that:
Pr[M(b) S ES
Edge LDP can be achieved by perturbing the neighbor list of each node using randomized response (RR, Warner 1965 Qin el al. 2017]. RR flips every bit of each neighbor list with probability 1/(e" + 1), guar- anteeing e-egge LDP. However, as large values of e are undesirable because they imply low privacy, and as the neighbor list is often sparse, RR increases the connectivity of the graph. The addition of many spurious edges has negative consequences on the performance of GNN trained on the perturbed graph (Joshi & Mishra 2022): thus, we develop different perturbation techniques which offer a better trade-off between privacy and model accuracy for graph data. In this work, we propose an alternative definition of adjacency for edge privacy which imposes additional conditions on the edges RR can act on.
To validate our approach, we test it against a Tinleeller attack. LinkTeller Ww et al. 2022 is an influence analysis based attack that recovers private edges from trained GNNs. The attack assumes that the trained can provide node features to query the API and obtain
GNN exposes inference API; at test time, predictions for said nodes. For each pair of nodes the attacker provides perturbed feature vectors for the first node and queries the API with them, evaluating the effect this has on the predictions of the second node. The alfacker then guesses the presence of edges between the pairs of nodes which have a high influence on each other. See Wu et al. (2022) for more details on LinkTTeller. As LinkTeller cannot deal with randomized models such as GraphSAGE (Wu et al. 2022), we instcad attack it using the LSAA attack described in He et al. (2021). LSA2 leverages on node-level information and computes the model posterior for every node the attacker possesses, assigning edges to pairs of nodes whose posteriors have a high correlation.
4

---

Published in Transactions on Machine Learning Research (09/2024)
3.4 Problem statement
We address private learning on graphs with LDP where each node can is considered as an individual user: for a graph G EV, Y) we consider V, E, X, and Y to be private to individual nodes/usery which only share noisy versions of them with server. The server uses the information train GNN for node classification, learning to predict labels Y in semi-supervised learming setting. More explicitly, no en- tity (neither users/nodes, nor the server) has complete and noise-free free information about the graph. The only noiseless in- formation a node can have access to its own features, label, and edges (Figure 1). We elect this as our setting of choice because of its similarities with real-world scenarios where indi- vidual nodes/ uudes/ users may not have knowledge about the entire graph beyond the nodes/users they directly interact with.
Node
1-hop neightors
2-hop neightors
Figure 1: In our setting, node knows only about its immediate, 1-hop neighbors. In fact, a node may not be aware of its 2- hop neighbors in a real-world sccnario.
4 Approach
In this section, we introduce our approach, called GraphPrivatizer, which provides edge, feature, and label privacy. Specifically, focus on investigating the trade-off between edge privacy and GNN performance in the local privacy setting described in [Section 3.4. A global notion of differential privacy is not allowed by our local privacy setting, no central entity is trusted with the entire graph. e-edge LDP (Definitonn 3.2 too has limitations in our privacy setting, as we will discuss in the next section. Therefore, we provide a new definition edge privacy for our sctting and propose a novel edge private algorithm based on it. To guarantee label and/or Teature privacy, GraphPrivat uses existing techniques presented in Section 4.3.
4.1 Adjacent neighborhoods
The definition of e-edge LDP provided in Section 3.3 entails the perturbation of the neighbor list of a node v using RR, where two neighbor lists are adjacent they differ by one bit. As previously mentioned, this perturbation leads to a great increase the counectivity the graph for small, thus desirable, values of e. Moreover, in the local privacy setting described in [Section 3.4 a node's neighbor list include only its immediate neighbors and there are therefore no graph-wide neighbor lists to perturb with the standard RR approach. To define notion of privacy which is appropriate for our setting choose to consider the set of neighbors of node v: two neighbor sets are said to be adjacent if they differ by single node.
Definition 4.1 (Adjacent neighborhoods). Consider node Let b {uI...., Va} N((v,, 8' Tvi....,''d = (N) be two neighhor sets, with d deg(v). We say N(v) and N' are adjacent if they differ in only one element; that is, they are adjacent neighborhoods if, without loss of generality, en vi and v; = v/ for 2 d.
We use Definiton 4.1 to introduce an edge set notion of LDP, which we refer to as e-edge set LDP.
Definition 4.2 (c-dge set LDP). Let > 0. A randomized mechanism M D - R satisfies e-edge set local differential privacy if, for any possible pairs user's neighbor sets b, b that are adjacent according to Definition 4.1, and for any possible oulputs S C R, it holds thal:
Pr[M(() E S] e PT[M((') e S]
cedge set LDP can be seen a relaxation of e-edge LDP Detinition 3.2 as it practically entails a more controlled perturbation of the edges of a node. To be more explicit on the relation between e-edge set LDP (Deinition 4.2) and the e-edge LDP (Definition 3.2 notion used by related work such as Joshi & Mishra (2023), note that one can obtain any set perturbation as described in Definition 4.1 by means of two bit flips on the neighbor list of node. A 2c-edge LDP mechanism is thus also e-ddge set LDP. The converse does not. hold not all two bit flips the neighbor list of node correspond to set perturbation
5

---

Published in Transactions on Machine Learning Research (09/2024)
Moreover, and in contrast with e-edge LDP, adjacent neighbor sets according to Definition 4.1 have the same number of nodes. Thus, a perturbation of the neighborhoods based on this notion of adjacency preserves, by construction, the degree of nodes. The preservation of node degrees after private perturbations is a desirable property as empirically shown, albeit for the different task of graph classification on unattributed graphs, by (Hidano Murakami 2022
described in Definition 4.1
4.2 Edge privacy
Equipped with the notion of adjacency in Definition 4.1] we develop a perturbation technique that acts on the neighbor set a node which is edge set LDP in the sense of Definiiion 4.2) Our approach informally soeks to replace nodes in a neighbor set with other nodes that are similar with respect to some similarity measure. The perturbed neighborhood can in this way retain more of the original information content of the neighborhood and provide good performance. Specifically, our proposal randomly replaces a neighbor u of a node with one of the neighbors of itself. That is, perform perturbations considering nodes in the two-hop extended local view (Sun et al.) 2019) of v. Two neighborhoods of are then adjacent according to Definition 4.1 if one can be obtained from the other by means of an edge perturbation within the two-hop expended local view
which preserves the degree of v. The replacement itself then occurs via RR, which ensures the privacy of the procedure. Conceptually, we can describe our method as consisting of two steps. The neighbor set (vv) of a node v is perturbed by: (t) selecting a set of candidate replacement nodes for the neighbors of and (ii) randomly picking of the replaccment nodes using RR. Algorithm 1 describes the procedure. We provide a summary of the main notation for ease of read.
Algorithm 1 Perturb neighborhood
Notation
Input: Graph G = (V,E, Y), node v E V, similarity Sox threshold aggregation coeff. a, strategy a)))
8
threshold on similarity
Output: (v): Perturbed neighborhood of node v
Cx
aggregation coefficient
1: (Nl) GetNeiggbors(v;.]]
feature vector of node u
2: (N'v)) + Ø
3: u E (v) do
aggregated feature vector of node u and M(),, eq. (3)
4: v' = [R, QuerySimilar(G Sn. a, (,
Zn,o
(w))) - (N))
cosine similarity between
6: end for
s. u)
Tv,a and Zu,os eq. (4)
7: returrn (v))
Consider node and assume we want to perturb its neighbor set NNu) by replacing some of its nodes. Nodes (v) are randomly replaced with nodes picked in a set of candidates, where the candidates are selected from nodes in the two-hop extended local view of v according to similarity measure s. That is, the set of nodes which are considered as candidates to replace a node u is constituted of nodes u' that are similar to u. Given our local privacy setting, non-parametric and non-learnable similarity measures are a natural choice as no prior information on the data is available. We provide a comparison of the performance of our approach using the Euclidean distance and the cosine similarity in Appendix B and find that the cosine similarity is preferable.
We therefore measure the similarity between u and candidate w' using the cosine similarity of their Zu' feature vectors Iu and Tw', = ||> ||,, In this regard, we devise two strategies to obtain the set of candidates based on similarity, which are described in Algorithm 3 and [Algorihhm 4 For both strategies, only the nodes u' which have a similarity score exceeding threshold ō are selected as the set of candidates. As GNNs perform aggregations of the features of neighbors produce embeddings, we additionally propose to use such aggregated leatures to compute similarity scores. We therefore evaluate the similarity of a node u which
using ACG,, = AcGREGATE((s, parameterizes the contribution of aggregated features in the similarity computation. That is, for cach node u we compute the aggregated feature vector Zu,a of node u and N(u) as
Vn E (N())) instead of zu. We denote with a the
Fu,a = (1 a) + AGG..
(3)

---

Published in Transactions on Machine Learning Research (09/2024)
The similarity between two nodes and u' is then computed as
Tu.a Tu'.a
Sa (u, = | Tul all
(4)
To summarisc, > can be used to filter out dissimilar replacement candidates, while a > O is used to introduce aggregate information in the similarity computation. The case a = 0 introduces no thresholds for the application of RR and no aggregation, and will thus be used as our reference in- vestigate the impact of such thresholds and aggregations. When computing Sinilarities/aggreaatioo tween nodes, noisy feature vectors obtained according to [Section 4.3 are used, ensuring that feature pri- vacy is not violated. Our method is thus consistent. with the setting described in [Section 3.4 as we assume that the only noiseless information a node has access to consists of its own features, labels, and edges to 1-hop neighbors. Algorithm describes the procedure to select replacement candidates.
be-
Algorithm 2 QuerySimilar
Input: Graph G = (V, E, X, Y), node E V, similarity sa, threshold ö, aggregation coeff. a, strategy g( a, 6) Output: S(v): set of nodes similar to v, according to Sa
1: S(v) < Ø
S(e) g(u, Sas ax
get similar nodes according to strategy
3: return S(e)
As anticipated, we utilize two different strategies g to select candidates for node u based on their similarity, Specifically, we either consider u's most similar neighbor if it exceeds the similarity threshold 8 as a candidate for replacement (Algorithm 3) or all the neighbors that exceed the similarity threshold 8 (Algorithm 4
Algorithm Most-similar neighbor
Algorithm 4 Threshold-basee similar neighbors
Input: node v, neighborhood Niv), similarity function Sa, threshold 6, aggregation coeff. a Output: my: v's most similar neighbor
Input: node v, its neighborhood W(v), similarity function Sa, threshold 6, aggregation coeff.
Output: T(v): set of neighbors similar to v
1: T(v) + 0
1: m. arg max So (u, wEN(U)
2: for a E do
3: if s. u) 2 5 then
8. (v, (., m.) ) 2 then
4:
T(v) + T(b) Un
3: return my
5: end if
end if
6: end for
return
7: return T(v)
For each node the number of similarity values which need to be computed to perturb its neighborhood de- pends on the number of nodes in the two-hop extended local view of v and is upper bounded ΣmeN(w) deg(u) which may thus be computationally expensive for very dense graphs. However, in a practical setting where nodes are distributed among different computing units, the neighbor perturbation performed locally by the individual nodes. Moreover, the nodes only require the (perturbed, possibly aggregated) features of their neighbor compute their similarity with them. In terms of communication cost, this amounts to two appli- cations of the AGCREgATE (Section 3.1) function and is done these considerations and the observation that real-world datasets have small average degree Table 4). we expect an efficient implementation of our approach to scale well to sparse large graphs
pre-processing step before training. With
Once a set of candidate nodes has been obtained, the neighbor perturbation is performed in Algorithm with RR. The probabilitics of replaccment associated with RR differ whether we consider one candidate replacement, (strategy in Algorithm 3) or set of candidate replacements (strategy in Algorithu 4p. Denote with Pr[u - w') the probability that node u gets replaced with node v'. If we consider the most similar replacement candidate only, RR is applied as follows.
=' =u
Pr[u + w/]= =
(5)
otherwise
7

---

Published in Transactions on Machine Learning Research (09/2024)
If we consider the threshold-bant based strategy, RR is instead applied as follows.
if o/ otherwise
Pr/u + u1 =
4 e
(6)
To distinguish the two strategies, we refer to our method as GraphiPrivatizer-m (GP-m) when using the most-similar strategy, and as GraphPrivatizer- (GP-t) when using the threshold- based strategy. Regardless of the strategy, our approach is c-ddge set private.
Theorem 4.3. Algorithm 1 is E-edge set LDP.
Proof. Algorithm with the neighbor selection described in Algorithm 3 is a randomized mechanism based on RR: we denote as M. The proof follows from the DP of RR (see, e.g.: Qin et al. 2017). Denote with Pr[u + u] the probability that node v gets replaced by node u, let p e=+1 be the probability of node replacement according to RR, and q p- Note that b (u/,...,u')) be two neighbor sets which differ in only one element; assuine, without loss of generality, that v1 + v1. Then, given any outpul {.,,..., 82) of M, it holds that:
0 implies g p. Let b (U.,..., vd):
Pr(M(() 8]
Pr(mi + 81] ... Pr(ce + 82l
Pr(ui + 81] < = Pr(u - 81] D
Pr[M(b]) s] Pr|c 81] .....Po'P,, 7 sal
With analogous reasoning (see, e.g., Wang et al. 2016). one can show that Algorithm selection described in Algorithm& is e-ddge set private.
with the neighbor
4.3 Feature and label privacy
In addition to edge privacy, GraphPrivatizer also ensures feature and label LDP. That is, for each node, GraphPrivatizer ensures that an attacker cannot confidently infer the feature vector or the label. Specifically, we make use of the Drop algorithm introduced in Sajadmanesh Gatica-Perez (021), which enables efficient LDP GNN training with both private labels and node Teatures. Features are privatized with a multi-bil mechanism, which allows individual nodes perturb their features before communicating them. Labels are, instead, privatized using RR: node's class is randomly replaced with one of the other available classes with the samn approach described in Equation (6) We refer the reader to the original publication for more details. We assign a privacy budget for feature privacy and cy for label privacy.
4.4 Complete architecture
Figure 2 summarizes the complete approach: GraphPrivatiize produces perturbed features X', edges E', and labels Y', which are then shared with server to train GNN. In particular, Figure 2 schematically shows which components of GraphPrivatizer have access to the inperturbed, private data.
Theorem 4.4. GruphPrioatizer is + + by LDP
Proof. The private feature vectors are only used by the multi-bit mechanism, the private labels are only used by the RR mechanism for labels, and the private edge information is only used by Algorithm I In particular, Algorithm 1 only post-processos the privatized feature vectors and, due to the composition and robustness to post procesrocessing properties of DP DDwork et al. 2014), GraphPrivatizer is thus c c cu + cy LDP.
5 Experiments
In this section, we empirically investigatd" the performance of GraphPrivatizer and assess the trade-off between edge privacy and GNN accuracy node classification tasks across several datasets. In particular, we (i) compare our approach against the bascline described in Section 5.1 and (ii) analyze the effects of the
Code available (ntthubbcom//mmm/////sssannnaan

---

Published in Transactions on Machine Learning Research (09/2024)
Multi Mechonism
Train GNN
o (0)
Nodes similar to E .f(()
Rondomized Response
.1())
Our Contribution
Randomized Response
%
User-aide
Server-side
Figure 2:
Scheme of GraphPrivatiizer and how it acts on the features, edges, and labels of a node v. The shaded area highlights our contribution and where the algorithms we propose are utilized.
parameters a and on the privacy-accuraatt trade-off for GraphPrivatizer. With respect to this trade-off, as discussed in [Section 4.2) we use the setting a = ô = as our reference and perform comparisons with a, > 0 to evaluate the benefits of higher thresholds and aggregation a coefficients. We empirically evaluate the edge privacy of approach against attacks that try to recover the private edges. We use variety of GNN architectures that include traditional convolutional GNNs, graph attention networks, and transformer networks, and perform experiments on the most commonly used benchmark datascts for node classification that include citation, co-purchase, and social networks. We experiment with GCN (Kipf & Welling 2017). GraphSAGE (Hamilton et al. 2017), GAT (Velččkovćć et al. 2018), GT (a graph transformer adapted from Shi et al. (2021)), GATv2 (Brody et al. 2022) and GraphConv (the graph convolution operator introduced in Morris et al. 2019 ) on the Cora (Yang et al.) 2016). Pubmed (Yang et al.) 2016), LastFM (Rozemberczki & Sarkar 2020). Facebook (Rozemberczki et al. 2021 and Amazon Photo (Shehur et al.. 2018) datasets. In what follows, we will take the feature privacy budget C2 and label privacy budgets cy to be fixed: the results and discussion will therefore focus on the edge privacy parameter which is simply referred to privacy budget. We leave additional details on hyper-parameters and on the datasets used to Appendix A
With regard to the privacy attack, we assume the trained GNN exposes an inference API that an attacker can query. We assume the attacker possesses feature information on pairs of nodes and wishes to determine whether an edge connects each pair of nodes. should be noted that, according to the data model we adopt and describe in [Section 3.4 no entily, either users or server, possesses noise-free information about other nodes' features. For this reason, we assume that the attacker itself may only have access to the noisy feature vector that a node sends to the server for, e.g., training. With these assumptions, we attack all models with LinkTeller (Wu et al. 2022) except for the GraphSAGE, which we attack with LSA2 (He let al. 2021 Wu et al.) 2022). For Link we use the default inffuence and graph density parameters of 0.001 and 1 (Wu et al. 2022). In all cases, we randomly sample 500 pairs of nodes that are connected in the original, unperturbed graph, as well as 500 pairs of nodes that are not connected the original, unperturbed graph. The lask of the allacker is to decide which of these nodes are connected or not connected, in a binary classification problem. We evaluate the performance of the attacker using the AUC, which report multiplied by a factor 102, that is, AUC E [0, 100). LinkTeller is a threshold-based binary classifier, so we use the AUC as a performance measure to capture all threshold values. A higher AUC denotes a higher ability of the attack to correctly identify the edges of the graph, and thus lower edge privacy, where an increase of AUC point can be interpreted as a 1% increase in the likelihood of correctly identifying edges. should be noted that the attacker has access to the API of a GNN which was trained on perturbed data, while we evaluate the attack AUC with respect to the original unperturbed data, which is what should be protected.
5.1 Comparison against baseline approaches
We compare GraphPrivatizer against a baseline approach adapted from existing literature on private node classification. Specifically the baseline approach adapted from (aajammanssh & Gatica-Perez (2021) and Wu et al. (2022) to our setting. Specifically, for the bascline we consider a slightly relaxation of the setting described in Figure aand assume that each node has access to the list of nodes in its 2-hop neighborhood. We
9

---

Published in Transactions on Machine Learning Research (09/2024)
then apply randomized response with privacy budget to this list, thus perturbing the 2-hop neighborhood of the node. This approach corresponds to local version of the EdgeRand approach described in [u let al. (2022) and applied to each node. These adaptations are necessary as the original algorithms assume access to the full adjacency matrix which is not compatible with our local privacy setting. A very similar approach is also used in Joshi & Mishra (2023), who apply RR to 2-hop neighborhoods as well. We refer to this baseline simply as a randomized response baseline and denote it with RR. The bascline approach does not, in general, preserve the degree of the nodes and thus the sparsity of the adjacency matrix of the graph. Additionally, no form of threshold or aggregation is considered for the baseline. We highlight that the baseline approach assumes that nodes have access to the list of nodes in the entire 2-hop neighborhood, while GraphPrivatizer operates with the more strict (and private) condition that only immediate neighbors are known. Our experiments show that, despite this more striet setting, GraphPrivat izer outperforms the baseline in terms of accuracy with comparable privacy and thus offers a better privacy-utilityy trade-off. We additionally compare our results with LPGNN (Sajadmanesh & Gatica-Porez 2021). which is mirrored by our experiments with do where no edge privacy is guaranleed. For all comparisons we set the threshold and aggregation parameters for GraphPrivatizer to d 0 and 0.5 respectively. With reference to the results in [Section 5.2] 8- = 0 ensures the best privacy as it imposes no threshold during the neighborhood perturbation, while a = 0.5 corresponds to an intermediate amount of aggregation which provides good accuracy without sacrificing privacy. Refer to Section 5.2 for more details on the effects of a and 8.
We present the results of our comparison between GraphPrivatizer (GP) and the RR baseline in Table our approach is better in terms of accuracy without sacrificing privacy across all datasets. We performed statistical testing using paired Wilcoxon signed rank test to compare the accuracy and privacy of our approach against the bascline across all privacy budgets, and report the p-values P in Table la For accuracy, we tested the null hypothesis Ho: ACcop ACCER 0 and found that GraphPrivatizeer has higher accuracy across all datasets with statistical significance. For attack performance, we tested the null hypothesis Ho: AUCor - AUCRR = 0 and found that there is no statistically significant difference in the privacy of our approach and the RR baseline across all datasets. In [Table 1b we use GAP to denote the utility gap, i.e., the accuracy loss with respect to the non-edge-private, = oc setting correspouding to LPGNN (Sajadmaneshi & Gatica-Perez, 2021). While the paa--ddeppivvatee setting is expected to provide better accuracy than the edge-private one, we are interested in evaluating how closely GraphPrivatizer and RR can match its accuracy while providing edge privacy. We report results for é = 0.1 and find that GraphPrivatice Privatizer narrows the utility gap when compared to the RR baseline across all datasets.
Table 1: Aggregate results across models for GraphPrivatizer (GP) and a randomized response (RR) bascline. For GraphPrivatizer, we report results for a = 0.5 and J = 0. Sub-table (a) reports the average improvement in accuracy of GraphPrivatizer over the baseline as well as the average difference in attack performance between GraphPrivatizer and the baseline across all models and privacy budgets. We report p-values P for a paired Wilcoxon signed rank test, testing respectively the null hypotheses Ho: Accep ACCRR = 0 and Ho: AUCGP - AUCRR 0. In sub-table (b) GAP denotes the utility gap, i.e., the accuracy loss with respect. to the non-odge-private, co setting corresponding to LPGNN (Sajadmanesh & Gatica-Perez 2021 where
we report aggregate results across models as (mean + standard deviation), for e e 0.1.
(a) Accuracy and AUC results across all privacy budgels.
(b) Utility gap (GAP) for e = 0.1.
dataset
Accop ACcRR
AUCpP AUCRR
dataset
GAPcP
GAPRR
Cora
3.9 (Px (o00001)
0.2 (P).00)
Cora
6.3 + 2.2
12.4 6.3
LastPM
10.1 (Pc.001)
(PS.00)
LastFM
6.3 3.2
21.7 4 13.8
PubMed
0.8 (Pc..00))
2.7 (P>-05)
PubMed
0.2
2.7 1.7
Pacebook
5.0 (Px..00)
0.6 (P> 00)
Facebook
5.0
1.218855
Amazon Photo
5.5 (Pc..0))
3.9 (P>.00)
Amazon Photo
3.4 3.412.7 2.7
8.0
Across all models and dalasets, GraphPrivatizer providdd an average 6.6 AUC points improvement in privacy with respect to the man-edg--rrivate LPGNN (Sajadmanesh & 4.9% decrcase in accuracy, while the RR bascline provides a similar 6.4 AUC points improvement in privacy but with a much less desirable 12.5% decrease in accuracy. Overall, GraphPrivatizer achieves thus a better privacy-utility trade-off than RR. Additional results in Appendix C
2021) setting while suffering a
10

---

Published in Transactions on Machine Learning Research (09/2024)
5.2 Results for GraphPrivatiier and discussion
While in [Section 5.1 we show that GraphPrivatizer outperforms the RR baseline approach and improves upon the privacy-utility trade-off, here we investigate our approach in more detail and determine to which degree the use of thresholds and aggregations described in Section 4 is beneficial. We are interested in establishing if positive threshold and aggregation parameters (i.c., a, 5 > 0) consistently provide a better privacy-utility trade-off than the reference case where no aggregation or threshold are considered (i.e., a = 0
Table 2: Aggregate results for GraphPrivatizer. We denote as ACcep and AUCGP the average accuracy and AUC results for GraphPrivatizer with a, values of and 8. We denote with Acco the average accuracy difference with the 8 = case across all tested values of a and larger than zero, where positive values of Acce indicate that GraphPrivatizer performs better when some thresholds are applied and/or aggregation is performed during the neighbor perturbation. Analogously, we denote with Âxue the average AUCx10² difference, where values close to zero indicate that GraphPrrvvaizerr offers the same protection against privacy attack when introducing a positive threshold and/or feature aggregation during the neighbor perturbation. We denote the datasets we Cora. (Cr), FM (FM), PubMed (PM), Facebook (Fb), and Amazon Photo (Ph). Results reported as (average values + standard deviation), for 0.1.
where the average taken across all positive tested
GP-t
GP-m
Model Dataset
AccCp
AUCCP
A
AAUC
Model
Dataset
ACcCP
AUCgP
A
AXUC
78.0 + 1.7
92 +1
7
3#4
Cr
78.9
1.8
73 +
3
0 0+ 3
FM
81.1 3.9
57 2
3
3
FM
82.1
3.0
57
2+
1
GAT
GAT
PM
$2.0
70
1.5 0.7
4
PM
82.1 0.3
72
1.5 0.7
0
Fb
8.7
63
4
2
Fb 0.7
64
2+1
0
Ph
83.3
4
11:5
9
Ph
85.9
81
0.5
0
Cr
1.1
7245
412
815
Cr 1.
9.1
412
513
FM
8.7
90
3+1
10
FM
8.4
92
3+1
543
GCN
GCN
PM
0.3
9611
1.7
1025
PM
0.3
97
1.7
2
9.2
9611
412
613
Fb 9.2
98
1.5
211
81
95
1317
313
Ph
3.8
96
1.2
2
Cr 1.0
78
4
5+3
Cr 80.4
77
4
3
FM 83.5
85
3
111
FM
+ 1.3
84
3
1
SAGE
SAGE
PM 0.3
56
1.7
0+1
PM
8.6
5543
1.5
0
Fb 9.2
02
4
4=2
Fb 9.2
74
2
1
Ph
83.4 0.6
25
13
17
Ph
86.1 3.5
90
0.6
8
We present an aggregate overview of our results Table 2 We focus here on the case = 0.1 and on the GCN, GraphSAGE, and GAT models, with additional results available in Appendix C GraphPrivatizer consistently performs better with a, 8 0 in terms of accuracy, it provides a positive accuracy improvement A in almost the totality of cases. In more than half of the cases, it also provides performance in defending against privacy attacks which is equivalent to the a = 8 = 0 setting, having ÁAUC which overlaps with zero. It should moreover be noted that the AAUC results reported in Table 2 are, as mentioned, multiplied by a factor 102. For this reason, most of the cases where AAUC > correspond to only a small decrease in privacy, with the majority of cases reporting AAUC S 2 which indicates an increase the likelihood that the attacker able to correctly identify edges of at most 2%. That is, it is on average preferable to introduce feature aggregation and/or to threshold to select similar neighbors during the neighbor perturbation. If we compare the different models tested, GCN appears to be more prone to worse performance against privacy attacks. This behavior is consistent with the observations reported in Wu et al. (2022) and may be explained by highlighting how the influence compulation that underlies the Link Teller allack is better suited for graph convolution aggregations, and thus for GCNs (more details on Wu et al. (2022) ). While information propagation between nodes can be exploited for other GNN architecture the introduction of, e.g., the attention mechanism in GAT HAT/GATVV /ATT22 can negatively impact the attack performance. Nevertheless, Table and Table 2 show that GriphPrivatizer performs well for different GNN models and datasets.
11

---

Published in Transactions on Machine Learning Research (09/2024)
While Table 2 shows that the setting a, 8 > 0 is generally preferable when considering averaged results across all values of and 6, a more detailed analysis shows that, depending on the model and the dataset, specific combinations of a and ò provide the best performance. We report here more detailed results for GP-t with GAT, leaving additional results in Appondix C
Cara
LastFM
PubMed
Facebook
Amazon Photo
7.7
8
9
9-0
8-9
3.0
7.0
6.3
6.9
8.7
0.8
19
200
19
19
366
54
55
55
522
06
14.7
14.7 14.7
14.8
29
10
7.4
10
E.
10
14.7
5
0:2
3.3
9.3
0.6
7.3
88
0.3
-01
18
2.8
19
-03
3.0
41
3.5
5.
235
24.7
14.3
14.0
00
925
3.5
4.5
7.1
4.1
6.0
0.6
7.1
4.4
0.4
4.7
-0.1
1.5
3.9
19
2.0
623
02
1.0
3.8
53
5.
635
0.3
10.4
14.
14.7
14.0
344
8.7
9.5
4.
0.0
1.4
3.9
199
1.7
311
5.0
143
146
0.0
0.1
0.25
0.5
1.0
0.0
9.1
0.23
1.0
0.0
0.1
0.25
0.5
100
0.0
0.1
0.25
0.5
1.
0.0
01
0.2
0.5
100
della
0eRa
duta
(a) Acc for different values of a and 8. Higher is better.
LastFM
PubMed
Facebook
3:2
5.5
2.0
4.2
3
5.5
23
25
27
2.0
84
7.9
9.6
15.5
7.75
-3.4
64
4.7
5:3
7.2
0255 05 0.75
0.5
2.4
4.2
4.
377
0.7
1.
377
34
5-1
0.6
4.7
24
27
2.3
13
87
8.0
611
15.0
0,25 0.5
1.9
50
3.5
43
5.9
6.0
MORE
033 00
277
24
7.4
15.5
0.000
1.6
3.6
5.3
5.5
37
2.0
033
10.4
12.6
5.
3.9
5.2
7.1
0.0
1.7
19
2.2
3.7
8-
0.0
2.0
2.2
4.2
5.6
0.
0.0
-0.3
3.2
4.3
22
3-
0.00
22
24.0
11.2
15.2
1.0
0.25 della
0.5
1.b
0.1
0.2
0.5 deta
05
100
01
025
deta
(b) AAUC for different values of a and 6. Smaller is better.
Figure 3: Results for GP-t with GAT, for = 0.1. Average values across 10 runs. The colormap is normalized to interpret all Ace 0 and AAUC S 2 desirable.
Figure 3 exemplifies the trade-off between improvements in model accuracy, and a decrease in edge privacy for all combinations of a and 8, with the combination a = 8 == representing the reference base case. Model accuracy tends to increase with larger values of a and 5, while privacy tends to decrease. In fact, a higher threshold 8 implies that fewer nodes may be selected as candidate replacements during perturbation, with 5 = 1 requiring that only nodes with similarity of may be considered. With respect to the aggregation parameter a, values larger than zero tend to provide increased accuracy for small 6. This suggests that, when computing similarities, it is beneficial to do so on aggregate features: in this way, nodes which behave similarly with respect to the output of the AcCREGATE function (Section 3.1), h, which is then used to train the GNN, will be favoured as candidates for replacement.
Small values of a and provide therefore a good trade-off between model accuracy and privacy, with some combinations remarkably offering both improved accuracy and better privacy over the 8 0 case. For instance, the combination 0.8% improvement in edge privacy. Considering the additional visualizations provided on Appendix C. this behavior generally holds across datasets, for both GP-t and GP-m. Even for GCN (see for instance Table 3b where average results show an unfavorable AAUC > 0, specific combinations of a and ō can provide accuracy improvements over the a = 8 = 0 case at a small or mull privacy cost.
0.5, 8 = 0.1 for Cora offers 5.4% improvement in accuracy and a
Finally, we consider what the benefits of GraphPrivatizer are across the range of privacy budgets we tested. We focus here on GP-t on LastFM for GCN: [Tbll 2 shows for this case decrease in protection against privacy attacks corresponding to relatively large AAUC 10 + 5 when introducing positive a or 6.
Analyzing this case more in detail, Table 3a shows that, as previously observed, on average GraphPrivatizer entails a 10% increase in the attack performance for this specific experiment for positive thresholds or aggregation coefficients. Nevertheless, ACcep for e = 0.1 is close to that of the non private model for == oc, despite having a smaller AUC. More detail, when compared to GraphPrivatizer for c c= 0.1, the no aggregations and no thresholds achieve a better accuracy only for c == 8, but with a worse AUC. That is, on average, GraphPrivatizer with threshold and feature aggregation provides a better trade-off bet
12

---

Published in Transactions on Machine Learning Research (09/2024)
Table 3: Accuracy and AUC across different values of e. We denote as with the subscript GP the average results for GraphPrivatizer across a, 0 O, while the subscript b denotes the base case a 8
(a) GCN on Last with GP-t. Average across a, 8.
(b) GCN on LastFM with GP-t. a == 0.75, 8
AAce
Accap
Acc;
AUCap
AUCb
Acc
Accgp
Acc,
AUCop
AUCb
0.1
3.2 = 1.0
85.7 + 1.5
82.6
90 5
80
0.1
0.4
83.0
82.6
80
81
1.7 + 1.0
1.1
84.2
92 =
84
1
1.1
84.1
83.0
85
85
2
1.7
+ 1.0
0.7
84.5
93 2
89
2
0.6
85.1
84.5
89
89
8
0.1
0.0
8.1
86.4
94 14
94
8
0.2
86.6
86.4
94
95
0
0.0
8.0
86.5
94
94
80
0
86.6
86.6
95
95
accuracy and privacy. Furthermore, the improvement is more evident for specific values of a and ō: for instance, Table 3b shows that for e 0.1, a = 0.75 and = 0, provide both 0.4% improvement in accuracy and a 1% improvement in AUC. Similarly, higher privacy budgets are still favorable to GraphPrivatizer with a, 5 > 0 which always outperforms the a = 5 = 0 case at a smaller or equal AUC.
Considering existing results available in literature, Sajadmanesh et al. (0223) perform experiments on the Facebook dataset and obtain an accuracy of 76.3 + 0.21 for a total privacy budget of 4. This result is, however, not directly comparable to ours as it considers different privacy setting (global vs local privacy) and assumes access to the adjacency matrix. Closer to our approach is that of Joshi & Mishra (2023) who train an eDge-LDP GNN where nodes have noiseless access to part of the adjacency matrix: despite the less strict privacy setting, they obtain worse accuracy and report a best accuracy of x 50 on Cora, = 70 on LastFM, and x 70 on PubMed, while not testing the effectiveness of their method against privacy attacks that try recover the edges. Their approach is, indeed, very similar to the one we adopt in [Section 5.1 as baseline which we have shown is consistently outperformed by our method and provides generally worse privacy-utility trade-off across all datasets.
6 Conclusions
Motivated by real-world applications, we investigated LDP GNNs. Considering a local privacy setting where the individual nodes of the graph can only have noiso-free access to their features, labels, and edges, we (i) introduced a new definition of LDP for our local privacy setting, (ii) proposed our private algorithm GraphPrivatizer, and (iii) empirically validated its performance on real-world datasets and against privacy attacks. GraphPrivatizer is fully private algorithm that protects edges, features, and labels. We introduced a new methodology to protect edges by means of controlled perturbations which replace the neighbors of a node with other similar nodes according to some similarity measure. We furthermore evaluated the impact of thresholds on the similarity between the original and the perturbed neighbor nodes and of feature aggregation in computing the similarity scores, finding that positive threshold and aggregation cocfficient provide the best privacy-utilits trade-off. Compared to existing approaches which do not provide edge- privacy (Sajadmanesh & Gatica-Perez 2021 or do so while requiring central entity to have complete information about the edges of the graph (Sajadmanesh et al.) 2023 Joshi & Mishra 2022). GraphPrivatizer provides LDP without requiring a trusted entity to have access to the adjacency matrix of the graph and is applicable to a variety of GNN models.
Future work could focus on addressing some of the limitations of GraphPrivatizer. First, GraphPrivatizer does not consider datasets containing edge features. While it could be possible to, e.g., privatize categorical edge features using randomized response, our local privacy setting would need to be adapted to determine which entity can have noisc-free access to the edge features. Additionally, better personalized user privacy requirements could be considered. In particular, the introduction of a notion of brust between nodes could allow two neighboring nodes that trust each other to exchange less noisy information, thus improving the GNN performance. Finally, while GraphPrivatizer is generally applicable to various types of GNN models, odge perturbations which are tailored to specific GNN architecture can possibly provide a better privacy- utility trade-off and could therefore be explored in future work.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Acknowledgments
We would like to thank Prof. Thomas Gärtner (TU Wien) for his helpful comments on the manuscript. This work was funded part by the TU Wien DK SecInt and by the Austrian Science Fund (FWF), project NanOX-ML (6728). The computational results presented have been achieved in part using the Vienna Scientific Cluster (VSC) and RIN00..
References
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Nya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference compuler and commanications security, pp. 308-318, 2016.
Morgane Ayle, Jan Schuchardt, Lukas Gosch, Daniel Zügner, and Stephan Günnemann. Training differ- entially private graph neural networks with random walk sampling. In Workshop Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022, 2022.
Adrien Benamira, Benjamin Devillers, Etienne Lesot, Ayush K Ray, Manal Saadi, and Fragkiskos D Malliaros. Semi-supervvsed learning and graph neural networks for fake news detection. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 568 569, 2019.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive graph attention networks? In International Conference on Learning Representations, 2022. URL
Graham Cormode, Somesh Jha, Tejas Kulkarni, Ninghui Li, Divesh Srivastava, and Tianhao Wang. Privacy at scale: Local differential privacy in practice. In Proceedings of the 2018 International Conference Managementt of Dala, pp. 1655 1658, 2018.
Cyuthia Dwork. Differential privacy. In Automato, Languages and Programming: 33rd International Collo- quium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II 39, pp. 1-12. Springer, 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of diffcrential privacy. Foundations and Trendso in Theoretical Computer Science, 9(3 4):211-4400 2014.
Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy BR Hayter, Richard Vickers, Charles Roberts, Jian Tang, al. Utilizing graph machine learning within drug discovery and development. Briefings in bioinformatics, bbbbbbbbb,,59, 2021.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances neural information processing systems, 30, 2017.
Xinlei He, Jinyuan Jia, Michael Backes, Neil Zhenqiang Gong, and Yang Zhang. Stealing links from graph neural networks. In 30th USENIX Security Symposium (USENIX Security 21), pp. 2669 2686, 2021.
Seira Hidano and Takao Murakami. Degree-preserving randomized response for graph neural networks under local differential privacy. arXiv preprint arXiv:2202.1000 10209, 2022.
Roshni G Iyer, Wei Wang, and Yizhou Sun. Bi-level attention graph neural networks. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 1126-1131. IEEE, 2021.
Rucha Bhalchandra Joshi and Subhankar Mishra. Edgo-level privacy in graph neural networks. In 18th International Workshop on Mining and Learning with Graphs, 2022.
Rucha Bhalchandra Joshi and Subhankar Mishra. Locally and structurally private graph neural networks. Digital Threats: Research and Practice, 2023.
Shiva Prasad Kasiviswanathan, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography: 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings, pp- 157-476. Springer, 2013.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Represenlations, 2017.
Jaewoo Lee and Chris Clifton. How Much Is Enough? Choosing e for Differential Privacy. In Xuejia Lai, Jianying Zhou, and Hui Li (ods.), Information Security, Lecture Notes in Computer Science, pp. 325-340) Berlin, Heidelberg, 2011. Springer. ISBN 978-3-642-2486144 doi: 10.1007 (-29999-------88888
22.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings 2019.
of the AAAI conference on artificial intelligence, volume 33, pp.
Tamara T Mueller, Johannes C Paetzold, Chinmay Prabhakar, Dmitri Usynin, Daniel Rueckert, and Geor- gios Kaissis. Differentially private graph classification with gnns. arXiv preprint ar 0rXiv2202.025 2022a.
Tamara T Mueller, Dmitrii Usynin, Johannos C Pactzold, Daniel Rucckert, and Georgios Kaissis. Sok: Differential privacy on graph-structured data. arviv preprint ar Xiv:22203 09205, 2022b.
Iyiola Emmanuel Olatunji, Thorben Funke, and Megha Khosla. Relcasing graph neural networks with differential privacy guarantees. Transactions on Machine Learning Reseurch, 2023.
Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decentralized social graphs with local differential privacy. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 425 438, 2017.
Sofya Raskhodnikova and Adam Smith. Differentially private analysis of graphs. Encyclopedia of Algorithmss 2016.
Benedek Rozemberezki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management, 2020.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, cnnab44,,, 2021.
Sina Sajadmanesh and Daniel Gatica-Perez Locally private graph neural networks. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp.
2021.
Sina Sajadmanesh, Ali Shahin Shamsabadi, Aurélien Bellet, and Daniel Gatica-Perez. Gap: Differentially private graph neural networks with aggregation perturbation. In USENIX Security 2023-32nd USENIX Security Symposium, 2023.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, (011)8 2008.
Oleksandr Shihur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint Xiv: 05868, 2018
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. Masked label predic- tion: Unified message passing model for semi seni-supervised classification. In Zhi-Hua Zhou (ed.), Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pp. 1548 1554. ijcai.org, 2021. doi: URL https:///oi. org/ 10. 14963/ijjaa.. 2021/214
Haipei Sun, Xiaokui Xiao, Issa Khalil, Yin Yang, Zhan Qin, Hui Wang, and Ting Yu. Analyzing subgraph statistics from extended local views with decentralized differential privacy. In Proceedings of the 2019 ACM SIGSAC Conference on Compuler and Communications Securily, pp. 703 717, 2019.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Represendations, 2018
15

---

Published in Transactions on Machine Learning Research (09/2024)
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The world wide web conference, pp- 2022 2022-2032, 2019.
Yue Wang, Xintao Wu, and Donghui Hu. Using randomized response for differential privacy preserving data collection. In EDBT/ICDT Workshops, volume 1558, pp. 0090-6770 0790-6778, 2016.
Stanley Warner. Randomized response: survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63 69, 1965.
Fan Wu, Yunhui Long, Ce Zhang, and Bo Li. Linkteller: Recovering private edges from graph neural networks via influence analysis. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 2005 2024.
IEEE, 2022.
Mengmeng Yang, Lingjuan Lyu, Jun Zhao, Tianqing Zhu, and Kwok-Yan Lam. Local diffcrential privacy and its applications: A comprehensive survey. arXiv preprinl ar Xiv:2000 03686, 2020.
Mengmeng Yang, Taolin Guo, Tianqing Zhu, Ivan Tjuawinata, Jun Zhao, and Kwok- Yan Lam. Local differential privacy and its applications: A comprehensive survey. Computer Standards & Interfaces, pp. 103827, 2023.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40 48. PMLR, 2016.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Macicjewski. Graph convolutional networks: a comprchensive review. Compulational Social Networks, 6(1):1 23, 2019.
Zaixi Zhang, Qi Liu, Zhenya Huang, Hao Wang, Chengqiang Lu, Chuanren Liu, and Enhong Chen. Graphmi: Extracting private graph data from graph neural networks. In Zhi-Hua Zhou (ed.), Proceedings of the Thirticth International Joint Conference on Artificial Intelligence, IJCAT-21, pp.
International Joint Conferences on Artificial Intelligence Organization, 8 2021. doi: 10.24963 /a//3//jjaai.102 2021//66
URL
https://doi.org
24963/ijcai. 2021/516 Main Track.
Zhikun Zhang, Min Chen, Michael Backes, Yun Shen, and Yang Zhang. Inference attacks against graph neural networks. In 31st USENIX Securily Symposium (USENIX Security 22), pp.
2022.
16

---

Published in Transactions on Machine Learning Research (09/2024)
A Experimental details
For all experiments, we divide our datasct with 50:25:25 train:validation:test set ratios, similarly to Sajad- manesh & Patica-PPrre (2021). We train all the models for 100 epochs, with learning rate 10-2, weight decay 10-3 and dropout rate 0.5. We run experiments with edge privacy budget = 10.1, 2, 8, x): a = {0, 0.25, 0.5, 0.75, 1.0), and = {0, 0.1, 0.25,,2222.0 0.5, 1}. We perform 10 runs for each value of e, a and with different seeds and consider average results. We perform label and feature perturbations as described in Section 4.3 with privacy budgets fixed at. ex = and ey 3. Additionally, we set. the KProp hyper- parameters in the Drop algorithm to the best values described in [Sajadmanesh & Gatica-Perez (0021 :: we use K2 16, Ky 2 for Cora, Kr 4, Ky 2 for Facebook, and K₂ 16, Ky 0 for LastPM and PubMed. After a grid-search tuning, we use K 4, Ky = 2 for Amazon Photo.
Table 4: Statistics of the datasets. Cora and PubMed Yang et al. (2016) are citation networks where an edge (i.j) exists between two documents if document i cites document, j, and features consist of bag-of- words representations of the documents. Classes consist of document categories. Facebook Rozemberczki ct al. 2021) is page-page graph of verified Facebook pages, where nodes correspond to official Facebook pages and edges correspond to mutual likes between pages. Node features are extracted from the site descriptions and the classes correspond to various page categories. LastFM Rozemberczki & Sarkar (2020)
is a friendship graph of LastFM users where nodes represent users and edges friendships between users. The classes correspond to the home countrics of the users. Amazon Photo (Shchur et al. 2018 is co-purchase network where nodes represent goods and edges correspond to two goods which have been frequently bought together Amazon. The features consist of bag-of-wordh representations of the goods and the classes correspond to product categories.
Datasct
Classes
Nodes
Edges
Features
Avg. Degree
Cora (Cr)
7
2708
5278
1433
3.90
LastFM (FM)
10
7083
25814
7842
7.29
PubMed (PM)
3
19717
44324
500
4.50
Facebook (Fb)
4
22470
170912
4714
15.21
Amazon Photo (Ph)
8
7650
238162
745
31.13
B Similarity metric
The performance of GraphPrivatizer is affected by the choice of similarity measure in Algorithm Non- parametric and non-learnable similarity measures are desirable in our local privacy setting, as they do not require access to data. We compare the cosine similarity with the Euclidean distance, and find that the cosine similarity is preferable. Refer to Section 5 for details on how privacy altacks are performed.
Table 5: We denote with Ase the average accuracy difference between results obtained with the cosine similarity and with the Euclidean distance. Analogously, denote with AAUC the average AUC x 102 difference. Results reported (average + standard deviation), for = 0.1 across 5 runs. The cosine similarity is preferable as it provides better accuracy AAce 0) with comparable privacy (AAuc x 0).
Dataset
AAco
AAUC
Cora
4.8 + 1.2
2 + 3
Facebook
1.6 0.5
1
LastFM
2.4
1+1
Amazon Photo
-0.9
-1 10
Pubmed
2.3
3
17

---

Published in Transactions on Machine Learning Research (09/2024)
C Additional results
C.1
Comparison against the RR baseline
Table 6: Results on all datasets for GraphPrivatiin and the RR baseline discussed in Section 5.1 subscript denotes the sal--ddge--ivaattt results.
The
Datasct
Model
A
AAUC
Accer
ACeRR
AUCgr
AUC
Accoo
AUC,o
GAT
3.2
-1.1
71.9
68.8 5.4
65.0 4.8
66.0 7.9
80.0 1.7
78.5 6.9
GATv2
1.2
2.3
69.8 2.3
2.8
3.1
79.7
2.0
6..6
GCN
3.1
-8.8
75.7
1.0
72.6 2.4
8.9
9.0
81.7 1.0
9.97
Cora
GConv
22.2
5.8
11.1
48.9
56.6 1.3
50.8
+
53.9 1.4
GT
3.4
4.1
71. 2.9
68.3 2.6
0.9
53.8 0.8
79.2 2.8
62.3 1.3+111
SAGE
3.4
-5.1
77.0 1.0
73.6 2.1
3.3
77.1 2.8
81.8
79.3
GAT
4.2
5.1
0.9
0.5
55.7 6.7
9.6
64.6
GATv2
3.4
0..7
1.00
1.1
1.77
3.54
88.6
61.3
GCN
5.9
1.6
8.3
80.6
91.3
9.1911111
91.9
99.1
Pacebook
GConv
26.7
2.3
0.8
8.89
52.4
5..1
8..5
0.51
GT
3.9
1.5
86.7 0.5
8.4
03.8
52.2
91.7
60.3
SAGE
5.3
-0.8
87.0 0.2
8.47
2.07
3.5
9.2
74.7 2.3
GAT
24.2
75.7 3.2
51.5 14.8
1.2
51.
3.3
2.2
GATv2
9.8
1.5
68.9 8.9
59.1
0.7
0.7
7.3
55.4 1.2
GCN
3.3
5.9
82.2 1.9
1.3
81.7
87.6
8.3
94.8 1 1.9
LastPM
GConv
42.3
2.8
65.2 6.9
22.9
1.79
50.1
60.8
51.8 1 1.6
GT
8.1
3.4
4.4
60.9
0.7
5.35
79.1
59.3 1 1.6
SAGE
4.8
-1.2
1.7
2.47
8.5
84.0
8..0
86.1 2.4
GAT
8.44
7.49
3.87
6.
0.2
3.6
GATv2
8..7
0.3
2.5
3.2
0.2
6.70
GCN
-12.3
80.6
8..3
8..7
0.5
0.3
9.72
PubMed
GConv
3.9
20.5
79.8
1.3
713
50.7
0.5
2.2
GT
0.7
7.7
80.0
8.47
0.5
5.6
0.3
6..3
SAGE
0.1
1.5
80.3 + 0.3
0.5
3.1
58.4
0.2
1.76
GAT
11.6
3.5
80.2 1.1
3.49
61.3 4.0
0.6
84.6
GATv2
9.0
0.5
4.2
6.7
1.
8..0
76.8
Amazon Photo
GCN
8.1
8.5
1.7
95.1
91.4
80.8
96.3
GConv
-3.6
-0.7
55.7 10.1
59.3 1.3
1.6
2.14
18.9
1.3
GT
7.3
12.1
8.66
2.
6.0
3.74
8.33
87
SAGE
9.5
-11.8
0.4
76.5
7.1
90.6
0.2
93.8 1 1.0
18

---

Published in Transactions on Machine Learning Research (09/2024)
C.2 Additional results for the GT, GATv2, and GConv models
Table 7: Aggregate results for GraphPrivatizer for all models. We denote ACcer and AUC the average accuracy and AUC results for GraphPrive Privaieri with a, > 0, where the average is taken across all positive tested values of a and 6. We denote with Acc the average accuracy difference with the = = 0 case across tested values of a and larger than zero, where positive values of Ace indicate that GraphPrivatizer performs better when some thresholds are applied and/or aggregation is performed during the neighbor perturbation. Analogously, we denote with AuC the average AUCx10² difference, where values close zero indicate that GraphPrrivttizer offers the same protection against privacy attack when introducing a positive threshold and/or feature aggregation during the neighbor perturbation. We denote the datasets use Cora. (Cr), LastFM (FM), PubMed (PM), Facebook (Fb), and Amazon Photo (Ph). Results reported as (average values + standard deviation), for e = 0.1.
GP-t
GP-m
Model
Dataset
ACoGP
AUCCP
Acc
AUC
Model
Datasct
ACcGP
AUCgp
AAce
AAtic
Cr
78.0
92 +
7
Cr
1.8
73
3
FM
81.1 1.1#39
37
6
3
FM
82.1
3.0
57
2
GAT
GAT
PM
82.0
5
1.5
4
PM
82.1
72
1.7
Fb 89.5
63
4
2
Fb
90.3
64
2
Ph
1.7
7
11
9
85.9
81
0.5
0+1
Cr 1.17
7245
4
845
Cr 1.14
9.1
412
613
FM
0.7
90
3
10
FM
8.77
92
341
613
GCN
GON
PM
8.3
96
1.7
10#5
PM
0.3
97
1.6
2
Fb 9.24
9611
4
613
Pb 9.2
9811
1.5
211
Ph
814119
95
1317
313
Ph
83.1
96
1.2110
214
Cr
1.07
78
4
5+3
Cr 1.04
77
4#2
3+2
FM
8.
85
3
111
FM
1.3
84
311
1+1
SAGE
SAGE
PM
8.37
56
1.7
0+1
PM
8..
55
1.5
0
Fb 9.
02
4
4+2
Fb 0.2
74
2+1
1
Ph 8.64
25
1
17
Ph 335
90
0.8
8
Cr 1.7
6112
613
342
Cr 14
6211
412
141
FM
1.1
14
31
FM
2.9
5911
311
GT
GT
PM 0.3
64
211
311
PM
0.33
6411
211
Fb 0.3
59
412
512
90.1
59
311
111
Ph 1.3
7814
714
1318
86.2
8114
1.700.
517
Cr 2.2
60
713
412
Cr 1.98
60
512
212
FM
7.18
5411
4#3
211
FM
8.2
65
142
0+1
GATv2
GAIV2
PM
0.4
6144
0.7
342
PM
0.3
65
1.4
411
Fb 1.5
58
4=1
3#2
Fb
8.7
59+4
3#1
2
Ph
81.116
68
1116
717
Ph
82.3 1.6
70.5
212
215
Cr 3.64+
55
4
-211
Cr
3..1
54
1+1
-211
FM
5.7
5241
312
-111
FM
70.0
5312
112
-111
GConv
GConv
PM
8.
7413
1.7
312
PM
1..
7513
1.7
-111
Fb 0.
51
4
-111
Fb
88.1
51
3#1
0
Ph
6.9
51
3=6
011
Ph
71.1
51
5
0
19

---

Published in Transactions on Machine Learning Research (09/2024)
C.3 Results for different privacy budgets
We denote as with the subscript. GP the average results for GraphPrrivalizer across a, > 0, while the subscript denotes the baseline a = 8 0.
Table 8: Results on Cora.
GP-t
GP-m
Model
Accep
Accp
AUCop
AUC,
Aoe
Accep
Accp.
AUCaP
AUC,
0.1
0.2110
79.3
1.4
71.1
74.2
2 2.5
69.2
3.4
79.8 + 1.6
76.4
7188 = 2.7
73.2
75.6
78.3
GAT
2.0
1.911
79.8 0.6
77.8
74.2
2.2
72.5
0.6 0.6
80.7 + 0.4
80.1
74.9 + 2.1
74.9
0.0
80.0
80.6
73.7
2.8
0.04
80.9
81.3
73.6
0.0
8.3
80.2
77.3
77.5
0.0 0.0
81.0
81.0
76.4 1: 1.3
73.3
1.2
0.8
7.00
73.2
1.0
4.6 0.0
79.2 0.3
74.5
61.6 1. 0.8
60.3
2.0 1.0
1.
77.1
61.5 1 0.8
60.1
GATv2
2.0
77.0
79.3
77.4
8.0
0.5
0.5
78.6
62.0 = 0.9
61.3
0.1
7.6
79.1
60.9
1.2
62.2
00
10.200000
79.9 0.3
80.0
62.3
62.6
-0.0 0.0
79.8 0.5
79.8
62.0
62.U
0.1
5.
8.1
75.4
94.8 = 2.4
$3.9
4.9
813
76.4
95.0 = 1.7
88.8
1.
0.5
76.9
8.
GCN
2.0
1.4
8.4
79.8
96.6 = 0.4
92.6
0.9
8..0
81.1
96.8 = 0.4
95.2
8.0
0.1
8.2
80.9
95.7 =
95.9
0.01
8.
81.9
95.9 =
95.9
0.0
8.0
81.7
95.7 1:
95.7
0.0
8.8
81.8
96.2
96.2
1.0
1.0
14
1.1
1.0
4.6
75.8
71.2
54.3 + 0.4
56.7
1.0100
75.2
74.3
54.6 + 0.6
54.9
GConv
0.7
77.0
-.
76.2
8.0
1.1
76.4
75.3
64.2 = 0.4
64.5
0.0
74.8
75.6
64.1 = 0.3
53.6
80
0.0
74.0
74.0
53.9
53.9
0.0
71.0
74.0
53.9
53.9
0.1
0.0
0.5
72.1
62.4 + 0.6
58.3
4.8
7.44
74.6
62.2 + 0.5
60.4
74.3
78.2
GT
2.0
0.7
0.4
76.9
62.1
+ 0.4
60.8
0.4
79.4
79.0
62.6 = 0.6
62.0
0.0
7.5
80.2
62.4
62.6
0.1
79.7
79.6
62.5
1.0
0.6
79.7
62.4 = 0.5
61.9
0.8
79.
78.7
62.2
0.5
62.5
5.3 1.0
80.8
75.5
2.1
72.6
4.5
81.3
76.8
78.6
74.7
1.0
3.4
8.5
77.7
79.5 2 0.5
75.9
1.5
8.4
80.0
79.3 = U.4
78.1
SAGE
81.2
8.0
0.4
0.1
81.1
80.0
2.4 0.4
80.1
-..1
81.5 0.2
81.7
79.6 - 0.5
79.8
00
0.0
81.8 1
81.8
79.3
79.3
0.0
81.8 0.0
81.8
79.3
79.3
20

---

Published in Transactions on Machine Learning Research (09/2024)
Table 9: Results on L.
GP+t
GP-m
Model
Ace
Arcep
Acep
AUCGP
AUC,
Aoe
Accep
Accp.
AUCGp
AUC,
7.4
82.5
75.1
57.9
54.4
3.2
83.1 0.8
56.7
1.0
2.8 1.0
83.3 1: 0.9
80.5
57.6
1 0.5
55.3
2.4.10
82.8
1 0.8
80.4
57.6 1 0.4
57.0
GAT
2.0
1.2 1.0
83.6
82.3
57.7
0.5
56.3
-0.8
83.3
1.1
84.1
57.
58.0
8.0
-1.910
82.8 0.9
84.7
57.8 4 0.4
58.6
2.6
84.1 + 0.8
81.5
58.1 = 0.6
56.9
0c
-0.5 1.0
82.9 0.8
83.5
57.5 1 0.3
57.8
0.4
83.5 1: 0.6
83.1
57.5 1: 0.3
57.6
0.1
4.9
1.9::200
44.6
69.8
54.8 - 0.5
52.6
1.3
77.0 + 1.8
75.7
55.1 + 0.4
54.8
T7.1
70.9
2.0
75.6
77.2
GATv2
2.0
6.0
3.6 3.5
71.9
64.9 = 0.4
53.2
0.4
76.9 + 1.5
76.5
56. = 0.4
55.
2..7
75.6 1.8
77.3
54.8
54.6
1.
76.9 + 1.1
78.6
55.2
54.6
0.2
77.1 0.4
76.9
55.5 +
55.7
0.0
77.1 1:1::00 0.4
77.3
55.5 0.1
55.3
0.9
0.4
82.6
80.8
0.2
86.
83.1
87.4
1.0
2.3
0.2
84.2
94.0 + 1.2
84.7
1.2
86.5
85.3
94.9 + 0.6
90.9
GCN
2.0
2.0
8..5
84.5
94.6
89.2
0.3
86.6
86.2
94.5
94.5
8.0
0.1
0.1
86.4
0.5 94.8
94.7
91.9
0.0
8.1
86.T
91.0 = 0.4
93.5
00
0.0 1: 0.0
86.5 1: 0.O
86.5
94.8
0.0 0.0
86.6 1.61100 0.0
86.6
94.5 1
94.5
0.1
4.0
70.5
66.5
51.9 = 0.2
53.3
1.1
70.4
69.3
52.5 = 0.6
53.7
GConv
2.0
2.4
69.9 1.3
67.5
52.6 + 0.7
52.9
+..
70.0
72.7
52.2 + 0.3
52.8
1.3 1.3+200
69.6 2.2
68.4
69.7
68.5
-
0.0 0.0
66.6 1. 0.0
66.6
51.8
51.8
0.0 0.0.0..00
66.6 0.0
66.6
51.8
51.8
80.3
1.0
6.8 1.8110
80.5 1: 0.8
73.7
59.4 1 0.4
55.4
2.8 1.0
81.0 0.6
78.2
59.1 1 0.4
57.9
5.7
74.2
0.5
80.6 0.5
80.1
8.0
1.0
80.1
81.1
59.3 = 0.3
59.0
1.0
7.9
81.2
58.9 = 0.1
58.8
00
-0.4 0.0
80.3 + 0.5
80.7
58.9
0.2
58.9
-0.4 1.0
80.4 0.6
80.8
58.8
0.2
59.0
0.1
4.6
0..6
80.0
85.9 1.2
$3.7
3.2 1.0
81.9
81.8
85.2 = 0.8
83.2
SAGE
2.0
1.8 0.0
84.6 0.3
82.7
85.7 1 0.8
85.4
1.8 1: 1.0
85.1 0.8
83.4
85.8 1 0.4
85.4
8.0
1.0
8..
85.3
85.7 0.9
83.5
1.2 0.0
85.3 0.5
84.2
85.8
85.1
0.0
8.00
86.0
86.1
86.1
0.0 0.0
0.0
86.0 0.0
86.0
86.1
86.1
21

---

Published in Transactions on Machine Learning Research (09/2024)
Table 10: Results on PubMed.
GP+t
GP-m
Model
Ace
Arcep
Acep
AUCb AUCGP
Accep
Accp.
AUCGP
AUCb
1.90000
0.1
67.3
+
82.4 0.2
1.0
1.4 0.0
82.4 0.1
0.1
81.1
72.4
1.4
65.4
0.7 1: 0.0
82.5 1 0.1
81.8
72.2
+ 1.3
73.8
GAT
2.0
0.8
82.5
81.7
71.8
69.7
0.0 0.0
82.4 0.1
82.4
71.9
69.5
8.0
0.1
0.1
82.4
72.8 4
70.9
0.1
62.5
82.4
72.7
1.3
73.3
oc
-0.0
82.5 0.510.00
82.5
73.0
0.2
73.2
-0.0
82.5 1: 0.0
82.5
73.0
1:
0.3
72.8
0.1
0.6
8.1
80.9
64.5 - 0.6
60.3
1.8
82.5
80.8
65.5 - 0.8
61.7
1.0
81.3
81.9
GATv2
2.0
0.8
0.1
81.7
64.3 = 0.8
62.8
0.4
8.1
82.1
64.9 = 1.4
64.9
0.0
8.1
82.4
05.2
65.3
0.0
8.0
82.6
65.2
66.5
-..1
0.1
82.7
66.2 =
66.2
0.0
8.66
82.6
66.2 = 0.2
66.2
1.8
0.1
80.6
98.5
85.9
1.0
0.1
80.5
1.0
1.0
0.1
81.4
98.9 + 0.5
89.9
0.7 0.0
8.1
81.6
99.1 + 0.2
97.2
GCN
2.0
0.5
8.4
81.9
99.1
94-4
0.0
8.4
82.3
99.1
98.9
8.0
0.1
8.01
82.3
=
99.1
0.1
8.14
82.3
99.1 =
98.8
00
0.0 1: 0.0
82.4
82.4
99.2
99.2
0.0 1: 0.0
$2.4
82.4
99.2 1
99.2
0.1
2.0
8.1
79.7
7488 = 1.0
71.4
1.5
818
80.3
74.4 = 0.8
76.0
1.1
0.1
GConv
2.0
0.0
81.7
81.1
74.1 0.7
77.5
0.6
81.9
81.3
74.5 + 1.0
74.4
0.2
8.1
81.0
74.9
0.0
8..8
81.7
73.8
74.5
0.0 0.0
0.0
8.0
82.0
75.0 1:
75.0
0.0 0.0.0...0
8.00
82.0
75.0
75.0
82.1
2.3
82.0
1.0
1.2 1.000.0
82.0
80.8
64.1 1: 0.5
61.0
0.8
82.0
81.2
64.1 1 0.2
64.1
0.0
82.1
81.0
64.3
0.4
8.10
81.7
8.0
0.1
0.1
82.0
61.2 = 0.2
61.1
0.3
8..1
81.9
61.1 = 0.3
64.5
00
0.0 + 0.0
82.1 + 0.D
82.1
0.2 64.2
64.3
-0.0 0.0
82.1
82.1
64.2
0.2
64.U
0.1
1.6
0.2
80.4
56.2 0.9
56.1
1.9
8.10
80.1
55.9 0.5
57.0
8.1
SAGE
2.0
0.5 0.0
1.1
81.5
55.8 1 0.5
54.8
1.21..00
82.0
81.8
55.9 1 0.6
54.6
8.0
0.0
82.0 0.1
82.1
55.9 0.5
55.7
0.1
82.0
82.0
56.0
57.0
0.0
82.0
82.0
56.6
1
56.6
0.0
82.0 0.0
82.0
56.6
56.6
22

---

Published in Transactions on Machine Learning Research (09/2024)
Table 11: Results on Facebook.
GP+t
GP-m
Model
Ace
Arcep
Acep
AUCGp
AUCb
Accep
Accp.
AUCGp
AUC,
90.5 1.1
85.8
60.8
+ 0.0
91.0 0.4
87.9
1.0
4.1 1.0
90.8 1: 0.8
86.6
65.2
1 1.7
62.9
1.0 1001:00
91.0 1 0.2
90.0
64.7
1 1.1
66.1
GAT
2.0
2.5
90.8 0.4
88.1
61.1
61.9
0.2
90.9 + 0.1
90.7
61.4
61.9
8.0
0.1 0.0
91.1
91.0
63.8 + 1.1
67.2
0.0
91.1 0.2
91.4
64.9 = 1.3
64.4
0c
0.1
1: 0.0
90.9 1:
90.8
64.7
0.3
64.8
-0.1 0.00
90.9 1: 0.1
91.0
64.6 1: 0.3
64.3
0.1
4.9
88.2 0.7
83.3
58.5 + 1.8
54.8
3.8
88.6
84.8
60.0 + 1.3
57.0
86.9
GATv2
2.0
0.0
88.4 0.4
85.1
58.8 + 1.0
55.9
0.2
88.3 0.5
88.1
59.9 = 1.6
59.3
0.1
88.6 0.5
88.5
61.2 2
59.7
0.0
88.2
88.4
57.8
0.1
0.1
88.4
61.7 U.4
61.8
0.2
88.6
88.4
61.9 = 0.4
61.3
1.8 1.0
91.1
86.6
98.1 1.5
90.8
2.9
91.8
89.0
96.9
1.0
4.0 1.0
91.6
87.6
98.5 + 1.0
93.2
1.1 1.1+0.0
0.1
90.8
99.0 = 0.1
98.7
GCN
2.0
3.0
91.7
88.7
98.8 0.4
96.8
0.5
91.9
91.5
99.0
99.1
8.0
0.1
9..
91.9
99.1=002
99.2
0.1
9..0
91.9
99.0 = 0.1
99.0
00
0.0 1: 0.0
91.9 1: 0.0
91.9
99.1
99.1
0.0 1: 0.0
91.9 1: 0.0
91.9
99.1
99.1
0.1
0.0
88.5
84.1
51.2 = 0.3
52.4
2.5
8.2
86.1
51.2 = 0.2
51.8
GConv
2.0
2.0 2.0
88.5
86.5
51.1 + 0.2
52.2
0.1 0.10
8.2
88.2
51.2 + 0.4
51.3
0.0
0.3
88.0
51.0
0.5
8.34
88.0
51.1
0.0 0.0
88.5
88.5
51.1 1:
51.1
0.0
8..5
88.5
51.1 1:
51.1
0.0
91.4
3.3
91.5
1.0
3.7 0.0
0.2
87.8
60.4 1 0.5
55.7
1.0
91.6
90.6
60.3 1 0.4
58.8
2.0
0.1
88.9
0.5
91.6
91.1
59.5
8.0
0.0
9.1
91.6
60.7 = 0.2
60.0
0.1
9.1
91.4
60.5 = 0.6
59.7
00
-0.0
91.6
91.6
60.3 0.4
60.1
0.0
91.6
91.5
60.3
0.2
60.1
0.1
44
9.9
86.9
75.0 1.0+1. 1.5
69.8
2.6
9.6
88.9
75.0 = 1.4
72.9
90.7
SAGE
2.0
2.5 2.0
9..6
89.1
74.6 1 0.8
71.0
0.4
91.8
91.4
75.2
1 0.5
75.2
8.0
0.0
9.0
91.8
75.6 0.5
76.2
0.1
9.8
91.7
75.8
0.9
74.2
0.0
0.0
91.9
74.7 1
74.7
0.0
9.0
91.9
74.7
74.7
23

---

Published in Transactions on Machine Learning Research (09/2024)
Table 12: Results on Amazon Photo.
Model
Ace
Accar
Aces
AUCer
AUC,
AAe
Accar
Aсоb
AUCar
AUCb
0.1
13.9 + 2.0
85.6 2.4
71.8
80.9 + 3.9
70.1
1.4
86.3 0.5
84.9
82.3 + 4.2
79.4
0.2
8.1
4.5
GAT
2.0
12.8 1: 2.0
85.6 1.8
72.8
83.5 1 1.9
72.2
-0.2
86.2
86.2 0.9
86.3
82.4
1 3.6
82.6
0.2
86.4
2.9
73.6
-0.2
86.
86.5
83.1
2.6
83.1
0.0
86.8
86.8
83.9 0.5
84.4
0.0
86.8
86.8
83.7
0.6
83.7
83.8
71.0 4.6
61.7
2.6
8.2
4.2
68.2
1.0
12.2 2 4.0
82.6 = 4.0
70.4
69.4 4.8
57.2
2.06
83.7 + 1.9
84.3
70.9
1: 4.1
72.4
GATv2
60.0
72.0
3.2
8.0
-.2
$3.8 1.3
85.0
3.4
71.8
-..1
83.4 1.8
84.5
72.6
2 3.4
69.9
00
0.0
76.7 0.8
77.6
0.0
84.9
76.6
0.9
77.3
0.1
3.0
84.1 2.9
68.7
96.4 1.7
89.2
0.5
83.2 1.6
82.7
96.2 + 0.9
95.9
3.0
83.7
95.9
2.07
83.5
GCN
2.0
12.8
83.3 3.1
70.4
95.3
93.0
33.8
81.9
85.7
96. + 1.0
95.5
2.0
-42-1.5
9.9
95.3
-44220
81.8 1.9
96.0 0.6
96.5
0.0
80.8
80.8
96.3 0.0
96.3
0.0
80.8 0.0
80.8
96.3
0.0
96.3
6.0
64.1=
67.3
51.8
52.0
7.0
70.8
76.1
52.2 0.6
51.7
1.0
5.1
65.9 5.0
60.5
0.9
51.7
9.0
62.2
69.9
52.1 1 0.7
52.2
GConv
8.0
-13.0 11.0
60.8 = 10.5
73.7
52.2 0.8
52.8
7.00
65.5 4
71.0
52.0 + 0.6
51.7
00
0.0
52.2 0.0
62.2
0.0
61.3
52.2
0.0
52.2
0.1
8.7 8.7 1.0
86.1 = 0.9
77.3
81.5 1: 6.6
66.4
1.3
86.4
85.2
82.7
4.2
74.5
78.4
0.7
GT
2.0
3.4
86.2 - 0.7
82.8
80.8 1. 4.2
67.1
0.0
8.54
86.3
83.5
1: 3.1
77.1
0.0
$6.6
82.5
80.3
0.0
8.1
84.7
2.4
81.0
0.0
$6.7 0.0
86.7
87.3 0.5
87.6
0.1
8.07
86.6
87.3
0.6
87.8
0.1
14.9 2.0
85.9
71.0
85.1 6.9
70.9
1.0
0.3
85.3
86.2
7.0
79.0
1.0
11.6
85.9 0.9
71.3
78 2.1
71.6
0.2
86.3
86.
77.6
2.8
83.0
SAGE
72.7
0.2
8.0
0.0
86.7 - 0.1
86.9
80.0 1: 1.9
80.0
0.1
86.5 0.1
86.4
78.7
2.0
83.0
00
0.0
86.4
86.4
93.8 + 0.0
93.8
0.0
86.4
86.4
93.8
0.0
93.8
24

---

Published in Transactions on Machine Learning Research (09/2024)
C.4 Additional results with GAT
We report results for e = 0.1 and different values of a and 6, for all our experiments, as averaged values across 10 runs.
Cora
LastFM
PubMed
Facebook
Amazon Photo
0.75
2.5
74
8:2
2/2
17
6.5
744
..0
18
2.0
2.
54
147
14.
14.7
abte
1
0
54
8.2
9.3
9.5
0.6
7.5
8.
66
8.1
0.0
18
18
19
19
3.0
411
55
52
32
134
14.7
143
14.6
00
025
3- 0.1
8
14.7
2.3
4.2
8.0
1.4
19
8-
5.0
24.3
14.5
0.0
6.1
0.25
0.5
1.0
0.1
0.25 delt
0.5
1.6
0.
0.1
6.25
100
0.25 deta
0.5
1.0
0.
0.
0.5
0.5
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
1.0
0.5
3.
4:6
6.5
6.8
2.0
4.1
4
3
4.2
54
3/2
3.3
2.7
5.5
2.8
2.3
25
27
2.0
711
84
7.9
966
15.5
0.7
12
57
1.9
5.
3.5
4.3
5.9
6.0
277
24
71
7.4
135
925
4.0
4.3
1.0
525
-0.0
1.6
2.7
2.7
3.0
925
2.5
5.9
3.9
3.9
5.5
-0.5
1.7
37
6.1
2.0
825
42
22
30.1
12.0
15.6
01
6.
1.7
14
177
2.5
2.2
566
-03
3.8
149
11.2
0.0
0.1
0.25
0.5
1.0
0.0
5.1
0.25
1.0
0.0
0.1
0.25
0.5
10
0.0
0.1
0.25
0.
10
0.0
0.5
0.5
10
(b) DAUC for different values of a and 6. Smaller is better.
Figure 4: Results for GP-t with GAT, for = 0.1. Average values across 10 runs. The colormap is normalized to interpret all Ace > and AUe & 2 as desirable.
Cora
LastiMM
PubMed
Facebook
Amazon Photo
2.8
3.0
4-1
3.0
3.7
2.5
1.9
19
32
32
3.0
1.2
12
0.75
5.5
03
4.2
3.8
4.9
4058
-066
1.5
39
2.7
3.6
03
16
1.8
18
19
1.5
2.9
33
34
32
0.6
12
17
18
200
-0
071
0.5
2.2
4.2
1.1
0.3
2.1
1.7
39
4.2
2.5
18
0.
1.4
15
18
19
R. 8..45
18
29
3.5
3.0
19
0.
1.4
18
20
0.
0.0
0.1
0.25
3.5
1.0
0.0
9.1
0.5 delas
0.5
1.0
0.0
0.1
0.25
05
1.0
0.0
0.25
0.5 deta
0.75
1.0
0.0
0.1
025
05
1.0
deta
data
daks
(a) Ace for different values of a and 8. Higher is better.
LastFM
PubMed
Racebook
Amazon
1.0
531
1:3
277
2.4
0.3
DA
0.7
05
0.6
111
1.
14
13
0.
2.2
15
14
3.
DB
5.1
2.5
-0.6
0.4
3.2
0.75
-14
-3.5
2.8
4.0
-0.9
02
0.0
04
-03
56
07
-14
12
57
-0.2
6.0
65
32
65
.85
0.5
11
03
7.6
0.25
-14
-5.1
17
44
52
0.55
0.
.05
1.6
0.
0.7
0.25
.17
42
3.8
02
1.3
023
.12
21
.03
-3.1
0.
0.5
1.1
4.5
1.7
3.6
5.1
08
0.0
-3.4
-17
32
0.0
13
2.0
00
4.1
1.6 255
0.0
-10
5.3
0.0
4.0
4.6
0.8
0.1
0.25
0.5
10
8.0
01
6.55
0.5
19
0.0
0.1
0.25 dala
05
1.3
8.
0.25
0.5
635
0.0
0.25
0.5
1.0
0ck3
(b) AAUC for different values of a and 6. Smaller is better.
Figure 5: Results for GP-m with GAT, for = 0.1. Average values across 10 runs. normalized to interpret all Acc > 0 and AAUC I 2 as desirable.
The colormap is
25

---

Published in Transactions on Machine Learning Research (09/2024)
C.5 Additional results with SAGE
We report results for e = 0.1 and different values of a and 6, for all our experiments, as averaged values across 10 runs.
Cara
LastFM
PubMed
Facebook
Amazon Photo
59
6.1
5.0
4.5
15.4
0.75
49
122
5.0
4.5
R 0.0
16
16
49
R
15.4
23.4 15.4
a
0.5
1.5
244
5.0
3.9
5.1
apte 0.5
0.4
4.6
3.4
5.5
4.5
01
1.
15
15
14
0.1
2.6
444
4.
4.5
37
142
23.4
15.7
15.6
-1
-0
325
2.7
0.3
-02
2.0
14
1.5
1.6
10.0
1.0
17
140
15.7
15.5
2.2
4.5
0.
1.
3.2
14.5
15.5
0.0
0.1
0.25
0.5
1.0
0.1
0.25 della
0.5
1.0
0.1
0.25
10
0.1
0.25
0.5
2.5
01
0:25
0.5
deta
068a
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
3.4
9.
11
9.1
7.3
3.0
288
2.8
2.8
3.1
1.1
144
3.4
144
0.5
3.5
666
6.6
6.6
5.7
6.8
25.4
25.4
25.4
24.6
0.75
7.3
28
14
1.2
4.0
9.1
0.9
055
28
0.8
0.6
0.8
0.0
4.8
23.4
26.1
0.25
13
2.2
6.0
5.4
7.3
02
1.8
2.0
0.5 18
3.1
0.5
0.7
0.8
0.3
0.5
0.3
3.3
2.9
3.8
1.6
11.5
24.0
25.9
24.6
60
0.6
5.1
0.25 delt
0.5
100
0.0
6.1
0.25
0.5
1.
6.0
0.1
0.25
0.5
1.0
6.
01
0.5
05
10
0.0
0.25 deba
0.5
1.0
dell
(b) AAUC for different values of a and 6. Smaller is better.
Figure 6: Results for GP-t with SAGE, for e 0.1. Average values across 10 runs. normalized to interpret all Acc > O and AAUC I 2 as desirable.
The colormap is
Cara
LastFM
PubMed
Facebook
Amazon Photo
5.1
3.2
4.2
2
9
29
1.0
0.75
4.
5.0
-62
3.3
4.2
2.
19
22
30
11
2.8
4.2
5:1
5.0
0.2
2.4
2.4
3.2
4.2
1.7
19
19
19
14
24
33
29
01
08
33
13
11
-0
525
1.4
1.6
-05
1.0
2.3
4.2
10
1.5
1.9
19
2.0
1.0
1.5
1.1
0'0
6.1
0.25
0.5
1.0
0.0
9.1
0.25 delta
0.5
1.0
0.0
0.1
0.5 data
05
1.0
0.0
0.1
0.25 deta
0.5
1.0
0.
0.
025
05
1.0
deta
daks
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
1.0
3.0
4:5
4:5
4.5
4.5
0.0
177
1.7
1.7
29
2.6
34
114
-14
4.3
1.0
3.5
3.5
3.5
18
0.9
12.0
12.0 12.0
12.0
0.75
3.5
4.5
4.6
0.3
100
17
29
6.75
-22
49
166
-14
-35
3.8
3.6
11.4
114
12.0
2.4
4.3
53
0.6
10
1.
05
17
05
13
21
3.1
1.
3.6
20
7.0
11.4
12.7
5:55
3.6
2.8
4.2
4.6
525
-1.4
13
1.9
27
29
025
2.0
4.4
12
-14
4.5
-31
21
1.3
1.0
1.0
525
2.9
3.
4.5
11.3
12.0
08
577
0.0
101
2.2
00
4.
211
0.
0.0
-12
5.6
0.0
6.3
103
12.0
0.8
0.1
0.25
0.5
10
8.0
01
6.55
0.5
10
0.0
0.1
0.25 dala
05
1.3
8.0
5.25
85
0.0
0.25
0.5
1.0
dck3
(b) AAUC for different values of a and 6. Smaller is better.
Figure 7: Results for GP-m with SAGE, for e = 0.1. Average values across 10 runs. normalized to interpret all A Acc > 0 and AAUC I 2 as desirable.
The colormap is
26

---

Published in Transactions on Machine Learning Research (09/2024)
C.6 Additional results with GCN
We report results for e = 0.1 and different values of a and 6, for all our experiments, as averaged values across 10 runs.
Cara
LastFM
PubMed
Facebook
Amazan Photo
5.
4
4.2
R-
54
9-
17.1
0.75
53
5.0
19
4.1
R
11
18
18
54
271
27.1
17.1
-1
525 0.5
3.
5.0
5.9
5.0
-044
3.4
39
4.3
4.2
-.0
1.5
17
18
1.8
103
2.9
5.0
3.4
5.3
26
11.
17.2
15.4
16.9
-0
2.3
6.0
1.0
1.4
1.3
17
4.0
0.1
11.7
15.4
14.9
2.1
4.2
11
1.
25.7
15.0
0.0
0.1
0.25
1.0
0.1
0.25 della
0.5
1.0
0.1
0.25
10
0.1
0.25 dela
0.5
2.0
01
0:25
0.5
de
068a
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
8.3
12:3
12:1
12.1
13.9
5:4
13.6
13:6
13:6
13.6
6.4
12:9
12.8
12.9
13.3
3.0
8
8:2
8:2
6.1
0:3
9.0
9.0
9.0
6.1
0.75
023
65
03
5.2
11.0
1.0
10.2
129
13.5
13.0
20.9
12.8
12.9
13.3
0.5
7.3
8.2
9.0
0.25
0.1
4.
5:4
12
11.9
0.25
0.7
6.0
1211
13.5
1366
0.0
9.3
12.7
18.1
13
0.0
3.0
6.3
8.1
8.1
2.9
7.6
8.0
6.1
00
0.6
5.1
0.25
0.5
1.0
0.0
6.1
0.24 dn
0.5
1.0
0.0
0.1
0.25 dell
0.5
1.0
6.0
01
0.5
05
10
0.0
0.25 de8a
0.5
1.0
delta
(b) AAUC for different values of a and 6. Smaller is better.
Figure 8: Results for GP-t with GCN, for = 0.1. Average values across 10 runs. The colormap is normalized to interpret all Aee > 0 and AAUC & 2 as desirable.
Cara
LastFM
PubMed
Facebook
Amazon Photo
5:6
Q
3.3
19
9
30
0.75
48
3.3
3.5
18
19
30
12
22
5.0
5.6
5.4
0.0
2.6
5.4
3.3
3.5
-1-00
1.5
19
19
19
10-0000
277 30 33
30
4A
10
12
0.4
1.0
-0
525
5.7
0.23
1.7
3.1
1.5
10
14
1.6
19
24
9.3
13
3.6
00
1.5
0'0
6.1
0.25
0.5
1.0
0.0
9.1
0.25 delta
0.5
1.0
0.0
0.1
0.5 data
055
1.0
0.0 0.25
0.5 deta
0.75
100
0.
0.1
025 daks
0.5
1.0
deta
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
1.0
5.9
5:3
5.2
7.4
3.0
75
2.5
7.5
72
1.7
3.4
5-4
54
3.5
5J7
23
24
21
22
1.5
0.5
0.5
05
0.4
0.75
6:1
6.9
7.4
0.7
6.4
7.5
72
0.3
5.0
5.
0.3
23
0.9
1.2
3.0
0.7
7.5
7.5
5.2
5.5
0.6
21
0.0
1.2
5:55
0.5
1.6
4.7
5.5
7.4
3.1
3.6
7.1
7.0
72
025
0.3
3.0
5.3
53
5.5
233
-33
12
23
23
22
A25
.0.7
2.0
1.0
01
0.4
08
1.3
74
0.0
2.1
6.6
6.
1.5
5.6
0.0
1.6
2.3
0.0
0.4
0.8
0.1
0.25
0.5
10
8.0
01
6.25
0.5
10
0.0
0.1
0.25 dalia
0.
1.3
05
0.25
0'3
0.5
10
0.0
0.25
05
1.0
dck3
(b) AAUC for different values of a and 6. Smaller is better.
Figure 9: Results for GP-m with GCN, for e = 0.1. Average values across 10 runs. normalized to interpret all Acc > 0 and AAUC I 2 as desirable.
The colormap is
27

---

Published in Transactions on Machine Learning Research (09/2024)
C.7 Additional results with GATv2
We report results for e = 0.1 and different values of a and 6, for all our experiments, as averaged values across 10 runs.
Cara
LastFM
PubMed
Facebook
Amazon Photo
8.
8.5
2.7
5.1
51
9-
14.7
0.75
84
79
3.3
2.6
1.6
3.
4.8
16
16
15
5.
5.0
142
24.7
14.5
-1
0.5
8.1
8.6
7.9
5.7
0.5
-0.9
5.1
41
5.
5.3
-3
1.5
17
13
14
-03
35
5.
32
5.0
29
142
24.5
15.7
14.7
-0
025
6.0
1.1
151
19
14
17
1.5
344
6.1
14
114
14.5
15.3
1.0
4.5
4.2
14.4
12.7
0.0
0.15
0.5
0.75
1.0
0.25
0.5 della
5.55
1.0
5.25
0.5
0.75
10
0.25
0.5
0.75
1.
01
0:25
0.5
da
063a
dela
0683
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
4.2
4.3
3-9
4.6
5.3
0.6
16
18
2.0
3.0
2.1
4.8
5.2
488
3.6
2.5
32
3.6
31
27
4.3
14.3
13.2
13.0
7.7
0.75
18
34
65
3.5
3.8
5.0
0.1
25
22
29
13
3.6
32
3.5
6.9
13.0
0.25
0.1
2.3
5:2
5.8
5.5
0.25
0.1
23
2.3
2.8
28
0.2
4.0
4.1
41
3.7
0.3
33
9.1
3.3
29
8.7
2.0
7.7
17.6
6.7
00
60
0.6
0.25
0.5
375
100
0.0
0.25
0.5
0.75
10
6.0
0.25
3.5
0.75
1.0
5.
0.25
0.5
0.75
100
0.0
0.25 deba
0.5
1.0
dell
della
(b) AAUC for different values of a and 6. Smaller is better.
Figure 10: Results for GP-t with GATv2, for e == 0.1. Average values across 10 runs. normalized to interpret all A AAce > 0 and AAUC S 2 as desirable.
The colormap is
Cara
LastFM
PubMed
Facebook
Amazon Photo
54
1.2
2
9
42
8.2
0.75
6.0
6.75
0.0
2.4
11
12
13
18
35
0.5
p
4.7
5.5
5.4
7.0
-1.0
21
1.7
0.5
0.0
1.7
1.6
17
19
104
2.9
35
4:
377
0.5
35
2.4
4.5
49
-0
325
3.0
0.23
1.5
1.6
0.9
10
1.8
13
3.0
47
4.6
334
0'0
0.25
0.5
0.75
1.0
0.0
0.25
0.5 della
3.5
1.0
0.0
0.5
055
0.75
1.0
0.0
0.25
0.5 deta
0.75
1.0
0.0
0.1
0.5 daks
0.5
1.0
dela
data
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
1.0
1.9
2.4
2.2
2.5
3.5
2..6
01
0.3
02
08
12
34
3A
24
4.5
-32
13
14
1.4
5.0
-7.9
40.4
1.1
0.6
9.5
0.75
2.5
1.1
4.3
-1.6
01
61
07
10
37
2.4
16
37
0.2
33
2.6
-3.4
-07
-13
05
03
2.7
2.5
4.0
112
01
81
0.4
42
54
2.9
2.9
39
0.9
0.7
9:25
2.
17
2.7
23
2.9
.2.6
.0.
0.4
0.7
0.9
025
24
25
3.6
32
5.
223
-35
10
3.5
2.6
4.5
5.5
-2.3
40.7
2.3
4.0
0.
08
12
11
3.6
0.0
01
1.2
0.5
6.0
6.3
15
0.0
0.7
3.6
0.0
0.7
0.8
5.25
05
5.5
10
8.0
0.5
0.5
0.75
10
0.0
0.25
3.5
0.5
1.3
0.
0.25
0'3
675
10
0.0
0.25
0.5
1.0
dala
0ck3
(b) AAUC for different values of a and 6. Smaller is better.
Figure 11: Results for GP-m with GATv2, for e = 0.1. Average values across 10 runs. normalized to interpret all Acc > 0 and AAUC I 2 as desirable.
The colormap is
28

---

Published in Transactions on Machine Learning Research (09/2024)
C.8 Additional results with GT
We report results for e = 0.1 and different values of a and 6, for all our experiments, as averaged values across 10 runs.
Cara
LastFM
PubMed
Facebook
Amazan Photo
7.0
7.5
2.5
0.75
17
11
8.5
R2
18
21
48
R
55
0.5
00
72
7.3
7.6
7.7
0.5
2.9
5.9
5.4
0.
7.0
3-
01
18
19
19
21
100
4.
5.0
43
5.
01
52
9.0
9.4
9.4
-1
-0
325
6.1
7.0
1
14
17
155
47
8.6
8.1
5.7
9.0
8.5
0.0
0.15
0.5
0.75
1.0
0.25
0.5 delta
5.15
1.0
5.25
0.5
0.75
10
0.25
0.5 dela
0.75
1.5
011
0:25
0.5
da
063a
068a
(a. Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
2.3
4.7
3.9
3.9
3.6
2.3
38
4.2
3.6
5.0
333
3.7
4.0
4.0
4.5
4.0
64
5:8
6.6
6.5
0.1
192
19.7
19.1
17.9
0.75
0.4
0.3
65
3.6
3.8
0.2
4.6
0.3
4.2
4.0
0.5
5.7
57
20.1
14.5
0.25
0.2
3.1
4.3
47
4.
0.2
0.0
3.5
4.8
4.8
45
0.0
3.9
4.0
4.1
4.5
0.2
8.3
5.2
6.2
0.6
14.7
14.7
17.8
00
0.6
2.25
0.5
575
100
0.0
0.25
0.5
0.75
1.
6.0
0.25
3.5 dell
0.75
1.5
6.
0.25
0.5
10
0.0
0.25
0.5
1.0
dela
dn
(b) AAUC for different values of a and 6. Smaller is better.
Figure 12: Results for GP-t with GT, for e e= 0.1. Average values across 10 runs. The colormap is normalized to interpret all Aee > and AAUC & 2 as desirable.
Cara
LastFM
PubMed
Facebook
Amazon Photo
52
Q
3.5
2
33
0.75
48
4.5
2.6
12
21
23
34
33
5.5
411
5.1
5.1
4.3
0.2
1.8
5.7
3.3
4.4
01
23
23
22
23
01
3.0
33
344
3.3
03
1.3
13
1.0
17
-0
025
3.6
0.25
-0.6
2.4
4.7
10
22
23
33
401
3.5
1.0
00
09
0'0
0.25
0.5
0.75
1.0
0.0
0.25
0.5 della
5.5
1.0
0.0
0.25
055
0.75
1.0
0.0
0.25
0.5 deta
0.75
1.0
0.0
0.1
025
05
1.0
dela
daks
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
1.0
0.1
2.1
19
3.4
1.9
0.6
13
1.5
19
12
0.6
0.7
3.8
1.
0.5
2.5
3.
3.
35
3.
0.0
10.
9.9
9.6
15.2
0.75
2.8
2.0
2.3
0.75
-0.5
15
1.
15
-04
13
0.5
32
32
22 677
2.1
11.4
12.2
65
23
3.
2.0
2
0.4
13
0.3
3.
14
33
35
11.4
10.1
2:25
42
10
19
23
2.4
01
13
1.3
31
14
025
.02
0.8
12
07
3.3
0.6
2.3
2.8
3.6
2.6
5.1
0.00
4.3
15.5
15.4
08
1.0
2.0
14
0.0
07
2.2
00
1.5
0.0
2.5
6.6
4.0
0.
5.25
055
5.5
10
8.0
0.55
0.75
10
0.0
0.25
3.5 data
0.75
1.3
8.
0.5
0.5
6.5
0.0
0.25 dck3
05
(b) AAUC for different values of a and 6. Smaller is better.
Figure 13: Results for GP-m with GT, for e = 0.1. Average values across 10 runs. The colormap is normalized to interpret all A > and AAUC & 2 as desirable.
29

---

Published in Transactions on Machine Learning Research (09/2024)
C.9 Additional results with GConv
We report results for 0.1 and different values of a and 8, for all our experiments, as averaged values across 10 runs.
Cora
LastFM
PubMed
Facebook
Amazon Photo
2
0.75
62
0:73
40
4.2
12
19
39
20
46
46
31
-1
16
agte
0.5
0.0
4.9
6.2
6.1
appt
0.5
1.3
5.1
4.0
4.
4.2
0.1
2.2
21
21
2.0
67
0.5
4.4
4.6
4.4
4.
8.7
12.0
77
61
366
-1
-0
0:25
12
0.3
8.
0.666
4.
4.3
4.2
8-
1.5
-22
11.2
0.0
0.55
0.5
0.75
1/0
0.0
0.25
0.5
2.5
1/0
0.0
5.5
0.5
0.75
10
0.0
0.25
0.5
0.75
1.
0.
0.1
0:25
0.5
della
della
06Ra
deta
0483
(a) Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
0.0
3.9
19
19
2.0
6.1
15
3.5
3.5
115
8.7
33
3.3
33
2.8
R-
9.2
33
11
33
13
E
2.0
1.2
-12
-12
0.2
0.75
13
0.0
3.6
3
23
2.0
.83
12
-15
3.4
-55
0.1
5.6
25
2.8
9.1
..0
13
333
33
0.2
18
-12
-.0
02
0.35
0.2
1.0
2
2.5
2.0
0.5
8.6
0.7
12
1.5
15
0.1
233
3.4
32
2.8
C33
0.
0.4
18
13
13
0.5
0.7
0.3
0.7
02
60
0.
0.25
0.5
3.5
16
0.0
0.25
0.5 dn
0.75
10
6.
0.25
3.5 della
0.75
1.0
5.
0.25
0.5
0.75
10
0.0
0.25
0.5
1.0
delt
(b) AAUC for different values of a and 6. Smaller is better.
Figure 14: Results for GP-t with GConv, for e = 0.1. Average values across 10 runs. normalized to interpret all A Acc > 0 and AAUC < 2 as desirable.
The colormap is
Cafa
LastFM
PubMed
Facebook
Amazon Photo
19
2.7
R
9-
19
4.1
F
4.0
-27
16
16
E.
24
18
1,4
-1
0.1
3A
1.9
2.3
-3.1
1.3
114
4.0
45
-27
-3
1.3
15
16
14
01
2.3
24
22
24
41
09
3.4
2.9
-16.7
1.8
4.1
-5.1
5.5
14
-7.7
19
13
344
166
25
0.0
21.5
6..
8
2.7
8
2.1
8
183
0.0
0.55
0.5
0.75
1.0
0.25
0.3 della
2.75
1.0
5.25
0.5 deta
0.75
10
0.25
0.5
0.75
2.5
0.0
01
0.2
0.5
de
dela
d4ta
Ace for different values of a and 8. Higher is better.
Cora
LastFM
PubMed
Facebook
Amazon Photo
1.9
13
2.6
2
266
3.3
0.6
06
3.6
0.6
188
L.7
0.9
0.9
09
1.
0.3
077
07
3.7
03
0.0
0.0
0.0
0.5
0.75
8
05
43
2.2
24
23
-11
2.4
2.5
3.9
11
21
35
0.3
3.5
.08
2.6
0.8
0.25
03
13
24
31
31
225
8.5
16
1.3
1.
025
0.9
311
10
1.3
0.7
0.1
0.8
8.5
0.7
0.0
03
0.3
0.
08
06
5.55
0%5
3.5
16
0.6
0.25
0.5
0.75
10
0a
0.25
3/5 dell
0.7%
1.3
6.
0.25
0.5
0.5
16
0.0
0.5 deba
05
1.0
dets
de
(b) AxUC for different values of a and 6. Smaller is better.
Figure 15: Results for GP-m with GConv, for == 0.1. Average values across 10 runs. normalized to interpret all A Aec > 0 and AXUG < 2 as desirable.
The colormap is
30


Reviews:
[{"review_id": "0KHql9Xvgk", "reviewer": "Reviewer_NPRv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The graph neural network architectures mentioned in the related work are quite outdated, as there are recent state-of-the-art architectures that use bi-level attention based graph aggregation for large-scale multi-relation general-purpose graphs. The authors should mention these works in their related work section for relevance and recency to the latest research: \n\n\"Bi-Level Attention Graph Neural Networks,\" 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand, 2021, pp. 1126-1131, doi: 10.1109/ICDM51629.2021.00133. \n\nHeterogeneous Graph Attention Network. In The World Wide Web Conference (WWW '19). Association for Computing Machinery, New York, NY, USA, 2022–2032. \n\nFurthermore, the authors should highlight what the novelty of their work is and limitations of existing models, since controlled perturbation of the graph structure by randomly replacing the neighbors of a node with other similar neighbors, according to some similarity metric has been proposed by other prior works.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose GraphPrivatizer that privatizes the structure of a graph under Differential Privacy. It uses controlled perturbation of the graph structure by randomly replacing the neighbors of a node with other similar neighbors, according to some similarity metric. Specifically, authors aggregate features to compute similarities and imposing a minimum similarity score between the original and the replaced nodes provides the best privacy-utility trade-off, and then train a Graph Neural Network server-side without disclosing users’ private information to the server.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to the above comments:\n\nPlease also provide one figure summarizing where algorithms 2-4 fit in, in terms of the overall architecture (Figure 2). \n\nPlease provide dataset properties and statistics summarized in one table (e.g., node count, edge count etc). \n\nThe experiment baselines also seem highly outdated, with GCN and GraphSAGE being very old models.", "broader_impact_concerns": "This work investigates a useful topic of research in Differential Privacy for graphs, however I have a concern regarding novelty of the works, outdated baselines (for experiments) and overall architecture (as detailed in the above comments).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tJe9cPKIVN", "reviewer": "Reviewer_zkvH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The paper is generally easy to follow and clear in terms of key points in methodology and experiments.\n- An experimental evaluation of the proposed method for different datasets and GNN architectures is provided along with a thorough analysis of the results.\n- A complete list of hyperparameters for the proposed algorithm is provided in the Appendix, enhancing the reproducibility of the experimental setup.\n\n**Weaknesses:**\n- Definition 4.2 as presented is unclear whether it is derived from the cited paper on page 5 (Hidano & Murakami, 2022) or provided by the authors. If it is the latter, the statement that “by construction, node degree is preserved” and the conclusion “while the converse does not hold” require further explanation. Additionally, since the authors claim to provide a definition of ε edge-set LDP for their local privacy settings as a main contribution, it is necessary to clarify any algorithmic or theoretical overlap with the cited works in the methods section, especially concerning edge-set LDP.\n- Given that the cited work (Hidano & Murakami, 2022) provides a degree-preserving randomized response, which appears closely related to the proposed method (operating on neighboring lists), comparisons between the two methods are necessary. The authors should justify if such a comparison is not meaningful, by providing more information for the cited work in the related works section.\n- For reproducibility purposes (it is not mentioned if the code will be publicly available), the exact hyperparameters of the GNNs need to be specified for the different variants, including the number of layers and hidden dimensions.\n- Including a limitations section in the conclusion discussing scenarios where the proposed algorithm may not be applicable would be crucial for guiding future research directions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce a framework that utilizes Graph Neural Networks (GNNs) in conjunction with differential privacy techniques to derive representations from graph-structured data while adhering to privacy requirements applicable in real-world scenarios, particularly emphasizing a local setting. To ensure the privacy of features and labels, the graph structure undergoes local privatization through a perturbation strategy, where private nodes are substituted with similar ones based on a similarity score.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Motivation:**\n- *Privacy Considerations:* Local and global privacy, as well as the limitations of the considered setups in real-world scenarios, should be more thoroughly addressed in the introduction and contributions sections to contextualize the impact of the proposed method for differential privacy (DP). The significance of focusing on the local setting should be elucidated, explaining why this is crucial and whether the proposed method could potentially extend to other settings.\n\n**Algorithm and Experiments:**\n- *Baseline Comparisons:* The authors compare their method with only one baseline adapted from two cited methods (Sajadmanesh & Gatica-Perez, 2021, and Wu et al., 2022). It is important to justify why these modifications are necessary and whether other related works could be applied with fewer adjustments.\n- *Distinction from Related Work:* Further clarification is needed regarding the distinction from the cited work (Hidano & Murakami, 2022). An experimental comparison should be included, or the authors should justify why such a comparison is not applicable.\n- *Similarity Metrics:* Cosine similarity is used as the sole measure for node replacement. The authors should justify this choice and discuss its potential impact on performance. Comparisons with other similarity metrics would provide valuable insights and could serve as a useful ablation study for the proposed algorithm.\n\n**Readability:**\n- *Symbol Clarity:* Symbols involved in definitions should be clearly denoted alongside the equations in which they are used. For instance, symbol $m_v$ in Equations (1) and (2) in section 3.1 and $Pr[.]$ in Definition 3.1 should be explicitly defined. Similarly, symbols in algorithms 2, 3, and 4 mentioned in Section 4.2 are hard to identify in the provided text. The basic notations currently provided in the large upper paragraph of page 6 could be repositioned into equations or summarized in a table of basic notations to enhance symbol clarity throughout the paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CzBqqo17vF", "reviewer": "Reviewer_vXhW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strong points:**\n- The problem considered here is very interesting and relevant. \n- The algorithm is theoretically validated to achieve $\\epsilon$-edge set LDP.\n- The proposed algorithm seems novel and is \"model-agnostic,\" making it easily applicable to the majority of available GNNs (also also shown in the experimental section).\n- The empirical results look promising.\n\n**Weak points:**\n- [W1] In section 2, you claim: “individual nodes have only access to their own edges, features, and labels,” but in the algorithm, each node has access not only to its neighborhood but also to its 2-hop neighbors (and their labels to compute similarity). Can you please clarify this?\n- [W2] The authors use a similarity score based on the cosine similarity of node features. I believe more advanced and relevant similarity scores could yield better results. Additionally, considering feature privacy can be confusing as the algorithm becomes a two-step randomization. Specifically, ensuring node features' privacy will likely affect edge-level privacy. \n- [W3] The code implementation seems to be missing, raising possible questions about the validity and reproducibility of the empirical results. Could you please provide it as part of the submission? \n- [W4] The paper lacks a discussion on time complexity. Specifically, how does the algorithm scale with larger datasets? \n- [W5] On a minor personal note, the ordering of the sections was confusing. It would be better to divide all the concepts into a preliminary section and then adapt the problem setup section to include everything related to the authors’ work and hypotheses.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates differentially private algorithms within the framework of graph neural networks, with a particular focus on edge-level differential privacy. The primary motivation is to address the limitations of existing methods, such as the Randomized Response technique, which can undesirably increase the connectivity of the underlying graph. The authors propose a novel algorithm that ensures $\\epsilon$-edge set Local Differential Privacy (LDP). Empirical results demonstrate the relative effectiveness of the proposed approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In addition to the previous weak points that should be addressed, a number of questions are also relevant and would be great to clarify in the manuscript: \n\n- In the beginning of Section 4.2, you state: “new definition.” Can you clarify this statement? Specifically, how novel is your “introduced definition” of adjacent neighborhoods compared to other available node-level privacy definitions (such as [1])? Note that while you aim for edge-level privacy, you seem to be using a node-level definition (Definition 4.1). \n- How can the similarity score be adapted in cases where nodes do not have labels? Generally, in the absence of node features, some crafted vectors (usually based on the node’s degree) are used. How can this be adapted in your case where the neighborhood is perturbed? \n- In accordance with W2, it seems that the interaction between label and edge privacy is not considered in Theorem 4.4. Can you please clarify this possible non-dependence? Additionally, a more formal and complete proof of this algorithm would be beneficial. \n- How does the algorithm scale with larger datasets? It would be great to provide results on larger datasets (perhaps OGBN-Arxiv?). \n- Related to the previous question, how can the model be adapted for datasets that contain edge features? How can this information be used to compute similarities? \n- In the experimental results, you use a 50:25:25 train/val/test split ratio (Appendix A). Is there a reason why you did not use the public folds available with some datasets (such as Cora and PubMed)? \n- As a suggestion, it would be great to expand your results to the graph classification setting. I believe your algorithm can be easily adapted to this setting as well.\n\n---\n[1] Preserving Node-level Privacy in Graph Neural Networks, Xiang & Al. - 2024.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three expert reviewers. The reviewers initially raised concerns about the presentation of the paper, the employed similarity metric and the scalability of the proposed approach. They also complained about missing related work and lack of discussion on how the proposed approach differs from prior work. Most of these concerns were addressed by the authors in the revision and all reviewers recommended weak acceptance of the paper. I thus think that the paper is now ready for publication. Since the main content of the paper is now longer than 12 pages, the authors should select "Long submission (more than 12 pages of main content)" instead of "Regular submission (no more than 12 pages of main content)" on OpenReview. Furthermore, the authors should add a link to the repository where the code is hosted.
Decision: Accept (poster)