- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper addresses the exponential growth of scenario trees with the planning horizon in scenario-based multistage stochastic programming (MSP). To tackle this issue, the authors propose MSP-GNN, a graph neural network motivated by the claimed subtree permutation invariance of scenario trees, with the aim of learning first-stage decisions accurately while achieving low prediction error.
Critical strengths
- The paper is easy to read and follow. The writing is clear.
Critical weaknesses
-
The connection between the proposed symmetry motivation and the design of MSP-GNN is unclear to me. I do not see a specific architectural component or adaptation in MSP-GNN that is directly motivated by the claimed subtree permutation invariance. In particular, standard tree/GNN message passing with permutation-invariant aggregation already appears to naturally preserve this type of symmetry. The authors should clarify what additional design choice is introduced specifically because of this observation.
-
More importantly, the current baselines, evaluation metrics, and ablation studies do not appear sufficiently complete. In Table 2, I believe Tree-GCNN, rather than FCNN, could be a strong competitor to MSP-GNN. Tree-based GNNs can also support bidirectional processing and may therefore capture information from both parent and child nodes. The authors’ argument that “we omit Tree-GNN from this experiment because its implementation assumes a balanced tree with a fixed branching factor” is not fully convincing. A balanced scenario tree is still a valid MSP setting, so the authors could construct a balanced-tree benchmark in which both Tree-GNN and MSP-GNN are applicable and provide a fair comparison. I would therefore like to see such a comparison, together with a more informative ablation study involving Tree-GNN.
For the evaluation metrics, I also suggest reporting the objective gap in the main results table. Since the ultimate goal of learning-to-optimize methods is decision quality rather than prediction accuracy alone, the objective gap would provide a more direct and meaningful measure of practical performance. And I also like to see at least one strong baseline from non-learning optimization methods to show the learning methods achieves extreme fast inference performance at the cost of minor optimal gap.
Questions for authors
No other question. expect the authors can clarify the weaknesses above.
7 comments
Thank you for your detailed response and the additional experiments addressing my concerns. I appreciate the authors' efforts. However, I still have three concerns.
- Clarification of the Tree-GNN baseline.
In Section 6 of the original manuscript, the authors state:
"We evaluate MSP-GNN against FCNN, DeepSets (Zaheer et al., 2017), and a bottom-up Tree-GNN baseline (Thost & Chen, 2021)."
However, the rebuttal states:
"Tree-GNN is not an existing scheme from the literature. It is an ablation of our proposed MSP-GNN."
These two statements appear inconsistent. Could the authors clarify whether Tree-GNN is an existing method adapted from the literature or an ablation specifically constructed from MSP-GNN? This distinction is important for evaluating the methodological novelty relative to existing Tree-GNN architectures.
- Limited performance advantage over Tree-GNN.
The additional results show that MSP-GNN actually performs slightly worse than Tree-GNN in the reported comparison (0.045% vs. 0.040%). Moreover, the objective gaps are extremely small(even comparable to solver mip_gap in scale of many settings), making it difficult to establish any meaningful advantage of MSP-GNN over Tree-GNN.
- Problem scale and computational efficiency.
The latest runtime results reported in the rebuttal show that HiGHS solves the problems in just a few milliseconds, with even the largest instance taking only 153 ms. This raises concerns about whether the tested problems are sufficiently challenging. Moreover, at such small runtimes, Python and solver-interface overhead may dominate the measurements, making it difficult to assess the actual computational advantage of the proposed method.
Response to Reviewer SYV5: Part I
Dear Reviewer SYV5,
Thank you for your response and insightful comment. Below, we respond to each point in detail.
C1. Clarification of the Tree-GNN baseline.
Response. Thank you for the comment. We would like to clarify that Tree-GNN is not an existing scheme from the literature. It is an ablation of our proposed MSP-GNN.
Tree-GNN is obtained from MSP-GNN by replacing bidirectional message passing with sequential bottom-up updates, while keeping everything else the same, including the hidden dimension, depth, aggregation, and update functions. Its purpose is to ablate the effect of the bidirectional message-passing scheme.
We cite Thost & Chen (2021) because their work employs a similar bottom-up message-passing scheme. The citation acknowledges bottom-up message passing as an established approach for tree-structured graphs and supports its use as a reasonable ablation choice. However, our Tree-GNN is not an implementation of their method: its architecture and update functions are inherited from MSP-GNN and differ from those of DAGNN. Moreover, DAGNN was not designed for learning first-stage decisions of MSP and cannot be directly applied to this task without constructing an appropriate graph representation of the MSP inputs and adapting its prediction mechanism. The wording in Section 6 did not make this distinction clear, and we have revised it.
Our contribution is not a particular permutation-invariant architecture, but a systematic framework for learning the first-stage solution mapping of MSP. It consists of
- (i) identifying the subtree permutation invariance of MSP,
- (ii) formulating first-stage decision learning as a graph learning problem by constructing a graph representation from MSP inputs,
- (iii) designing architectures that preserve the identified symmetry (with MSP-GNN as a simple and general instance, which uses sum aggregation and bidirectional message passing without restricting information flow to a single direction), and
- (iv) establishing the universal approximation capability of MSP-GNN.
To our knowledge, none of these four contributions has been previously established in the MSP literature.
This framework provides a mathematical foundation for applying symmetry-preserving architectures to MSP. Building on the identified invariance, the graph representation, and the theoretical analysis, researchers can adapt existing tree- or graph-based models or develop new ones.
Thus, our work goes beyond comparing particular architectural modules or message-passing schemes (e.g., bidirectional versus bottom-up message passing, or with versus without attention). While such comparisons are informative, they are not our main contribution. Instead, we provide a principled framework for learning first-stage solutions of MSP by exploiting its structural symmetry, opening the door to a broader range of symmetry-preserving tree/graph-based architectures.
We have revised Sections 1, 4.2, and 6, as well as Appendix G.1.3, to clarify these points in the uploaded revised manuscript, with all changes highlighted in blue.
(Continued in the next comment.)
Response to Reviewer SYV5
Dear Reviewer SYV5,
Thank you for your constructive feedback.
Response. We believe the motivation behind our architectural design was not made sufficiently clear in the manuscript, and we would like to clarify it as follows.
The architectures in existing studies are FCNN and DeepSets, but both have limitations for MSP: FCNNs flatten the scenario tree and suffer from the curse of dimensionality, while DeepSets ignores its parent-child relationships by treating all nodes as exchangeable.
To address this problem, we (i) identify the subtree permutation invariance of MSP, (ii) construct a graph representation that preserves the scenario tree structure, (iii) design MSP-GNN with permutation-invariant message passing and a root-based readout to respect this symmetry, and (iv) establish its universal approximation capability. Thus, rather than directly applying an existing GNN, our approach follows a principled design from the structural properties of MSP to graph representation, neural architecture, and theoretical guarantees. Our gains over FCNN and DeepSets are substantial (see Table 2).
Therefore, our primary contribution is not an isolated permutation-invariant module, but rather a systematic framework that exploits subtree permutation invariance, an unexplored property in prior MSP literature. While we agree that alternative architectures respecting this symmetry (such as standard tree-based or GNN models) could be adapted for this purpose, none have yet been investigated for MSP. Our work establishes the theoretical foundation necessary to motivate and guide such future variants, serving as a first and useful step toward tree-structured neural architectures in this domain.
Response. We understand that "Table 2" in the comment refers to Table 5, since Table 2 already includes Tree-GNN as an ablation. Please correct us if our understanding is inaccurate.
We conducted a comparison on a balanced tree (T=3, b=5, 31 nodes), where both models are applicable (mean ± SD over three seeds):
Both tree-aware architectures reduce the objective gap by more than 50× relative to FCNN and about 10× relative to DeepSets. Tree-GNN achieves a slightly lower mean objective gap than MSP-GNN, which we explain below.
First, the two are comparable within seed variation: the difference is about one standard deviation of Tree-GNN.
Second, the result is consistent with the special structure of LQR: being unconstrained and quadratic, it is solved by a backward recursion in which each node passes a fixed-size summary to its parent, exactly as in the bottom-up Tree-GNN.
Third, Tree-GNN is not an existing scheme from the literature. It is an ablation of our proposed MSP-GNN. Both respect subtree permutation invariance, which drives the main gains. Bidirectional message passing is one design choice, not necessarily superior.
Ablation. To assess the effect of parent-to-child (P2C) messages, we compare MSP-GNN, its w/o P2C variant, and Tree-GNN on asset allocation (test MSE ×10⁻³, averaged over six seeds):
We find that removing P2C messages increases the error of MSP-GNN in all five configurations, and that MSP-GNN is more accurate than Tree-GNN in all five. P2C messages therefore help in this problem.
Response. For each learning method, we fix the predicted first-stage decision and optimize subsequent decisions to compute the objective gap relative to HiGHS (zero-gap baseline). The table reports the mean gap (%) over three seeds and runtime per instance:
MSP-GNN achieves the lowest objective gap among the learning methods in all configurations (below 0.09%). On the same single-thread CPU, it is 3.9×–6.4× faster than HiGHS in the five main configurations and 20.0× faster on the 4,681-node tree (HiGHS time includes canonicalization).
We will include these clarifications and results in the revision.