Counterfactual Graph Learning for Link Prediction
Authors: Tong Zhao
Gang Liu
Daheng Wang
Wenhao Yu
Meng Jiang
Venue: NeurIPS 2021 Submitted (2021)
Keywords: link prediction
counterfactual inference
graph representation learning

Abstract: Learning to predict missing links is important for many graph-based applications. Existing methods were designed to learn the observed association between two sets of variables: (1) the observed graph structure and (2) the existence of link between a pair of nodes. However, the causal relationship between these variables was ignored and we visit the possibility of learning it by simply asking a counterfactual question: "would the link exist or not if the observed graph structure became different?" To answer this question by causal inference, we consider the information of the node pair as context, global graph structural properties as treatment, and link existence as outcome. In this work, we propose a novel link prediction method that enhances graph learning by the counterfactual inference. It creates counterfactual links from the observed ones, and our method learns representations from both of them. Experiments on a number of benchmark datasets show that our proposed method achieves the state-of-the-art performance on link prediction.

Counterfactual Graph Learning for Link Prediction
Anonymous Author(s)
Affiliation Address email
Abstract
Learning to predict missing links is important for many graph-based applications. Existing methods were designed to learn the observed association between two sets of variables: (1) the observed graph structure and (2) the existence of link between pair of nodes. However, the causal relationship between these variables was ignored and we visit the possibility of learning by simply asking counterfactual question: "would the link exist or not if the observed graph structure became different?" To answer this question by causal inference, pair as context, global graph structural properties as treatment, and link existence as outcome. In this work, we propose a novel link prediction method that enhances graph learning by the counterfactual inference. It creates counterfactual links from the observed ones. and our method learns representations from both of them. Experiments on a number of benchmark datasets show that our proposed method achieves the state-of-the-an performance on link prediction.
2
consider the information of the node
10
11
13
Introduction
14
Link prediction seeks to predict the likelihood of edge existence between node pairs based on the observed graph. Given the omnipresence of graph-structured data, link prediction has copious applica- tions such as movie recommendation (Bennett et al., 2007), chemical interaction prediction (Stanfield et al., 2017), and knowledge graph completion (Kazemi and Poole, 2018). Graph machine learning methods have been widely applied solve this problem. Their standard scheme is first learn the representation vectors of nodes and then learn the association between the representations of a pair of nodes and the existence of the link between them. For example, graph neural networks (GNNs) neighborhood aggregation to create the representation vectors: the representation vector of node computed by recursively aggregating and transforming representation vectors of its neighboring 24 nodes (Kipf and Welling, 2016a; Hamilton et al., 2017; Wu et al., 2020). Then the vectors are fed
16
18
20
21
22
23
25 into a binary classification model to learn the association. GNN methods have shown predominance
26 in the task of link prediction (Kipf and Welling. 2016b; Zhang and Chen, 2018; Zhang et al., 2020a).
Unfortunately, the causal relationship between graph structure and link existence was largely ignored in the previous work. Existing methods that learn from association only were not able to capture essential factors accurately predict missing links in the lest data. Take social network as example. Suppose Alice and Adam live in the same neighborhood and they are close friends. The association between neighborhood belonging and friend closeness could be too strong discover the essential factors of the friendship such as common interests or family relationship which could be the cause of being living the same neighborhood. So, our idea is to ask counterfactual question: "would Alice and Adam still be close friends if they were not living in the same neighborhood?" If graph learning
28
30
31
32
33
34
35 model could learn the causal relationship from data by asking the counterfactual questions, it would
36 improve the performance of link prediction with the novel knowledge it captured. Generally, the questions can be described as "would the link exist or not if the graph structure became different?"
37
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

Factual link:
Factual treatment: Same neighborhood
Decoder
GNN Encoder
Alice
Shared
Helan
Adam
Decoder
(Alice, Adam) Most similar with a (Helen, Bob) different treatment
Counterfactual treatment: Different neighborhoods
Counterfactual link:
Factual link:
Counterfactual link:
(a) Find counterfactual link as the most simi- lar node pair with different treatment.
(b) Train GNN-based link predictor to predict factual and counterfactual links given the corresponding treatments.
The proposed CFLP learns the causal relationship between the observed graph structure (c.g., neighborhood similarity, considered as treatment variable) and link existence (considered as outcome). In this example, the link predictor would be trained to estimate the individual treatment effect (ITH) as
Figure 1:
0 so it looks for factors other than neighborhood to predict the factual link.
38 As known to many, counterfactual question is a key component of causal inference and have been well defined in the literature. A counterfactual question is usually framed with three factors: context (as data point), manipulation (e.g., treatment, intervention, action, strategy), and outcome (van der Laan and Petersen, 2007; Johansson et al., 2016). (To simplify the language, we use "treatment" to refer to the manipulation in this paper, readers might be familiar more with the word "treatment.") Given certain data context, it asks what the outcome would have been if the treatment had not been the observed value. In the scenario of link prediction, as context, graph structural properties as treatment, and link existence as outcome. Recall the social network example. The context is Alice and Adam, which includes their personal attributes and relationships with others on the network. The treatment is living in the same neighborhood, which can be given one attribute or identified by community detection. And the outcome is their friendship.
39
41
43
consider the information of pair of nodes
45
46
47
48
49
In this work, we present a counterfactual graph learning method for link prediction (CFLP) that trains graph learning models to answer the counterfactual questions. Figure illustrates this two-step 51 method. Suppose the treatment variable is defined as one type of global graph structure, c.g., the neighborhood assignment discovered by spectral clustering community detection algorithms. We are wondering how likely the neighborhood distribution makes a difference on the link (non-)existence for each pair of nodes. So, given pair of nodes (like Alice and Adam) and the treatment value this pair (in the same neighborhood), we find a pair of nodes (like Helen and Bob) that satisfies two conditions: (1) it has different treatment (in different neighborhoods) and (2) it is the most similar pair with the given pair of nodes. We call these matched pair of nodes as "counterfactual links." " Note that the outcome of the counterfactual link can be either 1 or 0, depending on whether there exists an edge between the matched pair of nodes. The counterfactual link provides unobserved outcome to the given pair of nodes (Alice and Adam) under counterfactual condition (in different neighborhoods). After counterfactual links are created for all (positive and negative) training examples, CFLP trains a link predictor (which can be
59
55
56
57
58
59
60
61
62
learn the representation vectors of nodes to predict both the observed factual links and the counterfactual links. In this Alice-Adee Adam example, the link predictor is trained to estimate the individual treatment effect (ITE) of neighborhood assignment as
63
64
65
1 1 = 0. So, the leamer will try to discover the essential factors the friendship between Alice and Adam. For some other examples, if the outcome of counterfactual link is different from that of
66
67
the given pair of nodes, the learner will estimate the strong effect of the treatment variable. Therefore, CFLP enables graph learning models to predict missing links regarding causal relationship.
68
89
Contributions. Our main contributions can be summarized as follows. (1) This is the first work that proposes improve link prediction by causal inference, specifically, learning to answer counterfactual questions about link existence.
70
(2) This work introduces CFLP that trains GNN-based link predictors to predict both factual and counterfactual links. learns the causal relationship between global graph structure and link existence. (3) CFLP outperforms competitive baseline methods on several 73
71
72
74 benchmark datasets. On OGB-DDI, our CFLP achieves the state-of-the-an performance. We analyze the impact of counterfactual links as well as the choice of treatment variable. This work sheds insights
76 for improving graph machine learning with causal analysis, which has not been extensively studied yet, when the other direction (machine learning for causal inference) has been studied for long time.

---

78 2
Preliminary
Notations Let G (V.E) be undirected graph of N nodes, where V = {UI, ........ UN is 80 the set of nodes and & _ V x V is the set of observed links. We denote the adjacency matrix as 81 A E {0, 1jNNN, where A, 1 indicates nodes v and 2 are connected and vice versa. We denote the node feature matrix as X E R NNF,, where F is the number of node features and x; (bolded) indicates the feature vector of node 2/ (the i-th row of X).
83
84
Counterfactual Learning Let X' be the set of contexts, y be the set of outcome values, and T be the set of treatments. For a context æ E X and a treatment i E 'T, we denote the outcome of under the treatment t by (x)) E V. Ideally, we would need all possible outcomes of z under all kinds of treatments to study the causal relationships (Morgan and Winship, 2015). However, in reality, only one treatment was applied and thus only one outcome was observed for a given context æ. When the variables are specified in data, people use Neyman-Rubin casual model (BCM) to develop statistical learning methods such as propensity score matching (PSM) for causal inference (Rubin, 1974, 2005).
85
86
87
88
89
90
91 In this work, we look at link prediction on graphs. Here we define the variables of counterfactual learning in this scenario. Given a graph G. a context is a pair of nodes x = (v,, 2y) in the graph; and thus, X' V V. The outcome variable Y (xx) )) is naturally binary. indicating whether link exists between the node pair æ;; and thus, y = {0. 1). We study the causal effect of binary treatment variable
92
93
94
T = f0, 1), where the value of Yi (x) - Yo()) for a particular context x is of high interest and known as the individualized treatment effect (ITE) (van der Laan and Petersen, 2007; Weiss et al., 2015). The value of ITE indicates the causality relationship between the treatment and outcome on the context. And the expected ITE given the context distribution is called averaged treatment effect (ATE). i.e., ATE Ex~x ITE(2;), for a particular treatment variable.
95
96
97
98
99
100
However, as aforementioned. the fact that we can only observe one potential outcome under one particular treatment prevents the ITE from being known (Johansson et al., 2016). In the problem setting of link prediction, we refer the observed adjacency matrix as the factual outcomes A and the unobserved adjacency matrix when the treatment is different as the counterfactual outcomes A CF
101
102
103
We denote T E {0, 1] | NNN as the factual treatment matrix, where Tú, indicates the treatment of the node pair (v,, 22). We denote TCF as the counterfactual treatment matrix where T.CF 1 - Ti.-
104
105
We are interested in (1) estimating the counterfactual outcomes A CF via observed data, (2) learning with the counterfactual adjacency matrix A CF to enhance link prediction, and (3) learning the causal relationship between graph structural information (treatment) and link existence (outcome).
106
107
108
3 The Proposed Method
110
In this section, we introduce CFLP, novel counterfactual graph learning method for link prediction. In Section 3.1, we define treatment variable and counterfactual outcomes/links on graph data and present how to compute them (Figure (a)). In Section 3.2, we introduce the graph learning model that learns from both the observed graph and the created counterfactual links (Figure 1(b)).
111
112
113
114
3.1
Defining Treatment Variable and Counterfactual Links
115
Treatment Previous work graph machine learning (Velickovic et al., 2019; Park et al., 2020) showed that the graph's 's global structural information could improve the quality of representation vectors of nodes learned by GNNs. This is because the message passing- based GNNs aggregate local information in the algorithm of representation vector generation and the global structural information is complementary with the aggregated information. Therefore, for a pair of nodes, one option of defining the treatment variable is its global structural role in the graph. Without the loss of generality, we use Louvain (Blondel al., 2008), an unsupervised approach that has been widely used for
116
118
120
121
122
community detection, as an example. Louvain discovers community structure of a graph and assigns
123
each node to one community. Then we can define the binary treatment variable as whether these
124
two nodes in the pair belong to the same community. Let e V + N be any graph mining/clustering that each node belongs to. The
method that outputs the index of communityyclusserreiigoortt
125
128
treatment matrix T is defined as
[1
if c(u.) = c(vy);
Tij 0 otherwise.
(1)
3

---

127
For the choice of c, we suggest methods that group nodes based on global graph structural information, including but not limited to Louvain (Blondel al., 2008), K-core (Bader and Hogue, 2003). and spectral clustering (Ng et al., 2001).
128
129
130
As mentioned in Section 2, for each node pair (context), the observed data contains only the factual treatment and outcome, meaning that the link existence for the given node pair with an opposite treatment is unknown. Therefore, we use the outcome from the nearest observed context as substitute. This idea has been adopted by many methods (Johansson et al., 2016; Alaa and
Counterfactual Links
131
132
133
134
Van Der Schaar, 2019). That is, we want to find the nearest neighbor with the opposite treatment for each observed node pairs and use the nearest neighbor's is outcome as a counterfactual link. Formally,
135
136
Ve, vy) E V x V, we want to find its counterfactual link (Va: 1b) as below:
(Va: Ub) arg min (iiiin((((() (d(((t (Vas vb)) To.6 Vo
Tish.
137
where -): is a metric of measuring the distance between pair of node pairs (a pair of contexts). Considering that we want to find the nearest node pair based on not only the raw node features but also structural features, here we take the state-of-the-art unsupervised graph representation learning method MVGRL. (Hassani and Khasahmadi, 2020) to learn the node embeddings X E NxF from the observed graph. We use X to find the nearest neighbors of node pairs. Nevertheless, finding the nearest neighbors by computing the distance between all pairs of node pairs is extremely inefficient, which takes ( ) comparisons (as there are totally (NN) node pairs), Hence we approximate Eq. (2) by substituting the distance between node pairs by the distance between nodes. That is,
138
139
140
141
143
145
v(Ue, U1) E V x V, we want to find its counterfactual link (Va: Ub) as below:
(Va: 1b) = arg min (d(2,, x.) + x6) To,b 1 - T d(i,, Xa) Re) < 27), (3) VVV
148
where d(-,,) .) is specified as the Euclidean distance on the embedding space of X. and ry is a hyperpa- rameter that defines the maximum distance that two nodes are considered as similar. Note that when
147
148
no node pair satisfies the above equation, we do not assign any nearest neighbor for given node pair
149
to ensure all the neighbors are similar enough (as substitutes) in the feature space. Therefore, the counterfactual treatment matrix TCF and the counterfactual adjacency matrix A CF are defined as
150
CF [1 11 Tij, Aa, if 3 (Va, vb) E V x V satisfies Eq. (3);
TCP , ACP
(4)
(T.
otherwise.
151
It is worth noting that the node embeddings X and the nearest neighbors are computed only once and do not change during the learning process. X is only used for finding the nearest neighbors.
152
159
Learning from Counterfactual Distributions Let P be the factual distribution of the observed contexts and treatments, and PCF be the counterfactual distribution that is composed of the observed
154
contexts and opposite treatments. We define the empirical factual distribution PF ~ PF as PF
155
(vi, Uj [e and define the empirical counterfactual distribution PCF ~ pCF as pCF
156
{U; Bg, T Unlike traditional link prediction methods that take only fF as input and use the observed outcomes A as the training target, the idea of counterfactual graph learning is to take advantage of the counterfactual distribution by having PCF as complementary input and use the counterfactual outcomes A CF as the training target for the counterfactual data samples.
157
158
159
160
161
3.2
The Counterfactual Graph Learning Model
162
In this subsection, we present the design of our model as well as the training method, The input of the model in CFLP includes (1) the observed graph data A and raw feature matrix X. (2) the factual treatments T and counterfactual treatments TCF and (3) the counterfactual graph data A CF The
163
184
output contains link prediction logits in A and A CF for the factual and counterfactual adjacency matrices and CF,, respectively.
186
167
Graph Learning Model The model consist of two trainable components: graph encoder / and link decoder g. The graph encoder generates representation vectors of nodes from graph data G. And the link decoder projects the representation vectors of node pairs into the link prediction logits. The
188

---

170 choice of the graph encoder f can be any end-to GNN model. Without the loss of generality, here
171 we use the commonly used graph convolutional network (GCN) (Kipf and Welling, 2016a). Each
172
layer of GCN is defined as
(5) where / is the layer index, Á = A I is the adjacency matrix with added self-loops, is the diagonal degree matrix D., = Σ₁ A., H = X. w is the learnable weight matrix at the 1-th layer, and a-)) denotes nonlinear activation such ReLU. We denote Z = f(A, X) E RNN* as the output from the encoder's last layer, i.e., the /--dimensional representation vectors nodes. Following previous work (Zhang al., 2020a),
H (A, (11); w (D AD $ H (w))).
173
174
176
compute the representation of node pair as the Hadamard product of the vectors of the two nodes. That is, the representation for the node pair (U, U2) is C z E R", where @ stands for the Hadamard product.
178
180
For the link decoder that predicts whether a link exists between a pair of nodes, we opt for simplicity and adopt simple decoder based on multi-layer perceptron (MLP), given the representations of node pairs and their treatments. That is, the decoder g defined as
182
A = 9(Z, T), where A.s- = MLLP((, ① Zj, Tisl),
(6)
A g(Z, gZZ TCF), where A. MLP((Z, @ Zz. Ti5 1
183
where [ stands for the concatenation of vectors.
During the training process, data samples from the empirical factual distribution pF and the em- pirical counterfactual distribution PCF are fed into decoder g and optimized towards A and CF respectively. That is, for the two distributions, the loss functions are as follows:
184
185
186
CF
1 N2
An. log Ang + (1 - Ais) llog1 - Aig),
(8)
j=1
N
N
LCF
CF b.
log A +(1 - - log(1 - -A93)
N2
187
Balancing Counterfactual Learning In the training process, the above loss minimizations train the
model on both the empirical factual distribution po ~ pF and empirical counterfactual distribution per pCF that are not necessarily equal - the training examples (node pairs) do not have to be aligned. However, the stage of inference, the test data contains only observed (factual) samples.
188
189
190
Such gap between the training and test data distributions exposes the model in the risk of covariant shift, which is a common issue in counterfactual learning (Johansson et al., 2016; Assaad et al., 2021).
192
193
To force the distributions of representations of factual distributions and counterfactual distributions to be similar, we use the discrepancy distance (Mansour al., 2009; Johansson al., 2016) as another objective to regularize the representation learning. That is, we use the following loss term to minimize the distance between the learned representations from pr and pCF:
194
185
196
Laise dis((Pf,PPF)
PFF)) where disc Q) ||P 1PP-QleF
(10)
197
where| ||
|| denotes the Frobenius Norm, and P and PCr denote the node pair representations learned by graph encoder f from factual distribution and counterfactual distribution, respectively.
198
Training During the training of CFLP, want the model to be optimized towards three targets:
200
(1) accurate link prediction on the observed outcomes (Eq. (8)), (2) accurate estimation on the
counterfactual outcomes (Eq. (9)), and (3) regularization on the representation spaces learned from
of and PCF (Eq. (10)). Therefore, the overall training loss of our proposed CFLPin is
202
= Lr + LCF + B Ldise:
(11)
203
where a and 3 are hyperparameters to control the weights of counterfactual link prediction (outcome estimation) loss and diserepancy loss.
5

---

Table 1: Statistics of datasets used in the experiments.
Dataset
CORA CITESEER
PUBMED
FACEBOOK
OGB-DDI
nodes
2,708
3,327
19.717
4,039
4,267
# links
5,278
4,552
44,324
88,234
1,334,889
# validation node pairs
1,054
910
8,864
17,646
235,371
# test node pairs
2.110
1,820
17.728
35,292
229,088
205
Summary Algorithm summarizes the whole process of CFLP. The first step is to compute the factual and coun- terfactual treatments T. TCF as well
Algorithm 1: CFLP: Counterfactual graph learning for link prediction
208
207
Input : : g. A, X, reeepochs, n_epoch ft
208
Compute T by Eq. (I):
209
as the counterfactual outcomes A C.F.
Compute TCF A CF by Eqs. (3) and (4)
210
Then, the second step trains the graph learning model on both the observed factual data and created counterfactual data with the integrated loss function (Eq. (11)). Note that the discrepancy loss (Eq. (10)) is computed on the rep- resentations of node pairs Iearned by the graph encoder f. the decoder
/* model training
*/
Initialize , in I and 6g in g:
212
for epoch in range(n (cceeenn___cs) do
5
Z =
214
Get and C via with Eqs. (6) and (7):
7
Update e and 0g with L;
// (11)
216
end
/* decoder fine-tuning
*/
g is trained with data from both pf and PCF without balancing the con- straints. Therefore, after the model is sufficiently trained, we freeze the graph encoder f and fine-tune with only the factual data. Finally, after the decoder
218
Freeze O, and re-initialize θ,,
10 Z = [()
220
11 for epoch in range(n_epochs__ _epcch__ftt do
221
12
Get A via with Eq. (6);
222
13
Update O2 with LF;
// Eq. (8)
224
223
is sufficiently fine-tuned, we output the link prediction logits for both the fac- tual and counterfactual adjacency ma- trices.
14
end
/* model inferencing
225
15 Z [A,, x);
226
16 Get A and À CF via with Eqs. (6) and (7);
227
Output: Å for link prediction, CF
Complexity The complexity of the first step (finding counterfactual links with nearest neighbors) is proportional to the number of node pairs. When y is set as a small value to obtain indeed similar node pairs, this step (Bq. (3)) uses constant time. Moreover, the computation in Eq. (3) can be parallelized. Therefore, the time complexity is O(N2/CC where C' is the number of processes. For the complexity of the second step (training counterfactual learning model), the GNN encoder has time complexity of O + LH( (Wu al., 2020), where L is the number of GNN layers and И is the size of node representations. Given that we sample the same number of non-existing links as that of observed links during training, the complexity of three-layer MLP decoder is (((H++1 -d, + d, 1){El) =
229
230
231
232
233
234
235
236
237
O (d, H + 2)) where d, is the number of neurons in the hidden layer. Therefore, the second step
238
has linear time complexity w.r.t. the sum of node and edge counts.
First, mentioned above, the computation of finding counterfactual links has worst- case complexity of O(N2). Second, CFLP performs counterfactual prediction with only a single treatment; however, there are quite few kinds of graph structural information that can be considered as treatments. Future work can leverage the rich structural information by bundled treatments (Zou al., 2020) in counterfactual graph learning.
Limitations
240
241
242
243
Experiments
244
245
4.1
Experimental Setup
We conduct experiments on five benchmark datasets including citation networks (CORA, CITESEER, PURMED (Yang et al., 2016)), social network (FACEBOOK (McAuley and Leskovec, 2012)), and drug-drug interaction network (OGB-DDI (Wishart et al., 2018)) from the Open Graph Benchmark
247

---

Table 2: Link prediction performances measured by Hits 20. Best performance and best baseline performance are marked with bold and underline, respectively.
CORA
CITESBER
PUBMED
FACEBOOK
OGB-DDI
Node2Vee 49.96112.51
47.78
39.19:1.02
24.24::3022
23.26:12.09
MVGRI.
19.5342.64
14.07+0..99
14.19+00.85
14.43+00.3
1..02++.001
VGAE
45.91+33.38
44.04+44.86
23.73+11611
37.01+0..3
11.71+1.96
SEAL
51.35+2.26
43.60
28.45++3.81
40.89+45.0
30.56++3.86
LGLP
02.9810.556
57.43
37.86:12.13
GCN
1..06.11.72
13.5611132
21.8411..77
53,89:12.144
37.0715.07
GSAGE
53.54112.96
$3.67112.94
39.13:14.41
45.51
53.90.14.74
JKNet
48.2143.86
55.60+2.11
25.64+4.11
52.25+1.48
60.56
Our proposed CFLP with different graph encoders
CFLP w/ GCN
6..34.1..3
59.45112.30
34.12:12.72
$3.95.12.29
52.51 1.09
CFLP w/ GSAGE
1..33:11.73
53.05122.07
43.07:12.36
47.28
75.49-14.33
CFLP w/ JKNet 65.57=11005
68.09+1.49
44.90+2.00
15.22=
86.08
249
(OGB) (Hu al., 2020). For the first four datasets, we randomly select 10%/20% of the links and the same numbers of disconnected node pairs as validation/test samples. The links in the validation and test sets are masked off from the training graph. For OGB-DDI, we used the OGB official train/ arain/validation/tes splits. Statistics for the datasets are given in Table and details are in Appendix. We use K-core (Bader and Hogue, 2003) clusters as the default treatment variable. We evaluate CFLP on three commonly used GNN encoders: GCN (Kipf and Welling, 201 6a), GSAGE (Hamilton et al., 2017), and JKNet (Xu et al., 2018). We compare the link prediction performance of CFLP against Vec (Grover and Leskovec, 2016), MVGRL (Hassani and Khasahmadi, 2020), VGAE (Kipf' and Welling, 2016b), SEAL (Zhang and Chen, 2018), LGLP (Cai et al., 2021), and GNNs with MLP decoder. We report averaged test performance and their standard deviation over 20 runs with different random parameter initializations. Other than the most commonly used of Area Under ROC Curve (AUC), report Hits @ 20 (one of the primary metrics OGB leaderboard) metric, as it expects models to rank positive edges higher than nearly all negative edges.
250
251
253
255
257
259
more challenging
261
Besides performance comparison on link prediction, we will answer two questions to suggest way of choosing a treatment variable for creating counterfactual links: (Q1) Does CFL.P sufficiently learn the observed averaged treatment effect (ATE) derived from the counterfactual links? (Q2) What is the relationship between the estimated ATE learned in the method and the prediction performance? If the answer QI is yes, then the answer to Q2 will indicate how to choose treatment based observed ATE. To answer the Q1, caleulate the observed ATE (ATEg)e) by comparing the observed links in A and created counterfactual links A CF that have opposite treatments. And we calculate the estimated ATE (ATE,st) by comparing the predicted links in Å and predicted counterfactual links CF Formally, ATEobe and ATE st are defined as
263
265
268
270
N
ATEobs
1
Σ
(T
(INNN TRxx--II -T) (A A)l
(12)
N
1=1
ATE
(INxN-TT -OW +
(ACF -
-Ah
(13)
N
271
The treatment variables we will investigate are usually graph clustering or community detection meth- ods, such as K-core (Bader and Hogue, 2003), stochastic block model (SBM) (Karrer and Newman, 2011), spectral clustering (SpeeC) (Ng al., 2001), propagation clustering (PropC) (Raghavan et al.,
273
274
2007), Louvain (Blondel et al., 2008), common neighbors (CommN), Katz. index, and hierarchical clustering (Ward) (Ward Jr, 1963). We use JKNet (Xu et al., 2018) as the default graph encoder.
275
278
Implementation details and supplementary experimental results (e.g., sensitivity on ablation study on LCF and Edise) can be found in Appendix. Source code is available in supplementary material.
277
4.2
Experimental Results
279
Link Prediction Tables and show the link prediction performance of Hits and AUC by all methods. LGLP on PUBMED and OGB-DDI missing due to the out of memory error when
7

---

Table 3: Link prediction performances measured by AUC. Best performance and best baseline performance are marked with bold and underline, respectively.
CORA
CITESBER
PUBMED
FACEBOOK
OGB- DDI
Node2Vee 84.49=0.49
80.0010.68
80.32:10.29
86.4911..2
90.8310.02
MVGRI.
+3.67
61.20++0.55
8..78+
79.83+0.30
01.45
VGAE
88.68+00.4
85.35++0.60
95.80++0.13
98.66++0.04
93.08+00.1
SEAL
92.55+0.550
85.82++0.44
96.36++0.28
99.60+0.02
97.85+0.117
LGLP
91.30110.05
89.4111.113
98.5110.01
GCN
90.25110.53
1..4711.40
96.33110.80
99.43110.02
99.82110.05
GSAGE
90.24.10.34
87.3811..3
96.78.10.11
99.29110.04
99.93110.02
JKNet
89.05
88.58 1.78
96.58+0.23
99.43+0.02
99.94+0.01
Our proposed CFLP with different graph encoders
CFLP w/ GCN
92.55.10.50
89.65110.20
96.99.10.08
99.38
99.44.10.05
CFLP w/ GSAGE
92.61
91.84.10.20
97.01110.01
99.34110.10
99.83110055
CFLP w/ JKNet 93.05=:0.24
92.12=:0447
97.53+0.17
99.31
99.94+0.01
281
running the code package from the authors. We observe that our CFLP on different graph encoders achieve similar or better performances compared with baselines. The only exception is the AUC on FACEBOOK where most methods have tlose-to-perfect AUC. As AUC a relatively easier metric comparing with Hits @ 20, most methods achieved good performance on AUC. We observe that CFLP
283
284
285
with JKNet almost consistently achieves the best performance and outperforms baselines significantly
286
on Hits @ 20. Specifically, compared with the best baseline, CFLP improves relatively by 16.4% and
287
0.8% on Hits 20 and AUC, respectively. It is worth noting that CFLP with JKNet achieves the
288
state-of-ther the-art performance on the official leaderboard of OGB-DDL.
289
Figure shows the AUC performance of CFLP on CORA with different combinations of and 3. We observe that the performance the poorest when 3 0 and gradually improves and gets stable as a and 3 increase, showing that CFLP is robust the hyperparameters a and B.
291
0.93
293
0.92
0.91
AUC
294
0.90
0.92
ATE with Different Treatments Tables 4 and 5 show the link prediction performance, ATE and ATFest of CFLP (with JKNet) when using differ- ent treatments. The treatments Tables 4 and are sorted by the Hits @ 20 performance. Bigger ATE indicates stronger causal relationship between the treatment and outcome, and vice versa. We observe: (1) ATEa values are generally close ATEots showing that CFLP was sufficiently trained to learn
0.89
0.91
296
1.5
1.0
298
beta
1.0 alpha
1.5
0.0
300
Figure 2: AUC performance of CFLP on CORA w.r.t different combanitions of a and B.
303
304
the causal relationship between graph structure information and link existence; (2) ATE and ATE
305
are both negatively correlated with the link prediction performance, showing that we can pick
306
proper treatment prior to training model with CFLP. Using the treatment that has the weakest causal relationship with link existence likely train the model to capture more essential factors on the outcome, in a way similar to denoising the unrelated information from the representations.
307
309
Related Work
310
Link Prediction
With its wide applications, link prediction has draw attention from many research communities including statistical machine learning and data mining. Stochastic generative methods based on stochastic block models (SBM) are developed generate links (Mehta et al., 2019). In data mining, matrix factorization (Menon and Elkan, 201 1), heuristic methods (Philip et al., 2010; Martínez
312
313
314
al., 2016), and graph embedding methods (Cui et al., 2018) have been applied to predict links the graph. Heuristic methods compute the similarity score of nodes based on their neighborhoods. These
'https://obb.starrt stanffosttoordd wwtp:eedddddeeeeeeeeeoeoeeeeeeee han.alo/ooo.ntrroo//gggbgb--

---

Table 4: Results of CFLP with different treat- ments on CORA. (sorted by Hits@ 20)
Table 5: Results of CFLP with different treat-
ments on CITESEER. (sorted by Hits @0)
Hits@
ATEobs
ATEest
Hits@ 20
ATEobs
ATH
K-core
65.6.11.1
0.002
0.013:10.003
SBM
71.6 11.9
0.004
0.005 10.001
SBM
64.2.11.1
0.006
0.023110.015
K-core
68.1
0.002
0.01011.0002
CommN
62.3:1.6
0.007
0.053=#0002
Ward
67.0
0.003
0.037=000009
PropC
1..7#1.4
0.037
0.059=0.065
PropC
64.6+3.6
0.141
0.232=+0.113
Ward
61.2:42.3
0.001
0.033=00012
Louvain
63.3+2.5
0.126
0.151
SpecC
59.3+42.8
0.002
0.033++0011
SpecC:
59.9++1.3
0.009
0.166++0.034
Louvain
57.6++1.8
0.025
0.138+00.91
Katz
57.3++0.5
0.245
0.224+000377
Katz
56.6++3.4
0.740
0.802+00041
CommN
56.8++4.9
0.678
0.195+00.03
316
methods can be generally categorized into first-order, second-order, and high-order heuristics based on the maximum distance of the neighbors. Graph embedding methods learn latent node features via embedding lookup and use them for link prediction (Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016; Wang et al., 2016).
317
318
319
320
In the past few years, GNNs have showed promising results on various graph-basee based tasks with their ability of learning from features and custom aggregations on structures, (Kipf and Welling, 2016a; Hamilton et al., 2017; Xu et al., 2018; Wu et al., 2020). With node pair representations and an attached be used for link prediction (Zhang al., 2020a). For example, VGAF used GCN to learn node representations and reconstruct the graph structure (Kipf and Welling, 201 SEAL extracted local subgraph around each target node pair and then learned graph representation from local subgraph for link prediction (Zhang and Chen, 2018). Following the scheme of SEAL, Cai and Ji (2020) proposed to improve local subgraph representation learning by multi-scale graph representation learning. And LGLP inverted the local subgraphs to line graphs before learning representations (Cai et al., 2021). However, very limited work has studied to use causal inference for improving link prediction.
322
323
MLP inner-product decoder, GNNs
324
325
328
327
328
329
330
331
a mean of learning the causality between treatment and outcome, counterfactual prediction has been used for variety of applicaitons such as recommender sys- tems (Wang et al., 2020; Xu et al., 2020), health care (Alaa and van der Schaar, 2017), vision-language tasks (Zhang et al., 2020b; Parvaneh et al., 2020), and decision making (Coston et al., 2020; Pitis et al., 2020; Kusner et al., 2017). To infer the causal relationships, previous work usually estimated the ITE via function fitting models (Gelman and Hill, 2006; Chipman et al., 2010; Wager and Athey, 2018; Assaad et al., 2021) l) which estimated the transductive ITE. Peysakhovich et al. (2019) and Zou et al. (0000) studied counterfactual prediction with multiple agents and bundled treatments, respectively. Pawlowski et al. (2020) proposed a deep structural causal model for tractable counterfactual inference.
Counterfactual Prediction
333
395
337
338
339
340
Causal Inference Causal inference methods usually re-weighted samples based on propensity score (Rosenbaum and Rubin, 1983; Austin, 2011; Kuang et al., 201 7a.b) to remove confounding bias from binary treatments. Recently, several works studied about learning treatment invariant representation to predict the counterfactual outcomes (Hassanpour and Greiner, 2019b,a; Shalit et al.,
342
343
344
2017; Yao et al., 2018; Bica et al., 2020; Hassanpour and Greiner, 201 9a; Li and Fu, 2017). When part of unobserved outcomes may mislead the counterfactual prediction, Louizos et al. (2017) attempted to infer the outcomes from proxies, and Hartford et al. (2017) introduced instrumental variable. SITE preserved local similarity to balance the distributions of control and treated groups (Yao et al., 2018).
345
346
347
348
Yoon et al. (2018) estimated ITE with generative adversarial networks (GANs). Assaad et al. (2021) discussed the trade-off between achieving balance and predictive power.
350
6
Conclusion
351
In this work, we presented counterfactual graph learning method for link prediction (CFLP). We introduced the idea of counterfactual prediction to improve link prediction on graphs. CFLP accurately predicted the missing links by exploring the causal relationship between global graph structure and link existence. Extensive experiments demonstrated that CFLP achieved the state-of- tre-art performance on benchmark datasets.
352
354

---

References
356
357
Ahmed Alaa and Mihaela Van Der Schaar. Validating causal inference models via influence functions. In International Conference on Machine Learning, pages 191-201. PMLR, 2019.
Ahmed M Alaa and Mihaela van der Schaar. Bayesian inference of individualized treatment effects using multi-task gaussian processes. Advances in Neural Information Processing Systems, 2017.
360
361
Serge Assaad, Shuxi Zeng, Chenyang Tao, Shounak Datta, Nikhil Mehta, Ricardo Henao, Fan Li, and Lawrence Carin Duke. Counterfactual representation learning with balancing weights. In International Conference on Artificial Intelligence and Statisties, pages 1972-1980. PMLR, 2021.
362
363
384
Peter C Austin. An introduction to propensity score methods for reducing the effects of confounding in observational studies. Multivariate behavioral research, 46(3):399 424, 2011.
365
366
Gary D Bader and Christopher WV Hogue. An automated method for finding molecular complexes in large protein interaction networks. BMC bioinformatics, 4(1):1-27, 2003.
367
368
James Bennett, Stan Lanning, al. The netflix prize. In Proceedings of KDD cup and workshop, volume 2007, page 35. Citeseer, 2007.
389
370
Ioana Bica, Ahmed M Alaa, James Jordon, and Mihaela van der Schaar. Estimating counterfactual treatment outcomes over time through adversarially balanced representations. arXiv preprint arXiv:2002.04083, 2020.
372
373 Vincent D Blondel, tean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008
375
P100:8,,,08, 2008.
376
Lei Cai and Shuiwang Ji. A multi-scale approach for graph link prediction. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 3308-332 3,8--335,2000 2020.
Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
379
380
Hugh Chipman, Edward George, Robert E McCulloch, et al. Bart: Bayesian additive regression trees. The Annals of Applied Statistics, 4(1):266-29) 298, 2010.
382
Amanda Coston, Edward H Kennedy, and Alexandra Chouldechova. Counterfactual predictions under runtime confounding. Advances in Neural Information Processing Systems, 2020.
385
384
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu, survey on network embedding. IEEE Transactions on Knowledge and Data Engineering. 31(5):833 852, 2018.
385
Andrew Gelman and Jennifer Hill. Data analysis using regression and multtlevel/hienarchicaal models. Cambridge university press, 2006.
386
387
388
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
389
390
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. arXiv preprint 1706v:1700.022
392
2017.
393
Jason Hartford, Greg Lewis, Kevin Leyton- Leyton-Brown, and Matt Taddy. Deep iv: A flexible approach for counterfactual prediction. In International Conference on Machine Learning, pages 1414-1423.
385
PMLR, 2017.
396
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference Machine Learning, pages 4116-4128 PMLR, 2020.
Negar Hassanpour and Russell Greiner. Counterfactual regression with importance sampling weights In IJCAL, pages 5880-5887, 2019a.
399
400
Negar Hassanpour and Russell Greiner. Learning disentangled representations for counterfactual regression. In International Conference on Learning Representations, 2019b.
10

---

402
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00653 2020.
403
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual inference. In International conference on machine learning, pages 3020- 3020-3029. PMLR, 2016.
406
407
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1)0016177, 2011.
408
409
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances in Neural Information Processing Systems, volume 31, 2018.
411
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint (o0.:v660900290000 2016a.
412
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1rX1v:1611.07300. 2016b.
414
415
Kun Kuang, Peng Cui, Bo Li, Meng Jiang, and Shiqiang Yang. Estimating treatment effect in the wild via differentiated confounder balancing. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 265-274, 2017a.
416
417
Kun Kuang, Peng Cui, Bo Li, Meng Jiang, Shiqiang Yang, and Fei Wang. Treatment effect estimation with data-driven variable decomposition. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017b.
419
421
Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairesss. Advances in Neural Information Processing Systems, 2017.
422
Sheng Li and Yun Fu. Matching on balanced nonlinear representations for treatment effects estimation. In Advances in Neural Information Processing Systems, 2017.
424
425
Christos Louizos, Uri Shalit, Joris Mooij, David Sontag, Richard Zemel, and Max Welling. Causal effect inference with deep latent-variable models. arXiv preprint arXiv:1705.0882) 2017.
426
427
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.34330 2009.
429
Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. A survey of link prediction in complex networks. ACM computing surveys (CSUR), 49(4):1-33, 2016.
430
Julian J McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems, volume 2012, pages 548-56, 2012.
432
433
Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai. Stochastic blockmodels meet graph neural networks. In International Conference on Machine Learning, pages 4466-4474. PMLR, 2019.
434
435
Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. In Joint european conference on machine learning and knowledge discovery in databases, pages 437-452. Springer, 2011.
437
438
Stephen L Morgan and Christopher Winship. Counterfactuals and causal inference. Cambridge University Press, 2015.
439
440
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14:849-856 856. 2001.
Chanyoung Park, Jiawei Han, and Hwanjo Yu. Deep multiplex graph infomax: Attentive multiplex network embedding using global information. Knowledge-Bald Systems, 197:105861, 2020.
443
444
Amin Parvaneh, Ehsan Abbasnejad, Damien Teney, Qinfeng Shi, and Anton van den Hengel. Counter- factal rision-and-language navigation: Unravelling the unseen. Advances Neural Information Processing Systems, 33, 2020.
445
11

---

447
Nick Pawlowski, Daniel C Castro, and Ben Glocker. Deep structural causal models for tractable counterfactual inference. Advances in Neural Information Processing Systems, 2020.
448
449
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
451
452
Alexander Peysakhovich, Christian Kroer, and Adam Lerer. prediction. Advances in Neural Information Processing Systems, 2019.
Robust multi-agent counterfactual
453
454
S Yu Philip, Jiawei Han, and Christos Faloutsos. Link mining: Models, algorithms, and applications. Springer, 2010.
456
Silviu Pitis, Elliot Creager, and Animesh Garg. Counterfactual data augmentation using locally factored dynamics. Advances in Neural Information Processing Systems, 2020.
457
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3):036106, 2007.
459
480
Paul R Rosenbaum and Donald B Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55, 1983.
481
462
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of educational Psychology, 66(5):688, 1974.
464
Donald B Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association, 100(469):322-33,, 2005.
465
Uri Shalit, Fredrik D Johansson, and David Sontag. Estimating individual treatment effect: gen- eralization bounds and algorithms. In International Conference on Machine Learning, pages 3076-3085. PMLR, 2017.
467
469
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE winter conference on applications of computer vision (WACV), pages 464-472. IEEE, 2017.
470
Zachary Stanfield, Mustafa Coskun, and Mehmet Koyutürk. Drug response prediction link prediction problem. Scientific reports. 7(1):1-13, 2017.
472
473
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pages 1067-1077, 2015.
474
475
Mark J van der Laan and Maya L Petersen. Causal effect models for realistic individualized treatment and intention to treat rules. The international journal of biostatistics, 3(1), 2007.
477
478
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
479
480
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2019.
Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 123652)) 2018
483
484
Daixin Wang, Peng Cui, and Wenwu 7hu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1225-1234, 2016.
485
Zifeng Wang, Xi Chen, Rui Wen, Shao-Lun Lun Huang, Ercan E Kuruoglu, and Yefeng Zheng. Informa- tion theoretic counterfactual learning from missing-not--tt-andoo feedback. Advances in Neural Information Processing Systems, 2020.
488
489
490
Joe H Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American statistical association, 58(301):236-24,, 1963.
12

---

492
Jeremy Weiss, Finn Kuusisto, Kendrick Boyd, Jie Liu, and David Page. Machine learning for treatment assignment: Improving individualized risk attribution. In AMIA Annual Symposium Proceedings, volume 2015, page 1306. American Medical Informatics Association, 2015.
493
David S Wishart, Yannick D Feunang, An C Guo, Elvis J Lo, Ana Marcu, Jason R Grant, Tanvir Sajed, Daniel Johnson, Carin Li, Zinat Sayeeda, et al. Drugbank 5.0: a major update to the drugbank 2018.
496
database for 2018. Nucleic acids research,
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Iransactions on neural networks and learning systems, 2020.
489
500
501
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Adversarial counterfactual learning and evaluation for recommender system. Advances in Neural Information Processing Systems, 2020.
502
503
504
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5453-5462. PMLR, 2018.
506
507
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48, PMLR, 2016.
509
Liuyi Yao, Sheng Li, Yaliang Li, Mengdi Huai, Jing Gao, and Aidong Zhang. Representation learning for treatment effect estimation from observational data. Advances in Neural Information Processing Systems, 31, 2018
510
511
512
Jinsung Yoon, James Jordon, and Mihaela Van Der Schaar. Ganite: Estimation of individualized treatment effects using generative adversarial nets. In International Conference Learning Representations, 2018.
514
515
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, 2018
517
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint 10Xiv:2010.16103, 2020a.
518
519
Zhu Zhang, Zhou Zhao, Zhijie Lin, Xiuqiang He, et al. Counterfactual contrastive learning for weakly- supervised vision- language grounding. Advances Neural Information Processing Systems, 33: 18123-18134, 2020b.
520
Hao Zou. Peng Cui, Bo Li, Zheyan Shen, Jianxin Ma, Hongxia Yang, and Yue He. Counterfactual prediction for bundle treatment, Advances in Neural Information Processing Systems, 33, 2020.
523
Checklist
524
525
1. For all authors...
526
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] the end of Section 3.2
529
(c) Did you discuss any potential negative societal impacts of your work? [No]
530
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
532
2. If you are including theoretical results...
533
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
534
(b) Did you include complete proofs of all theoretical results? [N/A]
535
3. If you ran experiments..
536
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
13

---

538
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Section 4.1 and Appendix
539
540
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] in Appendix
543
544
4. If you are using existing assets (c.g., code, data, models) or curating/relcusing new assets...
545
(a) your work uses existing assets, did you cite the creators? [Yes]
546
(b) Did you mention the license of the assets? [N/A]
547
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
548
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
549
550
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
553
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
554
555
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
558
14


Reviews:
[{"review_id": "YU96rCA99hh", "reviewer": "Reviewer_9Usb", "summary": "The authors propose a model for link prediction that takes into account the counterfactuals. The main idea is to learn an embedding of the nodes and then use that embedding to train a classifier model for link prediction. The key part is that the embedding is learned in such a way as to minimize the discrepancy between the factual and counterfactual distributions.\nExperiments of various commonly-used datasets show that the proposed method results in improved link prediction performance compared to state-of-the-art methods.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The proposed counterfactual learning framework is very similar to the work of Johansson et al., 2016, with the difference that the authors inserted a graph neural network with suitable. In my opinion, the innovative part of the work is considering various structural properties, such as belonging to the same community, as treatments.\n\nQuality: The submission is technically sound. The proposed method builds naturally on existing work, and the experimental results show a clear advantage over state-of-the-art-methods. I have a concern when it comes to interpreting mutual community membership as a treatment. This raises the question of whether an adversarial party could decide to encourage nodes in the graph to connect / disconnect in order to manipulate the network for a malicious end.\n\nClarity: The paper is well-organized. Readers familiar with causal inference concepts as well as readers proficient with graph-based methods should be able to follow the paper and reproduce the results.\n\nSignificance: I believe the proposed work could be built upon by other researchers interested in causal learning in graphs. I would be interested to see follow up work on other problems besides link prediction.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately address the limitations of the work. Please, see above for a potential societal impact to address.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "QfLY27FVUVM", "reviewer": "Reviewer_eUXt", "summary": "This paper introduces the idea of counterfactual prediction to improve link prediction on graphs and proposes a framework, counterfactual graph learning method for link prediction (CFLP). Specifically, the authors first introduce a method of generating counterfactual samples and then utilize these new data as well as original factual data to train the proposed model. The proposed method outperforms competitive baseline methods on several benchmark datasets in the link prediction task. The authors also provide sensitivity analysis and examine the impact of different treatments (i.e., results from different community detection algorithms) to link prediction results.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe idea of introducing counterfactual learning into link prediction is novel. The authors introduce a new method of link prediction that combines graph neural networks and counterfactual learning.\n\nQuality: \n\n- The theoretical background is not clear enough. The formulated problem in this paper is to estimate individual treatment effects (ITE). In causal inference, assumptions are required in order to make individual causal effects identifiable, e.g., consistency, no-hidden confounders, etc. The authors should clarify and discuss these assumptions.\n\n- The authors claim that employing counterfactual learning can help train the model to capture more essential factors on the outcome. They obtain results of ATE and link prediction based on different treatments (see Table 4 and 5). However, the results are a little confusing. It is unclear how this method captures essential factors. The authors are supposed to provide more results or explanations to support their claim.\n\nClarity:\n\n+ Overall, this paper is well organized. The technical part is mostly clear. \n\n- The problem proposed in the introduction is not fully supported by the experiments. Specifically, the authors claim that answering counterfactual questions can help capture essential factors to accurately predict missing links in the test data. There is no evidence to show how this works.\n\n- The authors propose an approximation for finding counterfactual links (Eq. 3). There are no experimental results to show that the approximation method produces results similar to those in Eq. 2. Will different counterfactual link generation methods affect the model's link prediction results?\n\n- The introduction of Balancing Counterfactual Learning is not very clear. The authors should introduce the formal definitions of PˆF_f and PˆCF_f in Eq. 10. \n\n- In Figure 2, the results show that beta (balancing counterfactual learning) does not have much influence on AUC performance. Meanwhile, as the authors mentioned, AUC is an easier metric than Hits@20. The sensitivity results on Hits@20 are missing.\nEq. 8 and 9 are unclear. The training is conducted only on the training data. The loss should not be calculated based on all links, e.g., for loop N nodes.\n\n- The link prediction results need more explanation (see Significance).\n\nSignificance: \n\n- In this work, the authors first generate counterfactual samples and then train the proposed method based on the new data and original data. The contribution of this work seems limited except involving the concept of counterfactual learning. In short, the authors seem to add more samples to train a model for improving the link prediction performance. \n\n- The link prediction results need more explanation. Why does counterfactual learning help link prediction? There is a jump from treatment effects learning to link prediction. Meanwhile, since baselines are trained on original data (without counterfactual data), is this comparison fair?\n\n- There are some related works that should be included. The following published work seems to have achieved better AUC results in link prediction than the proposed method in this paper on the Cora and Citeseer datasets.\n\n(1) Davidson, T.R., Falorsi, L., De Cao, N., Kipf, T. and Tomczak, J.M., 2018. Hyperspherical variational auto-encoders. arXiv preprint arXiv:1804.00891.\n\n(2) Yang, H., Pan, S., Zhang, P., Chen, L., Lian, D. and Zhang, C., 2018, November. Binarized attributed network embedding. In 2018 IEEE International Conference on Data Mining (ICDM) (pp. 1476-1481). IEEE.\n\nMinor issues:\n- It would be better to describe terms consistently, e.g., individualized treatment effect and individual treatment effect.    \n- It would be clearer to draw balancing counterfactual learning in Fig.1(b).\n- It would be helpful to explain the ratio of created CF samples for each dataset (i.e., how many samples satisfy Eq.3). This might help evaluate the performance of the proposed model.\n\nThanks to the authors for the response.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors point out that the proposed method has limitations in terms of computation efficiency and the formulation of treatment. The authors do not provide potential negative societal impacts of this work. To this end, I suggest the authors consider the unfairness problem that might exist in this proposed method. ", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "CUHx5vOAaDS", "reviewer": "Reviewer_fY1x", "summary": "The paper consider the task of counterfactually predicting edges in attributed graphs. I think this is a good effort (but incomplete) in a consequential and fast growing area. The paper needs to define the counterfactual task formally and prove their approach really does what the paper claim it does.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern with this work is the absence of a clear counterfactual model and a proof that the approach indeed does counterfactual inference according to the model. I am unable to evaluate the correctness of the approach without a precise theoretical definition of the task and a proof that the method indeed can produce a counterfactual query.\n\n+ Very important task. I am excited to see work in this space. I encourage the authors to continue improving their paper.\n\n- No structural causal model or even a causal DAG. This alone is grounds for rejection, since the reviewers cannot evaluate the correctness of the approach.\n\n-In graphs, variables are often dependent. What is the causal mechanism that allows us to say that the \"counterfactual link\" (va,vb) is really a natural experiment of (vi,vj)? That is, please describe in mathematical terms how clustering affects the structural causal model and mathematically prove it allows counterfactual inference. Then, please prove that the proposed form of counterfactual inference is the correct. Ideally, by showing error bounds.\n\n- In \"3.1: Treatment\": It is unclear how the treatment is related to the hidden and observed variables in the task. How are the clusters described in the structural causal model? \n\n- When talking about \"Counterfactual Links\", the paper still offers no structural causal model. \n\n- The missing related work (Bevilacqua et al. 2021) tackles graph classification under a counterfactually-driven data shift. That work shows the structural causal model and proves a bound that the representation is robust to the counterfactual shifts.\n\n- The embedding of (Hassani and Khasahmadi, 2020) is a structural node embedding used to predict node attributes or graph labels (not links). It makes sense to use a structural embedding for d(xi,xa) but the use of GCN with H_0 = X (after Equation (5)) is puzzling... with H_0 = X rather than the GCN one-hot encoding (used for link prediction in Kipf and Welling) gives structural node embeddings, which is not to be used for link prediction. \n\nBevilacqua, Beatrice, Yangze Zhou, and Bruno Ribeiro. \"Size-Invariant Graph Representations for Graph Classification Extrapolations.\" ICML (2021)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, the authors did not adequately addressed the limitations. The work talks about counterfactual link prediction but does not provide guarantees that its counterfactual estimator is correct.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ALYxFPhntE", "reviewer": "Reviewer_oDMj", "summary": "In this paper, the authors consider a link prediction problem utilizing the idea of causal inference.\nTo find the essential factors between nodes, they make counterfactual links using a matching-like algorithm for pairs of nodes. A GNN-based model is trained to learn representations so that the model can predict both the factual and counterfactual links. In training, first they jointly optimize the entire loss function including the counterfactual loss and the balancing loss, and then they fix the encoder and only train the decoder using the factual data. In the link prediction experiment, they use public popular datasets to validate the proposed method and evaluate in terms of some metrics such as AUC and HitRatio. They also analyze the proposal in terms of ATE and discover negative correlation between the performance and ATE.\nThe main contributions of this paper are as follows: 1) This is the first work that introduce the idea of causal inference into link prediction task. 2) They make counterfactual links and trained GNN-based methods to learn the causal relationship. 3) The proposed method outperforms the strong baselines.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well written and easy to follow.\nI find the idea to incorporate causal inference into link prediction is novel and interesting. I thought the hyper-parameter gamma, that defines the maximum distance of two nodes are similar is quite important value because that defines the counterfactual links but in the supplement, they showed CFLP is robust to the choice of gamma. That is one of the benefits of CFLP and it would be better to provide some analysis why CFLP is robust to gamma.\nIn the experiment, the authors explain that they sample the same number of disconnected pairs as the links when validation. However, this should be improved because the ratio of positive and negative links is totally balanced and does not match that of the entire dataset. It also would be better to evaluate the results in terms of Precision and Recall.  Though the evaluation can be improved, the experimental results are convincing. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They approximate Eq. 2 to make counterfactual links for the sake of fast computation, the effect of approximation should be provided because it requires the additional hyper-parameter gamma. \nIt would be better to provide theoretical analysis.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new approach to link prediction problem inspired by causal inference. The idea of "counterfactual link" is very interesting and the effectiveness of the proposed method, which is expected to work well intuitively, is also well supported experimentally.
However, discussion of its theoretical background is somewhat lacking. While we agree that the central interest of this paper is not to give a causal model on graphs, a theoretical discussion of the conditions and assumptions under which the proposed method behaves well would strengthen the argument of the paper.
This paper is a solid contribution, but considering the competitive rate of NeurIPS, we have no choice but to give up the acceptance of this paper with the quality to be accepted at other conferences.

Decision: Reject