Lifelong Learning in Evolving Graphs with Limited Labeled Data and Unseen Class Detection

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

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

In real-world applications, graphs such as citation networks or social media platforms are dynamic entities. They evolve continuously as new users join, new topics emerge, and relationships shift. Most Graph Neural Network (GNN) research assumes a static environment with a fixed set of classes. However, in a "lifelong learning" scenario, a model must adapt to new classes while navigating two major hurdles: severe class imbalance and the emergence of previously unseen categories. Newly emerging classes often start with very few examples, making them difficult to distinguish from noise or existing data. This paper focuses on forward transfer—the ability of a model to detect and adapt to the next task in a sequence without requiring a full retrain from scratch.

The gDOC Framework

To address the challenge of detecting unseen classes in imbalanced graph data, the authors introduce gDOC (graph Deep Open Classification). This method adapts the Deep Open Classification (DOC) approach, originally used in text processing, for graph structures.

Unlike standard GNNs that use a Softmax output layer (which forces every node into a known category), gDOC employs element-wise Sigmoid activations. The core innovation is a weighted binary cross-entropy loss function. By penalizing errors more heavily for rare classes, gDOC allows the model to define more precise boundaries for "known" data, making it significantly more effective at identifying out-of-distribution (OOD) nodes.

Temporal Dynamics and History Selection

A critical aspect of lifelong learning is determining how much historical data is necessary to maintain performance. The authors developed the $k$-Neighborhood Time Difference ($tdiff_k$) measure to normalize temporal changes across diverse datasets, such as fast-moving social networks versus slower citation graphs.

Temporal task setup for lifelong graph learning

As illustrated in the figure above, the model is trained on a sliding window of past tasks (the history) to evaluate performance on the current task $t$. The research found that keeping a history size covering only 50% to 75% of the GNN's receptive field is sufficient to reach 95-99% of the accuracy achievable with the entire graph history. This significantly reduces the computational burden of maintaining massive historical datasets.

Key Insights and Experimental Results

The study yielded several surprising and impactful findings:

  • Unlabeled Data Impact: Adding unlabeled data during training does not significantly improve performance for inductively trained GNNs. This suggests that models only need updates when new labeled data arrives, simplifying the lifelong learning pipeline.
  • Parameter Reuse: "Warm restarts" (initializing a new task with weights from the previous task) consistently outperformed "cold restarts" (training from scratch), particularly when labels were scarce. Reusing weights acts as implicit knowledge that accelerates convergence.
  • OOD Detection Performance: On the challenging DBLP-hard dataset, gDOC achieved an Open-F1 score of 0.33, representing a 32% increase over the naive DOC adaptation (0.25). In highly constrained settings with minimal history, gDOC's OOD detection score was 0.09, compared to just 0.01 for the baseline.

Conclusion and Future Work

The gDOC method provides a robust framework for lifelong learning on evolving graphs, effectively handling both class imbalance and the emergence of new categories. While the current implementation relies on a manually tuned threshold (0.75), future research may explore automated thresholding and more sophisticated memory management techniques, such as prioritizing nodes with high centrality for the training history. Additionally, exploring how to "shrink" models by removing obsolete classes remains an open area for future investigation.

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},
  title = {{Lifelong Learning in Evolving Graphs with Limited Labeled Data and Unseen Class Detection}},
  booktitle = {Neural Networks},
  year = {2023},
  url = {https://openreview.net/forum?id=6gaGAHOuzK},
}
Figure