Chasing Label Shifters: A Change-Aware Framework for Dynamic Graph Node Classification

AI summary

Overview

Research area: Machine learning on dynamic (temporal) graphs — specifically dynamic graph neural networks (GNNs) for node classification, and the problem of nodes whose class labels change over time.

Technical level: Advanced. The paper assumes familiarity with message-passing GNNs, contrastive losses, recurrent and attention-based temporal architectures, and homophily measures on graphs.

Scope: The paper diagnoses a universal failure mode in dynamic GNNs on "shifter" nodes (nodes whose label changes between consecutive snapshots), attributes it to a mechanism they call embedding inertia, and proposes CHASE, a model-agnostic wrapper with three components that improves shifter classification across seven backbones and three newly constructed benchmarks.

What This Paper Is About

Real-world entities modeled as graph nodes — researchers, social media users, music listeners, firms — sometimes change category over time, which means their class labels change between snapshots. The authors call these nodes shifters and show that every major dynamic GNN architecture classifies them substantially worse than stable nodes, with errors overwhelmingly falling back on the node's old label. The goal is to explain why this happens and to build a framework that fixes it without changing the underlying encoder or hurting stable-node accuracy.

Key Contributions

1. Three new dynamic graph benchmarks with naturally shifting labels. DBLP-S (academic co-authorship, 34,717 nodes, 394,385 edges, 14 snapshots split 9/2/3, 2 classes, 2.62% shifters), GossipCop (news co-consumption, 6,091 nodes, 2,000,390 edges, 37 snapshots split 26/5/6, 2 classes, 4.06% shifters), and Music (music co-listening, 878 nodes, 1,009,457 edges, 24 snapshots split 15/4/5, 5 classes, 18.77% shifters). Labels are derived from observed behavior rather than synthetically injected.
2. Identification and quantification of a universal "shifter gap." Across seven dynamic GNN architectures and all three datasets, shifter accuracy and F1 lag stable-node accuracy and F1 by up to 50%p and 55.1%p respectively, and errors concentrate on the old label.
3. A structural diagnosis: embedding inertia. Neighborhood aggregation anchors shifter embeddings to the old-class centroid, most severely for shifters with low current homophily and high previous homophily. Centroid displacement analysis confirms correctly classified shifters move toward the new-class centroid while incorrectly classified ones do not.
4. CHASE, a model-agnostic change-aware framework. Three components — a homophily-guided contrastive loss, a change detection head, and a change-aware classifier — each motivated by a specific diagnostic finding, improving shifter performance on all 21 dynamic backbone–dataset combinations (up to 114.9% and 202.5% improvement on accuracy and F1) while preserving stable-node performance.

Main Findings

• The shifter gap is universal. Shifter accuracy and F1 lag stable-node counterparts by up to 50%p and 55.1%p across seven dynamic GNN models (GCN-GRU, EvolveGCN, DySAT, GCN-SE, IDGNN, TADGNN, SiGNN) and three datasets. The pattern is not attributable to any single architectural design choice.
• Errors are directionally biased toward the old label. On the five-class Music dataset, up to 76% of shifter errors default to the old class, far exceeding the 25% rate expected under uniform error. On Music, a shifter's embedding is most similar to its predicted class centroid (mean cosine similarity 0.83 versus 0.65 to other classes); shifters misclassified as their old class lie closest to that old class (0.84 versus 0.78 to the true new class and 0.70 to the remaining three).
• All four structural signals identify shifters, but only homophily signals predict correctness. Feature drift, neighborhood drift, current homophily, and previous homophily separate shifters from stable nodes (rank-biserial |r| up to 0.94, Mann-Whitney U test, p ≈ 0). Within the shifter subpopulation, drift signals lose discriminative power (|r| < 0.10) while homophily measures distinguish correctly from incorrectly classified shifters (|r| up to 0.52), with incorrect shifters showing lower current homophily and higher previous homophily.
• Correctly classified shifters show positive centroid displacement. Incorrectly classified shifters show Δc ≈ 0 or negative, meaning their embeddings have not moved toward the new-class centroid (p ≈ 0 across all models and datasets).
• CHASE improves shifter performance everywhere. All 21 dynamic backbone–dataset combinations improve, up to 114.9% on shifter accuracy and 202.5% on shifter F1. Gains are largest on GossipCop and Music, where baseline shifter performance is lowest. Example: GCN-SE on Music improves shifter accuracy from 36.8 to 79.1 (+114.9%), and on GossipCop shifter F1 improves from 20.1 to 60.8 (+202.5%).
• Stable-node performance is not sacrificed. Stable-node accuracy and F1 are generally preserved or improved substantially across cases; small decreases appear for some backbones (e.g., GCN-GRU on DBLP-S stable accuracy 97.0 to 96.3, and EERM on DBLP-S stable accuracy 96.3 to 96.1).
• The shifter–stable gap narrows. Under CHASE, the performance disparity between shifters and stable nodes is significantly reduced, by up to −73.0%.
• Improvement tracks homophily. CHASE's relative improvement is largest for nodes with the lowest current homophily and decreases monotonically as homophily increases, matching the diagnostic prediction.
• Improvement reflects genuine classification, not just old-label suppression. On the multiclass Music dataset, a model that merely avoided the old label would still misclassify 75% of the time among the remaining classes; CHASE achieves substantial shifter error reduction on all three datasets, with the greatest improvement on Music.
• Shifts away from the dominant class benefit most. On Music, class 0 (Rock) is the majority label; baseline accuracy is lowest for shifts away from the dominant class, moderate for shifts between non-dominant classes, and highest for shifts toward the dominant class.
• The change detection signal is the largest single contributor. In the GCN-GRU ablation, every component adds monotonically; the largest single jump occurs when the change detection head is added (+Detect.), because the earlier steps give the classifier the capacity to deviate but not the signal for when to do so.
• The problem differs from graph distribution shift. EERM, a GNN method designed for distribution shift, fails to meaningfully improve upon a plain GCN on its own, and still benefits from CHASE augmentation.
• Shifter influence propagates. On GossipCop, real-news neighbors of a recent shifter toward fake news are 2.0× more likely to shift themselves than neighbors of a stable fake-news user. Among nodes with fake-news neighbors, those whose fake-news neighbors are predominantly recent shifters are 3.9× more likely to shift than those whose fake-news neighbors are predominantly long-standing consumers.

Methodology in Plain English

The researchers first build three temporal graph datasets from real-world behavior logs, in which each node's label is recomputed at every snapshot from what the node actually did — a researcher's primary area, a user's majority news consumption, a listener's dominant genre. Because labels are recomputed rather than assigned once, a measurable fraction of nodes change label between consecutive snapshots, giving the authors a natural population of shifters to study.

They then run seven dynamic GNN models on these datasets and split every model's test performance into shifter accuracy/F1 and stable-node accuracy/F1, revealing a consistent gap. To explain the gap, they compute four per-node structural signals — how much a node's own features changed, how much its neighbors' average features changed, the fraction of its current neighbors sharing its current label (current homophily), and the fraction of its previous neighbors sharing its old label (previous homophily) — and test which signals separate shifters from stable nodes and, separately, which separate correctly from incorrectly classified shifters. They also measure centroid displacement: whether a node's learned embedding moved closer to the new-class centroid than the old-class centroid, with centroids computed only from stable nodes.

The diagnosis — embedding inertia, most severe under low current and high previous homophily — drives the design. CHASE wraps an existing backbone without touching its encoder and replaces only the classifier head. A margin-based contrastive loss (margin m = 0.5) pulls shifter embeddings toward the new-class centroid and away from the old, weighted by (1 − current homophily) so that the weakest-homophily shifters get the strongest correction; this loss applies only during training, where current labels are available. A change detection head takes the backbone embedding plus the drift signals plus a label-free proxy for previous homophily and outputs a probability that the node has shifted. A change-aware classifier consumes the backbone embedding, an aggregation-free projection of the node's own features, the change probability, and the model's own previous prediction, learning when to override the stale neighborhood signal. The total objective combines classification cross-entropy (with sqrt-dampened class weights), the contrastive loss, and the detection loss, with λ_hom = λ_change = 0.1; models are trained end-to-end with five random seeds and selected by validation F1, and all test-time inputs come from features, structure, and the model's own previous predictions, requiring no ground-truth test labels.

Why This Matters

Impact on research. The paper reframes label shift in dynamic graphs as a distinct problem from distribution shift: the mismatch happens within the observed graph across time, for a known node whose ground-truth label changed, and the failure is temporal inertia rather than unfamiliar structure. It introduces shifter-versus-stable evaluation as an explicit criterion, supplies three benchmarks where labels shift naturally (filling a gap the authors note in existing resources such as TGB, whose node-level task is affinity prediction rather than categorical label classification), and gives a diagnostic vocabulary — embedding inertia, current and previous homophily, centroid displacement — that other researchers can reuse. It also demonstrates that a model-agnostic head replacement, rather than a new architecture, is sufficient, which lowers the barrier for follow-up work.

Real-world applications.

• Misinformation detection: identifying users actively transitioning toward fabricated news before they shift, rather than only flagging long-standing fake-news consumers, since recent shifters are shown to be more influential over their neighbors.
• Academic analytics: tracking researchers whose primary field changes between years, which affects expert routing, reviewer assignment, and funding allocation.
• Financial risk monitoring: detecting firms transitioning between risk states based on their shifting transaction networks, so intervention can occur before a state change is confirmed.
• Recommender and streaming systems: catching listeners migrating between genres for timely catalog and playlist adaptation.

Industry relevance. Any platform that maintains a temporal interaction graph — social networks, news aggregators, streaming services, credit and fraud monitoring — faces label change as a routine operational phenomenon. The finding that a model's own architecture does not need replacing, only its classifier head, makes adoption practical for teams with existing dynamic GNN pipelines. The requirement that no test-time ground-truth labels be used, the modest additional loss terms, and the publicly released code at https://github.com/jhkim611/CHASE further support deployment-oriented adoption.

Future Directions

• Extension beyond classification heads. CHASE wraps encoders rather than modifying them. Whether architectures designed from the start around label shift can outperform a head-level augmentation remains open.
• Broader domains and label semantics. The three benchmarks cover academic co-authorship, news co-consumption, and music listening with shifter rates of 2.62%, 4.06%, and 18.77%. Domains with still different shift dynamics — and possibly continuous or hierarchical labels — are untested.
• Dependence on homophily signals. The framework's correction strength is driven by current homophily during training and by a label-free proxy for previous homophily at inference. Behavior on graphs where these signals are weak, noisy, or poorly defined is not established.
• Detecting shifts that do not propagate. The paper's motivation rests on shifters being influential over their neighbors. Whether the same mechanisms and gains hold in graphs where label change is individually driven with little neighborhood signal is an open question.

Target Audience

Researchers and practitioners working on dynamic or temporal graph learning, graph neural network robustness, and concept or label drift in deployed models. It is most useful to readers who already understand message-passing GNNs and temporal encoders and want a concrete evaluation protocol, a structural diagnosis of a specific failure mode, and a reproducible, model-agnostic fix. Readers interested in benchmarks for non-stationary graph data will also find the three constructed datasets valuable; readers seeking an introduction to GNNs will find the paper too specialized without background reading.

Authors’ abstract

Entities in real-world systems often evolve over time: users shift between information consumption patterns, researchers migrate between fields, and firms transition between financial risk states. When such systems are modeled as dynamic graphs, these transitions correspond to nodes whose class labels change between consecutive snapshots, which we call shifters. Correctly classifying shifters is often more consequential than classifying stable nodes with persistent labels, as detecting such transitions enables timely intervention in high-stakes settings. Yet, we identify a systematic failure mode across all major dynamic graph neural network architectures: shifter performance consistently lags behind stable nodes, with errors concentrated on the old label. Our structural analysis traces this failure to embedding inertia: neighborhood aggregation keeps shifter representations anchored to the old-class centroid, and this effect is strongest precisely where it is hardest to correct, namely for shifters whose neighborhoods remain aligned with the old class. Guided by this finding, we propose CHASE, a model-agnostic CHange-Aware framework for Shifting nodEs that wraps any dynamic GNN with targeted components for detecting label shifts and overriding stale neighborhood signals. CHASE consistently improves shifter performance across all tested models and datasets (up to 114.9% and 202.5% improvement on accuracy and F1 score, respectively) while preserving stable-node performance. We additionally contribute three dynamic graph benchmarks with naturally shifting labels, filling a gap in existing resources. The source code is available at https://github.com/jhkim611/CHASE