Imbalanced Graph Classification via Graph Similarity Learning

Graph classification is a fundamental task prevalent in fields such as molecular property prediction, bioinformatics, and social network analysis. However, real-world graph datasets suffer from severe graph size imbalance, which under limited label supervision induces size-driven similarity bias and semantic misalignment, resulting in significant performance gaps across size groups. In response, we propose a unified graph similarity-based learning framework **SimGraph** integrating balanced pairwise graph similarity (BPGS) learning and size-adaptive instance normalization (SAIN): BPGS formulates similarity estimation as pairwise binary classification with an asymmetric scaling scheme and a learnable decision boundary, while SAIN suppresses size-related variations in graph representations. We characterize the design-motivated properties of SimGraph, including its false-negative-free pairwise construction and bounded gradients, which provide principled support for stable optimization under size-imbalanced graph distributions. Extensive experiments on binary and multi-class benchmarks spanning molecular, biological, social, and heterogeneous graphs demonstrate that SimGraph achieves state-of-the-art performance on imbalanced graph classification with limited labels, with an average accuracy improvement of **4.2%** in size-imbalanced settings and up to **13%** on individual datasets.