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

• URL: http://arxiv.org/abs/2112.10558v2
• Date: Tue, 9 May 2023 16:43:54 GMT
• Title: Lifelong Learning on Evolving Graphs Under the Constraints of Imbalanced Classes and New Classes
• Authors: Lukas Galke, Iacopo Vagliano, Benedikt Franke, Tobias Zielke, Marcel Hoffmann, Ansgar Scherp
• Abstract summary: We address two critical challenges of lifelong graph learning: dealing with new classes and tackling imbalanced class distributions. We show that the amount of unlabeled data does not influence the results, which is an essential prerequisite for lifelong learning. We propose the gDOC method to detect new classes under the constraint of having an imbalanced class distribution.
• Score: 2.870762512009438
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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).

Related papers

• Open-World Semi-Supervised Learning for Node Classification [53.07866559269709]
  Open-world semi-supervised learning (Open-world SSL) for node classification is a practical but under-explored problem in the graph community. We propose an IMbalance-Aware method named OpenIMA for Open-world semi-supervised node classification.
  arXiv  Detail & Related papers  (2024-03-18T05:12:54Z)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Heterophily-Based Graph Neural Network for Imbalanced Classification [19.51668009720269]
  We introduce a unique approach that tackles imbalanced classification on graphs by considering graph heterophily. We propose Fast Im-GBK, which integrates an imbalance classification strategy with heterophily-aware GNNs. Our experiments on real-world graphs demonstrate our model's superiority in classification performance and efficiency for node classification tasks.
  arXiv  Detail & Related papers  (2023-10-12T21:19:47Z)
• Certified Graph Unlearning [39.29148804411811]
  Graph-structured data is ubiquitous in practice and often processed using graph neural networks (GNNs) We introduce the first known framework for emph certified graph unlearning of GNNs. Three different types of unlearning requests need to be considered, including node feature, edge and node unlearning.
  arXiv  Detail & Related papers  (2022-06-18T07:41:10Z)
• Geometer: Graph Few-Shot Class-Incremental Learning via Prototype Representation [50.772432242082914]
  Existing graph neural network based methods mainly focus on classifying unlabeled nodes within fixed classes with abundant labeling. In this paper, we focus on this challenging but practical graph few-shot class-incremental learning (GFSCIL) problem and propose a novel method called Geometer. Instead of replacing and retraining the fully connected neural network classifer, Geometer predicts the label of a node by finding the nearest class prototype.
  arXiv  Detail & Related papers  (2022-05-27T13:02:07Z)
• Graph Neural Network with Curriculum Learning for Imbalanced Node Classification [21.085314408929058]
  Graph Neural Network (GNN) is an emerging technique for graph-based learning tasks such as node classification. In this work, we reveal the vulnerability of GNN to the imbalance of node labels. We propose a novel graph neural network framework with curriculum learning (GNN-CL) consisting of two modules.
  arXiv  Detail & Related papers  (2022-02-05T10:46:11Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Graph Classification by Mixture of Diverse Experts [67.33716357951235]
  We present GraphDIVE, a framework leveraging mixture of diverse experts for imbalanced graph classification. With a divide-and-conquer principle, GraphDIVE employs a gating network to partition an imbalanced graph dataset into several subsets. Experiments on real-world imbalanced graph datasets demonstrate the effectiveness of GraphDIVE.
  arXiv  Detail & Related papers  (2021-03-29T14:03:03Z)
• Few-Shot Learning on Graphs via Super-Classes based on Graph Spectral Measures [14.932318540666545]
  We study the problem of few shot graph classification in graph neural networks (GNNs) to recognize unseen classes, given limited labeled graph examples. We propose an approach where a probability measure is assigned to each graph based on the spectrum of the graphs normalized Laplacian.
  arXiv  Detail & Related papers  (2020-02-27T17:11:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.