🤖 machine learning

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

PreGress is a novel framework that introduces ranking-native pre-training objectives and lightweight prompting modules to enable efficient, transferable, and high-quality node ranking across diverse tasks without requiring full model retraining.

Original authors: Lujie Ban, Jiasheng shi, Yingli Zhou, Kaiwen Xue, Daiyin Wang, Xubin Li, Shuanghua Li, Chenhao Ma

Published 2026-08-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Lujie Ban, Jiasheng shi, Yingli Zhou, Kaiwen Xue, Daiyin Wang, Xubin Li, Shuanghua Li, Chenhao Ma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a giant, bustling city where every person is connected to others by invisible threads of friendship, business, or shared interests. In the world of data science, this city is called a "graph," and the people are "nodes." Sometimes, you need to find the most important people in this city—maybe the ones who can spread a rumor the fastest, or the ones who connect two distant neighborhoods. This is called "node ranking." It's like trying to figure out who the top three most-cited scientists are in a massive library of research papers, or which products a customer is most likely to buy next.

For a long time, figuring out these rankings was like trying to count every single grain of sand on a beach to find the biggest one. It was slow, expensive, and required a human to do the math for every single question. Then, smart computers called "Graph Neural Networks" (GNNs) came along. They are like super-fast students who can learn to guess the answers by studying examples. But here's the catch: usually, if you wanted to teach a student to find the "most connected" person, you had to teach them all over again to find the "most influential" person. It was like having a student who was great at math but terrible at history, and you had to hire a whole new teacher for every new subject.

Recently, scientists started trying a different approach called "pre-training." Think of this as teaching a student a general set of skills—like how to read, how to think logically, and how to understand the world—before they ever see a specific test question. The idea is that once they have this general knowledge, they can quickly adapt to any new subject. But there was a problem: most of these general "students" were trained to do things like guessing missing words in a sentence or predicting if two people are friends. They weren't trained to rank things by importance. So, when you asked them to rank nodes, they were good at the basics but not great at the specific job.

This is where a new team of researchers, led by Lujie Ban and colleagues, stepped in with a fresh idea. They asked: "What if we built a student who was born to rank things?" They created a new system called PreGress. Instead of teaching a general student and hoping they can learn to rank later, they trained the system specifically on the concept of importance from the very beginning. They used a clever trick called "prompting," which is like giving the student a special pair of glasses or a hint card for each new test, rather than re-teaching the whole subject.

Here is how PreGress works in the real world. First, the system looks at a massive graph (like a social network) and breaks it down into small, manageable neighborhoods called "ego networks." Imagine looking at a city not as one giant map, but by focusing on one person's immediate circle of friends at a time. This helps the system understand local details without getting confused by the whole city at once.

Next, the system goes through a "pre-training" phase. It learns two main things:

Degree Centrality Prediction: It learns to guess how many friends a person has just by looking at their neighborhood. This is a direct measure of importance that is easy to calculate.
Attribute Reconstruction: It tries to guess missing details about a person (like their hobbies or job) based on what its friends are doing. This helps it understand the "personality" of the nodes, not just their connections.

By learning these two things together, the system builds a deep understanding of what makes a node important, both structurally (who they know) and by their own traits.

Once this "ranking-native" brain is built, it doesn't need to be retrained for every new job. Instead, the researchers use prompt tuning. If the system needs to find the "most central" person, it gets a simple, lightweight hint (a prompt) that tells it to focus on connection counts. If it needs to find people who act as bridges between groups, it gets a different hint that focuses on path-finding. The core brain stays frozen and unchanged; only the tiny hint cards are adjusted. This is like having a master chef who knows how to cook anything. You don't need to hire a new chef for every dish; you just give the same chef a different recipe card.

The researchers tested PreGress on six different public graphs and two real-world recommendation datasets (like Yelp and MovieLens). They found that PreGress was not only faster than traditional methods but also more accurate. It could rank nodes better than systems that had to be retrained from scratch every time. In fact, on some tasks, it was thousands of times faster than exact calculation methods while still getting the right answer.

One of the most exciting findings was that this approach works even when you have very little data to teach the system. In a "few-shot" test, where the system only saw 10 or 20 examples of what to rank, PreGress still performed incredibly well, beating other methods that needed hundreds of examples. This suggests that the pre-training really did teach the system a fundamental understanding of importance that it could apply anywhere.

The paper also looked at how deep the system could go. Usually, when neural networks get too deep (too many layers), they start to blur everything together, making it hard to tell one node from another—a problem called "over-smoothing." PreGress, however, handled deep layers beautifully, maintaining its ability to distinguish between different nodes even in very complex networks.

In short, PreGress is a new way to teach computers how to rank things in a network. Instead of training a new model for every single question, it builds one smart, adaptable model that learns the rules of importance once and then uses tiny hints to solve any ranking puzzle. It's faster, cheaper, and more accurate than the old ways, promising to make search engines, recommendation systems, and network analysis much smarter and more efficient. The authors suggest that this could be a big step forward in making graph-based AI more useful for everyone, from finding the best movie to watch to understanding how diseases spread through a population.

Technical Summary: PreGress

Problem Definition

Node ranking is a fundamental task in graph information retrieval, aiming to order nodes based on their relative importance or relevance for applications such as influence analysis, recommendation, and graph-based retrieval augmented generation (RAG). Traditional methods for computing ranking measures (e.g., PageRank, Betweenness Centrality, Local Subgraph Counting) face a scalability bottleneck: exact computation is often computationally prohibitive on large graphs, while approximate algorithms may yield inaccurate estimations.

Existing learning-based approaches utilizing Graph Neural Networks (GNNs) offer scalable approximations but suffer from two critical limitations:

Lack of Transferability: They are typically tailored to specific ranking criteria, requiring the collection of expensive ground-truth labels and retraining of a new model for every downstream task.
Misalignment in Pre-training: Recent graph pre-training efforts often employ objectives (e.g., link prediction) that are misaligned with node ranking, resulting in suboptimal adaptability when fine-tuned or prompted for ranking tasks.

The core challenge addressed by this work is how to derive unified, transferable meta-knowledge from easily accessible graph signals to enable a single model to adapt to diverse node ranking criteria without costly human annotation or full retraining.

Methodology: PreGress Framework

The authors propose PreGress, the first ranking-native pre-training and prompting framework for graph node ranking. The framework operates in three stages:

1. Ego Network Extraction

To mitigate the over-smoothing problem common in deep GNNs (where node embeddings become indistinguishable), PreGress does not process the entire graph as a single unit. Instead, it extracts $k$ -hop ego networks for each node. A subgraph neural network (SNN) processes these local subgraphs. This approach constrains the receptive field to local neighborhoods, preserving distinguishable node representations and capturing essential local structural and attribute information.

2. Multi-Task Pre-training

PreGress employs a multi-task pre-training strategy designed to align with the continuous numerical output space of ranking tasks. The pre-training objectives are:

Degree Centrality Prediction: A primary task where the model predicts the degree of each node. This provides a continuous, easily obtainable ground-truth signal that captures topological importance. The model uses a self-attention mechanism to aggregate node representations for this regression task.
Attribute Reconstruction: An auxiliary task inspired by BERT and Masked Autoencoders. The model reconstructs masked node attributes using the visible attributes and the underlying graph structure via a cross-attention mechanism. This ensures the model captures intrinsic relationships between node properties and structural importance.

The pre-training loss combines Mean Squared Error (MSE) for degree prediction, a listwise distribution-matching regularizer (KL divergence) to enforce ranking order consistency, and an InfoNCE loss for attribute reconstruction.

3. Task-Specific Prompt Tuning

To adapt the frozen pre-trained backbone to diverse downstream ranking tasks, PreGress utilizes lightweight, task-specific prompt modules rather than full fine-tuning:

For Centrality Prediction: A learnable vector is added to the node attributes of the downstream graph.
For Local Subgraph Counting: A lightweight GNN encodes the pattern graph (the subgraph structure to be counted) into a prompt vector, which is then added to the downstream graph's attributes. A Soft Canonical Correlation Analysis (Soft CCA) regularization term is used to align the representations of the pattern graph and the ego networks.

In this stage, only the prompt modules and a unified projection head are updated, while the pre-trained SNN backbone remains frozen.

Key Contributions

Ranking-Native Framework: Introduction of the first pre-training and prompting framework specifically designed for node ranking, distinguishing it from general graph pre-training methods.
Multi-Task Pre-training Strategy: A novel strategy combining degree centrality prediction and attribute reconstruction to jointly capture structural and attribute information, aligning pre-training objectives with fine-grained ranking requirements.
Task-Specific Prompt Modules: The design of lightweight, heterogeneous prompt mechanisms that allow a single frozen backbone to adapt to different ranking criteria (e.g., centrality vs. subgraph counting) without retraining the core model.
Empirical Validation: Comprehensive experiments demonstrating that PreGress achieves strong ranking performance with significantly reduced computational overhead and trainable parameters compared to fine-tuning and existing baselines.

Experimental Results

The authors evaluated PreGress on six public graphs (e.g., soc-brightkite, Flickr, YouTube) and two real-world recommendation benchmarks (Yelp2018, MovieLens-100K).

Ranking Performance: PreGress consistently achieved state-of-the-art or highly competitive results in Betweenness Centrality Prediction and Local Subgraph Counting, outperforming vanilla GNNs, fine-tuning methods (e.g., SimGRACE, GraphMAE), and existing prompt-tuning baselines (e.g., GraphPrompt, GPPT) across most datasets.
Efficiency: The framework demonstrated significant efficiency gains. In terms of trainable parameters, PreGress reduced the state overhead by approximately 99.9% compared to full fine-tuning in recommendation scenarios. It also achieved query latencies orders of magnitude faster than exact computation algorithms while maintaining superior accuracy compared to other learning-based approximations.
Robustness: The model showed strong generalization across different graph sizes and densities. Ablation studies confirmed the necessity of the subgraph backbone (SNN) for preventing over-smoothing and the importance of prompt tuning for task adaptation.
Few-Shot Learning: PreGress demonstrated superior performance in low-data regimes (10-shot to 50-shot), indicating that the pre-trained representations effectively capture transferable ranking signals.

Significance and Claims

The paper claims that PreGress addresses the critical gap between the need for scalable node ranking and the limitations of current learning-based methods. By shifting from "pre-training and fine-tuning" to "pre-training and prompting," PreGress enables:

Label Efficiency: Eliminating the need for expensive, task-specific ground-truth labels for every new ranking criterion.
Scalability: Providing a solution that scales to large graphs by avoiding full retraining and utilizing efficient prompt-based adaptation.
Unified Representation: Establishing a shared, transferable backbone that can support heterogeneous ranking tasks, moving beyond the siloed approach of training separate models for each metric.

The authors position PreGress as a step toward unifying node ranking problems under a shared pre-training-and-prompting framework, offering a practical recipe for deploying ranking systems in resource-constrained or rapidly changing environments.