Learning to quantify graph nodes

Alessio Micheli, Alejandro Moreo, Marco Podda, Fabrizio Sebastiani, William Simoni, Domenico Tortorella

Abstract

Network Quantification is the problem of estimating the class proportions in unlabeled subsets of graph nodes. When prior probability shift is at play, this task cannot be effectively addressed by first classifying the nodes and then counting the class predictions. In addition, unlike non-relational quantification on i.i.d. datapoints, Network Quantification demands enhanced flexibility to capture a broad range of connectivity patterns, resilience to the challenge of heterophily, and efficiency to scale to larger networks. To meet these stringent requirements we introduce XNQ, a novel method that synergizes the flexibility and efficiency of the unsupervised node embeddings computed by randomized recursive Graph Neural Networks, with an Expectation-Maximization algorithm that provides a robust quantification-aware adjustment to the output probabilities of a calibrated node classifier. We validate the design choices underpinning our method through comprehensive ablation experiments. In an extensive evaluation, we find that our approach consistently and significantly improves on the best Network Quantification methods to date, thereby setting the new state of the art for this challenging task. Simultaneously, it provides a training speed-up of up to 10x-100x over other graph learning based methods.

Introduction: From Classification to Quantification

In graph machine learning, the standard focus is node classification—assigning a specific label to an individual node. However, many real-world applications in sociology, epidemiology, and market research require quantification: estimating the total percentage of a class within a community (e.g., "What proportion of this network consists of bot accounts?").

A naive approach, "Classify and Count," fails when the test data distribution differs from the training data, a phenomenon known as Prior Probability Shift. If a classifier is trained on a 50/50 split but encounters a 5/95 split in the wild, it will likely over-predict the majority class from its training phase.

The impact of prior probability shift on prevalence estimation. Standard quantifiers often fail to track the ideal diagonal when the true prevalence deviates from the training prevalence.

The XNQ Framework

To address these challenges, we propose XNQ (eXtreme Network Quantifier), a three-stage pipeline designed for speed, scalability, and resilience to complex graph topologies like heterophily.

The XNQ architecture: Node embeddings are generated via a reservoir, passed to a calibrated readout classifier, and finally adjusted by an aggregative quantifier.
  1. Unsupervised Node Embedder: XNQ utilizes Graph Echo State Networks (GESN). Unlike traditional Graph Neural Networks (GNNs) that require expensive end-to-end training, GESNs use fixed, random weights to process graph connections. This "Reservoir Computing" approach captures complex topology with minimal computational overhead.
  2. Calibrated Readout Classifier: A Logistic Regression model is trained on the resulting embeddings. To ensure the output probabilities are statistically meaningful for quantification, we apply Platt Scaling for calibration.
  3. Aggregative Quantifier: The final stage employs the Saerens-Latinne-Decaestecker (SLD) algorithm. This Expectation-Maximization (EM) method iteratively adjusts prevalence estimates to best fit the observed probability distribution in the unlabeled test set.

Experimental Evaluation

XNQ was evaluated across diverse real-world networks, including citation networks (Cora), social networks (Genius, Twitch-DE), and crowdsourcing platforms (Tolokers).

Key Findings

  • State-of-the-Art Accuracy: XNQ consistently outperformed existing methods. Notably, on the Genius dataset, it reduced Absolute Error (AE) by over 90% compared to previous benchmarks.
  • Computational Efficiency: By avoiding backpropagation through the graph, XNQ is 10x to 100x faster to train than convolutional GNN-based quantifiers. It can process networks with 400,000 nodes in under a minute on a single GPU.
  • Resilience to Heterophily: The reservoir approach is naturally resistant to "over-smoothing," allowing XNQ to maintain high performance even in networks where connected nodes frequently belong to different classes.
  • Data Efficiency: The model remains robust even with minimal supervision, requiring as little as 2% of the network to be annotated.

Conclusion

XNQ represents a significant advancement in Network Quantification, offering a scalable and accurate solution for large-scale graph analysis. While currently an aggregative method, future work may explore non-aggregative approaches to directly estimate priors, potentially enhancing privacy by avoiding individual node labeling altogether.

Summary updated

Abstract

Network Quantification is the problem of estimating the class proportions in unlabeled subsets of graph nodes. When prior probability shift is at play, this task cannot be effectively addressed by first classifying the nodes and then counting the class predictions. In addition, unlike non-relational quantification on i.i.d. datapoints, Network Quantification demands enhanced flexibility to capture a broad range of connectivity patterns, resilience to the challenge of heterophily, and efficiency to scale to larger networks. To meet these stringent requirements we introduce XNQ, a novel method that synergizes the flexibility and efficiency of the unsupervised node embeddings computed by randomized recursive Graph Neural Networks, with an Expectation-Maximization algorithm that provides a robust quantification-aware adjustment to the output probabilities of a calibrated node classifier. We validate the design choices underpinning our method through comprehensive ablation experiments. In an extensive evaluation, we find that our approach consistently and significantly improves on the best Network Quantification methods to date, thereby setting the new state of the art for this challenging task. Simultaneously, it provides a training speed-up of up to 10x-100x over other graph learning based methods.
BibTeX
@article{micheli2025learning,
  author = {Alessio Micheli and Alejandro Moreo and Marco Podda and Fabrizio Sebastiani and William Simoni and Domenico Tortorella},
  title = {{Learning to quantify graph nodes}},
  journal = {Machine Learning},
  year = {2025},
}
Figure