In the world of graph-based forecasting—think traffic networks, power grids, or social media trends—we rely on prediction intervals to tell us how much to trust a model. But what happens when the ground truth data needed to verify those forecasts is missing?
A new paper from researchers at the Missouri University of Science and Technology, titled "Sequential Auditing of Connected Forecast Errors under Partial Observations," tackles this problem. They propose a framework for "auditing" these systems by strategically querying missing data to find clusters of errors.
TL;DR
The paper introduces a sequential strategy to efficiently detect connected clusters of forecast errors when ground truth data is only partially available. By adapting Boolean function evaluation techniques like MOMS, the authors show they can reduce the number of data queries required to reach a definitive audit decision by up to 38.5%.
What Problem Does This Paper Address?
In many real-world networks, an isolated forecast error might be a fluke, but a connected group of errors is often a sign of a systemic issue or a significant regional event. The authors define an "event of interest" as a connected subgraph of at least $k$ nodes where every node violates its forecast interval in the same direction (e.g., all nodes are significantly higher than predicted).
The challenge is that ground truth data is often incomplete. An auditor must decide which missing labels to "query" (retrieve at a cost) to determine if such an event exists. The goal is to reach a binary decision—"Yes, an event exists" or "No, it is impossible for one to exist"—with the fewest queries possible.
Methods
The authors frame the audit as a four-step sequential process:
- Observe: Start with known labels and identify "hidden" nodes.
- Form Witnesses: Identify "witnesses"—potential connected sets of size $k$ that haven't been contradicted by existing data.
- Query: Use a selection policy to pick the next node to reveal.
- Decide: Stop if a witness is fully confirmed or if all possible witnesses are ruled out.
The core contribution lies in the Query Policies. They adapt several established rules from Boolean satisfiability (SAT) and active learning:
- MOMS (Maximum Occurrences in clauses of Minimum Size): Prioritizes nodes that appear most frequently in the smallest potential error clusters.
- JW (Jeroslow-Wang): A weighted version of MOMS that considers all potential clusters, giving more weight to smaller ones.
- Shortest Witness: A greedy heuristic that focuses on the cluster closest to completion.
- Screened Random: A baseline that queries nodes randomly, but only if they are part of at least one potential error cluster.
Datasets
The researchers evaluated their methods on three public graph time-series datasets:
- METR-LA: Traffic speeds on Los Angeles highways (207 nodes).
- WikiMaths: Daily page views for math-related Wikipedia articles (64 nodes).
- MontevideoBus: Bus traffic data from Uruguay (675 nodes).
They simulated missing data using both Random Masks (uniform missingness) and Localized Masks (where missing data occurs in clusters, mimicking sensor array failures).
Key Insights and Ideas
- Decision vs. Discovery: There is a trade-off between reaching a final decision quickly and discovering positive cases early. While MOMS is excellent at minimizing the total number of queries to close an audit, the "Shortest Witness" policy is often better at finding an actual error cluster within a very tight budget (e.g., under 10 queries).
- The Power of Screening: Simply ignoring nodes that cannot possibly contribute to a connected error (Screened Random) significantly outperforms pure random sampling.
- Computational Overhead: Smart querying reduces the "cost" of data retrieval but increases local computation time. The authors found that for large graphs like MontevideoBus, calculating the optimal next query can be more computationally expensive than simpler graph traversal methods.
- Sensitivity to Ordering: The performance of these heuristics can be sensitive to how nodes are indexed in the graph, suggesting that the "structure" of the search space is as important as the algorithm itself.
Key Results
- Query Reduction: MOMS reduced the mean number of queries by 19.6% to 38.5% compared to the Screened Random baseline when 30% of labels were hidden.
- Early Discovery: On the METR-LA dataset with localized missing data, the Shortest Witness policy discovered 29 out of 52 hidden positive cases within just 10 queries. In contrast, MOMS only found 16 in the same budget.
- Efficiency: The authors developed a "component traversal" implementation that allows the auditor to identify relevant nodes without having to explicitly enumerate every possible connected subset of size $k$, which is computationally prohibitive for large $k$.
Limitations and Future Work
The authors acknowledge several constraints in their current model:
- Unit Cost Assumption: The model assumes every data query costs the same. In reality, some sensors might be more expensive or slower to query than others.
- Truthful Retrieval: The audit assumes that once a label is queried, the value returned is 100% accurate. It does not account for noisy or adversarial data.
- Static Snapshots: The current work looks at a single point in time. Future work could extend this to "spatio-temporal" auditing, where errors are connected across both space and time.
For engineers building monitoring systems for infrastructure or large-scale IoT networks, this research provides a principled way to verify system health when you can't afford to see everything at once.
Summary updated