Lifelong learning on evolving graphs under the constraints of imbalanced classes and new classes

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

TL;DR

This paper introduces gDOC, a novel framework for lifelong learning on evolving graphs that simultaneously tackles class imbalance and the detection of newly emerging classes. By combining an incremental training procedure with a weighted binary cross-entropy loss, the authors demonstrate that models can adapt to new data without forgetting the old, even when new classes are rare and labeled data is scarce.

What Problem Does This Paper Address?

Most Graph Neural Networks (GNNs) are trained on static snapshots, but real-world graphs—like citation networks or social media—are living organisms. They evolve. 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 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."

The authors aim to bridge the gap between lifelong learning (adapting over time) and open-world learning (detecting the unknown) specifically for graph-structured data.

Methods

The authors propose a multi-pronged approach to handle graph evolution:

  • Incremental Training: They compare "warm restarts" (initializing a model with parameters from the previous time step) against "cold restarts" (training from scratch).
  • gDOC (Graph Deep Open Classification): This is the paper's primary contribution. It adapts the DOC algorithm (originally for text) to graphs. Instead of a standard softmax output, gDOC uses an element-wise sigmoid activation. 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.
  • $k$-Neighborhood Time Difference ($tdiff_k$): To make experiments fair across different datasets (e.g., one graph might evolve daily, another yearly), they developed this measure. It calculates the distribution of time differences within a node's $k$-hop neighborhood, allowing researchers to select "history sizes" that are mathematically comparable across different domains.

Datasets

The study utilizes two categories of datasets:

  • Static Benchmarks: Cora, Citeseer, and Pubmed. These were used to test the impact of unlabeled data and the difference between transductive and inductive learning.
  • Evolving Benchmarks: The authors contributed three datasets specifically for lifelong learning: PharmaBio (co-authorship), DBLP-easy, and DBLP-hard (citation networks).
  • DBLP-hard is particularly challenging, featuring 73 classes, 23 of which emerge dynamically over a 12-year sequence.

Key Insights and Ideas

  • Unlabeled Data is Neutral: Surprisingly, adding unlabeled data during training doesn't significantly boost performance for inductively pre-trained GNNs. This is a win for lifelong learning, as it suggests models only need to be updated when new labels arrive.
  • The "50% Rule" for History: You don't need the entire history of a graph to perform well. Using a history size that covers just 50% of the GNN's receptive field (the $k$-hop neighborhood) achieves roughly 95% of the accuracy of a model trained on the full graph.
  • Warm Restarts are Essential: Reusing parameters from previous tasks (warm restarts) is significantly more effective than retraining from scratch, especially when history is limited or the label rate is low. It provides a form of "implicit knowledge" that compensates for missing "explicit" historical data.
  • Weighting is the Key to OOD: A naive adaptation of OOD (Out-of-Distribution) detection to graphs fails because of class skew. By simply weighting the loss function to account for imbalance, the model becomes much better at spotting new classes.

Key Results

  • OOD Detection Boost: On the DBLP-hard dataset with minimal history, gDOC achieved an OOD detection score (measured by MCC) 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).
  • Robustness to Label Scarcity: The authors showed that the benefits of warm restarts become even more pronounced as the "label rate" (the percentage of known node labels) drops, making the approach highly suitable for real-world scenarios where labeling is expensive.

Limitations and Future Work

While gDOC is a significant step forward, the authors note a few areas for improvement:

  • Threshold Tuning: Currently, the model requires a "crisp" decision threshold for OOD detection. In practice, tuning this threshold usually requires a validation set containing "known unknowns," which isn't always available in a true lifelong learning scenario.
  • Memory Management: The current "history" is based purely on time. Future work could explore more sophisticated "memory" budgets—for example, keeping nodes with high centrality or "bridge" nodes that connect different parts of the graph, regardless of their age.
  • Loss Functions: The authors suggest exploring other OOD-specific loss functions, such as IsoMax, to see if they can further improve the separation between known and unknown classes in the graph embedding space.

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 Marcel Hoffmann and Ansgar Scherp},
  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