Research map / Graph learning / Graph algorithms and clustering
Adjusted Count Quantification Learning on Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends Adjusted Classify & Count to graph quantification via structural importance sampling (SIS) for covariate shift and neighborhood-aware ACC (NACC) for non-homophilic edges, evaluated on synthetic and Twitch shifts.
Problem
Quantification learning (estimating label prevalences) on graph-structured data, where prior probability shift assumed by ACC often fails due to structural sampling biases and non-homophilic edges hurt class identifiability.
Approach
Reweight training vertices via kernel density ratios (PPR-based structural kernel) so the confusion matrix matches the test distribution under covariate shift (SIS), and augment the predicted-label space with the majority predicted label of each vertex's neighbors so the confusion profiles become identifiable (NACC).
Key results
- On synthetic shifts, SIS and NACC improve quantification over ACC/PACC under PPS and covariate shift, with SIS or SIS+NACC ranking best on average across classifiers and shift types.
- On Twitch Gamers, SIS generally outperforms standard ACC and CC for non-English language communities when using an APPNP classifier, but not for English (74% of training data).
- Using a structure-unaware MLP classifier, SIS did not significantly improve quantification on Twitch, highlighting the need for an accurate base classifier.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SIS importance weighting with the structural PPR kernel | ACC-based graph quantification · Synthetic graph shifts (PPS, BFS, and random walks) | AE | Helped |
| Add neighborhood-aware predictions to the quantifier (NACC) | ACC-based graph quantification · Synthetic graph shifts | AE | Helped |
| Use SIS with APPNP rather than standard ACC/CC | APPNP quantification · Twitch Gamers, German, French, Spanish, and Russian communities | AE | Helped |
| Use SIS rather than standard quantification approaches | Graph quantification · Twitch Gamers, English community | AE | Hurt |
| Use SIS with a structure-unaware MLP classifier | MLP quantification · Twitch Gamers | AE | No clear effect |
| Replace the structural PPR kernel with an inner-product feature kernel (ablation) | SIS · Synthetic structural covariate shifts | AE | Hurt |
| Use an interpolated PPR kernel with λ < 1 rather than λ = 1 (ablation) | SIS with NACC · CoraML and CiteSeer | AE | Helped |
| Use an interpolated PPR kernel with λ < 1 rather than λ = 1 (ablation) | SIS with NACC · Amazon Photos and Amazon Computers | AE | Hurt |
| Increase γ in the shortest-path kernel (ablation) | SIS with NACC · Synthetic PPS shifts | AE | Hurt |
| Increase γ in the shortest-path kernel (ablation) | SIS with NACC · Synthetic BFS and random-walk covariate shifts | AE | Helped |
| Replace the PPR kernel with the shortest-path kernel (ablation) | SIS · Synthetic shifts | AE | Mixed |
| Use the PPR kernel rather than the shortest-path kernel (ablation) | SIS · Synthetic shifts overall | AE | Helped |
Surprising findings
- The naive neighborhood-based ENQ performs worst among classifiers, while APPNP performs best, and SIS can perform worse than standard methods on the English partition where the shift is small.
Limitations
- No true graph quantification benchmark exists; synthetic shifts were introduced into node classification datasets.
- SIS requires a kernel suited to the sampling process; PPR kernel is a default that may not match other shifts (e.g., BFS shift is only approximately captured).
Experimental setup
Datasets: CoraML CiteSeer PubMed Amazon Photos Amazon Computers Twitch Gamers
Benchmarks: CoraML CiteSeer PubMed Amazon Photos Amazon Computers Twitch Gamers
Metrics: absolute error (AE) relative absolute error (RAE)
Baselines: MLPE CC PCC ACC PACC ENQ
Builds on: Adjusted Classify & Count APPNP QuaPy Ensemble neighborhood quantification (ENQ)
Closest papers by meaning
- Unveiling the sampling density in non-uniform geometric graphs (ICLR 2023 · similarity 0.86)
- No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.85)
- Fully-inductive Node Classification on Arbitrary Graphs (ICLR 2025 · similarity 0.84)
- Learning Graph Representation via Graph Entropy Maximization (ICML 2024 · similarity 0.84)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.84)
- Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.