Counterfactual Graph Learning for Link Prediction
Authors: Tong Zhao
Gang Liu
Daheng Wang
Wenhao Yu
Meng Jiang
Venue: ICLR 2022 Submitted (2022)
Keywords: Link Prediction
Graph Representation Learning
Graph Neural Networks.

Abstract: Learning to predict missing links is important for many graph-based applications. Existing methods were designed to learn the association between two sets of variables: (1) the observed graph structure (e.g., clustering effect) and (2) the existence of link between a pair of nodes. However, the causal relationship between these variables was ignored. We visit the possibility of learning it by asking a counterfactual question: “would the link exist or not if the observed graph structure became different?” To answer this question, we leverage causal models considering the information of the node pair (i.e., learned graph representations) 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 counterfactual inference. It creates counterfactual links from the observed ones, and learns representations from both the observed and counterfactual links. Experiments on benchmark datasets show that this novel graph learning method achieves state-of-the-art performance on link prediction.

Under review as a conference paper at ICLR 2022
COUNTERFACTUAL GRAPH LEARNING FOR LINK PREDICTION
Anonymous authors Paper under double-blind review
ABSTRACT
Learning to predict missing links is important for many graph-based applications. Existing methods were designed learn the association between two sets of vari- ables: (1) the observed graph structure (e.g.. clustering effect) and (2) the exis- tence of link between a pair of nodes. However, the causal relationship between these variables was ignored. We visit the possibility of learning it by asking a counterfactual question: "would the link exist or not if the observed graph struc- ture became different?" To answer this question, sidering the information of the node pair (i.e.. learned graph representations) as context, global graph structural properties as treatment, and link existence out- come. In this work, we propose novel link prediction method that enhances graph learning by counterfactual inference. It creates counterfactual links from the observed ones. and learns representations from both the observed and coun- terfactual links. Experiments on benchmark datasets show that this novel graph learning method achieves state-of-the-ar performance on link prediction.
leverage causal models con-
INTRODUCTION
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 appli- cations such as movie recommendation (Bennett et al. (007). chemical interaction prediction (Stan-) field et al. 2017), and knowledge graph completion (Kazemi & Poole 2018). Graph machine learn- ing methods have been widely applied to solve this problem. Their standard scheme is to first learn the representation vectors of nodes and then learn the association between the representations of pair of nodes and the existence of the link between them. For example, graph neural networks (GNNs) use neighborhood aggregation to create the representation vectors: the representation vec- tor of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes (Kipf & Welling 2016a Hamilton et al. 2017 Wu et al. 2020). Then the vec- tors are fed into binary classification model to learn the association. GNN methods have shown predominance in the task of link prediction (Kipf & Welling 2016b Zhang et al. 2020a).
Unfortunately, the causal relationship between graph structure and link existence was largely ignored in previous work. Existing methods that learn from association only-were are not able to capture essential factors to accurately predict missing links in the test data. Take social network as an 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 to 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 asking a counterfactual question: "would Alice and Adam still be close friends if they were not living in the same neighborhood?" If graph learning model could learn the causal relationship by answering the counterfactual questions, it would improve the accuracy 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?"
As known to many, counterfactual question is 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 & Petersen 2007] Dohansson et al., 2016). (To simplify the language, we use "treatment" to refer to the manipulation in this paper, as readers might be familiar more with the word "treatment.")

---

Notations Let = (V,E) be an undirected graph of N nodes, where V/ = {ur, U2. u is the set of nodes and & C V y is the set of observed links. We denote the adjacency matrix as Under review as a conference paper at ICLR 2022
Auder
Factual treatment:
Factual link:
Same neighborhood
Adam
Decoder
GNN Encoder
Alice
Shared
Helle
Decoder
(Alica, Adam) Most similar with (Helon, Bob)
different treatment
Counterfactual treatment:
Different neighborhoods
Counterfactual link:
Factual link:
Counterfactual link:
(a) Find counterfactual link as the most sim- ilar node pair with different treatment.
(b) Train GNN-based link predictor to predict factual and counterfactual links given the corresponding trcatments.
The proposed CFLP learns the causal relationship between the observed graph structure (e.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 (ITE) as 1 - = 0 so it looks for factors other than neighborhood to predict the factual link.
Figure 1:
Given certain data context, it asks what the outcome would have been if the treatment had not been the observed value. the scenario of link prediction, we consider the information of pair of nodes as context, graph structural properties as treatment, and link existence as outcome. Recall the social network example. The context is the representations of Alice and Adam that are learned from their personal attributes and relationships with others the network. The treatment is living in the same neighborhood, which can be identified by community detection. And the outcome is their friendship. In this work, we present counterfactual graph learning method for link prediction (CFLP) that trains graph learning models to answer the counterfactual questions. Figure illustrates this two- step method. Suppose the treatment variable is defined as one type of global graph structure, e.g., the neighborhood assignment discovered by spectral clustering or community detection algorithms. We are wondering how likely the neighborhood distribution makes a difference on the link (non- Jexistence for each pair of nodes. So, given pair of nodes (like Alice and Adam) and the treatment value on this pair (in the same neighborhood), we find pair of nodes (like Helen and Bob) that satisfies two conditions: (I) it has a different treatment (in different neighborhoods) and (2) it the most similar pair with the given pair of nodes. We call these matched pair of nodes "counterfactual links." " Note that the outcome of the counterfactual link can be either or O, depending on whether there exists edge between the matched pair of nodes (Helen and Bob). The counterfactual link provides unobserved outcome to the given pair of nodes (Alice and Adam) under a counterfactual condition (in different neighborhoods). After counterfactual links created for all (positive and negative) training examples, CFLP trains a link predictor (which can be GNN-based) to learn the representation vectors of nodes to predict both the observed factual links and the counterfactual links. In this Alice-Adam example, the link predictor is trained to estimate the individual treatment effect (TTE) of neighborhood assignment as on the outcome and zero indicates the given treatment has no effect on the outcome. So, the learner will try to discover the essential factors on the friendship between Alice and Adam. CFLP leverages causal models to find these factors for graph learning models to accurately predict missing links.
0, where ITE a metric for the effect of treatment
Contributions. Our main contributions can be summarized as follows. (1) This is the first work that proposes to improve link prediction by causal inference, specifically, learning to answer counter- factual questions about link existence.
(2) This work introduces CFLP that trains GNN-based link predictors to predict both factual and counterfactual links. It learns the causal relationship between global graph structure and link existence. (3) CFLP outperforms competitive baseline methods on several benchmark datasets. We analyze the impact of counterfactual links as well the choice of treatment variable. This work sheds insights 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.
2 PROBLEM DEFINITION
2

---

Under review as a conference paper at ICLR 2022
A [0,1) where Ar, indicates nodes i and by are connected and vice versa. We denote the node feature matrix X E RN where F is the number of node features and x, (bolded) indicates the feature vector of node v/ (the i-th row of X).
In this work, we follow the commonly accepted problem definition of link prediction on graph data (Zhang & Chen 2018| Zhang et al. 2020a Cai et al. 202T): Given an observed graph (with validation and testing links masked off), predict the link existence between every pair of nodes. More specifically, for the GNN-based link prediction methods, they learn low-dimensional node representations Z E RNNH where H is the dimensional size of latent space such that H < F, and then use Z for the prediction of link existence.
PROPOSED METHOD
3.1 IMPROVING GRAPH LEARNING WITH CAUSAL MODEL
Z
Leveraging Causal Model(s) Counterfactual causal infer- ence aims to find out the causal relationship between treat- ment and outcomes by asking the counterfactual questions such "would the outcome be different the treatment was different?" (Morgan & Winship 2015). Figure 2 is typ- ical example, in which we denote the context (confounder) as Z, treatment as T, and the outcome as Y. Given the context, treatments, and their corresponding outcomes, coun- terfactual inference methods aim to find the effect of treat- ment on the outcome, which is usually measured by individ- ual treatment effect (ITE) and its expectation averaged treat- ment effect (ATE) (van der Laan & Petersen 2007| Weiss et al.] 2015). For binary treatment variable T {0, 1,, denoting glz.1 T' as the outcome of z given the treatment T. we have (TE(z) - g(z. 1) g(z, 0), and ATE Ez-z ITE
T
Treatment Effect
Estimation
Figure 2: Causal modeling (not the target of our work but related to the idea we propose): Given Z and ob- served outcomes, find treatment ef- feet of 'T on Y.
? Z
Graph Representation Learning
Y
Ideally, we need all possible outcomes of the contexts under all kinds of treatments study the causal relationships (Mor- gan & Winshipp 2015). However, in reality, the fact that we can only observe one potential outcome under one partieu- lar treatment prevents the ITE from being known (Johansson) et al. (0166). Traditional causal inference methods use statisti- cal learning approaches such as Neyman-Rubin casual model (BCM) and propensity score matching (PSM) to predict the value of ATE (Rubin) 1974 2005).
Graph learning with causal model (the proposed idea): leverage the estimated ATE(Y|T) to improve the learning of Z.
Figure 3:
In this work, we look at link prediction with graph learning, which is essentially learning the best node representations Z for the prediction of link existence. Therefore, as shown in Figure 3, where the outcome Y is the link existence, the objective is different from classic causal inference. In graph learning, we can estimate the effect of treatment on the outcome (ATE(Y(T)), and we want to improve the learning of Z with the estimation. More specifically, in graph learning for link prediction, for each pair of nodes (i,, M2). its ITE can be estimated with
ITE (e..s) = 9((,, 2,), 1) g((2,, 2) and we use this information to improve the learning of Z, i.e., P(Z|Y).
We denote the observed adjacency matrix as the factual outcomes A and the unobserved adja- cency matrix when the treatment is different as the counterfactual outcomes A CCF, f We denote T 10,1 xN as the binary factual treatment matrix, where Th, indicates the treatment of the node pair (1,, n,). We denote TCF as the counterfactual treatment matrix where TCF = --TT,
We are interested in (1) estimating the counterfactual outcomes A CF via observed data, (2) learn- ing with the counterfactual adjacency matrix A CF enhance link prediction, and (3) learning the causal relationship between graph structural information (treatment) and link existence (outcome).
Treatment Variable Previous work on 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 representa- tion vectors of nodes learned by GNNs. This is because the message passing-based GNNs aggregate
3

---

Under review as a conference paper at ICLR 2022
local information in the algorithm of representation vector generation and the global structural in- formation 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 et al. 2008), an unsupervised approach that has been widely example. Louvain discovers community structure of graph
used for community detection, and assigns each node to one community. Then we can define the binary treatment variable as whether these two nodes in the pair belong to the same community. Let V N be any graph mining/clustering method that outputs the index of communixyylusseereigghhoooo belongs to. The treatment matrix T is defined as Ti = 1 if c(t;) c(v;). and Ti, otherwise. For the choice of c, we suggest methods that group nodes based on global graph structural informa- tion, including but not limited to Louvain (Blondel et al. 2008), K-core (Bader & Hogue 2003). and spectral clustering (Ng et al. 200T).
that each node
3.2 COUNTERFACTUAL LINKS
To implement the solution based on above idea, we propose counterfactual links. As aforemen- tioned. for each node pair, the observed data contains only the factual treatment and outcome, mean- ing that the link existence for the given node pair with an opposite treatment unknown. Therefore, we use the outcome from the nearest observed context as substitute. This type of matching on co- variates is widely used estimate treatment effects from observational data (Johansson et al. [016]] Alaa & 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 's outcome as a counterfactual link. Formally, v(U,, Uz) V x V, we want to find its counterfactual link (Va, Ub) as below:
(Vay 26) = arg min (h((1), U2); (Va, 26)) Ta,b = 1 )
where l((..)) is a metric of measuring the distance between a pair of node pairs (a pair of contexts). Nevertheless, finding the nearest neighbors by computing the distance between all pairs of node pairs is extremely inefficient and infeasible in application, which takes O(N*) comparisons (as there are totally ON22) node pairs). Hence we implement Eq. (2) using node-level embeddings. Specifically, considering that we want to find the nearest node pair based on not only the raw node features but also structural features,
take the state-of-the-ar unsupervised graph representation learning method MVGRL (Hassani & Khasahmadi 2020) to learn the node embeddings X E R. from the observed graph (with validation and testing links masked off). We use X to find the nearest neighbors of node pairs. Therefore, V(c,, 0;) E V x V. we define its counterfactual link (vas vb) as (Va: 1%) arg min (d(x,, xx) + d(fx,, xx)) Top6
Ti.j, d(x,, xx) + d(xx, xt)) < 2y), (3)
VVV
where d(., .) is specified as the Euclidean distance on the embedding space of X, and is hyperpa- rameter that defines the maximum distance that two nodes are considered as similar. When no node pair satisfies the above equation (i.e., there does not exist any node pair with opposite treatment that is close enough to the target node pair), we do not assign any nearest neighbor for the given node pair to ensure all the neighbors are similar enough (as substitutes) in the feature space. Thus, the counterfactual treatment matrix TCF and the counterfactual adjacency matrix A CF are defined as
1- 1 Au, 3 (va, vb) E V x V satisfies Eq. otherwise.
TC A
(4)
Aij
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. We also note that X must be structural embeddings rather than positional embeddings (as defined in (Srinivasan & Ribeiro (020)).
Learning from Counterfactual Distributions Let pf be the factual distribution of the observed contexts and treatments, and pCf be the counterfactual distribution that is composed of the observed contexts and opposite treatments. We define the empirical factual distribution pr PF as pF {(1,, By, -- and define the empirical counterfactual distribution PCF PCF as PCF {(V,, By, T;, IN )i Unlike traditional link prediction methods that take only pr 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 pCr as a complementary input and use the counterfactual outcomes A CF as the training target for the counterfactual data samples.
4

---

Under review as a conference paper at ICLR 2022
3.3 THE COUNTERFACTUAL GRAPH LEARNING MODEL
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 output contains link prediction logits in A and A CF for the factual and counterfactual adjacency matrices and A CF, respectively.
Graph Learning Model The model consist of two trainable components: graph encoder f and a 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 choice of the graph encoder f can be any end-to-end GNN model. Without the loss of generality, here we use the commonly used graph convolutional network (GCN) (Kipf & Welling 201 Each layer of GCN is defined as
(5) where / is the layer index, A A + is is the adjacency matrix with added self-loops, D is the diagonal degree matrix D. E; A.,. ()) = X. w is the learnable weight matrix at the I-th layer, and (-) denotes a nonlinear activation such as ReI.U. We denote Z = f(A, E Nx as the output from the encoder's 's last layer, i.c.. the H-dimensional representation vectors of nodes. Following previous work (Zhang et al.J (020a), we compute the representation of node pair as the Hadamard product of the vectors of the nodes. That is, the representation for the node pair (v,, U2) is z; O 2j E HR where @ stands for the Hadamard product.
H (A, H 1),,, w oD AD H (((")((()
For the link decoder that predicts whether a link exists between pair of nodes, opt for simplicity and adopt a simple decoder based on multi-layer perceptron (MLP), given the representations of node pairs and their treatments. That is, the decoder g is defined as
À g [Z. T), where A MLP(((z zj. Tigl), A CF = g(Z, TOF), where A. MLP([Z, C zjz 1.
(6)
(7)
where [ stands for the concatenation of vectors, and À and C can be used for estimating the observed ITE as aforemennioned in Eq.
During the training process, data samples from the empirical factual distribution pr and the em- pirical counterfactual distribution pcr are fed into decoder and optimized towards A and ACP respectively. That is, for the two distributions, the loss functions are as follows:
1 N2
LF
As.j log An,s + (1- 101-Aya Aij) log(1 - Aiz))
(8)
i=
j=
LCF N2
ACF log ACP + +11 log(1 10---9 -A
Balancing Counterfactual Learning In the training process, the above loss minimizations train the model on both the empirical factual distribution pr pf and empirical counterfactual dis- tribution pcr pCF that are not necessarily equal - the training examples (node pairs) do not have to be aligned. However, at the stage of inference, the test data contains only observed (factual) samples. Such gap between the training and testing data distributions exposes the model in the risk of covariant shift, which is common issue in counterfactual learning (Johansson et al.) 2016 Assaad et al. 2021).
To force the distributions of representations of factual distributions and counterfactual distributions to be similar, we use the discrepancy distance (Mansour et al. 2009: Johansson et al., 2016) as another objective to regularize the representation learning. That is, to minimize the distance between the learned representations from PF and PCF;
the following loss term
Laise disc( (Df. PCF), where disc(P, (P,Q) = ||P Qll,
(10)
5

---

Under review as a conference paper at ICLR 2022
where ||- IIF denotes the Frobenius Norm, and Pf and pf denote the node pair representations learned by graph encoder I from factual distribution and counterfactual distribution, respectively. That is, the learned representations for (v,, Eg, Tag) and Uy, " are [ze C Zz. Tugl (Eq. (6 (Eq. respectively.
and [2, C z,: T
Training During the training of CFLP, want the model to be optimized towards three targets:
(I) accurate link prediction on the observed outcomes (Eq. (8) ). (2) accurate estimation on the coun-
terfactual outcomes (Eq. (9)) ) and (3) regularization on the representation spaces learned from pr
and PCF (Eq. (10). Therefore, the overall training loss of our proposed CFLP
L = CF a LCF + B- Ldisc:
(11)
where and | are hyperparameters control the weights of counterfactual outcome estimation (link prediction) loss and discrepancy loss.
Summary Algorithm| 1 summarizes the whole process of CFLP. The first step is to compute the factual and counterfactual treatments T, TCF as well as the counterfactual outcomes A CF, Then, the second step trains the graph learning model on both the ob- served factual data and created coun-
Algorithm 1: CFLP: Counterfactual graph learning for link prediction
Input f. 9, A, X, n. n_epochs, n__epoh__ft
Compute T as presented in Section 3.1
Compute TCF AF by Eqs. and
/* model training Initialize 6 in f and Q in
4 for epoch in cange(n_epochil do
terfactual data with the integrated loss
Z = (A,
function (Eq, IT).. Note that the dis- crepancy loss (Eq. (TO)) is computed on the representations of node pairs learned by the graph encoder f. the decoder g is trained with data from both PP and PCF without balancing the constraints. Therefore, after the model is sufficiently trained, we freeze the graph encoder I and fine-tune y with only the factual data. Finally, after the decoder sufficiently fine- tuned, we output the link prediction logits for both the factual and counter- factual adjacency matrices.
Get A and A CF via with Eqs.
(6) and 77
Update O and Og with L;
Eq.
end
/* decoder fine-turing
Freeze O, and re-initialize Og:
10 Z = f),
11 for epoch in range(n.epochs.ft do
12
Get via g with Eq. (6)
Update 0g with LF;
// Eq.
end
/ model inferencing inference Z = f(A,
16 Get and A CF via with Eqs. 6 and Output: Á for link prediction, A CF
Complexity The complexity of the first step (finding counterfactual links with nearest neighbors) is proportional to the number of node pairs. When 7 set as a small value to obtain indeed similar node pairs, this step (Eq. (3) uses con- stant time. Moreover, the computation in Eq. B can be parallelized. Therefore, the time complexity O(N2/C) where C is the number processes. For the complexity of the second step (training counterfactual learning model), the GNN encoder has time complexity of O N + (HHE)) (Wul et 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 that of observed links during training, the complexity of a three-layer MLP decoder is O(((H + 1) dr + da 1)( = O(d, (H + 2) El), where dn is the number of neurons in the hidden layer. Therefore, the second step has linear time complexity w.r.t the sum of node and edge counts.
Limitations First, as 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 quite few kinds of graph structural information that can be considered as treatments. Future work can leverage the rich structural information by bundled treat- ments (ouu et al. 2020) in counterfactual graph learning.

---

Under review as a conference paper at ICLR 2022
Table 1: Link prediction performances measured by @its@20. Best performance and best baseline performance are marked with bold and underline, respectively.
CoRA
CITESBER
PUBMED
FACEBOOK
OGB-DDI
Node2Vec 49.96.12.51
47.78.1..72
39.19111.02
24.24.13.02
23.26.12.09
MVGRL
19.53+2.64
14.07=0.79
14.19:00.85
14.43+0033
10.02+1.001
VGAE
43.91+3.38
44.04+4.86
23.73+11.11
37.01=0.63
11.71
SEAL
51.35+2.26
40.90=+3,68
28.45:+..81
40.89=5,70
30.56#3.86
LGLP
02.98
57.4343.77
37.86:42.13
GCN
1..06
1..56++1.22
21.84:43.87
53.89++2.14
37.07+:5.07
GSAGE
53.54442.96
53.674+2.94
39.13++4.44
45.51+:3.22
53.90
JKNet
38.2113.86
55.6012.117
25.6441.111
52.25+1148
60.5618.69
Our proposed CFLP
with different graph encoders
CFLP w/ GCN
60.34++2.33
59.45+2.30
34.1242.72
53.95+2.229
52.51+ 1.09
CFLP w/ GSAGE
57.33:11.73
53.0512.007
43.07:12.36
47.2813.00
75.49
CFLP w/ JKNet
65.57
68.0911.499
44.9011.000
55.22.11.29
86.08 1.98
4 EXPERIMENTS
4.1 EXPERIMENTAL SETUP
We conduct experiments on five benchmark datasets including citation networks (CORA, CITE- SEER, PUBMED (Yang et al. 20166), social network (FACEBOOK (McAuley & Leskovee 2012 and drug-drug interaction network (OGB-DDI (Wishart et al. 2018)) from the Open Graph Bench- mark (OGB) (Hu al. 2020 For the first four datasets, 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/ hatn/validation/esst splits. Statistics and details for the datasets are given in Appendix. We use K-core (Bader & Hogue, 2003) clusters as the default treatment variable. We evaluate CFLP on three commonly used GNN encoders: GCN (Kipf & Welling) 2016a), GSAGE (Hamilton et al.) 2017). and JKNet (Xu et al. 2018). We compare the link prediction performance of CFLP against Node2 (Grover & Leskoved 2016), MVGRL (Hassani & Khasahmadi] 2020), VGAE (Kipf & Welling 2016b), SEAL (Zhagg& & Chen 2018). LGLP (Cai et al. 2021). and GNNs with MLP de- coder. 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.
challenging
Besides performance comparison link prediction, will answer two questions suggest way of choosing a treatment variable for creating counterfactual links: (Q1) Does CFLP 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 Q1 is yes, then the answer Q2 will indicate how to choose treatment based on observed ATE. To answer the Q1, we calculate the observed ATE (ATE by comparing the observed links in A and created counterfactual links C that have opposite treatments. And we calculate the estimated ATE (ATE by comparing the predicted links in A and predicted counterfactual links A Formally, ATE,he and ATE,st are defined as
N
N (A-) (1NXN - TA -A)
ATE
1
ΣΣ
(12)
N2
==
N
N
ATE.st
ΣV ==
(A
A-F) (1NNN CA Albes
(13)
Nº
The treatment variables will investigate are usually graph clustering community detection methods, such as K-core (Bader & Hogue 2003), stochastic block model (SBM) (Karrer & New- man 2011) 1). spectral clustering (SpecC) (Ng et al. 2001), propagation clustering (PropC) (Raghavan et al. 2007). Louvain (Blondel et al. 2008), common neighbors (CommN), Katz index, and hierar- chical clustering (Ward) (Ward Jr 1963). We JKNet (Xu et al. 2018) default graph encoder.

---

Under review as a conference paper at ICLR 2022
Table 2: Link prediction performances measured by AUC. Best performance and best baseline per- formance are marked with bold and underline, respectively.
CoRA
CITESBER
PUBMED
FACEBOOK
OGB-DDI
Node2Vec 84.49110.49
80.00110.68
80.32:10.29
86.49.14.22
90.83.10.02
MVGRL
75.07=3.63
61.20+0.55
80.78+1.228
79.83+0.30
0194
VGAE
88.68=0.40
85.35+0.60
95.80++0.13
98 98.66=0.044
93.08+0.1 15
SEAL
02.55=0.50
85,82+00,44
96.36:0.28
99.60=0.02
97.85=0.17
LGLP
91.30-10.00
89.41+10.13
98.51110.01
GCN
90.25++0.53
1..47
96.33++0.80
99.43
99.82++0.05
GSAGE
90.24410.34
17.3
96.78++0.11
99. 09.29
99.93-+0.02
JKNet
89.05=0.667
1.758
96.58-10.23
99.43:1002
99.94-10.01
Our proposed CFLP with different graph encoders
CFLP w/ GCN
92.55++0.50
39.65++0.20
96.99-+0.08
99.08+0001
99.44+H0.05
CFLP w/ GSAGE
92.61
91.84.10.20
97.01100.01
99.3410.10
99.83
CFLP w/ JKNet 93.05.10.24
92.12:10.47
97.5311.117
99.3111004
99.9410.01
Table 3: Results of CFLP with different treat-
Table 4: Results of CFLP with different treat-
ments on CORA. (sorted by Hits@20 20)
ments on CITESEER. (sorted by Hits @2)
Hits 20
ATEass
ATE,st
Hits 20
ATE
ATE.
K-core
6..6
0.002
0.013++0.003
SBM
71.6 1.9
0.004
0.005 +.0001
SBM
6.12+111
0.006
0.023+00015
K-core
68.1+1..
0.002
0.010+000022
CommN
62.3++1.6
0.007
0.053+00.021
Ward
6.7
0.003
0.037++0.009
PropC
61.7:11.4
0.037
0.05910.065
PropC
64.6113.6
0.141
0.2321101113
Ward
61.2:1:2.3
0.001
0.033110.02
Louvain
63.3:2..5
0.126
0.15110.078
SpecC
59.3:12.8
0.002
0.033-10.011
SpecC
59.9111.3
0.009
0.166:10.034
Louvain
57.6+1188
0.025
0. 0.138=#0.91
Katz
57.3++0.
0.245
0.224+00037
Katz
56.6#3..4
0.740
0.802+00041
CommN
56.8+4.99
0.678
0.195+000034
Implementation details and supplementary experimental results (e.g., sensitivity on y, ablation study on LCF and Ldise) can be found in Appendix. Source code is available in supplementary material.
4.2 EXPERIMENTAL RESULTS
Link Prediction Tables and 2 show the link prediction performance of Hits@20 and AUC by all methods. LGLP on PUBMED and DGB-DDI are missing due to the out of memory сπоо when 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 close-to-perfect AUC. As AUC is a relatively easier met- ric comparing with Hits @ 20, most methods achieved good performance CFLP with JKNet almost consistently achieves the best performance and outperforms baselines sig- nificantly on Hits @ 20. Specifically, comparing with the best baseline, CFLP improves relatively by 16.4% and 0.8% on Hits 20 and AUC, respectively. Comparing with the best performing baselines, which are also GNN-based CFLP benefits from learning with both observed link existence (A) and our defined counterfactual links (A CFF.
AUC. We observe that
ATE with Different Treatments Tables and show the link prediction performance, ATE and ATEsst of CFLP (with JKNet) when using different treatments. The treatments in Tables are sorted by the Hits fitss220 20 performance. Bigger ATE indicates stronger causal relationship between the treatment and outcome, and vice versa. We observe: (1) the rankings of ATE, and ATE, are positively correlated with Kendell's ranking coefficient (Abdil 2007) of 0.67 and 0.57 for CORA and CITESEER, respectively. Hence, CFLP was sufficiently trained to learn the causal relationship
between graph structure information and link existence; (2) ATE, and ATÉ,st are both negatively correlated with the link prediction performance, showing that we can pick a proper treatment prior to training model with CFLP. Using the treatment that has the weakest causal relationship with link existence is likely to train the model to capture more essential factors on the outcome, in way similar denoising the unrelated information from the representations.
8

---

Under review as a conference paper at ICLR 2022
5 RELATED WORK
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 to generate links (Mehta et al.) 2011)). In data mining, matrix factorization (Menon & Elkan 2011). )), heuristic methods (Philip al. 2010 Martinez ct al. 2016), and graph embedding methods (Cui et al., 2018) have been applied to predict links in the graph. Heuristic methods compute the similarity score of nodes based on their neighborhoods. These methods can be generally categorized into first-order, second-orde 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& & Leskoved [016 Wang et al., 2016).
Link Prediction
In the past few years, GNNs have showed promising results various graph-based tasks with their ability of learning from features and custom aggregations on structures (Kipf & Welling 2016a Hamilton et al.) 2017; Wu et al., 2020)(Cotta
al., 202T). With node pair representations and an attached MLP or inner-product decoder, GNNs can be used for link prediction (Zhang et al. 2020aa Davidson et al., 2018 Yang et al. 2018). For example, VGAE used GCN to learn node representations and reconstruct the graph structure (Kipf & Welling 201 SEAL extracted a local subgraph around each target node pair and then learned graph representation from local subgraph for link prediction (Zhang & Chen 2018). Following the scheme of SEAL, Cai & 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., 202T)
However, very limited work has studied to use causal inference for improving link prediction.
Counterfactual Prediction As a mean of learning the causality between treatment and outcome, counterfactual prediction has been used for a variety of applications such as recommender sys- tems (Wang et al., 2020 Xu et al.) 2020), health care (Alaa & van der Schaar 2017 Pawlowski et al. 2020), vision-
tasks
Zhang et al., |020b; Parvaneh et al. (020). and decision mak- 2020 | Kusner et al. 2017). To infer the causal relationships,
ing (Coston et al., 2020; Pitis et al.
previous work usually estimated the ITE via function fitting models (Gelman & Hill, 2006 Chipman
ct al. 2010 Wager& & Athey 2018: Assaad et al. 202T). Peysakhovich et al. (2019) and Zou et al.
(2020) studied counterfactual prediction with multiple agents and bundled treatments, respectively.
Causal Inference Causal inference methods usually re- re-weighted samples based on propensity
score (Rosenbaum & Rubin 1983 Austin 2011) to remove confounding bias from binary treat- ments. Recently, several works studied about learning treatment invariant representation to predict
the counterfactual outcomes (Shalit et al., 2017 Li& & Fu, 2017. Yao et al. 2018 Yoon et al. 2018
Hassanpour& & Greiner 2019a bj Bica et al. 2020). Few recent works combined causal inference
with graph learning (Sherman & Shpitser 2020; Bevilacqua et al. 2021 Lin et al. 202T Feng et al.
2021 For example. [Sherman & Shpitser (2020) proposed new concept in causal modeling, called
example,/Serrman
"network intervention", to study the effect of link creation on network structure changes. [Bevilac- qua et al.) (2021) studied the task of out-of-distribution (OOD) graph classification, and showed how subgraph densities can be used to build size-invariant graph representations, which alleviates the train-test gap when learning from OOD data.
CONCLUSION AND FUTURE WORK
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 accu- rately 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-the-art per- formance on benchmark datasets. This work sheds insights that good use of causal models (even basic ones) can greatly improve the performance of (graph) machine learming tasks, which in our case is link prediction. We note that the use of more sophistically designed causal models may lead to larger improvements for other machine learning tasks, which could be a valuable future research direction for the community. Other than our use of global graph structure as treatment, other treat- ments choices (with both empirical and theoretical analyses) are also worth exploring. Moreover, as CFLP first generates counterfactual links and then learns from both observed and counterfactual link existence, the underlying philosophy of our methodology could be considered as graph data augmentation. Therefore, investigating the relationship between counterfactual graph learning and graph data augmentation is also a possible future research direction.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Hervé Abdi. The kendall rank correlation coefficient. Encyclopedia of Measurement and Statistics.
Sage, Thousand Oaks, CA, pp. 508-5108-0 510, 2007.
Ahmed Alaa and Mihaela Van Der Schaar. Validating causal inference models via influence func-
tions. In International Conference on Machine Learning, pp. 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.
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 Statistics, pp. 1972-1980. PMLR, 2021.
Peter C Austin. An introduction propensity score methods for reducing the effects of confounding in observational studies. Multivariate behavioral research, 46(3):399-424, 2011.
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.
James Bennett, Stan Lanning, al. The netflix prize. In Proceedings of KDD cup and workshop, volume 2007, pp. 35. Citeseer, 2007.
Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classification extrapolations. arXiv preprint arXiv:2103.05045, 2021.
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.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10):P00008, 2008.
Lei Cai and Shuiwang Ji. A multi-scale approach for graph link prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3308-3313 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.
Hugh A Chipman, Edward I George, Robert E McCulloch, et al. Bart: Bayesian additive regression trees. The Annals of Applied Statistics, 4(1):266-29) 298, 2010.
Amanda Coston, Edward H Kennedy, and Alexandra Chouldechova. Counterfactual predictions under runtime confounding. Advances in Neural Information Processing Systems, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre-
sentations. Advances in Neural Information Processing Systems, 34, 2021.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE Transac- fions Knowledge and Data Engineering, 31(5):833-852, 2018.
Tim R Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub Tomezak. Hyperspheri- cal variational auto-encoders. arXiv preprint arXiv: /0X.v::800..000 00891, 2018.
Fuli Feng, Weiran Huang, Xiangnan He, Xin Xin, Qifan Wang, and Tat-Seng Chua. Should graph convolution trust neighbors? a simple causal inference method. In Proceedings of the 44th In- ternational ACM SIGIR Conference on Research and Development in Information Retrieval, pp- 1208-1218 2021.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
arXiv preprint arXiv: arX 02428, 2019.
10

---

Under review as a conference paper at ICLR 2022
Thorben Funke and Till Becker. Stochastic block models: A comparison of variants and inference methods. PloS one, 14(4), 2019.
Andrew Gelman and Jennifer Hill. Data analysis using regression and multileve//hierarchiicd mod- els. Cambridge university press, 2006.
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, pp. 855 864, 2016.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint urXiv:/706.0223 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pp. 4116-4126. PMLR, 2020.
Negar Hassanpour and Russell Greiner. Counterfactual regression with importance sampling weights. In IJCAI, pp. 5880-5887, 2019a.
Negar Hassanpour and Russell Greiner. Learning disentangled representations for counterfactual regression. In International Conference on Learning Representations, 2019b.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00632 2020.
Fredrik Johansson, Uri Shalit, and David Sontag. Learning representations for counterfactual infer- ence. In International conference on machine learning, pp. 3020-3029. PMLR, 2016.
Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure networks. Physical review E, 83(1):016177, 2011.
Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances in Neural Information Processing Systems, volume 31, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: wetp:0100900999 2016a.
Thomas N Kipf and Max Welling. arXiv:1611003008, 2016b.
Variational graph auto-encoders. arXiv preprint
Matt J Kusner, Joshua R Loftus, Chris Russell, and Ricardo Silva. Counterfactual fairness. Advances in Neural Information Processing Systems, 2017.
Sheng Li and Yun Fu, Matching on balanced nonlinear representations for treatment effects estima- tion. In Advances in Neural Information Processing Systems, 2017.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. PMLR, 2021.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.34300 2009.
Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. A survey of link prediction in complex networks. ACM computing surveys (CSUR), 4934):1-33, 2016.
Julian J McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Advances in Neural Information Processing Systems, volume 2012, pp. 548-56, 2012.
Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai. Stochastie blockmodels meet graph neural networks. In International Conference on Machine Learning, pp. 1466-4474. PMLR, 2019.
Aditya Krishna Menon and Charles Elkan. Link prediction via matrix factorization. In Joint ropean conference on machine learning and knowledge discovery databases, pp. 437-452. Springer, 2011.
11

---

Under review as a conference paper at ICLR 2022
Stephen L Morgan and Christopher Winship. Counterfactuals and causal inference. Cambridge University Press, 2015.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm.
Advances in neural information processing systems, 14:849 856, 2001.
Chanyoung Park, Jiawei Han, and Hwanjo Yu. Deep multiplex graph infomax: Attentive multiplex network embedding using global information. Stowledge-Basel Systems, 197:105861, 2020.
Amin Parvanch, Ehsan Abbasnejad. Damien Teney, Qinfeng Shi, and Anton van den Hengel. Coun- terfactual saiion-and-language navigation: Unravelling the unseen. Advances in Neural Informa- tion Processing Systems, 33, 2020.
Nick Pawlowski, Daniel Castro, and Ben Glocker. Deep structural causal models for tractable counterfactual inference. Advances in Neural Information Processing Systems, 2020.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 701-710, 2014.
Alexander Peysakhovich, Christian Kroer, and Adam Lerer. Robust multi-agent counterfactual pre- diction. Advances in Neural Information Processing Systems, 2019.
S Yu Philip, Jiawei Han, and Christos Faloutsos. Link mining: Models, algorithms, and applications. Springer, 2010.
Silviu Pitis, Elliot Creager, and Animesh Garg. Counterfactual data augmentation using locally factored dynamics. Advances in Neural Information Processing Systems, 2020.
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical review 76(3):036106, 2007.
Paul R Rosenhaum and Donald Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55, 1983.
Donald B Rubin. Estimating causal effects of treatments in randomized and nonrandomized studie.. Journal of educational Psychology, 66(5):688, 1974.
Donald B Rubin. Causal inference using potential outcomes: Design, modeling, decisions. Journal of the American Statistical Association, 100(469):322-331, 2005.
Uri Shalit, Fredrik Johansson, and David Sontag. Estimating individual treatment effect: gener- alization bounds and algorithms. In International Conference on Machine Learning, pp. 3076- 3085. PMLR, 2017.
Eli Sherman and Ilya Shpitser. Intervening on network ties. In Uncertainty in Artificial Intelligence, pp. 975-984. PMLR, 2020.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE winter conference on applications of computer vision (WACV), pp. 464 472. IEEE, 2017.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node em- beddings and structural graph representations. In International Conference on Learning Repre- sentations, 2020.
Zachary Stanfield, Mustafa Coskun, and Mehmet Koyutürk. Drug response prediction as a link prediction problem. Scientific reports, 7(1):1-13, 2017.
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, pp. 1067-1077, 2015.
Mark J van der Laan and Maya L Petersen. Causal effect models for realistic individualized treat- ment and intention to treat rules. The international journal of biostatisties, 3(1), 2007.
12

---

Under review as a conference paper at ICLR 2022
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:/710.10903, 2017.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR (Poster), 2019.
Stefan Wager and Susan Athey. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association, 113(523)1122--244) 2018.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 1225-1234, 2016.
Zifeng Wang, Xi Chen, Rui Wen, Shao-Lun Huang, Ercan E Kuruoglu, and Yefeng Zheng. Informa- tion theoretic counterfactual learning from missing-not-at-randoee feedback. Advances in Neural Information Processing Systems, 2020.
Joe H Ward Jr. Hierarchical grouping optimize an objective function. Journal of the American statistical association, 58(301):236-26) 1963.
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, pp. 1306. American Medical Informatics Association, 2015.
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 database for 2018. Nucleic acids research, 46(D1)D10744D1005 2018
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Adversarial coun- terfactual learning and evaluation for recommender system. Advances in Neural Information Processing Systems, 2020.
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, pp. 5453-5462. PMLR, 2018.
Hong Yang, Shirui Pan, Peng Zhang, Ling Chen, Defu Lian, and Chengqi Zhang. Binarized at- tributed network embedding. In 2018 IEEE International Conference on Data Mining (ICDM), pp. 1476-1481. IEEE, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. International conference on machine learning, pp. 40-48. PMLR, 2016.
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
Jinsung Yoon, James Jordon, and Mihaela Van Der Schaar. Ganite: Estimation of individualized treatment effects using generative adversarial nets. In International Conference on Learning Rep- resentations, 2018.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010.16103, 2020a.
Zhu Zhang, Zhou Zhao, Zhijie Lin, Xiuqiang He, al. Counterfactual contrastive learning for weakly- ssseevvied vision- Languaee grounding. Advances in Neural Information Processing Sys- tems, 33:18123-188 18134, 2020b.
13

---

Under review as a conference paper at ICLR 2022
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006. 04.31, 2020.
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.
14

---

Under review as a conference paper at ICLR 2022
Table 5: 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
APPENDICES
A ADDITIONAL DATASET DETAILS
In this section, we provide some additional dataset details. All the datasets used in this work are publicly available. Statistics for the datasets are shown in Table
Citation Networks CORA, CITESEER, and PUBMED are citation networks that were first used by Yang al. (0166) and then commonly used as benchmarks in GNN-related literature (Kipf & Welling. 2016a; Veličković et al. 2017). In these citation networks, the nodes are published papers and features are bag-of-word vectors extracted from the corresponding paper. Links represent the citation relation between papers. We loaded the datasets with the DGI package.
Social Network The FACEBOOK datase is a social network constructed from friends lists from 2012). The nodes Facebook users and links indicate the
Facebook (McAuley & Leskovee, friendship relation on Facebook. The node features were constructed from the user profiles and anonymized by McAuley & Leskoved (0112).
Drug-Drug Interaction Network The DGB-DDI dataset constructed from public Drug database (Wishart et al. (018)) and provided by the Open Graph Benchmark (OGB) (Hu et al. 2020). Each node in this graph represents existence of unexpected effect when the two drugs are taken together. This dataset does not contain any node features, and it can be downloaded with the dataloade provided
FDA-approved
experimental drug and edges represent the
provided by OGB.
B EXPANDED RELATED WORK
With the rapid development of graph machine learning in the past few years, researchers have been attempting relate graph neural networks (GNNs) with causal models. Recently, several works have been proposed to improve graph learning with causal models (Sherman & Shpitser 2020 Bevilacqua et al. 2021 Lin al. 2021 Feng al. 2021b. Sherman & Shpitser] new concept in causal modeling, called "network intervention", that is type of structural interven- tion in network contexts. (Sherman & Shpitser (2020) modeled social network with causal DAG and studied the effect of network intervention (link creation and removal) on network structure changes. causal learning task and proposed a causal explanation model with a loss designed based on Granger causal- ity. FFeng et al. (202T) formulated node classification of GNNs with causal DAG, which estimated the causal effect of the local structure on the prediction and adaptively chose whether to aggregate from the neighbors. [eevilaqqua al.) (202T) studied the task of out-of-distribution (OOD) graph classification, and showed how subgraph densitics can be used to build size-invariant graph repre- sentations. They modeled OOD graph classification with a twin network DAG causal model, which leamed approximately environment invariiat graph representations that better extrapolate between train and test data. The last three works, i.e., Lin et al. (2021). Feng et al. (2021). [evviaaquaa et al. causal models to improve the performance of three different types of graph machine learning tasks such as GNN explanation (subgraph) generation, node-level classification,
proposed
Lin et al. 202T) formulated the problem of post-hoc explanation generation for GNNs
202I), proposed
httpess//githuub..cmmmmt///
httpar//g...aatrrr....c//c/////p loader
15

---

Under review as a conference paper at ICLR 2022
and graph-level classification. Compared with them, our work has three points of uniqueness. First, to the best of our knowledge, our work makes the first attempt to use causal model to improve the performance of link prediction which is also important graph learning task. Second, to make the attempt successful, our work presents a novel concept of "counterfactual link" and proposes a novel method CFLP that learns from both factual and counterfactual link existence. Third, the proposed method CFLP is flexible with the choice of treatment variables and is able to suggest good treatment choices prior to training via ATE
C DETAILS ON IMPLEMENTATION AND HYPERPARAMETERS
All the experiments in this work were conducted on a Linux server with Intel Xeon Gold 6130 Processor (16 Cores @2.1Ghz), 96 GB of RAM, and 4 RTX 2080Ti cards (11 GB of RAM each). Our method are implemented with Python 3.8. 5 with PyTorch. Source code is available in the supplementary materials, A list of used packages be found in requiremente txt.
Baseline Methods For baseline methods, we use official code packages from the authors for MV- (H & Khasahmadi| 2020). SEAL (Zhang We use public implementation for VGAF (Kipf & Welling, 2016b) and OGB implementation for Node2Vec and baseline GNNs. For fair comparison, we set the size of node/link representations to be 256 of all methods.
(Z & Chen 2018), and LGLF (Cai al. 2021
CFLP We use the Adam optimizer with a simple cyclical learning rate scheduler (Smith 2017 7), in which the learning rate waves cyclically between the given learning rate (Ir) and le-4 in cry 70 epochs (50 warmup steps and 20 annealing steps). We implement the GNN encoders with torch torch_gecmet gecmet rice Fey & Lenssen 2019). Same with the baselines, set the size of all hid- den layers and node/link representations of CFLP as 256. The graph encoders all have three layers and JKNet has mean pooling for the final aggregation layer. The decoder is a 3-layer MLP with a hidden layer of size 64 and ELU as the nonlinearity. As the Euclidean distance used in Eq. (3) has range of [0, oo), the value of y depends on the distribution of all-pair node embedding dis- tances. which varies for different datasets. Therefore. we set the value of as the Tpet Pere-eeeee of all-pair node embedding distances. Commands for reproducing the experiments are included in README md.
Hyperparameter Searching Space Ir E (0.005, 0.01, 0.05, 0.1, 0.2). E {0.001, 0.01, 0.1, 1, {0.001, 0.01, 0.1, 1,2), Ypct (10,20, 20, 30).
We manually tune the following hyperparameters over range:
Treatments For the graph clustering community detection methods used treatments, we use the implementation from sci k weeikiittetttttooo
-o for Louvain (Blondel et al. 2008). SpecC (Ng al. 200T). PropC (Raghavan et al. 2007), and Ward (Ward Jr. 1963). We used implementation of We used SBM (Kareer & Newman, 2011) from a public implementation by Funke Becker (0019) For CommN and Katz, we set J. 1 if the number of common neighbors or Katz index between v and tj are greater equal to 2 or 2 times the average all Katz index values, respectively. For SpecC, we set the number of clusters as 16. For SBM, we set the number of communities as 16. These settings are fixed for all datasets.
K-core (Bader& & Hogue 2003) from netwo networkx:
attaa//ggthuht.co//aaasoorsssss SEAL L OGB
lankproppzed/ddii
16

---

Under review as a conference paper at ICLR 2022
Table 6: Link prediction performances measured by @5..@50. Best performance and best baseline performance are marked with bold and underline, respectively.
CORA
CITESEER
PUBMED
FACEBOOK
OGB-DDI
Node2Vec 63.64.10.76
14.57
50.73
43.91
2..34
MVGRL
29.97=3.06
26.48=0.98
16.96=0.56
17.06=0.19
12.03+0..11
VGAE
60.36#2.71
54.68=3.15
41.98=0.31
51.36=#0.8
23.00=
SEAL
51.68=22.85
54.55=1.77
42.85=2.03
1.820=
40.85=22977
LGLP
71,43-10.75
69.98-0.16
56.22-10.49
GCN
6.69
1..3
39.20=6.447
69,90
73.70+33.99
GSAGE
63.18++3.39
61.71+2.43
54.81
62.53+44.24
86.83+3..85
JKNet
1..64=1.40
62.26+2.10
48.16=3.118
68.81
91.48+2.41
Our proposed CFLP
with different graph encoders
CFLP w/ GCN
72.61=0.92
69.85
15.00=1.95
70.47+0.77
1.54
CFLP w/ GSAGE
73.25
64.75
1..16
63,89
83.32:13.61
CFLP w/ JKNet
75.49-1.554
77.01
62.80
71.41
93.07
Table 7: Link prediction performances measured by Average Precision (AP). Best performance and best baseline performance are marked with bold and underline, respectively.
CORA
CITESBER
PUBMED
FACEBOOK
OGB- DDI
Vec 88.53-00.2
84.42:10.48
87.15=0.12
99.07=0.02
98.3910.04
MVGRL
76.47=3.07
67.40
82.00=0.997
82.37=0.35
81.12::1.77
VGAE
89.89-0.50
86.9710.78
95.97=0.16
98.60-0.04
95.28110.11
SEAL
89.08=00557
88.55+0.32
96.33=0.28
99.51=0.033
98.39-
LGLP
93.05+0003
91.62++0099
98.62+0.01
GCN
91.42=00.45
90.87
09.88
99.42-00022
99.86=#0.03
GSAGE
91.52.10.46
89.43
96.9310.11
99.27-10.06
99.93110.01
JKNe
90.50.10.22
90.42 1.34
96.56_10.1
99.41
99.95.10.01
Our proposed CFLP with different graph encoders
CFLP w/ GCN
93.77=:0.99
91.8411.20
97.16
99.40-10.01
99.60
CFLP w/ GSAGE
93.55=10.49
00.80+0.87
97.10=0.08
99.29-0.066
99.88
CFLP w/ JKNet
94.24-10.28
93.92-10.41
07.69
99.35
99.96-10.01
D ADDITIONAL EXPERIMENTAL RESULTS AND DISCUSSIONS
Link Prediction Tables and 7 show the link prediction performance of Hits@ and Average Precision (AP) by all methods. LGLP PUBMED and OGB-DDI are missing due to the out of memory error when running the code package from the authors. Similar to the results in Tables a we observe that our CFLP different graph encoders achieve similar or better performances compared with baselines, with the only exception of AP on FACEBOOK where most methods have close-to-perfect AP. From Tables I [ we observe that CFLP achieves improvement over all GNN architectures (averaged across datasets). Specifically, CFLP improves 25.6% (GCN), 12.0% (GSAGE), and 36.3% (JKNet) on Hits @20, 9.6% (GCN), 5.0% (GSAGE), and 17.8% (JKNet) on Hits 50, 5.6% (GCN), 1.6% (GSAGE), and 1.9% (JKNet) on AUC, and 0.8% (GCN), 0.8% (GSAGE), and 1.8% (JKNet) on AP. We note that CFLP with JKNet almost consistently achieves the best performance and outperforms baselines significantly on Hits @ 50. Specifically, compared with the best baseline, CFLP improves relatively by 6.8% and 0.9% on Hits@50 and AP, respectively.
Ablation Study on Losses For the ablative studies of Ler (Eq. (9) and Ldise (Eq. 10 we show their effect by removing them from the integrated loss function (Eq. (II) Table 8 shows the results of CFLP on CORA and CITESEER under different settings (a 0, 0, original setting). We observe that CFLP in the original setting achieves the best performance. The performance drops significantly when having a 0. i.c., not using any counterfactual data during training. We note that having 3 = 0, i.c., not using the discrepancy loss, also lowers the perfor- mance. Therefore, both Lor and Laise essential for improving the link prediction performance.
O. and
17

---

Under review as a conference paper at ICLR 2022
Table 8: Link prediction performance of CFLP (w/ JKNet) CORA and CITESEER when removing LCF or Ldisc or both versus normal setting.
CORA
CITESBER
Hits 20
AUC
Hits@20
AUC
CFLP 0)
08.58=#0.23
89.16=0.93
65.49=2211
91.01=0.64
CFLP (8 = 0)
62.27=0084
92.96=0.34
91.98=0.17 1.892=1184
CFLP (a = 8 = 0)
58,52=00.3
88.79=0.28
64.69=3.25
90,61=0.64 68.09:11.49
CFLP
1..5
9.205-0.224
92.12:10.47
Table 9: Link prediction performance of CFLP (w/ JKNet) on CORA and CITESEER with node emheddings (X) learned from different methods.
CORA
CITESEER
OGB-DDI
Hits 20
AUC
Hits@ 20
AUC
Hits@20
AUC
(MVGRL)
65.57:11.05
93.05.10.24 92.28-10.69
18.09:11.49
92.12:10.47 93.80:10.36
1.908
99.94:10.01
(GRACE)
1.45
68.68:11.75
82.30:13.32
99.93:10.01
(DGI)
61.04++1.52
92.99:10:49
72.17
93,34:0.51
8..61
99.94:10.01
Ablation Study on Node Embedding X As the node embedding X is used in the early step of CFLP for finding the counterfactual links, the quality of X may affect the later learning process. Therefore, we also evaluate CFLP with different state-of-the-
unsupervised graph representation learning methods: MVGRL (Hassani & Khasahmadi] (020), DGI (Velickovic al. 2019), and GRACE (Zhu et al.] (020). shows the link prediction performance of CFLP (w/ JKNet) on CORA and CITESFER with different node embeddings. We observe that the choice of the method for learning X does have an impact the later learning process well as the link prediction performance. Nevertheless, Table / different choices of methods for learning X, as CFLP with X learned from all three methods showed promising link prediction performance.
shows CFLP's advantage can be consistently observed with
Sensitivity Analysis of a and | Figure shows the AUC performance of CFLP on CORA with different combinations of a and B3 We observe that the performance the poorest when a and gradually improves and gets stable as and /3 increase, showing that CFLP is generally robust to the hyperparameters a and B, and the optimal values are easy to locate.
Sensitivity Analysis of Figure shows the Hits @ 20 and AUC performance on link prediction of CFLP (with JKNet) on CORA and CITESEER with different treatments and "pot- We observe that the performance is generally good when 10 < Tpot S 20 and gradually get worse when the value of Tpot is too small or too large, showing that CFLP is robust to y and the optimal 7 is easy to find.
Sensitivity to Noisy Data We note that robustness w.r.t. noisy data is not within our claim of technical contributions. Nevertheless, CFLP is not more vulnerable than other link prediction base- lines. We conduct experiments with random attacks on the Cora dataset (randomly removing links and adding noisy links). Table T0 shows the AUC performances of our proposed CFLP (w/ JKNet) compared to the strongest baseline methods under different levels of random attacks (0%, 2%, 5%, and 10%). We can observe that the attack strength goes up, the link prediction performance of all methods go down. We also note that our proposed CFLP still outperforms the baseline methods.
Generalization to Graphs with Weighted Edges As our proposed CFLP uses GNN the graph encoder and GNNs are usually able to take weighted graph as input (e.g., the adjacency matrix A for GCN can be weighted), the model should be able to handle weighted graphs as given. Note the
link prediction losses (Eqs. (8) and ( need to be slightly modified considering the task. When the task to predict the link existence, the label adjacency matrix used in Eqs. and (9) must be of binary values. When the task is predict the link weights, the BCE loss functions (Eqs. and 9 need to be changed to regression loss functions such as MSE.
18

---

Under review as a conference paper at ICLR 2022
0.93
0.91 AUC
0.92
0.62
0.64
0.92
0.56
0.50
2.0
1.5
1.5
0.5
0.5
Deta
0.0
0.5
1.0
1.0
beta
aloha
1.5
2.0
0.0
alpha
1.5
2.0
0.0
(a) AUC performance.
(b) Hits @ performance.
Figure Performance CFLP on CORA different combinations and B.
0.645
0.932
0.670
0.936
H0
0.640
Hits@20
0.655
0.932
0.635
0.928
0.640
0.928
0.630
0.926
0.924
0.625
0.625
0.924
0.920
0.620
10
15
20
25
30
0
10
15
20
25
Vpct
Ypct
(a) Performances of CFLP on CORA when using K-core as treatment.
(h) Performances of CFLP on CORA when using SBM as treatment.
0.702
0.925
0.742
0.946
Hits@20
0.923
Hits@20
0.737
0.944
0.694
0.732
0.942
0.919
0.686
0.917
0.727
0.940
0.682
0.915
0.722
0.938
0
5
10
15
20
25
30
5
10
15
20
25
30
Vpct
Vpct
(c) Performances CFLP on CITESEER when using K-core as treatment.
(d) Performances CFLP on CITESEER when using SBM as treatment.
Figure 5: @its and AUC performances of CFLP (w/ JKNet) on CORA and CITESEER with different treatments w.r.t. different Ypct value.
Table 10: Link prediction performances measured by AUC on CORA when the graph is randomly perturbed at different levels. Best performances marked with bold.
0%
2%
5%
10%
SEAL
92.55++0.50
8..81+1.37
87.90-10.79
87.6 87.64-t0.89
LGLP
91.30.10.05
90.70-10.15
90.38.10.17
88.61-10.15
JKNet
89.05-10.67
88.85110.75
88.14-10.59
87.64.10.89
CFLP w/ JKNet
93.05.10.24
92.93.1..17
92.77-10.18
91.58.10.23
19


Reviews:
[{"review_id": "o3DGjTSrYzh", "reviewer": "Reviewer_LKEp", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "For experiment, I would recommend using more from OGB. I am curious as OGB has many ling prediction dataset, why authors only use one of them? In addition, OGB-DDI authors model should have ranked second best if author submit the results, I wonder why authors do not submit the results in the official leaderboard? I strongly recommending using official leaderboard to illustrate the performance.\n\nCFLP w/ JKNet consistently achieves the best performance across all dataset, while JKNet itself is only very outstanding. Is there any insight on the impact of CFLP for different architecture? \n\nFor the node representation, authors used MVGRL. Is there any ablation study on the impact of the node embedding? This is the early step and if embedding quality is low, the error can propagate through the learning process. \n\nAlso authors mentioned the embedding is learnt from the observed graph, so my understanding the link in validation/testing set is removed during embedding learning?\n\nIn page 4, \"That is, we want to find the nearest neighbor with the opposite treatment for each observed node pairs and use the nearest neighbor’s outcome as a counterfactual link.\" I would recommend adding reference to some matching based methods in causal inference.\n\nIn page 4, authors first used d for a distance function in (2) between two node pairs, while later used similar d for a distance function for two nodes. This is confusing and I would recommend using another symbol.\n\nFor RELATED WORK, it seems not clear how some literatures (especially in the causal inference section) are relevant to this work.", "summary_of_the_paper": "In this work, authors presented a counterfactual graph learning method for link prediction (CFLP), where authors introduced the idea of counterfactual prediction to improve link prediction on graphs.\n\nAuthors demonstrate the model performance on link prediction tasks and achieved promising results. Such results shed insights that a good use of causal models (even basic ones) can greatly improve the performance of (graph) machine learning tasks.", "summary_of_the_review": "From the quality and novelty perspective, the proposed method is interesting and the experiment is thorough. However, my major concern is the causal model in the paper. I am not very convinced with the causal model with 'node similarity' as a treatment, and 'link' as outcome. The proposed approach is more like a data augmentation, where similar pairs are found with different community-relation to enrich the training set. It would be helpful to spend more effort to illustrate why such causal graph design makes sense.\n\nIn addition, the experiment results are exciting, but I didn't observe any submission in the open benchmark website. I highly recommend make a submission for a fair comparison, or explain why the submission has not done yet.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OFwhMfn0OW", "reviewer": "Reviewer_Q6cy", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n\n- Highly creative and novel approach, to the best of my knowledge. The closest related work I have seen is to add and remove edges to a graph to try to improve link prediction accuracy, but that is very different to the counterfactual learning approach proposed here.\n- Proposed approach is conceptually easy to understand and could lead to many variants in the future.\n- Strong empirical performance compared to other recent GNNs.\n\nWeaknesses:\n\n- The proposed counterfactual learning formulation feels like a hammer looking for a nail. The way the treatment is defined seems highly unusual, and there is nothing really principled about it.\n- The authors claim that the estimates of average treatment effect (ATE) are generally close to the observed ATE, but I don't see this at all from Tables 3 and 4. The estimated ATEs are close only for a few specific cases. I do agree with the second conclusion about the ranking of estimated ATE being useful to select the treatment, however.\n\nQuestion regarding a claim from Page 5 section on Complexity:  \"When $\\gamma$ is set as a small value to obtain indeed similar node pairs, this step (Eq. (3)) uses constant time.\" Why is this the case? Also, what is $|\\mathcal{E}|$? Is this the total number of edges in the graph?\n\nTypo:\n\n- Page 3, 4th paragraph: \"Traditional causal inference methods hence statistical learning approaches\". \"hence\" should probably be replaced with \"use\"\n\n*After discussion period:*\nI have lowered my score slightly following the discussions but continue to support the paper. Despite the unusual framing as counterfactual learning as compared to data augmentation, the empirical gains are highly impressive. I think it could inspire future research investigating the use of other structural properties of the graph as the \"treatment\".", "summary_of_the_paper": "The authors propose an approach for link prediction using counterfactual learning. They define a \"treatment\" for a node pair as whether or not they belong in the same group (e.g. from running a graph clustering algorithm). They then find the most similar node pair with a different treatment and treat its outcome (whether there is a link) as the counterfactual of the outcome of the original node pair. To find the most similar node pair, they use a graph neural network (GNN) based encoder. They use two link decoders (both multi-layer Perceptrons) to predict both the actual and counterfactual outcomes. They demonstrate impressive improvements on link prediction accuracy on 5 real data sets.", "summary_of_the_review": "The authors propose a highly creative approach to improve link prediction accuracy by an innovative definition of treatment for a node pair in a counterfactual learning set up. The proposed approach yields highly impressive empirical link prediction accuracy.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LRNzmFUif2g", "reviewer": "Reviewer_y1dx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "strengths:\n- novelty:\nTo me, the new perspective and the main idea are novel in the context of link prediction. \n- correctness:\nTo my knowledge, the idea and technical contribution look sound.\n\nweaknesses:\n- No obvious weaknesses were found in this paper.\n- It is not clear why T^{CF}, A^{CF} = T, A, otherwise in Eq.(4)\n- It is not easy to digest \"...ITE of neighborhood assignment as 1-1=0...\" for someone without causality background!\n\nadditional questions:\n- can you discuss how to generalize your method to continuous-valued network data in the supplement? say, A_ij \\in [0,1], represents the connection strength between nodes i and j.\n- if possible, can you discuss or even conduct additional experiments to demonstrate the robustness of your method to missing (false zeros) and noisy link data, which is prevalent in large-scale networks. \n- except AUROC score, have you considered PR score to evaluate the link prediction performance as PR score is only sensitive to non-zero links?\n\ntypos: \n- pp.1 only were -> are\n- Algo 1 model inferencing -> inference\n- many places causal model -> causal model(s)", "summary_of_the_paper": "This paper targets an interesting question in network analysis: what are the main causes leading to the creation of a link between a pair of two nodes in a given network observations. \n\nMost previous related models assume a latent structure underlying observed network data, and suppose the creation of each link is driven by the latent structure behind two nodes associated with that link. Hence, the main cause effect resulting in the link between two nodes, may not be truly reflected by the underlying community structure.\n\nTo address this concern, the paper resorts to a counterfactual learning framework by learning counterfactual links between the most similar node pairs with a different treatment. Experimental results demonstrate the improved link prediction by the counterfactual graph learning method compared with latent community based methods.", "summary_of_the_review": "Overall, I vote for accepting this paper considering its novelty on solving link prediction from a new perspective of counterfactual learning.\nNonetheless, my background on causality does not allow to check all of its correctness in such a short time. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2gCxZjfGfz9", "reviewer": "Reviewer_WwN8", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Overall, I found this paper to be an interesting approach, but there are a few items that give me pause. Most importantly, it's not entirely clear what the causal estimand is that is being measured. The authors use membership to a community as the running treatment and consider the existence of a link between nodes as the outcome. However, it's not entirely clear to me that what the authors are ultimately doing is measuring a causal effect (the central task does not appear to be measuring a difference between observed and counterfactual networks). Instead, it seems that the proposed procedure is improving performance by enforcing a kind of invariance in representation between the observed network and the closest perturbed network. I find this to be a very interesting and compelling approach, but unfortunately it appears to be a bit obscured by the presentation.  \n\nA few more minor points:\n\n* Sherman & Shpitser (Intervening on Network Ties, UAI 2019) should probably be cited given the relative similarity in task\n\n* It would be helpful if the definition of ATE provided by equations 13 and 14 appeared earlier in the text. It would give a lot more clarity to the presentation to my eyes to have a more formal definition of the estimand provided during the problem setup. \n\n* The authors define the ATE as the expectation of the ITE. The ITE is also an expectation, but conditional on X, whereas the ATE is an unconditional measure (after marginalizing over X).  \n", "summary_of_the_paper": "This work looks at the problem of link prediction from the lens of causal inference. In particular, the authors introduce counterfactual links, which are links which would have existed under a different treatment (with a running example being the neighborhood identifier). The authors use this definition to define a training procedure which builds on prior art in neural net based causal inference that uses an IPM penalty to ensure balance in representation between treatment and control outcomes. Experimental results are provided which show strong empirical performance for the proposed model.", "summary_of_the_review": "Overall, I think this is an interesting approach, but unfortunately I think the framing of the paper as a causal estimation paper, rather than a paper which uses counterfactuals a mechanism to improve invariance and performance makes the contributions of the paper slightly obscured. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes an observational (not counterfactual) link prediction method based on clustering and data augmentation. The total score went down during the rebuttal phase. One of the challenges is that the title confused reviewers. The authors proposed other titles. But in the end all proposed titles had variations of "counterfactual graph", which is what makes the title confusing. 

I think if the work had been more empirically-focused and stayed away from a causal model, it would have been accepted. The idea is ingenious and it is likely that it indeed gives the empirical improvement in observational models that the authors claim. The authors have very scant citations to relevant works in the intersection of causality and representation learning anyways. But if the causal model must stay for future submissions, the authors should: (a) more clearly define and differentiate the causal and non-causal aspects of the task (and properly contextualize the work), and (b) more clearly specifies the causal model that is being utilized (and be more mathematically rigorous in general).

Unfortunately, the original description of the causal model in the paper was both sloppy and incorrect. I had to ask a total number of five (5) long clarifying questions (visible to authors and reviewers only) in order to understand the causal assumptions. In my back-and-forth with the authors, the authors proposed a total of 7 different causal DAGs to explain their method. Some of these DAGs contradicted each other and most of the answers were vague. My first advice to the authors is to always be mathematically precise for the benefit of reviewers and readers. Causality requires very clear assumptions and precise notation. For instance, the variables in the causal DAG given in Figures 2 and 3 had little to do with the variables in the actual graph model. The causal DAG must have the variables $A_{ij}$, $T_{ij}$, $C_i$, $C_j$, $z_i$, $z_j$, for all $i,j \in V$. The final causal DAG proposed by the authors in the discussion was:
- $z_i \to A_{ij}$
- $z_j \to A_{ij}$
- $z_i \to T_{ij}$ (may not be needed)
- $z_j \to T_{ij}$ (may not be needed)
- $C_i \to T_{ij}$
- $C_j \to T_{ij}$
- $T_{ij} \to A_{ij}$

Regarding the nature of $z_i$ and $z_j$: They need to be formally described as structural node embeddings of the graph, otherwise the DAG is incorrect. After digging and reading some of the references the authors use, I came to the conclusion that the empirical method indeed relies on structural embeddings (and the authors later confirmed it). This should be made **very** clear in the SCM description.

This final causal model after discussion looks reasonable. And one challenge that remains, however, is sampling or MAP point estimates of the posterior $P(C_i,C_j|A)$. All standard clustering methods that can use this DAG rely on node embeddings $z_i, z_j$ being positional embeddings, not structural ones. So, how are we actually obtaining $P(C_i,C_j|A)$? The authors would need to prove that standard clustering methods can perform this task (I have my doubts this is even true). I fear this issue could again derail the paper in a future submission if the counterfactual justification is used again. One of the reviewers raised concerns about the quality of the embedding already.

The proposed method is observational and does not need a causal description. But if a causal description is provided, it must be correct and the method must be theoretically sound. The causality part of the paper needs a substantial revision, unfortunately. I suggest rejection.
Decision: Reject