Rethinking the Capacity of Graph Neural Networks for Branching Strategy
Authors: Ziang Chen
Jialin Liu
Xiaohan Chen
Xinshang Wang
Wotao Yin
Venue: NeurIPS 2024 poster (2024)
Keywords: Mixed-integer linear programs
strong branching
message-passing graph neural networks
second-order folklore graph neural networks
Primary area: graph_neural_networks

Abstract: Graph neural networks (GNNs) have been widely used to predict properties and heuristics of mixed-integer linear programs (MILPs) and hence accelerate MILP solvers. This paper investigates the capacity of GNNs to represent strong branching (SB), the most effective yet computationally expensive heuristic employed in the branch-and-bound algorithm. In the literature, message-passing GNN (MP-GNN), as the simplest GNN structure, is frequently used as a fast approximation of SB and we find that not all MILPs's SB can be represented with MP-GNN. We precisely define a class of "MP-tractable" MILPs for which MP-GNNs can accurately approximate SB scores. Particularly, we establish a universal approximation theorem: for any data distribution over the MP-tractable class, there always exists an MP-GNN that can approximate the SB score with arbitrarily high accuracy and arbitrarily high probability, which lays a theoretical foundation of the existing works on imitating SB with MP-GNN. For MILPs without the MP-tractability, unfortunately, a similar result is impossible, which can be illustrated by two MILP instances with different SB scores that cannot be distinguished by any MP-GNN, regardless of the number of parameters. Recognizing this, we explore another GNN structure called the second-order folklore GNN (2-FGNN) that overcomes this limitation, and the aforementioned universal approximation theorem can be extended to the entire MILP space using 2-FGNN, regardless of the MP-tractability. A small-scale numerical experiment is conducted to directly validate our theoretical findings.

Rethinking the Capacity of Graph Neural Networks for Branching Strategy
Ziang Chen Massachusetts Institute of Technology ziang0mit. edu
Jialin Liu
University of Central Florida jialin. liu@ucf edu
Xiaohan Chen
Xinshang Wang
Wotao Yin
Alibaba US DAMO Academy
(xiaohan. chen,,ceenccc xhen,xins w, wotao, wii.a.yylllllabbbaaaa.aaaaaaaaaa inc. com
Abstract
Graph neural networks (GNNs) have been widely used to predict properties and heuristics of mixed-integer linear programs (MILPs) and hence accelerate MILP solvers. This paper investigates the capacity GNNs to represent strong branching (SB), the most effective yet computationally expensive heuristic employed in the branch-and- bounb algorithm. In the literature, as the simplest GNN structure, is frequently used as fast approximation of SB and we find that not all MIL.Ps's SB can be represented with MP-GNN. We precisely define class of "MP-tractable MILPs for which MP-GNNs can accurately approx- imate SB scores. Particularly, we establish a universal approximation theorem: for any data distribution over the MP-tractabe class, there always exists an MP-GNN that can approximate the SB score with arbitrarily high accuracy and arbitrarily high probability, which lays theoretical foundation of the existing works imitating SB with MP-GNN. For MILPs without the Mrrtractability, unfortunately, similar result is impossible, which can be illustrated by two MILP instances with different SB scores that cannot be distinguished by any MP-GNN, regardless of the number of parameters. Recognizing this, explore another GNN structure called the second-orde folklore GNN (2-FGNN) that overcomes this limitation, and the aforementioned universal approximation theorem can be extended to the entire MILP space using 2-FGNN, regardless of the MP-tractabilitt. A small-scale numerical experiment is conducted to directly validate our theoretical findings.
GNN (MP-GNN),
Introduction
Mixed-integer linear programming (MILP) involves optimization problems with linear objectives and constraints, where some variables must be integers. These problems appear in various fields, from logistics and supply chain management planning and scheduling, and in general NP-hard. The senochhand-bbuug (BnB) algorithm [33] is the core of MILP solver. It works by repeatedly solving relaxed versions of the problem, called linear relaxations. which allow the integer variables take on fractional values. If a relaxation's 's solution satisfies the integer requirements, it is a valid solution to the original problem. Otherwise, the algorithm divides the problem into two subproblems and solves their relaxations. This process continues until it finds the best solution that meets all the constraints.
Branching is the process of dividing linear relaxation into two subproblems. When branching, the solver selects a variable with fractional value in the relaxation's 's solution and create two new subproblems. In subproblem, the variable is forced to be less than or equal to the nearest integer
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

below the fractional value. In the other, it is bounded above the fractional value. The branching variable choice is critical because it can impact the solver's efficiency by orders of magnitude.
well-chosen branching variable can lead to significant improvement in the lower bound, which is a quantity that can quickly prove that subproblem and its further subdivisions are infeasible or not promising, thus reducing the total number of subproblems to explore. This means fewer linear relaxations to solve and faster convergence to the optimal solution. On the contrary, poor choice may result in branches that do little to improve the bounds or reduce the solution space, thus leading to large number of subproblems to be solved, significantly increasing the total solution time. The choice of which variable to branch on is pivotal decision. This is where branching strategies, such as strong branching and learning to branch, come into play, evaluating the impact of different branching choices before making a decision.
Strong branching (SB) 3 is a sophisticated strategy select the most promising branches to explore. In SB, before actually performing a branch, the solver tentatively branches on several variables and calculates the potential impact of each branch on the objective function. This "look-ahead" strategy evaluates the quality of branching choices by solving linear relaxations of the subproblems created by the branching. The variable that leads to the most significant improvement in the objective function is selected for the actual branching. Usually recognized as the most effective branching strategy. SB often results in a significantly lower number of subproblems to resolve during the branch-and and-b-unn (BnB) process compared to other methods [18]. As such, SB is frequently utilized directly or as a fundamental component in cutting-edge solvers.
While SB can significantly reduce the size of the BnB search space, it comes with high computational cost: evaluating multiple potential branches at each decision point requires solving many LPs. This leads to a trade-off between the time spent on SB and the overall time saved due to smaller search space. In practice, MILP solvers use heuristics limit the use of SB to where is most beneficial.
Learning to branch (L2B) introduces a new approach by incorporating machine learning (ML) to develop branching strategies, offering new solutions to address this trade-off. This line of research begins with imitation learning [5] 19 24 25 29 351 56 558, where models, including SVM, decision tree, and neural networks, are trained to mimic SB outcomes based on the features of the underlying MILP. They aim to create a computationally efficient strategy that achieves the effectiveness of SB on specific datasets. Furthermore, in recent reinforcement learning approaches, mimicking SB continues to take crucial roles in initialization or regularization
[4] 60]
While using a heuristic (an ML model) to approximate another heuristic (the SB procedure) may seem counterintuitive, it is important to recognize the potential benefits. The former can significantly reduce the time required to make branching decisions as effectively as the latter. As MILPs become larger and more complex, the computational cost of SB grows at least cubically, but some ML models grow quadratically, even just linearly after training theoretically solve LP relaxations in parallel. the time required for different LPs may vary greatly, and there is lack of GPU-friendly, methods that can effectively utilize starting bases for warm starts. In contrast, ML models, particularly GNNs, are more amenable to efficient implementation on GPUs, making them more practical choice for accelerating the branching variable selection process. Furthermore, additional problem-specifee characteristics can be incorporated into the ML. model, allowing it to make more informed branching decisions tailored to each problem instance.
set of similar MILPs. Although SB can
Graph neural network (GNN) stands out as an effective class of ML models for L2B, sur- passing other models like SVM and MLP, due to the excellent scalability and the permutation- invariant/cquiiarian property. 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 ap- proach [13 19 has gained prominence in not only L2B but various other MILP-related learning tasks 13 26 30
36
48 50
52
54 57]. More details are provided in Section ?
Despite the widespread use of GNNs on MILPs, a theoretical understanding remains largely elusive. A vital concept for any ML model, including GNNs, is its capacity expressive power (27 34 46), which in our context is their ability to accurately approximate the mapping from MILPs to their SB results. Specifically, this paper aims to answer the following question:
Given a distribution of MILPs, is there a GNN model capable of mapping each MILP problem to its strong branching result with a specified level of precision?
(1.1)
2

---

Related works and our contributions. While the capacity of GNNs for general graph tasks, such as node and link prediction or function approximation on graphs, has been extensively studied their capacities in approximating SB remains largely unexplored. The closest studies 11 12 have explored GNNs' ability to represent properties of linear programs (L.ss) and MsLPs, such as feasibility, boundedness, or optimal solutions, but have not specifically focused on branching strategies. Recognizing this gap, our paper makes the following contributions:
4
10
22
28
37
39
47
55
59
In the context of I.2B using GNNs, we first focus on the most widely used type: message-passinng GNNs (MP-GNNs). Our study reveals that MP-GNNs can reliably predict SB results, but only for specific class of MILPs that we introduce as message-passingg trasinne (MP-tractable)) We prove that for any distribution of MP-tractable MILPs, there exists an MP-GNN capable of accurately predicting their SB results. This finding establishes theoretical basis for the widespread use of MP-GNNs to approximate SB results in current research.
Through a counter-example, we demonstrate that MP-GNNs are incapable of predicting SB results beyond the class of MP-tractable MILPs. The counter-example consists of two MILPs with distinct SB results to which all MP-GNNs, however, yield identical branching predictions.
For general MILPs, we explore the capabilities of second-order folklore folkior GNNs (2-FGNNs), type of higher-order GNN with enhanced expressive power. Our results show that 2-FGNNs can reliably answer question (I1) positively, effectively replicating SB results across any distribution of MILP problems, surpassing the capabilities of standard MP-GNNs.
Overall, series of works have empirically shown that learning an MP-GNN as fast approximation of SB significantly benefits the performance of an MILP solver on specific data sets 5 19 24 25 29 33 56 58), our goal is to determine whether there is room, in theory, to further understand and improve the GNNs' performance on this task.
2 Preliminaries and problem setup
We consider the MILP defined in its general form as follows:
min cTar x, s.t. Az c b, l f u, Ty EEZ, #ER
(2.1)
where A E RmmX, b Im , C ... fs, = is the type of constraints, & E (f (f-00) U R)" and u E identifies which variables are constrained to be integers.
are the lower bounds and upper bounds of the variable x, and C (1,,,....
Graph Representation of MILP. Here we present approach represent MILP as bipartite graph, termed the MILP-graph. This conceptualization was initially proposed by [9] and has quickly become prevalent model ML for MILP-related tasks. The MILP-graph is defined as a tuple _n} W = (1.2.... ......................... are sets of nodes representing the constraints and variables, respectively. An edge (i.j) connects node i E V to node j E W if the corresponding entry Asj in the coefficient matrix of (.T) is non-zero, with Aij serving as the edge weight. Fv are features/attribute of constraints, with features U; = (b;, o;) attached to node i E V. Fw are features/atrributes of variables, with features Wy = (eg: Lj, Uj 6r)) attached to node j E W. where (y) E {0, 1} indicates whether the variable zı is integer-constrained.
G = (V, W, A, Fv, ) where the components are specified as follows: V = ?1, m and
We define Nw (i) =: (j E W o C C as the neighbors of E V and similarly define Nv-(i) =: {i E V Aij # 0} CV. This graphical representation completely describes a MILP's information, allowing to interchangeably refer a MILP and its graph throughout this paper. An illustrative example is presented in Figure [
We also introduce a space of MILP MILP-graphs:
Definition 2.1 (Space of MILP-graphs). We use Gm.n to denote the collection of all MILP-graphs induced from MILPs of the form 21. with n variables and m constraints
pesssag--passing graph neural networks (MP-GNNs) are a class of GNNs that operate on graph data, by passing messages between nodes in a graph to aggregate information from their local neighborhoods. In our context, the input is an aforementioned MILP-graph G (V, W, A, Fv, Fw), and each node in W is associated with a real-number output. We use the standard MP-GNNS for MILPs in the literature [2 19.
Specifically, the initial layer assigns features sf, 6 for each node as
'Rigorously, the space G..... S mm x xI" x xI" x (R) x is equipped with product topology. where all Euclidean spaces have standard Eudlidean topologies, discrete spaces (-00), (+20). {S. =, 2). and {0, 1) have the discrete topologies, and all unions are disjoint unions.
3

---

min
11
22
23
2
WI
W12
W3
3
(1, 1,1)
(2, 0, 1,
(3, O. 1,00
2
22
33
2
s.t.
33
0
U/3
(5, S)
1/2 (0, 2)
21
122
33 11
Figure 1: An illustrative example of MILP and its graph representation.
S = p (v:) for each constraint E V, and f = (wy) for each variable j E W. Then message-passing layers == 1.2,..., L. update the features via
$ p² (st D.jENw M(, Aii)) for each constraint V, and
- of (C) Ei (o) , for each variable j E W.
Finally, the output layer produces a number output yj for each node j E W:
yj rr st Ejew 14)
In practice, functions Lu/, 94, S', -= ,r, are learnable and usually parameterized with multi- linear perceptrons (MLPs). In our theoretical analysis, we assume for simplicity that those functions are continuous on given domains. The space of MP-GNNs is introduced follows.
Definition 2.2 (Space of MP-GNNs). We use JNP.GNN to denote the collection of all MP-GNNs constructed as above with p', d' being continuous with f'l (.,0) = O and g' (-, 0) = 0
Overall, any MP-GNN F E FMP-GNN maps MILP-graph G to re-im vector: y F(G' E R.
Second-order folklore graph neural networks (2-FGNNs) are an extension of MP-GNNs designed to overcome some of the capacity limitations. It is proved in (55] the expressive power of MP-GNNs can be measured by the Weisfeiler-Lehman test (WL test [53] To enhance the ability to identify more complex graph patterns, [42] developed high-order GNNs, inspired by high-order WI. tests ( Since then, there has been growing literature about high-order GNNs and other variants including high-order folklore GNNs 4 22 38 61). Instead of operating on individual nodes of the given graph, 2-FGNNs operate on pairs of nodes (regardless of whether two nodes in the pair are neighbors or not) and the neighbors of those pairs. We say two node pairs are neighbors if they share common node, Let G = (V, W, A, Fv, Fw) be the input graph. The initial layer performs:
59 = ("; wj. Asj) for each constraint E V and each variable j E W, and
hi3 = (w), W3z (/112) for variables j1.j2 E W, where وjun if j1 j2 and 8āún = O otherwise. For internal layers / = 1, 2..... compute
1/1 p² (5// 1-1 Enjew , 11,2)) for all i E V,j E W, and
$1.2 = = (C Eiev g' (5 s for all f2 W. The final layer produces the output y, for each node j E W:
yソ Eiev s/yr Eneew t//))
Similar to MP-GNNs, the functions within 2-FGNNs, including (p'.q' f g') 1, p², p..qo. are also leamable and typically parameterized with MLPs. The space of 2-FGNNs is defined with:
Definition 2.3. We use FLFGNN denote the set of all 2-FGNNs with continuous p' f. f'.g''
Any 2-FGNN, F F2.NNNN, maps MII.P-graph G n-dim vector: y F(G). While MP-GNNs and 2-FGNNs share the same input-output structure, their internal structures differ, leading to distinct expressive powers.
We require l',g' yield when the edge weight is 0 to avoid the discontinuity of functions in FMP GNN.

---

3 Imitating strong branching by GNNs
In this section, we present some observations and mathematical concepts underlying the imitation of strong branching by GNNs. This line of research, which aims to replicate SB strategies through GNNs, has shown promising empirical results across a spectrum of studies 19 24
56 58
yet it still lacks theoretical foundations. Its motivation stems from two key observations introduced earlier in Section [I which we elaborate on here in detail.
Observation I: SB is notably effective in reducing the size of the BnB search space. This size is measured by the size of the BnB tree. Here, "tree" refers hierarchical structure of "nodes", each representing a decision point or a subdivision of the problem. The tree's size corresponds to the number of these nodes. For instance, consider the instance peoss3761888--88 When solved using SCIP 7 g under standard configurations, the BnB tree size is 851, and it takes 61.04 seconds to attain optimality. However, disabling SB, along with all branching rules dependent on SB, results in an increased BnB tree size to 35548 and an increased runtime to 531.0 seconds.
from MIPLIB [23]
Observation II: SB itself is computationally expensive. In the above experiment under standard settings. SB consumes an average of 70.40% of the total runtime, 42.97 out of 61.04 seconds in total.
Therefore, there is a clear need of approximating SB with efficient ML models. Ideally, if we can substantially reduce the SB calculation time from 42.97 seconds to a negligible duration while maintaining its effectiveness, the remaining runtime of 61.04 42.97 18.07 seconds would become significantly more efficient.
To move forward, we introduce some basic concepts related to SB.
Concepts for SB. SB begins by identifying candidate variables for branching, typically those with non-integer values in the solution to the linear relaxation but which are required to be integers. Each candidate is then assigned SB score, non-negative real number determined by creating two linear relaxations and calculating the objective improvement. A higher SB score indicates the variable has a higher priority to be chosen for branching. Variables that do qualify as branching candidates assigned a zero score. Compiling these scores for each variable results in an n-dimensional SB score vector, denoted as (B) (SB( SB(G) SB.))
Consequently, the task of approximating SB with GNNs can be described with a mathematical language: finding F FMP or F E F2 such that F(G) Ns SB(G). Formally, it is:
Formal statement of Problem [TTp]: Given a distribution of G. is there F E FAP-GNN or F FINN such that [F))) SB( G)T is smaller than some error tolerance with high probability?
To provide clarity, we present a formal definition of SB scores:
Definition 3.1 (LP relaxation with a single bound change). Pick a G E -m,.- For any j E {1. 2....... nn). 1n (-oo) U TR, and ûj ERR U {+oo}, we denote by LP(G, [, úz) the following LP problem obtained by changing the lower/upper bound of x; in the LP relaxation of (.I):
min c xx, ZER"
s.t. Ar 2, ش ūj ly I. S uy for E (1,2.....
Definition 3.2 (Strong branching scores). Let G E Gm. be a MILP- KILLPhrraph associated with the problem (2.1) whose LP relaxation is feasible and bounded. Denote fip(G) E R as the optimal objective value of the LP relaxation of G and denote (īp(G) E R" as the optimal solution with the smallest Ez-norm. The SB score ; variable zj is defined via
So. SB(G), (fiN -
j &
ffr(G))
- fir(G)), ( otherwise,
where fip(G.j. (z) and fip uz) are the optimal objective values of (,) and L, uz) respectively, with ú, = (G); being the largest integer no greater than (G) and I, = [G)((G))))))))))))(()) being the smallest integer no less than Gip(G);, = 1,2,....
Remark: LP solution with the smallest norm. We only define the SB score for MILP problems with feasible and bounded LP relaxations; otherwise the optimal solution (G) does not exist. the I.P relaxation of G admits multiple optimal solutions, then the strong branching score SB(G) depends on the choice of the particular optimal solution. To guarantee that the SB score uniquely defined, in Definition 3.2
we use the optimal solution with the smallest normm which is unique.
5

---

min
81 01+22 23,
s.t.
T1 + 33 1
U1
Ti +1 1
0 21 22, F3 1 31, 01,42, 23 Z.
U/2
W/
Initialization
MILP formula
MILP-graph G
The WL test (Algorithm)
Figure 2: An illustrative example of color refinement and partitions. Initially, all variables share common color due to their identical node attributes, as do the constraint nodes. After a round of the WL test, 21 and D2 retain their shared color, while 23 is assigned a distinct color, it connects solely to the first constraint, unlike i and 222 Similarly, the colors of the two constraints can also be differentiated. Finally, this partition stabilizes, resulting in I {(1) [2)), J ((1,2), {3))-
Remark: SB at leaf nodes. While the strong branching score discussed here primarily pertains to root SB, it is equally relevant SB leaf nodes within the BnB framework. By interpreting the MILP--raph
G in Definition 3.2 as representing the subproblems encountered during the BnB process, we can extend our findings to strong branching decisions at any point in the BnB tree. Here, rool SB refers to the initial branching decisions made at the root of the BnB tree, while leaf nodes represent subsequent branching points deeper in the tree, where similar SB strategies can be applied.
Remark: Other types of SB scores. Although this paper primarily focuses on the product SB scores (where the SB score is defined as the product of objective value changes when branching up and down), our analysis can extend to other forms of SB scores in [4] (Refer to Appendix D.I
4
Main results
4.1 MP-GNNs represent SB for MP-tractable MILPs
In this subsection, we define a class of MILPs, named wessage-passing-tracttbb (MP-tractable) MILPs, and then show that MP- MP-GNNs can represent SB within this class.
To define MP-tractability, we first present the Seisfeiler-Lhhmall (WL) test 53 a well-known criterion for assessing the expressive power of MP-GNNs (55). The WI. test in the context of MIL.-graphss is stated in Al Algorithm[] 1 It follows exactly the same updating rule as the MP-GNN, differing only in the local updates performed via hash functions.
Algorithm 1 The WL test for MILP-Graphs
Require: A graph instance G' E Gm,n n and iteration limit L > O. 1: Initialize with Cý (i) HASHY (vx), CW (j) HASH (wz).
2: for I = 1,2, ... L do
3: (1) = HASH (CK,0) (1), (())), Azy) N (0)).
4: C (j) HASH, (C),, (C(C (g) Nv
5: end for
6: Output: Final colors CY (i) for all E V and CV (j) for all j e V.
The WL test can be understood as color refinement algorithm.
particular, each vertex in G is initially assigned a color CV (i) or CP (j) according to its initial feature v; or Wy. Then the vertex colors C/ (i) and CW (j) are iteratively refined via aggregation of neighbors' information and corresponding edge weights. If there is no collision of hash functions then two vertices are of the same color some iteration if and only if at the previous iteration, they have the same color and the same multiset of neighbors' information and corresponding edge weights. Such color refinement process is illustrated by an example shown in Figure 2
One can also view a vertex coloring as partition, i.e., all vertices are partitioned into several classes such that two vertices in the same class if and only if they of the same color. After each round
Heer, "no collision of hash function" indicates that the hash function doesn't map two distinct inputs to the same output during the WL test on a specific instance. Another stronger assumption, commonly used in WL test analysis (27). assumes that all hash functions are injective.

---

of Algorithm I the partition always becomes finer if no collision happens, though it may not be strictly finer. The following theorem suggests that this partitioon eventually stabilizes or converges. with the final limit uniquely determined by the graph G, independent of the hash functions selected.
Theorem 4.1 (II Theorem A.2]). For any G E 9m.. the vertex partition induced by Algo- rithm 7 (if no collision) will converge within O(m n) iterations to partition (I, where I= 17, ,2...,,J. }s} is a partition of [1,2..... m) and J = (J1,J2..... (J..J.........
J1l is a partition of
{1, ................................ n.,, and that partition (I, is uniquely determined by the input graph G.
With the concepts of color refinement and partition, we can introduce the core concept of this paper: Definition 4.2 dlessage-passing tractability). For G E 9m... let (I,J) be the partition as in Theorem 4.7 We say that G is pariege-pssinn-raaae tractable (MP-tractable) if for any p E (1.2....,3) and q .......:t all entries of the submatrix (EI.))E,, to denote the subset of all -il.P-graphs in 9m.n that are MP-Iractable.
the same. We use M Gmm,
In order to help readers better understand the concept of "MP-tractable", let's examine the MILP instance shown in Figure 2 After numerous rounds of WL tests, the partition stabilizes to I =
{{1): [2]} and J {11,2), (3)). According to Definition 4.2 one must examine the following
submatrices to determine whether the MILP is MP-tractable:
A[L, 1: 2] - [1. A = [1.1], A[1,3] = [4], A = [0].
All elements within each submatrix are identical. Hence. this MILP is indeed MP-tractable. To rigorously state our result, we require the following assumption of the MILP data distribution.
Assumption 4.3. P is Borel regulur probubility measure 9m. and P(SB(G) E Rd] = 1.
Borel regularity is a "minimal" assumption that is actually satisfied by almost all practically used data distributions such as normal distributions, discrete distributions, etc. Let us also comment on the other assumption (C) E BT = 1. Definition 3.2 the linear relaxation of G is feasible and bounded, which implies füp (G) R. However, it is possible for a linear program that is initially bounded and feasible to become infcasible upon adjusting a single variable's ' bounds, potentially resulting in fir (... ûz) = +oo or fip J.y, u,) = too and leading to an infinite SB score: SB(G); +cc Although we ignore such case by assuming P PJBB(G) E R") 1, is straightforward to extend all our results by simply representing + as 1 considering SB SBG; as a non-negative real number, thus avoiding any collisions in definitions.
Based on the above assumptions, as well as an extra assumption: G is message-passiinn tractable with probability one, we can show the existence of an MP-GNN capable of accurately mapping a MULL--graph G to its corresponding SB score, with an arbitrarily high degree of precision and probability. The formal theorem is stated follows.
Theorem 4.4. Let TP be any probability distribution over 9m, that satisfies Assumption 4.3 and
P(G E MP = 1. Then for any 6, 5 > 0, there exists a GNN F E FMP-GNN such that
P[] - SBB()]| S <8] 6) 2 1 1-c.
The proof of Theorem 4.4 is deferred to Appendix A with key ideas outlined here. First, we show that if Algorithm I produces identical results for two MP-tractable MILPs, they must share the same SB score. That is, if two MP-tractable MILPs have different SB scores, the WL test (or equivalently MP-GNNs) can capture this distinction. Building this result, along with generalized version of theorem and Luzin's 's theorem, we reach the final conclusion.
the
Let us compare our findings with [12 that establishes the existence of an MP-GNN capable of directly mapping G one of its optimal solutions, under the assumption that G must be unfoldable. Unfoldability means that, after enough rounds of the WL test, each node receives distinct color assignment. Essentially, it assumes that the WL test can differentiate between all nodes in G. and the elements within the corresponding partition (I have cardinality one: T 1 and JJ 1 for all p E (1, s) and g E 21, .,.,....4 Consequently, any unfoldable MILPP must be MP-tractable because the submatrices under the partition of an unfoldable MILP (Agg ).EA,.dE., must be 1 x 1 and obviously satisfy the condition in Definition 4.2) However, the reverse assertion is not true: The example in Figure 2 serves as a case in point-it is MP-tractable but not unfoldable. Therefore, unfoldability is a stronger assumption than MP-tractaiility. Our Theorem 4.4 demonstraatss that, to illustrate the expressive power of GNNG in approximating SB, -r-tractayiliiy suffices; we do not need to make assumptions as strong as those required when considering MP-GNN for approximating the optimal solution.
7

---

4.2 MP-GNNs cannot universally represent SB beyond MP-tractability
Our next main result is that MP-GNNs do not have sufficient capacity to represent SB scores on the entire MILP space without the assumption of MP-tractability, stated as follows.
Theorem 4.5. There exist two MILP problems with different SB scores, such that any MP-GNN has the same output on them, regardless of the number of parameters.
There are infinitely many pairs of examples proving Theorem 4.5 and we show two simple examples:
min
21 +
23 5/4 I +
28g
s.t.
22 2,,,,
2z 26 11,
(4.1)
2,
21 2, EZ, 1 sjss.
min
21 + 2 2,
s.t. 21 +
21, 22, 32
1, 2z 21, 28 1, 15 1 E 1 15 8.
(4.2)
26 + 24 2
We will prove in Appendix that these two MILP instances have different SB scores, but they cannot be distinguished by any MP-GNN in the sense that for any E FMP-GNN, inputs (4.1) and 4.2) lead to the same output. Therefore, it is impossible to train an MP-GNN to approximate the SB score meeting a required level of accuracy with high probability, independent of the complexity of the MP-GNN. Any MP-GNN that accurately predicts one MILP's SB score will necessarily fail on the other. We also remark that our analysis for (4.1) and can generalized easily any aggregation mechanism of neighbors' information when constructing the MP-GNNs, not limited to the sum aggregation as in Section 2
The MILP instances on which MP-GNNs fail to approximate SB scores,
are not MP-tractable. It can be verified that for both (4.1) and (4.2). the partition as in Theorem 4.1 given by I = = with 1 = {1, 2, .., 8} and J {J1] with J1 = (1,2..... .8, i.e., all vertices in V form a class and all vertices W form the other class. Then the matrices (Ag)) Je JeJ, and (Ae))E))))j are just A and A, the coefficient matrices in (4. and 442), and have both 0 and 1 as entries, which does not satisfies Definition 4.2
and
Based on Theorem 4.5 we can directly derive the following corollary by considering a simple discrete uniform distribution F' on only two instances 4 and (4.2).
Corollary 4.6. There exists a probability distribution IP over gm,n satisfying Assumption 4.3 and
constants 8 >> O, such that for any MP-GNN F E FMP--NNN it holds that
F[] SB(G)II 2 2
This corollary indicates that the assumption of -rttractability in Theorem 4.4 is not removable.
4.3 2-FGNNs are capable of universally representing SB
Although the universal approximation of MP-GNNs for SB scores is conditioned on the MP- tractability, we find an unconditional positive result stating that when we increase the order of GNNs a bit, is possible to represent SB scores MILPs, regardless of the MP-tractability.
Theorem 4.7. Let IP be any probability distribution over Gmnn that satisfies Assumption for any e, 8 > 0, there exists GNN F E F2-FGNN such that
Then
P[G] SB(G)II 8) 2
The proof of Theorem 4.7 leverages the second-order folklore Weisfeiler-Lehman (2-FWI.) test. We show that for any two MILPs, whether MP-tractable or not, identical 2-FWL results imply they share the same SB score, thus removing the need for MP-tractability. Details are provided in Appendix
Theorem 4.7 establishes the existence of a 2-FGNN that can approximate the SB scores of MILPs well with high probability. This is a fundamental result illustrating the possibility of training a GNN to predict branching strategies for MILPs that not MP-tractable In particular, for any probability distribution P as in Corollary 4.6 on which MP-GNNs fail to predict the SB scores well, Theorem 4.7 confirms the capability of 2-FGNNs to work on it.
However, it's worth noting that 2-FGNNs typically have higher computational costs, both during training and inference stages, compared to MP-GNNs. This computational burden comes from
8

---

the fact that calculations of 2-FGNNs reply on pairs of nodes instead of nodes, as we discussed in Section 2 To mitigate such computational challenges, one could explore the use of sparse or local variants of high-order GNNs that enjoy cheaper information aggregation with strictly stronger separation power than GNNs associated with the original high-order WI. test [41
4.4 Practical insights of our theoretical results
Theorem 4.4 and Corollary 4.6 indicate the significance of MP-tractability in practice. Before attempting to train a MP-GNN to imitate SB, practitioners can first verify if the MILPs in their dataset satisfy MP-tractability. If the dataset contains a substantial number of intrattacteele instances, careful consideration of this approach is necessary, and 2-FGNNs may be more suitable according to Theorem 4.7 Notably, assessing MP-tractability relies solely on conducting the WL test (Algorithm D. This algorithm is well-established in graph theory and benefits from abundant resources and repositories for implementation. Moreover, it operates with polynomial complexity (detailed below), which is reasonable compared to solving MILPs.
Complexity of verifying MP-tractability. To verify the MP-tractability of a MILP, one requires at most (m)+n) color refinement iterations according to Theorem 4.1 The complexity of each iteration bounded by the number of edges the graph [49]. In our context, it is bounded by the number of nonzeros in matrix A: nnz(A) ()). Therefore, the overall complexity is O( + n)) nnz( (A)), which is linear in terms of (m + n) and (A)) In contrast, solving a MILP or even calculating its all the SB scores requires significantly higher complexity. To calculate the SB score of cach MILP, one needs to solve at most n LPs. We denote the complexity of solving each LP as CompLP (m, n)). Therefore. the overall complexity of calculating SB scores is On CompLP 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 tractabba..l
While verifying MP-tractability is polynomial in complexity, the complexity of GNNs still not guaranteed. 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.
Frequency of MP-tractability. In practice, the occurrence of MP-tractable instances is highly dependent on the dataset. In both Examples|4.1 and 4.2 (both MP-intractablee, all variables exhibit symmetry, as they are assigned the same color by the WL test, which fails to distinguish them. Conversely, in the 3-variable example in Figure (MP (MMPtractable)) only two of the three variables, Ii and I2. are symmetric. Generally, the frequency of MP-tractability depends on the level of symmetry in the data higher levels of symmetry increase the risk of MP-intractabiliity This phenomenon commonly seen practical MILP datasets, such as MIPLIB 2017 (3). According to 12]. approximately one-quarter of examples show significant symmetry in over half of the variables.
5 Numerical results
We implement numerical experiments to validate our theoretical findings in Section
Experimental settings: We train an MP-GNN and 2-FGNN with L == 2, where we replace the functions , and g'
Aij) in the MP-GNN by Aiz (())))) and (s) to guar- antee that they take the value 0 whenever A.j O. For both GNNs, p², .g" are parameterized as linear transformations followed by a non-linear activation function; {p', lp',g', f )f are parameterized as 3-layer multi-layer perceptrons (MLPs) with respective learnable parameters; and the output mapping is parameterized as 2-layer MLP. All layers map their input use the ReLU activation function. With 0 denoting the set of all Iearnable parameters of a network, train both MP-GNN and 2-FGNN to fit the SB scores of the MILP dataset G. by minimizing 2 EGeg (G) SB with respect to 6, using Adam (T.. The networks and training scheme implemented with Python and TensorFlow (I. The numerical experiments conducted single NVIDIA Tesla V100 GPU for two datasets:
1024-dimensional vector and
We randomly generate 100 MILP instances, with 6 constraints and 20 variables, that are MP- tractable with probability 1. SB scores are collected using SCIP 6). More details about instance generation are provided in Appendix[B E
We train the MP-GNN and 2-FGNN to fit the SB scores of 4. and 4.2 i.e., the dataset only consists of two instances that are not MP-tractable.

---

15.0
MP-GNN
10
12.5
2-FGNN
10
Emror
Error
10-7
7.5
10-10
5.0
2.5
10 13
MP-GNN
2-FGNN
0.0
10-16
500
1000
1500
2000
500
1000
1500
2000
Epoch
Epoch
(a) MPMMMPPrrat tractabbeeele MILPs: Both MP MP-GNN and 2-FGNN fit the SB scores.
(b) MP -ittitracteblle MILPs 4.1 and
2-FGNN
can fit SB scores while MP- GNN
Figure 3: Numerical results of MP-GNN and 2-FGNN for SB score fitting. In the right figure, the training error of MP-GNN on MP-intractable examples does not decrease after however many epochs.
Experimental results: The numerical results are displayed in Figure 3 One can see from Figure 3a that both MP-GNN and 2-FGNN approximate the SB scores over the dataset of random MILP instances very well, which validates Theorem 4.4 and Theorem 4.7 As illustrated in Figure 3b 2-FGNN can perfectly fit the SB scores of (4.1) and (4.2) simultaneously while MP-GNN can not, which is consistent with Theorem and and Theorem 4.7 and serves as numerical verification of the capacity differences between MP-GNN and 2-FGNN for SB prediction. The detailed exploration of training and performance evaluations of GNNs is deferred to future work to maintain a focused investigation on the theoretical capabilities of GNNs in this paper.
Number of parameters: In Figure 3b the behavior of MP-GNN remains unchanged regardless of the number of parameters used, guaranteed by Theorem 4.5 This error is intrinsically due to the structure of MP- -ntraaacctbble MILPs and cannot be reduced by adding parameters. Conversely, 2-FGNN can achieve near-zero loss with sufficient parameters, guaranteed by Theorem 4.7 and confirmed by our numerical experiments. To further verify this, we tested 2-FGNN with embedding sizes from 64 to 2,048. All models reached near-zero errors, though epoch counts varied, as shown in Table The results suggest that larger embeddings improve model capacity to fit counterexamples. The gains level off beyond an embedding size of 1,024 due increased training complexity.
Table I: Epochs required to reach specified errors with varying embedding sizes for 2-FGNN.
Embedding size
64
128
256
512
1,024
2,048
Epochs to reach 10 error
16.570
5,414
2,736
1,442
980
1,126
Epochs to reach 10 10-12 12 error
18,762
7,474
4,412
2,484
1,128
1,174
Larger instances: While our study primarily focuses on theory and numerous empirical studies have shown the effectiveness of GNNs in branching strategies (as noted in Section [. we conducted experiments on larger instances to further assess the scalability of this approach. We trained an MP-GNN on 100 large-scale set covering problems, each with 1,000 variables and 2,000 constraints, generated following the methodology in [19. The MP-GNN achieved training loss of 1.94 x 10-4, calculated the average &2 norm of emros across all training instances.
Conclusion
In this work, we study the expressive power of two types of GNNs for representing SB scores. We find that MP-GNNs can accurately predict SB results for MII.Ps within a specific class termed pnnessage-passinge trasinntrrcctall tractable" (MP-tractable). However, their performance is limited outside this class. In contrast, 2-FGNNs, which update node-pair features instead of node features as in MP-GNNs, can universally approximate the SB scores on every MILP dataset for every MILP distribution. These findings offer insights into the suitability of different GNN architectures for varying MILP datasets, particularly considering the ease of assessing tracttbbabll We also comment on limitations and future research topics. Although the universal approximation result is established for MP-GNNs and 2-FGNNs to represent SB scores, parameters to achieve a given precision. It would thus be interesting and more practically useful to derive some quantitative results. In addition, exploring efficient training strategies or alternatives of higher order GNNs for MILP tasks is an interesting and significant future direction.
still unclear what is the required complexity/number of
10

---

Acknowledgments and Disclosure of Funding
We would like to express our deepest gratitude Prof. Pan Li from the School of Electrical and Computer Engineering at Georgia Institute of Technology (GaTech ECE), for insightful discussions on second-order folklore GNNs and their capacities for general graph tasks. We would also like to thank Haoyu Wang from GaTech ECE for helpful discussions during his internship at Alibaba US DAMO Academy.
References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. TensorFlow: system for Large-Scale machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pages 265-283, 2016.
[2] Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning-baan -basen approximation of strong branching. INFORMS Journal on Computing, 29(1):185-1195 2017.
[3] David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Finding cuts in the TSP, volume 95. Citeseer, 1995.
[4] Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference Learning Representations, 2021.
[5] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pages 344-353 PMLR, 2018.
[6] Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, et al. The scip optimization suite 8.0. arXiv preprint arXi::2112.08872, 2021.
[7] Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionísio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Dominik Kamp, Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, Erik Mühmer, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, and Lixing Xu. The SCIP Optimization Suite 9.0. Technical report, Optimization Online, February 2024.
[8] Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmicla, João Dionísio, Tim Donkiewicz, Jasper van Doormaaeen, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf der Hulst, Dominik Kamp. Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, Erik Mühmer, Mare E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, and Lixing Xu. The SCIP Optimization Suite 9.0. ZIB-Report 24-02-29, Zuse Institute Berlin, February 2024.
[9] Jin- Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-411 410, 1992.
[10] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances neural information processing systems, 32, 2019.
[11] 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.
[12] 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.
11

---

[13] Cheng Chi, Amine Aboussalah, Elias Khalil, Juyoung Wang, and Zoha Sherkat-Masouma A deep reinforcement learning framework for column generation. Advances in Neural Information Processing Systems, 35:9633-9644, 2022.
[14] Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. A theoretical and com- putational analysis of full strong-branching. Mathematical Progrumming, 205(1):303-333 2024.
[15] Jian-Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang, Yinghui Xu, and Le Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. In Proceedings of the aaai conference on artificial intelligence, volume 34, pages 1452-1459,
2020.
[16] Lawrence Evans and Ronald F Garzepy. Measure theory and fine properties of functions. Routledge, 2018.
[17] Jonas K Falkner, Daniela Thyssens, Ahmad Bdeir, and Lars Schmidt-Thieme. Learning to control local search for combinatorial optimization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 361-376 Springer, 2022.
[18] Gerald Gamrath and Christoph Schubert. Measuring the impact of branching rules for mixed- integer programming. In Operations Research Proceedings 2017: Selecied Papers of the Annual International Conference of the German Operations Research Society (GOR), Freie Universiät Berlin, Germany, September 6-8, 2017, pages 165-170. Springer, 2018.
[19] 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.
[20] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007. 12035, 2020.
[21] Floris Geerts. Walk message passing neural networks and second-order graph neural networks. arXiv preprini arXi::2006.00999) 2020.
[22] Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022.
[23] Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data-driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443 4904444444455 2021.
[24] Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems, 33:1 1887788871107, 2020.
[25] Prateck Gupta, Elias Boutros Khalil, Didier Chételat, Maxime Gasse, Andrea Lodi, Yoshua Bengio, and M. Pawan Kumar. Lookback for learning to branch. Transactions on Machine Learning Research, 2022.
[26] AbdeIrahman Hosny and Sherief Reda. Automatic milp solver configuration by learning problem similarities. Annals of Operations Research, pages 1-28, 2023.
[27] Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2022.
[28] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[29] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
12

---

[30] Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A bata-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 36, pages 10219-10227, 2022.
[31] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980) 2014.
[32] Abdel Ghani Labassi, Didier Chérelat, and Andrea Lodi. Learning to compare nodes in branch and bound with graph neural networks. Advances in Neural Information Processing Systems, 35:32000-32010, 2022.
[33] AH Land and AG Doig. An automatic method of solving discrete programming problems. Econometrica: Journal of the Econometric Society, pages 497-520, 1960.
[34] Pan Li and Jure Leskovec. The Expressive Power of Graph Neural Networks, pages 63-98. Springer Nature Singapore, Singapore, 2022.
[35] Jiacheng Lin, Jialin Zhu, Huangang Wang, and Tao Zhang. Learning to branch with tree-aware branching transformers. Knowledge-Bor Baased Systems, 252:109455, 2022.
[36] Defeng Liu, Matteo Fischetti, and Andrea Lodi. Learning to search in local branching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7796-3803. 2022.
[37] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference Leurning Representations, 2020.
[38] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances neural information processing systems, 32, 2019.
[39] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pages 4363-4377 PMLR, 2019.
[40] Tom Marty, Tristan François, Pierre Tessier, Louis Gautier, Louis-Martin Rousseau, and Quentin Cappart. Learning a generic value-selection heuristic inside a constraint programming solver. In 29th International Conference on Principles and Practice of Constraint Programming (CP
2023). Schloss Dagstuhl-Leibnizzz2e Leibniz-Zentrum für Informatik. 2023.
[41] 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.
[42] Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[43] Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012. 2020.
[44] Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane selection via imitation learning. In International conference on machine learning, pages 17584-17600. PMLR, 2022.
[45] Qingyu Qu, Xijun Li, Yunfan Zhou, Jia Zeng. Mingxuan Yuan, Jie Wang, Jinhu Lv, Kexin Liu, and Kun Mao. An improved reinforcement learning algorithm for learning to branch. arXiv preprint arXiv:2201.066 13, 2022.
[46] Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078 2020.
[47] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
13

---

[48] Lara Scavuzzo, Feng Yang Chen, Didier Chételat. Maxime Gasse, Andrea Lodi, Neil Yorke- Smith. and Karen Aardal. Learning branch with tree MDPs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[49] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler- graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[50] Wen Song, Zhiguang Cao, Jie Zhang, Chi Xu, and Andrew Lim. Learning variable ordering heuristics for solving constraint satisfaction problems. Engineering Applications of Artificial Intelligence, 109:104603 2022.
[51] Mark Tumer, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. Open Journal of Mathematical Optimization, 4:1-28, 2023.
[52] Zhihai Wang. Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. arXiv preprint arXiv:2302.00244 2023.
[53] Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NT1, Series, 229): 1968.
[54] Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[56] Yu Yang, Natashia Boland, Bistra Dilkina, and Martin Savelsbergh. Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems. European Journal of Operational Research, 301(3):828 840, 2022.
[57] Huigen Ye, Hua Xu, Hongyan Wang. Chengming Wang, and Yu Jiang. Gnn&gbdt-guiidh fast optimizing framework for large-scale integer programming. In International Conference on Machine Learning, pages 39864-39878. PMLR, 2023.
[58] Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and- search trees to learn branching policies. In Proceedings of the aaai conference on artificial intelligence, volume 35, pages 3931-3933 2021.
[59] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In The Eleventh International Conference on Learning Representations, 2023.
[60] Tianyu Zhang. Amin Banitalebi-Dehkorde and Yong Zhang. Deep reinforcement learning for exact combinatorial optimization: Learning to branch. In 2022 26th International Conference on Pattern Recognition (ICPR), pages 3105-3111. IEEE, 2022.
[61] Lingxiao Zhao, Neil Shah, and Leman Akoglu. A practical, progressively-expeessie gnn. Advances in Neural Information Processing Systems, 35:34106-34123 2022.
14

---

A Proof of Theorem 4.4
This section presents the proof of Theorem 4.4 We define the separation power WL in Definition A.] and prove that two MP-tractable MMLL--ggrahs or two vertices in a single MP-tractable graph, indistinguishable by WL test must share the same SB score in Theorem A.3 3 other words, WL test has sufficient separation power to distinguish MP-tractable MILP graphs, or vertices in single Mr-tractable graph, with different SB scores.
Before stating the major result, we first introduce some definitions and useful theorems.
Definition A.1. Let G,G E 9m, and let CÝ C| (j) and CY (i), CN (j) be the colors gen- erated by the WL test (Algorithm 1 for G and G. We say G W. G if {(C) :i:):iee)) ((C e V}} and C (j) = CL (i), Vj W holds for any L and any hash functions. Theorem A.2 ((II) Theorem A.2)). The partition defined in Theorem 4.7 satisfies:
(a) v = ey, Vi, E n, p P (1,2....,,8)
(b) W = wy, v.J E J4, E (1,2.....95
(c) {[Ay: : E J,)) = ([Ar) : J4)). Vi,d' p. p (1.2....,, 9 (1, ....................... f),
(d) {[Ag:iE = [[Ag Ip))) j.j' E Jq. p e
where {0) denotes the multiser considering both the elements and the multiplicities.
In Theorem A.2 conditions (a) and (b) mean vertices in the same class share the same features, while conditions (c) and (d) state that vertices in the same class interact with another class with the same multiset of weights. In other words, for any p E 21, 8) and g {1, ......... f), different rows/columns of the submatrix (Aij)iET,,.jE., provide the same multiset of entries.
With the above preparations, we can state and prove the main result now.
Theorem A.3. For any G, G E mmn with SB(G) E R and SB(G) E the following are true:
(a) IfG W. G, then SB(G) SB(G).
(b) If CF (11) C.. (jz) holds for any L and any hash functions, then SB(G) SB
Proof. (a) Since G W G. after applying some permutation on V (relabelling vertices in V/) in the graph G. the two and share the same partition I (2,, and = (J1, J.} as in Theorem A.2 and we have
For any (1,2,
8), ,8,
is constant over all i Ip.
For any E (1, ... f),03 my úy is constant over all j Jg.
For any p E (1, (1, .........). constant over all E Ip.
.) and E .1,2....,f. ,0, ([Ag : J,)) ((A,, j Jy)) is
8e and a (1,2,.... (), ((Ag :i 1,) ((Ag : (,) is For any p E (1, ...,,...))) constant over all Jy.
Here, we slightly abuse the notation not distinguish G and the MILP-graph obtained from G by relabelling vertice in V, and these two graphs have exactly the same SB scores since the vertices in W are relabelled.
Note that both G and are MP-tractable, i.e., for any E (1,2,.... 8) and q E {1,2,... l). (Aij) )ie jeeee and (Aij)iEr,,.fe are both matrices with identical entries, which combined with the third and the fourth conditions above implies that A. Aij for all and j E Jg. Therefore, have = G and hence SB(G) SB(G).
(b) The result a directly corollary (a) by considering and the MII.P-graph obtained from G relabeling jı as and relabeling j2 j1.
D
15

---

In addition to Theorem A.3 we also need the following two theorem to prove Theorem
Theorem A.4 (Lusin's theorem [66 Theorem 1.14]). Suppose that y is a Borel regular measure on TK" and that f : R. + R. p-meusurable, i.e, for any open subset y-mmasurable. Then for any u-measurable X C TR. with p u(X) < so and any 6 > 0, there exists compact set E C. X with u(X)B) < e, such that flæ continuous.
[RmT, (U) is
Theorem A.5 (II Theorem E.IJ). Let C. 9mm be a compact subset that closed under the action of Sm x Su- Suppose that & E C(X, R.) satisfies the followings:
(a) For any ov E Sm, ow E Sn, and G E X, it holds that (((ov, ow) G) ( where (o),ow) * G represents the MiLP-graph obtained from G by reordering vertices with permulations ov and ow.
(b) (G) (G) holds for all G, G X with G W G.
(c) Given any E and any J1. E {1,2, ..., n]. if (11) = CY. (12) holds for any L and any hash functions, then ((G),, (G)
Then for any > 0, there exists F E FMP-GGN such that
sup GeX
-P(G)-F((C) <.
Now we can present the proof of Theorem
Proof of Theorem 4.4 Lemma F.2 and Lemma F.3 in [ prove that the function that maps LP instances to its optimal objective value/optimal solution with the smallest nn-norm Borel measurable. Thus, SB Gm.. SB SB- (IR") IR" also Borel measurable, and is hence F-measurable due to Assumption 4.3 In addition, GMP is Borel subset of Gm., since the MP-tractability is defined by finitely many operations of comparison and aggregations. By Theorem A.4 and the assumption P[G E MP = 1, there exists compact subset X₁ C GMP SB (RR)) such that PP[Sm,, [Xi] S and SB xx continuous. For any ov E Sm and aw E Sn. (av, ow) X, is also compact and reuivaaraiiieeeeeeeeeeeeeee of SB. Set
SB (ex, is also continuous by the
X₂ =
U
(ov,ow) * X1.
Then X2 is permutationn-nnvaiiat and compact with
IP X22] S IP(Sm.n \X1] S.
In addition, SB x, is continuous by pasting lemma.
The rest of the proof apply Theorem A.5 for X X2 and + SB, for which we need to verify the four conditions in Theorem C.10 Condition (a) is true since SB is permutation-equivllene by its
definition. Conditions (b) and (c) follow directly from Theorem A.3 According to Theorem A.5
there exists some F E FLFGNN such that
|F(G) SB(G)) < GEXa
sup
Therefore, one has
P[[ SB(G)) > 8] < P PP [x]] S e,
which completes the proof.
B Proof of Theorem
In this section, we verify that the MILP instances 4. and (4. prove Theorem 4.5) We will first show that they have different SB scores while cannot be distinguished by any MP-GNNs.
16

---

Different SB scores
Denote the graph representation of 4.1 and 4.2) as G and G. respectively. For
both ) and (4.2). the same optimal objective value is and the optimal solution with the smallest 22-norm is (1/2, 2, 2, /2, 2 1/2, 1/2. 1 /2). To calculate SB(G), or SB(G); j. it is necessary create two L.ss for each variable zy. In one I.P, the upper bound of Ty is set to üj [1/2] = actually fixing zy at its lower bound 1 = 0. Similarly, the other LP sets 2. to 1.
even if fix æ1 1, the objective value of the LP relaxation can still achieve 4 by x = (1, 1, 0, 1, 0, 1,0). A similar observation also holds for fixing #1 = 0. Therefore, the SB score for 21 (also for any xy in (4.1) is 0. In other words,
For the problem
SB(G) = (0, 0, 0, 0,000,0000 0,0,0,0
However, for the problem (.2 if fix 1, then the optimal objective value of the LP relaxation is 9/2 since
1
Σ 12=1+ (22 + 23) +
2 51xx 25) + 7 (2s + xι) + 26 + x4) + (x7 + rz) 2 9/2
and the above inequality is tight as x = (1, 1/2, 1/2, 2, 122 1/2 1/2, If we fix x1 = 0, then I22 23 and the optimal objective value of the LP relaxation is also 9/2 since
8
24 2,201+14
21 + m3) + マ (1' + mz) + 2 (Te + x4) (#7 + xxg) 2 9/2,
Therefore, the the SB score for ž (also for any z; (1 < i i 6) in 4.2 is (9/2 4) (9/2 4) 11/4 If we fix 277 = 1, the optimal objective value of the LP relaxation is still 4 since 1/2 1/2, 1/2, 1/2, 1, 0) is an optimal
and the equality holds when x = 10.1,1,1/ 1
solution. A similar observation still holds if Ø7 is fixed to Thus the SB scores for 27 and rg are both O. Combining these calculations, we obtain that
4' 0,0 .
1 1
SB(G)=
4' 4
4'
4
MP-GNNs' output Although and G are non-isomorphic with different SB scores, they still have the same output for every MP-GNN, We prove this by induction. Referencing the graph representations in Section 2 we explicitly write down the features:
U; = 0; = (1,2), "y w/ = 11,0,1,1), for all i E (1. (1....8)), (1. .8).
Considering the MP-GNN's initial step where sf = (w:) and (w;) we can conclude that of 5 is constant for all i and t? E. is constant for all j. regardless of the choice of functions pd and qº. Thus, the initial layer generates uniform outcomes for nodes V and W across both graphs, which is the induction base. Suppose that the principle of uniformity applies to st st, 14,
for some 1 L 1. Since s/, s are constant across all we can denote their common value as s' and hence s' s & for all i. Similarly, we can define 1' with e² = 14 72 for all Then it holds that
J+1 = = - = (f and 1+- = - of (t', 20 (s',1).
where we used (1A j W)] = (1Ay : E WJ} = {{Ar, : 1' E W}} = ({Av, i' W}) = (f1, 0, 0,0,0.0..0) 0,00 for all i and j. This proves the uniformity for 1 1. Therefore, obtain the existence of t such that s/¹ = s. = s and th t = for all i,j. Finally, the output layer yields:
V D, = r(s" st",ty) ,t)) for all j e (1.....8)
which finishes the proof.
C Proof of Theorem 4.7
This section presents the proof of Theorem 4.7 The central idea is to establish separation result in the sense that two MILPs with distinct SB scores must distinguished by at least one F2RGNN, and then apply a generalized Stone-Weierstrer Weierstrass theorem in 4
17

---

C.1 2-FWL test and its separation power
The 2-FWL test as an extension to the classic WL test (53], is a more powerful algorithm for the graph isomorphism problem. By applying the 2-FWL test algorithm (formally stated in Algorithm 2 to two graphs and comparing the outcomes, one can determine the non-isomen -oniioomorphism of the two graphs if the results vary. However, identical outcomes do not confirm isomorphism. Although this test does not solve the graph isomorphism problem entirely, it can serve as a measure of 2-FGNN's separation power, analogous to how the WL test applies to MP-GNN (55]
Algorithm 2 2-FFWL test for MIL.P-Graphs
1: Input: A graph instance = (V. W, A, Fv, Fw) and iteration limit L > 0.
2: Initialize with
C (i.j) = HASH,
(e,, (es,, wy, Aiy).
Co (f1,12) HASH WWS (wij Wja 0jrdo)
3: for warl-10 1111122 1.2,.... L do
4: Refine the color
(( w))); CWW (J1. = HASH (CET (1..))): () :ie v)).
CY (i, = HASH
5: end for
6: Output: Final colors C (i.j) for all i E V.j E W and C for all J1, E W.
In particular, given the input graph G, the 2-FWL test assigns a color for every pair of nodes in the form of (i,j) with i E V.j E W or (2),22 with j1.J2 E W. The initial colors are assigned based on the input features and the colors are refined to subcolors at each iteration in the way that two node pairs are of the same subcolor if and only if they have the same color and the same neighbors' color information. Here, the neighborhood of (i.j) involves ({(()..), (i. : E WW and the neighborhood of (j1.j2) involves J((( j1)) : V}}. After sufficient iterations, the final colors are determined. If the final color multisets of two graphs G and G are identical, they are deemed indistinguishable by the 2-FWL test, denoted by G ~2 G. One can formally define the separation power of 2-FWL test via two equivalence relations on Gm,, as follows.
Definition C.1. Let G, G E Gmn and let CYW (i, j), CWW (21, and CV (i.)), C.W (f1,f2) be the colors generated by 2-FWI. test for G and G.
(a) We define G 22 G if the followings hold any L and any hash functions:
H (1,)) E WJ} [[Cr (1,5) (.)) ((C (J1,2)) : i1.52 E w}] [[O (1.h) f1, E W]].
(C.1)
(C.2)
(b) We define G W2 G following hold for any I. and any hash functions:
" (i.j): : v}} {1C (i.j): v1), Vje W, [[C (i..5)
(C.3)
(CC.)) in e w}} (10 (1,5) NeW], VjeW.
(C.4)
can be seen that C.3 and (C4) are stronger than C.I and C.2 since the latter requires that the entire color multiset is the same while the former requires that the color multiset associated with every j E Win is the same. However, we can show that they are equivalent up to a permutation.
Theorem C.2. For any G, G E Gm,no 22 G if and only if there exists a permutation ow E Sn
W such that G 22 ow G, where ow G the graph obtained by relabeling vertices W using ow-
W. One can understand that both ~² G and G 22 G mean that G and G cannot be distinguished by 2-FWL test, with the difference that G m2 G allows a permutation on W.
18

---

2 ow G implies that G ~2 G. We then prove the reverse direction, i.c., G ~2 G implies G ~2 ow G for ow E Sn- It suffices to consider L and hash functions such that there are no collisions in Algorithm 2 and no strict color refinement in the L-th iteration when G and G are the input, which means that two edges assigned with the same color in the I-th iteration if and only their colors are the same in the (L - 1 iteration. For any J2, E W, it holds that
Proof of Theorem C.2 is clear that G W
C (2,,2) C CF
(f(CE Ct (..i))
(. ((.)))))e)))
- - (((] and
Similarly, one has that
= CK (1.)) = [102 (t,) :e and [10 (1,52 =
and that
(i, -r -(.,2) (.h): ([(C"" -[I (th))
and
Therefore, for any
Ce CG
it follows from
C,2 that
[[C (2, : (4)): (())))))))(("()))))))))))) c}} =[[CLW (i1,12: {[OL (i,)): e (1.)) c]]
(C.5)
Particularly, the number of elements in the two multisets in that
C.5 should be the same, which implies
# (()) = # (jew 110 (1.5) (.D) which then leads to (HlCYW (v)): (1l1or" (..))iie]])) (.)]
One can hence apply some permutation on to obtain (C.3
Next we prove C.4 For any j W,
have
[[CL (i.j): :ie = [[CL (1,5) iiE]]] (Y,,), C (i2,j) for some i EV
(ICCW (f,,)) CKT (f1,1)) :n E W]] ([(C (H, CLT
in : eW)
for some i,, i2 V + ((.))())))) ji E w)] (1C (i. : :he which completes the proof.
C.2
SB scores of MILPs distinguishable by 2-FWL test
The following theorem establishes that the separation power of 2-FWI. test is stronger than equal to that of SB, in the sense that two AlI.--graphs, or two vertices single graph, that cannot be distinguished by the 2-FWL test must share the same SB score.
Theorem C.3. For any G, G E Gm. the followings are true:
19

---

(a) IfG M2 G, then SB(G) SB(G).
(b) IfG m2 G. then there exists some permutation ow Sn such that (B(G) ow (SB (SB(G)) (1,22: : e WW] holds for any and any hash
(c) If (1Cr (1.1): : jE = [[CM functions, then SB(G),, SB(()
We briefly describe the intuition behind the proof here. The color updating rule of 2-FWL test is based on monitoring triangles while that of the classic WL test is based on tracking edges. More specifically, in 2-FWL test colors are defined on node pairs and neighbors share the same triangle, while in WL test colors are equipped with nodes with neighbors being connected by edges. When computing the j-th entry of SB( ()), we change the upper/lower bound of Iy and solve two LP problems. We can regard j E W as special node and if we fixed it in 2-FWL test, triangle containing j W will be determined by the other two nodes, one in V and one in W, and their edge. This "reduces" to the setting of WL. test. is proved in that the separation power of WL. test stronger than or equal to the properties of LPs. This is to say that even when fixing special node, the 2-FWL. test still has enough separation power to distinguish different LP properties and hence 2-FWL test could separate different SB scores. We present the detailed proof of Theorem C.3 in the rest of this subsection.
Theorem C.4. For any G, G E Im i 22 G, then for any j E (1,2, ,n), I E { UIR, and ún R U (+oo), the two LP problems JP(G.j.l, út) and LP(G. úz) (,) have the same optimal objective value.
Theorem C.5 (III). Consider two LP problems with n variables and m constraints
min cTz, x, s.t. orob, I5ssu. sER
(C.6)
and
min c dJx x, s.t. Ar ob, 55
(C.7)
=ER=
Suppose that there exist I = [1, I2,...,,II Ie} and J = {J1, JJ.....JJ! J1} that are partitions of V (1,2..... ..................... m) and W [1, ................................ n respectively. such that the followings hold:
(a) For any p E (1, 88) (bi, oz) = (b,, 5.) is constant over all E Ipi
(b) For any E (,, ................................ 4, (ej L, uj) = (āj, Iis ūz)) is constant over all j E Jqi
(c) For any p E (1,2, and q .1, th. Eje,, Ass EsEs, Aij is constant over all i Ip.
(d) For any p (1,2,...,s)) and q E (1,2..... f). Eier, Auj = Eies, Aig is constant over all j E Jg.
Then the two problems (C.6) and (C7 have the same feasibility, the same optimal objective value, and the same optimal solution with the smallest 2--norm feasible and bounded).
Proof of Theorem C.4 Choose L and hash functions such that there are no collisions in Algorithm and no strict color refnement the L-th iteration when G and G are the input. Fix any j E W and construct the partions I = {I,, I2.... I,} and J = [JI. J.....,J as follows:
.a....I,,
i1, 12 Ip for some p E (1,2....,68) 8) if and only if CY (6 CC
J1,32 E J, for some y E (1, ... if and only C., (ii,j) = C.. (j2,J).
Without loss of generality, we can assume that j E Jj. One observation is that Jn = [i)- This is because ýi E Jn implies that C (j1-j) CWW (i,J), which then leads to C (j1,5) CWW (i.5) and 55. = 63z since there is no collisions. We thus have j1
W Note that we have CC.3 and C.4 from the assumption G 22 G. So after permuting G on V and W (.) one can obtain CVW
CyW (i.j) for all E V and CWW (j cW (f1. j) for all Ji E W. Another observation is that such permutation does not change the optimal objective value of JL, lg, ûz) as is fixed.
(i,j)
20

---

Next, we verify the four conditions in Theorem C.5 for two LP problems LP(G, j. و, (.G. ūz) with respect to the partitions I (7 2 ....
úz) and ..... [s) and J J2, ........ Jt).
Since there is no collision in the 2-FWL test Algorithm 2 C. (i,j) C% (i.5) implies that (i,))) C. (i,j) and hence that 2 ü, which is also constant over all E lp since CL (i,j) is contant over all 1p by definition.
Verification of Condition (a) in Theorem C.5
Verification of Condition (b) in Theorem
C.5 It follows from Ch () = CV (j1,j) that
CO CWW (j1,5) = C (ii,j and hence that Wij = Wii which is also constant over all j1 E I since C
CWW (f1.5) is contant over all j1 E Ig by definition.
Verification of Condition (c) in Theorem C.S
Consider any (,, and any i E Ip- It
follows from CVW (i,5) = CL (1, that
{[CCZ- (i,,), CL (1,51)) i1 E w]] (1 (i,,),
and hence that
HIC (g, ji [ (1g))
i W]]
where we used the fact that there is strict color refinement in the I--th iteration and there is no collision in Algorithm
2
We can thus conclude for any E (1,2,...,t that
{[Aih 51 {4)) = ((A :h E Jq)
which implies that Ene,, Aun = Ener, As that constant over In since Cy. (i.j) =
CVW(i.) is constant over i Ip.
Verification of Condition (d) in Theorem follows from C (f1.)) CL CWW (fr.)) that ((C)) CY (1,5)) (7.)) :in)))ee))) - :
Consider any q E (1,2....,4) and any ji Jg.
and hence that
H(C W v
(1,5), A,)
where we used the fact that there is no strict color refinement at the L-th iteration and there is no We thus conclude for any p
collision in Algorithm 2
that
({Ai : E ET)) = ((A,, : E [p]);
which implies that Eier, Au = -iEr,, Aij, that is constant over ji E Jg since CW (j1,5) C.. (f1.5) is constant over j1 E Jq.
Combining all discussion above and noticing that J1 = =)), one can apply Theorem C.5 and conclude that the two LP problems I. (, úz)) and which completes the proof.
j: have the same optimal objective value,
W. Corollary C.6. For any G, G,G E Gm if G ~2 G. then the LP relaxations of G and G have the same optimal objective value and the same optimal solution with the smallest E--norm (if feasible and bounded).
Proof. If no collision, it follows from CC44 that CWW (j.j) = OWW (j.5) which implies 1, I and u, = ūj for any j E W. Then we can apply Theorem C.4 to conclude that two LP problems L, uz) and LP(G, [5, ū.) that are LP relaxations of G and have the same optimal objective value.
In the case that the LP relaxations of and G are both feasible and bounded, we use and z to denote their optimal solutions with the smallest &n-nrmm For any E W, and z are also the optimal solutions with the smallest form for LP(G, j, u,) and LP(G, J,G,j, ;;, ūyy) respectively. By Theorem
C.3 and the same arguments as in the proof of Theorem C.4 we have the æ; ãz. Note that we cannot infer x = T by considering single j E W because we apply permutation on V and W H in the proof of Theorem C.4 But we have zj ã. for any j E W which leads to F. L
21

---

Proof of Theorem C.3
(a) By Corollary C.6 Theorem C.4
(b) By Theorem C.2 and (a).
(c) Apply (a) on G and the graph obtained from G by switching ji and j2-
C.3 Equivalence between the separation powers the 2-FWL test and 2-FGNNs
The section establishes the equivalence between the separation powers of the 2-FWL test and 2- FGNNs.
Theorem C.7. For any G, G E Im, the followings are true:
(a) G 2 G ind and only if F(G) F(G) for all F E F2FONN-
(b) {{CE (J.J1): E W]] = [[C ; EW) holds for any and any hash functions if and only F(G), = =(()) V F2FGNN.
(c) G G22 G if and only if f(G)= ([G)=f(G) f(G) for all scalar function f with fl E FF2FNNN-
The intuition behind Theorem C.7 is the color updating rule in 2-FWL test is of the same format as the feature updating rule in 2-FGNN, and that the local update mappings p', g', f'. can be chosen injective on current features. Results of similar spirit also exist in previous literature; see We present the detailed proof of Theorem C.7 in the rest of this subsection.
e.g.,
22 55
Lemma C.8. For any G, G E Gm, iG W G, then F(G) = FFG) all F F2-GNNN.
Proof. Consider any F' E F2-FGNN with L layers and let s'y t jidsa and s Z7 51.2 be the features in the 1-th layer of F. Choose T. and hash functions such that there are no collisions in Algorithm when G and G are the input. We will prove the followings by induction for 0 S 1 i L:
(a) CY (i.j) CPW (f,5") implies ر'y l'ygg
(b) Cy (i.j) CY (7,j') implies sty 8'68"'
(c) (i,(i = CY (f',)") implies st "'ag"'
(d) cW (f1,12) = C. (1)12) implies t//3 = 3/33
(c) CW (J1, = -CW
W (Hi 12) implies 1/13 = 81 R,32"
n C. (f1.52) = CC (2) implies 5, 7 33.35
As the induction base, the claims (a)-(f) are true for = O since HASH W and HASH have collisions. Now assume that the claims (a)-(f) are all true for 1 where / E (1, and prove them for 1. In fact, one can prove the claim (a) for as follow:
WW do not
CV C. (1'5") (1.)) (f'5") and
(11.)) (( (4.1)) :he [[(C (f..5') Ch. in E W}} - - and ((() ( : e W)] ( (155)) :i w]]
= -
dpg-
The proof of claims (f)-(f) for is very similar and hence omitted.
Using the claims (f)-(f) for L, we can conclude that
G 2 G
- (IcI/(i.):iiv)))) (IC Vje W, and
22

---

([ ( (1,1) in W]] Ajew
=
Vje W, and
(1 t E w]]
: e W Wjew
r
Σ
Σ
=r
Σ EVV
Σ
AjEW
iEV
JIEW
hew
= (
which completes the proof.
Lemma C.9. For any G,Ge E gm Cfn...fFFG.. F(G) all F F2FFNNN then G W. ~2 G.
Proof. We claim that for any L there exists 2-FGNN layers for l 2,,,2.... ................................ L, such that the followings hold true for any 0 S 1 < T. and any hash functions:
(a) o/ by implies CP (i. = (t.
(b) b Byg implies CP (i.j) = CX"((.)))
(c) 8 k implies CYW (i. = (Y"(('))
(d) in 3
implies C (2) C. (21,2))
(c) 1/ Z implies CWW (f1, C.W (11
1/
(f) z Jihe
= 3 implies C (21, = -. (2)
Such layers can constructed inductively. First, for = 0, we can simply choose pd that is injective on {vi, Wy. Ag) ; E V.j W) U (Te, Wy Ag) : E V.j W) and dd that is injective on {(w), W22 (122) : 11.32 E [( Wy (.22) J2 E W}.
Assume that the conditions (f)-(f) are true for -- where 1 S 1 L, we aim to construct the 1-th layer such that (a)-(f) are also true for l. Let 0n 02,.0,,,,00 collect all different elements in (oly
V,j E W] (8) :ic V,j E W) and let 11.32......3 By collect all different elements in (t/-2 : J1. E W Jida f1,j2 E W). Choose some constinuous f such that f( ax) = e @ eg E R='xu, xu, where ey is a vector in Ry with the k' entry being 1 and other entries being and et is vector in I"" with the k-th entry being and other entries being O. Choose i V,j W) U
some continuous p' that is injective the set {
1-1 Enew f'(
(1 W. M str)) : V,j E }. By the injectivity of p' and the linear independence of (e Sc : s u K s u'), we have that
1/1 d
1-1 1-1
and Σ E Σ ((ST
81 524
jiEW
jIEW
J-1 1-1
and for any 1 1 15 W s
# {ii E W: 1 = 3, 1- --1==a) = #(11 E EW - =a
1/7 s/g 1-1
and (( i1 E w}} ((( :hE W}}
- cKW (i, = (t..) and
ew EW]] =
- [( (i oi
= CV = cC)
23

---

which is to say that the condition (a) is satisfied. One can also verify that the conditions (b) and (c) by using the same argument. Similarly, we can also construct g' and q' such that the conditions (d)-(f) are satisfied.
Suppose that G ~2 G is not true. Then there exists L and hash functions such that
(1.)" : * {10r" (i.)):ie]],
{ {C2 (Ji.)): i1 E ww] + ([Or (1.3): : : WW]
holds for some j W. We have shown above that the conditions (a)-(f) are true for L and some carefully constructed 2-FGNN layers. Then holds for some j E W that
{1 :e v]] + (1 :iE]))
(C.8)
or
(1 1 E EW) * (1 : eW}
(C.9)
In the rest of the proof we work with (C.)) and the argument can be easily modified in the case that C..9 is true. follows from (C.8) that there exists some continuous function such that
Σ
((3
KV
EVV
Then let us construct the (L + 1)-th layer yielding
L+1
= =
and
L++ = p(8
and the output layer with
Σ
Σ
1+1
Σ iEV
+
Σ iEV
Σ LEV
L+1 Σ
74+1
313
VEV
JIEW
JiEW
This is to say F(G); + F(G); for some F F2HGNN, which contradicts the assumtion that F has the same output on G and G. Thus we can conclude that G W2 G.
Proof of Theorem C.7 (a). By Lemma C.8 and Lemma C.9
Proof of Theorem and j2.
(b). Apply Theorem on G and the graph obtained from G by switching ji
Proof of Theorem
C.7 (c). Suppose that G ~² G. By Theorem C.2 there exists some permutation
ow E Sn. such that mug ow * G. For any scalar function with f1 F2-ONNN by Theorem C.7 it holds that (G) = (fl)(aw * G) = GG) where we used the fact that f1 is permutation cquivariant. We can thus conclude that f(G)= f(G).
W
Now suppose that G m2 G is not true. Then there exist some L and hash functions such that
(I.)
+ 11C (v.)):
or
[[ (11,12 : f1.12 E W)) + {[CL (f1, f152 EW).
By the proof of Lemma C.9 one construct the 1-th 2-FGNN layers inductively for 0 S $15 L. such that the condition (a)-(f) in the proof of Lemma C.9 are true. Then we have
{ : vij.
E W}} * (( :i e E Vev.jeWe W]],
(C.10)
or
((th,s 11112 w}] # { (17 f1.je W)).
(C.11)
We first assume that (C.10) is true. Then there exists continuous function with
Σ
p(st))+
Σ
p(5
SE JEV
JEVJEW
24

---

Let us construct the (L + 1) layer such that
85
L+1
=p pt
(
6in)
Σ (p(
jIEW
JIEW
LL+
p 1+1
Σ
= Σ
p(
iij
JIEW
JIEW
and the output layer with
+++
Σ iEV jeW
Σ
p( +
Σ Σ ((5))) =
Σ
L+1
Σ
Z
BEV
jEW
REV JIEW
iEV
JIEW
which is independent of je f(G).
W. This constructs E F2FGNN of the form F fl with f(G) +
Next, we consider the case that C.III true. Then
(1 i E [)) 12 e []] + (1 i1 E [W] j2 E EW].
(C.12)
and hence there exists some continuous vb such that
}} *
j2 E W }}
Σ ((th))) : ja w ew]
Σ
JIEW
jiEW
Let us construct the (L + 1)-th layer such that
L+1 81j
=pbtt
L
Σ
s
Σ
Sijt
jIEW
NEW
L++ 1+1
Σ
Σ with
JiEW
NEW
and we have from (C.12 that
H1 :ieV.j [.]jjW]]] (18
We can therefore repeat the argument for (C.10) and show the existence of f with f1 E F2-GNN and f(G) f(G). The proof is hence completed.
C.4 Proof of Theorem 4.7
We finalize the proof of Theorem in this subsection. Combining Theorem C.3 and Theorem C.7 one can conelude that the separation power of F2-FGNN is stronger than or equal that of SB scores. Hence, we can apply the Stone- Hooe--Wiersstrass-e Weierstrass-type theorem to prove Theorem 4.7
Theorem C.10 (Generalized Weierssrssssssss theorem (4). Let X be a compact topology space and let G be finite group that continuously X and T.P.. Define the collection of all equivariant continuous functions from X to IR" as follows:
Cg(X, R (F E C(), F(g+ ( (0)+)==0) = g F(x), E
Consider any F Cx(X and any & E Cx(X, R"). Suppose the following conditions hold:
(a) F is subalgebra of C(X, R²) and 1 E F, where 1 is the constant function whose ouput is always 11, 1) E R".
(b) For any v, x' E X, if [(x) = [(x') holds for any C(X, with fl F, then for any F. E F, there exists g G such that F(x) g F(x').
25

---

(c) For any z, x' E X, F()) F(x') holds for any F E F, then ((x) = ((x))
(d) For any E X, it holds that (x)), ()))a2) v (j1.22) E J(x), where
J(x) = (2), E 2 nnp F(x), = =(x) YFEFJ
Then for any 6 > O, there exists F E F such that
sup - - Sc =eX
Proof of Theorem 4.7 Lemma F.2 and Lemma F.3 in I prove that the function that maps L.P instances to its optimal objective value/optimal
solution solution with the smallest f2-norm is Borel measurable. Thus, SB Gmnn C SB (IR") + IR" is also Borel measurable, and is hence F-measurable due to Assumption 4.3 By Theorem a.d Assumption 4.3 there exists compact subset X₁ SB SB")(R") such that 9m. {X]] S and SB|x, is continuous. For any av Sm and ow E Sn, (av, ow (ww)XX) +X1 is also compact and SB (av.ow))Xx is also continuous by the commutation-equvariiann of SB. Set
X2
U
(ov,ow) X1.
Then X₂ is permutation invariiinnnnn and compact with
P (X2] s P( {X1] SC.
In addition, SB|x, x, is continuous by pasting lemma.
The rest of the proof is to apply Theorem C.10 for X = X2.
Sm X Sn, 4- = SB, and
F= F2 FANN- FANN- We need to verify the four conditions in Theorem C.10 Condition (a) be proved by similar arguments as in the proof of Lemma D.2 in [11]. Condition (b) follows directly from
Theorem C.7 (a) and (c) and Theorem C.2 Condition (c) follows directly from Theorem
and Theorem C.3 (a). Condition (d) follows directly from Theorem C.7 (b) and Theorem
(c).
According to Theorem C.10 there exists some F2NNNNN such that
sup GEX²
| -600-SB00 SB(])I 6
Therefore, one has
P[] - SB(G)] > 8) < <PP9 \X21 S
which completes the proof.
D Extensions of the theoretical results
This section will explore some extensions of our theoretical results.
D.1 Extension to other types of SB scores
The same analysis for Theorem 4.4 and Theorem 4.7 still works as long the SB score is function of fip j. Ig, 4z), fip uz), and fip(G)):
We prove in Theorem A.3 that if two MILP 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 Theorem C.4 that
MILP MILP-graphs are indistinguishable by 2-FWL test, then they have the same value of [i ûz) (and fip I,, uz)). Therefore, Theorem
C.3 still holds if the SB score a function of Jip úz), (G. u;), and (G), which implies that Theorem 4.7 is still true.
Therefore, Theorems
4.4 and 4.7 work for both linear product score functions in 14
26

---

D.2 Extension to varying MILP sizes
While Theorems and assume MILP sizes m and n are fixed, we now discuss extending these results to data distributions with variable m and n.
First, our theoretical results can be directly extended to MILP datasets distributions where m and vary but remain bounded. Following Lemma 36 in [ if universallapprooimaaiinn theorem applies to Im.. for any fixed m and (as shown in work) and least GNN can distinguish graphs of different sizes, then the result holds across a disjoint union finitely many 9m.x-
If the distribution has unbounded m nt, for any 0, can always remove portion of the tail to ensure boundedness in m and n. In particular, there always exist large enough me and no such that Pfm(G) I mu] mo and no can always be found. Although these values may be large and dependent on e, they are still finite. This allows to apply the results for the bounded-supper case.
and (P) I nu] 2
The key point is that for any O, such
Note that the "tail removal" technique mentioned above comes from the fact that a probability distribution has total mass of 1:
P(n(G) = n] lim n=0
P(n(G) = =n] = lim P[n(G) S no).
By the definition of a limit, this clearly implies that for any > 0, there exists a sufficiently large no such that (G] S no] 2 1116. e. A similar argument applies to m.
E
Details about numerical experiments
Random MILP instances generation We generate 100 random MILP instances for the experiments in Section We set m and n 20, which means each MILP instance contains 6 constraints and 20 variables. The sampling schemes of problem parameters are described below.
The bounds of linear constraints: by ~ (O, 1).
The coefficients of the objective function: Cj A((0,)) 1).
The non-zero elements in the coefficient matrix: Ai NNO0, 1). The coefficient matrix A contains 60 non-zero elements. The positions are sampled randomly.
The lower and upper bounds of variables: 14, (O 109). We swap their values 4 Uj after sampling.
The constraint types are randomly sampled. Each type (S. = or 2) occurs with equal probability.
The variable types are randomly sampled. Each type (continuous integer) occurs with equal probability.
Implementation and training details We implement MP-GNN and 2-FGNN with Python 3.6 and TensorFlow 1.15.0 [ Our implementation is built by extending the MP-GNN implementation The SB scores of randomly generated
of [19] in httph:tt://// htttpp:///ithub. com/
MILP instances are collected using SCIP 6
For both GNNs, p", are parameterized as linear transformations followed by non-linear activa- tion function; {p' . :f',, f', of ) are parameterized as 3-layer multi-layer perceptrons (MLPs) with respective learnable parameters; and the output mapping is parameterized layers map their input to a 1024-dimensional vector and use the ReLU activation function. Under these settings, GP-GNN contains 43.0 millions of learnable parameters and 2-FGNN contains 35.7 millions of parameters.
2-layer MLP. All
We adopt Adam 31 to optimize the learnable parameters during training with learning rate of 10-5 for all networks. We decay the learning rate to 10-6 and 10-7 when the training error reaches 10-6 and 10-12 respectively to help with stabilizing the training process.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The results claimed in the abstract and the introduction established theoret- ically in Section and verified numerically Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in the last paragraph of Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

The assumptions are stated in Section 4 and the complete proofs are included in the appendices.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental settings and details are presented in Section 5 and Ap- pendix E. which is sufficient to reproduce the results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
29

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the source code and data reproduce the main results, along with sufficient instructions to run the code, in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc
aablic/guudees/Coeeetbiisss www.ssssnoooiiillooooooool for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wwtps/cccppppclgguiueeeeaeco
Ceaeee/CCSSSuSbisSS..S.. www.ssssiicgcyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental settings and details are presented in Section 5 and Ap- pendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Our experiments are only for directly validating the theoretical findings rather than competing with state-of-the-ee and no statistical significance needs be considered.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
30

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information the computation resources used for experiments are provided in Section
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttps:/neuripss.cm
inne ott.e//oooiiigt/rr///ooooooooooo htwpeerrippsccppppii////ecc....t
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm that this paper conforms with it in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper conducts theoretical research in machine learning and has no societal impact.
Guidelines:
31

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper conducts theoretical research in machine learning and poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We used synthesized data for numerical experiments. The creators of the code, based on which we build our implementation of the networks and training schemes, are credited in Appendix E
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
32

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets.papersstt paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper conducts fundamental research machine learning and does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper conducts fundamental research machine learning and does not involve crowdsoureing research with human subjects.
Guidelines:
33

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "T6FuuHfOzD", "reviewer": "Reviewer_BDoF", "summary": "The paper investigates the effectiveness of GNNs in approximating strong branching (SB) strategies in mixed-integer linear programming (MILP) problems. SB is a heuristic used in the branch-and-bound algorithm to choose branching variables. SB is among the best-performed heuristics in branch-and-bound algorithm, but is extremely computationally expensive.\n\n### Key Contributions:\n1. The paper defines a class of MILPs called \"MP-tractable\" for which message-passing GNNs (MP-GNNs) can approximate SB scores accurately. It establishes a universal approximation theorem for MP-GNNs within this class.\n2. The study shows that MP-GNNs cannot represent SB scores for MILPs beyond the MP-tractable class. This is demonstrated through counter-examples where MP-GNNs fail to distinguish different MILP instances with distinct SB scores.\n3. The paper proposes second-order folklore GNNs (2-FGNNs), which overcome the limitations of MP-GNNs and can universally approximate SB scores across any MILP distribution. Small-scale numerical experiments are performed to support the claim.", "questions": "The paper is generally well-written. Besides the issues in the section of ``Weakness\", I don't have further questions so far.", "limitations": "Yes.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "SB is a very important heuristic in branch-and-bound. It is strongly desired to develop a computationally efficient method to approximate SB score, so as to accelerate the solving of MILP. This paper proves that traditional MP-GNN can not universally approximate SB scores, and proposes a new GNN framework that can universally approximate SB scores. This theoretical insight is of great importance to the L2O community.", "weaknesses": "1. The paper provides a nice theoretical justification for why MP-GNN can not handle the intrinsic symmetry in SB scores. However, it is not clear whether such symmetry causes issues in practice. The symmetric case such as the counter-example in this paper is very rare in common MILP problems.\n\n2. Even for small-scale data, 2-FGNN needs more than 30,000 epochs to fit the MP-intractable data. The lack of learning efficiency shows that 2-FGNN is far from practical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your encouraging comments! Please find our responses below:\n* __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.\n* __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. \n\n    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. \n\n    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:  \n    * 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.\n    * 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.\n\n__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.\n\n(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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kABK2kpYcT", "reviewer": "Reviewer_uxqS", "summary": "This paper provides a new lens through which the capacity of GNNs can be analyzed---branching strategy. The correspondence between strong branching and GNNs is established and the expressiveness of GNNs are discussed in terms of whether universally approximating strong branching is possible.", "questions": "- what would the behavior in Figure 3b change if the number of parameters were varied?", "limitations": "The limitations have been sufficiently addressed in the paper.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- the idea is novel and sound\n- the presentation of the paper is excellent and easy to follow\n- the notion of going beyond WL test to study the expressiveness of GNNs are likely to encourage and guide the design of more expressive GNNs", "weaknesses": "- only one experiment (in Figure 2b) is employed to showcase the difference in the expressive power between MILP and MP-GNN, and the difference only shows after 30,000 epochs. How would this practically affect the real-life experiments?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your encouraging comments! Please find our responses below:\n* __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.\n\n    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.\n    \n    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: \n    * 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.\n    * 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.\n    \n* __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. \n    \n    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. \n\n    | Embedding size | 64 | 128 | 256 | 512 | 1,024 | 2,048 |\n    |-----------------------|-----|-------|------|-------|---------|---------|\n    | Epochs to reach $10^{-6}$ error | 16,570 | 5,414 | 2,736 | 1,442 | 980 | 1,126 |\n    | Epochs to reach $10^{-12}$ error | 18,762 | 7,474 | 4,412 | 2,484 | 1,128 | 1,174 |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CwCcCSzYTG", "reviewer": "Reviewer_1NEU", "summary": "This paper concerns the expressive power of GNN in the context of approximating Strong Branching scores in learning to branch. In this paper, the authors proposed the notion of \"MP-tractable\" Mixed Integer Linear Programs (MILPs) and analytically proved that all MP-tractable MILPs are distinguishable by message passing GNNs - a structure frequently used in state-of-the-art models in learning to branch. The authors then demonstrated through example that the same may not hold non-MP-tractable MILPs, and further provided analytical that all MILPs, regardless of MP-tractability, can be distinguished by 2-FGNNs. A small scale numerical experiment is included as a prove of concept.", "questions": "1. This paper focused on product-type strong branching scores in their analysis. While it is popularly used as the default scoring scheme in SCIP, there are other strong branching rules that exists as well (see [1]). How does your result generalizes to different strong branching scores, and what properties does the strong branching scheme need for your results to be applied?\n\n[1] Dey, S.S., Dubey, Y., Molinaro, M. et al. A theoretical and computational analysis of full strong-branching. Math. Program. 205, 303–336 (2024). https://doi.org/10.1007/s10107-023-01977-x", "limitations": "The authors have discussed the limitations of the work. The large-scale experiments are still a problem in existing studies.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is rigorously written and easy to follow, claims are accompanied with theoretical justifications \n2. Examines the limitations of a commonly used tactic in Learning to Branch, with proposed necessary condition for being GNN-distinguishable weaker than previous work.", "weaknesses": "1. The proofs seems to be dependent on the assumption that the LP solution is one of minimum L2 norm, which somewhat limits its implication in real-life scenarios as such solution is often not selected by LP solving algorithms like simplex", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your encouraging comments! Please find our responses below:\n* __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. \n        \n    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.\n\n* __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)$:\n\n    * 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.\n    * 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.\n\n    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. \n\n__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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aHsmkgRge1", "reviewer": "Reviewer_xf7T", "summary": "In this article the authors present new results regarding the expressivity of GNNs with respect to branching strategies in mixed integer linear programming (MILP). In particular, they explicit a class of MILPs (called MP-tractable) such that for each MILP in the class, there exists a MP-GNN that can ``mimic'' the strong branching heuristic in some senses, a popular and performant heuristic used in MILP solvers. More precisely, they show that the MP-GNN can compute a strong branching score (that the authors define), for each of the variable to be branched in the MILP. The authors also extend this result to more general MILPs, using some 2-Folklore GNN, a variant of the standard message passing GNNs. The main results are stated in Theorem 4.4 and Theorem 4.7, and hold in probability, given a distribution on the considered class of MILPs.", "questions": "- Following first point in the weakness section: the authors mention that this gives a practical way of checking if one can compute the branching scores with a GNN. However, the very definition of MP-tractability implies that the partition obtained by color refinement is specific to the graph of the MILP. But to check that definition, one needs to verify this for every other graph input, and there are potentially exponentially many of them. This makes the verification computationally difficult, not polynomally as the authors claim.\n\n- On the theoretical side, there is no discussion about the role of m and n in the results. In the current form of the statements, m and n are fixed, so the size of the graph inputs is fixed. Can the authors explain why this is a not a fundamental issue if one is interested in say, training a GNN that predicts SB scores across MILPs of different sizes?", "limitations": "The authors address in a few sentences the limitations and follow-up of their work in the conclusion.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper contributes to lay some theoretical foundations of the use of GNNs for MILPs, and more generally combinatorial optimization. This is critical as the use of machine learning in optimization solvers is increasing.\n\nThe authors combine results in Approximation Theory (to approximate the SB function using GNNs) and known results about connections between color refinement and message passing GNNs.\n\nOverall, this draft provides a serious study. I find the motivations and the current results interesting. \nHowever, the paper in its current form has some issues, and I have have several concerns stated below.", "weaknesses": "- Concerning MP-tractability, I have a major concern that I state in the question list below (as I want to make sure I understood the result correctly).  I would be willing to revise my evaluation if the authors clarify this.\n\n- The experiments are carried out on 100 instances, 6 constraints and 20 variables. The authors mention that one of the follow-ups is to conduct large-scale experiments, but a few thousand or say 10000 could already been more convincing (before large-scale ones).\n\n- Some major statements are imprecise mathematically: Theorem 4.4. In which space does $G$ belong to: $G^{\\text{MP}}$ or $G$?\n\n- The notations and presentation of the proofs in the appendix is not very well written, making them difficult to follow and verify, despite their relative simplicity (in essence).\n\n\tSome examples:\n\n\t-  in Theorem A.3, the statement starts with $G \\sim \\bar{G}$, and a) states ``If $G \\sim \\bar{G}$ then [...]'' \n\t-  in The statement of Theorem A.5, where you introduce $(\\sigma_V, \\sigma_W) * G$ without explaining the notation beforehand.  \n\t-  Lemma C.8, one can group several substatements to simplify the presentation. \n\t\nMore generally, since the paper's main contributions are theoretical, the authors should reserve a section or subsection in the main paper to present sketches of proofs of their main results, that convey the key elements and ideas. Also, the authors should explain the main new ideas or techniques they introduced to obtain their results (or if they are essentially extensions or existing techniques, and so on), for example in comparison with the reference [11] that the authors cite.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments! Please find our responses below:\n\n* __[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. \n    \n    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.\n\n    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.\n\n* __[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.\n    \n* __[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].\"\n\n    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.\n\n* __[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$.\n    \n* __[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:\n    * 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}}$ ...\" \n    * 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$.\n    * 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.\n\n__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.\n\n(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.\n\n(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.\n\n(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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MQbo8xLZPU", "reviewer": "Reviewer_VcHk", "summary": "This submission analyzes the capacity of message-passing graph neural networks (MP-GNNs) in learning strong branching (SB) scores. A class of MILPs, so-called MP-tractable MILPs, are identified as a suitable class, whose SB scores could be accurately approximated by common MP-GNNs. For general MILPs, the authors also prove a similar result using more complex models, i.e., 2-FGNNs. Counterexamples are constructed to show that MP-GNNs cannot distinguish two different MP-intractable MILPs. Experiments on several small problems support the theoretical results.", "questions": "1. Have the authors considered adding more features to handle the incapacity? For instance, adding one more feature for each variable representing the number of variables associated with this variable by one or multiple constraints. In (4.1), this feature will be $8$ for all $8$ variables. In (4.2), however, this feature will be $3$ for $x_1,\\dots, x_6$, while $2$ for $x_7$ and $x_8$. Then MP-GNN is probably capable of distinguishing these two MILPs.\n\n2. Is root SB considered in all experiments? How much one can benefit from applying leaf SB? if one applies L2B in leaf nodes, I think local cuts will help break MP-intractability by involving more constraints (local cuts), or changing bounds of variables, etc.. \n\n3. The tested MILPs are quite small and there are just a few features, why using $3$ layers with $1024$ hidden features in each MLP? The models are large and very likely to overfit. Also, why there are fewer parameters in 2-FGNN comparing to MP-GNN as shown in lines 935 - 936?", "limitations": "See above for the limitations of this paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper has three theoretical contributions:\n\n- MP-GNNs are universal approximations to SB scores of MP-tractable MILPs.\n\n- MP-GNNs can not approximate arbitrary MILPs accurately. Counterexamples are constructed.\n\n- 2-FGNNs are universal approximations to SB scores of all MILPs.\n\nThe theoretical part is solid. I do not check every step but the skeleton of each proof looks quite reasonable. Considering the countless works on directly using various ML techniques to solve problems without fully thinking the compatibility between models and problems, such work is more valuable to me.", "weaknesses": "1. My first concern is about the MILP graph representation, which forms the basis of the proposed theories. Such representation is quite intuitive but relatively simple: the relationships between variables are not fully expressed. There could be multiple graphs with the same features, as well as the same local adjacent relationships, e.g., (4.1) and (4.2). I understand that there will be too many edges if one links any two variables appearing in the same constraint, and that 2-FGNN is a good alternative to capture such relationships without a over-complex graph structure. But I think the incapacity does not come from MP-GNNs but from the MILP graph representations.\n\n2. My second concern comes from the numerical results.\n\n- No experiments on MILP benchmarks. Testing on random instances with the same (and small) size is not enough to show that both MP-GNN and 2-FGNN are good approximations for all MP-tractable MILPs.  \n\n- The only test on (4.1) and (4.2) indeed shows that 2-FGNN outperforms MP-GNN. However, it is unclear that how much the solver can benefit from such improvement from $\\sim 10^{-2}$ to $\\sim 10^{-15}$ on SB score error, especially considering the extra cost on training $\\sim 40000$ epochs. Providing the training time for both models and improved solving time using 2-FGNN will be more convincing.   \n\n- There is no information to show how common MP-intractable MILPs are. From my perspective, MP-intractability is mainly caused by symmetries between variables and constraints. I wonder how likely a real MILP problem has such symmetries.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable comments! Please find our responses below:\n* __[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.\n\n    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].\"\n    \n* __[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.\n\n    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.\n\n* __[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. \n    \n    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.\n\n    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:  \n    * 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.\n    * 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.\n\n* __[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\".\n    \n* __[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.\n\n* __[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. \n    \n    We definitely agree with you that there might be less symmetry in leaf SB due to the local cuts.\n\n* __[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).\n\n    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}$.\n\n    | Embedding size | 64 | 128 | 256 | 512 | 1,024 | 2,048 |\n    |---|---|---|---|---|---|---|\n    | Epochs to reach $10^{-12}$ error | 18,762 | 7,474 | 4,412 | 2,484 | 1,128 | 1,174 |\n\n    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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: After the rebuttal, all five reviewers agreed that this paper is worth being accepted, mainly for its important theoretical contribution regarding the expressive power of GNNs for strong branching, a strategy used in (the theory and practice) of mixed-integer programming. "Learning to branch" is a big deal in the MIP world, and this paper provides important fundamental insights into what is generally possible.

Some doubts regarding the presentation remain, and even though everyone is ok with acceptance in the end, I urge the authors to take the reviewer comments very serious when preparing the final version.
Decision: Accept (poster)