Core Knowledge Learning Framework for Graph

Bowen Zhang, Zhichao Huang, Guangning Xu, Xiaomao Fan, Mingyan Xiao, Genan Dai, Hu HuangAAAI 2025 · DOI

TL;DR

This paper introduces the Core Knowledge Learning (CKL) framework, which addresses key challenges in graph classification by focusing on learning an "explanatory subgraph" – the most critical part of a graph for prediction. CKL aims to improve adaptability, scalability, and robustness in graph domain adaptation and few-shot learning tasks, demonstrating significant performance gains over existing methods.

What Problem Does This Paper Address?

Graph classification, a crucial task in machine learning with applications ranging from social network analysis to bioinformatics, faces several significant hurdles. These include:

  • Task Adaptability: Current models are often designed for specific tasks, limiting their ability to transfer knowledge to new prediction tasks.
  • Domain Shift: Models trained on one domain often perform poorly on others due to variations in data distribution. Adapting to these shifts is challenging.
  • Data Scarcity: Handling scenarios with limited labeled data, especially in few-shot learning, is difficult, further exacerbated by imbalanced data distributions.

Existing methods tend to address these challenges in isolation, leading to fragmented solutions. This paper proposes a unified framework, CKL, to tackle these issues holistically by identifying and leveraging the most informative subgraph within a larger graph.

Methods

The core innovation of CKL lies in its ability to extract an "explanatory subgraph" (Gsub) that captures the essential information for graph classification, while discarding task-irrelevant parts (Grest). This is achieved through a multi-module framework:

  1. Core Subgraph Knowledge Module: This module learns the probability of selecting both nodes and edges to form the core subgraph. It uses a GNN to obtain node embeddings, followed by MLPs to generate node and edge sampling probabilities. To handle the non-differentiable nature of direct sampling, it employs the Gumbel-softmax trick for continuous relaxation. The objective is to maximize the mutual information between the graph labels and the extracted subgraph.
  2. Graph Domain Adaptation Module: For GDA, CKL leverages the learned core subgraphs. Instead of complex domain alignment operations, it measures the similarity between source and target domain core subgraphs using the Weisfeiler-Lehman (WL) subtree kernel. The label of the most similar source subgraph is then assigned to the target graph, enabling effective domain transfer.
  3. Few-Shot Learning Module: In the few-shot learning context, CKL uses the learned core subgraph as input to a GNN classifier. It employs a bi-level optimization strategy. The inner optimization updates the parameters of the GNN classifier for a specific task using a small support set, while the outer optimization updates the parameters of the core subgraph learning module across multiple tasks to ensure generalization.

Datasets

The paper evaluates CKL on several standard graph classification datasets for graph domain adaptation, including:

  • Mutagenicity (M)
  • Tox21_AhR, FRANKENSTEIN (F)
  • PROTEINS (P) and DD (D)
  • COX2 (C) and COX2_MD (CM)
  • BZR (B) and BZR_MD (BM)

For the graph domain adaptation experiments, the Mutagenicity, Tox21, FRANKENSTEIN, and PROTEINS datasets were further partitioned into four sub-datasets based on edge density.

For few-shot learning, the experiments were conducted on widely used few-shot molecular property prediction datasets.

Key Insights and Ideas

  • Focusing on the "Core" is Key: The central idea that a small, explanatory subgraph holds the most predictive power for graph classification is a significant insight. This contrasts with traditional methods that process the entire graph, potentially diluting important signals with irrelevant information.
  • Simplifying Domain Adaptation: By aligning core subgraphs rather than entire complex graph structures, CKL offers a more efficient and potentially more robust approach to graph domain adaptation. This bypasses intricate domain alignment techniques.
  • Unified Framework for Diverse Challenges: CKL's ability to address both domain adaptation and few-shot learning with a common core subgraph extraction mechanism highlights its versatility and potential as a general-purpose graph learning component.
  • Adaptability through Subgraph Learning: The framework's design inherently promotes adaptability, as the learned core subgraph is intended to be task-agnostic, making it suitable for various downstream applications.

Key Results

  • Graph Domain Adaptation: CKL consistently outperformed state-of-the-art baselines across various datasets, showing significant improvements in accuracy. For instance, on the Mutagenicity dataset with edge density domain shifts, CKL achieved the highest average accuracy (74.9%).
  • Few-Shot Learning: CKL also demonstrated superior performance in few-shot learning tasks, achieving the highest ROC-AUC scores on multiple benchmark molecular property prediction datasets, often by a notable margin (e.g., 1.62% average improvement over the highest-performing baseline, EGNN).
  • Flexibility: Experiments showed that CKL's performance is robust when different GNN backbones (GIN, GCN, GraphSage, GMT) and graph kernels (WL subtree, Graph Sampling, Random Walk, Propagation) are used, indicating the framework's generalizability.

Limitations and Future Work

  • Computational Cost: While CKL aims for efficiency by focusing on subgraphs, the process of learning these subgraphs and performing bi-level optimization in few-shot learning can still be computationally intensive.
  • Kernel Choice: The performance of the GDA module is dependent on the chosen graph kernel (WL subtree kernel in this paper). Exploring other advanced graph kernels could potentially further enhance performance.
  • Future Directions: The authors suggest that CKL's core subgraph learning mechanism could be extended to other graph-based tasks beyond classification, such as graph regression or link prediction. Further research into more efficient subgraph extraction methods and exploring different types of core knowledge could also be beneficial.

Summary updated

BibTeX
@inproceedings{zhang2025core,
  author = {Bowen Zhang and Zhichao Huang and Guangning Xu and Xiaomao Fan and Mingyan Xiao and Genan Dai and Hu Huang},
  title = {{Core Knowledge Learning Framework for Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i12.33438},
}
Figure