Graph forecasting systems often rely on prediction intervals to quantify uncertainty across connected locations, but the true outcomes needed for evaluation may be only partially observed. We study how an auditor can selectively retrieve missing outcomes to determine whether there exists a connected group whose outcomes violate the same side of their respective forecast intervals. The audit stops when the observed labels determine the event or the query budget is exhausted. On three public graph time series, MOMS reduces mean queries by 19.6% to 38.5% relative to screened random acquisition when 30% of labels are hidden. Under localized masking on METR-LA, shortest witness finds more positive cases within ten queries, although the difference depends on node ordering. Direct component traversal reproduces all 9,696 screened random traces without enumerating connected subsets. The experiments show that reducing queries to a decision does not necessarily improve early event discovery or reduce local computation.
Figures & tables
Figure 1: Illustrative certificate audit. Symbols distinguish known interval labels ( + , 0 ) from unknowns ( ? ). Retrieved labels update compatible witnesses until presence or absence is established, or the budget is exhausted.
Dataset
Mask
Screened random
MOMS
Shortest witness
Shortest pool
JW
WikiMaths64
Random
3.389
2.287
2.563
2.289
2.305
Localized
12.977
7.974
8.650
7.988
8.014
METR-LA
Random
35.997
25.761
29.252
25.856
26.174
Localized
51.763
41.618
44.401
41.756
42.035
MontevideoBus
Random
18.019
14.432
18.535
14.408
14.587
Localized
102.310
67.511
150.621
67.470
67.874
Table 1: Mean queries among initially unresolved audits at 30% masking. All policies use the same exact stopping rule. Lower values indicate fewer queries.
Figure 2: Discovery of hidden connected triples across query budgets under 30% localized masking. Each panel reports positive cases and distinct positive timestamps. Line styles distinguish policies in grayscale. Queries reveal actual withheld labels. Repeated masks do not create independent events.
Dataset / mask
E
C
MOMS
WikiMaths64 / R
0.052
0.071
0.070
WikiMaths64 / L
0.141
0.159
0.243
METR-LA / R
0.583
0.823
1.030
METR-LA / L
2.342
0.976
4.939
MontevideoBus / R
0.263
1.919
0.366
MontevideoBus / L
1.212
8.114
2.510
Table 2: Audit computation in ms: 24 shared cases, 30% masking. R/L: random/localized. E/C: enumerated/component screening. Values are median round means.
Spatio-temporal graph neural networks combine a node's history with information from graph neighbors. The central question is whether graph neighbors provide predictive information beyond each node's own history. Forecast accuracy depends on both the choice of neighbors and the way graph messages enter the temporal model. We study these choices as graph construction and graph exposure on U.S. state unemployment, traffic speed, and electricity demand. Our diagnostic design uses two comparisons: varying exposure while holding the domain graph fixed, and varying construction while holding late gated integration fixed. A GRU using only each node's own history and randomized graph controls help assess what the graph contributes. Under a common change forecasting protocol, the same domain graph can improve or worsen error relative to the GRU across integration designs. Late integration alone is insufficient, while adding a fusion gate yields lower mean error in all three tasks. With late gated integration fixed, a graph based on residual correlations has the lowest mean error among the tested graphs, although randomized graphs perform similarly on unemployment. The findings support evaluating graph construction and integration together, with conclusions tied to the comparisons actually performed.
Confidence estimates guide human review in LLM-built knowledge graphs, but better error prediction can yield little improvement in an audit. We study this gap through repairability, selection headroom and label validity. Modelling non-adaptive auditing as budgeted covering, we characterise the minimal decision-relevant error statistics and bound the regret of scalar-preserving first-order planning by a structural mass Δcl. We simulate ideal repair against benchmark-aligned labels for five extraction configurations and two cross-document graphs on Re-DocRED, followed by frozen confirmation on test and replication on 500 hash-selected training documents. On the held-out cross-document graphs, an error-rate × fan-out queue leaves 3.98-4.74 percentage points more errors than a joint model with the same actions. By comparison, opening shared actions for that joint planner reduces residual errors by 0.89-1.43 points relative to its own fact-only plans, in point estimates. Equivalence between joint and independent-block models remains inconclusive. Generic LLM verification improves three of four model-budget configurations on each held-out set. LLM adjudication identifies possible benchmark omissions.
Zehao Lin, Kai Chen, Xixuan Hao +3
1MemTensor · 3The Hong Kong University of Science and Technology (Guangzhou) · 2Shanghai Jiaotong University
Search-augmented reasoning systems can reach correct answers while making errors in intermediate steps. Reliable auditing must check whether evidence D covers the question Q, reasoning T addresses Q, and T is grounded in D. We introduce GraphRail, which represents requirements, evidence, and reasoning as structured claims and compares them without a generative judge or gold answer. Across three multi-hop QA benchmarks and three reasoning frameworks, GraphRail improves error recall over generative verifiers while remaining stable under stochastic extraction. Its diagnoses can also guide online reasoning, providing a traceable way to detect and correct intermediate errors.