TGNN: A Joint Semi-supervised Framework for Graph-level Classification
TGNN combines message passing and graph kernel modules with consistency loss for semi-supervised graph classification, outperforming baselines.
Key Findings
Methodology
TGNN integrates two modules: a message passing neural network (based on Kipf-Welling GCN) and a graph kernel module utilizing random walk kernels. It computes similarity distributions between unlabeled and labeled graphs in both embedding spaces, enforcing their consistency via a novel loss. Memory banks store representative labeled samples, enhanced by data augmentation strategies (edge/node/drop/subgraph). The overall training optimizes supervised cross-entropy loss combined with an unsupervised consistency loss, enabling effective semi-supervised learning of graph representations.
Key Results
- On datasets like PROTEINS, DD, IMDB-B, and REDDIT-B, TGNN surpasses state-of-the-art models with 3-4% accuracy gains, achieving 71.0% on PROTEINS and ROC-AUC of 64.1% on OGB-HIV. Performance remains strong at low label ratios (1%), demonstrating robustness in label-scarce scenarios.
- Varying labeled data ratios from 1% to 10%, TGNN consistently improves, indicating effective utilization of unlabeled data. Ablation studies confirm that combining message passing and graph kernel modules yields the best results, with data augmentation further boosting performance.
- Large-scale experiments on OGB datasets validate the scalability and generalization of TGNN, with significant margins over competitors.
Significance
This work advances graph classification by explicitly modeling structural information through dual pathways, addressing the limitations of implicit-only approaches. It effectively leverages unlabeled data, crucial for real-world applications where labels are costly. The framework's ability to incorporate high-order substructures and global topology enhances interpretability and accuracy, impacting fields like bioinformatics, social network analysis, and cheminformatics. It sets a new standard for semi-supervised graph learning, bridging the gap between theory and practice.
Technical Contribution
TGNN introduces a dual-module architecture combining implicit message passing and explicit graph kernel comparison, linked via a novel consistency loss. The use of a memory bank for representative samples and data augmentation strategies enhances robustness. The framework enables joint learning of structural features in different embedding spaces, providing theoretical guarantees of consistency and improved generalization. This design opens new avenues for integrating structural priors into semi-supervised graph models.
Novelty
First to incorporate a graph kernel module based on random walk similarity into a semi-supervised GNN framework, explicitly capturing high-order structural features. The cross-module similarity consistency loss facilitates mutual learning, a novel approach in graph classification. Unlike prior works relying solely on implicit message passing or contrastive methods, this framework explicitly models and aligns structural similarities, leading to superior performance.
Limitations
- Despite improvements, performance drops in extremely low-label regimes (e.g., 1%) due to limited structural cues. Computational complexity increases with larger graphs and more hidden graphs, requiring optimization.
- The current design relies on hyperparameters like random walk length and number of hidden graphs, which need careful tuning. Handling very large graphs efficiently remains challenging.
- Capturing complex high-order structures beyond random walks, such as motifs or subgraphs, could further improve results but is not addressed here.
Future Work
Future directions include integrating multi-scale structural features, employing self-supervised pretraining to reduce label dependency, and optimizing computational efficiency for large graphs. Extending the framework to dynamic or heterogeneous graphs and exploring more expressive kernels could further enhance its applicability and robustness.
AI Executive Summary
Graph-structured data permeate many domains, from social networks to molecular chemistry. Traditional graph neural networks (GNNs), such as Kipf-Welling's GCN and Veličković's GAT, have achieved remarkable success in node and edge tasks. However, graph classification—determining the overall category of an entire graph—remains challenging, especially under limited labeled data. Existing methods often rely solely on local neighborhood aggregation, which inadequately captures the rich global and high-order structural information inherent in complex graphs.
To address these limitations, this paper introduces TGNN, a novel semi-supervised framework that synergistically combines message passing and graph kernel techniques. The message passing module, based on GNN principles, learns node embeddings by aggregating neighbor information, implicitly encoding local topology. Complementarily, the graph kernel module employs a random walk kernel to explicitly compare graph structures, capturing high-order substructures and global topology. These two modules operate in parallel, exchanging similarity information through a carefully designed consistency loss, which aligns their similarity distributions in different embedding spaces.
The framework leverages a memory bank of labeled samples, augmented via strategies like edge, node, attribute, and subgraph perturbations, to enhance robustness and diversity. During training, the similarity distributions between unlabeled graphs and the stored labeled anchors are computed in both modules, and the consistency loss encourages these distributions to agree, effectively propagating structural information from labeled to unlabeled data. The overall objective combines supervised classification loss with this unsupervised consistency term, enabling TGNN to learn discriminative graph representations even with scarce labels.
Extensive experiments on datasets such as PROTEINS, DD, IMDB-B, and large-scale OGB benchmarks demonstrate TGNN's superior performance, with accuracy improvements of 3-4% over state-of-the-art models. Notably, TGNN maintains high accuracy at low label ratios (1%), showcasing its ability to leverage unlabeled data effectively. Ablation studies confirm that the combination of modules and data augmentation strategies significantly boosts results, validating the design choices.
This work marks a significant step forward in graph classification, providing a robust, interpretable, and scalable approach that explicitly models structural features. Its implications extend to numerous applications, including drug discovery, social network analysis, and bioinformatics, where labeled data is limited but structural information is abundant. Future research will explore multi-scale features, more efficient kernels, and pretraining techniques to further enhance the framework's capabilities and real-world impact.
Deep Dive
Plain Language Accessible to non-experts
想象你在管理一个大型工厂，工厂里有很多机器（代表节点）和它们之间的连接（代表边）。传统的管理方式只关注每台机器的状态，比如温度或速度，但忽略了它们之间的关系和整体布局。TGNN就像用两种不同的眼睛来看这个工厂：一种是观察每台机器和它的邻居（消息传递），另一种是用特殊的放大镜（图核）比较不同工厂的整体布局。通过让这两只眼睛互相学习，工厂管理者可以更全面地理解整个工厂的运作情况。这样，即使只看到少量工厂样本，也能学到很多关于工厂结构的知识，从而更准确地判断工厂的类型或状态。这就像用两种不同的视角观察一个复杂的系统，最终获得更清晰、更全面的理解。
ELI14 Explained like you're 14
想象你在玩一个超级复杂的拼图游戏，每个拼图块代表一个节点，拼图的整体形状代表整个图。传统的方法就像只看每个拼图块的颜色（节点信息），但忽略了拼图块之间的连接方式。TGNN就像用两只眼睛：一只看每个拼图块和它周围的邻居（消息传递），另一只用特殊的放大镜（图核）来比较不同拼图的整体结构。通过让这两只眼睛互相学习，拼图的整体形状就能更清楚地被理解。即使你只有少量拼图样本，也能通过这种方法学到很多拼图的规律，从而更快找到正确的拼图组合。这样一来，拼图游戏变得更容易，也更有趣！
Abstract
This paper studies semi-supervised graph classification, a crucial task with a wide range of applications in social network analysis and bioinformatics. Recent works typically adopt graph neural networks to learn graph-level representations for classification, failing to explicitly leverage features derived from graph topology (e.g., paths). Moreover, when labeled data is scarce, these methods are far from satisfactory due to their insufficient topology exploration of unlabeled data. We address the challenge by proposing a novel semi-supervised framework called Twin Graph Neural Network (TGNN). To explore graph structural information from complementary views, our TGNN has a message passing module and a graph kernel module. To fully utilize unlabeled data, for each module, we calculate the similarity of each unlabeled graph to other labeled graphs in the memory bank and our consistency loss encourages consistency between two similarity distributions in different embedding spaces. The two twin modules collaborate with each other by exchanging instance similarity knowledge to fully explore the structure information of both labeled and unlabeled data. We evaluate our TGNN on various public datasets and show that it achieves strong performance.