State of the Art and Potentialities of Graph-level Learning

Graph-structured data has been studied since the 18th century, exemplified by the Königsberg bridge problem. With advances in molecular biology, neuroscience, and social network analysis, graphs have become essential for modeling complex relationships. Traditional methods like graph kernels (e.g., Weisfeiler-Lehman, shortest path) and substructure mining (e.g., gSpan, AGM) provided initial tools for graph comparison and classification. However, these approaches faced limitations in scalability and feature expressiveness. The emergence of deep learning, particularly graph neural networks (GNNs) such as GCN, GAT, and Graph Isomorphism Network (GIN), enabled automatic learning of node and graph representations, significantly improving performance on tasks like molecular property prediction, protein classification, and social network analysis. Hierarchical pooling methods like DiffPool further enhanced the ability to capture multi-scale structural information. Despite these advances, challenges in interpretability, scalability, and transferability persist, motivating ongoing research to develop more robust, explainable, and scalable graph models.

The core challenge in graph-level learning is to develop models that can effectively capture the complex, irregular, and large-scale structures of graphs for tasks such as classification, regression, and similarity measurement. Traditional methods rely on handcrafted features and kernel functions, which are computationally intensive and limited in expressiveness. Deep models, while powerful, often lack interpretability and require substantial computational resources, especially for large graphs. Moreover, existing methods struggle with heterogeneous and multi-modal data, as well as transferability across domains. Addressing these issues is crucial for deploying graph learning in real-world applications like drug discovery, brain network analysis, and social media understanding, where data complexity and scale are significant hurdles.

The paper introduces a unified taxonomy that systematically categorizes graph-level learning methods, emphasizing their evolution and interconnections. It highlights the integration of traditional kernel/substructure techniques with modern deep GNNs and pooling strategies, fostering a holistic understanding. Key innovations include the detailed comparison of algorithms, the identification of interaction pathways between methods, and the proposal of 12 future research directions such as multi-modal fusion, explainability, and scalable architectures. This framework facilitates a comprehensive understanding of the field, guiding future innovations and practical deployments.

• �� Traditional kernel methods (e.g., Random Walk Kernel, Shortest Path Kernel) compute graph similarity via predefined measures, feeding kernel matrices into classifiers like SVM.
• �� Substructure mining algorithms (e.g., gSpan, AGM) extract frequent subgraphs as features for supervised learning.
• �� Graph embedding techniques (e.g., Graph2Vec, Graphlet) convert graphs into low-dimensional vector spaces, enabling scalable learning.
• �� Deep GNNs (e.g., GCN, GAT, GIN) perform message passing, aggregating neighborhood information to learn node and graph representations.
• �� Hierarchical pooling methods (e.g., DiffPool, Hierarchical Pooling) compress graph structures into coarser representations, preserving hierarchical information.
• �� Hybrid models combine these techniques, leveraging their respective strengths for improved performance and robustness.

The evaluation uses datasets like MUTAG, PROTEINS, and ogbn-products, focusing on classification and regression tasks. Metrics include accuracy, F1 score, and mean absolute error. Hyperparameters are tuned via cross-validation. Ablation studies assess the contribution of each component, such as pooling layers or specific kernels. Results show deep GNNs outperform traditional kernels by about 10%, with hierarchical pooling boosting accuracy on large datasets. The experiments validate the effectiveness of the proposed taxonomy and highlight the importance of method fusion for optimal performance.

Deep GNNs like GIN achieved over 85% accuracy on QM9, surpassing traditional kernel methods by approximately 10%. Hierarchical pooling techniques like DiffPool improved F1 scores on large datasets like ogbn-products to 92%. Hybrid models combining kernel methods and deep GNNs reached 88% accuracy in protein classification, demonstrating the benefit of multi-technique integration. These results confirm the superiority of deep models in handling complex, large-scale graphs, and highlight the significance of pooling strategies for capturing hierarchical structures.

Graph-level learning is vital in drug discovery (predicting molecular activity), bioinformatics (protein function classification), social network analysis (community detection, user behavior prediction), and recommendation systems. These applications require models that can handle large, heterogeneous, and multi-modal data, providing accurate and interpretable insights. The developed techniques enable industry practitioners to automate complex analysis tasks, accelerate discovery processes, and improve decision-making efficiency.

Current methods face scalability issues with very large or heterogeneous graphs, often requiring high computational resources. Deep models lack transparency, limiting their adoption in sensitive domains like healthcare. Transfer learning across different graph domains remains underdeveloped, restricting model generalization. Future work must address these challenges by improving efficiency, interpretability, and cross-domain adaptability.