TL;DR
This paper tackles the critical issue of "agnostic label selection bias" in Graph Neural Networks (GNNs), where the training data distribution differs from the real-world test data distribution. They introduce Debiased Graph Neural Networks (DGNN), a novel framework that uses a "differentiated decorrelation regularizer" to learn sample weights, effectively mitigating estimation bias and improving generalization on unseen nodes.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) have shown remarkable success in learning from graph-structured data. However, a fundamental assumption in their training is that the distribution of labeled training nodes mirrors that of unseen test nodes. This assumption often breaks in real-world scenarios due to "selection bias." This bias arises because data collection and labeling are not perfectly controlled, leading to inconsistencies between the training and test sets. For instance, in a scientific collaboration network, researchers might preferentially label scientists involved in interdisciplinary projects, creating a bias. When GNNs are trained on such biased data, they learn spurious correlations between node features, graph structure, and labels, which significantly degrades their performance on new, unseen nodes. The problem is exacerbated because test data is typically unavailable during training, making this bias "agnostic."
Methods
The authors propose a novel framework called Debiased Graph Neural Networks (DGNN). The core of their approach is a differentiated decorrelation regularizer. This regularizer aims to eliminate the spurious correlations between "stable" and "unstable" variables within node embeddings.
Here's a breakdown of their methodology:
- Theoretical Analysis: They first provide a theoretical justification for why selection bias leads to parameter estimation bias in GNNs. They decompose node embeddings into stable (related to the true label) and unstable (spurious correlations) components and show how biased data distorts this relationship.
- Variable Decorrelation (VD): They build upon existing Variable Decorrelation techniques, which aim to make different variables within embeddings independent. However, standard VD requires a large number of samples.
- Differentiated Variable Decorrelation (DVD): To address the limitations of VD, they introduce a differentiated approach. This means they don't treat all variables equally. Instead, they learn sample weights that account for each variable's contribution to the confounding bias. This is inspired by causal inference techniques, where confounders are balanced to estimate treatment effects.
- Sample Reweighting: The learned sample weights from the DVD regularizer are then used to reweight the GNN's loss function. This effectively "debiases" the training process, leading to more stable parameter estimation and improved generalization.
- Framework Integration: The VD/DVD regularizer can be seamlessly integrated into existing GNN architectures like GCN and GAT, making DGNN a flexible framework.
Datasets
The paper evaluates their proposed DGNN framework on several widely used graph datasets for node classification:
- Cora: A citation network.
- Citeseer: A citation network.
- Pubmed: A citation network.
For these datasets, they specifically simulate label selection bias by creating training sets with varying degrees of bias (light, medium, heavy), in addition to an unbiased baseline.
They also evaluate on:
- NELL: A knowledge graph dataset, used to test small sample selection bias, where each class has a very limited number of labeled nodes.
Key Insights and Ideas
- Selection Bias is a Major Bottleneck: The experimental investigation clearly demonstrates that standard GNNs are highly sensitive to selection bias, with performance dropping significantly as bias increases. This highlights a critical, often overlooked, issue in real-world GNN applications.
- Theoretical Foundation for Bias: The paper provides a solid theoretical grounding for why selection bias causes parameter estimation bias in GNNs, linking it to spurious correlations between stable and unstable embedding components.
- Differentiated Approach is Crucial: The DVD term, which differentiates variable weights, consistently outperforms the simpler VD term, especially in scenarios with heavier bias or fewer labeled nodes. This suggests that not all spurious correlations are equal, and a targeted approach is more effective.
- DGNN is a Flexible Enhancement: The DGNN framework is designed to be easily integrated with existing GNN architectures (GCN, GAT), acting as a plug-in module to improve their robustness.
Key Results
- Significant Performance Gains: DGNN consistently outperforms state-of-the-art GNNs (GCN, GAT) across various datasets and bias levels. For example, they report up to 17.0% performance improvements over base models, with larger gains observed under heavier bias conditions.
- Robustness to Bias: The proposed models show remarkable robustness to different degrees of label selection bias, maintaining higher accuracy compared to their non-debiased counterparts.
- Effectiveness in Small Sample Scenarios: On the NELL dataset, DGNN also demonstrates significant improvements under small sample selection bias, indicating its utility when labeled data is scarce.
- Training Time: The additional computational cost for DGNN is comparable to the base GNN models, making it practical for real-world deployment.
Limitations and Future Work
- VD vs. DVD Trade-off: The paper notes that while the VD term aggressively decorrelates variables, it theoretically requires a large number of samples. The DVD term, by differentiating weights, is more effective with fewer samples but introduces more parameters, potentially increasing model instability. The authors suggest that when labeled samples are abundant, GNN-VD might yield more stable results.
- Generalization to Other GNNs: While the paper demonstrates integration with GCN and GAT, they mention that extending the VD/DVD term to other GNN architectures is a direction for future work.
- Causal View Limitations: The theoretical analysis is partly based on a linear regression predictor. While they extend it to classification, the core assumptions might not perfectly capture all complex GNN behaviors.
- Prior Knowledge: The DVD term requires differentiating variable weights, which is motivated by causal inference. While it doesn't require explicit prior knowledge of the test distribution, the underlying causal assumptions are implicitly leveraged.
Summary updated