Rethinking the Capacity of Graph Neural Networks for Branching Strategy

Authors: ziang  chen
jialin  liu
xiaohan  chen
xinshang  wang
wotao  yin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:19:07

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.

Main paper: 
 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 to planning and scheduling, and are in general NP-hard. The branch-and-bound (BnB) algorithm [33] is the core of a MILP solver. It works by repeatedly solving relaxed versions of the problem, called linear relaxations, which allow the integer variables to take on fractional values. If a relaxation'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 a linear relaxation into two subproblems. When branching, the solver selects a variable with a fractional value in the relaxation's solution and create two new subproblems. In one subproblem, the variable is forced to be less than or equal to the nearest integer 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.A well-chosen branching variable can lead to a significant improvement in the lower bound, which is a quantity that can quickly prove that a 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, a poor choice may result in branches that do little to improve the bounds or reduce the solution space, thus leading to a large number of subproblems to be solved, significantly increasing the total solution time. The choice of which variable to branch on is a 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 to 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-bound (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 a smaller search space. In practice, MILP solvers use heuristics to limit the use of SB to where it 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 [2, 5, 19, 24, 25, 29, 35, 56, 58] , 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 [45, 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 on a set of similar MILPs. Although SB can theoretically solve LP relaxations in parallel, the time required for different LPs may vary greatly, and there is a 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 a more practical choice for accelerating the branching variable selection process. Furthermore, additional problem-specific characteristics can be incorporated into the ML model, allowing it to make more informed branching decisions tailored to each problem instance.Graph neural network (GNN) stands out as an effective class of ML models for L2B, surpassing other models like SVM and MLP, due to the excellent scalability and the permutationinvariant/equivariant 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 approach [15, 19] has gained prominence in not only L2B but various other MILP-related learning tasks [13, 17, 26, 30, 32, 36, 40, 43, 44, 48, 50-52, 54, 57] . More details are provided in Section 2.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 or 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)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 [4, 10, 22, 28, 37, 39, 47, 55, 59] , their capacities in approximating SB remains largely unexplored.The closest studies [11, 12] have explored GNNs' ability to represent properties of linear programs (LPs) and MILPs, such as feasibility, boundedness, or optimal solutions, but have not specifically focused on branching strategies. Recognizing this gap, our paper makes the following contributions: • In the context of L2B using GNNs, we first focus on the most widely used type: message-passing GNNs (MP-GNNs). Our study reveals that MP-GNNs can reliably predict SB results, but only for a specific class of MILPs that we introduce as message-passing-tractable (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 a 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 GNNs (2-FGNNs), a type of higher-order GNN with enhanced expressive power. Our results show that 2-FGNNs can reliably answer question (1.1) positively, effectively replicating SB results across any distribution of MILP problems, surpassing the capabilities of standard MP-GNNs. Overall, as a series of works have empirically shown that learning an MP-GNN as a fast approximation of SB significantly benefits the performance of an MILP solver on specific data sets [2, 5, 19, 24, 25, 29, 35, 56, 58] , our goal is to determine whether there is room, in theory, to further understand and improve the GNNs' performance on this task. 
preliminaries and problem setup: 
 We consider the MILP defined in its general form as follows:EQUATIONwhereA ∈ R m×n , b ∈ R m , c ∈ R n , • ∈ {≤, =, ≥} m is the type of constraints, ℓ ∈ ({-∞} ∪ R) nand u ∈ (R ∪ {∞}) n are the lower bounds and upper bounds of the variable x, and I ⊂ {1, 2, . . . , n} identifies which variables are constrained to be integers.Here we present an approach to represent MILP as a bipartite graph, termed the MILP-graph. This conceptualization was initially proposed by [19] and has quickly become a prevalent model in ML for MILP-related tasks. The MILP-graph is defined as a tuple G = (V, W, A, F V , F W ), where the components are specified as follows: V = {1, 2, . . . , m} and W = {1, 2, . . . , n} are sets of nodes representing the constraints and variables, respectively. An edge (i, j) connects node i ∈ V to node j ∈ W if the corresponding entry A ij in the coefficient matrix of (2.1) is non-zero, with A ij serving as the edge weight. F V are features/attributes of constraints, with features v i = (b i , • i ) attached to node i ∈ V . F W are features/attributes of variables, with features w j = (c j , ℓ j , u j , δ I (j)) attached to node j ∈ W , where δ I (j) ∈ {0, 1} indicates whether the variable x j is integer-constrained.We defineN W (i) =: {j ∈ W : A ij ̸ = 0} ⊂ W as the neighbors of i ∈ V and similarly define N V (j) =: {i ∈ V : A ij ̸ = 0} ⊂ V .This graphical representation completely describes a MILP's information, allowing us to interchangeably refer to a MILP and its graph throughout this paper. An illustrative example is presented in Figure 1 . We also introduce a space of MILP-graphs: Definition 2.1 (Space of MILP-graphs). We use G m,n to denote the collection of all MILP-graphs induced from MILPs of the form (2.1) with n variables and m constraints. 1Message-passing graph neural networks (MP-GNNs) are a class of GNNs that operate on graph-structured 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, F V , F W ), and each node in W is associated with a real-number output. We use the standard MP-GNNs for MILPs in the literature [12, 19] .Specifically, the initial layer assigns features s 0 i , t 0 j for each node asEQUATIONFigure 1 : An illustrative example of MILP and its graph representation.• s 0 i = p 0 (v i ) for each constraint i ∈ V , and t 0 j = q 0 (w j ) for each variable j ∈ W . Then message-passing layers l = 1, 2, . . . , L update the features via• s l i = p l s l-1 i , j∈N W (i) f l (t l-1 j , A ij )for each constraint i ∈ V , and• t l j = q l t l-1 j , i∈N V (j) g l (s l-1 i , A ij )for each variable j ∈ W . Finally, the output layer produces a read-number output y j for each node j ∈ W :• y j = r i∈V s L i , j∈W t L j , t L j .In practice, functions {p l , q l , f l , g l } L l=1 , r, p 0 , q 0 are learnable and usually parameterized with multilinear 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 as follows.Definition 2.2 (Space of MP-GNNs). We use F MP-GNN to denote the collection of all MP-GNNs constructed as above with p l , q l , f l , g l , r being continuous with f l (•, 0) ≡ 0 and g l (•, 0) ≡ 0. 2 Overall, any MP-GNN F ∈ F MP-GNN maps a MILP-graph G to a n-dim vector: y = F (G) ∈ R n .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 WL tests [9] . Since then, there has been growing literature about high-order GNNs and other variants including high-order folklore GNNs [4, 20-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 a common node. Let G = (V, W, A, F V , F W ) be the input graph. The initial layer performs:• s 0 ij = p 0 (v i , w j , A ij )for each constraint i ∈ V and each variable j ∈ W , and • t 0 j1j2 = q 0 (w j1 , w j2 , δ j1j2 ) for variables j 1 , j 2 ∈ W , where δ j1j2 = 1 if j 1 = j 2 and δ j1j2 = 0 otherwise. For internal layers l = 1, 2, . . . , L, compute• s l ij = p l s l-1 ij , j1∈W f l (t l-1 j1j , s l-1 ij1) for all i ∈ V, j ∈ W , and• t l j1j2 = q l t l-1 j1j2 , i∈V g l (s l-1 ij2 , s l-1 ij1) for all j 1 , j 2 ∈ W . The final layer produces the output y j for each node j ∈ W :• y j = r i∈V s L ij , j1∈W t L j1j. Similar to MP-GNNs, the functions within 2-FGNNs, including {p l , q l , f l , g l } L l=1 , r, p 0 , q 0 , are also learnable and typically parameterized with MLPs. The space of 2-FGNNs is defined with: Definition 2.3. We use F 2-FGNN to denote the set of all 2-FGNNs with continuous p l , q l , f l , g l , r.Any 2-FGNN, F ∈ F 2-FGNN , maps a MILP-graph G to a 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. 
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, 25, 35, 48, 56, 58 ], yet it still lacks theoretical foundations. Its motivation stems from two key observations introduced earlier in Section 1, 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, a "tree" refers to a 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 "neos-3761878-oglio" from MIPLIB [23] . When solved using SCIP [7, 8] 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.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 a SB score, a 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 not qualify as branching candidates are assigned a zero score. Compiling these scores for each variable results in an n-dimensional SB score vector, denoted as SB(G) = (SB(G) 1 , SB(G) 2 , . . . , SB(G) n ).Consequently, the task of approximating SB with GNNs can be described with a mathematical language: finding an F ∈ F MP-GNN or F ∈ F 2-FGNN such that F (G) ≈ SB(G). Formally, it is: Formal statement of Problem (1.1): Given a distribution of G, is there F ∈ F MP-GNN or F ∈ F 2-FGNN such that ∥F (G) -SB(G)∥ 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 ∈ G m,n . For any j ∈ {1, 2, . . . , n}, lj ∈ {-∞} ∪ R, and ûj ∈ R ∪ {+∞}, we denote by LP(G, j, lj , ûj ) the following LP problem obtained by changing the lower/upper bound of x j in the LP relaxation of (2.1):min x∈R n c ⊤ x, s.t. Ax • b, lj ≤ x j ≤ ûj , l j ′ ≤ x j ′ ≤ u j ′ for j ′ ∈ {1, 2, . . . , n}\{j}. Definition 3.2 (Strong branching scores). Let G ∈ G m,n be a MILP-graph associated with the problem (2.1) whose LP relaxation is feasible and bounded. Denote f * LP (G) ∈ R as the optimal objective value of the LP relaxation of G and denote x * LP (G) ∈ R n as the optimal solution with the smallest ℓ 2 -norm. The SB score SB(G) j for variable x j is defined viaSB(G) j = 0, if j / ∈ I, (f * LP (G, j, l j , ûj ) -f * LP (G)) • (f * LP (G, j, lj , u j ) -f * LP (G)), otherwise,where f * LP (G, j, l j , ûj ) and f * LP (G, j, lj , u j ) are the optimal objective values of LP(G, j, l j , ûj ) and LP(G, j, lj , u j ) respectively, with ûj = ⌊x * LP (G) j ⌋ being the largest integer no greater than x * LP (G) j and lj = ⌈x * LP (G) j ⌉ being the smallest integer no less than x * LP (G) j , for j = 1, 2, . . . , n. Remark: LP solution with the smallest ℓ 2 -norm. We only define the SB score for MILP problems with feasible and bounded LP relaxations; otherwise the optimal solution x * LP (G) does not exist. If the LP 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 is uniquely defined, in Definition 3.2, we use the optimal solution with the smallest ℓ 2 -norm, which is unique.v 1 v 2 w 1 w 2 w 3 Initialization l = 1 l = 2The WL test (Algorithm 1) MILP-graph G min x 1 + x 2 + x 3 , s.t.x 1 + x 2 + x 3 ≤ 1, x 1 + x 2 ≤ 1, 0 ≤ x 1 , x 2 , x 3 ≤ 1, x 1 , x 2 , x 3 ∈ Z.MILP formula Figure 2 : An illustrative example of color refinement and partitions. Initially, all variables share a common color due to their identical node attributes, as do the constraint nodes. After a round of the WL test, x 1 and x 2 retain their shared color, while x 3 is assigned a distinct color, as it connects solely to the first constraint, unlike x 1 and x 2 . 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 to SB at leaf nodes within the BnB framework. By interpreting the MILP-graph 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, root 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 [14] . (Refer to Appendix D.1)4 Main results 
mp-gnns can represent sb for mp-tractable milps: 
 In this subsection, we define a class of MILPs, named message-passing-tractable (MP-tractable) MILPs, and then show that MP-GNNs can represent SB within this class.To define MP-tractability, we first present the Weisfeiler-Lehman (WL) test [53] , a well-known criterion for assessing the expressive power of MP-GNNs [55] . The WL test in the context of MILP-graphs is stated in Algorithm 1. It follows exactly the same updating rule as the MP-GNN, differing only in the local updates performed via hash functions.Require: A graph instance G ∈ G m,n and iteration limit L > 0.1: Initialize withC V 0 (i) = HASH V 0 (v i ), C W 0 (j) = HASH W 0 (w j ). 2: for l = 1, 2, • • • , L do 3: C V l (i) = HASH V l C V l-1 (i), C W l-1 (j), A ij : j ∈ N W (i) . 4: C W l (j) = HASH W l C W l-1 (j), C W l-1 (i), A ij : i ∈ N V (j) . 5: end for 6: Output: Final colors C V L (i) for all i ∈ V and C W L (j) for all j ∈ V .The WL test can be understood as a color refinement algorithm. In particular, each vertex in G is initially assigned a color C V 0 (i) or C W 0 (j) according to its initial feature v i or w j . Then the vertex colors C V l (i) and C W l (j) are iteratively refined via aggregation of neighbors' information and corresponding edge weights. If there is no collision of hash functions 3 , then two vertices are of the same color at 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 a color refinement process is illustrated by an example shown in Figure 2 .One can also view a vertex coloring as a partition, i.e., all vertices are partitioned into several classes such that two vertices are in the same class if and only if they are of the same color. After each round of Algorithm 1, the partition always becomes finer if no collision happens, though it may not be strictly finer. The following theorem suggests that this partition eventually stabilizes or converges, with the final limit uniquely determined by the graph G, independent of the hash functions selected. Theorem 4.1 ([11, Theorem A.2]). For any G ∈ G m,n , the vertex partition induced by Algorithm 1 (if no collision) will converge within O(m + n) iterations to a partition (I, J ), where I = {I 1 , I 2 , . . . , I s } is a partition of {1, 2, . . . , m} and J = {J 1 , J 2 , . . . , J t } is a partition of {1, 2, . . . , n}, and that partition (I, J ) 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 (Message-passing-tractability). For G ∈ G m,n , let (I, J ) be the partition as in Theorem 4.1. We say that G is message-passing-tractable (MP-tractable) if for any p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}, all entries of the submatrix (A ij ) i∈Ip,j∈Jq are the same. We use G MP m,n ⊂ G m,n to denote the subset of all MILP-graphs in G m,n that are MP-tractable. 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 = {{1, 2}, {3}}. According to Definition 4.2, one must examine the following submatrices to determine whether the MILP is MP-tractable:A[1, 1 : 2] = [1, 1], A[2, 1 : 2] = [1, 1], A[1, 3] = [1], A[2, 3] = [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 a Borel regular probability measure on G m,n andP[SB(G) ∈ R n ] = 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 P[SB(G) ∈ R n ] = 1. In Definition 3.2, the linear relaxation of G is feasible and bounded, which implies f * LP (G) ∈ R. However, it is possible for a linear program that is initially bounded and feasible to become infeasible upon adjusting a single variable's bounds, potentially resulting in f * LP (G, j, l j , ûj ) = +∞ or f * LP (G, j, lj , u j ) = +∞ and leading to an infinite SB score: SB(G) j = +∞. Although we ignore such a case by assuming P[SB(G) ∈ R n ] = 1, it is straightforward to extend all our results by simply representing +∞ as -1 considering SB(G) j 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-passing tractable with probability one, we can show the existence of an MP-GNN capable of accurately mapping a MILP-graph G to its corresponding SB score, with an arbitrarily high degree of precision and probability. The formal theorem is stated as follows. Theorem 4.4. Let P be any probability distribution over G m,n that satisfies Assumption 4.3 andP[G ∈ G MP m,n ] = 1.Then for any ε, δ > 0, there exists a GNN F ∈ F MP-GNN such thatP[∥F (G) -SB(G)∥ ≤ δ] ≥ 1 -ϵ.The proof of Theorem 4.4 is deferred to Appendix A, with key ideas outlined here. First, we show that if Algorithm 1 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 on this result, along with a generalized version of the Stone-Weierstrass theorem and Luzin's theorem, we reach the final conclusion.Let us compare our findings with [12] that establishes the existence of an MP-GNN capable of directly mapping G to 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 a 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, J ) have cardinality one: |I p | = 1 and |J q | = 1 for all p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}. Consequently, any unfoldable MILP must be MP-tractable because the submatrices under the partition of an unfoldable MILP (A ij ) i∈Ip,j∈Jq must be 1 × 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-tractability. Our Theorem 4.4 demonstrates that, to illustrate the expressive power of MP-GNNs in approximating SB, MP-tractability suffices; we do not need to make assumptions as strong as those required when considering MP-GNN for approximating the optimal solution.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:EQUATION)EQUATIONWe will prove in Appendix B that these two MILP instances have different SB scores, but they cannot be distinguished by any MP-GNN in the sense that for any F ∈ F MP-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 (4.2) can be generalized easily to 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, (4.1) and (4.2), are not MP-tractable. It can be verified that for both (4.1) and (4.2), the partition as in Theorem 4.1 is given by I = {I 1 } with I 1 = {1, 2, . . . , 8} and J = {J 1 } with J 1 = {1, 2, . . . , 8}, i.e., all vertices in V form a class and all vertices in W form the other class. Then the matrices (A ij ) i∈I1,j∈J1 and ( Āij ) i∈I1,j∈J1 are just A and Ā, the coefficient matrices in (4.1) and (4.2), and have both 0 and 1 as entries, which does not satisfies Definition 4.2.Based on Theorem 4.5, we can directly derive the following corollary by considering a simple discrete uniform distribution P on only two instances (4.1) and (4.2). Corollary 4.6. There exists a probability distribution P over G m,n satisfying Assumption 4.3 and constants ϵ, δ > 0, such that for any MP-GNN F ∈ F MP-GNN , it holds thatP[∥F (G) -SB(G)∥ ≥ δ] ≥ ϵ.This corollary indicates that the assumption of MP-tractability in Theorem 4.4 is not removable.Although the universal approximation of MP-GNNs for SB scores is conditioned on the MPtractability, we find an unconditional positive result stating that when we increase the order of GNNs a bit, it is possible to represent SB scores of MILPs, regardless of the MP-tractability. Theorem 4.7. Let P be any probability distribution over G m,n that satisfies Assumption 4.3. Then for any ε, δ > 0, there exists a GNN F ∈ F 2-FGNN such that 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 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 WL test [41] .P[∥F (G) -SB(G)∥ ≤ δ] ≥ 1 -ϵ.Theorem ((m + n) • nnz(A)), which is linear in terms of (m + n) and nnz(A). In contrast, solving an MILP or even calculating its all the SB scores requires significantly higher complexity. To calculate the SB score of each MILP, one needs to solve at most n LPs. We denote the complexity of solving each LP as CompLP(m, n). Therefore, the overall complexity of calculating SB scores is O(n • 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.While verifying MP-tractability is polynomial in complexity, the complexity of GNNs is 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-intractable), 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 2 (MP-tractable), only two of the three variables, x 1 and x 2 , 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-intractability. This phenomenon is commonly seen in practical MILP datasets, such as MIPLIB 2017 [23] . According to [12] , approximately one-quarter of examples show significant symmetry in over half of the variables. 
numerical results: 
 We implement numerical experiments to validate our theoretical findings in Section 4.We train an MP-GNN and a 2-FGNN with L = 2, where we replace the functions f l (t l-1 j , A ij ) and g l (s l-1 i , A ij ) in the MP-GNN by A ij f l (t l-1 j ) and A ij g l (s l-1 i ) to guarantee that they take the value 0 whenever A ij = 0. For both GNNs, p 0 , q 0 are parameterized as linear transformations followed by a non-linear activation function; {p l , q l , f l , g l } L l=1 are parameterized as 3-layer multi-layer perceptrons (MLPs) with respective learnable parameters; and the output mapping r is parameterized as a 2-layer MLP. All layers map their input to a 1024-dimensional vector and use the ReLU activation function. With θ denoting the set of all learnable parameters of a network, we train both MP-GNN and 2-FGNN to fit the SB scores of the MILP dataset G, by minimizing1 2G∈G ∥F θ (G) -SB(G)∥ 2 with respect to θ, using Adam [31] . The networks and training scheme is implemented with Python and TensorFlow [1] . The numerical experiments are conducted on a single NVIDIA Tesla V100 GPU for two datasets:• We randomly generate 100 MILP instances, with 6 constraints and 20 variables, that are MPtractable with probability 1. SB scores are collected using SCIP [6] . More details about instance generation are provided in Appendix E.• We train the MP-GNN and 2-FGNN to fit the SB scores of (4.1) and (4.2), i.e., the dataset only consists of two instances that are not MP-tractable. Experimental results: The numerical results are displayed in Figure 3 . One can see from Figure 3a that both MP-GNN and 2-FGNN can 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 4.5 and Theorem 4.7 and serves as a 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.In Figure 3b , the behavior of MP-GNN remains unchanged regardless of the number of parameters used, as guaranteed by Theorem 4.5. This error is intrinsically due to the structure of MP-intractable MILPs and cannot be reduced by adding parameters. Conversely, 2-FGNN can achieve near-zero loss with sufficient parameters, as 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 1 . The results suggest that larger embeddings improve model capacity to fit counterexamples. The gains level off beyond an embedding size of 1,024 due to increased training complexity. 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 1), 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 a training loss of 1.94 × 10 -4 , calculated as the average ℓ 2 norm of errors across all training instances.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: We provide the source code and data to 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. • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable). • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
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 MILPs within a specific class termed "message-passing-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 or 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 MP-tractability. 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, it is still unclear what is the required complexity/number of 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 Appendix E.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA] Justification: Our experiments are only for directly validating the theoretical findings rather than competing with state-of-the-arts and no statistical significance needs to 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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • 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 or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are 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. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: Information on the computation resources used for experiments are provided in Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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:• 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: This section presents the proof of Theorem 4.4. We define the separation power of WL test in Definition A.1 and prove that two MP-tractable MILP-graphs, or two vertices in a single MP-tractable graph, indistinguishable by WL test must share the same SB score in Theorem A.3. In other words, WL test has sufficient separation power to distinguish MP-tractable MILP graphs, or vertices in a single MP-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 m,n and let C V l (i), C W l (j) and CV l (i), CW l (j) be the colors generated by the WL test (Algorithm 1) for G and Ḡ. We sayG W ∼ Ḡ if C V L (i) : i ∈ V = CV L (i) : i ∈ Vand C W L (j) = CW L (j), ∀ j ∈ W holds for any L and any hash functions. Theorem A.2 ([11, Theorem A.2]). The partition defined in Theorem 4.1 satisfies:(a) v i = v i ′ , ∀ i, i ′ ∈ I p , p ∈ {1, 2, . . . , s}, (b) w j = w j ′ , ∀ j, j ′ ∈ J q , q ∈ {1, 2, . . . , t}, (c) {{A ij : j ∈ J q }} = {{A i ′ j : j ∈ J q }}, ∀ i, i ′ ∈ I p , p ∈ {1, 2, . . . , s}, q ∈ {1, 2, . . . , t}, (d) {{A ij : i ∈ I p }} = {{A ij ′ : i ∈ I p }}, ∀ j, j ′ ∈ J q , p ∈ {1, 2, . . . , s}, q ∈ {1, 2, . . . , t},where {{}} denotes the multiset 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 ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}, different rows/columns of the submatrix (A ij ) i∈Ip,j∈Jq provide the same multiset of entries.With the above preparations, we can state and prove the main result now. Proof. (a) Since G W ∼ Ḡ, after applying some permutation on V (relabelling vertices in V ) in the graph Ḡ, the two G and Ḡ share the same partition I = {I 1 , I 2 , . . . , I s } and J = {J 1 , J 2 , . . . , J t } as in Theorem A.2 and we have • For any p ∈ {1, 2, . . . , s}, v i = vi is constant over all i ∈ I p ,• For any q ∈ {1, 2, . . . , t}, w j = wj is constant over all j ∈ J q ,• For any p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}, {{A ij : j ∈ J q }} = {{ Āij : j ∈ J q }} is constant over all i ∈ I p ,• For any p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t},{{A ij : i ∈ I p }} = {{ Āij : i ∈ I p }} is constant over all j ∈ J q .Here, we slightly abuse the notation not to distinguish Ḡ and the MILP-graph obtained from Ḡ by relabelling vertice in V , and these two graphs have exactly the same SB scores since the vertices in W are not relabelled.Note that both G and Ḡ are MP-tractable, i.e., for any p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}, (A ij ) i∈Ip,j∈Jq and ( Āij ) i∈Ip,j∈Jq are both matrices with identical entries, which combined with the third and the fourth conditions above implies that A ij = Āij for all i ∈ I p and j ∈ J q . Therefore, we have G = Ḡ and hence SB(G) = SB( Ḡ).(b) The result is a directly corollary of (a) by considering G and the MILP-graph obtained from G by relabeling j 1 as j 2 and relabeling j 2 as j 1 .In addition to Theorem A.3, we also need the following two theorem to prove Theorem 4.4.Theorem A.4 (Lusin's theorem [16, Theorem 1.14] ). Suppose that µ is a Borel regular measure on R n and that f : R n → R m is µ-measurable, i.e., for any open subset U ⊂ R m , f -1 (U ) is µ-measurable. Then for any µ-measurable X ⊂ R n with µ(X) < ∞ and any ϵ > 0, there exists a compact set E ⊂ X with µ(X\E) < ϵ, such that f | E is continuous.Theorem A.5 ([11, Theorem E.1]). Let X ⊂ G m,n be a compact subset that is closed under the action of S m × S n . Suppose that Φ ∈ C(X, R n ) satisfies the followings:(a) For any σ V ∈ S m , σ W ∈ S n , and G ∈ X, it holds that Φ((σV , σ W ) * G) = σ W (Φ(G)),where (σ V , σ W ) * G represents the MILP-graph obtained from G by reordering vertices with permutations σ V and σ W .(b) Φ(G) = Φ( Ḡ) holds for all G, Ĝ ∈ X with G W ∼ Ḡ.(c) Given any G ∈ X and any j 1 , j 2 ∈ {1, 2, . . . , n}, if C W L (j 1 ) = C W L (j 2 ) holds for any L and any hash functions, then Φ(G) j1 = Φ(G) j2 .Then for any ϵ > 0, there exists F ∈ F MP-GNN such thatsup G∈X ∥Φ(G) -F (G)∥ < ϵ.Proof of Theorem 4.4. Lemma F.2 and Lemma F.3 in [11] prove that the function that maps LP instances to its optimal objective value/optimal solution with the smallest ℓ 2 -norm is Borel measurable. Thus, SB : G m,n ⊃ SB -1 (R n ) → R n is also Borel measurable, and is hence P-measurable due to Assumption 4.3. In addition, G MP m,n is a Borel subset of G m,n since the MP-tractability is defined by finitely many operations of comparison and aggregations. By Theorem A.4 and the assumptionP[G ∈ G MP m,n ] = 1, there exists a compact subset X 1 ⊂ G MP m,n ∩ SB -1 (R n ) such that P[G m,n \X 1 ]≤ ϵ and SB| X1 is continuous. For any σ V ∈ S m and σ W ∈ S n , (σ V , σ W ) * X 1 is also compact and SB| (σ V ,σ W ) * X1 is also continuous by the permutation-equivariance of SB. SetX 2 = σ V ∈Sm,σ W ∈Sn (σ V , σ W ) * X 1 .Then X 2 is permutation-invariant and compact withP[G m,n \X 2 ] ≤ P[G m,n \X 1 ] ≤ ϵ.In addition, SB| X2 is continuous by pasting lemma.The rest of the proof is to apply Theorem A.5 for X = X 2 and Φ = SB, for which we need to verify the four conditions in Theorem C.10. Condition (a) is true since SB is permutation-equivalent by its definition. Conditions (b) and (c) follow directly from Theorem A.3. According to Theorem A.5, there exists someF ∈ F 2-FGNN such that sup G∈X2 ∥F (G) -SB(G)∥ ≤ δ.Therefore, one hasP[∥F (G) -SB(G)∥ > δ] ≤ P[G m,n \X 2 ] ≤ ϵ,which completes the proof.In this section, we verify that the MILP instances (4.1) and (4.2) prove Theorem 4.5. We will first show that they have different SB scores while cannot be distinguished by any MP-GNNs.Different SB scores Denote the graph representation of (4.1) and (4.2) as G and Ḡ, respectively. For both (4.1) and (4.2), the same optimal objective value is 4 and the optimal solution with the smallest ℓ 2 -norm is (1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2). To calculate SB(G) j or SB( Ḡ) j , it is necessary create two LPs for each variable x j . In one LP, the upper bound of x j is set to ûj = ⌊1/2⌋ = 0, actually fixing x j at its lower bound l j = 0. Similarly, the other LP sets x j to 1.For the problem (4.1), even if we fix x 1 = 1, the objective value of the LP relaxation can still achieve 4 by x = (1, 0, 1, 0, 1, 0, 1, 0). A similar observation also holds for fixing x 1 = 0. Therefore, the SB score for x 1 (also for any x j in (4.1)) is 0. In other words, SB(G) = (0, 0, 0, 0, 0, 0, 0, 0). However, for the problem (4.2), if we fix x 1 = 1, then the optimal objective value of the LP relaxation is 9/2 since 8 i=1x i = 1 + (x 2 + x 3 ) + 1 2 (x 4 + x 5 ) + 1 2 (x 5 + x 6 ) + 1 2 (x 6 + x 4 ) + (x 7 + x 8 ) ≥ 9/2and the above inequality is tight as x = (1, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2). If we fix x 1 = 0, then x 2 , x 3 ≥ 1 and the optimal objective value of the LP relaxation is also 9/2 since 8 i=1x i ≥ 0 + 1 + 1 + 1 2 (x 4 + x 5 ) + 1 2 (x 5 + x 6 ) + 1 2 (x 6 + x 4 ) + (x 7 + x 8 ) ≥ 9/2,and the equality holds when x = (0, 1, 1, 1/2, 1/2, 1/2, 1/2, 1/2). Therefore, the the SB score for x 1 (also for anyx i (1 ≤ i ≤ 6) in (4.2)) is (9/2 -4) • (9/2 -4) = 1/4.If we fix x 7 = 1, the optimal objective value of the LP relaxation is still 4 since (1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1, 0) is an optimal solution. A similar observation still holds if x 7 is fixed to 0. Thus the SB scores for x 7 and x 8 are both 0. Combining these calculations, we obtain thatEQUATIONMP-GNNs' output Although G and Ḡ 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:v i = vi = (1, ≥), w j = wj = (1, 0, 1, 1), for all i ∈ {1, • • • , 8}, j ∈ {1, • • • , 8}.Considering the MP-GNN's initial step where s 0 i = p 0 (v i ) and t 0 j = q 0 (w j ), we can conclude that s 0 i = s0 i is a constant for all i and t 0 j = t0 j is a constant for all j, regardless of the choice of functions p 0 and q 0 . Thus, the initial layer generates uniform outcomes for nodes in V and W across both graphs, which is the induction base. Suppose that the principle of uniformity applies to s l i , sl i , t l j , tl j for some 0 ≤ l ≤ L -1. Since s l i , sl i are constant across all i, we can denote their common value as s l and hence s l = s l i = sl i for all i. Similarly, we can define t l with t l = t l j = tl j for all j. Then it holds thats l+1 i = sl+1 i = p l s l , 2f l (t l , 1) and t l+1 j = tl+1 j = q l t l , 2g l (s l , 1) , where we used {{A ij ′ : j ′ ∈ W }} = {{ Āij ′ : j ′ ∈ W }} = {{A i ′ j : i ′ ∈ W }} = {{ Āi ′ j : i ′ ∈ W }} = {{1, 1,0, 0, 0, 0, 0, 0}} for all i and j. This proves the uniformity for l + 1. Therefore, we obtain the existence of s L , t L such that s L i = sL i = s L and t L j = tL j = t L for all i, j. Finally, the output layer yields:y j = ȳj = r 8s L , 8t L , t L for all j ∈ {1, • • • , 8},which finishes the proof.This section presents the proof of Theorem 4.7. The central idea is to establish a separation result in the sense that two MILPs with distinct SB scores must be distinguished by at least one F ∈ F 2-FGNN , and then apply a generalized Stone-Weierstrass theorem in [4] .The 2-FWL test [9] , 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-isomorphism of the two graphs if the results vary. However, identical 2-FWL 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-FWL test for MILP-Graphs 1: Input: A graph instance G = (V, W, A, F V , F W ) and iteration limit L > 0. 2: Initialize with Refine the colorC V W 0 (i, j) = HASH V W 0 (v i , w j , A ij ), C W W 0 (j 1 , j 2 ) = HASH W W 0 (w j1 , w j2 , δ j1j2 ).C V W l (i, j) = HASH V W l C V W l-1 (i, j), (C W W l-1 (j 1 , j), C V W l-1 (i, j 1 )) : j 1 ∈ W , C W W l (j 1 , j 2 ) = HASH W W l C W W l-1 (j 1 , j 2 ), (C V W l-1 (i, j 2 ), C V W l-1 (i, j 1 )) : i ∈ V . 5: end for 6: Output: Final colors C V W L (i, j) for all i ∈ V, j ∈ W and C W W L (j 1 , j 2 ) for all j 1 , j 2 ∈ 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 ∈ V, j ∈ W or (j 1 , j 2 ) with j 1 , j 2 ∈ 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 {{((j 1 , j), (i, j 1 )) : j 1 ∈ W }} and the neighborhood of (j 1 , j 2 ) involves {{((i, j 2 ), (i, j (a) We define G ∼ 2 Ḡ if the followings hold for any L and any hash functions:C V W L (i, j) : i ∈ V, j ∈ W = CV W L (i, j) : i ∈ V, j ∈ W , (C.1) C W W L (j 1 , j 2 ) : j 1 , j 2 ∈ W = CW W L (j 1 , j 2 ) : j 1 , j 2 ∈ W . (C.2) (b) We define G W ∼ 2 Ḡif the followings hold for any L and any hash functions:C V W L (i, j) : i ∈ V = CV W L (i, j) : i ∈ V , ∀ j ∈ W, (C.3) C W W L (j 1 , j) : j 1 ∈ W = CW W L (j 1 , j) : j 1 ∈ W , ∀ j ∈ W. (C.4)It can be seen that (C.3) and (C.4) are stronger than (C.1) 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 ∈ W is the same. However, we can show that they are equivalent up to a permutation.Theorem C. W ∼ 2 σ W * Ḡ implies that G ∼ 2 Ḡ.We then prove the reverse direction, i.e., G ∼ 2 Ḡ implies G W ∼ 2 σ W * Ḡ for some σ W ∈ S n . It suffices to consider L and hash functions such that there are no collisons in Algorithm 2 and no strict color refinement in the L-th iteration when G and Ḡ are the input, which means that two edges are assigned with the same color in the L-th iteration if and only if their colors are the same in the (L -1)-th iteration. For anyj 1 , j 2 , j ′ 1 , j ′ 2 ∈ W , it holds that C W W L (j 1 , j 2 ) = C W W L (j ′ 1 , j ′ 2 ) =⇒ (C V W L (i, j 2 ), C V W L (i, j 1 )) : i ∈ V = (C V W L (i, j ′ 2 ), C V W L (i, j ′ 1 )) : i ∈ V =⇒ C V W L (i, j 1 ) : i ∈ V = C V W L (i, j ′ 1 ) : i ∈ V and C V W L (i, j 2 ) : i ∈ V = C V W L (i, j ′ 2 ) : i ∈ V .Similarly, one has thatEQUATIONC V W L (i, j 2 ) : i ∈ V = CV W L (i, j ′ 2 ) : i ∈ V ,and thatCW W L (j 1 , j 2 ) = CW W L (j ′ 1 , j ′ 2 ) =⇒ CV W L (i, j 1 ) : i ∈ V = CV W L (i, j ′ 1 ) : i ∈ V and CV W L (i, j 2 ) : i ∈ V = CV W L (i, j ′ 2 ) : i ∈ V .Therefore, for anyC ∈ C V W L (i, j) : i ∈ V : j ∈ W ∪ CV W L (i, j) : i ∈ V : j ∈ W , it follows from (C.2) that C W W L (j 1 , j 2 ) : C V W L (i, j 1 ) : i ∈ V = C V W L (i, j 2 ) : i ∈ V = C = CW W L (j 1 , j 2 ) : CV W L (i, j 1 ) : i ∈ V = CV W L (i, j 2 ) : i ∈ V = C . (C.5)Particularly, the number of elements in the two multisets in (C.5) should be the same, which implies that# j ∈ W : C V W L (i, j) : i ∈ V = C = # j ∈ W : CV W L (i, j) : i ∈ V = C ,which then leads toC V W L (i, j) : i ∈ V : j ∈ W = CV W L (i, j) : i ∈ V : j ∈ W .One can hence apply some permutation on W to obtain (C.3). Next we prove (C.4). For any j ∈ W , we haveC V W L (i, j) : i ∈ V = CV W L (i, j) : i ∈ V =⇒ C V W L (i 1 , j) = CV W L (i 2 , j) for some i 1 , i 2 ∈ V =⇒ (C W W L (j 1 , j), C V W l-1 (i 1 , j 1 )) : j 1 ∈ W = ( CW W L (j 1 , j), CV W l-1 (i 2 , j 1 )) : j 1 ∈ W for some i 1 , i 2 ∈ V =⇒ C W W L (j 1 , j) : j 1 ∈ W = CW W L (j 1 , j) : j 1 ∈ W ,which completes the proof.The following theorem establishes that the separation power of 2-FWL test is stronger than or equal to that of SB, in the sense that two MILP-graphs, or two vertices in a single graph, that cannot be distinguished by the 2-FWL test must share the same SB score. Theorem C.3. For any G, Ḡ ∈ G m,n , the followings are true:(a) If G W ∼ 2 Ḡ, then SB(G) = SB( Ḡ). (b) If G ∼ 2 Ḡ, then there exists some permutation σ W ∈ S n such that SB(G) = σ W (SB( Ḡ)). (c) If C W W L (j, j 1 ) : j ∈ W = C W W L(j, j 2 ) : j ∈ W holds for any L and any hash functions, then SB(G) j1 = SB(G) j2 .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(G), we change the upper/lower bound of x j and solve two LP problems. We can regard j ∈ W as a special node and if we fixed it in 2-FWL test, a 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. It is proved in [11] that the separation power of WL test is stronger than or equal to the properties of LPs. This is to say that even when fixing a 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 m,n , if G W ∼ 2 Ḡ,then for any j ∈ {1, 2, . . . , n}, lj ∈ {-∞} ∪ R, and ûj ∈ R ∪ {+∞}, the two LP problems LP(G, j, lj , ûj ) and LP( Ḡ, j, lj , ûj ) have the same optimal objective value. Theorem C.5 ([11] ). Consider two LP problems with n variables and m constraintsmin x∈R n c ⊤ x, s.t. Ax • b, l ≤ x ≤ u, (C.6)and minx∈R n c⊤ x, s.t. Āx • b, l ≤ x ≤ ū. (C.7)Suppose that there exist I = {I 1 , I 2 , . . . , I s } and J = {J 1 , J 2 , . . . , J t } that are partitions of V = {1, 2, . . . , m} and W = {1, 2, . . . , n} respectively, such that the followings hold:(a) For any p ∈ {1, 2, . . . , s}, (b i ,• i ) = ( bi , •i ) is constant over all i ∈ I p ;(b) For any q ∈ {1, 2, . . . , t}, (c j , l j , u j ) = (c j , lj , ūj ) is constant over all j ∈ J q ;(c) For any p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}, j∈Jq A ij = j∈Jq Āij is constant over all i ∈ I p .(d) For any p ∈ {1, 2, . . . , s} and q ∈ {1, 2, . . . , t}, i∈Ip A ij = i∈Ip Āij is constant over all j ∈ J q .Then the two problems (C.6) and (C.7) have the same feasibility, the same optimal objective value, and the same optimal solution with the smallest ℓ 2 -norm (if feasible and bounded).Proof of Theorem C.4. Choose L and hash functions such that there are no collisons in Algorithm 2 and no strict color refinement in the L-th iteration when G and Ḡ are the input. Fix any j ∈ W and construct the partions I = {I 1 , I 2 , . . . , I s } and J = {J 1 , J 2 , . . . , J t } as follows:• i 1 , i 2 ∈ I p for some p ∈ {1, 2, . . . , s} if and only ifC V W L (i 1 , j) = C V W L (i 2 , j).• j 1 , j 2 ∈ J q for some q ∈ {1, 2, . . . , t} if and only ifC W W L (j 1 , j) = C W W L (j 2 , j).Without loss of generality, we can assume that j ∈ J 1 . One observation is that J 1 = {j}. This is becausej 1 ∈ J 1 implies that C W W L (j 1 , j) = C W W L (j, j), which then leads to C W W 0 (j 1 , j) = C W W 0(j, j) and δ j1j = δ jj = 1 since there is no collisions. We thus have j 1 = j.G W ∼ 2 Ḡ. So after permuting Ḡ on V and W \{j}, one can obtain C V W L (i, j) = CV W L (i, j) for all i ∈ V and C W W L (j 1 , j) = CW W L (j 1 , j) for all j 1 ∈ W .Another observation is that such permutation does not change the optimal objective value of LP( Ḡ, j, lj , ûj ) as j is fixed.Next, we verify the four conditions in Theorem C.5 for two LP problems LP(G, j, lj , ûj ) and LP( Ḡ, j, lj , ûj ) with respect to the partitions I = {I 1 , I 2 , . . . , I s } and J = {J 1 , J 2 , . . . , J t }.Verification of Condition (a) in Theorem C.5 Since there is no collision in the 2-FWL test Algorithm 2,C V W L (i, j) = CV W L (i, j) implies that C V W 0 (i, j) = CV W 0 (i, j) and hence that v i = vi , which is also constant over all i ∈ I p since C V W L (i, j) is contant over all i ∈ I p by definition. Verification of Condition (b) in Theorem C.5 It follows from C W W L (j 1 , j) = CW W L (j 1 , j) that C W W 0 (j 1 , j) = CW W 0 (j 1 , j) and hence that w j1 = wj1 , which is also constant over all j 1 ∈ I q since C W W L (j 1 , j) is contant over all j 1 ∈ I q by definition.Verification of Condition (c) in Theorem C.5 Consider any p ∈ {1, 2, . . . , s} and any i ∈EQUATION)) : j 1 ∈ W , and hence that(C W W L (j 1 , j), A ij1 ) : j 1 ∈ W = ( CW W L (j 1 , j), Āij1 ) : j 1 ∈ W ,where we used the fact that there is no strict color refinement in the L-th iteration and there is no collision in Algorithm 2. We can thus conclude for any q ∈ {1, 2, . . . , t} that{{A ij1 : j 1 ∈ J q }} = {{ Āij1 : j 1 ∈ J q }}, which implies that j1∈Jq A ij1 = j1∈Jq Āij1 that is constant over i ∈ I p since C V W L (i, j) = CV W L (i, j) is constant over i ∈ I p .Verification of Condition (d) in Theorem C.5 Consider any q ∈ {1, 2, . . . , t} and anyj 1 ∈ J q . It follows from C W W L (j 1 , j) = CW W L (j 1 , j) that (C V W L-1 (i, j), C V W L-1 (i, j 1 )) : i ∈ V = ( CV W L-1 (i, j), CV W L-1 (i, j 1 )) : i ∈ V ,and hence that(C V W L (i, j), A ij1 ) : i ∈ V = ( CV W L (i, j), Āij1 ) : i ∈ V ,where we used the fact that there is no strict color refinement at the L-th iteration and there is no collision in Algorithm 2. We can thus conclude for any p ∈ {1, 2, . . . , s} that{{A ij1 : i ∈ I p }} = {{ Āij1 : i ∈ I p }}, which implies that i∈Ip A ij1 = i∈Ip Āij1 that is constant over j 1 ∈ J q since C W W L (j 1 , j) = CW W L (j 1 , j) is constant over j 1 ∈ J q .Combining all discussion above and noticing that J 1 = {j}, one can apply Theorem C.5 and conclude that the two LP problems LP(G, j, lj , ûj ) and LP( Ḡ, j, lj , ûj ) have the same optimal objective value, which completes the proof.Corollary C.6. For any G, Ḡ ∈ G m,n , if G W ∼ 2 Ḡ,then the LP relaxations of G and Ḡ have the same optimal objective value and the same optimal solution with the smallest ℓ 2 -norm (if feasible and bounded).Proof. If no collision, it follows from (C.4) that C W W L (j, j) = CW W L (j, j) which implies l j = lj and u j = ūj for any j ∈ W . Then we can apply Theorem C.4 to conclude that two LP problems LP(G, j, l j , u j ) and LP( Ḡ, j, lj , ūj ) that are LP relaxations of G and Ḡ have the same optimal objective value.In the case that the LP relaxations of G and Ḡ are both feasible and bounded, we use x and x to denote their optimal solutions with the smallest ℓ 2 -norm. For any j ∈ W , x and x are also the optimal solutions with the smallest ℓ 2 -norm for LP(G, j, l j , u j ) and LP( Ḡ, j, lj , ūj ) respectively. By Theorem C.5 and the same arguments as in the proof of Theorem C.4, we have the x j = xj . Note that we cannot infer x = x by considering a single j ∈ W because we apply permutation on V and W \{j} in the proof of Theorem C.4. But we have x j = xj for any j ∈ W which leads to x = x. 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 l and q l such that the conditions (d)-(f) are satisfied.Suppose that G W ∼ 2 Ḡ is not true. Then there exists L and hash functions such thatC V W L (i, j) : i ∈ V ̸ = CV W L (i, j) : i ∈ V , or C W W L (j 1 , j) : j 1 ∈ W ̸ = CW W L(j 1 , j) : j 1 ∈ W , 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 it holds for some j ∈ W thats L ij : i ∈ V ̸ = sL ij : i ∈ V , (C.8) or t L j1j : j 1 ∈ W ̸ = tL j1j : j 1 ∈ W .(C.9) In the rest of the proof we work with (C.8), and the argument can be easily modified in the case that (C.9) is true. It follows from (C.8) that there exists some continuous function φ such thati∈V φ(s L ij ) ̸ = i∈V φ(s L ij ).Then let us construct the (L + 1)-th layer yieldings L+1 ij = φ(s L ij ) and sL+1 ij = φ(s L ij ), and the output layer withr   i∈V s L+1 ij , j1∈W t L+1 j1j   = i∈V φ(s L ij ) ̸ = i∈V φ(s L ij ) = r   i∈V sL+1 ij , j1∈W tL+1 j1j   .This is to say F (G) j ̸ = F ( Ḡ) j for some F ∈ F 2-FGNN , which contradicts the assumtion that F has the same output on G and Ḡ. Thus we can conclude thatG W ∼ 2 Ḡ.Proof of Theorem C.7 (a). By Lemma C.8 and Lemma C.9.Proof of Theorem C.7 (b). Apply Theorem C.7 on G and the graph obtained from G by switching j 1 and j 2 .Proof of Theorem C.7 (c). Suppose that G ∼ 2 Ḡ. By Theorem C.2, there exists some permutationσ W ∈ S n such that G W ∼ 2 σ W * Ḡ. For any scalar function f with f 1 ∈ F 2-FGNN , by Theorem C.7, it holds that (f 1)(G) = (f 1)(σ W * Ḡ) = (f 1)( Ḡ), where we used the fact that f 1 is permutationequivariant. We can thus conclude that f (G) = f ( Ḡ). Now suppose that G ∼ 2 Ḡ is not true. Then there exist some L and hash functions such thatC V W L (i, j) : i ∈ V, j ∈ W ̸ = CV W L (i, j) : i ∈ V, j ∈ W , or C W W L (j 1 , j 2 ) : j 1 , j 2 ∈ W ̸ = CW W L (j 1 , j 2 ) : j 1 , j 2 ∈ W .By the proof of Lemma C.9, one can construct the l-th 2-FGNN layers inductively for 0 ≤ l ≤ L, such that the condition (a)-(f) in the proof of Lemma C.9 are true. Then we haves L ij : i ∈ V, j ∈ W ̸ = sL ij : i ∈ V, j ∈ W , (C.10) or t L j1j2 : j 1 , j 2 ∈ W ̸ = tL j1j2 : j 1 , j 2 ∈ W . (C.11)We first assume that (C.10) is true. Then there exists a continuous function φ with i∈V,j∈Wφ(s L ij ) ̸ = i∈V,j∈W φ(s L ij ).Let us construct the (L + 1)-th layer such thats L+1 ij = p L+1   s L ij , j1∈W f L+1 (t L j1j , s L ij1 )   = j1∈W φ(s L ij1 ), sL+1 ij = p L+1   sL ij , j1∈W f L+1 ( tL j1j , sL ij1 )   = j1∈W φ(s L ij1 ),and the output layer withr   i∈V s L+1 ij , j1∈W t L+1 j1j   = i∈V j1∈W φ(s L ij1 ) ̸ = i∈V j1∈W φ(s L ij1 ) = r   i∈V sL+1 ij , j1∈W tL+1 j1j   , which is independent of j ∈ W . This constructs F ∈ F 2-FGNN of the form F = f 1 with f (G) ̸ = f ( Ḡ).Next, we consider the case that (C.11) is true. Thent L j1j2 : j 1 ∈ W : j 2 ∈ W ̸ = tL j1j2 : j 1 ∈ W : j 2 ∈ W , (C.12)and hence there exists some continuous ψ such that      j1∈W ψ(t L j1j2 ) : j 2 ∈ W       ̸ =       j1∈W ψ( tL j1j2 ) : j 2 ∈ W       .Let us construct the (L + 1)-th layer such thats L+1 ij = p L+1   s L ij , j1∈W f L+1 (t L j1j , s L ij1 )   = j1∈W ψ(t L j1j ), sL+1 ij = p L+1   sL ij , j1∈W f L+1 ( tL j1j , sL ij1 )   = j1∈W ψ( tL j1j ),and we have from (C.12) thats L+1 ij : i ∈ V, j ∈ W ̸ = sL+1 ij : i ∈ V, j ∈ W .We can therefore repeat the argument for (C.10) and show the existence of f with f 1 ∈ F 2-FGNN and f (G) ̸ = f ( Ḡ). The proof is hence completed.C.4 Proof of Theorem 4.7We finalize the proof of Theorem 4.7 in this subsection. Combining Theorem C.3 and Theorem C.7, one can conclude that the separation power of F 2-FGNN is stronger than or equal to that of SB scores. Hence, we can apply the Stone-Weierstrass-type theorem to prove Theorem 4.7 Theorem C.10 (Generalized Stone-Weierstrass theorem [4] ). Let X be a compact topology space and let G be a finite group that acts continuously on X and R n . Define the collection of all equivariant continuous functions from X to R n as follows:C E (X, R n ) = {F ∈ C(X, R n ) : F (g * x) = g * F (x), ∀ x ∈ X, g ∈ G}.Consider any F ⊂ C E (X, R n ) and any Φ ∈ C E (X, R n ). Suppose the following conditions hold:(a) F is a subalgebra of C(X, R n ) and 1 ∈ F, where 1 is the constant function whose ouput is always (1, 1, . . . , 1) ∈ R n .(b) For any x, x ′ ∈ X, if f (x) = f (x ′ ) holds for any f ∈ C(X, R) with f 1 ∈ F, then for any F ∈ F, there exists g ∈ G such that F (x) = g * F (x ′ ).(c) For any x, x ′ ∈ X, if F (x) = F (x ′ ) holds for any F ∈ F, then Φ(x) = Φ(x ′ ).(d) For any x ∈ X, it holds that Φ(x) j1 = Φ(x) j2 , ∀ (j 1 , j 2 ) ∈ J(x), whereJ(x) = (j 1 , j 2 ) ∈ {1, 2, . . . , n} 2 : F (x) j1 = F (x) j2 , ∀ F ∈ F .Then for any ϵ > 0, there exists F ∈ F such thatsup x∈X ∥F (x) -Φ(x)∥ ≤ ϵ.Proof of Theorem 4.7. Lemma F.2 and Lemma F.3 in [11] prove that the function that maps LP instances to its optimal objective value/optimal solution with the smallest ℓ 2 -norm is Borel measurable. Thus, SB : G m,n ⊃ SB -1 (R n ) → R n is also Borel measurable, and is hence P-measurable due to Assumption 4.3. By Theorem A.4 and Assumption 4.3, there exists a compact subsetX 1 ⊂ SB -1 (R n ) such that P[G m,n \X 1 ] ≤ ϵ and SB| X1 is continuous. For any σ V ∈ S m and σ W ∈ S n , (σ V , σ W ) * X 1is also compact and SB| (σ V ,σ W ) * X1 is also continuous by the permutation-equivariance of SB. SetX 2 = σ V ∈Sm,σ W ∈Sn (σ V , σ W ) * X 1 .Then X 2 is permutation-invariant and compact withP[G m,n \X 2 ] ≤ P[G m,n \X 1 ] ≤ ϵ.In addition, SB| X2 is continuous by pasting lemma.The rest of the proof is to apply Theorem C. This section will explore some extensions of our theoretical results.The same analysis for Theorem 4.4 and Theorem 4.7 still works as long as the SB score is a function of f * LP (G, j, l j , ûj ), f * LP (G, j, lj , u j ), and f * LP (G):• We prove in Theorem A.3 that if two MILP-graphs are indistinguishable by the WL test, then they must be isomorphic and hence have identical SB scores (no matter how we define the SB scores). So Theorem 4.4 is still true.• We prove in Theorem C.4 that if two MILP-graphs are indistinguishable by 2-FWL test, then they have the same value of f * LP (G, j, l j , ûj ) (and f * LP (G, j, lj , u j )). Therefore, Theorem C.3 still holds if the SB score is a function of f * LP (G, j, l j , ûj ), f * LP (G, j, lj , u j ), and f * LP (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] .While Theorems 4.4 and 4.7 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 or distributions where m and n vary but remain bounded. Following Lemma 36 in [4] , if a universal-approximation theorem applies to G m,n for any fixed m and n (as shown in our work) and at least one GNN can distinguish graphs of different sizes, then the result holds across a disjoint union of finitely many G m,n .If the distribution has unbounded m or n, for any ϵ > 0, one can always remove a portion of the tail to ensure boundedness in m and n. In particular, there always exist large enough m 0 and n 0 such that P[m(G) ≤ m 0 ] ≥ 1 -ϵ and P[n(G) ≤ n 0 ] ≥ 1 -ϵ. The key point is that for any ϵ > 0, such m 0 and n 0 can always be found. Although these values may be large and dependent on ϵ, they are still finite. This allows us to apply the results for the bounded-support case.Note that the "tail removal" technique mentioned above comes from the fact that a probability distribution has a total mass of 1:1 = ∞ n=0 P(n(G) = n) = lim n0→∞ n0 n=0 P(n(G) = n) = lim n0→∞ P(n(G) ≤ n 0 )By the definition of a limit, this clearly implies that for any ϵ > 0, there exists a sufficiently large n 0 such that P[n(G) ≤ n 0 ] ≥ 1 -ϵ. A similar argument applies to m.Random MILP instances generation We generate 100 random MILP instances for the experiments in Section 5. We set m = 6 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: b i ∼ N (0, 1).• The coefficients of the objective function: c j ∼ N (0, 1).• The non-zero elements in the coefficient matrix: A ij ∼ N (0, 1). The coefficient matrix A contains 60 non-zero elements. The positions are sampled randomly. • The lower and upper bounds of variables: l j , u j ∼ N (0, 10 2 ). We swap their values if l j > u j after sampling.• The constraint types • are randomly sampled. Each type (≤, = or ≥) occurs with equal probability. • The variable types are randomly sampled. Each type (continuous or integer) occurs with equal probability.We implement MP-GNN and 2-FGNN with Python 3.6 and TensorFlow 1.15.0 [1] . Our implementation is built by extending the MP-GNN implementation of [19] in https://github.com/ds4dm/learn2branch. The SB scores of randomly generated MILP instances are collected using SCIP [6] .For both GNNs, p 0 , q 0 are parameterized as linear transformations followed by a non-linear activation function; {p l , q l , f l , g l } L l=1 are parameterized as 3-layer multi-layer perceptrons (MLPs) with respective learnable parameters; and the output mapping r is parameterized as a 2-layer MLP. All layers map their input to a 1024-dimensional vector and use the ReLU activation function. Under these settings, MP-GNN contains 43.0 millions of learnable parameters and 2-FGNN contains 35.7 millions of parameters.We adopt Adam [31] to optimize the learnable parameters during training with a 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.• 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to 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 to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe 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 be possible for other researchers to have some path to reproducing or verifying the results.Rigorously, the space Gm,n ∼ = R m×n ×R n ×R m ×(R∪{-∞}) n ×(R∪{+∞}) n ×{≤, =, ≥} m ×{0, 1} n is equipped with product topology, where all Euclidean spaces have standard Eudlidean topologies, discrete spaces {-∞}, {+∞}, {≤, =, ≥}, and {0, 1} have the discrete topologies, and all unions are disjoint unions.We require f l , g l yield 0 when the edge weight is 0 to avoid the discontinuity of functions in FMP-GNN.Here, "no collision of a 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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.

### Key Contributions:
1. 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.
2. 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.
3. 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.
strength_weakness: strength_weakness: 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.

2. 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.
questions: questions: The paper is generally well-written. Besides the issues in the section of ``Weakness", I don't have further questions so far.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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?
questions: questions: - what would the behavior in Figure 3b change if the number of parameters were varied?
limitations: limitations: The limitations have been sufficiently addressed in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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
questions: 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?

[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: limitations: The authors have discussed the limitations of the work. The large-scale experiments are still a problem in existing studies.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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).

- Some major statements are imprecise mathematically: Theorem 4.4. In which space does $G$ belong to: $G^{\text{MP}}$ or $G$?

- 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).

	Some examples:

	-  in Theorem A.3, the statement starts with $G \sim \bar{G}$, and a) states ``If $G \sim \bar{G}$ then [...]'' 
	-  in The statement of Theorem A.5, where you introduce $(\sigma_V, \sigma_W) * G$ without explaining the notation beforehand.  
	-  Lemma C.8, one can group several substatements to simplify the presentation. 
	
More 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.
questions: 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.

- 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: limitations: The authors address in a few sentences the limitations and follow-up of their work in the conclusion.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. My second concern comes from the numerical results.

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

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

- 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.
questions: 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.

2. 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.. 

3. 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: limitations: See above for the limitations of this paper.

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

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

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

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

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

**Symmetry of MILPs in practice**: My original meaning is "MP-intractable case is rare", not "symmetric case is rare". As long as the MILP is MP-tractable, GNN can handle no matter how much symmetry (in terms of the number of different colors output by the WL-test) exists.

**Training efficiency**: I appreciate the authors' effort in the additional experiments. I agree that more advanced training techniques or new network architecture in the future can resolve this problem.
Dear Reviewer xf7T,

Thank you very much for increasing the score! We appreciate all your valuable comments and will modify the presentation and proof flows accordingly in our revision.
Thanks for the detailed answers. I am satisfied with the authors' answers and raise my score to 5. 
I am convinced that the core of the results are interesting. However, a significant improvement the presentation of the contributions (including mentioning limitations as explained in Q1 above), and the proofs (including some more developments to present their essence), could have improved my overall score further. Given the fact that this would be substantial modifications, I decided to raise to 5.
My only concern was on practical impact/generalizability of result, and it has been adequately addressed in the rebuttal. I have no further comment.
Thanks for your additional questions! Here are our answers:

**Reply to Q1.** We completely agree with you that our main results focus on the existence of GNNs representing the SB score, and we have not yet established the complexity of such GNNs. In our revision, we will clearly comment that verifying MP-tractability is polynomial in complexity, but the size and running time of GNNs currently have no theoretical guarantees.

However, we would like to kindly emphasize that this does not hurt our main contribution. The main purpose of this paper is to address a theoretical question: **whether GNNs can or cannot universally represent the SB score** for all MILPs, especially given the numerous empirical studies on this topic. We clearly answer this question with Theorem 4.4, Corollary 4.6, and Theorem 4.7—when an MILP exhibits strong symmetry (such as in equations (4.1) and (4.2)), MP-GNNs are not suitable, and other GNN structures need to be explored. This conclusion is inherent, regardless of how large MP-GNNs might be, and we believe it provides useful insights to the learning-to-branch community.

As for the complexity of these GNNs (whether polynomial or exponential), this relates to a different question: **how well GNNs can represent the SB score.** We believe this is an interesting direction for future research.

To further address the reviewer's concern, we will include the following in our revision:

> At the end of Section 4.3, we will add: While verifying MP-tractability is polynomial in complexity, this does not imply that calculating the SB score is polynomial, as the complexity of GNNs is not guaranteed. Our Theorems 4.4 and 4.7 address existence, not complexity. In other words, this paper answers the question of whether GNNs can represent the SB score. To explore how well GNNs can represent SB, further investigation is needed.

We chose to include the comment at the end of Section 4.3 because it involves concepts like MP-tractability and Theorems 4.4 and 4.7. Positioning the comment after these concepts and theorems are introduced ensures a smoother flow for the readers.


**Reply to Q2.** Yes, the results hold for any Borel regular probability distribution. We would like to provide more details on how to extend our results to a data distribution with varying sizes $m,n$. 
    
According to Lemma 36 in (Azizian and Lelarge, 2021), if one can obtain a universal-approximation-type theorem on $G_{m,n}$ for any **fixed** $m$ and $n$ (as we addressed in our manuscript), and if graphs with different sizes can be distinguished by at least one GNN (this is straightforward), then the result can be extended directly to the disjoint union of **finitely many** $G_{m,n}$. This addresses the case of "bounded-support distributions (in $m$ and $n$)" mentioned by you. 
    
If the distribution is not bounded-support in $m$ and $n$, for any $\epsilon>0$, one can always remove a portion of the tail to ensure boundedness in $m$ and $n$. That is what we mentioned in the rebuttal: there always exist large enough $m_0$ and $n_0$ such that $\mathbb{P}[m(G)\leq m_0]\geq 1-\epsilon$ and $\mathbb{P}[n(G)\leq n_0]\geq 1-\epsilon$. The key point is that for any $\epsilon>0$, such $m_0$ and $n_0$ can always be found. Although these values may be large and dependent on $\epsilon$, they are still finite. This allows us to apply the results for the bounded-support case.

Note that the "tail removal" technique mentioned above comes from the fact that a probability distribution has a total mass of 1:
$$1 = \sum_{n=0}^{\infty}\mathbb{P}(n(G) = n) = \lim_{n_0 \to \infty} \sum_{n=0}^{n_0}\mathbb{P}(n(G) = n) = \lim_{n_0 \to \infty} \mathbb{P}(n(G)\leq n_0)$$
By the definition of a limit, this clearly implies that for any $\epsilon> 0$, there exists a sufficiently large $n_0$ such that $\mathbb{P}[n(G)\leq n_0]\geq 1-\epsilon$. A similar argument applies to $m$.

Please let us know if you have further comments or questions!

**(References).** (Azizian and Lelarge, 2021) Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021.
Thank you for your detailed answers. I would like to follow up with additional question(s) to the authors about the main theoretical contribution. 

Q1: Verifying MP-tractability can indeed be performed in polynomial time with respect to the dataset's size (and other constants / parameters). So given a set of instances, one can verify in a reasonable time if they are MP-tractable. However, in the statement of Theorem 4.4, the GNN's size potentially depends on the level of error and probability. The size of the GNN to insure one has low error and high probability may be exponential (w.r.t to $\epsilon$ and $\delta$). Also, the $\epsilon$ and $\delta$ have to grow with the size of the instances to make sure one is close enough to the true branching score. Therefore, the poly-time MP-tractable testing advertised by the authors could be overtaken by the GNN's size in this case (let alone the complexity to actually find or train this GNN). Can the authors comment on this?
In that regard, a clear presentation of the nature of the result in the contributions section (or elsewhere in the article), which is (as far as I understood), existential and not constructive, could be helpful.  

Q2: Do you mean that the statement would hold for any distribution (say with total weight 1)? 
Would it help to consider bounded-support distributions (in m and n), if this allows to remove technical difficulties? (and is probably relevant to most applications).
Thanks for your response. I have no more questions.
Many thanks for your rebuttal. My concerns are all sufficiently addressed.