Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
Experiments of various commonly-used datasets show that the proposed method results in improved link prediction performance compared to state-of-the-art methods.
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.

Quality: 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.

Clarity: 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.

Significance: 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.
limitations_and_societal_impact: The authors adequately address the limitations of the work. Please, see above for a potential societal impact to address.
review_title: null

final_score: rating: 3: Clear rejection
review_content: 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.
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.

+ Very important task. I am excited to see work in this space. I encourage the authors to continue improving their paper.

- 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.

-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.

- 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? 

- When talking about "Counterfactual Links", the paper still offers no structural causal model. 

- 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.

- 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. 

Bevilacqua, Beatrice, Yangze Zhou, and Bruno Ribeiro. "Size-Invariant Graph Representations for Graph Classification Extrapolations." ICML (2021)
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors consider a link prediction problem utilizing the idea of causal inference.
To 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.
The 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.
main_review: This paper is well written and easy to follow.
I 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.
In 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. 
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. 
It would be better to provide theoretical analysis.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Originality:

The 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.

Quality: 

- 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.

- 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.

Clarity:

+ Overall, this paper is well organized. The technical part is mostly clear. 

- 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.

- 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?

- 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. 

- 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.
Eq. 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.

- The link prediction results need more explanation (see Significance).

Significance: 

- 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. 

- 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?

- 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.

(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.

(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.

Minor issues:
- It would be better to describe terms consistently, e.g., individualized treatment effect and individual treatment effect.    
- It would be clearer to draw balancing counterfactual learning in Fig.1(b).
- 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.

Thanks to the authors for the response.


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_title: null

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