Lifelong Learning on Evolving Graphs Under the Constraints of Imbalanced Classes and New Classes

Lukas Galke, Iacopo Vagliano, Benedikt Franke, Tobias Zielke, Ansgar Scherp, Scherp, Ansgar

Abstract

Lifelong graph learning deals with the problem of continually adapting graph neural network (GNN) models to changes in evolving graphs. We address two critical challenges of lifelong graph learning in this work: dealing with new classes and tackling imbalanced class distributions. The combination of these two challenges is particularly relevant since newly emerging classes typically resemble only a tiny fraction of the data, adding to the already skewed class distribution. We make several contributions: First, we show that the amount of unlabeled data does not influence the results, which is an essential prerequisite for lifelong learning on a sequence of tasks. Second, we experiment with different label rates and show that our methods can perform well with only a tiny fraction of annotated nodes. Third, we propose the gDOC method to detect new classes under the constraint of having an imbalanced class distribution. The critical ingredient is a weighted binary cross-entropy loss function to account for the class imbalance. Moreover, we demonstrate combinations of gDOC with various base GNN models such as GraphSAGE, Simplified Graph Convolution, and Graph Attention Networks. Lastly, our k-neighborhood time difference measure provably normalizes the temporal changes across different graph datasets. With extensive experimentation, we find that the proposed gDOC method is consistently better than a naive adaption of DOC to graphs. Specifically, in experiments using the smallest history size, the out-of-distribution detection score of gDOC is 0.09 compared to 0.01 for DOC. Furthermore, gDOC achieves an Open-F1 score, a combined measure of in-distribution classification and out-of-distribution detection, of 0.33 compared to 0.25 of DOC (32% increase).

Introduction: The Challenge of Evolving Graphs

Real-world graphs—such as citation networks, social media, or biological interaction maps—are not static; they are living organisms that evolve over time. This evolution presents two major hurdles for "lifelong" learning:

  1. New Classes: As a graph grows, entirely new categories of nodes can appear (e.g., a new field of research in a citation graph). Standard models often try to force these new nodes into existing categories.
  2. Class Imbalance: Newly emerged classes are often tiny compared to established ones. This skew makes it incredibly difficult for models to distinguish between a "rare known class" and a "completely new unknown class."
Temporal task structure for lifelong graph learning, illustrating the sliding window of history and evaluation on new tasks.

The goal of this research is to bridge the gap between lifelong learning (adapting over time) and open-world learning (detecting the unknown) specifically for graph-structured data.

Methodology: gDOC and Temporal Normalization

The primary contribution of this work is gDOC (Graph Deep Open Classification), which adapts the DOC algorithm to graphs. Unlike standard GNNs that use a softmax output, gDOC employs element-wise sigmoid activations. The "secret sauce" is a weighted binary cross-entropy loss that penalizes errors more heavily for rare classes, preventing the model from being overwhelmed by the majority.

Formal notation and definitions used to define the lifelong learning framework and graph states.

The framework also utilizes:

  • Incremental Training: We found that "warm restarts" (initializing a model with parameters from the previous time step) are significantly more effective than "cold restarts" (retraining from scratch), especially when labels are scarce. Reusing parameters provides implicit knowledge that compensates for missing historical data.
  • $k$-Neighborhood Time Difference ($tdiff_k$): To make experiments fair across different datasets, we developed this measure to calculate the distribution of time differences within a node's $k$-hop neighborhood. This allows for selecting "history sizes" that are mathematically comparable across different domains.

Key Insights and Experimental Results

The study utilized both static benchmarks (Cora, Citeseer, Pubmed) and new evolving benchmarks: PharmaBio, DBLP-easy, and DBLP-hard. DBLP-hard is particularly challenging, featuring 73 classes, 23 of which emerge dynamically over a 12-year sequence.

Major Findings:

  • Unlabeled Data is Neutral: Adding unlabeled data during training doesn't significantly boost performance for inductively pre-trained GNNs, suggesting models only need updates when new labels arrive.
  • The "50% Rule" for History: Using a history size that covers just 50% of the GNN's receptive field achieves roughly 95% of the accuracy of a model trained on the full graph.
  • OOD Detection Boost: On the DBLP-hard dataset with minimal history, gDOC achieved an out-of-distribution (OOD) detection score of 0.09, whereas the baseline DOC scored a near-random 0.01.
  • Open-F1 Score: gDOC improved the Open-F1 score (a metric combining classification accuracy and OOD detection) to 0.33, a 32% increase over the baseline DOC (0.25).

Conclusion

gDOC demonstrates that by simply weighting the loss function to account for class imbalance, GNNs become significantly better at spotting new classes in evolving environments. While this is a major step forward, future work will address the need for automated threshold tuning for OOD detection and more sophisticated memory management strategies that go beyond simple time-based history.

Summary updated

Abstract

Lifelong graph learning deals with the problem of continually adapting graph neural network (GNN) models to changes in evolving graphs. We address two critical challenges of lifelong graph learning in this work: dealing with new classes and tackling imbalanced class distributions. The combination of these two challenges is particularly relevant since newly emerging classes typically resemble only a tiny fraction of the data, adding to the already skewed class distribution. We make several contributions: First, we show that the amount of unlabeled data does not influence the results, which is an essential prerequisite for lifelong learning on a sequence of tasks. Second, we experiment with different label rates and show that our methods can perform well with only a tiny fraction of annotated nodes. Third, we propose the gDOC method to detect new classes under the constraint of having an imbalanced class distribution. The critical ingredient is a weighted binary cross-entropy loss function to account for the class imbalance. Moreover, we demonstrate combinations of gDOC with various base GNN models such as GraphSAGE, Simplified Graph Convolution, and Graph Attention Networks. Lastly, our k-neighborhood time difference measure provably normalizes the temporal changes across different graph datasets. With extensive experimentation, we find that the proposed gDOC method is consistently better than a naive adaption of DOC to graphs. Specifically, in experiments using the smallest history size, the out-of-distribution detection score of gDOC is 0.09 compared to 0.01 for DOC. Furthermore, gDOC achieves an Open-F1 score, a combined measure of in-distribution classification and out-of-distribution detection, of 0.33 compared to 0.25 of DOC (32% increase).
BibTeX
@inproceedings{galke2023lifelong,
  author = {Lukas Galke and Iacopo Vagliano and Benedikt Franke and Tobias Zielke and Ansgar Scherp and Scherp, Ansgar},
  title = {{Lifelong Learning on Evolving Graphs Under the Constraints of Imbalanced Classes and New Classes}},
  booktitle = {Neural Networks},
  year = {2023},
  url = {https://openreview.net/forum?id=6gaGAHOuzK},
}

Loading related content...

Figure