acceptodds
Under review as a conference paper at ICLR 2027

Finite Teaching, Infinite Horizons: Sharp Guarantees for Min-Aggregation

Abstract

We show when errors on a small teaching set certify a learned graph algorithm on unseen graphs and at arbitrary execution lengths. For nonnegative, bias-free min-aggregation networks of arbitrary width, we compute the exact worst-case relative error against Bellman–Ford from the weights alone. Just labeled endpoints identify exact -step execution. With normalized mixing and bounded edge coefficients, their teaching error equals the global error. For shared networks with fixed normalized connections, we determine the optimal error amplification over all execution lengths. It is finite exactly when teaching exposes every eventually observable channel. This factor also guides readout design. For irreducible connections with message channels, an optimized readout achieves one-step amplification within a factor of optimal. Matching hitting and propagation bounds certify multi-step optimality. In three paired fits, adding one teaching graph reduces global errors initially between 19.92% and 47.99% to below 0.163% in every case.

Primary area:
learning theory
Keywords:
Neural Algorithmic Reasoning, Graph Neural Networks, Out-of-Distribution Generalization, Machine Teaching, Shortest Paths

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_tUUkOpenReview ↗
Rating
3(+2)
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper addresses how errors on a small set can certify graph algorithms on unseen graphs and at arbitrary length. The results are restricted to a min-aggregation setting with ReLu or linear updates.

The paper gives a sequence of results regarding generalisation to unseen graphs, to infinite horizons, and addresses how to optimise the readout. The results are illustrated on a toy example.

Critical strengths

The paper delves fairly deeply into theoretical results.

Critical weaknesses

The paper is very difficult to follow. A main issue is that of dimension. Equation (2) seems to give vectors as outcomes, and \gamma_0 in (6) is a matrix, but the paper treats these quantities as one-dimensional.

Moreover there are a number of notions in the paper which are introduced ad-hoc and not explained; see the questions below.

No case is made for the practicality of the approach. Could it be used for certifying GNNs?

Questions for authors

How general is the non-negative, bias-free min-aggregation setting? Could sigmoid readout functions be used? What is meant by bias-free here?

Why is (2) simpler than (1)? Is there some dimension reduction argument?

Equation (2): q_t > 1? are the node values high-dimensional and the edge weights one-dimensional? If everything is one-dimensional then I do not see the key novelty; the arguments could be much simplified. Assuming that these are indeed high-dimensional: Which ordering is used in (4)? Do all components have to be positive? Is 1 supposed to be a vector?

Just before (5): what is a walk here?

(6) If \gamma is a matrix then what is U?

From my understanding the number of nodes is not fixed when taking the infimum and the supremum in (7), or is G supposed to be fixed? If Gamma_K is a matrix then why can we divide by it?

Section 4: what is a K-edge path - a path on K edges or K paths? If the former then why are the paths indexed by j \le K? How does a fixed path clip a large edge coefficient? What is the state coefficient, what is the inner maximum in (12)? What is an error path?

Section 5: What is the state space of the Markov chain? What happened to c in (15)? Which assumptions are needed on SS for the argument to work? What is the signed average, could you write it out to see how positive and negative values cancel out? What do you mean by overestimation?

End of page %: how do these quantities extend to convex functions, in which sense? Do you mean that the results extend to such functions? If so is there a proof?

Theorem 10: what is meant by coverage holding?

End of p.7: What is meant by a connection here? is there a unique chain attaining the bound? Is there assumed to be a unique stationary distribution, and if so, how does that translate into assumptions on A, B, and c?

Section 6: what is a channel-hitting LP? How does this bound the best amplification; what is meant by an amplification here?

Section 7: What is the stationary graph? What are the settings for this example? Is it the one from Appendix I.4? How do periodic constructions enter?

Reviewer_xFYoOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether a small teaching set can guarantee that a learned GNN correctly executes Bellman–Ford on unseen graphs and over arbitrary execution lengths. It derives exact worst-case error bounds, identifies conditions under which finite teaching controls long-term errors, and proposes readout optimization to improve these guarantees.

Critical strengths

1.The paper addresses an important generalization question. 2. This paper provides several strong theoretical results, including exact worst-case error characterization, finite teaching guarantees, and sharp bounds on long-horizon error amplification.

Critical weaknesses

The paper provides theoretical guarantees for readout optimization in Sec 6, but the training experiments in Sec7 do not evaluate its practical effectiveness. It would be helpful to compare the long-horizon errors of models trained with standard and optimized readouts to better demonstrate the benefit of this design.

Questions for authors

See weakness

Reviewer_3KjrOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper tackles the two related questions:

  1. Generalization across graphs: if a network reproduces KK steps of Bellman–Ford on K+2K+2 constructed examples, does it correctly reproduce KK steps on every admissible graph?
  2. Generalization across execution lengths: if the network reproduces Bellman–Ford accurately for KK steps, how much worse can its error become when we run it for more than KK steps?

The paper finds that for the case of nonnegative min-aggregation networks with scalar input and output, it is possible to establish lower and upper bounds from the weights for the underestimation and overestimation (of BF iterations) across every admissible graph. Furthermore, in what seems like a surprising and interesting result, the paper proves that K+2K+2 well chosen examples are sufficient to guarantee correct execution of KK BF iterations. Those examples must be exactly fitted for this main result, for approximate fitting and other technical details, the paper provide further analysis in Theorem 6 for example. The analysis also considers other issues such as infinite horizons.

Critical strengths
  • The problem, approach, and question is highly interesting and relevant.
  • The mathematical contributions are detailed, sound and in some sense surprising. The main theorem seems highly non-trivial.
  • The analysis goes beyond exact identification to address approximate fitting, which is an closer to real-world scenario for learning algorithms and models.
  • The proofs are generally detailed and have interesting connections (e.g. Markov-chain stopping problems).
Critical weaknesses
  1. Restrictive hypothesis class. The guarantees rely on nonnegative, bias-free linear min-agg networks, the connection to this result with broader class of models, even at intuition level, is not obvious.
  2. Limited experimental validation. The experiments use small synthetic architectures, with only three seeds for the paired teaching intervention.
  3. Dense, difficult to follow and unintuitive writting style. Right from the start the paper uses the vocabulary of certification, teaching, horizons, channel exposure, and amplification before providing enough intuition about the actual computational problem. For instance, "teaching set" sounds like an ordinary training dataset, but here it is a specially constructed collection of graph examples designed to identify or constrain an algorithm. And "arbitrary execution lengths" simply means running the same recurrent network for more iterations than those included in its teaching examples. Related to this issue there is also excessive abstraction with phrases such as “finite teaching certifies infinite horizons” obscuring fairly concrete mathematical questions. Words such as certificate, sharp, exposure, alignment, and amplification appear repeatedly, sometimes where simpler mathematical language would be enough.
Questions for authors
  • Is K+2K+2 the minimum teaching-set size required to uniquely identify KK-step Bellman–Ford within this architecture, or could a smaller teaching set suffice?
  • Could the author discuss expressive power versus achievable worst-case approximation guarantees? Given the established connection between message-passing GNNs and the 1-WL test, it would be interesting to understand where the proposed MinAgg architecture lies in this expressivity hierarchy. Furthermore it would interesting to have some discussion if expressivity of the model affect the number of K-steps needed for BF.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.