When Labels Go Stale: Reach-Aware Label Acquisition on Evolving Graphs

When only a handful of nodes in a network can be labeled by hand, which nodes you choose matters enormously. A graph neural network spreads each label along edges, and a well-placed label informs a large region of the graph. On a graph that keeps changing, a label that once covered a large region can quietly stop reaching anything useful. The natural shortcut is to treat highly connected nodes, the hubs, as the most informative. That shortcut rests on the degree of a node, meaning its number of edges. A long line of network-science results shows that degree is a poor guide to how far anything spreads: two graphs with exactly the same degree for every node can have percolation thresholds (the edge-retention level at which a giant connected component appears) anywhere from about 0.618 down to 0 (Zhou et al.).

This note proposes treating label acquisition on an evolving graph as a coverage-maintenance problem. We track, cheaply and incrementally, how far each already-acquired label actually propagates. New labels are requested only when that propagation reach decays, and they go to the nodes that restore the most reach. The claim that makes this worth testing is that reach can collapse while every degree-based signal stays exactly constant. Methods that choose, rewire, or detect drift by degree are therefore blind to the failure this method is built to catch.

Core Claim

In label-scarce dynamic node classification, the value of a label is not fixed at acquisition time. It decays as the structure around it rewires, and the rate of decay is governed by mesoscale connectivity rather than by degree. A policy that monitors the propagation reach of the labeled set and spends a fixed labeling budget reactively should beat two kinds of policy at equal budget. The first spends labels on a fixed schedule. The second triggers on degree statistics. The gap should be largest when the graph drifts in degree-preserving ways.

The novelty is not a new classifier. It is the acquisition policy: when to spend labels over time, and on whom, under structural drift. The existing work that touches this intersection handles neither question. L2DGCN fights degree bias under 3- to 10-shot labeling by pruning hub edges and grafting feature-similar edges onto low-degree nodes. It is static and purely degree-driven. CurvPrompt adapts few-shot dynamic models by routing nodes to curved-geometry experts using local neighborhood signals. It never decides which nodes get labeled. TMetaNet uses zigzag persistent homology, a technique that tracks cycles and voids across snapshots, to modulate a single global learning rate for link prediction. It has no node-level supervision budget. The two graph active-learning methods, RIM and FeatProp, pick propagation-central nodes but assume one fixed graph. They say nothing about when a previously good label has gone stale.

Why Degree Is the Wrong Monitor

The motivating evidence comes from network science. Statistical Connectomics formalizes that distinct topologies share identical low-order summaries. Zhou et al. build a deterministic family of scale-free graphs with an identical degree sequence, indexed by a rewiring parameter $q$. Along that family, percolation threshold and average path length move from a large-world regime to a small-world one. Fractal scale-free networks resistant to disease spread shows fractal wiring alone can make spreading thresholds nonzero. Label propagation in a message-passing network is a spreading process, so these results transfer directly: a node's label influence can shrink by orders of magnitude with no change to its degree.

L2DGCN supplies the complementary observation that scarce labels starve low-degree nodes. It diagnoses that starvation by degree, however, which is exactly the statistic the network-science results say is insufficient.

Research Program

The central object is an approximate personalized PageRank vector $\pi_t(u,\cdot)$ for each labeled node $u$ at time $t$. This vector gives the stationary probability that a random walk restarting at $u$ sits at each other node, and it is a standard proxy for how strongly $u$'s label reaches them. We define the coverage of labeled set $L$ as

$$\mathrm{Cov}_t(L) = \frac{1}{|V_t|}\,\Big|\{v \in V_t : \max_{u\in L}\pi_t(u,v) \ge \epsilon\}\Big|,$$

where $V_t$ is the node set at time $t$ and $\epsilon$ is a reach threshold tuned once on a validation stream. PageRank vectors can be updated locally when edges arrive or disappear, because each edge event only perturbs probability mass near its endpoints. Maintaining coverage therefore costs work proportional to the local change, not a full re-propagation. This is the incremental update that FeatProp's precomputed smoothed features lack, and the same staleness that LD2 and Node Dependent Local Smoothing suffer on changing graphs.

The acquisition policy has two parts. The trigger fires when coverage falls a set fraction below its value after the last acquisition, or when newly arrived nodes are uncovered. The selector greedily adds nodes that maximize marginal coverage gain multiplied by a reliability factor borrowed from RIM, which down-weights nodes whose neighborhood disagrees with them. Coverage is a submodular set function (adding a node helps less when the set already covers its region), so greedy selection keeps the usual constant-factor guarantee within each acquisition round. The total budget $B$ over the whole stream is fixed and identical for every policy.

The downstream classifier is held fixed across policies so that only acquisition differs. We use two classifiers. One is a TGN backbone (Temporal Graph Networks). The other is plain time-decayed label propagation, which tests whether gains depend on a learned model.

The analysis half of the program builds a controlled benchmark in which drift is degree-preserving by construction. We start from Zhou et al.'s $q$-family, and from stochastic block models with planted class communities. We then evolve each graph over time with double-edge swaps. A double-edge swap takes two edges (a,b) and (c,d) and replaces them with (a,d) and (c,b), which leaves every node's degree unchanged. We schedule these swaps so that $q$ drifts, or so that community boundaries dissolve and reform. On this benchmark every degree-based trigger records zero change, while true label reach, which we can compute exactly, moves substantially.

Baselines

The naive reference points are two. The first spends the budget uniformly at random over nodes and time. The second spends it all at the first snapshot, choosing the nodes with RIM, and never re-queries. Together they establish whether re-acquisition matters at all.

The degree baseline selects by degree centrality and re-queries whenever degree-distribution moments shift. This is the reviewer's first instinct. FeatProp and RIM already report it losing on static graphs, and it is the baseline our controlled benchmark is designed to expose.

The strongest existing competitor is snapshot-recomputed RIM. It runs RIM from scratch on each snapshot and spends $B$ evenly across snapshots. It uses the same reliability term we reuse, so it isolates exactly what our trigger adds, and it is the method a careful practitioner would actually deploy. We also run snapshot FeatProp, and L2DGCN-style degree rewiring applied per snapshot on top of RIM selection. For L2DGCN we recall its reported 78.50% accuracy in 3-shot Cora, and we reproduce that static number before using it dynamically as a sanity check. All methods receive the same streams, the same total label budget, the same classifier, and the same hyperparameter search budget of equal trials on a held-out validation stream. Beating snapshot-RIM means higher time-averaged macro-F1 at equal $B$ with non-overlapping confidence intervals over seeds, or equal accuracy at substantially lower acquisition compute.

For TGB node affinity we include Moving Average, which reports NDCG@10 of 0.559 on tgbn-reddit against TGN's 0.315 (TGB). No reported result was found on Lacuna for TGN's absolute dynamic node classification score on Wikipedia or Reddit, so those baselines are rerun rather than quoted.

We also include a topological-trigger baseline in the spirit of TMetaNet, which fires acquisitions on zigzag-persistence change. Two ablations isolate our ingredient. The first swaps reach for degree in both trigger and selector. The second keeps reach-based selection but uses a fixed schedule.

Why not just…?

Why not just label the highest-degree nodes and re-query when the degree distribution shifts? On static graphs this already loses to propagation-based selection, per FeatProp and RIM, and RIM shows hubs amplify label noise. Under drift, the controlled benchmark makes the failure structural: degree-preserving swaps leave the trigger silent by construction. The honest caveat is that real streams may rarely drift this way. We therefore measure, on each real dataset, how much of the observed reach change is unexplained by degree change. If that fraction is small, the degree baseline is adequate there, and we will say so.

Why not just rerun RIM on every snapshot with an even budget? This is the real threat. RIM already scores nodes by multi-hop reach rather than raw degree, so it may choose nearly the same nodes we do. Our method can only win on timing, spending labels when coverage actually decays rather than on a clock, and on cost, through local updates. The fixed-schedule ablation settles this directly. If reach-based selection on a fixed schedule matches the triggered version, timing is irrelevant, and the contribution reduces to an efficiency result. We would report it as that.

Why not just use persistent homology to detect drift, as TMetaNet does? Homology is more expressive than degree, and Topological Strata of Weighted Complex Networks shows it separates structures that degree cannot. But it answers a different question: did global topology change, rather than did my labels stop reaching nodes. It is also expensive; TMetaNet reports 14% to over 200% added training time. If the homology trigger beats reach at equal budget, it means label value depends on structure that random-walk reach misses, which would itself be a finding worth reporting.

Why not just skip labels and use Moving Average or EdgeBank? For node-affinity tasks this may simply win, as TGB shows. Our claim is confined to semantic labels such as bans and dropouts that history heuristics cannot predict, and we report the heuristic wherever it applies.

Proposed Experiments

The decisive synthetic test uses the degree-preserving drifting $q$-family and the drifting block models, with 3 to 10 labels per class and a fixed total budget. The prediction is sharp. Degree-based policies are flat in what they select as $q$ drifts, yet their accuracy degrades. Snapshot-RIM partially recovers. Reach-triggered acquisition tracks the exactly computed coverage and retains accuracy. We will plot accuracy against true label reach to check that reach, not degree, explains the variation across policies.

On real streams we use four node-level tasks. Two are the dynamic node classification labels on Wikipedia and Reddit used by TGN. The third is MOOC dropout prediction as in JODIE. The fourth is tgbn-reddit and tgbn-genre from TGB. For each we report time-averaged macro-F1 or AUC, or NDCG@10 for TGB, against labels spent. We also report acquisition wall-clock time against snapshot-RIM, and variance across seeds, since CurvPrompt flags high variance as the defining difficulty of few-shot dynamic node classification.

Three outcomes would falsify the core claim. The first is snapshot-RIM matching our method at equal budget on the real streams. The second is the fixed-schedule ablation matching the triggered version. The third is reach failing to track accuracy on the controlled benchmark. Any one of these would show that the timing of acquisition, the ingredient this proposal adds, does not matter.