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

1 Introduction

• Shifters are classified substantially worse than stable nodes across three datasets and seven models, and misclassifications overwhelmingly predict the old label.The pattern holds across the examined architectures and is not attributable to one design choice.Source: §1 · p. 2
• The paper constructs three benchmarks from real-world data and observed behavior, spanning academic co-authorship, news co-consumption, and music co-listening.The benchmarks address the lack of existing resources with meaningful label change for systematic shifter evaluation.Source: §1 · p. 2
• Neighborhood aggregation creates embedding inertia by anchoring shifter representations to the old-class centroid, most strongly when local homophily still reflects the old class.Correctly classified shifters move toward their new-class centroid, unlike incorrectly classified shifters.Source: §1 · p. 2
• CHASE wraps a dynamic GNN without modifying its encoder, combining homophily-guided contrastive learning, shift detection, and a classifier that can override stale predictions.The components respectively counter embedding inertia, estimate when a label shift occurs, and provide capacity to deviate from prior predictions.Source: §1 · pp. 2–3
• Across seven models and three datasets, CHASE improves shifter performance in every case, with up to 114.9% improvement on accuracy and 202.5% on F1 score, while stable-node performance is preserved or enhanced.All components contribute monotonically in ablation.Source: §1 · p. 2

2.1 Dynamic Graph Neural Networks

• Dynamic graph methods combine spatial graph encoders with recurrent or attention-based sequence modeling, with newer approaches exploring equilibrium, deep propagation, and spiking activations.Examples include GCRN, EvolveGCN, DySAT, GCN-SE, IDGNN, TADGNN, and SiGNN.Source: §2.1 · p. 3
• Existing methods and evaluation protocols do not explicitly distinguish shifters from stable nodes or target shifter performance, despite acknowledging that node properties can evolve over time.GCN-SE observes attention changes on synthetic label changes, but its real-world changing-label evaluation lacks node features and its model does not detect or adapt to shifts.Source: §2.1 · p. 3
• Existing dynamic graph benchmarks do not foreground categorical node-label change; TGB’s node-level task predicts future interaction affinity rather than changing labels.The paper constructs behavior-derived benchmarks and evaluates shifters separately from stable nodes.Source: §2.1 · p. 3

2.2 Distinction from Distribution Shift on Graphs

• Unlike distribution-shift methods that seek invariant representations across training and deployment contexts, the shifter problem concerns known nodes changing labels across observed time steps.The described distinction is temporal inertia within the observed graph, rather than unfamiliar structure.Source: §2.2 · p. 3

3 Preliminaries and Datasets

• A dynamic graph is represented as discrete snapshots containing nodes, edges, node features, and labels; a node is considered across consecutive snapshots when defining label shifts.The node set may evolve, with new nodes appearing and inactive nodes retained with zero degree.Source: §3 · p. 4
• Training, validation, and test data are contiguous non-overlapping windows ordered in time, and test-time information is unavailable to models.At test time, models predict labels for all nodes in each test snapshot.Source: §3 · p. 4
• Three benchmarks derive labels from observed behavior and allow them to shift naturally: yearly researcher fields, weekly fake-news consumption, and monthly listener genres.They represent co-authorship (DBLP-S), news co-consumption (GossipCop), and music co-listening (Music).Source: §3 · p. 4

4 Diagnosing the Shifter Gap

• Shifter accuracy and F1 lag stable-node counterparts by up to 50%p and 55.1%p, respectively, across seven models and three datasets.Figure 2 also shows the gap across models and datasets and that shifter errors predominantly stick to the previous label.Source: §4 · pp. 4–5, Figure 2 · p. 5
• All four structural signals distinguish shifters from stable nodes, but only homophily meaningfully separates correctly from incorrectly classified shifters.Feature and neighborhood drift do not meaningfully distinguish correctness within the shifter group; incorrectly classified shifters have lower current and higher previous homophily.Source: §4 · p. 5, Figure 3 · p. 5
• Embedding inertia occurs when neighborhood aggregation anchors shifter representations to the old-class centroid, most strongly with low current and high previous homophily.Correctly classified shifters show positive centroid displacement, while incorrectly classified ones show displacement near zero or below.Source: §4 · p. 5
• On Music, shifters misclassified as their old class lie closer to that class than to their true new class, unlike shifters misclassified as another class.The reported cosine similarities are 0.84 to the old class versus 0.78 to the true new class for old-label errors; other-class errors lie closest to their predicted class.Source: §4 · p. 6
• The analysis motivates correcting shifter embeddings toward the new class, detecting shifts from structural signals, and giving the classifier an explicit signal to override old-label predictions.Correction should be stronger where homophily is least supportive.Source: §4 · p. 6

5 CHASE: CHange-Aware Framework for Shifting NodEs

• CHASE wraps a dynamic GNN without modifying its encoder and adds three targeted components to its classification pipeline.The components are a homophily-guided contrastive loss, a change detection head, and a change-aware classifier.Source: §5 · p. 6, Figure 4 · p. 6

5.1 Homophily-Guided Contrastive Loss

• The homophily-guided contrastive loss pulls shifter embeddings toward the new-class centroid and away from the old, weighting correction more strongly at low current homophily.The loss is applied during training, when current labels are available; its margin is 0.5 across experiments.Source: §5.1 · p. 6

5.2 Change Detection Head

• The change detection head estimates shift probability from concatenated structural signals, using a prediction-based proxy for previous homophily to avoid label leakage.Current homophily is excluded from this head because it requires current labels, the prediction target.Source: §5.2 · pp. 6–7

5.3 Change-Aware Classifier

• The change-aware classifier combines the neighbor-aggregated embedding, an aggregation-free projection of node features, shift probability, and the previous prediction.The change signal helps the classifier learn when to override a prediction that may still point to the old class.Source: §5.3 · p. 7

5.4 Training Objective

• CHASE combines classification, homophily, and change-detection losses, trains jointly with the backbone, and uses only the detection head and classifier at inference.Test-time inputs come from node features, graph structure, and the model’s previous predictions, without ground-truth labels from test snapshots.Source: §5.4 · p. 7

5.5 Model-Agnostic Design

• CHASE replaces only the classifier head, and “model-agnostic” means the backbone can vary rather than that a frozen pretrained model is wrapped.All backbones use the same two-layer MLP classifier.Source: §5.5 · p. 7

6.1 Setup

• The evaluation covers three real-world datasets, seven dynamic GNN baselines, and static baselines in collapsed and sequential training settings, using five seeds and shifter/stable accuracy and macro F1.CHASE is also reported to improve static baselines, so its benefit is not contingent on temporal modeling.Source: §6.1 · pp. 7–8, §6.2 · p. 8

6.2 Main Results

• Across all 21 dynamic backbone–dataset combinations, CHASE improves shifter performance by up to 114.9% on accuracy and 202.5% on F1 while generally preserving or improving stable-node performance.The shifter–stable performance gap also narrows by up to −73.0%.Source: §6.2 · p. 8, Table 2 · p. 8, Figure 5 · p. 8

6.3 Ablation Study

• Every CHASE component contributes monotonically to shifter performance, with the largest single jump when the change-detection head is added.Without its pchange signal, the classifier can deviate from old predictions but lacks a cue for when to do so.Source: §6.3 · p. 9

6.4 Further Analysis

• CHASE’s relative shifter gains are largest at the lowest current homophily and decrease monotonically as homophily rises, matching the condition where embedding inertia is most severe.The reported alignment links the empirical gains to the analysis-driven design.Source: §6.4 · p. 9
• On five-class Music, CHASE reduces shifter error, and its gains are largest for shifts away from the dominant class, moderate between non-dominant classes, and smallest toward it.This pattern distinguishes genuine movement toward correct labels from merely suppressing the old label; baseline accuracy is lowest for shifts away from the dominant class.Source: §6.4 · p. 9
• CHASE’s gains concentrate on inertial shifters, reaching up to +40.1%p, while corrected shifters’ centroid displacement moves from −0.19 to +0.09.Already-correct shifters remain on the new-class side, shifting from +0.27 to +0.19; non-inertial shifters show no gain.Source: §6.4 · pp. 9–10, Table 4 · p. 10

• Shifters are classified substantially worse than stable nodes, with errors concentrated on the old label, across major dynamic GNN architectures.The paper attributes this failure to neighborhood aggregation anchoring representations to the old class.Source: §7 · p. 10
• CHASE counters embedding inertia with a homophily-guided contrastive loss, a change-detection head, and a change-aware classifier.It is model-agnostic and improves shifter performance across tested backbone–dataset combinations while preserving stable-node performance.Source: §7 · p. 10
• The work contributes three dynamic graph benchmarks with naturally shifting labels to address a gap in existing evaluation resources.Source: §7 · p. 10

8 Limitations and Future Work

• Binary shift labels leave gradual transitions untreated until nodes cross the labeling threshold.The contrastive loss and detection head therefore do not act on nodes approaching the decision boundary, allowing embedding inertia to accumulate before a shift is registered.Source: §8 · p. 10
• Current detection targets shifts at time t, not prediction at t+1.The authors propose combining transition-intensity scores with forward-looking detection as a step toward early-warning systems.Source: §8 · p. 10
• Discrete snapshots limit the granularity of transition-intensity measurement and the temporal resolution of anticipatory detection.The proposed continuous-time extension would compute drift over sliding windows, use neighbors’ latest predictions, and output change probabilities per event.Source: §8 · p. 10

A Dataset Construction Details

• DBLP-S spans 14 yearly snapshots from 2005–2018, with 34,717 authors connected by yearly co-authorship and labeled by whether Computer Networks or Machine Learning dominates their publications.Authors’ 768-dimensional features use BERT embeddings of paper titles and abstracts; the node pool evolves as authors enter and inactive authors become isolated.Source: A Dataset Construction Details · p. 15
• GossipCop spans 37 weekly snapshots from November 2017–July 2018 and 6,091 users, connected by co-consumed articles and labeled fake-news consumers when over half of weekly engagements are fabricated.Users must have engaged with at least three articles; 768-dimensional features average BERT embeddings of their engaged articles.Source: A Dataset Construction Details · p. 15
• Music spans 24 monthly snapshots from January 2007–December 2008 and 878 listeners, connected by co-listened tracks and labeled by their month’s dominant genre across five classes.Its 779-dimensional features combine semantic tag embeddings, audio properties, popularity signals, and listening-behavior features.Source: A Dataset Construction Details · p. 15

B Extended Diagnostic Analysis

• Across models and datasets, homophily signals distinguish correctly from incorrectly classified shifters, while drift signals lose discriminative power.The reported homophily pattern is high current and low previous homophily for correctly classified shifters, and the reverse for incorrectly classified shifters.Source: B Extended Diagnostic Analysis · p. 16, Figure 8 · p. 17, Figure 9 · p. 18
• Correctly classified shifters generally have positive centroid displacement, whereas incorrectly classified shifters generally have negative displacement across models and datasets.The figure breakdowns are presented as demonstrating that the Section 4 findings are not limited to specific cases.Source: B Extended Diagnostic Analysis · p. 16, Figure 10 · p. 18

C.1 Pseudocode

• The forward pass takes a snapshot graph, current and previous features, and previous edges, and returns predictions, updated hidden state, and change probabilities.Training combines classification, homophily, and change-detection losses; structural signals and current homophily weights are precomputed, while the previous-homophily proxy is computed per forward pass.Source: B Extended Diagnostic Analysis · p. 19, §C.1 · p. 19

C.2 Computational Complexity

• CHASE adds O(n · d · dh + |E(t−1)| · C) overhead per snapshot, while the base encoder cost is unchanged.The one-time precomputation cost is O(Ttrain · (e · d + n · d)); the authors report that these costs are a small fraction of multi-layer message passing.Source: §C.2 · p. 19

D.1 Baselines

• The evaluated baselines include static GCN and EERM protocols, plus dynamic architectures such as GCN-GRU, EvolveGCN, DySAT, GCN-SE, IDGNN, TADGNN, and SiGNN.Sequentially trained static backbones are also compared with and without CHASE augmentation.Source: §D.1 · p. 20

D.2 Implementation Details

• All models use Adam, early stopping on validation F1, temporally split snapshots, and the same classifier architecture for fair CHASE comparisons.Training runs for up to 500 epochs with patience 10; the experiments use PyTorch 2.2.1 and CUDA 11.8 on one NVIDIA RTX A6000 GPU.Source: §D.2 · p. 20
• CHASE uses 2-layer MLPs with hidden dimensions 32 for change detection and 128 for the change-aware classifier, with λhom = λchange = 0.1 and margin m = 0.5.The self-projection maps input features to hidden dimension 128; the stated hyperparameters are used across CHASE-augmented experiments.Source: §D.2 · p. 20
• Table 5 reports full results with standard deviations across five seeds, while Table 6 reports test-snapshot AUROC for shifter detection.The captions specify percentage points for Table 5 and AUROC percentage for Table 6; no cell values are supplied here.Source: Table 5 · p. 21, Table 6 · p. 21

E Full Numerical Results

• Table 7 compares shifter F1 for CHASE and a rule-based variant, averaged across backbones.Source: Table 7 · p. 21
• Baseline standard deviations are consistently higher than their +CHASE counterparts, indicating more stable training with CHASE.Table 5 reports standard deviations corresponding to the main results in Table 2.Source: E Full Numerical Results · p. 21
• Table 5 reports standard deviations corresponding to the main results in Table 2.Source: E Full Numerical Results · p. 21

F.1 Analysis on pchange

• Shifter-detection AUROC for pchange reaches 97.4%, and CHASE outperforms a rule-based variant across the tested binary and multiclass datasets.The rule-based variant improves over unmodified baselines on DBLP-S and GossipCop but degrades considerably on Music, showing that detecting a shift alone does not identify the new class.Source: §F.1 · p. 21

F.2 Improvement by Number of Shifts

• CHASE’s relative shifter-F1 improvement increases with the number of label shifts, even as baseline shifter F1 generally decreases.The analysis groups nodes by one, two, or at least three shifts during the test window and averages across seven dynamic backbones.Source: §F.2 · p. 22, Figure 11 · p. 22

F.3 Per-Snapshot Consistency and Comparison with Retraining Baselines

• CHASE consistently achieves the highest shifter and stable F1 across test snapshots, outperforming retraining baselines that use previously observed ground-truth labels.Its improvement is distributed across time rather than concentrated in particular snapshots; retraining does not always help the baselines.Source: §F.3 · p. 22, Figure 12 · p. 22

F.4 Hyperparameter Sensitivity

• CHASE’s shifter accuracy and F1 remain stable across all tested values of λhom, λchange, and m on GCN-GRU.The defaults are 0.1, 0.1, and 0.5, respectively; each hyperparameter was varied independently across three datasets.Source: §F.4 · p. 23, Figure 13 · p. 23

F.5 Case Study

• In a Music case study, CHASE detects a shifter whose embedding remains anchored to its old class and moves its prediction to the new class, while leaving a stable node correctly classified.For the shifter, pchange = 0.83 and the classifier changes ∆c by +0.24, turning it positive; the stable node triggers no change signal.Source: §F.5 · p. 23, Table 8 · p. 23

F.6 Robustness to Incorrect Previous Predictions

• With incorrect previous predictions, CHASE’s effect is dataset-dependent: performance degrades modestly on binary datasets but still improves substantially on multiclass Music.On binary data, lower hproxy can reduce pchange and curb shifts from a wrong prior prediction; on Music, hproxy is less affected and other classifier inputs help identify the new class.Source: §F.6 · pp. 23–24, Table 9 · p. 24

F.7 Robustness to Input Noise

• Under feature and edge noise, CHASE is more robust than the baseline across datasets, retaining a substantial advantage at noise level α = 0.5.The authors attribute this to structural drift signals remaining discriminative because they measure relative change between snapshots.Source: §F.7 · p. 24, Table 10 · p. 24, Figure 14 · p. 25

F.8 Computation Overhead

• CHASE adds approximately 0.24–0.50 seconds per epoch in the reported configurations, or under a minute over 100 epochs in the worst case.Precomputation takes 15.1 seconds on DBLP-S, 8.1 seconds on GossipCop, and 1.5 seconds on Music; on a synthetic million-node graph, it adds 15.2 seconds per epoch, 635 MB peak GPU memory, and 377.3 seconds of precomputation.Source: §F.8 · pp. 24–25

NeurIPS Paper Checklist

• The authors report no high-risk misuse concerns and say they have cited the existing assets used in the paper.They also state that their source code is provided and well documented, with implementation and dataset-construction details in the appendix.Source: NeurIPS Paper Checklist · pp. 30–31
• The paper states that it involves neither crowdsourcing nor research with human subjects.The authors mark both the human-subjects and IRB checklist questions as not applicable.Source: NeurIPS Paper Checklist · p. 31
• The authors state that LLMs are not part of the model or core method.They mark the LLM-usage declaration as not applicable.Source: NeurIPS Paper Checklist · p. 32