PreGress: Ranking-Native Pre-training and Prompting for Graph Node Ranking

PreGress is the first ranking-native pre-training and prompting framework for supporting a wide range of node ranking tasks. It addresses the limitations of existing GNN-based ranking methods, which are typically tailored to individual ranking criteria and require retraining for each downstream task, and recent graph pre-training approaches, whose learning objectives are largely misaligned with node ranking. PreGress performs multi-task pre-training using carefully designed objectives, including degree centrality prediction and attribute reconstruction, to jointly capture structural and attribute information. To support heterogeneous ranking criteria, it designs lightweight, task-specific prompt modules that adapt a frozen ranking backbone to downstream tasks without full retraining. Experiments on six public graphs and two real-world query-to-item benchmarks—Yelp2018 and MovieLens-100K—together with a controlled five-criterion graph-access study demonstrate strong ranking quality with low task-specific state overhead.

The framework consists of three stages: ego network extraction, multi-task pre-training, and task-specific prompt tuning. In the ego network extraction stage, the data graph is divided into multiple k-hop ego networks, and a subgraph neural network is used as the pre-training model to focus node representations on local information and mitigate over-smoothing issues common in vanilla GNNs. In the multi-task pre-training stage, degree centrality prediction is adopted as a pre-training task because it provides continuous output values and uses easily obtainable ground-truth labels—the degrees of nodes—aligning with continuous-output downstream ranking tasks and supporting large-scale pre-training. Node attribute reconstruction is employed as an auxiliary task to capture intrinsic relationships among node properties. The pre-training loss combines degree centrality prediction, using both pointwise score regression and a listwise distribution-matching regularizer, and masked attribute reconstruction, using an InfoNCE objective. In the task-specific prompt tuning stage, for betweenness centrality tasks, a simple learnable vector is used as the prompt function to adjust graph representations; for local subgraph counting tasks, a graph neural network is incorporated to learn prompts based on pattern graphs, with soft canonical correlation analysis applied as a regularization term to exploit similarity between the pattern graph and ego networks. By tuning only the prompt functions and a unified projection head while keeping the pre-trained model's parameters frozen, efficiency is enhanced and computational cost is reduced.

The paper provides theoretical insights showing that GNN-generated prompting can realize function adaptations not easily achievable by fine-tuning constrained around a fixed pre-trained solution, that subgraph neural networks have greater expressive power than standard message-passing GNNs, and that subgraph neural networks mitigate over-smoothing by restricting message passing within ego-networks. Time complexity analysis shows the pre-training phase has inference time complexity of O(V × V ego × d ego + V2), and the prompt tuning phase has approximately linear growth in inference time as node number increases.

Experimental results show PreGress achieves the most consistent and strongest ranking performance for betweenness centrality prediction across six datasets, attaining the best NDCG@10/20 on BK, FL, ID, WS, and YT, and remaining highly competitive on FB. For local subgraph counting, PreGress achieves the best results on BK, FB, ID, WS, and YT for both cutoffs, and remains highly competitive on FL, with clear improvements over the traditional baseline DISC. For link prediction, although PreGress is designed for node-ranking tasks, it still achieves the best results on most metrics, including all three metrics on BK, FL, and ID, MRR/H@10 on FB, MRR on WS, and MRR/H@20 on YT. On real-world recommendation tasks, PreGress-CNA on Yelp2018 achieves comparable retrieval quality to the strongest native recommender SimGCL with a 99.9% reduction in trainable state and a 39.1× downstream-training speedup, while on MovieLens, PreGress-ID is best, achieving 0.7474 Recall@20, 0.3501 NDCG@20, and 0.2454 MRR. Ablation studies confirm that prompt tuning is essential, subgraph-aware pre-training matters, and ego-net extraction helps. Pre-training task analysis shows degree centrality prediction combined with attribute reconstruction performs best among variants. Over-smoothing suppression analysis shows PreGress maintains stable and even improved NDCG@10/20 at larger depths up to 30 layers, while most baselines suffer from clear performance degradation. Few-shot accuracy evaluation shows PreGress consistently outperforms fine-tuning and existing prompt-tuning baselines under 10/20/50-shot settings. Efficiency evaluation shows PreGress consistently achieves low query latency, significantly outperforming exact algorithms by several orders of magnitude, and provides a better accuracy-efficiency trade-off than other learning-based methods.

Improvements to AI systems:

1. Ranking-native pre-training with multi-task objectives: Pre-train a graph backbone using degree centrality prediction (pointwise regression + listwise distribution matching) and masked attribute reconstruction (InfoNCE). This aligns pre-training with continuous-output ranking tasks, unlike contrastive or generative objectives that misalign with ranking.

2. Frozen backbone + lightweight prompt modules for task adaptation: Avoid full retraining for each ranking criterion. Instead, freeze the pre-trained subgraph neural network and tune only (a) a learnable vector prompt for global centrality tasks (e.g., betweenness) or (b) a GNN-based prompt conditioned on pattern graphs for local subgraph counting, with soft canonical correlation analysis (CCA) regularization to exploit pattern–ego-network similarity.

3. Ego-network extraction to prevent over-smoothing: Replace vanilla message passing with k-hop ego-network subgraph neural networks. This restricts message passing locally, preserving node-specific information at depth, enabling stable performance up to 30 layers where standard GNNs degrade.

4. Unified projection head for task-specific output: Use a single projection head shared across tasks, tuned alongside prompts, to map frozen representations to ranking scores. This reduces trainable parameters by 99.9% and speeds downstream training by 39× versus native recommenders.

5. Theoretical grounding for prompt expressiveness: Leverage the proof that GNN-generated prompts can realize function adaptations not achievable by fine-tuning around a fixed pre-trained solution. This justifies using prompts for non-linear task shifts (e.g., from degree to betweenness) without modifying the backbone.

What the improved AI system can do:

• Perform multiple node-ranking tasks (e.g., betweenness centrality, local subgraph counting, link prediction, recommendation) with a single pre-trained model, switching tasks by swapping lightweight prompts—no retraining of the backbone.

• Achieve state-of-the-art ranking quality (best NDCG@10/20 on 5 of 6 graphs for centrality; best on 5 of 6 for subgraph counting; competitive or best on link prediction and real-world benchmarks like Yelp2018 and MovieLens-100K).

• Operate with extremely low memory and compute overhead—trainable state reduced by 99.9% and downstream training speedup of 39.1× compared to strong baselines like SimGCL.

• Maintain accuracy at very deep architectures (up to 30 layers) without over-smoothing, enabling modeling of long-range dependencies in graphs.

• Adapt to new ranking criteria with few-shot data (10/20/50 shots), consistently outperforming fine-tuning and existing prompt-tuning baselines.

• Provide fast inference—several orders of magnitude faster than exact algorithms (e.g., for betweenness centrality) while retaining high ranking accuracy, suitable for real-time query-to-item retrieval.

Node ranking is a fundamental problem in graph information retrieval, measuring the relative importance of nodes and supporting a wide range of applications such as influence analysis, recommendation, and graph-based retrieval augmented generation. However, exact computation of graph-based ranking measures is often computationally prohibitive at scale. Existing GNN-based ranking methods provide scalable approximations, but they are typically tailored to individual ranking criteria and require retraining for each downstream task, which limits their transferability and efficiency. Recent graph pre-training approaches aim to enable knowledge transfer across tasks, yet their learning objectives are largely misaligned with node ranking, resulting in suboptimal adaptability to ranking-oriented applications. To address these limitations, we propose PreGress, the first ranking-native pre-training and prompting framework for supporting a wide range of node ranking tasks. PreGress performs multi-task pre-training using our carefully designed objectives, including degree centrality prediction and attribute reconstruction, to jointly capture structural and attribute information. To support heterogeneous ranking criteria, we design lightweight, task-specific prompt modules that adapt a frozen ranking backbone to downstream tasks without full retraining. Experiments on six public graphs and two real-world query-to-item benchmarks---Yelp2018 and MovieLens-100K---together with a controlled five-criterion graph-access study demonstrate strong ranking quality with low task-specific state overhead.