text:
\section*{Appendix}

\subsection{Expectations for Revision}
\vspace{0.5cm}
\setcounter{expectation}{0}

\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Stealthiness)}:
\textit{Discuss alternative detection strategies which would reduce the number of queries used in the attack (perhaps at the cost of performance, \eg, Precision). }
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We have pointed out the stealthiness issue and alternative detection strategies in~\Cref{sec:dp-bound} and concretely discussed the details in~\Cref{sec:append-stealthy}.

In particular, we describe details of potential detection strategies as follows. First, a defender can use validation data to evaluate both the attack and benign query performance in terms of the attack F1-score and query node classification accuracy under different query limits.
Then the defender could optimize a query limit $Q$ which decreases the attack performance while maintaining reasonable benign query accuracy. Such a query limit would depend on the properties of different datasets and how safety-critical the application is. Note that in general limiting the number of queries will not affect the performance for a single user, while it would hurt if several users aim to query about the same set of nodes, thus the query limit could be made for each node. In practice, the defender can directly flag the users who try to exceed the query limit $Q$ for a limited set of nodes as suspicious for further inspection.

\vspace{0.5cm}
\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Choice of parameters)}:
\textit{Ensure that all parameters are selected during validation and final performance determined during testing.}
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We have followed the suggestion to select the privacy parameter $\varepsilon$ based on the validation set, and then report the final performance on the testing set.
The results are added to~\Cref{sec:eval-dp-util} and~\Cref{sec:append-choice}.

Basically, when selecting $\varepsilon$ on the \textit{validation set}, we set a lower threshold for the model utility, and select the smallest $\varepsilon$ satisfying the condition that the utility of the trained DP-GCN on the validation set is higher than the given threshold. (One example threshold is the F1-score of the MLP model.) Then, we evaluate both the model utility and attack success rate under the selected $\varepsilon$ on the \textit{testing set}.

We additionally point out that the added results serve as the supplementary result to our current results in~\Cref{fig:dp-attack} and analysis in~\Cref{sec:eval-dp-util} and~\Cref{sec:tradeoff}, where we aim to show the existence of a tradeoff between model utility and privacy, as well as the dependencies of the tradeoff, which are interesting and novel findings of the work.

\vspace{0.5cm}
\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Density belief)}:
\textit{Discuss actionable strategies for the attacker given limited knowledge of the density $k$ and/or strategies to improve the accuracy of the density belief. Tone down claims that estimation of $k$ is unimportant and frame the discussion with respect to the observed Precision and Recall rather than the broad performance across all $\hat{k}$s.}
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We completely agree and appreciate that the reviewers point this out. $k$ is indeed important and our previous observation was that overall it is not too sensitive. We have:

\begin{enumerate}
    \item toned down the claim that the estimation of $k$ is unimportant and presented finer-grained discussions, as suggested, for Precision and Recall rather than overall performance in~\Cref{sec:attack-eval}.
    \item provided discussion on the actionable strategies for the attacker given limited knowledge of the density $k$ and/or strategies to improve the accuracy of the density belief in~\Cref{sec:oracles} and~\Cref{sec:append-belief}. For example, the attacker could use some similar publicly available graphs (\eg, a similar social network) or partial graphs to estimate $k$. Specifically:
    \begin{enumerate}
        \item The attacker could estimate $k$ based on partial graph information (as suggested by Reviewer A). With the prior knowledge of some connected/unconnected pairs, the attacker can calculate the influence values for each known pair. Then, she can estimate a threshold for distinguishing the connected pairs from the unconnected ones with high confidence, and thus obtain the estimated density belief $\hat k$.
        \item The attacker could estimate $k$ based on the relationship of one or a few particular nodes (as suggested by Reviewer C). The attacker can start from an intentionally low $\hat k$ and increase it until an edge is inferred for the relationship, or until the known existing edges are inferred. The attacker then stops at this specific $\hat k$ and takes it as the density belief.
        \item The attacker could estimate $k$ by running a link prediction algorithm. When a partial graph is available, the attacker can run a link prediction algorithm, \eg, training a link prediction model, to predict all edges in the graph. Based on the predictions, the attacker will then obtain a rough estimate of the density belief $\hat k$ for use in \linkteller.
    \end{enumerate}
\end{enumerate}

\vspace{0.5cm}
\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Attacker capabilities)}:
\textit{Discuss how the attack might change in settings where the attacker's capabilities are stronger or weaker. For example, where they have additional knowledge of some edges or can only control a subset of node features.}
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We have discussed the variations of our attack under different settings of various attacker capabilities in~\Cref{sec:oracles} and~\Cref{sec:append-capable}, with a focus on the two settings outlined by the reviewers.

\ul{When the attacker has additional knowledge of some edges}: The attacker's prior knowledge on the existence of some edges can be leveraged to improve the density belief $\hat k$ in our \linkteller. More concretely, based on the knowledge of some edges, the attacker can calculate their influence values. Then, she can estimate a threshold for distinguishing the edges from the unconnected pairs with high confidence, and then obtain a refined estimation of the density belief $\hat k$. The attack effectiveness will subsequently be improved.

\ul{When the attacker has only partial control over a subset of node features}: We thank Reviewer A for clarifying the setting. In this setting, part of the feature information is lost, and thus the accuracy of the estimation of the influence value would be negatively impacted, leading to the decrease of attack performance. However, how much the attack effectiveness will degrade also depends on the importance of the missing features.

\vspace{0.5cm}
\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Other architectures)}:
\textit{Clarify that the GAT experiment evaluates the \textit{transferability} of the attack from a GCN. Reason about the performance in this setting and outline the limitations that future work must overcome to adapt \linkteller to other architectures. }
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We have followed the reviewers' suggestion and clarify the goal of our GAT experiment on \textit{transferability} and provide more discussion about its performance in~\Cref{sec:attack-gat}, as detailed below.

The GAT experiment mainly aims to investigate the \textit{transferability} of our influence analysis based attack from GCNs, as both of them perform information propagation guided by the graph structure. However, since the structures of GCNs and GATs are different, the exact influence calculation for the two models shall be different (one related to the graph convolution, the other related to the attention mechanism). As revealed by the experiment, the influence calculation is indeed not directly generalizable, leading to the lower attack performance of \linkteller on GAT, and interestingly, it is still much higher than baseline methods.

We have also added the discussion on the limitations to overcome in adapting \linkteller to other architectures in~\Cref{sec:append-limit}. First and foremost, in order to achieve high attack effectiveness, we need to derive exact influence calculations for different GNN structures specifically. We believe that our influence analysis based framework has the potential to perform well on different GNN structures with the influence value calculation tailored to each of them. Another potential obstacle in the adaptation is that \linkteller cannot deal with randomized models, such as the aggregation over sampled neighbors in GraphSAGE~\cite{hamilton17graphsage}. It could be an interesting future work to take such randomness into account for influence calculation.

\vspace{0.5cm}
\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Hard labels)}:
\textit{Discuss how the attack might be adapted when logits are not available (as included in the rebuttal). }
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We have added the discussion in~\Cref{sec:append-capable} which focuses on the variations of the settings. We explain that it is not straightforward to adapt our \linkteller to handle the case where logits are not available, which belongs to the "decision based blackbox attack category" rather than the score based. There are a few works~\cite{brendel2017decision,dong2019efficient} in the image domain that perform certain decision-based blackbox attacks. However, how to estimate the gradient/influence value in GNNs based on decision remains an interesting future direction.

\vspace{0.5cm}
\stepcounter{expectation}
\noindent \textbf{Expectation \theexpectation}
\textbf{(Baselines)}:
\textit{Provide more clarity on the reasons for the poor performance of the baselines. }
\vspace{0.2cm}

\noindent \underline{\textbf{Response}:}
We have added more clarifications for the poor performance of the baselines and conducted additional experiments to compare \linkteller with baselines in trasductive setting in~\Cref{sec:attack-eval} and~\Cref{sec:append-baseline-cmp}.

First of all, we note that LSA-X~\cite{he2020stealing} relies on measuring certain distances based on either posteriors (of the node classification model) or node attributes to predict the connections. However, node classification and edge inference (i.e., privacy attack goal here) are two distinct tasks, and node features (or posteriors) are useful for node classification does not mean that they will be useful for edge inference. Thus, LSA-X which tries to provide the attacker with different levels of node information as prior knowledge to perform the edge re-identification attack is not effective. On the contrary, \linkteller tries to analyze the influence between nodes, which reflects the edge connection information based on our theoretical analysis (\Cref{thm:k-layer-gcn}) and is indeed more effective for edge inference as we show empirically.

We point out that, to our best knowledge, there are no such settings where \linkteller may fail but other existing approaches (\eg, LSA-X) may succeed. The detailed reasons are provided above. To summarize, our \linkteller leverages the edge influence information, which is more relevant for the task of edge re-identification attack than purely node level information used in LSA-X and we have add the discussion in~\Cref{sec:append-baseline-cmp}. We then discuss the two specific scenarios outlined by the reviewers.

\ul{If the model makes inferences on single nodes and not subgraphs}: In this case, \linkteller cannot obtain influence information between nodes of interests, and thus the edge re-identification performance would be less effective. Similarly for the baselines, where they would fail to calculate the statistics of a set of nodes to compare their similarity. That is to say, if the model makes inferences on single nodes, both \linkteller and baselines may fail to effectively attack, while \linkteller may still outperform baselines given that it leverages the influence value of edges explicitly.

\ul{If the inference is transductive vs. inductive}: We first point out that the inductive setting is more challenging than the transductive setting, where the inference nodes are already included in the training graph. We then analyze the potential performance of \linkteller in the transductive setting. \linkteller is naturally applicable to the transductive setting. Since these nodes are involved in model training, the influence value and the rank may be more accurate, leading to even better attack performance. Thus, we expect that \linkteller will achieve better performance in the transductive setting and retain its advantage over LSA-X.

We have conducted additional experiments as shown in~\Cref{sec:append-trans} comparing \linkteller to LSA-X using the datasets and evaluation protocols from He \etal~\cite{he2020stealing}, and we show that \linkteller still outperforms the baselines in the trasductive setting.

\iffalse
\subsection{Responses and Revisions to  Detailed Reviews}
\label{sec-A2}

\fan{the responses here in Section B are not reflected in the revision yet--we can discuss and decide whether and what to include}

\subsubsection{General Response}~\\
\stepcounter{comment}
\noindent \textbf{Threat Model:}
Does the threat model *require* Bob to supply part of the training data (the nodes) or is this just to show the typical setting? The attack itself seems to start at inference time (RA, RB, RC, RD).
\begin{itemize}[leftmargin=*]
    \item[--] If so, how much control over the nodes does Bob need? (RA)
    \item[--] Are there variations of this threat model for which the attack would still succeed (e.g., partial knowledge of edges) (RA)?
    \item[--] If possible, can the authors give more real-world instantiations of this threat model (RA, RC, RD)?
\end{itemize}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewers for the helpful question and suggestions.
We clarify that indeed the threat model does not require Bob to supply training data. We are sorry for the confusion, and we will update our paper by using another agent to provide the training data instead of Bob.
In particular, the GNN model can be trained using local data or data provided by \textit{any} user, and then deployed as a cloud service with a blackbox API exposed to users.
\begin{itemize}[leftmargin=*]
    \item[--] Bob only needs the node features of the set of nodes that he is interested in during inference.
    \item[--] Indeed, if the attacker has partial knowledge w.r.t. the existence of some edges, this prior knowledge can actually be leveraged to improve the process of \linkteller.
Assuming Bob has the prior knowledge of some connected/unconnected pairs,
after calculating the influence value for each pair,
he can obtain a distribution of the influence values, and thus estimate the threshold for distinguishing the connected pairs from the unconnected ones with high confidence.
In another word, such prior knowledge can help to estimate the \textit{density belief} in our algorithm, leading to potentially more successful attack.
    \item[--]
    We first provide the abstract example. In our threat model, Alice and Bob could belong to different departments of the same company and Alice provides API access to other departments by training models with their (social) connection data, and she cannot transfer such connection data due to privacy concerns. If Bob is adversarial, he is particularly interested in the relationship between some nodes (\eg, product, personnel) out of personal interest, and thus conduct the privacy attacks to inference certain edge connections.

We then refer to some real-world instantiations.
On one hand, in particular, the similar vertically data split setting in graph data is also discussed in Zhou \etal~\cite{zhou2020privacy}.
On the other hand, our work is inspired
by one realistic scenario from our
industrial collaborations, which we will
include in the revised version of this paper. Specifically, a large Internet company that
we work with has two divisions, one
focuses on recommendations and another focuses on financial services. One division
has data about user interactions (the graph)
while the other division has more features and labels about a user. For policy reason, one cannot copy data across division boundaries, and can only happen in a differentially private way. In this case, one division becomes
Alice and the other becomes Bob.
This is one real-world
instantiation of our setting.

In addition, nowadays there are several ML/AI services/platforms that take the training data from users and help them to train  ML models as  queryable APIs, such as Vertex AI~\cite{VertexAI} from Google Cloud,  ParlAI platform~\cite{ParlAI} from Facebook AI, and  InfoSphere Virtual Data Pipeline~\cite{InfoSphe} from IBM.
Thus, against these real-world cloud services, such threat model could lead to potential privacy concerns or even severe consequences.

\end{itemize}

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Parameters:}
The attack is somewhat sensitive to the parameters.
\begin{itemize}[leftmargin=*]
    \item[--] Results regarding the best parameters (e.g., privacy budget) are obtained by analyzing test data, is it expected that practitioners could obtain similar performance by calibrating on validation data? (RB)
    \item[--] The Precision-Recall tradeoff seems highly dependent on $k$, would an attacker be able to take action on the output of the attack despite the high variance here? (RC)
\end{itemize}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewers for the insightful question.
\begin{itemize}[leftmargin=*]
    \item[--]
    We provide clarifications on the privacy parameter ${\epsilon}$ from the following two aspects.
    \underline{First},
one of our initial goals on such trade-off evaluation is to investigate and present the existence of such a trade-off,
as well as its dependence on the dataset type (\eg, whether and how much the graph structure helps) and the degree distribution of the interested nodes (\eg, low degree nodes); the existence of the trade-off and its dependencies are interesting and novel findings of this work.
\underline{Second},
determining parameters via a validation dataset and evaluating the parameters on the testset can be expected to give similar performance, since the validation dataset and the testset are in similar distributions.
There is one case where the practitioner might suffer a performance degradation---when the graph is very sparse, the validation set may not be able to provide good insights on the performance on the test set.
Otherwise, it is expected that practitioners could obtain similar performance by calibrating on validation data, and we will follow the suggestion to conduct experiments in our revision.
    \item[--]
    Regarding the density belief parameter $\hat k$, from our evaluation in Table I (under the worst case where the attacker has no knowledge about $k$), we can see that even wrong belief $\hat k$ (\eg, $\hat k=k/4$ or $4k$) provides reasonable attack success rate (far outperforming the baselines).
    On top of that, with some prior knowledge on the existence of some edges,
    we can allow the attacker to achieve better attack performance by first estimating the density belief $\hat k$ via calculating the influence value for each known pair and obtaining the value distribution.
In another word, the attacker can achieve reasonable attack performance without any knowledge of $k$, while the attack can be further improved by leveraging certain prior knowledge to estimate $\hat k$.

\end{itemize}

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Baselines:}
Are the authors able to elaborate on why the baselines (LSA-X, etc) perform so poorly? (RB, RC)

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewers for the helpful question.
First,
we note that LSA-X~\cite{he2020stealing} rely on measuring certain distances based on either posteriors (of the node classification model) or node attributes to predict the connections.
However, node classification and edge inference (\ie, privacy attack goal here) are two distinct tasks, and node features (or posteriors) are useful for node classification does not mean that they will be useful for edge inference.
Thus, LSA-X which tries to provide the attacker with different levels of node information as prior knowledge to perform the edge re-identification attack is not very effective. On the contrary, \linkteller tries to analyze the influence between nodes, which reflects the edge connection information based on our theoretical analysis (Theorem 1) and is indeed more effective for edge inference as we show empirically in~\Cref{tab:att-np} and~\Cref{tab:att-np-auc}.

We provide some additional evidence that supports the point that node features may not be very useful for edge inference.
On some of the datasets (\eg, twitch-\{DE, ENGB\} and PPI), the performance of MLP (relying only on node features) are quite good,
indicating that
the gains from incorporating \textit{graph structures} into the node classification task are marginal,
further implying the weak correlation between node features and the graph structure.
Thus, node feature information is far from sufficient in the edge inference task, which also explains the poor performance of LSA-X~\cite{he2020stealing}.
We will make these discussions more clear in our revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Stealthiness:}
While the runtime of the attack is small, do the authors agree that the number of queries may become quite high, which would make the attack easier to detect? Can they imagine potential mitigation strategies given this observation? (RB)

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the interesting question and suggestion.
We agree that the number of queries will become quite high in the case when the attacker has a \textit{large} set of interested nodes (and thus inference nodes), since the query number is equal to $|V^{(I)}|$ in our algorithm.

Following the suggestion, we believe it is possible to evaluate the precision of the {attack} depending on the size of
$V^{(I)}$ and $V^{(C)}$ to understand the impact of the number of attempts on the attack. If such impact is significant, we can potentially check the distribution of query numbers of different users and  identify the adversaries who may query specific nodes with high frequency. We will add the discussion in our revision.

\subsubsection{Reviewer A} ~\\
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{The scenario in which the adversary knows and provides the node features for training the GNN may have somewhat limited applicability. Can you add more discussion about possible real-world instantiations of this scenario?}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the question.
We want to clarify that in our interaction model, we only need the \textit{users} to provide training information (\ie, node features), but such information does not need to come from the \textit{adversary}. The adversary only needs to provide the information of interested nodes during testing (attack) time. We will make our setting more clear in the revision.

Nowadays there are several ML/AI services/platforms that take the training data from  users and help users to train an ML model based on the provided data.
Vertex AI~\cite{VertexAI} from Google Cloud is such a unified platform that can help users train a built-in algorithm against their provided datasets without requiring the users to write a training application~\cite{vertexai-train-overview}.
They provide easy-to-use services, APIs, and client libraries that facilitate the process~\cite{vertexai-train-api}.
The ParlAI platform~\cite{ParlAI} from Facebook AI as well as the InfoSphere Virtual Data Pipeline~\cite{InfoSphe} from IBM also provide similar services.
Our interaction model is an abstraction of these prevalent ML services.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Can the setting be broadened in some way e.g. giving the attacker only partial control over the nodes, or control over only some of the nodes? Can it be adapted to settings in which the adjacency matrix takes values in the range [0,1] to indicate different strengths of the connection?}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the thoughtful comment and suggestions.
For the \underline{first} suggestion, we would like to clarify that the attacker does not have full control over all nodes. In fact, in the inference stage, Bob only queries the set of nodes that he has control over and is interested in by passing in the features of these nodes.
For the \underline{second} suggestion: Yes, both the GCN model and our \linkteller can be easily extended to the case of weighted adjacency matrix.
In terms of GCN, several works~\cite{liu2019higher,zhou2020weighted} have specifically studied weighted GCNs to account for connections of different strength (\eg, higher order connections).
Regarding our \linkteller, the real-valued weighted adjacency matrix will directly translate into our influence value calculation.
We will add related discussion in the paper.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Does the attack change if the attacker already knows some of the edges? If so, could this be used to improve the process of inferring edges e.g., once the attacker is sufficiently certain that there is an edge between nodes u and v, adjusting the influence matrix accordingly to account for this?}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the excellent point.
Indeed, the prior knowledge of the attacker w.r.t. the existence of some edges can be further leveraged to improve the process of \linkteller.
For instance, assuming Bob has the prior knowledge of some connected pairs and unconnected pairs,
after calculating the influence value for each pair,
he can obtain a distribution of the influence values for the connected/unconnected pairs, and thus estimating the threshold for distinguishing the connected pairs from the unconnected ones with high confidence.
In another word, such prior knowledge can help to estimate the \textit{density belief} in our algorithm, leading to a potentially more successful attack, and we will add related discussion in the paper.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Minor points including the abbreviation (GCN) and the typos (Alice and twitch-DE).}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for pointing them out. We will make corresponding updates in the revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Section 5F: the performance on GATs is described as ``slightly lower'' than on GCNs, but the differences between Tables 1 and 3 looks quite significant.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for pointing it out.
Indeed, we will update our description to be precise.
We explain the differences between Table 1 (attack performance against GCNs) and Table 3 (attack performance against GATs) as follows.
Since the structures of GCNs and GATs are different, the exact influence calculation for the two models shall be different (one related to the graph convolution, the other related to the attention mechanism).
In our experiment, we directly apply \linkteller with the influence calculation derived on GCNs to GATs, aiming to evaluate the \textit{transferability} of our influence analysis based attack.
As revealed by the experiment, the influence calculation is not directly generalizable, and it is an interseting future work to derive the influence calculations for different GNN structures.
In the revision, we will adjust our statement and add the above discussion.

\vspace{0.5cm}
\subsubsection{Reviewer B}~\\
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{For instance, a \textbf{more detailed evaluation of the number of GNN layers} would be interesting.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the helpful suggestion.
We have provided results for $2$-layer GCNs in Section V-E and $3$-layer GATs in Section V-F in the main paper, as well as results for 3-layer GCNs and analysis of $1$-layer and more than $3$-layer GCNs in Appendix E2.
In the revision, we will add additional evaluations on GNN with more layers and add corresponding analysis of the number of GNN layers.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Moreover, I am somewhat torn by the described setting: While the authors argue for a ``jointly trained'' model, the setting, as a matter of fact, describes a remotely deployed model with a user querying inputs. As the adversary is not using the knowledge of the training data, there is no need to consider this more complex and maybe more ``exotic'' scenario.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for pointing this out.
Sorry for this confusion in our interaction model: Indeed, we do not need the adversary to have knowledge of training data. We will make
this clear in our revision by introducing another user who provides the training data, rather than using the same user ``Bob".

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{The proposed attack queries the same set of testing samples $V^{(I)}$ multiple times ($n=|V^{(C)}|$) with one sample slightly altered to infer the relations among the nodes (in the presented experiments $|V^{(I)}|=|V^{(C)}|=500$). This significantly increases the number of queries conducted by the adversary, which, in turn, may allow to detect the attack easily.
The authors give this a casual brush-off by stating that the runtime of the attack is relatively small (tens of seconds according to Table VIII in Appendix E-4). While this might be acceptable in this specific scenario, I want to motivate the authors to \textbf{discuss alternative detection strategies based on the queries themselves}. For instance, one could evaluate the precision of the attack depending on the size of $V^{(I)}$ and $V^{(C)}$.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the comment.
We will follow the suggestion to discuss alternative detection strategies.
Following the suggestion, we would evaluate the precision of the {attack} depending on the size of
$V^{(I)}$ and $V^{(C)}$ to understand the impact of the number of attempts on the attack. If such impact is significant, we can potentially check the distribution of query numbers of different users and  identify the adversaries who may query specific nodes with high frequency. We will add the discussion in our revision.

In addition, we apologize for the typo in the evaluation section, where  $V^{(I)}$ should be replaced by $V^{(C)}$, and $|V^{(I)}|>|V^{(C)}|=500$.
Concretely,
for the twitch datasets, the set of inference nodes are all nodes in each test graph; for PPI and Flickr, we will add the detailed split (training/validation/testing) in dataset statistics in Table IV.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{\textbf{What is the influence of the dataset?} According to the presented experiments, the used datasets can be learned with MLPs as well. The F1 scores lie within 0.06 (Flicker) or less (*Please use equal ranges for the plots in Figure 3a*). The flicker dataset is also the one where the attack performs worst. Moreover, LSA-X has been evaluated on completely different datasets. For the sake of transparency, it would be great to have these datasets analyzed as well.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the comments and helpful suggestions.
We summarize the following properties of the dataset that will influence the F1 score and attack performance:
1) closeness of the training  and  testing graph in distribution;
2) sparsity of the graph.
In general, large difference in training and testing and severe sparsity of the graph will increase the difficulty of both training and attack.
For the poor performance on Flickr dataset, we provide an analysis at the end of Section V-E.
In short, given the highly sparse structure of the Flickr dataset, the trained GCN model on Flickr does not achieve good performance. This implies that the parameters of the trained network on this dataset may not capture the graph structure very well, and thus the attack performance is negatively influenced.
The sparsity also leads to the large variance in attack results which arises from node sampling.
We will follow the suggestion to use equal ranges for the plot.
Finally, we explain the distinction between the dataset selection in our paper and  the baseline LSA-X~\cite{he2020stealing}.
LSA-X was evaluated on datasets designed for \textit{transductive setting} while we focus on \textit{inductive setting} in our interaction model. Thus, we have to choose  datasets accordingly.
In fact, our \linkteller can also be generalized to transductive setting, and we will consider adding some experiments in our revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{\textbf{What are alternative ways of defense next to DP?} For most applications, it probably is not necessary to communicate the logits through the remote API. When reading the paper, I was wondering what would be necessary to conduct a similar attack if only the final class $c$ would be reported or a rank of the top-x classes. In other words, what are the limits of the attack in a slightly different but equally practical scenario: not leaking logits.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the interesting question.
Yes, as \linkteller requires the logits outputs as query results,  reporting only the final class $c$ or a rank of top-x classes would be a potential defense against \linkteller.
In addition, in the case where only the final class $c$  or a rank of the top-x classes would be reported, it will require more queries to perform certain decision based blackbox attacks in image domain~\cite{dong2019efficient,brendel2017decision}, and how to estimate the gradient/influence value in graphs is  an interesting future direction.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{\textbf{Why is LinkTeller superior to LSA-X (He et al., 2021)} The authors briefly address this in Section V-E but do not go into much detail. For instance, they say that LSA does not work because it relies on posteriors or node attributes. However, judging by the presented results using MLP, it seems perfectly manageable to learn the data at hand without any additional graph-based data.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the interesting question.
First,
we would like to clarify that the presented results of MLP represent the model's performance on node classification \emph{not} the performance of the attack.
Node classification and edge inference (\ie, privacy attack goal here) are two distinct tasks, and node features are useful for node classification does not mean that they will be useful for edge inference.
Thus, LSA-X which tries to provide the attacker with different levels of node information as prior knowledge to perform the edge re-identification attack is not very effective. On the contrary, \linkteller tries to analyze the influence between nodes, which would reflect the edge connection information based on our theoretical analysis (Theorem 1), and we show that such influence analysis is indeed effective for edge inference empirically.

In addition, the good performance of MLP (relying only on node features) on some datasets indicates that
the gains from incorporating \textit{graph structures} into the node classification task are marginal,
further implying the weak correlation between node features and the graph structure.
Thus, node features are far from sufficient in the edge inference task, which also explains the poor performance of LSA-X~\cite{he2020stealing}.
We will make these discussions more clear in our revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Finally, I would like to point the authors to their argumentation of choosing the correct parameters, such as the privacy budget $\epsilon$. In Section VI-D, ``Tradeoff between Model Utility and Privacy,'' it is suggested that it is possible to balance the individual objectives by inspecting the presented results. However, as these are determined on testing data (for which we do not have ground truth in practice), this is not possible but has to be done on validation data. That aspect can be easily fixed in the paper by more careful argumentation. However, I believe it would be worthwhile to demonstrate this in the experiments and \textbf{determine all parameters during validation (including $\epsilon$) and demonstrate performances with these on testing data}. This mimics reality as close as possible and would add a nice touch to the evaluation.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the suggestion.
We will definitely check and make more careful argumentation in our revision.
One of our initial goals on the evaluation is to investigate and present the existence of such a trade-off,
as well as its dependence on the dataset type (\eg, whether and how much the graph structure helps) and the degree distribution of the interested nodes (\eg, low degree nodes); the existence of the trade-off and its dependencies are novel findings of this work.
We will also follow the suggestion and will conduct experiments accordingly by determining parameters during validation and evaluating on the testset in our revision.

\vspace{0.5cm}
\subsubsection{Reviewer C}~\\
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{I think this is vital because the attacker doesn't know if their estimate is too high or too low, so they are not able to adjust their future actions based on the most likely outcome, i.e., they don't know if a particular edge is likely to be a true positive, whether they have many missing edges, or vice-versa, so it's difficult for them to act on the predictions. }

\textit{This could be improved by providing some actionable strategies for the attacker given limited knowledge of $k$. For example, if they're interested in a particular node relationship, can they start from an intentionally low $\hat{k}$ and increase it until an edge is inferred for this relationship. Then given the $\hat{k}$ at which the edge appears, can they estimate the likelihood of it being a true positive? }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the valuable suggestion.
Indeed, we can allow the attacker to estimate the density belief $\hat k$ first for better attack performance. For instance, assuming Bob has the prior knowledge of some connected pairs and unconnected pairs,
after calculating the influence value for each pair,
he can obtain a distribution of the influence values for the connected/unconnected pairs, and thus estimating the threshold for distinguishing them with high confidence.
In another word, even with limited knowledge of $k$, the attacker can leverage prior knowledge as such to obtain the density belief $\hat k$ which leads to potentially more successful attack.
In addition, from our evaluation under the worst case where the attacker has no knowledge about $k$, we can see from Table I that even wrong belief $\hat k$ (\eg, $\hat k=k/4$ or $4k$) provides reasonable attack success rate (outperforming the baselines).

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Note that the attacker goals are tightly linked to $n^{(I)} = |V^{(I)}|$, so considering values other than 500 would be really beneficial here. }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the suggestion.
We will provide additional experimental results with values other than $500$ in the revision for the comprehensiveness of the evaluation.
Note that here we randomly picked the number 500 without any tuning and we \textit{randomly} sampled the set of nodes of interest for attack.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Also related to $k$: it's not clear what value is used for the setting in Table II which has extremely high AUC-PR. Presumably it was fixed at some value to fit the setting in prior work. }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the question.
We clarify that in the calculation of AUC-PR, the knowledge of $k$ is not required.
Overall, the AUC-PR value gives an evaluation of the performance of a binary classifier under a series of $k$ (as explained below).
Basically, to calculate AUC-PR, we only need the influence value of each connected/unconnected pair. Then, we can sort the pairs increasingly by their influence values. At each pair, we can compute a precision/recall value to obtain a PR curve. The AUC-PR value is thus the area under the PR curve.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{The attack performance in some settings is quite low; namely for the Flikr dataset and when applied to the GAT—for which it is extremely low. In addition, the claim that ``LinkTeller has the potential to generalize to other GNNs'' seems unsubstantiated (§V.F). It's also noted that the ``influence based analysis does imply some fundamental common characteristics of GNNs which could lead to other future research'' (§V.F) but these common characteristics are not mentioned. }

\textit{I would consider this experiment a bonus result, but these statements should be toned down—although I think it could also be a really valuable opportunity to reason about these characteristics. Conceptually, why should LinkTeller generalize to other architectures like GAT? How does the information propagation manifest in different architectures? From LinkTeller's perspective, does the attention mechanism in GAT play a similar role to the convolutions in the GCN? The performance is considerably lower, why might this be? What are the limitations that future work must overcome to adapt LinkTeller to other architectures?  }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the comment and the thoughtful suggestions.
We will provide explanations from two aspects.
\underline{First}, the attack performance of \linkteller on the Flickr dataset  is not quite high, and we have analyzed the potential reason at the end of Section V-E.
Basically, due to the highly sparse structure of the Flickr dataset, the trained GCN model does not achieve good performance, and thus the parameters of the trained network may not capture the graph structure very well, leading to the poor attack performance.
\underline{Second}, our goal of applying \linkteller to GAT is to investigate the generalizability of our influence analysis based attack, as both of them perform information propagation guided by graph structure.

However, as revealed by the experimental results,
a more exact influence calculation for the GAT model is needed to achieve high attack performance.
We believe that  \linkteller framework has the potential to perform well on different GNN structures with the influence value calculation  tailored to each of them.
One potential limitation in adapting \linkteller to other architectures is that \linkteller cannot deal with randomized models, such as the aggregation over sampled neighbors in GraphSAGE~\cite{hamilton17graphsage}, which could be an interesting future work to take such randomness into account for influence calculation.
In the revision, we will add corresponding discussions.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Another aspect of the evaluation which could use deeper analysis is the performance of the baselines which all fail, almost universally. It would be really valuable to explore why this is the case. Is it wholly due to their assumption that shadow datasets or partial graphs are available or is it that including information about node influence makes all the difference? }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the suggestion.
In our opinion, it is indeed the influence that gives us the huge advantage over their method.
We note that LSA2-\{post, attr\}~\cite{he2020stealing} rely on measuring certain distances based on either posteriors or node attributes to predict the connections.
However,
node classification and edge inference (\ie, privacy attack goal here) are two distinct tasks, and node features (or posteriors) are useful for node classification does not mean that they will  be useful for edge inference.
Thus, LSA2-\{post, attr\} is not very effective only leveraging these to perform the edge re-identification attack.
In comparison, \linkteller tries to analyze the influence between nodes, which reflects the edge connection information based on our theoretical analysis (Theorem 1) and is indeed more effective for edge inference empirically.

We provide some additional evidence that supports the point that node features may not be very useful for edge inference.
On some of the datasets (\eg, twitch-\{DE, ENGB\} and PPI), the performance of MLP (relying only on node features) are quite good,
indicating that
the gains from incorporating \textit{graph structures} into the node classification task are marginal,
further implying the weak correlation between node features and the graph structure.
Thus, node features are far from sufficient in the edge inference task, which also explains the poor performance of LSA2-\{post, attr\}~\cite{he2020stealing}.
We will make these discussions more clear in our revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{It doesn't seem that the LinkTeller attack requires the attacker to also provide the training nodes. Is it the case that the attacker can actually recover private edges from any pretrained cloud-based GCN (for example)? This would be a much stronger and more compelling attack.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the comment. We do not need to assume that the attacker provides the training data.
The attacker can actually recover private edges from any pretrained cloud-based GCN by querying the set of nodes of interest.
 We will make this clear in our revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{I might have missed something, but in the evaluation there is no $V^{(C)}$, only $V^{(I)}$, is it correct to assume that in the evaluation $V^{(C)} = V^{(I)}$ (i.e., all of the inference nodes are of interest)?}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We are sorry for the typo and we clarify that all $V^{(I)}$ in the evaluation section should be  $V^{(C)}$. In fact, $V^{(C)}$ is a subset sampled from $V^{(I)}$.
Concretely, for the twitch datasets, $V^{(I)}$ is the set of all nodes in each test graph; for PPI and Flickr, we will add the detailed split (training/validation/testing) in dataset statistics in Table IV.
$V^{(C)}$ is the subset of $V^{(I)}$ sampled following different criteria in terms of the node degree distribution.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{It's stated that ``$V$ can be a union of nodes in a group of graphs, as long as the grouping makes logical and practical sense'' (§III.A). Is this just describing a typical setting or is it an actual assumption required by the attack? }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We are sorry for the confusion.
Here we aim to describe a typical scenario in the inductive setting. We will consider removing the notation $V$ for clarity, since $V^{(T)}$ and $V^{(I)}$ are already sufficient for denoting the training and inference graph.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{It's stated that ``the attacker has no information about the API model except that it is a GNN model with unknown architecture and parameters'' (§III.B), however the attacker does also know the node training data. This is clear in context but should be explicit here.  }

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the comment.
This comment and the response are in fact associated with that in Comment 6.
The attacker does not need to know the training data. Only the information about the blackbox API and the features of nodes targeted by the attacker is sufficient for the attacker to carry out the attack.
We will modify relevant parts in the revision to make this more clear.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{In §IV.A I think it would be beneficial to give some quick intuition about why EdgeRand and LapGraph are differentially private when they're first mentioned here, or at least provide a forward pointer to their in-depth descriptions in §IV.B as the motivation of this subsection hinges on the DP guarantees of the perturbation methods.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the thoughtful suggestion and will add the discussion on the intuitions in the revision. Concretely, both \edgerand and \lapgraph are differentially private due to the perturbation of the adjacency matrix. The perturbation guarantees that the probability of getting the same perturbed matrix is close for two adjacency matrices differing by one edge. Specifically, \edgerand flips each entry in the adjacency matrix independently with a probability determined by the privacy budget. \lapgraph adds Laplacian noise to the adjacency matrix and uses the noisy density estimation to clip each entry of the adjacency matrix into 0 or 1. We will add these discussions in our revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{It would be useful if the y-axes of Figs. 3 and 4 were to the same scale, just to allow easier comparison between datasets.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the suggestion and will adjust the y-axes of the figures accordingly in the revision.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{As the values $d_{low}$ and $d_{high}$ are chosen ``empirically'' it would be useful to mention what kind of reasoning was used to pick them (§V.D).}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the question.
We choose nodes of different degrees to provide a more comprehensive evaluation of the performance of \linkteller under different scenarios (i.e., nodes of interest are of low/high degrees).
The values $d_{\rm low}$ and $d_{\rm high}$ are chosen by examining the node degree distribution of each specific graph.
We select the two values such that the total number of nodes with degree $\leq d_{\rm low}$ (or $\geq d_{\rm high}$) are of roughly similar scale.
For example, twitch datasets contain graphs of thousands of nodes and the node degree distribution is relatively more concentrated, so we pick the two values to be $5$ and $10$.
The consideration for some special cases such as twitch-PTBR, PPI, and Flickr are more concretely explained at the end of Section V-D.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Other abbreviations, typos, and statements.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for pointing them out, and we will update all of them in the revision.

\vspace{0.5cm}

\subsubsection{Reviewer D}~\\
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{Although I do understand the scenario/threat model the authors describe,
how realistic is it really for Bob to perform adversarial queries
against Alice's trained model to infer private information that wouldn't
have been ``copied'' over in the first place due to privacy concerns?
(The assumption and the concern here is that Bob and Alice belong to the
same company and while I do see why Alice won't be sharing information
due to privacy concerns, I do see less likely Bob performing such an
attack due to ethics and liability.) Don't get me wrong: the attack still
exists, and so does the vulnerability. It would however be more
convincing if the authors could clarify this further with real examples.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the question.
We refer to Zhou \etal~\cite{zhou2020privacy} for the vertically data split setting in graph data where each data holder holds partial node features and their own edges.
In particular, we would like to first give an \textit{abstract} example of our threat model---Alice and Bob belong to different departments of the same company. Alice provides API access to other departments of the company. Bob is particularly interested in the relationship between some nodes (\eg, product, personnel) out of personal interest.

In \textit{real-world scenarios}, there are several ML/AI services/platforms that take the training data from users and help users to train an ML model based on the provided data, such as Vertex AI~\cite{VertexAI} from Google Cloud, the ParlAI platform~\cite{ParlAI} from Facebook AI, and the InfoSphere Virtual Data Pipeline~\cite{InfoSphe} from IBM. Our interaction model is an abstraction of these prevalent ML services.
In our interaction model particularly,
we only need the \textit{users} to provide training information (\ie, node features), but such information does not need to come from the adversary. The \textit{adversary} only needs to provide the information of interested nodes during testing (attack) time.
We will make our setting more clear in the revision by introducing another user who provides the training data other than ``Bob''.

\vspace{0.5cm}
\stepcounter{comment}
\noindent \textbf{Comment \thecomment:}
\textit{In Section III.A, the authors mention that ``[...] during the inference
stage, Bob will collect node features of the inference graph $X^{(I)}$
(e.g., patients in the next months). What guarantees do we have that
$X^{(I)}$ does not introduce non-stationarity that would affect the
performance of the underlying model to start with? That might affect the
attack somehow although I don't have any intuition on how nor severity.
However, I am also assuming this to not really be a problem as that
would otherwise affect the underlying performance of the model and it
should have been quite visible to the authors.}

\vspace{0.2cm}
\noindent \textbf{\underline{Response:}}
We thank the reviewer for the thoughtful comment.
We would like to clarify that the task of the underlying model (\eg, public API) is to perform the node classification on the selected nodes $V^{(I)}$, while an adversary aims to infer the private edge connection information via such queries. That is to say, the performance of the underlying model is related with the inference node selection but would be less likely to be largely affected since the attacker did not manipulate any information.
We will make the discussion clear in our revision.

\fi

\section{Introduction}

Graph neural networks (GNNs) have been widely applied to different domains owing to their ability of modeling the high-dimensional feature and high-order adjacency information on both homogeneous and heterogeneous graph structured data~\cite{long2015fully,wei2019mmgcn,zhou2020privacy}.
The high-quality graph structured data have enabled a range of successful applications, including traffic prediction~\cite{zhao2020traffic}, recommendation systems~\cite{ying2018recommendation}, and abnormal access detection~\cite{jiang2019abnormal}.
As these applications are becoming more and more prevalent, privacy concerns in these applications are non-negligible given the sensitive information in the graph data. Thus, undesirable outcomes may arise due to lack of understanding of the models and application scenarios.

\begin{figure}[t!]
\centering
\includegraphics[width=1.0\columnwidth]{figures/pipeline.pdf}
\vspace{-1.5em}
\caption{\small Vertically partitioned graph  data for different data holders.}
\label{fig:pip}
\end{figure}

In this paper, we aim at
understanding the \textit{edge privacy} in applications
of GNN models. We
focus on one specific
 scenario as
\textit{training/serving GNN models
in a vertically partitioned graph
setting}. As illustrated in~\Cref{fig:pip},
in this setting, node features
and adjacency information (edges) are isolated or hosted by different data holders.
Our interest in
this setting is inspired
not only by recent academic research
(\eg, Zhou \etal~\cite{zhou2020privacy}
proposed a
privacy-preserving GNN (PPGNN) mechanism via homomorphic encryption
under this setting)
but also a real-world
industrial example we see and
the potential privacy risks it incurs. In such an example, an international
Internet company hopes to
train a single GNN model jointly
using data collected by two of its subdivisions (namely, data holder Alice and Bob). Because these subdivisions focus on different products, their data are heterogeneous in nature. Specifically, in this example,  Alice collects user interaction (social network) data (\ie, adjacency information), and
 Bob collects user behavior data (\ie, node features).
Noticing the potential benefit of
integrating user interaction
data into its predictive model,
 Bob hopes to enrich the
model using data collected by
 Alice. Although they belong to
the same company, directly copying
the user interaction data from Alice to Bob is not allowed due to privacy concerns.
Thus, Bob will first send training data containing node features and labels to Alice, and Alice will train a GNN model jointly with her edge information.
Then Alice will release an inference API to Bob. During inference, Bob would send a new set of test nodes with their features to query the API and obtain corresponding predictions.
\m{Different users can query the API to enjoy the service from Alice.}
\m{For instance, in practice there are  several ML/AI service platforms that provide similar interactions---taking the training data from users to train an ML model and providing inference APIs for users to make queries with their test data---such as Vertex AI~\cite{VertexAI} from Google Cloud, ParlAI platform~\cite{ParlAI} from Facebook, and InfoSphere Virtual Data Pipeline~\cite{InfoSphe} from IBM.}

During this type of interaction, \textit{the fundamental question is to understand the risks of edge privacy
(mainly for data holder Alice) for training and releasing a GNN inference API on graph data, as well as possible ways to
amortise such risks.}

\vspace{0.3em}
\noindent
\textbf{\underline{{Challenges and Problem Formulation.}}}\quad
The main motivation and challenge of the problem attributes to
the heterogeneity of data---one data holder owns the features of users (\ie, node features), while the other holds the ``connections'' or ``interactions'' among users (\ie, adjacency information) as shown in~\Cref{fig:pip}.
Inspired by this real-world example, we abstract it into
the following technical
problem.
Let there be $n$ users and
$A \in \{0,1\}^{n\times n}$
be the adjacency information. Data holder Alice has full access
to adjacency information $A$ while it is kept secret
from the data holder Bob. Bob interacts
with Alice during both \textit{training} and \textit{inference} stages.
\begin{enumerate}[leftmargin=*]
\item
Training: During
training, \m{Bob (or some other users)
collects (training) node features and labels
for a subset of users}, forming
a feature matrix $X$ with
label vector $y$, and sends them to Alice.
Alice then trains a GNN model using all the node features from Bob and her collected adjacency information $A$, and releases an
inference API to Bob.
\item Inference: During
inference, Bob
collects features for another (test)
subset of users $X'$, and sends them to Alice via the inference
API, who will run inference
using the trained GNN model, and return corresponding
predictions.
\end{enumerate}
Given this interaction model,
we aim to ask: Whether
the inference API will leak private
information of the adjacency information to a potentially malicious user Bob indirectly? How can we better protect the adjacency information
from privacy leakage while preserving high model utility?

Apart from this specific case, there have been similar concerns from different real-world cases. For instance, the advertisement department of Facebook would usually hold certain public features of individuals (\ie, node features), and needs to query the predictions from another department that holds the social network connection information which is private. Thus, how to protect the edge privacy in this setting is critical.
However, directly conducting such privacy attacks is challenging. For instance, given a large graph, naively comparing the similarities between nodes to infer their connections is clearly not enough. On the other hand, it is known that the trained GNN is based on the node influence propagation~\cite{klicpera2018predict}: If two nodes are connected, there is a high chance that changing the features of one would affect the prediction of the other.
Thus, we hope to address the research question: \textit{Is it possible to design an effective edge re-identification attack against GNNs based on the node influence information?}

Different from existing work~\cite{he2020stealing} which collects node pairs with and without connections to train a model to infer the existence of an edge, in this paper, we aim to analyze and leverage the \textit{node influence} to predict potential edge connections.
In particular, we first propose an attack strategy \linkteller under such a vertically data partitioned setting based on the node influence analysis, and explore how much the private adjacency information could be revealed from Alice via answering queries from Bob.
Then we will evaluate the proposed \linkteller attack against both an existing and a proposed differentially private graph convolutional network (DP GCN)  mechanisms to analyze whether the  \linkteller could further attack the privacy preserving GCN models. In addition, we explore what is the \textit{safe} privacy budget to choose in order to protect the trained GCN models from being attacked by privacy attacks such as \linkteller on different datasets via extensive empirical evaluation.

\vspace{0.3em}
\noindent
\textbf{\underline{Technical Contributions.}}\quad
In this paper, we focus on
understanding the \textit{edge privacy} risk
and the strength of the privacy protection mechanisms (\eg, DP) for vertically partitioned graph learning.
Specifically, we make following contributions.
\begin{enumerate}[leftmargin=*]
\item We propose the \textit{first} query based edge re-identification attack \linkteller against GNN models
by considering the influence propagation in GNN training. We
show that
it is possible to re-identify private edges  effectively in a vertically partitioned graph learning setting.
\item \looseness=-1 We explore and evaluate the proposed \linkteller attack against different DP GCN mechanisms as countermeasures.
Since there is no DP GCN mechanism proposed so far, we evaluate  \linkteller against a standard DP strategy \edgerand on graph, and a proposed DP GCN approach \lapgraph.
\item
\looseness=-1
We provide formal privacy analysis for the two DP GCN approaches and an upper bound for general edge re-identification attack success rate on DP GCN mechanisms.
\item
\m{We design extensive experiments on eight datasets under the inductive setting and three datasets under the transductive setting to show that the proposed \linkteller is able to achieve high attack precision and recall, and significantly outperforms the random attack and two state of the art methods.
We show that both DP GCN approaches
are not always resilient against \linkteller empirically under mild privacy guarantees.}
\item We systematically depict the empirical tradeoff space between (1)
\textit{model utility}---the quality of
the trained GCN model, and (2)
\textit{privacy vulnerability}---the risk of a GCN model being successfully attacked.  We
carefully analyze different regimes
under which a data holder
might want to take different
actions \m{via evaluating a range of privacy budgets, and we also analyze such tradeoff by selecting a privacy budget via a validation dataset}.
\end{enumerate}

\section{Preliminaries}

\vspace{-1mm}
\subsection{Graph Neural Networks}
\vspace{-1mm}

Graph Neural Networks (GNNs)~\cite{wu2020comprehensive} are commonly used in semi-supervised node classification tasks on graphs. Given a graph $G=(V,E)$ with $V$ denoting the nodes ($n=|V|$) and $E$ the edges, the adjacency matrix $A\subseteq \{0,1\}^{n\times n}$ is a sparse matrix, where $A_{ij}=1$ denotes the existence of an edge from node $i$ to node $j$.
Since Graph Convolutional Network (GCN)~\cite{Kipf2016gcn} is one most representative class of GNN, we next introduce GCN, which is a stack of multiple graph convolutional layers as defined below:
\begin{align}
\label{eq:gcn-layer}
    H^{l+1}=\sigma(\widehat A { H}^{l} W^l),
\end{align} where $\widehat A$ is the normalized adjacency matrix derived using a certain normalization technique and $\sigma$ is the activation function.
For the $l$-th graph convolutional layer, we denote the input node embeddings by ${H}^l$, the output by ${H}^{l+1}$, and the learnable weight by $W^l$.
Each graph convolutional layer constructs the embeddings for each node by aggregating the embeddings of the node's neighbors from the previous layer. Specifically, ${H}^0$ is the node feature matrix $X$.

GNNs were first proposed for transductive training where training and testing occur on the same graph.
Recently, inductive learning has been widely studied and applied~\cite{hamilton17graphsage,rong2020dropedge,zeng20graphsaint,xu2018representation}, which is a setting where the trained GNNs are tested on unseen nodes/graphs.
There are two main application scenarios for the inductive setting: 1) training on an evolving graph (\eg, social networks, citation networks) for future use when more nodes arise in the graph; 2) training on one graph belonging to a group of similarly structured graphs, and transfer the model to other graphs from the similar distribution.
We consider both
the inductive and transductive settings in this paper.

\vspace{-1mm}
\subsection{Differential Privacy}
\vspace{-1mm}
Differential privacy~\cite{dwork14dp} is a privacy notion that ensures an algorithm only outputs general information about its training data without revealing the information of individual records.
\begin{definition}[Differential Privacy]
    A randomized algorithm $\mathcal{M}$ with domain $\mathbb N^{|\cal X|}$ is $({\epsilon},0)$-differentially private if for all $\cal S\subseteq $ Range($\cal M$) and for all $x,y\in \bb N^{|\cal X|}$ such that $\lVert x-y\lVert_1\leq 1$:
    \begin{align*}
        \operatorname{Pr}[\mathcal{M}(x) \in\cal  S] \leq \exp (\varepsilon) \operatorname{Pr}[\mathcal{M}(y) \in\cal  S]
    \end{align*}
\end{definition}
There are two extensions of differential privacy to preserve private information in graph data. Edge differential privacy~\cite{karwa2014private} protects the edge information, while node differential privacy~\cite{kasiviswanathan2013analyzing} protects the existence of nodes.
A recent work has proposed an algorithm to generate synthetic graphs under edge local differential privacy~\cite{qin2017generating}, which provides privacy protection when the graph data is distributed among different users.
We consider a practical privacy model in the data partitioning scenario where one data holder only owns either the edge or node information, and we aim to protect the edge information from being leaked during the training and inference processes.

\section{\linkteller: Link Re-identification Attack}
In this section, we focus on understanding the risk of edge
privacy leakage caused by
exposing a GNN trained on private graph data via an inference API.
We first describe the \textbf{interaction model} between data holders, and then
the \linkteller
algorithm that
probes the \textit{inference
values} between pairs of nodes and uses these
values as our confidence
on whether edges
exist between pairs of nodes.
As we will see, this attack allows us to
recover a significant number of edges
from the private graph structured data.

\vspace{-1mm}
\subsection{Interaction Model between Data Holders}
\vspace{-1mm}
We consider an ML application based on graph structured data, where
different data holders have access to different information of the graphs (\eg, nodes or edges).
More specifically, the graph edge information is not available to everyone, since the edge connections or interactions between the node entities usually contain sensitive information, which can be exploited for malicious purposes.
Thus, we first make the following abstraction of the data holder interaction.

As shown in~\Cref{fig:int-model},
the data holder Alice holds private edge information of a graph, while \m{other  users hold the node information, and due to privacy concerns, the sensitive edge information from Alice cannot be directly shared.}
During the \textit{training stage}, in order to jointly train a GNN model on the graph data, \m{some users will first send the node features of the training graph $X^{(T)}$ together with their labels $y^{(T)}$ for a set of nodes $V^{(T)}$ to Alice; and Alice will train a GNN model together with her edge connection information for future inference purpose by releasing an inference API to external users.
}
During the \textit{inference stage}, \m{a potential adversarial user Bob will collect the node features of the inference graph $X^{(I)}$ (\eg, patients in the next month) and obtain their predicted labels from Alice via the inference API. }
Alice will then send the prediction matrix $P^{(I)}$ formed by the prediction vector for each node to Bob.
\m{Without loss of generality, in the following we will use ``Bob" to denote both the general users during training and inference time and the adversary during inference, although they are usually independent users in practice. }

\begin{figure}
    \centering

    \includegraphics[width=0.9\columnwidth]{figures/GCN_interaction_2.pdf}
    \caption{\small \textbf{The interaction model.} \m{In the training stage, first, some users send Alice the node set $V^{(T)}$, the associated features $X^{(T)}$ and labels $y^{(T)}$. Next, Alice trains a GNN model with corresponding adjacency matrix $A_{V^{(T)}}$, $X^{(T)}$, and $y^{(T)}$. In the inference stage, an adversarial user Bob queries Alice with a test node set $V^{(I)}$ and associated features $X^{(I)}$. Alice outputs the prediction matrix $P^{(I)}$.
    }}
    \label{fig:int-model}
\end{figure}

Next, we will define such training interaction formally. In particular, we will use the lower case letter to denote a vector and the upper case letter to denote a matrix.
We denote the set of nodes of the training graph held by Bob as $V^{(T)}=\{v^{(T)}_1,v^{(T)}_2,\ldots, v^{(T)}_n\} \subseteq V$.
In the training stage, data holder Bob will first send the corresponding node features
${ X}^{(T)}$
and labels
${ y}^{(T)}$
to Alice.
Here each label $y^{(T)}_i$ takes the value from a set of $c$ classes.
Then the data holder Alice who holds the node connection information will generate the adjacency matrix $A_{V^{(T)}}\subseteq \{0,1\}^{n\times n}$, where ${A_{V^{(T)}}}_{ij} = 1$ if and only if there is one edge between node $v^{(T)}_i$ and $v^{(T)}_j$.
This way, Alice can leverage the node features and labels from Bob together with her adjacency information to train a GNN model and provide the model as a \textbf{blackbox} API, $G_{BB}(\cdot, \cdot)$, for Bob.
The learned model parameters are denoted as $\{{W}^i\}$, where
$W^i\in \bb R^{d_i\times d_{i+1}}$
represents the weight of the $i$-th layer.

During the inference stage, the data holder Bob who owns another set of nodes from the inference graph will query the inference API for node prediction. In particular, given a set of inference nodes $V^{(I)} \subseteq V$, Bob will send the associated node features $X^{(I)}$ to the trained GNN API $G_{BB}(\cdot, \cdot)$.
Then together with the private adjacency matrix of inference graph $A_{V^{(I)}}$, the API from Alice will make inference on the nodes, and following the standard commercial ML inference services
such as Clarifai~\cite{clarifai} and Google Vision API~\cite{VisionAI43}, Alice will send the logits information back to Bob as below.
\begin{align*}
    {G_{BB}}&(V^{(I)}, {X}^{(I)})=\mbox{GNN}(A_{V^{(I)}},{X}^{(I)}, \{W^i\}).

\end{align*}
For ease of reference, we denote the output \textit{prediction matrix} of $G_{BB}(V^{(I)}, {X}^{(I)})$ as $P^{(I)}$, which is of shape $|V^{(I)}|\times c$.
Each row of the prediction matrix corresponds to one node in $V^{(I)}$, and each column corresponds to the confidence for one class.
Alice will then send $P^{(I)}$ back to Bob.

We discuss more
on the properties of $V^{(T)}$, $V^{(I)}$, and $V$.
It is worth noting that $V$ may not necessarily be a fixed set. New nodes and edges may arise with time elapsing, though Alice always has an up-to-date view of the graph structure. In this case, $V^{(T)}$ can be nodes in the stale graph, and $V^{(I)}$ can be the newly arisen nodes.
There is also no restriction that all nodes in $V$ should form a connected component. Rather, $V$ can contain nodes in a group of graphs, as long as the grouping makes logical and practical sense. Under this setting, $V^{(T)}$ and $V^{(I)}$ can be the nodes of different graphs in the group.

\vspace{-1mm}
\subsection{Overview of the Attack}
\label{sec:attack}
\vspace{-1mm}

We will first introduce the capability/knowledge of the attacker, and then provide overview of the attack method.
During the attack, the attacker has access to a set of node features and their labels which are required during training. During inference, Bob is able to query the trained API for multiple times with the subset of nodes that are of interest.
That is to say, the attacker's \textbf{capability} includes the query access to a blackbox GNN model and the obtained prediction probability for a set of nodes during inference.
Note that the attacker has no information about the API model except
that it is a GNN model with unknown architecture and parameters.
Unlike He \etal~\cite{he2020stealing} which assumes the knowledge of partial graphs or a shadow dataset, here, we have no such additional assumptions.

The \textbf{overview} of the proposed link re-identification attack \linkteller is as follows. The attacker plays the role of Bob in the interaction model (\Cref{fig:int-model}).
The \textit{goal} of the attacker is to recover the connections among the  inference node entities.
Concretely, during inference, attacker Bob will query the GNN API with a set of inference nodes. With the returned prediction probability vectors, Bob will infer the connections between certain pairs of nodes.
The attack succeeds if the attacker can correctly determine whether two given nodes are connected by a link or not.
We use the standard \textbf{metrics} \textit{precision}, indicating what fraction of pairs inferred to be connected are indeed connected in the graph; and \textit{recall}, indicating what fraction of the connected pairs are revealed,
to measure the attack success rate.
We also evaluate the \textit{AUC scores}.

\paragraph*{Intuitions}
Our attack is inspired by the intuition behind the training of
a GNN model---during training,
if two nodes $u$
and $v$ are connected by an edge, GNN would ``propagate''
the information of $u$ to
$v$. As a result,
if there is an edge from $u$
to $v$, we would expect that
changing the feature vector of
$u$ would impact the prediction of $v$.
Thus, if we can
compute the \textit{influence} of one node on the other,
we could use it to guess whether
there is an edge between the two nodes:
If the \textit{influence value} is ``large'',  we would be more confident on the existence of an edge; if the \textit{influence value} is ``small'', we would be more confident that the nodes are not directly connected.
Below, we describe
a concrete algorithm
to approximate such an influence
value by probing the trained GNN inference API.

\iffalse
\subsection{Overview of the Attack}
\label{sec:attack}

\cz{need a pass}

We first specify the \textbf{ability} of the attacker and then provide the \textbf{overview} of the proposed attack strategy.
In order to perform the attack, the attacker needs two \textbf{oracles} to compute the influence of one node on the other and the graph density. We will discuss how to approximately compute these two oracles in~\Cref{sec:oracles}.

Here the potential attacker Bob aims to obtain the private graph connection information among inference nodes $V^{(I)}$.
The attacker has access to a set of node features and their labels which are required during training.
During inference, Bob is able to query the trained API for multiple times with the subset of nodes that are of interest.
The attacker has no information about the API model except
that it is a GNN model with unknown architecture and parameters.
The attacker may have some prior belief about the graph density $k$, which we denote as \textit{density belief} $\hat k$.
For instance, in the hospital medical record accessing model, an attacker would have a reasonable guess about how many access one nurse would make per day~\cite{xxx}.\fan{cite}
\cz{Note that our attack does not
need $k$ to be exactly right to be effective and we study the sensitivity of our attack success rate against $k$ in our experiments.}

The setting of our proposed link re-identification attack is as follows. The attacker plays the role of Bob in the interaction model (\Cref{fig:dp-attack}).
The goal of the attacker is to recover the connections among the sensitive inference entities.
The attack succeeds if the attacker can correctly determine whether two given nodes are connected by a link or not.
We use the standard metric \textit{precision}, indicating what fraction of pairs inferred to be connected are indeed connected in the graph; and \textit{recall}, indicating what fraction of the connected pairs are revealed,
to measure the attack success rate.

Our attack is inspired by the intuition that the edge between two connected nodes serves as a bridge for information flow.
As a consequence, \textit{the influence of one node on the other would be larger when they are directly connected by an edge than the case where they are several hops away. }
We call such \textit{influence} of one node on the other as the \textit{influence value} of the link between two nodes.
If the \textit{influence value} is ``large'',  we can assert the existence of an edge; if the \textit{influence value} is ``small'', we would conclude that the nodes are not directly connected. To this end, we need to determine whether the value is ``large'' or ``small'', and one can achieve the goal through computational comparison.

For a set of sensitive nodes, we first get the pairwise influence value between all pairs of nodes, then we sort all the numbers in a decreasing manner.
With high confidence,
the first several node pairs with large influence values are connected pairs, and those with small influence values come from the unconnected pairs.
It is generally hard to tell whether the pairs with medium influence values are connected or not, and a few additional assumptions will suffice to simplify the problem.
First, we need an oracle to measure the influence value such that the values, and all connected pairs are higher than those of the unconnected pairs. The second assumption is that we know the exact number of connected pairs $m$ (\ie, graph density). Second we need an oracle to tell the graph density $m$.
As a straightforward result, in the decreasingly sorted sequence, the first $m$ pairs are connected and the  remaining pairs are unconnected, which will achieve 100\% precision and 100\% recall.

However, the two oracles are challenging to compute, especially the existence of a perfect measurement for influence values. In the following subsection, we will show that it is possible to approximately compute the oracles effectively  and  develop an effective attack algorithm \linkteller in practical scenarios.

\fi

\vspace{-1mm}
\subsection{\linkteller: Edge Influence Based Attack}
\label{sec:oracles}
\vspace{-1mm}

\linkteller attack proceeds in
two phases.
First, given a collection of
nodes $V^{(I)}$ at the inference time
and the inference API, $G_{BB}(\cdot,\cdot)$,
the attacker tries to
calcluate the
\textit{influence value}
between each pair of nodes in $V^{(I)}$.
Second, \linkteller then sorts
all pairs of nodes by their
influence value, and predict
the first
$m=\hat k\cdot \frac{n(n-1)}{2}$ node
pairs with highest influence
values as ``\texttt{\small with edge}''
and all other pairs as ``\texttt{\small without edge}''. Here $\hat{k}$ is a
hyperparameter specified by the attacker,
which indicates his prior ``belief'' of
the graph density. \m{We call $\hat{k}$
the \textit{density belief}, which is a key hyper-parameter (details in \Cref{alg:attack}). In our experiments,
we observe that
the attack performance will decrease slightly given
the discrepancy between estimated $\hat{k}$ and ground truth $k$.
Nevertheless, we show that
\linkteller remains more
effective than the state-of-the-art attacks even with  inaccurate estimation for $\hat{k}$.}

\m{In practice, it is also possible for attackers to further estimate $\hat k$ or the influence value \textit{threshold} for edge re-identification with additional knowledge.
For instance,
if the attacker has partial graph information, she can either estimate $\hat k$, or directly
calculate the influence values for known connected/unconnected pairs and estimate the threshold for distinguishing them.
More concrete descriptions of such actionable strategies are deferred to~\Cref{sec:append-belief}, which we hope can inspire more effective attacks as interesting future work.
}
\iffalse
In this section, we provide detailed solutions to approximate the two oracles about inference value measurement and density belief calculation.
We start from the design of an efficient measurement for the influence values in place of a hypothetically perfect measurement, and then deal with the oracle for computing the number of connected pairs in a private graph.
\fi

\paragraph*{Measuring Influence Values via the Inference API}
Here we describe the calculation of
the influence value between a node pair.
Recall that in the interaction model, for any inquiry involving a set of nodes and their features, the attacker Bob is given a prediction vector for each node.
With the hope of taking advantage of the prediction vectors to obtain the influence value, we look into the structure of graph convolutional layers and analyze the influence of an edge on its incident nodes.

We characterize the influence of one node $v$ to the other node $u$
by measuring the change in the prediction for node $u$ when the features of the node $v$ get reweighted.
Formally, let $V^{(I)}$ be the set of nodes involved in the inference stage and
${X}=[{x}_1^\top,\ldots, {x}_v^\top,\ldots]^\top$
be the corresponding feature matrix. By upweighting the features of the node $v$ by a small value $\Delta$, the attacker generates a new feature matrix $
{X}'=[{x}_1^\top,\ldots, (1+\Delta){x}_v^\top,\ldots]^\top
$. The difference between the two predictions $P^{(I)}$ and $P'^{(I)}$ with respect to $\Delta$ denotes the influence of reweighting $v$ on the prediction of all other nodes.
We define the influence matrix of $v$ on other nodes as $I_v=\lim_{\Delta\rzero}\left(P'^{(I)}-P^{(I)}\right)/\Delta$ with size $|V^{(I)}| \times c$
Its $u$-th row ${i_{v}}_u \in I_v$ represents the prediction influence vector of $v$ on $u$ for each class dimension.
Finally, we compute the $\ell_2$ norm of the corresponding influence vector as the influence value of $v$ on $u$ as $\norm{{i_{v}}_u}$.
Since computing the influence matrix $I_v$
yields the influence of one node $v$ on \textit{all} other nodes, to compute the influence value between  $n^2$ pairs of nodes ($n$ is the number of nodes of interest), we only need to compute $n$ influence matrices, each for one node in the interested node set.
This requires $2n$ forward passes of the trained network in all, which does not constitute a significant overhead during inference time. We report the running time of \linkteller in~\Cref{sec:append-runtime}.

Next, we will theoretically show that the influence value $\norm{{i_{v}}_u}$ comes with a nice property for GCN models, that is, \textit{two nodes that are at least $k+1$ hops away have no influence on each other in a $k$-layer graph convolutional network}.
We start from the simple case of a 1-layer GCN in~\Cref{thm:1-layer-gcn}.

\vspace{-1mm}
\begin{proposition}[Influence value of a 1-layer GCN]
\label{thm:1-layer-gcn}
For a 1-layer trained GCN model with parameters $W$, when its input adjacency matrix is $A$ and feature matrix is $X$, when there is no edge between node $u$ and node $v$, the influence value $\norm{{i_{v}}_u}=0$.
\end{proposition}

\vspace{-1mm}
We omit the proof in~\Cref{sec:append-proof-thm-1-layer-gcn}
and next present a natural extension of the above conclusion for a $k$-layer GCN.
\vspace{-1mm}
\begin{theorem}[Influence value for a $k$-layer GCN]
\label{thm:k-layer-gcn}
For a $k$-layer trained GCN model,
when node $u$ and node $v$ are at least $k+1$ hops away,
the influence value $\norm{{i_{v}}_u}=0$.
\end{theorem}
\iffalse
Ignoring the activation layers, the output of the GCN is simply $A^kXW$, where $A^k$ is the $k$-th power of the adjacency matrix $A$ and $W=W^1\bf \cdots W^k$.
Therefore, the $j$-th entry of ${i_{v}}_u$ is $(A^k)_{uv}\langle {x}_v, {w}_j\rangle$ where ${w}_j$ is the $j$-th column vector of $W$.
When node $u$ and node $v$ are at least $k+1$ hops away, we can prove $(A^k)_{uv}=0$ by mathematical induction.
Then a similar reasoning as ~\Cref{thm:1-layer-gcn} applies.
\fi
\vspace{-1mm}
The complete proof is provided in~\Cref{sec:append-proof-thm-k-layer-gcn}.
With the guarantee provided by~\Cref{thm:1-layer-gcn}, we can identify the connected pairs against a 1-layer GCN with high confidence; the criterion is that the pair is connected if and only if the influence value is non-zero.
For GCNs with more layers, though this criterion does not directly apply,
\Cref{thm:k-layer-gcn} can help to rule out nodes that are $k+1$ hops apart, thus eliminating a significant number of negative examples (\ie, unconnected pairs).
Moreover, the node pairs that are directly connected would have higher influence values,
observed by studies on local neighborhood properties~\cite{xu2018representation}.
Although there is no strict guarantee that the influence values of the connected pairs are the largest since the values also depend on the features and the learned weights, in practice, the learned weights will generally display a preference for connected pairs for better label propagation, and thus the corresponding influence values of connected pairs are larger.

\iffalse
\subsubsection{Distinguishing Node Pairs Using Density Belief}
\label{sec:o2}

We next address the second oracle, \ie, computing the number of connected pairs $m$ within a graph. Instead of assuming the exact knowledge about the graph density which is too strong, we can safely assume that the attacker is able to come up with a reasonable guess of the graph density.
In essence, there is plenty of evidence that an attacker can rely on to back up her guess, \eg, background knowledge of the common density value for the same type of natural graphs.
Let the density belief of the attacker be portion $\hat k$. For a set of $n$ nodes, the number of expected edges is $m=\hat k\cdot \frac{n(n-1)}{2}$. Thus, after we sort the influence values in a decreasing manner, we conclude that the first $m$ pairs are connected while the remaining pairs are not.

Putting the two parts together, we depict a practical attack strategy \linkteller in~\Cref{alg:attack}.
In addition, we intentionally separate the sensitive set $V^{(I)}$ from the non-sensitive ones to save the unnecessary queries while making use of as much information in $V^{(T)}$ as possible.
In this way, \linkteller is highly efficient in practice.
\fi

\begin{small}
\begin{algorithm}[t!]
\algsetup{linenosize=\tiny}
\footnotesize
\DontPrintSemicolon
\KwIn{A set of nodes of interest $V^{(C)} \subseteq V^{(I)}$; the associated node features $X$;
the inference API $G_{BB}(\cdot,\cdot)$; density belief $\hat k$, reweighting scale $\Delta$}
\KwOut{a $0/1$ value for each pair of nodes, indicating the absence/presence of edge}
\SetKwFunction{calc}{InfluenceValue}
\SetKwFunction{infmat}{InfluenceMatrix}
\SetKwProg{Fn}{Function}{:}{}
  \Fn{\infmat{$V^{(I)},X,G_{BB}(\cdot,\cdot),v$}}{
    $P=G_{BB}(V^{(I)},X)$\;
    $X'=[{x}_1^\top,\ldots, (1+\Delta){x}_v^\top,\ldots, ]^\top$\;
    $P'=G_{BB}(V^{(I)},X')$\;
    $I=\frac{1}{\Delta}(P'-P)$\;
    \KwRet $I$
  }
  \;
\For {each node $v\in V^{(C)}$} {
    $I \leftarrow$ \infmat($V^{(I)},X,G_{BB}(\cdot,\cdot),v$)\;
    \For {each node $u\in V^{(C)}$} {
        $i_{uv}\leftarrow \norm{I[u,:]}$\Comment*[r]{\scriptsize The norm of the $u$-th row of $I$}
    }
}
Sort all $i_{uv}$ in a descending order\;
$n\leftarrow$ $|V|$\;
$m\leftarrow$ $\hat k\cdot \frac{n(n-1)}{2}$\;
Assign $1$ to the first $m$ pairs, and $0$ to the remaining\;
 \caption{\small Link Re-identification Attack ({\linkteller})}\label{alg:attack}
\end{algorithm}

\end{small}

\section{Countermeasures of \linkteller: Differentially Private GCN}
In this section, we aim to evaluate to what extent the proposed \linkteller in~\Cref{sec:attack} reveals the private connection information effectively through a trained GCN, as well as the sufficient conditions of the attack, via considering different countermeasure approaches.
The most direct countermeasure or defense against such an attack would be a differentially private GCN model.
However, so far there is no existing work directly training differentially private GCN models to our best knowledge.
As a result, we first revisit the \textbf{general framework} and principles of developing a differentially private (DP) GCN against such edge re-identification attacks (\Cref{sec:defense-overview}).
We then formally define the DP GCN, followed by two proposed \textbf{practical algorithms} to train a DP GCN. We also discuss the upper bound of the precision of general edge re-identification attacks on DP GCNs. Importantly, we point out that the theoretical guarantee of differential privacy is insufficient in preserving both privacy and utility for a GCN. It is equally important to empirically choose an appropriate privacy budget to strike a better privacy-utility balance.

\vspace{-1mm}
\subsection{Overview of DP GCN Framework}
\label{sec:defense-overview}
\vspace{-1mm}

In the following sections, we review the definition of edge differential privacy for graph algorithms~\cite{karwa2014private} and present two practical DP GCN training algorithms via graph structure input perturbation. Input perturbation for GCN is a non-trivial problem since naively adding noise to the graph structure would destroy the sparsity of the adjacency matrix. The loss of sparsity greatly  limits a GCN's performance and increases its memory and computation cost.

To preserve the sparsity of the adjacency matrix, we discuss two approaches for GCN input perturbation: \edgerand and \lapgraph. \edgerand adapts the idea in Mülle \etal~\cite{muile2015pig} and randomly flips each entry in the adjacency matrix according to a Bernoulli random variable. \lapgraph improves upon \edgerand by pre-calculating the original graph density using a small privacy budget and using that density to clip the perturbed adjacency matrix. Compared to \edgerand, \lapgraph preserves the sparsity of the adjacency matrix under a small privacy budget.

\paragraph*{Differentially Private GCN}
In edge differential privacy~\cite{karwa2014private}, two undirected graphs are said to be neighbors if one graph can be obtained by the other by adding/removing one edge. \Cref{def:nbr} defines the neighboring relation using the adjacency matrix representation.

\begin{definition}[Neighboring relation]
    \label{def:nbr}
    Let $\cal A$ be the set of adjacency matrices of undirected graphs. Any pair of two \textit{symmetric} matrices $A,A'\in \cal A$ are said to be neighbors when the graph represented by $A'$ could be obtained by adding/removing one edge from  graph  $A$, denoted as $A\sim A'$. Further, we denote the differing edge as $e=A\oplus A'$.
\end{definition}

\begin{definition}[\eedgedp]
    \label{def:edgedp}
    A mechanism $\mathcal{M}$ is \Eedgedp~if for all valid matrix $A\in\cal A$, and $A'\sim A$, and any subset of outputs $\cal S\subseteq Range(\cal M)$, the following holds:
    \begin{align}
        \label[ineq]{eq:dp}
        \Pr[\mathcal{M}(A)\in \cal S]\leq \exp({\epsilon})\cdot \Pr[\mathcal{M}(A')\in \cal S].
    \end{align}
    The probability $\Pr$ is taken over the randomness of $\mathcal{M}$.
\end{definition}
\Cref{def:edgedp} formally presents the definition of \eedgedp (\eedgedpshort). It guarantees that the outputs of a mechanism $\mathcal{M}$ should be indistinguishable on any pair of neighboring input graphs differing in one edge.

Next, we apply \eedgedpshort to a GCN. To protect against link re-identification attacks, we need to guarantee that a GCN's inference results do not reveal the edge information of its input graph. Specifically, in the inductive training, the edge information of both the training graph and the inference graph should be protected. In addition, the privacy protection should hold even if the attacker submits an infinite number of inference queries.

Based on the above criteria, we first perturb the graphs before training a GCN. Since the training and the inference steps are both post-processing on the perturbed DP graphs, the edge information is protected for both the training and inference graphs. Moreover, submitting more queries would not reveal sensitive edge information.

\m{We present the detailed algorithm of \textit{perturbation}, \textit{training}, and \textit{inference} in a differentially private GCN framework in~\Cref{alg:dpgcn} in~\Cref{sec:append-algo-dp-gcn}.}
First, the adjacency matrix $A$ is perturbed to meet the DP guarantee. Second, a DP GCN model is trained on a subset of training nodes in the perturbed graph. Finally, during inference, the DP GCN model is used to predict the labels for a subset of inference nodes in the perturbed graph.
Essentially, \eedgedpshort is achieved in the step of adjacency matrix perturbation (line 1-2), and the guarantee is provided by the privacy guarantee of the perturbation mechanism. Since the same perturbed graph is used for both the training and inference steps, making multiple inferences would not consume additional privacy budget.

The following theorem provides differential privacy guarantee for the training procedure in~\Cref{alg:dpgcn} for GCN models.

\begin{theorem}[\Eedgedp GCN]
\label{thm:DP GCN}
The DP GCN model trained by~\Cref{alg:dpgcn} is \Eedgedp if the perturbation mechanism $M_\varepsilon$ is \Eedgedp.
\end{theorem}

We omit all proofs for the DP guarantees in~\Cref{sec-append-dp-proof}.
Next, we show that the \texttt{\small Inference} step in \Cref{alg:dpgcn} guarantees \eedgedpshort for edges in both the training and testing graph ($A_{V^{(T)}}$ and $A_{V^{(I)}}$). To prove this privacy guarantee, we first introduce the parallel composition property of \eedgedpshort.

\begin{lemma}[Parallel composition of \eedgedpshort]
\label{lemma:parallel_composition}
If the perturbation mechanism $M_{\varepsilon}$ is \Eedgedp and $A_1, A_2, \dots, A_m$ are adjacency matrices with non-overlapping edges, the combination of $M_{\varepsilon}(A_1), M_{\varepsilon}(A_2), \dots, M_{\varepsilon}(A_m)$ is also \Eedgedp.
\end{lemma}

The following theorem guarantees differential privacy for any inference using the DP GCN model.

\begin{theorem}[\Eedgedp GCN inference]
\label{thm:dp-infer}
The \texttt{\small Inference} step in~\Cref{alg:dpgcn} is \Eedgedp~for any $V^{(I)} \subseteq V$.
\end{theorem}

The above analysis of the general DP GCN framework provides  privacy guarantees for GCN models trained following the principles in Algorithm~\ref{alg:dpgcn}. Next, we will introduce two such concrete training mechanisms.

\vspace{-1mm}
\subsection{Practical DP GCN}
\vspace{-1mm}

In \Cref{alg:dpgcn}, the perturbation step $M_\varepsilon$ takes the adjacency matrix of the input graph and adds noise to the adjacency matrix to guarantee \eedgedpshort. In this section, we present two practical DP mechanisms for this process.

The intuition behind perturbing the adjacency matrix is to add enough noise in the adjacency matrix to guarantee the indistinguishability between any pair of neighboring adjacency matrices $A$ and $A'$---the ratio of the probability of getting the same perturbed matrix from $A$ and $A'$ should be bounded by a small constant $\varepsilon$. The smaller $\varepsilon$ is, the stronger the protection is.

In addition to the privacy requirements, the perturbed adjacency matrix $A'$ also needs to satisfy the following two requirements in order to be used as a training/inference graph for DP GCN. First, for large graphs, $A'$ needs to preserve a reasonable level of sparsity to avoid huge memory consumption when training a GCN model. Second, each row in the perturbed adjacency matrix $A'$ should represent the same node as its corresponding row in the original adjacency matrix $A$. This requirement ensures that the node features and labels can be associated with the right graph structure information in the perturbed adjacency matrix during training and inference.

However, the second requirement is often not satisfied by prior work on DP synthetic graph generation~\cite{sala2011sharing,wang2013preserving,xiao2014differentially,brunet2016novel,qin2017generating}.
This line of work aims at generating graphs that share similar statistics with the original graphs.
Though the desired statistics of the graphs are preserved, the nodes in the generated graph and the original graph are intrinsically unrelated. Therefore, the new DP graph structure cannot be connected with the node features and labels to train a DP GCN model. More discussions on prior works are provided in the related work section.

To satisfy the privacy and utility requirements for DP GCN, we introduce two perturbation methods that directly add noise to the adjacency matrix.

\subsubsection{Edge Randomization (\edgerand)}
We set out with a discrete perturbation method proposed in Mülle \etal~\cite{muile2015pig}. This algorithm was originally proposed as a pre-processing step for DP node clustering. Since the algorithm naturally preserves the sparse structure of the adjacency matrix, we adopt it as the input perturbation algorithm for DP GCN and name it \edgerand.
\m{We present the algorithm for \edgerand in~\Cref{alg:pig} in~\Cref{sec:append-algo-dp-mech}.}
We first randomly choose the cells to perturb and then randomly choose the target value from $\{0,1\}$ for each cell to be perturbed.

In \edgerand, the level of the sparsity of the perturbed adjacency matrix is purely determined by the sampling parameter $s$, which can be conveniently controlled to adapt to the given privacy budget ${\epsilon}$. The relationship between $s$ and ${\epsilon}$ is characterized in~\Cref{thm:dppig}.

\begin{theorem}
    \label{thm:dppig}
    \edgerand guarantees \eedgedpshort for ${\epsilon}\geq\ln \left(\frac{2}{s}-1\right)$, $s\in (0,1]$.
\end{theorem}

\edgerand guarantees differential privacy for the perturbed adjacency matrix. However, the privacy protection comes at the cost of changing the density of the perturbed graph.
Let the density of the input graph to \edgerand be $k$, the expectation of the density of the output graph is $k'=(1-s)k+s/2$.
Take ${\epsilon}=1$ as an example, in this case, $s$ shall be at least $0.5379$ according to~\Cref{thm:dppig}, and $k'$ is therefore larger than $1/4$.
As such, when ${\epsilon}$ is small, the perturbed graph generated by \edgerand could have a much higher density compared to the original one. This would increase the memory consumption for training DP GCNs on large graphs and may cause memory errors when the perturbed adjacency matrix becomes too dense to fit into the memory.

\subsubsection{Laplace Mechanism for Graphs (\lapgraph)}
\edgerand is not applicable to large graphs under small privacy budgets due to the huge memory consumption caused by a dense adjacency matrix. Therefore, we propose \lapgraph to address this problem.

The classical idea of adding Laplace noise to the private value is also applicable to our scenario.
The difference is that, in traditional scenarios, Laplace noise is applied to entities such as a database entry, while in our case, the private entity is the adjacency matrix. Therefore, additional care shall be taken to tailor the Laplace mechanism to the graph scenario.

By the definition of Laplace mechanism~\cite{dwork14dp}, adding a certain amount of noise to each cell in the adjacency matrix will lead to any two neighboring adjacency matrices being indistinguishable.
However, directly applying this mechanism will add a huge amount of continuous noise to each cell of the adjacency matrix, which inevitably undermines the sparse property of the matrix. The loss of sparse property introduces two problems: First, it drastically increases the computation and memory cost of training a GCN. Second, adding the continuous noise in the adjacency matrix is equivalent to adding new weighted edges between almost \emph{every} pair of nodes in the graph, which greatly impairs the utility of the adjacency matrix and, consequently, the GCN trained on it.

To retain the sparsity, after adding noise, we only keep the largest $T$ cells as existing edges in the perturbed graph. To preserve the original graph structure, we set $T$ to be the approximation of the number of edges in the original graph using a small portion of the differential privacy budget.
We name the perturbation method \lapgraph and \m{present the details in~\Cref{alg:laplace} in~\Cref{sec:append-algo-dp-mech}. }
The privacy guarantee for this method is given in~\Cref{thm:dplap}.

Compared with \edgerand, \lapgraph has the advantage of better preserving the density of the original graph, especially for large graphs and small $\varepsilon$. Since the number of edges in a large graph is often orders of magnitude higher than the sensitivity of adding/removing a single edge, it is possible to estimate $T$ even under a very limited privacy budget. Thus, the density of the perturbed graph is much closer to the original one than \edgerand. This improvement makes it possible to train DP GCN on large graphs under small privacy budgets without causing memory errors.

\begin{theorem}
\label{thm:dplap}
    \lapgraph guarantees \eedgedpshort.
\end{theorem}

Due to the lack of DP GCN approaches, here we focus on the existing technique \edgerand and the proposed \lapgraph to provide DP guarantees for GCN as countermeasures to further evaluate the proposed attack \linkteller. We have provided the formal analysis for the privacy guarantees for \edgerand and \lapgraph above, and next, we will discuss a general upper bound of edge privacy on DP GCN models.

\subsection{Discussion: Upper Bound of Edge Re-Identification Attack Performance on DP GCN}
\label{sec:dp-bound}
\vspace{-1mm}

As implied by \eedgedpshort in~\Cref{def:edgedp}, it is generally difficult to tell, among the two neighboring adjacency matrices $A$ and $A'$, which one leads to the observed prediction. The direct consequence of the indistinguishability is that the existence of the differing edge $e=A\oplus A'$ cannot be inferred. In this section, we aim to analyze the upper bound of edge re-identification attacks against  DP GCN.

Same as the attack model introduced in \Cref{sec:attack}, we assume the attacker has access to a set of node features and their labels without any knowledge about the GCN structure and parameters.

To start with, we formalize the link re-identification attack proposed in \Cref{sec:attack} as the following game between the graph owner Alice and the attacker Bob:
\begin{enumerate}[leftmargin=*]
    \item Let $V$ be a set of nodes and $\mathcal{A}_V$ be the set of all possible adjacency matrices for graphs with nodes $V$. First, Alice selects an adjacency matrix $A \in \mathcal{A}_V$ uniformly at random and uses it to generate a graph.
    \item Bob selects a set of training nodes $V^{(T)} \subseteq V$. He sends $V^{(T)}$ with the features and labels of $V^{(T)}$ to Alice.
    \item Alice then trains an \Eedgedp GCN model and exposes the inference API $G_{BB}$ to Bob.
    \item Bob selects a set of inference nodes $V^{(I)} \subseteq V$ and nodes of interests $V^{(C)} \subseteq V^{(I)}$. Let $k^{(C)}$ denote the graph density over $V^{(C)}$. For each pair of nodes $<u,v>\in V^{(C)}\times V^{(C)}$, Bob launches a link re-identification attack $\mathcal{R}_{G_{BB}}(u, v)$ to infer whether an edge exists between nodes $u$ and
    $v$, and $\mathcal{R}_{G_{BB}}(u, v) \in \left\{0,1\right\}$.
\end{enumerate}

To obtain an upper bound for the above attack, we assume the attacker  knows the inference node density $k^{(C)}$.
Formally, we bound the expected precision of the link re-identification attack $\mathcal{R}$ by the following theorem.

\begin{theorem}
\label{thm:dp-bound}
The precision of $\mathcal{R}_{G_{BB}}$ over nodes of interests $V^{(C)}$ with density $k^{(C)}$ is upper-bounded by:
\begin{small}
\begin{equation*}
    \underset{<u,v>\in V^{(C)}\times V^{(C)}}{\Pr}\left[A_{uv} = 1 \mid \mathcal{R}_{G_{BB}}(u, v) = 1 \right] \leq \exp({\epsilon}) \cdot k^{(C)},
\end{equation*}
\end{small}
where the probability is calculated over the randomness in the graph selection, the noise introduced by the DP GCN training, and the selection of node pair $<u, v>$.
\end{theorem}

\textbf{Proof Sketch.} \quad Based on \Cref{def:edgedp} and Bayes' theorem, the ratio between the posterior probability $\Pr[A_{uv}=1 \mid G_{BB} \in S]$ and the prior belief on $\Pr[A_{uv}=1]$ is bounded by $\exp(\varepsilon)$. Since the precision of a random guess based on the prior probability (\ie, the graph density) is at most $k^{(C)}$, the upper bound for the precision of a link re-identification attack on an \Eedgedp GCN is $\exp(\varepsilon)\cdot k^{(C)}$. The complete proof is provided in~\Cref{sec:append-proof-thm-dp-bound}.

Although~\Cref{thm:dp-bound} provides a theoretical upper bound for the precision of an edge re-identification attack, it may not be sufficiently tight to provide the best privacy-utility trade-off. For example, given a graph with $1\%$ density, the attack precision is bounded below $2\%$ (\ie, no more than two times higher than random guessing using the prior probability) if and only if ${\epsilon} \leq \ln{2}$. However, in practice, the same empirical protection might be achieved by a model with weaker privacy protection (\ie, higher privacy budget) and therefore better utility. Thus, in~\Cref{sec:eval-dp-attack}, we empirically evaluate the privacy-utility trade-off of DP GCN across multiple datasets.

\m{In addition to DP GCN approaches, it may also
be possible to leverage some heuristics to detect such attacks. For instance, one may distinguish the abnormal behavior of querying the same set of inference nodes $V^{(I)}$ multiple times (with the node features of one node slightly altered in each query).
The defender could also optimize a query limit $Q$ which decreases the attack performance while maintaining reasonable benign query accuracy, although there is no guarantee for such detection. More discussions on the detection strategies are deferred to~\Cref{sec:append-stealthy}, and in this paper, we will focus on the DP GCN mechanisms with privacy guarantees.
}

\section{Evaluation of \linkteller}
\label{sec:eval-attack}
We evaluate the effectiveness of the \linkteller attack on multiple graph datasets under various scenarios compared with three baselines.
In particular, we investigate how different factors such as node degree affect the attack performance.

\vspace{-1mm}
\subsection{Datasets}
\label{sec:datasets}
\vspace{-1mm}

\m{We evaluate \linkteller on eight datasets in the \textit{inductive} setting and {three} datasets in the \textit{transductive} setting (\Cref{sec:append-datasets}) and provide a brief description of the data below.}
\m{Under the inductive setting,
the first dataset is the \textit{twitch dataset}~\cite{rozemberczki2019multiscale} which is composed of 6 graphs as disjoint sets of nodes.} Each of the graphs represents a set of people in one country; the nodes within a graph represent users in one country, and the links represent mutual friendships between users.
The dimension of the features is the same across different graphs and each dimension has the same semantic meaning. Some sampled features include games they like, location, and streaming habits. The task is a binary classification task which classifies whether a streamer uses explicit language.
This dataset is proposed for transfer learning, \ie, applying the model learned on one graph to make inferences on the other graphs corresponding to different countries.
In our evaluation, we train the GNN model on the graph twitch-ES, and transfer it to other five countries (RU, DE, FR, ENGB, PTBR).
\textit{PPI}~\cite{hamilton17graphsage} and \textit{Flickr}~\cite{zeng20graphsaint} are another two standard datasets used in graph inductive learning setting. PPI is a dataset for multi-label classification task, which aims to categorize the function of proteins across various biological protein-protein interaction graphs.
Flickr is an evolving graph for the classification task, which contains descriptions and common properties of images as node features.
For both PPI and Flickr, we use the standard splits for training and testing following the previous works.
\m{Under the transductive setting, we adopt three standard datasets (Cora, Citeseer, and Pubmed). More details of the data can be found in~\Cref{sec:append-datasets}.}

\vspace{-1mm}
\subsection{Models}
\label{sec:models}
\vspace{-1mm}

We mainly experiment with GCN models.
The configurations/hyperparameters
include the normalization techniques applied to the adjacency matrix, the number of hidden layers, the number of input units, hidden units, and output units, as well as the dropout rate. For each combination of hyperparameters, we train the network to minimize the cross-entropy loss for the intended tasks.
We performed grid search to get the best set of hyperparameters on the validation set. The search space for the hyperparameters and the formulae for different normalization techniques are provided in~\Cref{sec:append-eval-detail}.
To measure the
performance of a GCN model, we follow previous work and use F1 score for their corresponding binary classification tasks. We leave the description of the best hyper-parameters we achieve in~\Cref{sec:append-best-para}.
In addition to the 2-layer GCNs evaluated in the main paper, in~\Cref{sec:append-3-layer}, we also experimented with the 3-layer GCNs and include a discussion about GCNs of 1 layer and more than 3 layers.
We conclude that \linkteller is a successful attack against most practical GCN models.
In addition, we evaluate \linkteller on Graph Attention Networks (GATs). The details are in~\Cref{sec:attack-gat}.

\iffalse
Below, we describe the best combinations we get.

For twitch-ES, we use the method First-Order GCN to normalize the input graph. We train a two-layer GCN with the number of hidden units 256. The dropout rate is set to 0.5 and the learning rate is 0.01. The training epoch is 200 and the model converges within 200 epochs. For PPI, we use Augmented Normalized Adjacency with Self-loop for normalizing the adjacency matrix and train a two-layer GCN with the number of hidden layers 256. The dropout rate is 0.4 and the learning rate is 0.05. The training epoch is 200 where the model converges. For Flickr, we use Augmented Normalized Adjacency for normalization and train a two-layer GCN with the number of hidden layers 256. The dropout rate is 0.2 and the learning rate is 0.0005. The number of epochs is 200 within which the model converges.
\fi

\vspace{-1mm}
\subsection{Setup of the Evaluation}
\vspace{-1mm}
In this section, we first describe the metrics we use to evaluate the attack effectiveness of \linkteller.
We then present the baseline attack methods.

\subsubsection{Evaluation Metrics of the attack}
\label{sec:eval-metric}
We use the standard metrics: \textbf{precision} (the fraction of existing edges among the pairs recognized as true by Bob) and \textbf{recall} (the fraction of edges discovered by Bob over all existing edges among the subset of nodes).
We also compute the \textbf{F1 score} (the harmonic mean of precision and recall).
The reason we adopt the metric is that our problem here (distinguishing connected pairs from unconnected ones) is an imbalanced binary classification problem where the minority (the connected pair) is at the core of concern. See~\Cref{sec:append-eval-metrics} for more details.
Additionally, for fair comparison with baselines, we follow the evaluation in He \etal~\cite{he2020stealing} and compute the \textbf{AUC score}.

\subsubsection{Baseline Attacks}
\label{sec:baseline-attack}

We compare \linkteller with two baselines: random attack and LSA2 attacks
in He \etal~\cite{he2020stealing}.

For the random attack,
we follow the standard notion
and construct a
random classifier
as a Bernoulli random variable with parameter $p$ which predicts true if and only if the random variable takes the value $1$~\cite{flach2015precision}.
Given a set of instances where $a$ of them are true and $b$ are false, the precision of this classifier is $a/(a+b)$ and the recall is $p$.
In our case, $a$ is the number of connected pairs of nodes, while $a+b$ is the number of all pairs.
Therefore, \textit{precision} is exactly the \textit{density} $k$ of the subset, which we formally define as
$
    k = 2 m/(n(n-1))
$, where $n=|\m{V^{(C)}}|$ is the size of the set of interest and $m$ is the number of connections among the set \m{$V^{(C)}$}.
The recall of
such a random classifier
will be the
density belief $\hat{k}$.

We also compare \linkteller with the state of the art LSA2 attacks~\cite{he2020stealing}.
In the paper, the authors discussed several types of background knowledge including node attributes, partial graph, and a shadow dataset for attackers.
Among the combinations, their \textit{Attack-2} is closest to our scenario where the attacker has only access to the target graph's node features.
We follow their best practices, computing the \textit{correlation distance} between 1) \textit{posteriors} given by the target model and 2) \textit{node attributes},
referred to as LSA2-post and LSA2-attr attacks.

\vspace{-1mm}
\subsection{Evaluation Protocol}
\label{sec:attack-setup}
\vspace{-1mm}

Think about the paparazzi who are fanatical about exploiting the connections among celebrities, or
the indiscriminate criminals that are maliciously targeted at the mass mediocre majority, their targets are substantially different.
Consequently,
the subsets they gather for attack have diverse node degree distributions.
Catering to the need of evaluating our attack against \textit{nodes of different degree distributions}, we design the scenario as follows.
We consider three types of subsets that are of potential interest to the attacker: nodes of low degree, unconstrained degree, and high degree.
\m{For each type, we randomly sample a fixed number $\m{n^{(C)}}$ of nodes to form a subset \m{$V^{(C)}$} for evaluation. When sampling nodes of low (or high) degree, we place a threshold value $d_{\rm low}$ (or $d_{\rm high}$) and sample from nodes whose degrees are no larger than $d_{\rm low}$ (or no smaller than $d_{\rm high}$). The value $d_{\rm low}$ and $d_{\rm high}$ are chosen empirically based on the graph.
When sampling nodes of unconstrained degree, we sample nodes from the entire test set uniformly at random.}

More specifically, for all datasets, we choose $\m{n^{(C)}}=|\m{V^{(C)}}|=500$.
For twitch datasets,
to form the unconstrained subset, we sample from each entire testing graph.
For the low degree subset and high degree subset, the threshold $d_{\rm low}$ and $d_{\rm high}$ are set to $5$ and $10$, respectively.
We set the $d_{\rm low}$ value to $10$ for twitch-PTBR, since the graph is much denser with abundant connections among a small number of nodes.
For PPI and Flickr graphs, the subsets for testing are sampled from the testing graphs/nodes that are not involved in training.
We set $d_{\rm low}$ as $15$ and $d_{\rm high}$ as $30$ for these two large graphs.

We also evaluate different \textit{density belief} $\hat k\in\{k/4,k/2,k,2k,4k\}$, where $k$ is the true density. In the experiments, we round the density $k$ to the closest value in its most significant bit (\eg, 5.61e-5 rounded to 6e-5).
As we will see, the effectiveness of \linkteller does not heavily depend on the exact knowledge of the density $k$.

\vspace{-1mm}
\subsection{Evaluation for \linkteller}
\label{sec:attack-eval}
\vspace{-1mm}

\input{tables/tab_attack_nonprivate}
\input{tables/tab_attack_nonprivate_auc}

We first evaluate
the precision, recall, and AUC of \linkteller on eight datasets in the inductive setting,
under 3 sampling strategies (low, unconstrained, and high degree), using 5 density beliefs ($k/4,k/2,k,2k,4k$), compared with different baselines.
For each scenario, the reported results are averaged over 3 runs using different random seeds for node sampling.

We report the precision, recall, and AUC results on some datasets in~\Cref{tab:att-np} and~\Cref{tab:att-np-auc} and the remaining datasets in~\Cref{sec:append-eval-results}
due to the space limit.
We leave the results of the weak random attack baseline in~\Cref{sec:append-rand-baseline}.
As a brief summary,
\linkteller significantly outperforms the random attack baseline.
We mainly focus on the comparison with LSA2 attacks~\cite{he2020stealing}.
We show that \linkteller significantly outperforms these two baselines.
In~\Cref{tab:att-np}, LSA2-\{post, attr\} fail to attack in most of the scenarios, while \linkteller attains fairly high precision and recall.
\m{The AUC scores in~\Cref{tab:att-np-auc} also demonstrate the advantage of \linkteller.}
\m{Since the baselines LSA2-\{post, attr\} are  only performed under transductive setting in He \etal~\cite{he2020stealing},
to demonstrate the generality of \linkteller, we also compare with them  following the same evaluation protocol as in He \etal~\cite{he2020stealing}  on three datasets in the transductive setting.
The results are reported
in~\Cref{sec:append-trans}.}
\m{We can see that the inductive setting is indeed more challenging: the baselines always fail to attack in the inductive setting while \linkteller is effective; the baselines are able to re-identify some private edges in the transductive setting, while \linkteller is consistently more effective.}

\m{Intuitively, the high attack effectiveness of \linkteller compared to baselines is because that LSA2-\{post, attr\} only leverage node-level information (posteriors or node attributes) to perform the edge re-identification attack.}
\m{Although these node-level features can be correlated with the graph structure in some graphs, this correlation is not guaranteed, especially in the inductive setting.
In comparison, \linkteller leverages the graph-structure information inferred from the inter-node influence in a GCN model according to \Cref{thm:k-layer-gcn}.}
\m{We defer more detailed comparison and analysis in~\Cref{sec:append-baseline-cmp}.}

\m{In addition,
it is clear that given an accurate estimation of the density ($\hat k=k$), \linkteller achieves very high precision and recall across different node degree distributions and datasets.
It is interesting to see that even when the density estimation is inaccurate (\eg, $\hat k\in\{k/4,k/2,2k,4k\}$), the attack is still effective.
Concretely, when the belief is smaller ($\hat k=k/2$),
the precision values increase in all cases; when the belief is larger ($\hat k=2k$), almost all recall values are above 90\% except for Flickr.
Even under extremely inaccurate estimations such as $\hat k=k/4$ (or $\hat k=4k$), the precision values (or the recall values) are mostly higher than $95\%$.
This observation demonstrates the generality of \linkteller.}
We notice that \linkteller's performance on Flickr is
slightly poorer than other datasets.
This may be because that
the trained GCN on Flickr does not achieve good performance given its highly sparse structure. This implies that the parameters of the trained network on Flickr may not capture the graph structure very well,
and thus negatively influencing the attack performance.

\vspace{-1mm}
\subsection{Beyond GCNs: \linkteller on GATs}
\label{sec:attack-gat}
\vspace{-1mm}
In this section, we aim to study the effectiveness of \linkteller on other GNNs.
Since the rule of information propagation holds almost ubiquitously in GNNs, we hypothesize that our influence analysis based \linkteller can also successfully attack other types of GNNs.
We directly apply~\Cref{alg:attack} on another classical model---Graph Attention Networks (GATs)~\cite{velivckovic2017graph}\m{, aiming to investigate the \textit{transferability} of our influence analysis based attack from GCNs.}

We evaluate the attack on the two large datasets PPI and Flickr introduced in~\Cref{tab:dataset}. For both datasets, we train a 3-layer GAT. We leave details of the architecture and hyperparameters to~\Cref{sec:append-best-para-gat} and report the result in~\Cref{tab:att-gat}.
\m{Although \linkteller still significantly outperforms the baselines, it is less effective than that on GCNs. This is mainly due to the different structures of GCNs and GATs, which leads to different influence calculations for the two models (one related to the graph convolution and the other related to the attention mechanism).
We provide more discussion on conveniently adapting \linkteller to other architectures in~\Cref{sec:append-limit}.
}

\input{tables/tab_attack_gat}

\section{Evaluation of Differentially Private GCN}
\label{sec:dp-gcn}
In this section, we aim to understand the capability of \linkteller attack
by experimenting with potential ways to defend against it.
In particular, we examine whether it is possible to weaken the effectiveness of \linkteller by ensuring the \eedgedpshort guarantee of the GCN model.
We further investigate the utility of the DP GCN models.
In the end, we demonstrate the tradeoff between privacy and utility, which may be of interest to practitioners who wish to use DP GCNs to defend against \linkteller.

In particular,  we aim to evaluate the attack effectiveness of \linkteller and the model utility on four types of models: DP GCN models derived using DP mechanisms \edgerand and \lapgraph, vanilla GCN models which have no privacy guarantee, as well as multi-layer perceptron (MLP) models
with only node features.
We note that MLP can be viewed as ``perfectly" private since the edge information is not involved.

\subsection{Datasets and Models}
\vspace{-1mm}

We use the datasets described in~\Cref{sec:datasets}.
The DP GCN models are derived using DP mechanisms \edgerand and \lapgraph under various privacy guarantees.
For each privacy budget ${\epsilon}$, we execute the procedure outlined in~\Cref{alg:dpgcn}, first getting a perturbed copy of the adjacency matrix, then using the perturbed training graph to train a GCN. We follow the criteria in~\Cref{sec:models}
for parameter searching and model training,
and
leave more descriptions to~\Cref{sec:append-search-space}.

We provide an evaluation of the model utility,
aiming to characterize the tradeoff between model utility and the success rate of \linkteller.
In evaluating the utility of the DP GCNs, we compare with two baseline models: 1) vanilla GCNs which are expected to have higher utility, though vulnerable to \linkteller as previously shown;
2) MLPs trained only on node features which may achieve lower classification utility but provide perfect protection of the edge information due to the non-involvement of edge information in the model.

\input{figs_desc/fig_dp}
\vspace{-1mm}
\input{figs_desc/fig_degree}

\subsection{DP GCN against \linkteller}
\label{sec:eval-dp-attack}
\vspace{-1mm}

We validate the effectiveness of \linkteller under various levels of privacy guarantees.
We first provide the experimental setup, followed by concrete results including comparisons of the attack effectiveness of \linkteller on different models.

\subsubsection{Experimental Setup}

We inspect the effectiveness of \linkteller on DP GCN using the same setup as~\Cref{sec:attack-setup}.
Similar to~\Cref{sec:attack-eval}, we use \textit{precision} and \textit{recall} to evaluate the attack.
For each dataset, we consider all combinations of $2$ DP mechanisms (\edgerand and \lapgraph), $10$ privacy budgets ($1.0,2.0,\ldots,10.0$), $3$ sampling strategies (low, unconstrained, and high degree), and $5$ density beliefs ($k/4, k/2, k,2k,4k$).
The reported result of each scenario is averaged over 3 runs with different random seeds for sampling.

\subsubsection{Evaluation Results}

We leave the full evaluation results for all scenarios
in~\Cref{sec:append-eval-results} and focus on density belief $\hat k=k$  here. In~\Cref{fig:dp-attack}(b), we plot the \textit{F1 score} of the attack w.r.t.
DP budget ${\epsilon}$.
We see that the effectiveness of \linkteller decreases as a result of applying DP. Particularly, the F1 score becomes
almost 0 when the privacy budget ${\epsilon}$ becomes smaller.
When ${\epsilon}$ is large, however, the protection offered by DP is limited. In these cases, \linkteller is able to achieve a success rate close to that of attacking the non-private baseline.

We also note that the node degree distribution has an impact on the performance of \linkteller.
The trend is clear that as the node degree increases, the attack success rate increases substantially.
Together with our previous observation in the non-private scenario that the attack success rate does not differ much for varying node degrees, we conclude that DP can offer better protection to low degree nodes than high degree nodes.
We offer a simple and intuitive explanation as follows.
By the design of \edgerand and \lapgraph,
the perturbations in all cells of the matrix are independent. As a result, nodes of low degree (those incident to fewer edges) are more susceptible to the influence, and therefore better protected by DP.

\subsection{Model Utility Given DP Protection}
\label{sec:eval-dp-util}
\vspace{-1mm}

We next present the evaluation of the model utility, not only to complement the evaluation of the DP GCNs, but also to provide insights about the tradeoff between model utility and robustness against the \linkteller attack.

\subsubsection{Experimental Setup}

We evaluate the influence of applying DP (\edgerand and \lapgraph) on the utility of the GCN models by comparing the results with two baseline models (a non-private vanilla GCN model and a ``perfectly'' private MLP baseline).
We adopt the same metric to evaluate the utility of all four models:
F1 score of the rare class for the twitch datasets and micro-averaged F1 score for PPI and Flickr datasets. The rationale is put in~\Cref{sec:append-eval-metrics}.

\subsubsection{Evaluation Results}

The figures for the model utility are presented in~\Cref{fig:dp-attack}(a). We plot the change of the utility with the increase of privacy budget of two DP mechanisms \edgerand{} and \lapgraph{}, as well as the utility of two baseline models independent of the privacy budget.
For each privacy budget ${\epsilon}$, the reported results are averaged over 10 runs for different random seeds.
We examine~\Cref{fig:dp-attack}(a) to see how the model utility of DP methods compares with the baselines.
We first compare the performance of two baseline models: GCN (the black horizontal line) and MLP (the red line).
We note that
GCN is almost always better than MLP except on the PPI dataset.
The observation is well suited to our intuition that the knowledge of the graph structure can benefit learning.
For most datasets, the model utility increases with the growth of the privacy budget, since the privacy protection to the graph structure becomes weaker.
However, \textbf{twitch-ENGB} is an exception that achieves slightly higher utility when more privacy noise is added.
This may be due to the following reason.
For twitch datasets, the model is trained on the graph of twitch-ES and   tested on graphs of other five countries.
When the training and testing graph distribution distance is too large, there is no guarantee that the performance on the training graph can be transferred to the testing graph.
This is the case for twitch-ENGB, which is an extremely sparse graph (see~\Cref{tab:dataset}(a)) compared with the training graph. Thus, with slightly more random noise added, its generalization may be improved.
\m{In addition to the evaluation over a range of ${\epsilon}$, we also evaluate such tradeoff of model utility and privacy resiliency by selecting appropriate ${\epsilon}$ based on a validation dataset. The detailed setups and results are omitted to~\Cref{sec:append-choice}.}

\vspace{-1mm}
\subsection{Tradeoff between Model Utility and Privacy}
\label{sec:tradeoff}
\vspace{-1.5mm}

We analyze the tradeoff between model utility and the attack performance:
models with high utility tend to be more vulnerable to \linkteller.
The sweet spot differs across datasets and scenarios.
Summarizing the observations, we derive a series of conclusions on \textit{how to protect privacy given the gap of the model utility between the vanilla GCN and the MLP model}.
\textbf{First}, if the utility of the vanilla GCN is much higher than the MLP model, then
there is space for performance degradation caused by ensuring privacy.
We do observe a few cases
where the utility of the DP model is above the MLP baseline, and the attack success rate at that point is relatively low, especially under the low degree case, \eg, the DP model on twitch-RU when ${\epsilon}=7$.
In such cases, carefully choosing an ${\epsilon}$ will give the practitioner fairly good \textit{utility} and a certain level of \textit{privacy} guarantee simultaneously.
\textbf{Second}, when the performance of the vanilla GCN only exceeds MLP by a small margin,
almost all DP models that can effectively defend against the attack suffer tremendous utility loss.
We point out that most scenarios fall under this category, where either privacy or utility will be sacrificed. This further substantiates the power of \linkteller.
\textbf{Third}, when the graph structure hurts learning (\eg, PPI), we may avoid using the graph structure in training by using MLP. There might exist other graph neural networks that can achieve better performance on datasets like PPI, and applying
\linkteller to these models are exciting future work.

\textbf{Utility and privacy of low-degree nodes.}\quad
As noted in~\Cref{sec:eval-dp-attack}, DP GCN offers better protection to nodes of low degree.
A natural question is then: \textit{does better protection imply a degradation of utility of these nodes?}
To answer this question, we separate the nodes into bins by degree (\eg, 1-5, 6-10, $\ldots$, 46-50, 50-), and investigate the F1 score of nodes in each individual bin.
The results on all datasets, two DP mechanisms, with three privacy budgets are presented in~\Cref{fig:dp-degree}.
We can see that the utility for low-degree nodes does not drop faster than high-degree nodes when the privacy budget decreases,
which indicates that DP GCN does not sacrifice the utility of low-degree nodes particularly.

\textbf{Discussion: \edgerand{} or \lapgraph{}.}\quad
\label{sec:discussion}
We further compare the results of the two mechanisms regarding model utility and attack success rate.
When ${\epsilon}$ is small, the utility of \edgerand and \lapgraph do not differ much (especially on PPI).
When ${\epsilon}$ is large, \edgerand{} generally has better model utility, while \lapgraph is more robust to \linkteller.
The results for \edgerand are incomplete for the large scale dataset Flickr under tight privacy budgets (${\epsilon}\in\{1,2,3,4\}$) using \edgerand.
Under these cases, the graphs become much denser after perturbation of large magnitudes, and we experience an OOM error using an 11 GB GPU.
In comparison, \lapgraph does not suffer such an issue.

\section{Related Work}
\subsubsection{Privacy Attack on Graphs}
This topic was widely studied~\cite{ZheGet07preserve,hay2007anonymizing,zhang09anonymity,runden12perturb} before graph neural networks came into play.
There are mainly three types of privacy attacks on graphs: identity disclosure, attribute disclosure, and link re-identification~\cite{ZheGet07preserve}, corresponding to different components (nodes, node attributes, and edges) of a graph.
In this paper, we focus on \textit{edge privacy}. Previous endeavors have illustrated
the feasibility of the link re-identification attack,
whilst
relying on strong prior knowledge and
information that arguably might not
always hold or accessible.
For example,
when prior knowledge about
the graph is available---\eg,
nodes with similar attributes or
predictions are likely connected---He \etal~\cite{he2020stealing} claim that an attacker could infer links
in the training graph
by applying methods such as
clustering to predict connections for nodes within the same cluster.
Duddu \textit{et al.}~\cite{duddu2020quantifying}
show that with access to the node embeddings
trained to preserve the graph structure,
one can recover edges by analyzing predictions based on the embeddings.
Apart from the privacy attacks, there exist other adversarial attacks on GNNs, \eg, against node embeddings~\cite{bojchevski2019adversarial} and
graph- and node-level classifiers~\cite{dai2018adversarial}.
Despite the promising attacks illustrated by these
early endeavors, there is a clear need to
weaken the assumptions for more reliable, practical settings.
In this paper, we thus answer:  to what extent can we recover
private edges of a graph by  probing
a trained blackbox GNN model
\textit{without} strong
prior knowledge? Could we leverage the property of influence propagation among nodes in GNNs to design an effective attack?

\subsubsection{Differential Privacy for Graphs}

Differential privacy~\cite{dwork14dp} is a notion of privacy that entails that the outputs of the model on neighboring inputs are close. This privacy requirement ends up obscuring the influence of any individual training instance on the model output.
There are a series of works that examine the theoretical guarantee or the practical performance of models under differential privacy guarantees~\cite{li2013membership,Yeom2018PrivacyRI,jayaraman2019evaluating,erlingsson2019that,jayaraman2020revisiting,humphries2020differentially}.
Depending on the properties of the datasets, \eg, the distinction between the distribution of members and non-members and the underlying correlations within the datasets, there is no trivial answer to this problem.

The extension of differential privacy to the graph setting was first conducted in Hay \etal~\cite{hay2009accurate}.
Since then, there has been extensive research on computing graph statistics such as degree distribution~\cite{hay2009accurate}, cut queries~\cite{blocki2012johnson}, and sub-graph counting queries~\cite{blocki2013differentially} under edge or node differential privacy.
These statistics are useful for graph analysis but insufficient for training a GCN model. Thus, in this paper, to evaluate the strength of the \linkteller attack, we adapt one existing algorithm \edgerand and propose a Laplacian mechanism \lapgraph for training DP GCN models as evaluation baselines.

\iffalse
For example, when the graph embeddings are publicly released, it is possible to infer the graph structure and the node attributes of the private training graph~\cite{duddu2020quantifying}.
\textcolor{red}{ }
\textcolor{red}{
Despite these previous explorations,
two questions linger: (1)
To what extent can we recover
private edges of a graph by simply probing
a trained graph neural network models
\textit{without} any strong
prior knowledge? and
(2) To what extent can we defend against
edge recovery attacks via differential
privacy and how can we characterizie
the underlying fundemental
tradeoff between model ulitlity and
vulnerability?}

When the background knowledge (\eg, node attributes/partial graph of the private training graph) is available, an attacker can effectively infer the links in the training graph~\cite{he2020stealing}.

Despite the extensive analysis of different attack scenarios based on varying assumptions provided in these works,
in reality, not all scenarios are practical or equally important/concerning.
Upon this, we point out that,
to better understand the privacy concerns in the application of GCNs, it is more recommended to motivate our problem with real-world examples, so as to provide constructive insights for researchers and practitioners in specific domains.
\fi

\iffalse
Therefore, in order to jointly maximize the data utility of different data holders while respecting the privacy requirement when training GCN models,
novel learning paradigms or interaction models need to be adopted. For example, Zhou \textit{et al.}~\cite{zhou2020privacy} recently proposed a Privacy-Preserving GNN (PPGNN) paradigm that operates on vertically partitioned data, which is one special case of data isolation. They separate the computation graph into two parts: private data related computation on data holders and the remaining computation on a semi-honest server. Through Multi-Party Computation (MPC) at the individual level, privacy is guaranteed during training.
During inference, \textcolor{red}{XXX ... ... ...}
\fi

\section{Conclusions}

We propose
the first edge re-identification attack \linkteller via influence analysis against GNNs.
We also evaluate \linkteller against differentially private GNNs trained using an existing  and a proposed DP mechanisms \edgerand and \lapgraph to understand the capability of the attack.
Extensive experiments on real-world datasets \m{(8 for  inductive  and 3 for  transductive setting)} demonstrate the effectiveness of \linkteller in revealing private edge information, even when there are certain privacy guarantees provided by a DP mechanism.

We believe this work will inspire a range of  future research opportunities
and lay down a foundation
for future explorations by providing a clear data isolation problem setup, analysis of edge privacy, together with extensive empirical observations and conclusions.

\noindent\textbf{Acknowledgement.}
This work is partially supported by the
NSF grant No.1910100, NSF CNS 20-46726 CAR, NSF TRASE (ECCS-2020289), and Amazon Research Award.

\newpage

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv