- 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 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?