GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networks

AI summary

Overview

• Research area: Graph machine learning, specifically graph prompting for adapting pre-trained Graph Neural Networks (GNNs) to downstream node classification.
• Technical level: Advanced (assumes familiarity with GNNs, message passing, and prompt-tuning concepts).
• Scope: The paper proposes and evaluates GraphTOP, the first graph prompting framework that adapts frozen pre-trained GNNs by modifying graph topology (edges) rather than node features, tested on five datasets under four pre-training strategies against six baselines.

What This Paper Is About

Graph Neural Networks are usually trained in a "pre-train, then adapt" pattern: a model is first trained on large unlabeled graphs, then adapted to a specific task such as node classification. Existing graph prompting methods do this adaptation by injecting learnable prompt vectors into node features or hidden representations, while leaving the graph's edges untouched. This paper argues that graph topology is an equally fundamental part of graph data and asks how prompting should be designed if it instead rewires the graph's edges.

Key Contributions

1. Problem formulation: The authors formulate and conduct what they describe as an initial investigation of graph prompting from the perspective of graph topology, framing it as an edge rewiring problem.
2. Algorithmic design: They propose GraphTOP, described as the first topology-oriented prompting framework, which adapts pre-trained GNNs by learning to modify the input graph's topology while keeping the pre-trained model frozen.
3. Theoretical analysis: They provide analysis based on the contextual stochastic block model (CSBM) showing that their edge rewiring design can enlarge the expected distance between class centroids, supporting improved node classification.
4. Experimental evaluation: They run experiments on five public graph datasets under four pre-training strategies, comparing against six baselines, and report that GraphTOP achieves the best performance in most cases.

Main Findings

• Topology prompting wins in most settings: On 5-shot node classification, GraphTOP records the best accuracy in the majority of dataset/pre-training combinations — for example 63.44 ± 4.21 on Cora, 68.28 ± 4.15 on PubMed, 27.43 ± 7.02 on Amazon, 68.25 ± 7.14 on Minesweeper, and 30.93 ± 9.07 on Flickr under GraphCL pre-training. The paper states GraphTOP outperforms the other baselines in 17 cases (the sentence stating the total number of cases is truncated in the available text).
• Not a clean sweep: Under SimGRACE pre-training, GraphPrompt+ reaches 51.26 ± 4.90 on Cora (bolded as best) compared with GraphTOP's 50.57 ± 2.91, and ProNoG reaches 63.03 ± 2.74 on Minesweeper (bolded) versus GraphTOP's 61.25 ± 5.08. Under LP-GraphPrompt, GraphPrompt reaches 68.16 ± 8.23 on PubMed (bolded) versus GraphTOP's 68.14 ± 5.47.
• A simple linear probe is competitive in places: The Linear Probe baseline, which only trains a classifier on top of frozen pre-trained representations, outperforms several prompting baselines on Flickr across all four pre-training strategies (for example 29.31 ± 8.91 under GraphCL and 26.78 ± 5.29 under SimGRACE).
• ProNoG is the strongest baseline: The authors identify ProNoG as a strong baseline relative to the other prompting methods, taking the runner-up position in several cases, such as on four datasets under LP-GPPT pre-training.
• Theoretical separation result: For a pre-trained 2-layer linear GCN and a graph drawn from CSBM(μ₁, μ₂, p, q) with p ≠ q, the expected Euclidean distance between class representations after GraphTOP's rewiring satisfies Dist′ = (p+q)/|p−q| · Dist > Dist.
• Low added cost: With ρ = 2, the complexity analysis concludes that computing the prompt probabilities adds O(D²d_l² + D²d_l) time, which the authors state does not introduce significant additional computation compared with the GCN itself (O(KD²d_l² + KD³d_l)).

Methodology in Plain English

• Start from the graph's edges, not its features. The prompted graph is written as G̃ = (S, X), where X is the original node features and S is a learned binary edge-selection matrix. An entry s_ij = 1 means the edge (v_i, v_j) exists in the prompted graph.
• Make discrete edge choices trainable. Because binary edge decisions are not differentiable, each edge selector is treated as a Bernoulli random variable with probability p_ij, and the objective is rewritten as an expected loss over these probabilities.
• Use Gumbel-Softmax sampling. Theorem 1 shows that Pr(G₁ − G₂ + log(p_ij/(1−p_ij)) ≥ 0) = p_ij for Gumbel(0,1) variables, giving a way to sample edges while keeping gradients flowing. The indicator is replaced by a sigmoid with a temperature parameter τ that decreases linearly during training.
• Get probabilities from a shared projector. Rather than learning every p_ij freely, a single projector m computes p_ij = σ(W₂(ReLU(W₁(h_i + h_j)))) from the frozen pre-trained node representations, where φ = {W₁, W₂}. Because h_i + h_j is symmetric, p_ij = p_ji, matching undirected graphs; the authors note concatenation could handle directed graphs.
• Constrain rewiring to local subgraphs. Instead of all node pairs, edges are rewired only between each target node and other nodes within its ρ-hop subgraph (ρ = 2 is the default), keeping other subgraph edges intact. This drops the cost from roughly O(D^{2ρ}) to O(D^ρ).
• Regularize for stable, sparse graphs. An entropy term L_E pushes each probability toward 0 or 1 so the continuous relaxation becomes tight at inference, and a sparsity term L_S keeps the average number of connected edges near a target γ. The full objective is min L_P + λ₁L_E + λ₂L_S.
• Setup used for evaluation: A 2-layer GCN with hidden size 128, a 5-shot setting, Adam with learning rate 0.005, 500 epochs, γ = 0.5, grid search over λ₁ and λ₂, and results averaged over five runs with different random seeds. Datasets are Cora, PubMed, Amazon, Minesweeper, and Flickr; pre-training strategies are GraphCL, SimGRACE, LP-GPPT, and LP-GraphPrompt.

Why This Matters

• Research impact: It opens a direction that prior graph prompting work had largely skipped — treating graph structure itself as the prompt. The CSBM analysis gives a concrete theoretical reason why rewriting local edges can separate classes, which may encourage more structure-aware prompting research rather than feature-only designs.
• Practical appeal of frozen models: Because the pre-trained GNN stays frozen and the probabilities for node representations can be precomputed, adapting to a new task requires training only a small projector and classifier, which suits resource-constrained or multi-task deployments.
• Real-world applications (graph domains named in the paper: social networks, knowledge graphs, traffic networks, and healthcare):
  • Improving node classification in social networks where labels are scarce but unlabeled structure is plentiful.
  • Adapting knowledge-graph models to new relation or entity-typing tasks without retraining the backbone.
  • Traffic networks, where sensor graphs can be rewired to reflect changing connectivity.
  • Healthcare settings, where graph models on patient or biomedical data must be adapted under limited annotation budgets.
• Industry relevance: The pre-train-once, prompt-many pattern matches how production systems often want a single large graph model serving multiple downstream tasks; topology-aware prompting suggests the graph itself can be tuned per task, complementing feature-based prompt methods.

Future Directions

• Scaling beyond local rewiring: The method restricts edge edits to ρ-hop subgraphs to keep cost manageable; whether broader or global rewiring can be made tractable is left open.
• Sensitivity to hyperparameters: The objective introduces γ, λ₁, λ₂, ρ, and a temperature schedule, with only γ = 0.5 given and λ₁/λ₂ handled by grid search — a systematic study of robustness is a natural next step.
• Extending to other tasks and graph types: The paper centers on node classification; link prediction, graph classification, and directed graphs (which would need a different integration strategy than h_i + h_j) are not evaluated.
• Interaction with stronger backbones and stronger baselines: Since results show a linear probe and ProNoG sometimes beat GraphTOP, understanding when topology prompting genuinely helps — versus when a simpler adaptation suffices — remains an open question.

Target Audience

• Graph learning researchers studying pre-training, adaptation, and prompting who want a structure-focused alternative to feature-oriented methods.
• Practitioners applying GNNs in low-label settings who need to adapt a frozen pre-trained model to new node classification tasks.
• Students and engineers with GNN background interested in the mathematical machinery of turning discrete edge decisions into a differentiable, trainable objective (Gumbel-Softmax, entropy regularization, sparsity control).
• Readers without prior exposure to graph neural networks or the "pre-train, adaptation" paradigm will find the paper's notation-heavy methodology difficult; the abstract and introduction alone are accessible.

Authors’ abstract

Graph Neural Networks (GNNs) have revolutionized the field of graph learning by learning expressive graph representations from massive graph data. As a common pattern to train powerful GNNs, the "pre-training, adaptation" scheme first pre-trains GNNs over unlabeled graph data and subsequently adapts them to specific downstream tasks. In the adaptation phase, graph prompting is an effective strategy that modifies input graph data with learnable prompts while keeping pre-trained GNN models frozen. Typically, existing graph prompting studies mainly focus on *feature-oriented* methods that apply graph prompts to node features or hidden representations. However, these studies often achieve suboptimal performance, as they consistently overlook the potential of *topology-oriented* prompting, which adapts pre-trained GNNs by modifying the graph topology. In this study, we conduct a pioneering investigation of graph prompting in terms of graph topology. We propose the first **Graph** **T**opology-**O**riented **P**rompting (GraphTOP) framework to effectively adapt pre-trained GNN models for downstream tasks. More specifically, we reformulate topology-oriented prompting as an edge rewiring problem within multi-hop local subgraphs and relax it into the continuous probability space through reparameterization while ensuring tight relaxation and preserving graph sparsity. Extensive experiments on five graph datasets under four pre-training strategies demonstrate that our proposed GraphTOP outshines six baselines on multiple node classification datasets. Our code is available at https://github.com/xbfu/GraphTOP.