Budgeted Task-Aware Acquisition of Dynamic Networks

• Earlier work studies graph dynamics, partial observation, acquisition cost, or downstream utility separately, while queries can reveal node states, incident edges, and unknown neighbors whose effects overlap through graph propagation.Source: §1 · p. 1
• The paper defines the value of refreshing graph information by its expected downstream-task utility rather than by structural change alone.Source: §1 · p. 1
• In controlled comparisons, downstream task utility provides a more effective supervision signal than graph change for learning acquisition decisions.Source: §1 · p. 1
• Scout instantiates the formulation with a lightweight learned scorer and is evaluated on synthetic and real-world dynamic networks under multiple observation budgets.Source: §1 · p. 1

2.1 Problem Framework

• A query set is valued by its expected improvement in downstream performance, but its utility must be estimated from stale graph information and observation history because current node states are unknown before querying.The updated maintained graph is carried forward to the next time step.Source: §2.1 · p. 2

2.2.2 Maintained-Graph Encoder.

• Scout constructs node features from stored states, query history, temporal uncertainty, maintained neighbors, and task-model signals, then applies graph convolutions with skip connections to produce node representations.A shared scoring MLP maps each node representation to an acquisition score.Source: §2.2 · p. 2, §2.2.2 · p. 2

2.2.3 Task-Utility Learning.

• Training targets come from singleton counterfactual queries: their task-score improvements are standardized, then used in regression and ranking losses.Counterfactual observations construct training targets but are unavailable to Scout at inference time.Source: §2.2.3 · p. 2
• Scout adds a staleness bonus to learned acquisition scores and selects the budgeted number of known nodes with the highest adjusted scores.The bonus encourages occasional exploration of nodes that might otherwise remain unqueried.Source: §2.2.3 · p. 2

2.2.5 Query Execution with Graph Update.

• After selection, Scout queries each chosen node, incorporates the returned observations into the maintained graph, and carries the updated graph forward.Existing queried nodes have their observation times updated.Source: §2.2.5 · p. 2

3.1 Experimental Setup

• The evaluation uses drift_sbm for node classification and four SNAP networks for link prediction, with nine acquisition baselines and multiple query budgets.Training, validation, and test episodes use disjoint graph instances or temporal windows.Source: §3.1 · p. 3

3.2 Budgeted Acquisition Performance

• Despite smaller gains on Reddit and MathOverflow, Scout remains strongest on MathOverflow across budgets; uncertainty-based acquisition leads Reddit at 5% (0.785 versus 0.780 AUC).The reported margins over baselines are modest on both networks.Source: §3.2 · p. 3
• Scout achieves the highest mean performance in 19 of 21 benchmark–budget settings.Figure 2 covers node-classification accuracy on drift_sbm and link-prediction AUC on four real-world networks.Source: §3.2 · p. 3, Figure 2 · p. 4

3.3 Ablation Study

• Task-utility supervision beats structural-change supervision in 13 of 16 real-world settings, while scorer capacity shows no consistent performance relationship.The ablation compares Scout with 39- and 321-parameter scorers; capacity-related results are mixed.Source: §3.3 · p. 3, Table 1 · p. 4

3.4 Task Dependence of Acquisition

• Task-matched training improves link-prediction AUC by 0.012–0.016 and node-classification accuracy by 0.064–0.090 across budgets.The comparison uses Scout trained on the same task versus Scout trained on the other task.Source: §3.4 · pp. 3–4

4 Discussion and Conclusion

• Downstream utility provides a more effective acquisition signal than structural graph change, and scorer capacity does not explain Scout’s gains.The discussion also distinguishes task-aware acquisition from generic graph monitoring or change detection.Source: §4 · p. 4
• The formulation assumes singleton query utilities, unit query costs, an initially observed graph, and a task-specific acquisition model.Singleton utilities approximate individual-query value but do not model interactions among multiple queried nodes.Source: §4 · p. 4
• The conclusion frames learning downstream utility as a way to allocate limited observation budgets more effectively on dynamic networks.The paper presents this as a general direction for resource-constrained learning on dynamic graphs.Source: §4 · p. 4