Where to Find Fascinating Inter-Graph Supervision: Imbalanced Graph Classification with Kernel Information Bottleneck

Imbalanced graph classification is ubiquitous yet challenging in many real-world applications. Existing methods typically follow the same convention of treating graph instances as discrete individuals and exploit graph neural networks (GNNs) to predict graph labels. Despite their success, they only propagate intra-graph information within a single graph while disregarding extra supervision globally derived from other graphs. In fact, the inter-graph learning plays a vital role in providing more supervision for minority graphs. However, it is disadvantageous to accurately derive reliable inter-graph supervision because the redundancy information from majority graphs is introduced to obscure the representations of minority graphs during the propagation process. To tackle this issue, we propose a novel method that integrates the restricted random walk kernel with the global graph information bottleneck (GIB) to improve imbalanced graph classification. Specifically, the restricted random walk kernel is proposed to perform the inter-graph learning with learnable graph filters and produce kernel outputs. To ensure that the redundant information of majority graphs does not plague kernel outputs, we model the entire kernel learning as a Markovian decision process and employ the global GIB manner to optimize it. Extensive experiments on real-world graph benchmark datasets verify the competitive performance of the proposed method.