PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning from Counterfactual Links for Link Prediction

Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, Meng Jiang

arXiv:2106.02172v2cs.LG

TL;DR

Link prediction methods largely learn associations between graph structure and link existence, leaving their causal relationship underexplored. CFLP uses counterfactual links to augment training with alternate-treatment outcomes, and achieves state-of-the-art performance on benchmark datasets.

  • Problem

    Existing link predictors learn associations between graph structure and link existence while largely ignoring their causal relationship.

    Source: §1 · p. 1

  • Method

    CFLP treats node-pair representations as context, global structural roles as treatment, and link existence as outcome, adding counterfactual links to factual training.

    Source: §1 · pp. 1–2, §3.1 · p. 3

  • Results

    CFLP achieves state-of-the-art performance on benchmark datasets; on BOOK, it improves relatively by 16.4% on Hits@20 over the best baseline.

    Source: §4.2 · p. 7, §6 · p. 9

  • Takeaways & Limitations

    The authors conclude that even basic causal models can improve graph-machine-learning performance, including link prediction.

    Source: §6 · p. 9

    CFLP performs counterfactual prediction with only a single treatment.

    Source: §3.3 · p. 6

Abstract

from arXiv · show

Learning to predict missing links is important for many graph-based applications. Existing methods were designed to learn the association between observed graph structure and existence of link between a pair of nodes. However, the causal relationship between the two variables was largely ignored for learning to predict links on a graph. In this work, we visit this factor by asking a counterfactual question: "would the link still exist if the graph structure became different from observation?" Its answer, counterfactual links, will be able to augment the graph data for representation learning. To create these links, we employ causal models that consider the information (i.e., learned representations) of node pairs as context, global graph structural properties as treatment, and link existence as outcome. We propose a novel data augmentation-based link prediction method that creates counterfactual links and learns representations from both the observed and counterfactual links. Experiments on benchmark data show that our graph learning method achieves state-of-the-art performance on the task of link prediction.

1. Introduction

Prior link predictors largely learn associations between graph structure and link existence, leaving their causal relationship unaddressed. CFLP asks whether a link would exist under a different graph structure, creating counterfactual links to augment training and learn from both factual and counterfactual links.

1. Introduction

  • Existing methods largely ignore the causal relationship between graph structure and link existence, and associations may obscure other factors relevant to links.The motivating example is that neighborhood belonging could mask factors such as common interests or family relationships.Source: §1 · p. 1
  • CFLP frames link prediction counterfactually: would a link exist if the graph structure differed from what was observed?Node-pair information is context, graph structural properties are treatment, and link existence is outcome.Source: §1 · p. 1
  • CFLP introduces counterfactual links as augmented training data and trains a GNN-based link predictor on both factual and counterfactual links.The paper reports that CFLP outperforms competitive baselines on several benchmark datasets.Source: §1 · p. 2
  • For each node pair, CFLP finds the most similar pair with a different treatment; that pair’s observed edge or non-edge supplies the counterfactual outcome.The counterfactual links enrich the training set, and the predictor learns from them alongside factual links.Source: §1 · p. 2
  • The authors describe CFLP as the first work to improve link prediction through causal inference and report gains over competitive benchmark baselines.They also analyze the impact of counterfactual links and treatment-variable choice.Source: §1 · p. 2

2. Problem Definition

The section defines link prediction on an observed graph with validation and testing links masked, and describes the graph and node representations used by GNN-based methods.

2. Problem Definition

  • The graph is denoted G = (V, E), with V the nodes and E the observed links; its adjacency matrix records which node pairs are connected.The node feature matrix X contains feature vectors for the nodes.Source: §2 · p. 2
  • Given an observed graph with validation and testing links masked, the task is to predict link existence between every node pair.GNN-based methods learn low-dimensional node representations and use them to predict links.Source: §2 · pp. 2–3

3. Proposed Method

CFLP treats global graph structure as a treatment for link existence and uses estimated counterfactual links to augment graph learning. It trains on factual and counterfactual link data while regularizing their representations.

3.1. Improving Graph Learning with Causal Model

  • CFLP uses each node pair’s global structural role as treatment and estimates its effect on link existence to improve node representations.The example treatment assigns pairs to same-community or different-community groups.Source: §3.1 · p. 3

3.2. Counterfactual Links

  • For each pair, CFLP substitutes the observed outcome of a nearest pair with opposite treatment, selected using node embeddings and an embedding-distance threshold.If no opposite-treatment pair is close enough, CFLP assigns no nearest neighbor.Source: §3.2 · p. 4

3.3. Learning from Counterfactual Links

  • The graph encoder can use a GCN, represents node pairs with a Hadamard product, and passes pair representations and treatments to an MLP link decoder.The paper presents GCN as an example encoder; the encoder can be any end-to-end GNN.Source: §3.3 · pp. 4–5
  • Training combines factual-link and counterfactual-link prediction losses with a discrepancy loss between representations, then fine-tunes the decoder on factual data.The discrepancy term addresses the risk of covariate shift because training distributions need not align while inference uses factual samples.Source: §3.3 · p. 5
  • Counterfactual-link search has worst-case complexity O(N^2), and CFLP uses only a single treatment despite other graph structural information being available.The paper identifies bundled treatments as a direction for future work.Source: §3.3 · p. 6

4. Experiments

Experiments compare CFLP across benchmark datasets, GNN encoders, and treatment choices. CFLP generally matches or outperforms baselines, while estimated and observed treatment effects track one another and are negatively correlated with link-prediction performance.

4.1. Experimental Setup

  • Across five benchmarks, evaluation uses three GNN encoders, six named baseline methods, and averaged test performance over 20 random initializations.The first four datasets use randomly selected validation and test links and equal numbers of disconnected node pairs; OGB-DDI uses official splits.Source: §4.1 · p. 6
  • Across five benchmark datasets, experiments use K-core clusters as the default treatment variable and report AUC and Hits@20, with Hits@20 a more challenging metric because it expects positive edges to rank above nearly all negative edges.The appendix includes sensitivity results on γ and ablation studies on LCF and Ldisc.Source: §4.1 · pp. 6–7

4.2. Experimental Results

  • On link-prediction benchmarks, CFLP with JKNet almost consistently achieves best performance and, versus the best baseline, improves relatively by 16.4% on Hits@20 and 0.8% on AUC.Source: §4.2 · p. 7
  • CFLP’s improvement over GNN-based baselines is attributed to learning from observed links together with counterfactual links.The results section says the counterfactual data complement partial observations for learning better representations.Source: §4.2 · pp. 7–8
  • Observed and estimated ATE rankings are positively correlated on CORA and CITESEER, with Kendall coefficients of 0.67 and 0.57, respectively.The treatment comparisons include link-prediction performance and both ATE estimates.Source: §4.2 · p. 7, Table 4 · p. 8, Table 5 · p. 8
  • Observed and estimated ATEs are both negatively correlated with link-prediction performance, and weaker treatment–outcome relationships are described as likely to help capture essential outcome factors.The authors suggest choosing a treatment before training; they compare graph clustering and community-detection treatments, including K-core, SBM, spectral clustering, Louvain, common neighbors, and Katz index.Source: §4.1 · p. 6, §4.2 · p. 7

5. Related Work

Prior link-prediction work spans statistical, data-mining, embedding, and GNN approaches, while causal inference and graph data augmentation have largely been studied separately from link prediction. The section identifies causal inference for link prediction and link-prediction data augmentation as underexplored.

Link Prediction

  • Link-prediction approaches include stochastic block models, matrix factorization, heuristics, graph embeddings, and GNNs that combine node-pair representations with a decoder.Examples include VGAE, SEAL, multi-scale subgraph representations, and LGLP’s conversion of local subgraphs to line graphs.Source: §5 · p. 8

Causal Inference

  • Causal-inference work includes propensity-score reweighting, treatment-invariant representations, and graph-learning studies, but little prior work uses causal inference to improve link prediction.Sherman & Shpitser (2020) studied network intervention to examine how link creation changes network structure.Source: §5 · p. 8
  • Counterfactual prediction has been applied in recommender systems, health care, and decision making, with prior work often estimating individual treatment effects through function-fitting models.The section also reviews methods for learning treatment-invariant representations and estimating causal effects.Source: §5 · p. 8

Graph Data Augmentation

  • Graph data augmentation has focused mainly on node- and graph-level tasks, leaving augmentation for link prediction under-explored.Prior augmentation examples include edge dropping and link-predictor-based graph-structure manipulation.Source: §5 · pp. 8–9

6. Conclusion and Future Work

The paper presents counterfactual links and CFLP, which uses them as augmented training data to explore how global graph structure relates to link existence. Experiments report state-of-the-art benchmark performance, while the authors identify more sophisticated causal models and alternative treatments as future directions.

6. Conclusion and Future Work

  • Counterfactual links answer counterfactual questions about link existence and serve as augmented training data in CFLP.CFLP explores the causal relationship between global graph structure and link existence to predict missing links.Source: §6 · p. 9
  • Extensive experiments demonstrate state-of-the-art performance for CFLP on benchmark datasets.Source: §6 · p. 9
  • The authors suggest that more sophisticated causal models and treatments beyond cluster-based global graph structure merit future empirical and theoretical exploration.They also state that even basic causal models can improve machine-learning tasks such as link prediction.Source: §6 · p. 9

A. Additional Dataset Details

The additional dataset details describe three citation networks, a Facebook friendship network, and a drug–drug interaction network. All datasets used in the work are publicly available.

Additional Dataset Details

Citation Networks

  • CORA, CITESEER, and PUBMED are citation networks whose nodes are papers, features are bag-of-word vectors, and links represent citations.The datasets are described as commonly used benchmarks in GNN-related literature.Source: A. Additional Dataset Details · p. 13

Social Network

Drug-Drug Interaction Network

  • OGB-DDI represents drugs as nodes and unexpected effects when two drugs are taken together as edges; it has no node features.The dataset is provided by the Open Graph Benchmark.Source: A. Additional Dataset Details · p. 13

B. Details on Implementation and Hyperparameters

The experiments use standardized baseline representations and a specified CFLP architecture, with implementation settings and treatment definitions documented for reproducibility.

Implementation

  • Experiments ran on a Linux server with four RTX 2080Ti cards, using Python 3.8.5 and PyTorch; code is publicly available.The system had an Intel Xeon Gold 6130 processor and 96 GB RAM.Source: B. Details on Implementation and… · p. 13

Baseline Methods

  • Baselines use 256-dimensional node and link representations for fair comparison.The study uses official or public implementations of MVGRL, SEAL, LGLP, VGAE, Node2Vec, and baseline GNNs.Source: B. Details on Implementation and… · p. 13

CFLP

  • CFLP uses three-layer GNN encoders, mean-pooled JKNet aggregation, and a three-layer ELU MLP decoder, with 256-dimensional hidden layers and representations.It uses Adam with a cyclical learning rate between the chosen rate and 1e-4 every 70 epochs; γ is set to a percentile of all-pair embedding distances.Source: B. Details on Implementation and… · p. 13

Hyperparameter Searching Space

  • The hyperparameter search manually varies learning rate, α, and β over five values each, and γpct over 10, 20, and 30.The tested learning rates are 0.005, 0.01, 0.05, 0.1, and 0.2; α and β each use 0.001, 0.01, 0.1, 1, and 2.Source: B. Details on Implementation and… · p. 13

Treatments

  • Treatments include Louvain, SpecC, PropC, Ward, K-core, and SBM, with 16 clusters for SpecC and 16 communities for SBM across datasets.CommN and Katz treatments use thresholds based on at least two common neighbors or twice the average Katz index, respectively.Source: B. Details on Implementation and… · pp. 13–14

Link Prediction

  • Tables 6 and 7 report link-prediction performance using Hits@50 and Average Precision, respectively.The tables mark the best result and best baseline result.Source: Table 6 · p. 14, Table 7 · p. 14

C. Additional Experimental Results and Discussions

Additional experiments compare CFLP with baselines, test its loss and embedding choices, and examine sensitivity to α, β, and γ. They report gains over baselines and robustness across several settings.

Link Prediction

  • CFLP improves over baselines across GNN architectures, and JKNet almost consistently achieves the best performance, including relative gains of 6.8% on Hits@50 and 0.9% on AP versus the best baseline.Averaged across datasets, CFLP improves Hits@20 by 25.6% (GCN), 12.0% (GSAGE), and 36.3% (JKNet), and Hits@50 by 9.6% (GCN), 5.0% (GSAGE), and 17.8% (JKNet). It also improves AUC by 5.6% (GCN), 1.6% (GSAGE), and 1.9% (JKNet), and AP by 0.8% (GCN), 0.8% (GSAGE), and 1.8% (JKNet).Source: C. Additional Experimental Results and… · p. 14

Ablation Study on Losses

Ablation Study on Node Embedding

Sensitivity Analysis of α and β

Sensitivity Analysis of γ

  • For JKNet on CORA and CITESEER, performance is generally good when 10 ≤ γpct ≤ 20 and worsens when γpct is too small or too large.Figure 4 compares Hits@20 and AUC across different treatments and γpct values; the authors describe CFLP as robust to γ with an easily found optimum.Source: C. Additional Experimental Results and… · p. 15, Figure 4 · p. 16
Loading 2106.02172v2…