Reply to Reviewer xf7T
Thanks for your additional questions! Here are our answers:
**Reply to Q1.** We completely agree with you that our main results focus on the existence of GNNs representing the SB score, and we have not yet established the complexity of such GNNs. In our revision, we will clearly comment that verifying MP-tractability is polynomial in complexity, but the size and running time of GNNs currently have no theoretical guarantees.
However, we would like to kindly emphasize that this does not hurt our main contribution. The main purpose of this paper is to address a theoretical question: **whether GNNs can or cannot universally represent the SB score** for all MILPs, especially given the numerous empirical studies on this topic. We clearly answer this question with Theorem 4.4, Corollary 4.6, and Theorem 4.7—when an MILP exhibits strong symmetry (such as in equations (4.1) and (4.2)), MP-GNNs are not suitable, and other GNN structures need to be explored. This conclusion is inherent, regardless of how large MP-GNNs might be, and we believe it provides useful insights to the learning-to-branch community.
As for the complexity of these GNNs (whether polynomial or exponential), this relates to a different question: **how well GNNs can represent the SB score.** We believe this is an interesting direction for future research.
To further address the reviewer's concern, we will include the following in our revision:
> At the end of Section 4.3, we will add: While verifying MP-tractability is polynomial in complexity, this does not imply that calculating the SB score is polynomial, as the complexity of GNNs is not guaranteed. Our Theorems 4.4 and 4.7 address existence, not complexity. In other words, this paper answers the question of whether GNNs can represent the SB score. To explore how well GNNs can represent SB, further investigation is needed.
We chose to include the comment at the end of Section 4.3 because it involves concepts like MP-tractability and Theorems 4.4 and 4.7. Positioning the comment after these concepts and theorems are introduced ensures a smoother flow for the readers.
**Reply to Q2.** Yes, the results hold for any Borel regular probability distribution. We would like to provide more details on how to extend our results to a data distribution with varying sizes $m,n$.
According to Lemma 36 in (Azizian and Lelarge, 2021), if one can obtain a universal-approximation-type theorem on $G_{m,n}$ for any **fixed** $m$ and $n$ (as we addressed in our manuscript), and if graphs with different sizes can be distinguished by at least one GNN (this is straightforward), then the result can be extended directly to the disjoint union of **finitely many** $G_{m,n}$. This addresses the case of "bounded-support distributions (in $m$ and $n$)" mentioned by you.
If the distribution is not bounded-support in $m$ and $n$, for any $\epsilon>0$, one can always remove a portion of the tail to ensure boundedness in $m$ and $n$. That is what we mentioned in the rebuttal: there always exist large enough $m_0$ and $n_0$ such that $\mathbb{P}[m(G)\leq m_0]\geq 1-\epsilon$ and $\mathbb{P}[n(G)\leq n_0]\geq 1-\epsilon$. The key point is that for any $\epsilon>0$, such $m_0$ and $n_0$ can always be found. Although these values may be large and dependent on $\epsilon$, they are still finite. This allows us to apply the results for the bounded-support case.
Note that the "tail removal" technique mentioned above comes from the fact that a probability distribution has a total mass of 1:
$$1 = \sum_{n=0}^{\infty}\mathbb{P}(n(G) = n) = \lim_{n_0 \to \infty} \sum_{n=0}^{n_0}\mathbb{P}(n(G) = n) = \lim_{n_0 \to \infty} \mathbb{P}(n(G)\leq n_0)$$
By the definition of a limit, this clearly implies that for any $\epsilon> 0$, there exists a sufficiently large $n_0$ such that $\mathbb{P}[n(G)\leq n_0]\geq 1-\epsilon$. A similar argument applies to $m$.
Please let us know if you have further comments or questions!
**(References).** (Azizian and Lelarge, 2021) Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021.