Efficient quantification on large-scale networks

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

TL;DR

This paper introduces XNQ, a novel method for "network quantification" (NQ) that accurately estimates class proportions in large, interconnected networks, even when the data distribution shifts. XNQ achieves state-of-the-art performance by combining efficient graph neural networks with a robust quantification algorithm, significantly outperforming existing methods.

What Problem Does This Paper Address?

The paper tackles the problem of Network Quantification (NQ). Imagine you have a large social network, and you want to know the proportion of users who are "bots" versus "real users" within a specific community or subset of the network. Traditional classification would try to label each user individually, but NQ aims to estimate the overall percentage of bots and real users in that subset.

This task becomes challenging when:

  • Prior Probability Shift (PPS): The distribution of classes (e.g., bot vs. real user) in the data used to train the model is different from the distribution in the data you want to quantify. This is common in real-world scenarios.
  • Network Structure: Nodes in a network are not independent. Their connections and relationships (e.g., a bot following other bots) provide crucial information that simple classification methods miss.
  • Heterophily: Networks often have "inter-class edges" – connections between nodes of different classes (e.g., a real user interacting with a bot). This makes it harder for models that assume "homophily" (nodes tend to connect to similar nodes).
  • Scalability: Real-world networks can be massive, requiring efficient methods that can handle millions of nodes and edges.

Existing NQ methods struggle with these challenges, often failing to accurately estimate class proportions, especially under PPS, and lacking scalability or the ability to effectively leverage network structure and heterophily.

Methods

XNQ is a three-module system:

  1. Unsupervised Node Embedder: This module uses Graph Echo State Networks (GESN), a type of reservoir computing Graph Neural Network (GNN). GESNs are efficient because their "reservoir" weights are randomly initialized and frozen, meaning they don't require training. This allows them to learn rich node representations (embeddings) that capture both node features and network topology, even in large, heterophilic graphs, without needing a large amount of labeled data.
  2. Intermediate Readout Classifier: The node embeddings from the GESN are fed into a trained logistic regression classifier. This classifier outputs raw posterior probabilities for each node belonging to a class. These probabilities are then calibrated using Platt scaling to better reflect the observed class frequencies.
  3. Downstream Aggregative Quantifier: This module adapts the Saerens-Latinne-Decaestecker (SLD) method, an Expectation-Maximization (EM) algorithm known for its robustness to PPS. It takes the calibrated posterior probabilities and the known class distribution from the labeled data to iteratively refine the prevalence estimates until convergence.

The key novelty lies in the combination of an efficient, untrained GNN embedder (GESN) for robust node representations, a calibrated classifier, and a powerful EM-based quantifier, all designed for scalability and handling network complexities.

Datasets

The paper evaluates XNQ on five publicly available datasets commonly used for node classification tasks, adapted for NQ:

  • Cora: A citation network where nodes are publications and edges are citations. Used to derive a binary classification task.
  • Genius: A social network from a song annotation platform, classifying users as regular or spam.
  • Questions: A network from Yandex Q, classifying users as active or inactive.
  • Tolokers: A network from the Toloka platform, classifying workers as banned or not banned.
  • Twitch-DE: A social network of German Twitch users, classifying profiles as adult content or not.

Additionally, for multi-class evaluation, they use:

  • Cora-Multi: The original Cora dataset with all 7 classes.
  • Amazon: A product co-purchasing network.
  • Flickr: A graph of images with common properties.

These datasets represent real-world networks of varying sizes, heterophily levels, and class imbalances.

Key Insights and Ideas

  • Untrained GNNs for Embeddings: Using reservoir computing GNNs (GESN) for node embeddings is surprisingly effective and efficient. It bypasses the need for extensive training of the embedder itself, making the overall system faster and less reliant on labeled data.
  • Calibration is Crucial: Simply getting raw probabilities from a classifier isn't enough for quantification. Calibrating these probabilities (e.g., via Platt scaling) is essential for accurate prevalence estimation.
  • EM for Robust Quantification: The SLD method, an EM algorithm, proves to be a powerful downstream quantifier, especially when dealing with prior probability shift, a common challenge in real-world NQ tasks.
  • Heterophily is Not a Dealbreaker: XNQ's design, particularly the GESN embedder, effectively handles heterophilic graphs, where nodes connect to different classes, a weakness of many traditional GNNs.
  • Scalability is Achieved: XNQ demonstrates impressive scalability, maintaining accuracy on networks with hundreds of thousands of nodes and significantly outperforming baselines in terms of training time.

Key Results

  • State-of-the-Art Performance: XNQ consistently achieves the lowest Average Error (AE) across all tested datasets, significantly outperforming existing NQ methods. For instance, it achieved a 90.48% reduction in AE on the Genius dataset.
  • Efficiency: XNQ is considerably faster to train than other graph-learning methods, often by more than an order of magnitude, making it practical for large-scale applications.
  • Robustness: XNQ performs well across diverse datasets with varying sizes, heterophily levels, and class imbalances, demonstrating its generalizability.
  • Data Efficiency: XNQ's performance remains strong even with very small fractions of annotated training data (down to ~2%), highlighting its ability to learn from scarce labels.
  • Multi-class Extension: XNQ extends effectively to multi-class NQ, maintaining its superior performance.

Limitations and Future Work

  • Quantifier Choice: While SLD is effective, the paper notes that other quantifiers (like ACC) can lead to performance ties, suggesting that the choice of downstream quantifier can still be important.
  • Non-aggregative NQ: The paper mentions that future work could explore non-aggregative NQ methods, which estimate class priors without assigning labels to individual nodes. This is desirable for applications like measuring fairness where individual predictions are not needed.
  • Further Multi-class Exploration: While XNQ was extended to multi-class settings, further investigation into specific multi-class challenges could be beneficial.

Summary updated

Abstract

Network quantification (NQ) is the problem of estimating the proportions of nodes belonging to each class in subsets of unlabelled 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, NQ demands enhanced flexibility in order to capture a broad range of connectivity patterns, resilience to the challenge of heterophily, and scalability to large networks. In order 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. In an extensive evaluation, in which we also validate the design choices underpinning XNQ through comprehensive ablation experiments, we find that XNQ consistently and significantly improves on the best network quantification methods to date, thereby setting the new state of the art for this challenging task. XNQ also provides a training speed-up of up to 10x-100x over other methods based on graph learning.
BibTeX
@article{micheli2025efficient,
  author = {Alessio Micheli and Alejandro Moreo and Marco Podda and Fabrizio Sebastiani and William Simoni and Domenico Tortorella},
  title = {{Efficient quantification on large-scale networks}},
  journal = {Machine Learning},
  year = {2025},
}
Figure