Rethinking the Capacity of Graph Neural Networks for Branching Strategy

Thank you very much for your valuable comments! Please find our responses below:

• [Weakness 1] MILP-graph representation: The bipartite graph representation is standard in the existing literature and has already been utilized in MILP-related learning tasks. The goal of our paper is to provide theoretical foundations and insights into this approach, specifically addressing what GNNs can and cannot represent in learning-to-branch (L2B) tasks.

  To provide more context, we reference a sentence from our manuscript (lines 80-83 in Section 1): "To utilize a GNN on a MILP, one first conceptualizes the MILP as a graph and the GNN is then applied to that graph and returns a branching decision. This approach [14, 18] has gained prominence in not only L2B but various other MILP-related learning tasks [13, 16, 25, 29, 31, 35, 39, 42, 43, 47–50, 52, 55]."

• [Weakness 2] Benchmarks: Our work is mostly theoretical and aims to provide theoretical foundations for the learn-to-branch community. There have been numerous existing empirical works demonstrating the effectiveness of GNNs for branching strategies, as mentioned in the previously quoted sentence (lines 80-83 in Section 1 of our manuscript). These studies include real-world benchmarks such as MIPLIB 2017.

  To further address the reviewer's concern, we conducted additional experiments on larger instances. In this experiment, we trained an MP-GNN on 100 large-scale set covering problems with 1,000 variables and 2,000 constraints for each, which are generated following the practice in Gasse et al., (2019). The MP-GNN was successfully trained to achieve a training loss of $1.94\times 10^{-4}$, which was calculated as the average $\ell_2$ norm of errors on all training instances. We will add the discussion and the additional numerical results in the revised version.

• [Weakness 2] Training epochs: The purpose of the experiments in this paper is to directly validate our theoretical findings. In our experiment, we merely used basic end-to-end training without incorporating advanced techniques from the state-of-the-art literature. Therefore, the training performance shown in Figure 3 does not represent the upper limit of 2-FGNN and MP-GNN's training performance.

  Improving the practical training efficiency of 2-FGNNs for MILP tasks is an interesting and significant future direction. One possible way to improve the training efficiency of high-order GNNs is to employ the sparsity as in Morris et al., (2020). We will add this discussion to our revised manuscript.

  To further address the reviewer's concern, we have conducted additional experiments on this issue. We adopted two additional training techniques that significantly decreased the training epochs needed. With an embedding size of 1,024, it now takes 980 epochs to reach $10^{-6}$ training loss and 1,128 epochs to reach $10^{-12}$ to fit the counter-examples as in Figure 3b. The two techniques introduced are:

  • We let the two counter-examples come in stochastic order to break the symmetry of their gradients. Previously we used the full-dataset (batch size of 2) gradients for training.
  • We used a linear layer to map the edge weights to 128-dimensional hidden embeddings. Previously we directly used the scalar edge weights as the embeddings.

• [Weakness 2] How common are MP-intractable MILPs: MP-intractability comes from the symmetry of MILPs. The symmetry of a MILP can be measured by the number of different colors in the output of the WL test. For example, (4.1) and (4.2) both admit two different colors, significantly less than the number of vertices in the corresponding MILP-graphs. In practice, even if there may not exist many examples with such strong symmetry, it is common to have some symmetry -- As reported by Chen et al., (2023), "for around 1/4 of the problems in MIPLIB 2017 (Gleixner et al., 2021), the number of colors generated by WL test is smaller than one half of the number of vertices".

• [Question 1] Adding more features: We appreciate your observation that adding more features is helpful for breaking the symmetry. The additional feature proposed by you (the number of associated variables by some constraint) can indeed distinguish (4.1) and (4.2). However, there exist other counter-examples with this additional feature. For example, one can add another constraint $\sum_{i=1}^8 x_i\geq 1$ to both (4.1) and (4.2). Then the additional feature becomes $8$ for all variables while the SB scores remain unchanged.

• [Question 2] Root SB vs Leaf SB: Yes, root SB is considered in our experiments. However, our theoretical findings can also be applied to leaf SB. This can be done by treating the leaf node as a new MILP and inputting this new graph into the GNNs.

  We definitely agree with you that there might be less symmetry in leaf SB due to the local cuts.

• [Question 3] Number of parameters: We use a relatively large model size to demonstrate that the error/limitation of MP-GNN revealed in this paper is inherent; regardless of the number of parameters, even a large MP-GNN cannot fit the two toy instances shown in Figure 3(b).

  To further address the reviewer's concern, we conducted additional experiments on 2-FGNN training (using improved training techniques described as above) with varying embedding sizes ranging from 64 to 2,048. The results showed that a smaller embedding size, say 64, can still lead to a high accuracy $10^{-12}$.

  Embedding size	64	128	256	512	1,024	2,048
  Epochs to reach $10^{-12}$ error	18,762	7,474	4,412	2,484	1,128	1,174

  Additionally, the reason that the number of parameters of 2-FGNN is comparable with (even a bit smaller than) MP-GNN is that only local updates are learnable and the aggregations are fixed.

Thank you very much for your valuable comments! Please find our responses below:

• [Question 1, Weakness 1] Complexity of verifying MP-tractability: You are correct that verifying the MP-tractability of a MILP data set requires implementing the color refinement on each of the MILP-graphs in a data set.

  Consider a set of MILPs, $\mathcal{D}$, containing $|\mathcal{D}|$ MILPs. To verify each of the MILPs in this set, one requires at most $\mathcal{O}(m+n)$ color refinement iterations according to Theorem 4.1. The complexity of each iteration is bounded by the number of edges in the graph (Shervashidze et al., 2011). In our context, it is bounded by the number of nonzeros in matrix $A$: $\text{nnz}(A)$. Therefore, the overall verification complexity is $\mathcal{O}(|\mathcal{D}|\cdot (m+n)\cdot \text{nnz}(A))$, which is linear in terms of $|\mathcal{D}|$, $(m+n)$, and $\text{nnz}(A)$. Note that $\text{nnz}(A) \leq m \times n$. This is why we say it is polynomial time.

  In contrast, solving all the MILPs or even calculating all the SB scores in the given dataset $\mathcal{D}$ requires significantly higher complexity. To calculate the SB score of each MILP, one needs to solve at most $n$ LPs. We denote the complexity of solving each LP as $\text{CompLP}(m,n)$. Therefore, the overall complexity of calculating SB scores is $\mathcal{O}(|\mathcal{D}| \cdot n \cdot \text{CompLP}(m,n) )$. Note that, currently, there is still no strongly polynomial-time algorithm for LP, thus this complexity is significantly higher than that of verifying MP-tractability.

• [Question 2] The role of $m$ and $n$: You are correct that our current theory only considers fixed $m$ and $n$, which matches with existing literature on theories of GNNs for (MI)LPs (Chen et al., 2023a; 2023b). The theory can be extended directly to MILP dataset/distribution with varying but upper-bounded $m(G)$ and $n(G)$. Actually, the universal-approximation-type results can even be extended to unbounded sizes. This is because for any MILP distribution $\mathbb{P}$ and any $\epsilon>0$, 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$. We will clarify this point in our revision.

• [Weakness 2] Large-scale numerical results: Our work is mostly theoretical and aims to provide theoretical foundations for the learn-to-branch community. There have been numerous existing empirical works demonstrating the effectiveness of GNNs for branching strategies. To support this point, we reference a sentence from our manuscript (lines 80-83 in Section 1): "To utilize a GNN on a MILP, one first conceptualizes the MILP as a graph and the GNN is then applied to that graph and returns a branching decision. This approach [14, 18] has gained prominence in not only L2B but various other MILP-related learning tasks [13, 16, 25, 29, 31, 35, 39, 42, 43, 47–50, 52, 55]."

  To further address the reviewer's concern, we conducted additional experiments on this matter. In this experiment, we trained an MP-GNN on 100 large-scale set covering problems with 1,000 variables and 2,000 constraints for each, which are generated following the practice in Gasse et al., (2019). The MP-GNN was successfully trained to achieve a training loss of $1.94\times 10^{-4}$, which was calculated as the average $\ell_2$ norm of errors on all training instances. We will add the discussion and the additional numerical results in the revised version.

• [Weakness 3] Statement in Theorem 4.4: While our theorem statement includes both notions $G_{m,n}$ and $G_{m,n}^{\textup{MP}}$, we would like to kindly emphasize that this statement is mathematically precise. First, we acknowledge that $G_{m,n}^{\textup{MP}} \subset G_{m,n}$. The probability distribution is built on the entire space $G_{m,n}$, not just the subspace $G_{m,n}^{\textup{MP}}$. We then assume that G belongs to the MP-tractable space $G \in G_{m,n}^{\textup{MP}}$ with probability one, which means $\mathbb{P}[G\in G_{m,n}\backslash G_{m,n}^{\textup{MP}}] = 0$.

• [Weakness 4] Presentation issues: In our revision, we will make sure to reserve a subsection in the main paper to clearly sketch the proof and explain the main ideas/techniques used in the proof. We will also clarify some notation including:

  • There is a typo in the statement of Theorem A.3. It should be "For any $G,\bar{G}\in G_{m,n}^{\textup{MP}}$ ..."
  • In Theorem A.5, $(\sigma_V,\sigma_W)\ast G$ is the MILP-graph obtained from $G$ by reordering vertices with permutations $\sigma_V$ and $\sigma_W$.
  • Lemma C.8: We will group certain substatements for clarity: (a) and (c) both represent the equivalence between vertices within a single graph, so they can be merged. However, (b) represents the equivalence between vertices of two different graphs and cannot be trivially merged with (a). Similarly, (d) and (f) can be merged as they both represent the equivalence within a single graph.

References: (Shervashidze et al., 2011) Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12, no. 9, 2011.

(Chen et al., 2023a) Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.

(Chen et al., 2023b) Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.

(Gasse et al., 2019) Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.

Dear Reviewer xf7T,

Thank you very much for increasing the score! We appreciate all your valuable comments and will modify the presentation and proof flows accordingly in our revision.

Thank you very much for your encouraging comments! Please find our responses below:

• LP solution with the smallest $\ell_2$-norm: One reason we choose LP solution with the smallest $\ell_2$-norm rather than an arbitrary one is to make sure that the LP solution, as well as its resulting SB score, is uniquely defined. Another reason for this assumption is to keep the theoretical results clean and simple while providing sufficient insight -- When the dataset has strong symmetry, it is not suitable to use MP-GNNs and one can explore other GNN structures.

  Additionally, we will mention that in some cases, the assumption (LP solution with the smallest $\ell_2$-norm) can be directly applied: (1) The LP relaxation admits a unique optimal solution. (2) The solution selected by LP algorithms and the solution with the smallest $\ell_2$-norm have the same output with the floor and ceiling functions.

• Other types of strong branching scores: The same analysis for Theorem 4.4 and Theorem 4.7 still works as long as the SB score is a function of $f_{\textup{LP}}^*(G,j,l_j,\hat{u_j})$, $f_{\textup{LP}}^*(G,j,\hat{l_j},u_j)$, and $f_{\textup{LP}}^*(G)$:

  • We prove in Theorem A.3 that if two MILP-graphs are indistinguishable by the WL test, then they must be isomorphic and hence have identical SB scores (no matter how we define the SB scores). So Theorem 4.4 is still true.
  • We prove in Theorem C.4 that if two MILP-graphs are indistinguishable by 2-FWL test, then they have the same value of $f_{\textup{LP}}^*(G,j,l_j,\hat{u_j})$ (and $f_{\textup{LP}}^*(G,j,\hat{l_j},u_j)$). Therefore, Theorem C.3 still holds if the SB score is a function of $f_{\textup{LP}}^*(G,j,l_j,\hat{u_j})$, $f_{\textup{LP}}^*(G,j,\hat{l_j},u_j)$, and $f_{\textup{LP}}^*(G)$, which implies that Theorem 4.7 is still true.

  In particular, Theorem 4.4 and Theorem 4.7 work for both linear score function and product score function in Dey et al., (2024). Additionally, it can be easily verified (with almost the same calculation as in Appendix B) that the counter-examples (4.1) and (4.2) also work for the linear score function. We will clarify this point in our revision.

References: (Dey et al., 2024) Santanu S. Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. "A theoretical and computational analysis of full strong-branching." Mathematical Programming 205(1):303-336, 2024.

Thank you very much for your encouraging comments! Please find our responses below:

• Practical impact: The purpose of the experiment in Figure 3b is to illustrate the difference between 2-FGNN and MP-GNN for MILP problems with symmetry (beyond the MP-tractable class). Our paper is mostly theoretical and the current experiment is only for validating the theoretical findings. While we have not yet achieved highly efficient training of 2-FGNN in practice (which will be a future research direction), we believe that our results provide theoretical insights and offer guidance to the learn-to-branch community -- When the dataset has strong symmetry, it is not suitable to use MF-GNNs and one can explore other GNN structures.

  It's important to note that in our experiment, we merely used basic end-to-end training without incorporating advanced techniques from the state-of-the-art literature. Therefore, the training performance shown in Figure 3 does not represent the upper limit of 2-FGNN and MP-GNN's training performance.

  To further address the reviewer's concern, we conducted additional experiments on this matter. We adopted two additional training techniques that significantly decreased the training epochs needed. With an embedding size of 1,024, it now takes 980 epochs to reach $10^{-6}$ training loss and 1,128 epochs to reach $10^{-12}$ to fit the counter-examples as in Figure 3b. The two techniques introduced are:

  • We let the two counter-examples come in stochastic order to break the symmetry of their gradients. Previously we used the full-dataset (batch size of 2) gradients for training.
  • We used a linear layer to map the edge weights to 128-dimensional hidden embeddings. Previously we directly used the scalar edge weights as the embeddings.

• Number of parameters: In Figure 3b, the behavior of MP-GNN will not change no matter how many parameters we use, which is guaranteed by Theorem 4.5. This error is inherently related to the symmetry structure of MP-intractable MILPs and cannot be eliminated by increasing the number of parameters. In contrast, the loss of 2-FGNN can be arbitrarily close to $0$ if there are sufficiently many parameters, which is guaranteed by Theorem 4.7 and validated in our numerical experiment.

  To further address the reviewer's concern, we conducted additional experiments on 2-FGNN training (using improved training techniques described above) with varying embedding sizes ranging from 64 to 2,048. We observed that all models achieved near-zero errors but took different numbers of epochs as shown in the table below. The results showed that overall an increased embedding size enlarges the model capacity to fit the counter-examples, which saturates when the embedding size is over 1,024. This may be attributed to the increased training difficulty because the embedding size becomes too large.

  Embedding size	64	128	256	512	1,024	2,048
  Epochs to reach $10^{-6}$ error	16,570	5,414	2,736	1,442	980	1,126
  Epochs to reach $10^{-12}$ error	18,762	7,474	4,412	2,484	1,128	1,174

Thank you very much for your encouraging comments! Please find our responses below:

• Symmetry of MILPs in practice: The symmetry of a MILP problem can be measured by the number of different colors in the output of WL test. For example, (4.1) and (4.2) both admit two different colors, significantly less than the number of vertices in the corresponding MILP-graphs. This phenomenon frequently occurs in practical MILP datasets such as MIPLIB 2017. As noted in Chen et al., (2023), "for around 1/4 of the problems in MIPLIB 2017 (Gleixner et al., 2021), the number of colors generated by WL test is smaller than one half of the number of vertices," indicating that approximately 1/4 of the problems exhibit symmetry. We will add this discussion to our revised manuscript.

• Training efficiency: We agree that our work is primarily theoretical, and our experiments were designed to directly validate our theoretical findings. In our experiment, we merely used basic end-to-end training without incorporating advanced techniques from the state-of-the-art literature. Therefore, the training performance shown in Figure 3 does not represent the upper limit of 2-FGNN and MP-GNN's training performance.

  Improving the practical training efficiency of 2-FGNNs for MILP tasks is an interesting and significant future direction. One possible way to improve the training efficiency of high-order GNNs is to employ the sparsity as in Morris et al., (2020). We will add this discussion to our revised manuscript.

  To further address the reviewer's concern, we have conducted additional experiments on this issue. We adopted two additional training techniques that significantly decreased the training epochs needed. With an embedding size of 1,024, it now takes 980 epochs to reach $10^{-6}$ training loss and 1,128 epochs to reach $10^{-12}$ to fit the counter-examples as in Figure 3b. The two techniques introduced are:

  • We let the two counter-examples come in stochastic order to break the symmetry of their gradients. Previously we used the full-dataset (batch size of 2) gradients for training.
  • We used a linear layer to map the edge weights to 128-dimensional hidden embeddings. Previously we directly used the scalar edge weights as the embeddings.

References: (Chen et al., 2023) Ziang Chen, Jialin Liu, Xinshang Wang, Jianfeng Lu, and Wotao Yin. On representing mixed-integer linear programs by graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.

(Morris et al., 2020) Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33:21824–21840, 2020.

MP-intractability vs Symmetry: Thank you very much for your response and clarification! The density of MP-intractable MILPs varies across datasets and needs to be verified numerically depending on the dataset. Fortunately, verifying MP-tractability in practice can be done efficiently.

To verify MP-intractability of a MILP, one requires at most $\mathcal{O}(m+n)$ color refinement iterations according to Theorem 4.1. The complexity of each iteration is bounded by the number of edges in the graph (Shervashidze et al., 2011). In our context, it is bounded by the number of nonzeros in matrix $A$: $\text{nnz}(A)$. Therefore, the overall complexity of the color refinement algorithm is $\mathcal{O}((m+n)\cdot \text{nnz}(A))$, which is linear in terms of $(m+n)$ and $\text{nnz}(A)$.

In contrast, solving an MILP or even calculating its all the SB scores requires significantly higher complexity. To calculate the SB score of each MILP, one needs to solve at most $n$ LPs. We denote the complexity of solving each LP as $\text{CompLP}(m,n)$. Therefore, the overall complexity of calculating SB scores is $\mathcal{O}( n \cdot \text{CompLP}(m,n) )$. Note that, currently, there is still no strongly polynomial-time algorithm for LP, thus this complexity is significantly higher than that of verifying MP-tractability.

These discussions will be included in our revision. We hope these discussions address your concern.

References: (Shervashidze et al., 2011) Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12, no. 9, 2011.