TL;DR
This paper introduces HeterGP, a novel graph prompt-tuning method designed to effectively handle graph neural networks (GNNs) in scenarios with high graph heterogeneity (where neighboring nodes often have different features or belong to different categories). By employing a multi-view approach that captures both homophilic and heterophilic information, HeterGP significantly improves performance on downstream tasks, especially in few-shot learning settings.
What Problem Does This Paper Address?
Graph Neural Networks (GNNs) are powerful tools for analyzing graph-structured data, but they often struggle with real-world graphs that exhibit high heterogeneity. Traditional GNNs and even recent prompt-tuning methods often assume graph homophily (where connected nodes are similar), which limits their effectiveness in heterophilic environments. Furthermore, training GNNs typically requires a large amount of labeled data, which is often scarce. Prompt-tuning methods aim to bridge this gap by adapting pre-trained GNNs to downstream tasks with limited labels, but existing approaches often fail to adequately address the challenges posed by heterophily. This paper tackles the problem of adapting GNNs to downstream tasks in a few-shot setting, specifically for graphs with high heterogeneity, by proposing a new prompt-tuning strategy.
Methods
The core of HeterGP lies in its multi-view prompting strategy. Instead of relying on a single type of information, HeterGP extracts two distinct perspectives:
- Homophilic View: This view captures information similar to traditional methods, focusing on local neighborhood structures.
- Heterophilic View: This view is specifically designed to capture information from nodes that are dissimilar but connected, which is crucial for heterophilic graphs.
To achieve this, HeterGP employs a Path Extractor & Subgraph Reformer module that uses a modified random walk (inspired by Node2Vec) with parameters p and q. This allows for controlled exploration:
- BFS-like behavior (p < 1, q > 1): Captures homophilic information by staying close to the starting node.
- DFS-like behavior (p > 1, q < 1): Captures heterophilic information by exploring further away from the starting node.
These two views generate separate subgraphs. The Prompt Graph Generator then creates prompt tokens for each subgraph. Crucially, the connections within the prompt tokens and between the prompt tokens and the subgraph nodes are designed differently for homophilic and heterophilic views, using distinct similarity thresholds. Finally, an Attention-based Classifier merges the representations from both views to make the final prediction.
Datasets
The paper evaluates HeterGP on a variety of real-world datasets for both Node Classification (NC) and Graph Classification (GC) tasks.
Node Classification Datasets: * Homophilic: Cora, CiteSeer, PubMed * Heterophilic: Texas, Wisconsin, Actor, Chameleon, Squirrel
Graph Classification Datasets: * ENZYMES, PROTEINS, MUTAG, COX2, BZR
The paper also calculates the "label-defined edge homophily ratio" (L.H.R.) for each dataset to quantify its homophily/heterophily level.
Key Insights and Ideas
- Heterophily is a critical challenge: Existing prompt-tuning methods, while effective for homophilic graphs, fall short when faced with high heterogeneity.
- Multi-view prompting is key: Capturing both homophilic and heterophilic information simultaneously is essential for robust performance in diverse graph settings.
- Controlled random walks for information extraction: The use of
pandqparameters in random walks provides a flexible way to balance exploring local (homophilic) vs. distant (heterophilic) neighbors. - Tailored prompt design for each view: Separate prompt graph generation and connection strategies for homophilic and heterophilic views allow for better adaptation to the specific characteristics of each information type.
- Prompt tuning shines in few-shot settings: The paper demonstrates that prompt-tuning, especially with HeterGP, significantly outperforms traditional GNNs and fine-tuning approaches when labeled data is scarce.
Key Results
- HeterGP consistently outperforms baseline methods on heterophilic datasets for node classification, especially in few-shot scenarios.
- In node classification, HeterGP achieves the best performance on 19 out of 25 settings and excels in 21 cases when comparing prompt categories.
- For graph classification, HeterGP performs comparably to or better than traditional GNNs and shows significant improvements over the "All-in-One" approach, particularly on ENZYMES and BZR datasets.
- The ablation study confirms that both the homophilic and heterophilic prompt components are crucial for HeterGP's effectiveness.
- The number of prompt tokens has a diminishing return effect, suggesting that a small number is sufficient for good performance.
Limitations and Future Work
- Homophily assumption in traditional GNNs: The paper notes that even some pre-training methods and prompt-tuning approaches implicitly rely on homophily assumptions, which HeterGP aims to overcome.
- Dataset size and characteristics in GC: For graph classification, the performance improvement with more samples was not as consistent as in node classification, suggesting that dataset size and specific characteristics play a significant role.
- Future work directions: The authors suggest exploring the adaptability and robustness of prompt tuning on more complex graph structures, including those with evolving dynamics. They also propose incorporating domain-specific knowledge into prompt design as a promising avenue.
Summary updated