Scout
Budgeted task-aware acquisition of dynamic networks — learning which stale graph information is worth refreshing when observing the network is itself expensive.
The problem
On an evolving graph, the graph a model holds is always a little out of date. Changes in the underlying system do not announce themselves — detecting them and refreshing the maintained graph costs observation and computation, so complete updates are impractical under limited resources. The model ends up predicting from a graph in which some nodes, edges and states are stale.
That forces a choice: which stale information to refresh. The usual answer optimizes for freshness — refresh whatever is most likely to have changed. But a query is only worth what the revealed change does for the task you actually care about, and the part of the graph that changed the most is not necessarily the part the task needs.
Core idea — value to the task, not freshness
Scout is a lightweight framework that learns the task value of querying each node, using only what is available before the query is made: the maintained (stale) graph and the history of past observations.
A stale view
The model maintains an observed graph in which every known node carries the time it was last observed. Anything older than the current step may be wrong: a node state, an added edge, a removed edge, or a node that no longer exists.
A score before the answer
A node's current state is unknown until it is queried, so its value has to be estimated in advance — from the stale graph and the observation history alone, never from the answer being bought.
Spend the budget
The queries that fit within the budget go to the highest-scoring nodes. A query returns that node's current state and neighbourhood, which exposes both added and removed edges — and any previously unknown nodes they lead to.
Supervised by utility
The scorer is trained on what a query is worth to the downstream task — not on how much structure it turned out to change. Separating those two supervision signals is exactly what the evaluation isolates.
Key results
The task dependence is measurable, not rhetorical: on the same dynamic network, acquisition matched to the task beats acquisition matched to the other task by 0.012–0.016 link-prediction AUC and by 0.064–0.09 node-classification accuracy.
The code
Released, MIT-licensed, and built so the numbers above can be rebuilt rather than taken on trust.
The repository holds the experiments the paper reports together with the evidence behind them: the 16 checkpoints the reported numbers came from, the result caches the figure and tables read, and a run card for every run recording its configuration, package versions and graph fingerprint. Three commands rebuild the figure and both tables in seconds — no data download, no training, no GPU — and each builder refuses to emit an artefact that disagrees with the others.
Underneath that are rules the code enforces on itself rather than documents: checkpoints selected on validation episodes only, evaluation and training seeds asserted disjoint in time, every comparison paired by seed, a fingerprint guard that refuses to pool results from graphs that are not the same graph, and no silent fallback to random selection when a learned policy has no weights.
Why it matters
Two claims come out of this. Useful graph observations are not a property of the graph alone — they depend on the downstream task. And a limited observation budget is allocated more effectively by learning directly from downstream utility than by chasing structural change. Triad and Highway asked which structure carries the inference with the whole graph in front of them; Scout asks the same question one step earlier — when seeing the graph is itself the thing you cannot afford.
Single-authored work — problem formulation, method, experiments and paper.
Cite
@misc{zhou2026scout,
title = {Budgeted Task-Aware Acquisition of Dynamic Networks},
author = {Zihe Zhou},
year = {2026},
eprint = {2609.05862},
archivePrefix = {arXiv},
primaryClass = {cs.LG},
url = {https://arxiv.org/abs/2609.05862}
}