Mastering Long-Tail Complexity on Graphs: Characterization, Learning, and Generalization

• URL: http://arxiv.org/abs/2305.09938v4
• Date: Fri, 31 May 2024 17:02:37 GMT
• Title: Mastering Long-Tail Complexity on Graphs: Characterization, Learning, and Generalization
• Authors: Haohui Wang, Baoyu Jing, Kaize Ding, Yada Zhu, Wei Cheng, Si Zhang, Yonghui Fan, Liqing Zhang, Dawei Zhou,
• Abstract summary: We propose a generalization bound for long-tail classification on graphs by formulating the problem in the fashion of multi-task learning. Our theoretical results show that the generalization performance of long-tail classification is dominated by the overall loss range and the task complexity. Building upon the theoretical findings, we propose a novel generic framework HierTail for long-tail classification on graphs.
• Score: 33.89914557812127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the context of long-tail classification on graphs, the vast majority of existing work primarily revolves around the development of model debiasing strategies, intending to mitigate class imbalances and enhance the overall performance. Despite the notable success, there is very limited literature that provides a theoretical tool for characterizing the behaviors of long-tail classes in graphs and gaining insight into generalization performance in real-world scenarios. To bridge this gap, we propose a generalization bound for long-tail classification on graphs by formulating the problem in the fashion of multi-task learning, i.e., each task corresponds to the prediction of one particular class. Our theoretical results show that the generalization performance of long-tail classification is dominated by the overall loss range and the task complexity. Building upon the theoretical findings, we propose a novel generic framework HierTail for long-tail classification on graphs. In particular, we start with a hierarchical task grouping module that allows us to assign related tasks into hypertasks and thus control the complexity of the task space; then, we further design a balanced contrastive learning module to adaptively balance the gradients of both head and tail classes to control the loss range across all tasks in a unified fashion. Extensive experiments demonstrate the effectiveness of HierTail in characterizing long-tail classes on real graphs, which achieves up to 12.9% improvement over the leading baseline method in accuracy.

Related papers

• Core Knowledge Learning Framework for Graph Adaptation and Scalability Learning [7.239264041183283]
  Graph classification faces several hurdles, including adapting to diverse prediction tasks, training across multiple target domains, and handling small-sample prediction scenarios. By incorporating insights from various types of tasks, our method aims to enhance adaptability, scalability, and generalizability in graph classification. Experimental results demonstrate significant performance enhancements achieved by our method compared to state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-07-02T02:16:43Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Graph Learning under Distribution Shifts: A Comprehensive Survey on Domain Adaptation, Out-of-distribution, and Continual Learning [53.81365215811222]
  We provide a review and summary of the latest approaches, strategies, and insights that address distribution shifts within the context of graph learning. We categorize existing graph learning methods into several essential scenarios, including graph domain adaptation learning, graph out-of-distribution learning, and graph continual learning. We discuss the potential applications and future directions for graph learning under distribution shifts with a systematic analysis of the current state in this field.
  arXiv  Detail & Related papers  (2024-02-26T07:52:40Z)
• Towards Long-Tailed Recognition for Graph Classification via Collaborative Experts [10.99232053983369]
  We propose a novel long-tailed graph-level classification framework via Collaborative Multi-expert Learning (CoMe) To equilibrate the contributions of head and tail classes, we first develop balanced contrastive learning from the view of representation learning. We execute gated fusion and disentangled knowledge distillation among the multiple experts to promote the collaboration in a multi-expert framework.
  arXiv  Detail & Related papers  (2023-08-31T10:12:32Z)
• RAHNet: Retrieval Augmented Hybrid Network for Long-tailed Graph Classification [10.806893809269074]
  We propose a novel framework called Retrieval Augmented Hybrid Network (RAHNet) to jointly learn a robust feature extractor and an unbiased classifier. In the feature extractor training stage, we develop a graph retrieval module to search for relevant graphs that directly enrich the intra-class diversity for the tail classes. We also innovatively optimize a category-centered supervised contrastive loss to obtain discriminative representations.
  arXiv  Detail & Related papers  (2023-08-04T14:06:44Z)
• Unsupervised Task Graph Generation from Instructional Video Transcripts [53.54435048879365]
  We consider a setting where text transcripts of instructional videos performing a real-world activity are provided. The goal is to identify the key steps relevant to the task as well as the dependency relationship between these key steps. We propose a novel task graph generation approach that combines the reasoning capabilities of instruction-tuned language models along with clustering and ranking components.
  arXiv  Detail & Related papers  (2023-02-17T22:50:08Z)
• CrossCodeBench: Benchmarking Cross-Task Generalization of Source Code Models [33.78307982736911]
  Cross-task generalization is of strong research and application value. We propose a large-scale benchmark that includes 216 existing code-related tasks.
  arXiv  Detail & Related papers  (2023-02-08T13:04:52Z)
• Association Graph Learning for Multi-Task Classification with Category Shifts [68.58829338426712]
  We focus on multi-task classification, where related classification tasks share the same label space and are learned simultaneously. We learn an association graph to transfer knowledge among tasks for missing classes. Our method consistently performs better than representative baselines.
  arXiv  Detail & Related papers  (2022-10-10T12:37:41Z)
• FAITH: Few-Shot Graph Classification with Hierarchical Task Graphs [39.576675425158754]
  Few-shot graph classification aims at predicting classes for graphs, given limited labeled graphs for each class. We propose a novel few-shot learning framework FAITH that captures task correlations via constructing a hierarchical task graph. Experiments on four prevalent few-shot graph classification datasets demonstrate the superiority of FAITH over other state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-05-05T04:28:32Z)
• 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)
• Model-Agnostic Graph Regularization for Few-Shot Learning [60.64531995451357]
  We present a comprehensive study on graph embedded few-shot learning. We introduce a graph regularization approach that allows a deeper understanding of the impact of incorporating graph information between labels. Our approach improves the performance of strong base learners by up to 2% on Mini-ImageNet and 6.7% on ImageNet-FS.
  arXiv  Detail & Related papers  (2021-02-14T05:28:13Z)

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.