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

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).

arXiv commentAccepted manuscript (after peer review, before copy-editing). Published article available at https://doi.org/10.1016/j.neunet.2023.04.022

References in corpus (20)

• Power laws, Pareto distributions and Zipf's law
• Inductive Representation Learning on Large Graphs
• Deep Learning for Anomaly Detection: A Review
• Fast Graph Representation Learning with PyTorch Geometric
• A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks
• Characterizing Concept Drift
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
• Dynamic Graph Convolutional Networks
• Generalized Out-of-Distribution Detection: A Survey
• DynGEM: Deep Embedding Method for Dynamic Graphs
• Residual Gated Graph ConvNets
• Adaptive Sampling Towards Fast Graph Representation Learning
• SIGN: Scalable Inception Graph Neural Networks
• Stochastic Training of Graph Convolutional Networks with Variance Reduction
• Graph-MLP: Node Classification without Message Passing in Graph
• Inductive Representation Learning on Temporal Graphs
• Entropic Out-of-Distribution Detection
• Learning Dynamic Embeddings from Temporal Interactions
• Can Graph Neural Networks Go "Online"? An Analysis of Pretraining and Inference

Cited by in corpus (2)

• Topology-aware Embedding Memory for Continual Learning on Expanding Networks
• Advances in Continual Graph Learning for Anti-Money Laundering Systems: A Comprehensive Review