- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies neural algorithmic reasoning when graph inputs are noisy or partially observed. Instead of using a single adjacency and weight matrix, UANAR represents each graph through statistics from repeated noisy observations: mean edge weights, weight variances, and edge-existence frequencies. The method introduces a gated encoder with separate pathways for weight and structural uncertainty, uncertainty information in intermediate hints, and an additional loss that penalises confident incorrect predictions. The models are trained to recover algorithm outputs on the underlying clean graph. Experiments cover Floyd–Warshall, Bellman-Ford, Dijkstra, and Prim under weight corruption, missing edges, spurious edges, and combinations of these conditions. The paper reports improvements in accuracy and calibration, including comparisons where methods receive the same number of observations.
Critical strengths
- The paper addresses a relevant limitation of neural algorithmic reasoning. Good performance on clean graphs does not establish that a model can recover useful answers from corrupted observations. Examining weight noise, missing edges, and spurious edges across four algorithms makes this problem concrete.
- The equal-information comparison is a useful control. Table 5 shows that aggregation and denoising recover much of the performance lost by the deterministic baseline, but UANAR still improves over the denoising pipeline. This provides stronger evidence than a comparison against a single noisy input alone.
- The paper acknowledges the limitations of the observation setting. Section 8.6 makes clear that repeated observations or a reliable noise model are needed and that single-observation deployment remains difficult.
Critical weaknesses
-
The contribution beyond learning from repeated observations needs stronger isolation. Table 4 shows that U-Base, which uses the belief inputs without the proposed additions, already increases mean accuracy significantly. This is a substantial result, but it also means that much of the headline improvement comes before the uncertainty-aware architectural components are added. Table 5 addresses this concern with equal-information baselines and shows a further improvement over denoising. However, that detailed comparison covers one Floyd-Warshall mixed-noise setting. The broader results would be more convincing if the strongest matched-information comparator were used consistently across algorithms and noise conditions. As presented, the evidence for richer observation statistics is stronger than the evidence for propagating uncertainty through the reasoning process.
-
The probabilistic interpretation of the graph representation needs more care. Eq. 2 defines as the frequency with which an edge appears in corrupted observations. This is not directly the probability that the edge exists in the underlying clean graph; that interpretation depends on the false +ve and false -ve processes. Likewise, observed weight variance measures variability in the measurements, rather than uncertainty in the estimated clean weight itself. Section 4.3 describes these quantities as separating aleatoric measurement uncertainty from epistemic structural uncertainty, but that distinction is not established by the construction. The representation can still be useful empirically. My concern is that the description as probabilistic inference over beliefs is stronger than what these statistics alone justify.
-
The calibration objective is an error-dependent confidence penalty, and its connection to calibration is insufficiently explained.
-
The uncertainty-propagating hints are not defined precisely enough. Since uncertainty propagation is one of the main proposed contributions, these details are necessary to assess the mechanism and reproduce it.
-
The headline architecture is difficult to identify from the main results. Table 4 reports several variants but does not include a model combining all three proposed additions. Different variants also perform best under different metrics. Meanwhile, Tables 2 and 3 report “UANAR (Ours)” without making the configuration explicit. I cannot tell from the main paper whether this denotes one fixed architecture or a configuration selected separately for each algorithm.
Questions for authors
- What is the standard deviation in Equation 9 calculated over, and where does the resulting quantity enter the next reasoning step?
- Is intended only as an empirical observation frequency, or as an estimate of clean-edge probability? If the latter, how are the corruption rates accounted for?
- Are comparisons against the strongest equal-information denoising baseline available beyond the Table 5 setting? These would help establish how broadly the improvement extends beyond observation aggregation.