Distribution Matching for Graph Quantification Under Structural Covariate Shift

AI summary

Overview

• Research area: Machine learning — quantification learning (label prevalence estimation) on graph-structured data, specifically addressing distribution shift between training and test node samples.
• Technical level: Intermediate. The paper assumes familiarity with classification, probability distributions, distribution matching, and graph neural networks, but its motivation is explained with concrete examples.
• Scope: The paper extends a graph-aware importance-sampling correction (structural importance sampling) from Adjusted Classify & Count to the KDEy distribution matching quantifier and evaluates the combination on five node-classification benchmark graphs.

What This Paper Is About

Quantification learning estimates how common each label is in a set of instances, rather than predicting the label of any single instance. In graph data, the training nodes and test nodes may come from different regions of the graph, which violates the label-conditional assumptions that standard quantifiers rely on. The authors extend a graph-aware "structural importance sampling" idea to the state-of-the-art KDEy distribution matching quantifier so that it stays accurate under this structural covariate shift.

Key Contributions

1. Extends structural importance sampling (SIS) from Adjusted Classify & Count to the distribution matching framework, which previously only supported the ACC-style quantifier family.
2. Derives a reweighted variant of KDEy in which the kernel density estimates of the class-conditional densities of predicted probabilities are computed with per-instance weights, and those weights are themselves estimated via kernel density estimation using a vertex kernel on the graph.
3. Evaluates the proposed method against multiple quantifiers, classifiers, and shift types on five benchmark node-classification datasets using absolute error and relative absolute error.
4. Releases an open-source implementation (code available at the GitHub repository listed in the paper).

Main Findings

• KDEy with structural importance sampling performs best overall: Looking at average ranks, KDEy with SIS outperforms KDEy without SIS, Probabilistic Classify & Count, and Probabilistic Adjusted Classify & Count.
• Consistency across conditions: The advantage holds across all three types of distribution shift examined, all model types, and both the absolute error and relative absolute error metrics.
• No benefit under prior probability shift: Under prior probability shift, where SIS is not necessary, SIS generally does not significantly improve quantification performance; nevertheless, KDEy with SIS has a better average rank than KDEy without SIS there as well.
• Classifier quality still matters: Although an unbiased quantifier does not strictly require a good classifier, the quality of the estimate correlates with classifier accuracy. The structure-unaware Multilayer Perceptron performs worst, while approximate personalized propagation of neural predictions performs best.
• Kernel choice should match the shift mechanism: The personalized page-rank kernel matches random-walk sampling, while the shortest path kernel was tested as a better match for the breadth-first-search sampling setting. The paper's evaluation of the covariate shift types is cut off in the provided content, so the full conclusions on this point are not available.
• Numeric result values are not reported in the provided text: The results table's underlying data file is referenced but its numeric entries are not included in the content supplied, and the text reports relative comparisons (average ranks and statistical significance) rather than concrete value figures.

Methodology in Plain English

The authors start from a factorization that underlies both Adjusted Classify & Count and distribution matching quantifiers: the distribution of some transformed instance feature on the test set can be written as a mixture of class-conditional distributions weighted by the unknown label prevalences. This factorization relies on the class-conditional distributions being the same in training and test data, which fails when the test nodes sit in a different part of the graph.

To repair this, they borrow the structural importance sampling idea: rewrite the unknown test class-conditional instance distribution in terms of the training distribution multiplied by a density ratio between the test and training node distributions. That ratio is estimated with kernel density estimation, using a kernel defined over graph structure (a personalized page-rank-based kernel, a shortest path kernel, or an interpolated personalized page-rank kernel that guarantees a minimum weight per vertex).

Substituting the reward into the distribution matching setup yields a weighted version of the KDEy method. Instead of averaging a Gaussian kernel over the labeled training nodes uniformly, the method averages with per-node weights derived from the graph-based density ratio. The prevalence vector is then obtained by solving the same divergence-minimization problem KDEy uses; the authors use the Kullback-Leibler divergence variant (KDEy-ML).

For evaluation, they take five node-classification datasets and split each randomly 10 times into classifier train (5%), quantifier train (15%), and quantifier test (80%) partitions. They train each of four classifiers 10 times on each classifier train set, yielding 100 classifiers per dataset. Training data is sampled uniformly at random; the test partitions are synthetically shifted in three ways: prior probability shift (10·K sets of 100 nodes with Zipf-sampled label distributions), random-walk-based structural covariate shift (10 seed vertices per label, 100 nodes sampled via random walks of length 10 with teleportation parameter 0.1), and breadth-first-search-based structural covariate shift. Quantification quality is measured with absolute error and relative absolute error.

Why This Matters

Quantification is often the actual goal in network analytics: stakeholders frequently care about group-level prevalence rather than individual predictions, and individual-level classifiers are not optimized for that quantity. This paper shows that a modern distribution matching quantifier can be made robust to the fact that training and test nodes are drawn from different regions of a graph — a very common situation when data is collected locally but deployed globally.

Real-world applications suggested by the paper's framing:

• Social network opinion estimation: predicting the prevalence of political preferences or opinions in a population rather than any individual user's view.
• Citation network topic prevalence: the CoraML, CiteSeer, and PubMed datasets model documents linked by citations and labeled with topics.
• Product co-purchasing analytics: the Amazon Photos and Amazon Computers graphs model products linked when frequently bought together, labeled by product category.
• Epidemiological prevalence studies: the paper uses disease prevalence in a population as the canonical quantification example (discussed in the context of prior probability shift).

Industry relevance: any platform deploying node classification on graphs — social networks, e-commerce, scholarly search — can benefit from label distribution estimates that remain accurate when the inference population is sampled from a different part of the network than the training population.

Future Directions

• Extending non-aggregative quantifiers to covariate shift: the authors explicitly state they focus on aggregative methods here and leave the extension of non-aggregative quantification methods to covariate shift for future work.
• Kernel selection: the paper notes that the appropriate notion of "closeness" depends on the nature of the covariate shift, and that the kernel should be chosen based on available knowledge about the problem to reflect the shift as closely as possible; the breadth-first-search results are used to check whether a distance-based kernel matches that sampling process.
• Applying SIS to other distribution matching divergences: KDEy supports Hellinger, L2, Cauchy-Schwarz, Jensen-Shannon, and Kullback-Leibler divergence variants; the experiments use KDEy-ML, leaving the others open.
• Hyperparameter handling: the interpolated kernel introduces a parameter controlling the minimum weight assigned to each vertex, which raises the question of how best to select such hyperparameters in practice.

Target Audience

Researchers and practitioners working on quantification learning, distribution shift, or graph machine learning. It is most useful to readers who already know the basics of classification and probability distributions and want to understand how to make prevalence estimation robust when training and test nodes come from different graph regions. It is also relevant to applied data scientists who need group-level statistics from networked data rather than per-instance predictions.

Authors’ abstract

Graphs are commonly used in machine learning to model relationships between instances. Consider the task of predicting the political preferences of users in a social network; to solve this task one should consider, both, the features of each individual user and the relationships between them. However, oftentimes one is not interested in the label of a single instance but rather in the distribution of labels over a set of instances; e.g., when predicting the political preferences of users, the overall prevalence of a given opinion might be of higher interest than the opinion of a specific person. This label prevalence estimation task is commonly referred to as quantification learning (QL). Current QL methods for tabular data are typically based on the so-called prior probability shift (PPS) assumption which states that the label-conditional instance distributions should remain equal across the training and test data. In the graph setting, PPS generally does not hold if the shift between training and test data is structural, i.e., if the training data comes from a different region of the graph than the test data. To address such structural shifts, an importance sampling variant of the popular adjusted count quantification approach has previously been proposed. In this work, we extend the idea of structural importance sampling to the state-of-the-art KDEy quantification approach. We show that our proposed method adapts to structural shifts and outperforms standard quantification approaches.