Privacy-Preserving Graph Machine Learning
from Data to Computation: A Survey

Attackers can be classified into the active attackers and passive attackers [5].

The first category is active attackers, where the core idea is that the attackers actively plant certain structures into the graph before it is being published. Then, the attackers can identify victims in the published graph by locating the planted structures. For example [113], the attackers create a subgraph $H$ containing $k$ nodes and then use $H$ to connect $b$ target nodes in the original graph $G$ (subgraph $H$ is better to be unique and has the property to be recovered in the published graph). After the original graph $G$ is privacy-preserved (e.g., mask and disturb connections) and published as $G^{\prime}$, the attackers try to find $H$ in $G^{\prime}$ and then determine those $b$ nodes.

Active attackers usually need to access the original graph beforehand and then make corresponding active actions like creating new nodes, linking new edges, and planting subgraphs. The planting and recovery operations are usually computationally costly [5]. Therefore, another direction points to passive attacks and defense.

Passive attackers are based on the fact or the assumption that most entities (e.g., nodes and edges) in graphs usually belong to a unique, small identifiable graph. Then, different from active attackers, passive ones do not need to create new nodes and edges in the original but mostly rely on the observation of the published graph to identify victims. In the initial proposal of passive attacks [5], a passive attacker (e.g., a node in a social network) needs to collude with other $(k-1)$ nodes on the original graph, and the coalition needs to know the external information (e.g., their 1-hop neighbors’ name in the social network), such that they can reconnect on the published graph to identify the victims. Here, we expand the scope of passive attacks to include the attackers whose core is observation plus little external information. For example, in [29], an attacker knows the external background information like “Greg is connected to at least two nodes, each with degree 2” and tries to observe the candidate of plausible Greg in the published social network.

The ultimate goals of most graph privacy attackers can be roughly divided into disclosing the node identity (e.g., name, DOB, and SSN in the social network) and the link existence (e.g., sensitive connections in the social network) [51, 94, 101, 113]. Next, we formally introduce the general definition of these two goals.

Node Identity Disclosure. The node identity disclosure problem often arises from the scenario that the attackers aim to identify a target node identity in the published graph (usually, which has been anonymized already). For example, in a published social network with usernames masked already, the node identity disclosure aims to identify which node is Greg [29]. To be more specific, the identity disclosure can be detailedly divided into node existence disclosure (i.e., whether a target node existed or not in a published graph), node property disclosure (i.e., partial features of a target node are disclosed like its degree, distance to the center, or even sensitive labels, etc) [113].

Link Re-Identification. In a given graph, edges may be of different types and can be classified as either sensitive or not. Some links (i.e., edges) are safe to release to the public, such as classmates or friendships. And some links are sensitive and should maintain private but not published, like the personal disease records with hospitals. The problem of link re-identified is defined as inferring or predicting sensitive relationships from anonymized graphs [111]. Briefly speaking, the adversary (or attacker) achieves the goal when it is able to correctly predict a sensitive link between two nodes. For example, if the attacker can figure out which there is a transaction between two users, given the properties of the released financial graph. Also, there are some detailed categorizations of the line re-identification other than the link existence, such as the link weight and link type or labels [113].

Compared with active attackers, passive attackers are typically efficient in executing for adversaries and do not need to interact with the original graph beforehand very much. Thus, within the scope of passive attackers, achieving those attacking goals (node identity disclosure or link re-identification) relies on the observation of the published graph and certain external background knowledge to further identify victims.³³3Node identity disclosure and link re-identification can also be achieved in active ways [5], but in the paper, we focus on introducing the passive manners that achieve those goals. Next, we focus on introducing what requirements passive attackers need to execute attacks passively.

In general, the background knowledge for achieving node identity disclosure is to help them to detect the uniqueness of victims (i.e., nodes in the published graph) and thus narrow down the scope of candidate sets to increase the successful attack probability. For example, assume that the attackers know some background knowledge $\mathcal{H}$ about a target node, after that, the attackers observe the published graph and find 2 candidates satisfying the condition (i.e., $\mathcal{H}$), then the attackers have $50\%$ confidence to reveal the identity of that target node in the published graph. Next, we introduce some methods to acquire background knowledge.

Vertex Refinement Queries [29]. These are interactive queries, which describe the local structure of the graph around a target node $x$. The initial query in vertex refinement queries is denoted as $\mathcal{H}_{0}(x)$ that simply returns the label of node $x$ in the labeled graph (or a constant $\epsilon$ in the unlabeled graph). And $\mathcal{H}_{1}(x)$ returns the degree of node $x$. Then, iteratively, $\mathcal{H}_{i}(x)$ is defined as the multiset of $\mathcal{H}_{i-1}(\cdot)$ queries on 1-hop neighbors of node $x$, which can be expressed as follows.

where $d_{x}$ is the degree of node $x$. For example, in a social network, $\mathcal{H}_{2}(Bob)=\{1,1,4,4\}$ means that Bob has four neighbors their degrees are 1, 1, 4, and 4, respectively.

Subgraph Queries [29]. These queries assert the existence of a subgraph around a target node. Compared with the above vertex refinement queries, subgraph queries are more general (i.e., the information is not exclusively occupied to a certain graph structure) and flexible (i.e., informativeness is not limited by the degree of a target node). In brief, the adversary is assumed capable of gathering some fixed number of edges around a target node $x$ and figuring out what subgraph structure those collected edges can form. For example, still targeting Bob in a social network, when collecting 3 edges, attackers can find 3 distinct neighbors. And collecting 4 edges can find a tree rooted by Bob. Those existences of structures form $H$ such that attackers can use them to reveal the identity of Bob. Also, different searching strategies can result in different subgraph structures. For example, based on collecting 3 edges from Bob, breadth-first exploration may result in a star subgraph, and depth-first exploration may end up with a three-node-line. We refer to [29], where a range of searching strategies are tested to empirically illustrate the descriptive power of background knowledge.

Hub Fingerprint Queries [29]. First of all, a hub stands for a node that has a high degree and a high betweenness centrality (i.e., the proportion of shortest paths in the graph that include that node) in the graph. Then, a hub fingerprint is the description of a node’s connections to hubs. To be more specific, for a target node $x$, the corresponding hub fingerprint query $\mathcal{H}_{i}(x)$ records the shortest distance towards each hub in a graph. In $\mathcal{H}_{i}(x)$, $i$ is the limit of measurable distance. For example, $\mathcal{H}_{1}(Bob)=(1,0)$ means Bob is 1 distance away from the first hop and not connected to (or 1 distance non-reachable from) the second hub. And, $\mathcal{H}_{2}(Bob)=(1,2)$ means that Bob is 1 distance away from the first hop and 2 distance away from the second hub.

Neighborhood Relationships Queries [112]. Targeting a node, if an adversary has background knowledge about its neighbors and the relationship among the neighbors, then the victim can be identified in the anonymized graph. To be specific, the neighborhood relationship query rely more on the isomorphism of the ego-graph (i.e., 1-hop neighbors) of a target node to reveal its identity, compared with iterative vertex refinement query [29] and general subgraph query [29]. For example, in a social network, if Bob has two close friends who know each other (i.e., are connected) and two close friends who do not know each other (i.e., are not connected), then this unique information obtained by the adversary can be used to find Bob in the published anonymized graph.

Link Prediction Probabilistic Model [111]. This probabilistic model is proposed to determine whether a relationship between two target nodes. And different kinds of background information (i.e., observation) can be leveraged to formalize the probabilistic model, such as (1) node attributes, e.g., two social network users who share the same interest are more likely to be friends; (2) existing relationships, e.g., two social network users in the same community are more likely to be friends; (3) structural properties, e.g., the high degree nodes are more likely to connect in a graph; and (4) inferred relationships (i.e., a complex observation that is more likely based on the inference of the invisible relationship), e.g., two social network users are more likely to be friends if they both are close friends of a third user.

Mathematically, those above observations can be expressed for predicting the existence of a sensitive relation between node $i$ and node $j$ as $P(e^{s}_{ij}|O)$, where $e^{s}_{ij}$ stands for the sensitive relationship and $O$ consists of several observations $\{o_{1}$, …, $o_{n}\}$. For example, if we use the second kind of information (i.e., existing relationships), then $\{o_{1}$, …, $o_{n}\}$ is a set of edges between node $i$ and node $j$ with the edge type other than $s$, denoted as $e^{l}_{ij}$ and $l\in\{1,\ldots,n\}$ is the index of other edge relationships. To solve out $P(e^{s}_{ij}|O)$, the noisy-or model [61] can be used as suggested by  [111], where each observation $o_{l}\in\{o_{1},\ldots,o_{n}\}$ is considered as independent with each other and parameterised as $\lambda_{l}\in\{\lambda_{1},\ldots,\lambda_{n}\}$. Moreover, there is a leak parameter $\lambda_{0}$ to capture the probability that the sensitive edge is there due to other unmodeled reasons. Hence, the probability of a sensitive edge is expressed as follows.

where $s$ in $e^{s}_{ij}$ is the indicator of sensitive relationship, and the details of fitting the values of $\lambda_{l}$ can be found in [111].

Randomization-based Posterior Probability [100]. To identify a link, this observation is based on randomizing the published graph $G^{\prime}$ and counting the possible connections over a target pair of nodes $i$ and $j$. And those countings are utilized for the posterior probability to determine whether there is a link between nodes $i$ and $j$ in the original graph $G$. Formally, the posterior probability for identifying the link $e_{ij}$ in the original graph $G$ is expressed as follows.

where the attacker applies a certain randomization mechanism on the published graph $G^{\prime}$ $N$ times to get a sequence of $G^{\prime}_{s}$, and $s\in\{1,\ldots,N\}$. In each $G^{\prime}_{s}$, if there is an edge connects the target nodes $i$ and $j$, then the indicator function $\mathds{1}(G^{\prime}_{s}(i,j)==1)$ will count one.

In general, the protection mechanisms are proposed to enlarge the scope of candidates of victims, i.e., reduce the uniqueness of victims in the anonymized graphs.

$k$-degree Anonymization [52]. The motivation for $k$-degree anonymization is that degree distribution is highly skewed in real-world graphs, such that it is usually effective to collect the degree information (as the background knowledge) to identify a target node. Therefore, this protection mechanism aims to ensure that there at least exist $k-1$ nodes in the published graph $G^{\prime}$, in which $k-1$ nodes share the same degree with any possible target node $x$. In this way, it can largely prevent the node identity disclosure even if the adversary has some background knowledge about degree distribution. To obtain such anonymized graph $G^{\prime}$, the method is two-step. First, for the original graph $G$ with $n$ nodes, the degree distribution is encoded into a $n$-dimensional vector $\mathbf{d}$, where each entry records the degree of an individual node; And then, based on $\mathbf{d}$, the authors proposed to create a new degree distribution $\mathbf{d}^{\prime}$, which is $k$-anonymous with a tolerated utility loss (e.g., isomorphism cost) instanced by the $L_{1}$ distance between two vectors $\mathbf{d}$ and $\mathbf{d}^{\prime}$. Second, based on the $k$-anonymous degree vector $\mathbf{d}^{\prime}$, the authors proposed to construct a graph $G^{\prime}$ whose degree distribution is identical to $\mathbf{d}^{\prime}$.

$k$-degree Anonymization in Temporal Graphs [69]. For temporal graphs (i.e., graph structures and attributes are dependent on time [19]), this method aims to ensure that the temporal degree sequence of each node is indistinguishable from that of at least $k-1$ other nodes. On the other side, this method also tries to preserve the utility of the published graph as much as possible. To achieve the $k$-anonymity, the proposed method first partition $n$ nodes in the original temporal graph $G$ into $m$ groups using $k$-means based on the distance of temporal degree vectors $\mathbf{d}$ of each node, which is a $T$-dimensional vector records the degree of a node at different timestamp $t$.To realize the utility, constrained by the cluster assignment, the method refines $\mathbf{d}$ of each node into $\mathbf{d}^{\prime}$ while minimizing the $L_{1}$ distance between matrices $\mathbf{D}$ and $\mathbf{D}^{\prime}$ (which are stacks of $\mathbf{d}$ and $\mathbf{d}^{\prime}$). After that, the anonymized temporal graph $G^{\prime}$ is constructed by $\mathbf{D}^{\prime}$ to release for each timestamp individually.

$k$-degree Anonymization in Knowledge Graphs [33]. Different from the ordinary graph, the knowledge graph has rich attributes on nodes and edges [35]. Therefore, the $k$-degree is upgraded with the $k$-attributed degree that aims to ensure a target node in the anonymized knowledge graph has $k-1$ other nodes who share the same attributes (i.e., node level) and degree (i.e., edge level) [32]. Then the $k$-degree anonymization solution gets upgraded in [33], which aims to solve the challenge when the data provider wants to continually publish a sequence of anonymized knowledge graphs (e.g., the original graph needs to update and so the anonymized does). Then, in [33], the $k$-ad (short for $k$-attributed degree) is extended to $k^{\omega}$-ad, which targets to defend the node identity disclosure in the $\omega$ continuous anonymized versions of a knowledge graph. The basic idea is to partition nodes into clusters based on the similarity of node features and degree; Then, for the knowledge graph updates (like newly inserted nodes or deleted nodes), manual intervention is applied (e.g., adding fake nodes) to ensure the $k^{\omega}$ anonymity; Finally, the anonymized knowledge graph gets recovered from the clusters. This initial idea [33] gets further formalized and materialized in [34].

$k$-neighborhood Anonymization [112]. This protection is proposed to defend the node identity disclosure when the adversary comprehends the background knowledge about neighborhood relationships of a target node (i.e., Neighborhood Relationship Queries discussed in Subsection 2.2.1). The core idea is to insert nodes and edges in the original graph $G$ to get an anonymized graph $G^{\prime}$, such that a target node $x$ can have multiple nodes whose neighborhood structure is isomorphic in $G^{\prime}$. Given a pair node $v$ and $u$ in graph $G$ (suppose node $v$ is the target), the authors first propose the neighborhood component and use DFS search to encode the ego-net $Neighbor_{G}(v)$ and $Neighbor_{G}(u)$ into vectors. Then, by comparing the difference between $Neighbor_{G}(v)$ and $Neighbor_{G}(u)$, the authors then greedy insert missing (labeled) nodes and edges (into $Neighbor_{G}(v)$ or $Neighbor_{G}(u)$) to make $Neighbor_{G}(v)$ and $Neighbor_{G}(u)$ isomorphic. Those inserted nodes and edges make $G$ into $G^{\prime}$.

$k$-automorphism Anonymization [117]. This method is proposed for the structural queries by attackers, especially for the subgraph queries (as discussed in Subsection 2.2.1). Basically, given an original graph $G$, this method produces an anonymization graph $G^{\prime}$ to publish, where $G$ is the sub-graph of $G^{\prime}$ and $G^{\prime}$ is k-automorphic. To do this, the authors propose the KM algorithm, which partitions the original graph $G$ and adds the crossing edge copies into $G$, to further convert $G$ into $G^{\prime}$. Hence, the $G^{\prime}$ can satisfy the $k$-different match principle to defend the subgraph query attacks, which means that there are at least $k$-different matches in $G^{\prime}$ for a subgraph query, but those matches do not share any nodes.

The general idea of solutions here is proposed to reduce the confidence of attackers (which usually can be realized by a probabilistic model) for inferring or predicting links based on observing the published anonymized graphs.

Intact Edges [111]. This solution is straightforward and trivial. Given the link re-identification attacker aims to predict a target link between two nodes, and the corresponding link type (i.e., edge type) is denoted as $s$, then the intact edges strategy is to remove all $s$ type edges in the original graph $G$ and publish the rest as the anonymized graph $G^{\prime}$. Those remaining edges are so-called intact.

Partial-edge Removal [111]. This approach is also based on removing edges in the original graph $G$ to publish the anonymized graph $G^{\prime}$. Partial-edge removal does not exhaustively remove all sensitive (indexed by $s$ type) edges in $G$, but it removes part of existing edges. Those removed existing edges are selected based on the criteria of whether their existence contributes to the exposure of sensitive links, e.g., they are sensitive edges, they connect high-degree nodes, etc. Even those removals can be selected randomly.

Cluster-edge Anonymization [111]. This method requires that the original graph $G$ can be partitioned into clusters (or so-called equivalence classes) to publish the anomymized graph $G^{\prime}$. The intra-cluster edges are removed to aggregate a cluster into a supernode (i.e., the number of clusters in $G$ is now the number of nodes in $G^{\prime}$), but the inter-cluster edges are reserved in $G^{\prime}$. To be more specific, for each edge whose edge type is not sensitive (i.e., not $s$ type), if it connects any two clusters, it will be reserved in $G^{\prime}$; otherwise, it will be removed. It can be observed that this method needs the clustering pre-processing, which also means that it can cooperate with the node anonymization method. For example, the $k$-anonymization [71, 44, 56] can be applied on the original graph $G$ first to identify the equivalence classes, i.e., which nodes are equivalent in terms of $k$-anonymization (for example, nodes who have the same degree).

Cluster-edge Anonymization with Constraints [111]. This method is the upgraded version of the previous cluster-edge anonymization, and it is proposed to strengthen the utility of the anonymized graph $G^{\prime}$ by adjusting the edges between clusters (i.e., equivalence classes). The core idea is to require the equivalence class nodes (i.e., cluster nodes or supernodes in $G^{\prime}$) to have the same constraints as any two nodes in the original graph $G$. For example, if there can be at most two edges of a certain type between nodes in $G$, there can be at most two edges of a certain type between the cluster nodes in $G^{\prime}$.

Besides the protections that are designed deliberately for the node identity disclosure and link re-identification risks, there are also other protection mechanisms that are not designed for a specific kind of attacker but for the general and comprehensive scenario, such as randomized mechanisms with constraints and differential privacy schema. Next, we will discuss these research works.

Graph Summarization [29]. This method aims to publish a set of anonymized graphs $G^{\prime}$ given an original graph $G$, through the graph summarization manner. To be specific, this method relies on a pre-defined partitioning method to partition the original graph $G$ into several clusters, then each cluster will just serve as a node in the anonymized graph $G^{\prime}$. The selection of connecting nodes in $G^{\prime}$ results in the variety of $G^{\prime}$, which means that a sequence of $G^{\prime}$ will appear with a different edge connecting strategy. The detailed connection strategy can be referred to  [29].

Switching-based Graph Generation [100]. Here, the authors aim to publish the anonymized graph $G^{\prime}$ that should also preserve the utility of the original graph $G$. Therefore, they propose the graph generation method based on the switching operations that can preserve the graph features. Moreover, the switching is realized in an iterative Monte Carlo manner, each time two edges ($a$, $b$) and ($c$, $d$) are selected. Then they will switch into ($a$, $d$) and ($b$, $c$) or ($a$, $c$) and ($b$, $d$). The authors constrain that two selected edges are switchable if and only if the switching generates no more edges or self-edges, such that the overall degree distribution will not change. After sufficient Monte Carlo switching operations, the authors show that the original graph features (e.g., eigenvalues of adjacency matrix, eigenvectors of Laplacian matrix, harmonic mean of geodesic path, and graph transitivity) can be largely preserved in the anonymized graph $G^{\prime}$.

Spectral Add/Del and Spectral Switch [99]. The idea of this method starts from Rand Add/Del and Rand Switch. Rand Add/Del means that the protection mechanism randomly adds an edge after deleting another edge and repeats multiple times, such that the total number of edges in the anonymized graph will not change. Rand Switch is the method that randomly switches a pair of existing edges ($t,w$) and ($u$, $v$) into $(t,v)$ and $(u,w)$ (if $(t,v)$ and $(u,w)$ do not exist in the original graph), such that the overall degree distribution will not change. In [99], the authors develop the spectrum-preserving randomization methods Spectral Add/Del and Spectral Switch, which preserve the largest eigenvalue $\lambda_{1}$ of the adjacency matrix $\mathbf{A}$ and the second smallest eigenvalue $\mu_{2}$ of the Laplacian matrix $\mathbf{L}=\mathbf{D}-\mathbf{A}$. To be specific, the authors first investigate which edges will cause the $\lambda_{1}$ and $\mu_{2}$ increase or decrease in the anonymized graph and then select the edges from different categories to do Rand Add/Del and Rand Switch to control the values of $\lambda_{1}$ and $\mu_{2}$ not change too much in the anonymized graph.

RandWalk-Mod [60]. This method aims to inject the connection uncertainty by iteratively copying each existing edge from the original graph $G$ to an initial null graph $G^{\prime}$ with a certain probability, guaranteeing the degree distribution of $G^{\prime}$ is unchanged compared with $G$. Starting from each node $u$ in the original graph $G$, this method first gets the neighbor of node $u$ in $G$ denoted as $\mathcal{N}_{u}$. Then for each node in $\mathcal{N}_{u}$, this method runs multiple random walks and denotes the terminated node in each walk as $z$. Finally, RandWalk-Mod adds the edge $(u,z)$ to $G^{\prime}$ with certain probabilities under different conditions (e.g., 0.5, a predefined probability $\alpha$, or $\frac{0.5d_{u}-\alpha}{d_{u}-1}$, where $d_{u}$ is the degree of node $u$ in $G$).

Next, we introduce an important component in the graph privacy-preserving techniques, i.e., differential privacy [36]. The general idea of differential privacy is that two adjacent graphs (e.g., one node/edge difference between two graphs) are indistinguishable through the permutation algorithm $\mathcal{M}$. Then, this permutation algorithm $\mathcal{M}$ satisfies the differential privacy. The behind intuition is that the randomness of $\mathcal{M}$ will not make the small divergence produce a considerably different distribution, i.e., the randomness of $\mathcal{M}$ is not the cause of the privacy leak. If the indistinguishable property is measured by $\epsilon$, then the algorithm is usually called $\epsilon$-differential privacy algorithm. The basic idea can be expressed as follows.

where $G$ and $G^{\prime}$ are adjacenct graphs, $\mathcal{M}$ is the differential privacy algorithm, and $\epsilon$ is the privacy budget. The above equation illustrates that the probability of the same output range is almost equivalent.

Within the context of graph privacy, the differential privacy algorithm can be roughly categorized as edge-level differential privacy and node-level differential privacy. Given the input original graph $G$, the output graph of the differential algorithm $\mathcal{M}(G)$ can be used as the anonymized graph $G^{\prime}$ to publish.

Edge-level Differential Privacy Graph Generation. We first introduce the edge-level differential privacy algorithms, which means that the privacy algorithm can permute adjacent graphs (e.g., one edge difference) indiscriminately.

• •

  DP-1K and DP-2K Graph Model [87]. This edge-level differential privacy algorithm is proposed with the utility preserving concern of complex degree distribution. Here, 1k-distribution denoted by $P_{1}(G)$ is the ordinary node degree distribution in graph $G$, e.g., the number of nodes having 1 degree is 10 then $P_{1}(1)=10$, the number of nodes having 2 degrees is 5 then $P_{1}(2)=5$, etc. 2K-distribution denoted by $P_{2}(G)$ is the joint graph distribution in graph $G$, e.g., the number of edges connecting an $i$-degree node and a $j$-degree node, with iterating $i$ and $j$. And $P_{2}(2,3)=6$ means that the number of edges in $G$ connecting a 2-degree node and a 3-degree node is 6. Hence, DP-1K (or DP-2K) Graph Model first computes the 1K-(or 2K-) degree distribution $P_{1}(G)$ (or $P_{2}(G)$) and then permutes the degree distribution under the edge-level DP to obtain the $P_{1}(G)^{\prime}$ (or $P_{2}(G)^{\prime}$). Finally, an off-the-shelf graph generator (e.g., [70]) is called to build the anonymized graph $G^{\prime}$ based on $P_{1}(G)^{\prime}$ (or $P_{2}(G)^{\prime}$).

• •

  Local Differential Privacy Graph Generation (LDPGEN) [64] is motivated by permuting the connection distribution, i.e., proportionally flipping the existing edge to non-existing and vice versa. To make the generated graph preserve the original utility, LDPGEN [64] first partitions the original graph $G$ into the disjoint clusters and adds Laplacian noise on the node’s degree vector in each cluster, which guarantees the local edge-level differential privacy. After that, the estimator is used to estimate the connection probability of intra-cluster edges and inter-cluster edges based on the noisy degree vectors, such that the anonymized graph $G^{\prime}$ is generated.

• •

  Differentially Private Graph Sparsification [3]. On the one hand, this method constrains the number of edges in the anonymized graph $G^{\prime}$ is less than the original graph $G$ to a certain extent. On the other hand, the method requires that the Laplacian of the anonymized graph $G^{\prime}$ is approximated to the original graph $G$ (i.e., see Eq.1 in [3]). The two above objectives are unified into an edge-level differential privacy framework. The new graph $G^{\prime}$ is then obtained by solving an SDP (i.e., semi-definite program) problem.

• •

  Temporal Edge-level Differential Privacy. In [82], two temporal graphs are adjacent if they only differ in one update (i.e., the existence and non-existence of a temporal edge, different weights of an existing temporal edge). Based on the Priv-Graph algorithm (i.e., adding noise to graph Laplacian matrix), Sliding-Priv-Graph [82] is proposed to (1) take recent updates and ensure the temporal edge-level differential privacy and (2) meet the smooth Laplacian property (i.e., the positive semi-definite of consecutive Laplacian matrices). Moreover, in [14], the authors distinguish the edge-adjacency and node-adjacency in the temporal graphs. Two temporal graphs are node-adjacent (or edge-adjacent) if they only differ in one node (or edge) insertion or deletion.

• •

  Deep Graph Models with Differential Privacy. Following the synergy of deep learning and differential privacy [1], another way to preserve privacy is targeting the gradient of deep graph learning models. In [97], a deep graph generative model called $DPGG_{AN}$ is proposed under the edge-level differential privacy constraints, where the privacy protection mechanism is executed during the gradient descent phase of the generation learning process, by adding Gaussian noise to the gradient of deep learning models.

Node-level Differential Privacy Graph Generation. Compared with edge-level differential privacy, node-level differential privacy is relatively difficult to be formalized and solve. In [39], authors contribute several theoretical node-level differential privacy solutions such as Flow-based Lipschitz extension and LP-based Lipschitz extensions. But they all focus on realizing part of the graph properties instead of the graph data itself, such as anonymized degree distribution, subgraph counting, etc. The same kind of research flavor also appeared in relevant node-level differential privacy works like [6, 39, 66]. Again, differential privacy mechanisms on graphs is a large and comprehensive topic, a more detailed introduction and extensive literature review can be found in [36].

As discussed above, most privacy-preserving graph anonymization methods still consider the input graphs as static. However, in complex real-world scenarios, the graphs are usually evolving over time [22, 114, 17, 18], which brings critical challenges to the current privacy-preserving static graph generation process. In other words, the time domain enriches the node attribute dimension and may also dictate the attribute distribution, which leads to increased exposure risk. For example, some graphs contain multiple dynamics and accurately representing them could contribute to graph tasks like classification [115, 16]. But, the existence of various dynamics increases the probability of being unique and enlarges the leaking risk.

During the node identity disclosure and link re-identification, it can be observed that the majority of background knowledge is solely from structural queries, which is already forceful enough. In heterogeneous graphs [76, 21], the abundant node and edge features increase the risk of leaking sensitive information and bring challenges to protection mechanisms, especially the heterogeneous graphs start to evolve [23, 48].

To the best of our knowledge, how to generate privacy-preserving heterogeneous or temporal graphs remains open.

• •

  What kind of feature information is sensitive in heterogeneous or time-evolving graphs and should be hidden in the generated graph?

• •

  If the corresponding sensitive information is determined, what techniques are effective for protecting structures and features in the heterogeneous or time-evolving environment?

• •

  Last but not least, if the corresponding protection mechanism is designed, how to maintain the generation utility simultaneously with privacy constraints?

A typical FL framework has one central server and $N$ clients, each with its own dataset $\mathcal{D}_{i}$. The main steps can be summarized as follows:

1. 1.

   Parameter broadcasting. The server broadcasts the current global model to (selected) clients.

2. 2.

   Local update. Each client locally trains its local model.

3. 3.

   Parameter uploading. Each client sends upload the model update back to the server.

4. 4.

   Model aggregation. The server aggregates the model updates collected from clients and updates the global model.

5. 5.

   Repeat: Steps 1-4 are repeated for multiple communication rounds until the global model converges to satisfactory performance.

One of the most popular FL algorithms is FedAvg [58]. In each communication rounds, the server randomly selects a subset of clients, and broadcasts the global model to them. Each client locally updates the model with multiple iterations of stochastic gradient descent, and uploads its local model back to the server. Finally, the server computes a weighted average of local model parameters, and updates the global model parameters. Algorithm 1 gives the pseudo-code of FedAvg. Notice that in FedAvg, local data never leaves the client side. Besides FedAvg, most of the FL algorithms strictly follow the aforementioned training protocol [47, 13], or roughly follow it with a few modifications [27, 102].

FL protects client privacy in two main ways. Firstly, instead of transmitting the raw data, FL transmits only the model parameters, which are updated based on the local data of each client. By doing so, FL ensures that sensitive data remains on the client’s device and is not transmitted to the central server and other clients. Secondly, the model parameters uploaded to the server only reveal the distribution of local data, rather than individual data points. This approach helps to maintain privacy by obscuring the specific data points used to train the model.

FL can be equipped with differential privacy mechanisms [59, 91] to enhance privacy protection. As described in the last section, differential privacy is a technique that involves adding noise to data in order to obscure individual contributions while still maintaining overall data patterns. However, different from graph generation, where the noise is added to the data (e.g., node feature, edges, etc), in the context of FL, the noise is added to the uploaded and downloaded model parameters. This ensures that even if an attacker were to obtain the model parameters, they would not be able to accurately infer the raw data from the model parameter. By adding moderate noise to the parameters, the model’s accuracy may be slightly reduced, but the overall performance remains comparable to non-private models. In summary, by using differential privacy mechanisms, FL can achieve even better privacy protection by making it harder for attackers to identify the sensitive data contributed by individual clients.

In this part, we introduce important applications of federated learning on graph data. Roughly, we survey three representative application scenarios: graph-level FL, subgraph-level FL, and node-level FL.

1. 1.

   Graph-level FL: Each client has one or several graphs, while different graphs are isolated and independent. One typical application of graph-level FL is for drug discovery [31], where biochemical industries collaborate to train a graph neural network model predicting the property of molecules. Each molecule is a graph with basic atoms as nodes and chemical bonds as edges.

2. 2.

   Subgraph-level FL: Each client has one graph, while each graph is a subgraph of an underlying global graph. One representative application of subgraph-level FL is for financial transaction data [43]. Each FL client is a bank that keeps a graph encoding the information of its customers, where nodes are individual customers and edges are financial transaction records. While each bank holds its own graph, customers in one bank may have connections to customers in another bank, introducing cross-client edges. Thus, each bank’s own graph is a subgraph of an underlying global graph.

3. 3.

   Node-level FL: Each client is a node of a graph, and edges are the pairwise relationships between clients, e.g., their distribution similarity or data dependency. One example is the smart city, where clients are traffic sensors deployed on the road and linked to geographically adjacent sensors. While clients form a graph, each client can make an intelligent decision based on the collected road conditions and nearby devices.

Figure 4 illustrates the three application scenarios above. Next, we investigate each application scenario in the following three subsections individually.

Global federated learning (GFL) aims to train a shared global model for all clients. FedAvg [58] provides an initial solution for training GNNs with isolated graphs from multiple clients. However, when clients have significantly different underlying distributions, FedAvg needs much more communication rounds for convergence to a satisfactory model, and may converge to a sub-optimal solution [58]. This phenomenon of worse convergence is usually explained by weight divergence [110], i.e, even with the same parameter initialization, the model parameters for different clients are substantially different after the first local stochastic gradient descent (SGD) step. With different model parameters, the mean of client gradients can be different from the gradient in centralized SGD, and introduce error to the model loss [84].

Data-sharing. To tackle the non-IID challenge to FL optimization, a simple but effective method is to share a small amount of data among clients. [110] first explore an association between the weight divergence and the non-IIDness of the data, and propose a method to share a small amount of data among the server and all clients. As a result, the accuracy can be increased by  30% for the CIFAR-10 dataset [40] with only 5% globally shared data. [102] further improves the privacy of this approach by sharing the average of local data points, instead of raw data. Specifically, each client uploads averaged data, receives averaged data from other clients, and performs Mixup [104] data augmentation locally to alleviate weight divergence. However, both methods require modification of the standard FL protocol and transmission of data. Another way to improve privacy is to share synthetic data generated by generative adversarial networks (GANs) [28], instead of the raw data. The synthetic data can be a collection of each client’s synthetic data generated with local GANs or generated with one global GAN trained in FL [67, 12]. However, it is unclear whether GAN can provide enough privacy, since it may memorize the training data [4].

Modifying local update. Another line of research works modifies the local update procedure to alleviate weight divergence without changing the communication protocol of FL. FedProx [47] adds a proximal term to the local objective to stabilize the training procedure. The proximal term is the squared L2 distance between the current global model and the local model, which prevents the local model from drifting too far from the global model. SCAFFOLD [38] estimates how local updates deviate from the global update, and it then corrects the local updates via variance reduction. Based on the intuition that the global model can learn better representation than local models, MOON [45] conducts contrastive learning at the model level, encouraging the agreement of representation learned by the local and global models.

While the aforementioned algorithms can accelerate the model optimization for GFL, one model may not always be ideal for all participating clients [72]. Recently, personalized federated learning (PFL) has been proposed to tackle this challenge. PFL allows FL clients to collaboratively train machine learning models while each client can have different model parameters.

Clustered FL. In clustered FL, clients are partitioned into non-overlapping groups. Clients in the same group will share the same model, while clients from different groups can have different model parameters. In IFCA [27], $k$ models are initialized and transmitted to all clients in each communication round, and each client picks the model with the smallest loss value to optimize. FedCluster [72] iteratively bipartition the clients based on their cosine similarity of gradients. GCFL [95] generalizes this idea to graph data, enabling collaborative training with graphs from different domains. Observing that the gradients of GNNs can be fluctuating, GCFL+ [95] uses a gradient sequence-based clustering mechanism to form more robust clusters.

Personalized Modules. Another prevalent way for PFL is personalized modules. In these works, the machine learning model is divided into two parts: the shared part and the personalized part. The key is to design a model structure suitable for personalization. For example, when a model is split into a feature extractor and classifier, FedPer [2] shares the feature extractor and personalizes the classifier, while LG-FedAvg [49] personalizes the feature extractor and shares the classifier. Similar techniques in used in FMTGL [54] and NGL-FedRep [80]. Moreover, PartialFed [75] can automatically select which layers to personalize and which layers to share. On graph data, [78] observe that while the feature information can be very different, some structural properties are shared by various domains, revealing the great potential for sharing structural information in FL. Inspired by this, they propose FedStar that trains a feature-structure decoupled GNN. The structural encoder is globally shared across all clients, while the feature-based knowledge is personalized.

Local Finetuning and Meta-Learning. Finetuning is widely used for PFL. In these works, a global model is first trained with all clients. The global model encodes the information of the population but may not adapt to each client’s own distribution. Therefore, each client locally finetunes the global model with a few steps of gradient descent. Besides vanilla finetuning, Per-FedAvg [13] combines FL with MAML [15], an algorithm for meta-learning, to improve the performance of finetuning. Similarly, pFedMe [10] utilize Moreau Envelopes for personalization. It adds a proximal term to the local finetuning objective, and aims to find a local model near the global model, with just a few steps of gradient descent. GraphFL [83] applies a similar meta-learning framework on graph data, addressing the heterogeneity among graph data and handling new label domains with a few new labeled nodes.

Multi-task Learning. PFL is also studied within the framework of multi-task learning. MOCHA [73] uses a matrix to model the similarity among each pair of clients. Clients with similar distribution will be encouraged to have similar model parameters. FedGMTL [31] generalizes this idea to graph data. Similarly, SemiGraphFL [79] computes pairwise cosine similarity among clients’ hidden representations. As a result, clients with more similar data will have greater mutual influence. However, it requires the transmission of hidden representation. FedEM [57] assumes that each client’s distribution is a mixture of unknown underlying distributions and proposes FedEM, an EM-like algorithm for multi-task FL. Finally, FedFOMO [107] allows each client to have a different mixture weight of local models during the aggregation steps. It provides a flexible way for model aggregation.

Graph Structure Augmentation. In the previous works, graph structures are considered as ground truth. However, graphs can be noisy or incomplete, which can hurt the performance of GNNs. To tackle incomplete graph structures, FedGSL [109] optimizes the local client’s graph and GNN parameters simultaneously.

When the cross-client edges are available, the major challenge is to enable cross-client information propagation without leaking raw data. FedGraph [8] designs a novel cross-client convolution operation to avoid sharing raw data across clients. It avoids exchanging representations in the first GCN layer. Similarly, FedPNS [11] control the number of neighbor sampling to reduce communication costs. FedCog [43] proposes graph decoupling operation, splitting local graph to internal graph and border graph. The graph convolution is accordingly divided into two sequential steps: internal propagation and border propagation. In this process, each client sends the intermediate representation of internal nodes to other clients. Considering that directly exchanging feature representations between clients can leak private information. In user-item graphs, FedPerGNN [92] design a privacy-preserving user-item graph expansion protocol. Clients upload encrypted item IDs to the trusted server, and the server matches the ciphertexts of item IDs to find clients with overlapping item IDs. DP-FedRec [65] uses private set intersection to exchange the edges information between clients and applies differential privacy techniques to further protect privacy. Different from the above methods, FedGCN [98] does not rely on communication between clients. Instead, it transmits all the information needed to train a GCN between the server and each client, only once before the training. Moreover, each node at a given client only needs to know the accumulated information about the node’s neighbors, which reduces possible privacy leakage.

For some applications, the cross-client edges can be missing or not stored in any clients. Notice that although each client also holds a disjoint graph in graph-level FL, graph-level FL and subgraph-level FL with missing neighbors are substantially different. For graph-level FL, there are essentially no cross-client edges. For example, there are no chemical bonds between two molecules from different corporations’ datasets. However, for subgraph-level FL, the cross-client edges exist, but are missing in certain applications. We may get suboptimal GNN models if ignoring the existence of cross-client edges. Therefore, the major challenge is to reconstruct these missing edges, or reconstruct missing neighbors for each node.

FedSAGE [106] first defines the missing neighbors’ challenge, and proposes a method the generate pseudo neighbors for each node. It uses existing subgraphs to train a neighbors generator and generate one-hop neighbors for each client to mend the graph. Since missing neighbors are generated locally, no feature exchange is required between clients after the local subgraphs are mended. However, the training of neighbor generators requires cross-client hidden representation exchanges. Similarly, FedNI [63] uses a graph GAN model to generate missing nodes and edges.

Traditional FL relies on a central server to enable communication among clients. Each client trusts the central server and uploads their model update to the server. However, in many scenarios, a trusted central server may not exist. Even when a central server exists, it may be expensive for clients to communicate with the server. Therefore, serverless FL (a.k.a. peer-to-peer FL) has been studied to relieve communication constraints.

The standard solution for serverless FL is fully decentralized FL [42, 41], where each client only averages its model parameter with its neighbors. D-FedGNN [62] uses these techniques to train GNN models. SpreadGNN [31] generalizes this framework to personalized FL, where each client has non-IID data and a different label space.

When the central server is available, a graph of clients may still be beneficial when it models distributional relationships among clients. When edges link clients with highly similar distributions, parameter sharing along edges can potentially improve the model performance for both clients. When edges link clients with data dependency, information exchange along edges can even provide additional features for inference.

FedGS [89] models the data correlations of clients with a data-distribution-dependency graph, and improves the unbiasedness of the client sampling process. Meanwhile, SFL [9] assumes a pre-defined client relation graph stored on the server, and the client-centric model aggregation is conducted along the relation graph’s structure. GraphFL [108] considers client-side information to encourage similar clients to have similar models. BiG-Fed [96] applies graph convolution on the client graph, so each client’s prediction can benefit from its neighbors with highly correlated data. Finally, [86] designs a client sampling technique considers both communication cost and distribution similarity.

Finally, we summarize the official implementation of FL algorithms and useful repositories in Table 2.

In previous works of graph-level FL, although each FL client usually has different data distribution it is usually assumed that the model architecture is shared across all clients. However, the optimal architecture for different clients can be different. For example, a well-known issue in GNNs is the over-smoothing problem. When the number of graph convolutional layers is higher than the diameter of the graph, GNN models may learn similar representations for all nodes in the graph, which harms the model performance. When each FL clients hold a substantially different size of graphs, it is highly likely that the optimal depth of the GNN model is different for them.

Most of the previous subgraph-level FL algorithms highly rely on direct information exchange along cross-client edges. While such operations are natural variants of graph convolution, such operations also raise privacy concerns. Moreover, different from traditional FL where each client downloads aggregated model parameters that reveal the population, feature exchange along the edges can expose information about individuals. It would be beneficial if the cross-client transmission can be avoided without greatly degrading the model.

When combining privacy-preserving data generation with computation, noises are added to both raw data and model parameters. However, it is still unclear how to distribute the privacy budget between data generation and computation in a way that optimizes the privacy-utility trade-off. In this approach, noises are added to the graph data during data generation and to the model parameters during data computation (i.e., federated learning), which results in an overall reduction in accuracy. However, while the privacy analysis for data generation is directly defined on the data space, the privacy analysis for federated learning requires transforming the change on parameter space back to data space. Such transformation requires estimating the sensitivity of a machine learning algorithm (i.e., how the change of a data point affects the learned parameters), which is only loosely bounded in current works [59, 91]. A more precise analysis of privacy is required to better understand the impact of privacy budget allocation on the overall privacy-utility trade-off.

Another future challenge when combining privacy-preserving data generation and computation is the disentanglement of task-relevant and task-irrelevant information. Currently, the noise added to the model parameters is isotropic, meaning that task-relevant and task-irrelevant information are equally protected. However, not all information is equally important for model utility. If we can identify which information has a significant influence on model performance, we can distribute more privacy budget to this information while allocating less privacy budget to task-irrelevant information. This can result in a better privacy-utility trade-off. Disentangling task-relevant and task-irrelevant information would require a more sophisticated analysis of model architecture and data characteristics to determine which features contribute most to model performance.