Counterfactual learning on graphs: A survey

Graphs are a ubiquitous data structure and a universal language for representing objects and complex interactions. They can model a wide range of real-world systems, such as social networks, chemical compounds, knowledge graphs, and recommendation systems. For instance, in social networks, nodes represent people, and edges between nodes denote social connections between them. In molecular graphs, nodes correspond to atoms, and edges represent the chemical bonds between them, providing a structural representation of chemical compounds that can be used for tasks like drug discovery or material design. The pervasiveness of graph-structured data has raised the broad attention of researchers on graph analytics and mining, and various methods have been proposed.

Network representation, which aims to learn low-dimensional vector representations of nodes or graphs that capture the intrinsic feature and structure information of nodes or graphs, is one essential task of graph mining. The learned representation can facilitate various downstream tasks such as node classification, link prediction, community detection and graph classification. Neural networks have shown great power in representation learning for many domains such as computer vision, natural language processing, etc. Neural network-based methods have also inspired the emergence and flourishing of graph neural networks (GNNs). Since graph convolutional network was proposed, there have been various variants of GNNs. They greatly boost the development of graph learning methods and have achieved state-of-the-art performance on many graph mining tasks, e.g., node classification, link prediction and graph classification. Due to the great power of graph learning methods, they have been successfully applied in many high-stakes decision scenarios, such as drug discovery, fake news detection and financial analysis.

Despite the great potential of real-world benefits, recent studies show that existing graph learning methods tend to inherit the bias pattern from the biased dataset, lack the interpretability and cannot exploit the rich information stored in graph data. For example, with the biased dataset, GNNs are easy to learn an unfair classifier, e.g., give applicants different decisions based on their races or other sensitive information. These issues severely hinder trust in the model and limit the real-world application of graph learning methods. Counterfactual learning gives a chance to alleviate the intrinsic bias, making models interpretable and exploiting the information stored in data well. The notation of counterfactual comes from the research community of causal inference. Counterfactual reasoning aims to answer “what would have happened, given the knowledge of what in fact happened”. The ability to learn with counterfactuals and generalize to unseen environments is considered a significant component of general AI. The topic of learning causality has been well studied in many areas, such as economics, education, and medical science. To know the causal effect of an action, people need to know the factual outcome with the observed action and the counterfactual outcome with unobserved action. A straightforward approach is to conduct randomized controlled trials to get counterfactual outcomes. However, in the real-world setting, people only have access to the observational factual data, i.e., the observed action and its corresponding factual outcome, which is a key challenge to learn causality. Fortunately, the development of information technology gives abundant data sources that people can take advantage of to find the implied information in the data. Hence, the core question is how to get the counterfactuals from the observational data, and how to use the counterfactuals to aid machine learning models.

Counterfactual learning on graphs is an emerging direction and only has a very short history. However, recent works on graph counterfactual learning have shown great potential to overcome the aforementioned challenges on fairness, explanation, etc. In Fig. 1, researchers show some motivation examples for graph counterfactual learning. Concretely, equipped with counterfactual learning, people can go beyond the fairness definition at the group level and achieve fairness for each individual as in the factual world and the counterfactual world, where the individual belongs to a different demographic group. As depicted in Fig. 1(a), the goal of counterfactual fairness is to ensure that an applicant and his counterfactual counterpart (with a different gender) receive the same credit card application outcome. For counterfactual explanation on graphs, in addition to finding a compact subgraph which is highly correlated to the prediction, it aims at finding a reasonable change to have different result, which can be used to not only answer why the model gives such prediction but also give suggestions on what to do in order to achieve another desired result. As illustrated in Fig. 1(b), in a credit card application scenario, when an applicant is rejected, a conventional explanation might state that their “credit score was too low.” In contrast, a counterfactual explanation could provide actionable recommendations on what minimal changes (e.g., in transaction relationships) the customer could make to alter the decision and ultimately gain approval. Besides the aid on fairness and interpretability, the research community also utilizes counterfactual learning to provide additional information from the counterfactual world, e.g., using both factual links and counterfactual links to help build more powerful GNNs. As shown in Fig. 1(c), two friends live in the same neighborhood. By placing them in different neighborhoods, GNNs can infer the counterfactual link between them. This enables GNNs to gain a deeper understanding of the causal factors that shape their relationships while mitigating the impact of neighborhood factors. Considering the increasing trend of graph counterfactual learning and the diversity of related pretext tasks, there is an urgent need to have a systematic taxonomy to summarize the methodologies and applications of graph counterfactual learning.

To fill the gap, this survey paper published in Machine Intelligence Research conducts the first comprehensive and up-to-date overview of the booming area of graph counterfactual learning, provides some insights and potential future directions, and creates a “one-step-stop” that collects a set of open-source implementations, public datasets and commonly-used evaluation metrics together. The intended audiences for this article are general machine learning researchers who would like to know graph counterfactual learning, graph learning researchers who want to keep track of the most recent advances in graph neural networks, and domain experts who would like to generalize graph counterfactual learning to new applications or other fields. The core contributions of this survey are:

1) The first survey of counterfactual learning on graphs. This survey is the first to review counterfactual learning techniques for graphs. The most relevant surveys are about causal inference and causal machine learning. At the time the survey was initially completed, there has been no dedicated and comprehensive survey about causal learning in graph domain.

2) A comprehensive and up-to-date review. Researchers review the most up-to-date graph counterfactual learning techniques published in influential international conferences and journals of deep learning, data mining, computer vision, natural language processing, and artificial intelligence, including ACM TOIS, ICLR, NeurIPS, ICML, SIGKDD, WSDM, CIKM, WWW, ICDM, NAACL, IJCAI, AAAI and others. Researchers also include papers in other domains like chemical science.

3) Systematic taxonomy and unified frameworks. Researchers systematically categorize existing works into counterfactual fairness, counterfactual explanation, counterfactual link prediction and recommendation, and applications. For most of the categories, researchers provide unified frameworks that mathematically formalize graph counterfactual learning approaches in each category.

4) Future directions and “one-step-stop” for resources. From the survey results, researchers point out promising and important future directions. They also provide a collection of open-source implementations, public datasets, and commonly used evaluation metrics to facilitate the community. Researchers maintain a repository containing papers in graph counterfactual learning and they will keep updating these papers in the repository: https://github.com/TimeLovercc/Awesome-Graph-Causal-Learning.

Comparison is with related survey articles. There is one Table in this survey that highlights the differences between this survey and related survey papers. Most existing surveys primarily focus on general causal inference, counterfactual fairness, and counterfactual explanation, seldom discussing research progress on graph data. While other graph domain surveys address fairness and interpretability, they rarely summarize existing work from causal or counterfactual learning perspectives. This survey provides the first comprehensive overview of graph counterfactual learning, offering causal learning background, reviewing graph counterfactual learning techniques for fairness-aware models, explainable models, link prediction, recommender systems, real-world applications, and promising research directions. Hence, this survey is distinct from existing surveys and can support the growth of this important and emerging domain.

In Section 2, researchers give the notations and definitions frequently used in this survey. Researchers also provide some background knowledge for the following sections.

In Section 3, researchers introduce the background of fairness issues in graph learning and counterfactual fairness, followed by a general framework of graph counterfactual fairness models and their details. Researchers conclude with widely used fairness evaluation metrics and datasets.

In Section 4, researchers first introduce background and definition of graph counterfactual explanation. Then researchers summarize existing works into a general framework of graph counterfactual explanation followed by a detailed review of existing methods. Finally, they review widely used metrics and datasets.

In Section 5, researchers give a comprehensive review of existing works on counterfactual link prediction and counterfactual recommendation with graph learning.

Due to its superior performance in many tasks, graph counterfactual learning has wide applications in real-world scenarios. In Section 6, researchers first review applications in various domains, including physical systems, medical and molecular. They then review the adoption of graph counterfactual learning to facilitate other machine learning techniques.

Despite various efforts taken on graph counterfactual learning, it is still in its early stage. Existing approaches mainly focus on static graphs and lack the ability to generalize to other settings, such as large-scale graphs and dynamic graphs. Moreover, most existing datasets and metrics are developed for factual learning, not dedicated to counterfactual learning, which may not accurately reflect the performance of counterfactual learning methods. Additionally, some directions are not yet fully explored and require further investigation, such as unsupervised graph counterfactual learning and counterfactual data augmentation. In Section 7, researchers summarize the existing open-source implementations to help readers have a better knowledge of current progress. Next, researchers give the details of future works, aiming to provide researchers with insights into crucial directions in this field.

Section 8 concludes this survey. In this survey, researchers present a comprehensive review of counterfactual learning on graphs from the problems of counterfactual fairness, counterfactual explanation, counterfactual link prediction and the real-world applications of graph counterfactual learning. This is the first survey for counterfactual learning on graphs. In particular, researchers first introduce the basic concept of counterfactual learning, then introduce a framework to give a unified understanding of the problems. Researchers also summarize the datasets and metrics used in each category. Then researchers go beyond the counterfactual learning on graphs to its applications in many areas, such as physical systems, medical, etc. Finally, researchers also discuss future directions and encourage domain experts to contribute to essential and urgent topics in this area. They believe this survey can give starters the fundamental knowledge and inspire the domain experts to solve the urgent challenges in this area.

See the article:

Counterfactual Learning on Graphs: A Survey

http://doi.org/10.1007/s11633-024-1519-z