TLDR: SamGoG is a novel sampling-based Graph-of-Graphs (GoG) framework designed to overcome the challenges of class and graph size imbalance in graph classification. It achieves state-of-the-art accuracy and significant training acceleration by employing a learnable pairwise graph similarity function, adaptive GoG node degree allocation, and dynamic sampling, ensuring better performance on underrepresented classes and graph sizes.
Graph Neural Networks (GNNs) have emerged as powerful tools for understanding and classifying complex graph structures, finding applications in diverse fields like social network analysis and bioinformatics. These networks excel at capturing both the structural relationships and feature-based information within graphs, leading to remarkable success in various tasks.
The Challenge of Imbalanced Graph Data
Despite their capabilities, GNNs face significant hurdles when dealing with real-world graph data that often exhibits two critical forms of imbalance: class imbalance and graph size imbalance. Class imbalance occurs when some categories of graphs have far fewer training examples than others, leading GNNs to become biased towards the majority classes and perform poorly on the underrepresented ones. Graph size imbalance, on the other hand, refers to situations where input graphs vary substantially in their number of nodes (size). This can impair performance on smaller graphs and hinder the model’s ability to generalize across different graph sizes.
Existing methods typically address only one type of imbalance or come with high computational costs, making them less practical for large-scale applications. This highlights a pressing need for a more comprehensive and efficient solution.
Introducing SamGoG: A Novel Framework
To tackle these challenges, researchers have proposed SamGoG, a sampling-based Graph-of-Graphs (GoG) learning framework. SamGoG is designed to effectively mitigate both class and graph size imbalances simultaneously, offering a significant leap forward in imbalanced graph classification. The core idea behind GoG is to represent each input graph as a node in a higher-level graph, with connections (edges) between these GoG nodes defined by the similarity between the original input graphs. This inter-graph representation allows for richer supervision, especially for minority-class or small graphs, by embedding them within a broader context of similar graphs.
How SamGoG Works
SamGoG constructs multiple GoGs through an efficient, importance-based sampling mechanism. Instead of building a single, static GoG, it dynamically generates several GoGs during training. This sampling process is guided by several innovative components:
-
Learnable Pairwise Graph Similarity: Unlike traditional GoG methods that rely on computationally expensive graph kernels to measure similarity, SamGoG employs a learnable function. This function jointly encodes both structural and semantic features, allowing it to more accurately capture relationships between graphs and prioritize connections between graphs of the same class.
-
Adaptive GoG Node Degree Allocation: Instead of assigning a fixed number of neighbors to each GoG node, SamGoG adaptively adjusts the neighborhood size for each node. This is done using three smart rules that consider whether a graph is labeled or unlabeled, if it belongs to a majority or minority class, and its size relative to the training data distribution. This adaptive allocation ensures that graphs with higher ‘homophily probability’ (likelihood of connecting to same-label neighbors) are assigned more connections, thereby improving the overall quality of the GoG structure.
-
Dynamic and Parallel Sampling: SamGoG replaces the traditional one-shot GoG construction with a dynamic and parallel sampling method. This allows the framework to generate multiple GoGs throughout the training process, capturing a wider range of graph-level interactions and reducing inductive biases.
Also Read:
- EAGLE: A Faster, More Accurate Way to Predict Links in Evolving Graphs
- Optimizing Reinforcement Learning with Diminishing Returns: A New Approach Using Pruned Submodularity Graphs
Breakthrough Results
Extensive experiments on benchmark datasets demonstrate that SamGoG achieves state-of-the-art performance. It has shown an average accuracy increase of 5.07% in class imbalance experiments and 4.13% in graph size imbalance experiments. Notably, SamGoG can achieve up to a 15.66% accuracy improvement while accelerating training by up to 6.7 times. It also significantly improves classification performance on both minority classes and tail-size graphs, which are typically challenging for GNNs.
Furthermore, SamGoG dramatically reduces the time needed for pairwise graph similarity computation, completing tasks in milliseconds compared to seconds or minutes for older kernel-based methods. This efficiency makes it highly scalable for large-scale graph datasets, such as ogbg-molhiv, where it maintains superior accuracy and Macro-F1 scores with minimal preprocessing overhead.
SamGoG represents a significant advancement in addressing the critical issues of class and graph size imbalance in graph classification, offering a robust, accurate, and highly efficient framework for real-world applications. You can read the full research paper here.
