ROCO: A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs
Authors: Han Lu
Zenan Li
Runzhong Wang
Qibing Ren
Xijun Li
Mingxuan Yuan
Jia Zeng
Xiaokang Yang
Junchi Yan
Venue: ICLR 2023 poster (2023)
Keywords: Combinatorial Optimization
Robustness
Graph Neural Networks
Reinforcement Learning

Abstract: Solving combinatorial optimization (CO) on graphs has been attracting increasing interests from the machine learning community whereby data-driven approaches were recently devised to go beyond traditional manually-designated algorithms. In this paper, we study the robustness of a combinatorial solver as a blackbox regardless it is classic or learning-based though the latter can often be more interesting to the ML community. Specifically, we develop a practically feasible robustness metric for general CO solvers. A no-worse optimal cost guarantee is developed as such the optimal solutions are not required to achieve for solvers, and we tackle the non-differentiable challenge in input instance disturbance by resorting to black-box adversarial attack methods. Extensive experiments are conducted on 14 unique combinations of solvers and CO problems, and we demonstrate that the performance of state-of-the-art solvers like Gurobi can degenerate by over 20% under the given time limit bound on the hard instances discovered by our robustness metric, raising concerns about the robustness of combinatorial optimization solvers.

Published as a conference paper at ICLR 2023
ROCO: A GENERAL FRAMEWORK FOR EVALUAT- ING ROBUSTNESS OF COMBINATORIAL OPTIMIZATION SOLVERS ON GRAPHS
Han Lu Zenan Li Runzhong Wang', Qibing Ren', Xijun Li,, Mingxuan Yuan", Jia Zeng?, Xiaokang Yang', Junchi Yan
"MoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University "Huawei Noah's ' Ark Lab dajtu_luhan, emi mamyyli,, runzheng. wang, renqibing. xkyang, yanjunchi @ @s .dd.co (xi jun. yuan. mingxuan, zeng. jia wwwwwei.ww..occmm
Code:
com com/ wtw.:/Tiikaaaaatt////OOO.
ABSTRACT
Solving combinatorial optimization (CO) on graphs has been attracting increasing interests from the machine learning community whereby data-driven approaches were recently devised to go beyond traditional masially-designated algorithms. In this paper, we study the robustness of combinatorial solver as a blackbox regard- less it is classic or bearning-based though the latter can often be more interesting to the ML community. Specifically, we develop a practically feasible robustness metric for general CO solvers. A no-worse optimal cost guarantee is developed as such the optimal solutions are not required to achieve for solvers, and we tackle the -in-differenttable challenge in input instance disturbance by resorting to black-box adversarial attack methods. Extensive experiments are conducted on 14 unique combinations of solvers and CO problems, and demonstrate that the perfor- mance of state-of-the-at art solvers like Gurobi can degenerate by over 20% under the given time limit bound on the hard instances discovered by our robustness metric, raising concerns about the robustness of combinatorial optimization solvers.
INTRODUCTION
The combinatorial optimization (CO) problems on graphs are widely studied due to their important applications including aligning cross-modality labels (Lyu et al. 2020), discovering vital seed users in social networks (Zhu et al. 2019), tackling graph matching problems (Wang et al. 2020 2022) and scheduling jobs in data centers (Mao et al. 2019). etc. However, CO problems are non-trivial to solve due to the NP-hard challenge, whereby the optimal solution can be nearly infeasible to achieve for even medium-sized problems. Existing approaches to practically tackle CO include heuristic methods (Van Laarhoven & Aarts 1987 [Whitey|] 1994), powerful branch-and-boun solvers (Gurobi
| Optimization] 2020 The SCIP Optimization Suite 8.0, [021 Forrest al., (002) and recently
developed learning- based models (Khalil et al. [217]] Yu et al. 2020: Kwon et al. 2021
Despite the success of solvers in various combinatorial tasks, little attention has been paid to the vulnerability and robustness of combinatorial solvers. As pointed out by Yehuda et al. (0220.. we cannot teach a perfect solver to predict satisfying results for all input CO problems. Within the scope of the solvers and problems studied in this paper, our results shows that the performance of solver may degenerate lot given certain data distributions that should lead to the same or better solutions compared to the original distribution assuming the solver works robustly. We also validate in experiments that such a performance degradation neither caused by the inherent discrete nature of CO. Such discovery raises our concerns about the robustness (i.c. the capability to perform stably w.r.t. perturbations on problem instances) of combinatorial solvers, which is also aware by Varma & Yoshida (022): Geisler et al. (202T). However, Varma & Yoshidal (2021) focuses theoretical analysis and requires the optimal solution, which is infeasible to reach in practice. Geisler et al. 1202
"Han Lu and Zenan Li contribute equally. Junchi Yan is the correspondence author who is also with Shanghai AI Laboratory. The work was in part supported by National Key Research and Development Program of China (2020AA00107600), NSFC (62222607, 72192821) and STCSM (22511 105 022511105000 100).

---

Published as a conference paper at ICLR 2023
Table 1: We make a (no strict) analogy by comparing the proposed ROCO framework with two popular attacking paradigms FGSM (Goodfellow et al. 2015) and RL-S2V (Dai et al. 2018). perturb means the change of one pixel should be bounded in c. B B-hop neighbourhood means the new attack edges can only connect two nodes with distance less than B.
Method
Data
Task
Attack target
Attack budget
Attack principle
FGSM
image
classification classification
pixels
e-Perturb
invisible change
RL-S2V
graph
edges (connectivity)
# edge
B-hop neighbour
ROCO (ours)
CO instance
solving CO
edges (constraints/cost)
# edge
no worse optimum
applies the andeeee-edeeee study in deep learning into learning- based combinatorial optimization models, requiring a differentiable neural network that is infeasible for general solvers that can often be undifferentiable. Our paper also differs from the namely "robust optimization" (Buchheim & Kurtz 2018), where the expected objective score is optimized given known data distribution. We summarize the challenges and our initiatives of evaluating the robustness of existing solvers as follows:
1) Robustness metric without optimal solutions:
The underlying NP-hard challenge of combinato- rial optimization prohibits us from obtaining the optimal solutions. However, the robustness metric proposed by Varma & Yoshida (2021) requires optimal solutions, making this metric infeasible in practice. In this paper, we propose a problem modification based robustness evaluation method, whereby the solvers' performances are evaluated on problems that can guarantee worse optimal costs. That is, the optimal solution of the modified problem instance gives better objective value than the original problem, which resolves the needs of the optimal solution.
2) Robustness metric of general (non-differentiable) solvers: Despite the recently developed deep-learning solvers, most existing solvers are non-differentiable due to the discrete combinatorial nature. Thus, the gradient-based robustness metric by Geisler et al. (202T) has the limitation to generalize to general solvers. In this paper, we develop a reinforcement learning (RL) based attacker that modifies the CO problems to get hard problem instances (where the solvers perform poorly) with no worse optimal costs. Regarding arbitrary types of solvers as black-boxes, the RL agent is trained by policy gradient without requiring the solver to be differentiable. Our framework also owns the flexibility where the agent can be replaced by other search schemes e.g. simulated annealing.
Being aware that many CO problems can be essentially formulated as graph problem and there are well-developed graph-based learning models (Scarselli et al. 2008; Kipf & Welling 2016 Velickovic et al. 2017), the scope of this paper is restricted within combinatorial problems graphs following (Khalil et al. 2017: Wang et al. 2021). To develop a problem modification method that achieves worse optimal costs, propose to modify the graph structure with problem-dependeen dependent strategy exploiting the underlying problem natures. Two strategies are developed concerning the studied four combinatorial problems: 1) loosening the constraints such that the feasible space be enlarged while the original optimal solution is preserved; 2) lowering the cost of a partial problem such that the objective value of the original optimal solution can become better. Such strategies are feasible when certain modifications are performed on the edges, and tackle the challenge that we have no access to the optimal solutions. The generated data distributions can also be close to the original data by restricting the number of edges modified. The graph modification steps are performed by our proposed attackers that generate problem instances where the solvers' performances degenerate, and we ensure the no worse optimal costs guarantee by restricting the action space of the attackers.
Our framework can be seen as the attack on the solvers and how much the worst cases near the clean instances will do harm to the solver are considered as the robustness. Tbl. [ compares our framework to classical works on adversarial attacks for images/graphs. The highlights of this paper are:
1) We propose Robust Combnaotorial Optimization (ROCO), a general framework (see Fig. to empirically evaluate the robustness of CO solvers on graphs. It is performed without requiring optimal value or differentiable property.
2) We design a novel robustness evaluation method with no worse optimal costs guarantee to eliminate the urgent requirements for the optimal solution of CO problems. Specifically, we develop a reinforcement learning (RL) based attacker combined with other search-based attackers to regard the solvers black- even they are nonddifferentiable solvers
3) Comprchensive case studies are conducted on four common combinatorial tasks: Directed Acyclic Graph Scheduling, Asymmetric Traveling Salesman Problem, Maximum Coverage, and Maximum
2

---

Published as a conference paper at ICLR 2023
Coverage with Separate Coverage Constraint, with three kinds of solvers: traditional solvers, learning- based solver and specific MILP solver like Gurobi.
The results presented in this paper may raise the community's ' attention to the robustness, c.g. big performance drop for the commercial solver Gurobi though it is not a big surprise given the NP-hard nature of many CO problems. It can also be connected to data augmentation for tarning-based CO solvers or other methods like parameter tuning to improve solvers' robustness (see Appendix for more results and discussions). We leave more advanced defense strategies for future work which is still an open problem (Yehuda el al. 2020).
Remark. Note we somewhat 'abuse' the term 'attack' which in fact originates from the area of adversarial attack/defense e.g. [Goodfellow et al.) (2015). Here we use it to express the concept of hard case mining on 'clean' (i.e. raw) instances. In fact, we try to make an analogy between the attacks for image data and our case while we are also aware there are fundamental differences. To ease readers' potential confusion and make the presentation more precise, we will give the formal definition of attack in our context for CO solvers' robustness evaluation in Def. ii Sec. 2.1
The related work is deferred to Appendix A which mainly refers to the solvers for combinatorial optimization on graphs including traditional and recent learning- based solvers, as well as adversarial attack and defense especially for graph learning.
2 THE ROCO FRAMEWORK
2.1 ADVERSARIAL ROBUSTNESS FOR CO
Formulation. In general, a CO problem aims find the optimal solution under a set of constraints (usually encoded by a latent graph). Here we formulate a CO problem Q as:
min c(x, Q) s.t. 1x Q) < 00, i I,...!
where x denotes the decision variable (i.e. solution) that should be discrete, c(x, Q) denotes the cost function given problem instance Q and (h, Q)}== represents the set of constraints. For example, in DAG scheduling, the constraints ensure that the solution x, i.e. the execution order of the DAG job nodes, lies in the feasible space and does not conflict the topological dependency structure of Q. However, due to the NP-hard nature, the optimal solution x" can be intractable within polynomial time. Therefore, we use solver x (Q), which gives mapping ʃa Q + X to approximate the optimal solution x". In this work, are solvers' parameters (e.g. weights and biases in a neural solver, hyperparameters in Gurobi), solution. x also lies in the feasible space that satisfies all the constraints.
Q is the problem instance, and & E X is the approximated
Solvers' robustness. In this paper, we would like raise the concern that the estimation capability of the solvers can be unstable and fail on certain hard instances. Thus, we need methods to discover the non-trivial hard instances for the solvers the robustness metric where a more robust solver can perform better on hard instances. Here non-trivial means these hard instances are not obtained by trivial operations like increasing the size of problems. In short, given certain solver fe. we design an attacker (i.e. perturbation model) g to modify the existing clean instances Q = ff.. Q) and discover hard instances around. For example, the attacker can modify a limited number of constraints in Q to get new problem Q. Besides working as robustness metric, the discovered hard instances can guide the parameter setting of solvers, i.e. design solvers' parameters for better performance (robustness) on hard instances, which is beyond the scope of this paper and we mainly focus on developing the first practically feasible robustness metric. Some preliminary results on hard case utilization are presented in Appendix
Robustness metric. A natural evaluation of the solvers' robustness is to use the gap c(x, Q)-c(x", Q) (Varma & Yoshida (02I), where narrower gap stands for better performance. However, the optimum x" usually unavailable due to the NP-hardness. In this paper, we propose a robustness evaluation method without requiring the optimal solution, and the attack is defined by:
Definition (Successful Attack). Given a solver fe and clean CO problem instance Q. obtain new problem Q = g(fo, Q) by the attacker g s.s. the optimal cost value after perturbation will become no-worse, i.e. c(x², Q) I c(x", , Q), where X denotes the new optimal solution. A successful atlack occurs when el fo (Q), ) Q) > c(fo(Q),Q).
3

---

Published as a conference paper at ICLR 2023
Original graph
Attacked graph Optimal
Optimal
Constraint:
c(8 .
<(x'.0) c(R',
Attackerr:
Clean instance
Attacked instance Salved <(fa()))
Ri/Search
Salved <cfx())).)) Q) Successful Artack:
clfr1).0) <ff.(0).))
Iterate actionn
Olack-box
Black-box
Solver
Salver
Attacker's Constraint: <ox" @) o(F" .Q)
(0)+0) (((0)0
Reward:
Optimal cost c(x..Q)
Optimal cost o(R" QQ)
Objective <0v(02).0
Attacked Objective (l/(0)))))
ROCO framework
(b) Successful attack
Figure I: Overview and intuition of our attack framework. Left: Overview of our attack framework
ROCO for CO solvers. ROCO targets on the CO problems which can be encoded by graphs (often
holds in practice). Here modifying the edges in the encoded graph represents modifying constraints or lowering the cost in CO. Right: The definition of a successful attack.
The intuition is that restrict the attacker to discover new problem instance with no- no-worse optimal cost value, such that the gap between the solver and the optimal will be definitely enlarged the solver gives worse cost value:
c) S c(x", Q), c(fo( () ((fo(Q)) Q) c(fo(9). c(x", Q) < clfo Q) c(x' QQ)
which represents successful attack (see Fig. 1(b).
Attacker's target. In conclusion, the attacker should maximize the solver's cost value after perturba- tion while conforming to the no-worse restriction. Therefore, we formulate our attack objective:
max c(Jo( - c(Je(Q),
s.t. Q g(fo Q), c(x², Q) S c(x",Q) QQ)
As consensus in the filed of robustness, the robustness definition should be against the attacker's objective (Carlini al. 2019 Chen al. 2022a). Now with the attack objective, we can successively
define solvers' robustness quantitatively:
Definition 2 (Solvers' Robustness). Given a certain solver fo a test dataset 'D consisted of CO problems, its robustness r is defined as the inverse of the expected worst case cost value after attacked by the attacker g under the no worse optimal cost constraint:
=-BquD B- [mnxx (o()) Q11
Q
(4)
8.1. Q = - Q), cxx Q) S c(xx, Q)
We add the negative sign in Eq. so that a higher value denotes better robustness.
Attacker's constraints. Two types of strategies are developed to meet the no worse optimal cost constraint for the attackers: 1) Loosening the constraints of the problem. In this way, the original optimal solution still lies in the feasible space and its cost is not affected, while the enlarged feasible space may include better solutions. Therefore. the new optimal cost cannot be worse than the original one, and we discover this strategy effective for DAG scheduling (see Section 3.J. 2) Modifying partial problem by lowering the costs. Such a strategy ensures that the cost that corresponds the original optimal solution can never become worse, and there are also chances to introduce solutions with lower costs. We demonstrate its successful application in traveling salesman (see Section 3.2 and max coverage problems (see Section 3.3 & Appendix C).
Attack via graph modification. As mentioned above, a CO problem Q can usually be encoded by latent graph g (V, E). For example, the DAG problem can be represented by a directed acyclic graph (see Fig. 4). s.t. the graph nodes stand for the DAG jobs, the directed edges denote the sequential constraints for the jobs, and the node features represent the jobs' completion time. Hence, the perturbation to the problem instance can be conducted by modifications to the graph structure (Dai et al., 2018). Besides, to get non-trivial hard instances around clean examples, the attack is limited within a given attack budget K, e.g. the attacker can remove < K edges in a DAG problem Q. Typically, in our setting, the graph modification is all conducted by modifying edges.
4

---

Published as a conference paper at ICLR 2023
2.2 IMPLEMENTATIONS OF THE ATTACKER
Random attack baseline. The baseline simply chooses and modifies K random edges sequentially, then calculates the new cost. We compare other attackers (which achieve much higher attack effects) to the random attack baseline to claim that our framework can uncover far more hard instances than the inherent instability caused by the CO problems.
Reinforcement learning attacker (ROCO-RL). We use Eq. B as the objective and resort reinforce- ment learning (RL) to find Q in data-driven manner. Specifically, we modify the graph structure and compute el c(fo(Q), (Q), Q) alternatively, getting rewards that will be fed into the PPO (Schulman et al. 2017) framework and train the agent.
Given instance (fo, Q) along with modification budget K, we model the attack via sequential edge modification as Markov Decision Process (MDP):
State. The current problem instance Q' (i.c. the problem instance Q obtained after ht actions) is treated the state. The original problem instance Q Q is the starting state.
Action. The attacker is allowed to modify edges in the graph. So a single action at time step k is a E A C E* Here our action space A is usually a subset of all the edges E since we can narrow the action space (i.e. abandon some useless edge candidates) according to the previous solution fa(Q*) speed up our algorithm. Furthermore, decompose the action space (O([V)3) + O((Vl)) by transforming the edge selection into two sequential node selections: first selecting the start node, then the end node.
Reward. The objective of the new CO problem Qk+11 is c(fo(Qh+))) Q++1)) To maximize the new cost value, we define the reward as the increase of the objective:
r = c(fo(Q)+)),
(5)
Terminal. Once the agent modifies K edges or edge candidates become empty, the process stops.
The input and constraints of a CO problem can often be encoded in graph G = (V, E), and the PPO agent (i.e. the actor and the critic) should behave according to the graph features. We resort to the Graph Neural Networks (GNNs) for graph embedding:
GNN(G"), ) g = AutPool(n)
where G is the corresponding graph of problem Q* the matrix n (with the size of node number x embedding dim) is the node embedding. An attention pooling is used to extract a graph level embedding g. The GNN model can differ by the CO problems (details in Appendix(D) After graph feature extraction, we design the actor and critic nets:
Critic. It predicts the value of each state Q*, Since aims at reward maximization, a max-pooling layer is adopted over all node features which are concatenated (denoted by [-Il-]) with the graph embedding g. fed into a network (e.g. ResNet block (He et al. 2016)) for value prediction:
V(Q")) ResNet, (MaxPool(n))
Actor: The edge selection is implemented by selecting the start and end node sequentially. The action scores are computed using two independent ResNet blocks, and a Softmax layer is added to regularize the scores into probability [o, 1):
P(a1) = Softmax(ResNetyy ((nl)l()(()))))))
(8)
P(azla1) Softmax(ResNerl
where n [[1] denotes node a1 's embedding. We add the feature vector of the selected start node for the end node selection. For training, actions sampled by their probabilities. For testing, beam search is used to find the optimal solution: actions with top-B probabilities are chosen for each graph in the last time step. Only those actions with top-B 3 rewards will be reserved for the next search step (see Alg. T].
Other attacker implementations. We also implement three traditional attack algorithms for compar- ison: random search, optimum-guider search and simulated annealing.
i) Random Search (RCOO-RA) In each iteration, an edge is randomly chosen to be modified in the graph and it will be repeated for K iterations. Different from the random attack baseline without any
5

---

Published as a conference paper at ICLR 2023
search process, will run N attack trials and choose the best solution. Despite its simplicity, it can reflect the robustness of solvers with the cost of time complexity O(NK).
ti) Optinan--Gaided Search (ROCO-OG): This method focuses on finding the optimum solution during each iteration. We use beam search to maintain the best B current states and randomly sample M different actions from the candidates generate next states. The number of iterations is set to be no more than K. The time complexity is O(BMK).
fii) Simulated Annealing (ROCO-SA): Sim- ulated annealing (Van Laarhoven & Aarts 1987) comes from the idea of annealing and cooling used in physics for particle crystal- lization. In our scenario, a higher tempera- ture indicates higher probability of accept- ing worse solution, allowing to jump out of the local optimum. As the action num- ber increases, the temperature decreased, and we tend to reject bad solutions. The detailed process is shown in Appendix [ repeat it for N times. SA is fine-tuned al- gorithm and we can use grid search to find the best parameter to fit the training set. Its time complexity is (K..
Algorithm 1: ROCO: Attack via iterative edge manipulation on the input graph Input: Input prohlem Q: solver fo; max number of actions K; heam size B.
L.. f- Q: Q < Q; set initial state
for k 4- 1..K do
for b <- 1..B do
# do beam search for problems in last step
Predict P(ar). P(aala1) on Q
Select (a1, au) with top- B probabilities;
and we will
for each (6, a1, pair pair do
('(b,a1,00 f- modify edge (21,02) in O
if cl (1b, > c(fo, Q*) then Q + Q'bb, a1, 02)
# update the best attacked problem
Tbl. 7 in Appendix || concludes the attack- ers' property and complexity. Since the three traditional algorithms are inherently stochas- tic, we run them multiple times. The trained RL attacker behaves deterministicly and we choose the best trained model.
Sort ('(...)) w.r.t. cost values by decreasing order;
Q + Di # select top- B for next step
Output: Best attacked problem instance Q.
3 STUDIED CO TASKS AND RESULTS
We conduct experiments on four representative CO tasks: Directed Acyclic Graph Scheduling, Asym- metric Traveling Salesman Problem, Maximum Coverage and Maximum Coverage with Separate Coverage Constraint. Considering the page limitation, the details of the last task is postponed to Appendix C We also test the robustness of representative solvers including heuristics (Helsgaun)
2017 Grandl et al. 2014), branch-an -id----n---ddddddd solvers (Forrest et al., [022] The SCIP Optimization Grand
Suite 8.0| Gurobi Optimization 2020) and learning- based methods (Kwon et al. 2021). The detailed graph embedding methods for the four tasks is shown in Appendix [ In Appendix I we provide training and evaluation hyperparameters of different solvers for fair time comparison and reproducibility. Experiments are run on our heterogeneous cluster with RTX 2080Ti and RTX 3090.
Metrics. The quantitative robustness has been defined in Def.] 2 and here propose more intuitive metric of robustness in terms of ratios, which is also against the attacker's s objective. Typically, we just adopt the relative change rate between the cost value after attacked and the cost of the incumbent optimal solution, i.c. the best solution we can find, so that the ratio is proportional to the attacker's s objective. In the result tables, we report the raw cost value of different solvers under different attacks. Besides, we also report the robustness ratio for ROCO-RI, which is the best attacker in most cases.
3.1 TASK I: DIRECTED ACYCLIC GRAPH SCHEDULING
Many task scheduling systems formulate the job stages and their dependencies as a Directed Acyelic Graph (DAG) (Saha et al.) 2013 Chambers et al. 2010), shown in Fig. 4 The data center has limited computing resources to allocate the jobs with different resource requirements. These jobs can run in parallel if all their parent jobs have finished and the required resources are available. Our goal is to minimize the makespan (i.e. finish all jobs as fast as possible.)
We choose three popular heuristic solvers our attack targets. First, the Shortest Job First algorithm chooses the jobs greedily with minimum completion time. Second, the Critical Path algorithm finds the bottlenecks and finishes the jobs in the critical path sequence. Third, the Tetris
Solvers.

---

Published as a conference paper at ICLR 2023
Table 2: Evaluation on DAG scheduling. Clean makespans are results on the clean test set. Stronger attackers result in larger attacked makespans. Random denotes the random attack baseline with the mean and std tested for 100 trials. ROCO-RAVGG/A are tested for 10 trials to calculate the mean and std. ROCO-RL is reported with a single value since it is invariant to random seeds. The ratio in red is the robustness raio defined in metrics. A lower ratio denotes a more robust solver.
Clean Makespan
Attack Method (Attacked Makespans (x100))
Solver
#job
(x10*) )
Random
ROCO-RA
ROCO-0G
ROCO-SA
ROCO-RL
Shortesz Job First
1,461
1,0406
0.0035
1.074 0.0013
1,0000 4: 0.0019
1,0622
0.0007
10808
28. 28.94%
Critical Pach
0.5695
0.0077
0.902 0.0038
0.9480
0.0021
0.0013
0.9500 (r 15.47%)
Terrs
50
0.8227
0,8582
0.0079
0.8022
0.004g
0,9218
+ 0.0066
0.9380
0.1153
0.9397 (r 14.22%
Shortest Job First
100
1.9660
1.8532 0.0075
1-9210
0.0006
1,9239 1: 0.0008
1.9239
0.0008
1.926 (r 26. 36.85%)
Critical Parh
1.6018
0.0167
1.7301
1.7456 + 0.0043
0.0000
1.7498 (r 15. 15.22%)
Terris
100
1.5186
1.5830 + 0.0196
1.7201 = 0.0055
1,7000 + 0.0111
1.7418
0.0074
1.7526 (r 15.41%%
Shortest Job First
150
2,8578
2.8281 0.0074
2,8818
0.0020
2,8898 1: 0.0023
2.8850
0.0014
2.8964 (r 28. 91%)
Critical Parh
2,4398
8.0200
2,5698
0.0033
2,5028
0.0090
2.6020
0.0029
2.6069 (r 16.02%)
Teuris
150
2,2469
2,3581 +: 0.02700
2-4988 = 0.0191
2,5059 +: 0.0202
2.5399
0.0058
2.5329 (r 12.739)
2014) scheduling algorithm models the jobs 2-dimension blocks in the Tetris games according to their finishing time and resource requirement.
(randl et al.
Attack model. The edges in a DAG represent job dependencies. and removing edges will relax the constraints. After removing existing edges in a DAG, it is obvious that the new solution will be equal to or better than the original with fewer restrictions. Therefore, the attack model selectively removes existing edges.
Attack Budgst
Adack Sucget K
Figure 2: Left: RL Attack results w.r.t. attack bud- gets K on TPC-H-50 dataset for solvers Shortest Job First(SJF), Critical Path(CP) and Tetris(TS). Attack ratio is the ratio of the increased makespan after the attack to the clean makespan. Right: RL Attack results w.r.f. attack budgets K on TPC-H- 50/100/150 150 datasets for the Tetris (TS) solver.
Dataset. We use TPC-H datase composed of business-oriented queries and concurrent data modification. Many DAGs referring to compu- tation jobs, have tens or hundreds of stages with different duration and numbers of parallel tasks. We gather the DAGs randomly and generate three different sizes of datasets, TPC-H-50, TPC-H-100, TPC-H-150, each with 50 training and 10 testing samples. The DAG nodes have two properties: execution time and resource requirement.
Results and analysis. Tbl. 2 reports the results of our four attack methods. In the designed attack methods, RL outperforms other learning- free methods in most cases, illustrating the correctness of our feature extraction techniques and training framework. It is worth noting that even the simplest random search (ROCO-RA) can cause significant performance degradation to the CO solvers, showing their vulnerability and the effectiveness of the attack framework. Besides, all four attack methods perform better than the random attack baseline, which usually leads to shorter makespan than the clean instances (unsuccessful attack), proving that our attack framework can find more hard instances than those because of the inherent instability of CO problems. Fig. 2 (left) shows the attack ratio for different solvers on TPC-H-50. In general, the attack ratio increases then flattens out w.r.t. attack budgets, corresponding with the fact that we can find more hard instances under a larger searching space (but harder to find new successfully attacked instances as we remove more constraints). Fig. (right) demonstrates the effect of attack budgets different sizes of datasets using the solver Tetris The figure illustrates that attack ratios on smaller datasets tend to flatten first (larger datasets allow for more attack actions), which can guide to select the right number of attack actions for different datasets. We also conduct experiments to verify the generalizability of ROCO-RL in Appendix L, which shows that our attacker can be trained efficiently on small problem instances, then be directly used on larger problems.
3.2 TASK II: ASYMMETRIC TRAVELING SALESMAN
The classic traveling salesman problem (TSP) is to find the shortest cycle to travel across all the cities. Here we tackle the extended version asymmetric TSP (ATSP) for generality.
Solvers. The robustness of four algorithms are evaluated: First, Nearest Neighbour greedily adds the nearest city to the tour. Second, Furthest Insertion finds the city with the furthest distance to existing cities in the tour and inserts it. Third, Lin-Kemighhan Heuristic (LKH3) (Helsgaun) 2017) is
http: http:://ppe..rrg/pphhh/eeea
7

---

Published as a conference paper at ICLR 2023
Table 3: Evaluation of solvers for ATSP. Stronger attacker result in larger attacked tour lengths. MatNet (fixed) represents training MatNet with 10000 fixed ATSP instances.
Salver
Problem Size: Fiily
Clean Tour
(x100)) 4
Random
ROC0-RA
Attck Method (Attacked Tour Length (x:10))
ROCO-63
ROCO-SA
ROCO-RI
Nearest Neighbour
20
1.9354
1.9143
0.0259
2.1307 0.0155
0.0025
2.1344
2.188
49.76%)
Purthest Insertion
20
1,6092
1.5847
-000142
1.6953 + 0.0105
1,0026
0.0137
1.7183 + 0.0114
1.7469 ( 19.02%)
LKHB
20
1.4955
1.4201
0.0080
144000
+: 0.0003
14399
2: 0.0004
1,4610 = 0.0017
1.611 ( 0.11%)
MatNer
20
1.4616
1.4237
1.4674
0.0012
1,4683
1,4683 0.0009
1,4708
0.77%)
MatNet (fixed)
20
1.4623
1,4227-
0.0086
1.4865 0.0013
1.4087
0.0004
1,4714 0.0013
1.4737 (r 0.97%)
Nearest Neighbour
50
2,2247
2.2221
0.0131
2,3635 1: 0.0082
2 2,3809 1: 0.0096
2/0058 2: 0.0151
2.4530 (r 47.58%)
Furthest Insertion
50
1.9772
1.9730
0.0091
2,0533
0.0071
2,0466 0.0125
2,0632 2: 0.0089
2.1150
27.25%%
LKIB
30
16621
18098
0,0041
1.6853
0.001T
1,682 0,0010
1.6079 (r 0.35%)
MatNet
30
1.6915
1.6786
0.0051
1.7153 1: 0.0012
1.7201 0.0016
1.7255 2: 0.0012
1.7279 (r 3.96%)
MaiNetifieed
30
16992
0.0054 16694
1.7171 + 0.0021
1,7205 A 0.0005
1,7279 + 0.00077
1.7349 (r 4.38%%
Nearest Neighbour
100
2,1456
0.0079
2:2319
0.0008
2:2973
0.0112
2.2533
42.95%)
Purthest Insertion
100
1,92209
1.9188
0.0061
1.9762 0.0088
1,9782
0.0111
1,9853
0.0063
2.0144
27.79%)
LKHS
100
1,5763
1.5716
= 0.0016
1 1,5826
1: 0.0006
1 1,5818 1: 0.0005
1.5856 : 0.0008
1.5662 (r 0.62%)
MaiNet
100
1,6545
1.6492
0.0036
L.7722 0.0012
1,6815 0.0005
1.6841 + 0.0007
1,6873
(r 7.04%0
MatNet (fxee))
1.6556
1.0196-
0.0037
1.6788 0.0008
0.0003
1.08.6 0.0015
1,6919 (r 7.33%)
the traditional SOTA TSP solver. Finally, Matrix Encoding Networks (MatNet) (Kwon et al. 2021
claims as a SOTA learning-basee solver for ATSP and flexible flow shop (FFSP).
Attack model. The attack is to choose an edge and half its value, by which we get a no-worse theoretical optimum since the length of any path will maintain the same decrease. To reduce the action space, we will not select the edges in the current path predicted by the solver at the last time step. An attack example is shown in Fig. 5 in Appendix
B
The dataset comes from (K won et al. 2021), consisting of 'tmat' class ATSP instances which have the triangle inequality and are widely studied by the operation research community (Cirasella itt al. 2001). We solve the ATSP of three sizes, 20, 50 and 100 cities. The distance matrix is fully connected and asymmetric, and each dataset consists of 50 training samples and 20 testing samples.
Dataset.
Results and analysis. Tbl. 3 reports the attack results of four target solvers. where the RL based attack outperforms other methods in most cases. Note that LKH3 is the most robust among all compared solvers. We attribute the phenomenon to two aspcets of LKH3: Different initial states- LKH3 will take runs with diffenent initial states in our setting; Step by step improvement- Specifically, L.KH3 uses k-opt (Lin) 1965) to iteratively reorder and optimize the result tour sequence. The introduction of randomization and optimization should contribute to the strong robustness of LKH3. Inspired by this idea, we conduct experiments to improve the robustness of Nearest Neighbor and Furtherest Insertion in Tbl. 2 and Tbl. I0 MatNet generates different random problem instances for training in each iteration. The comparison between "MatNet" and "MatNet (fixed)" proves that the huge amount of i.i.d. training instances promotes both the performance and the robustness of the model. As Yehuda al. (2020) points out, learning-based solvers for CO cannot be trained sufficiently due to the theoretical limitation of data generation. Thus, the training paradigm with large unlabeled data can be good choice for learning-basee -based CO solvers. Besides, feeding hard samples discovered by ROCO to "MatNet (fixed)" to conduct adversarial training may also promote robustness (see Tbl. III.
3.3 TASK III: MAXIMUM COVERAGE
The maximum coverage (MC) problem is widely studied in approximation algorithms. Specifically, as input we will be given several sets S = {St, ..., Sm and a number k. The sets consist of weighted elements E & and may have overlap with each other. Our goal is to select at most i of these sets such that the maximum weight of elements are covered. The above problem can be formulated as follows, where w(-): E
+ E denotes the weight of certain element.
max
w(e) x IIE E U S.) S,ES!
s.t. S' S Sk
3E0
Solvers. It has been shown that the greedy algorithm choosing set that contains the largest weight of uncovered elements achieves approximation ratio of (1 (1-2) (Hochbaum) 1996). which has also been proved to be the post-bos polynomial-tnn -ime approximation algorithm for maximum coverage unless P=NP (Feige 1998). So choose it to serve as first attack target. Besides, the maximum coverage problem is quite suitable to be formulated as an integer linear program (ILP). Using Google ORTools AP( we transform Eq. 9 into the II.P form and attack three other general- -prppss solvers:
https::/devel www.e/ewwwoprroo..oooom googl e. wtt. izztionn
8

---

Published as a conference paper at ICLR 2023
Table 4: Evaluation for MC. The time limit in brackets for B&B solvers, which is set long enough
to output a feasible solution in the clean dataset. Stronger attackers result in smaller attacked weights.
Salver
#act-4olement
Problem Size:
Clean Weight
(x10+*
Random
ROCO-RA
Attack Method (Attakkdd
ROC0-0G
ROCO-SA
ROCO-RL
Greedy
100-200
0.7349
0.7355
0.0007
0.00012
0.7255
0.0013
0.0007
0.7239
3.36%)
CBC/0 S6)
100-200
0.7115
0.7022 + 0.0122
0J6161
0.0206
0.5448 = 0.0255
0.5423
0.0315
0,5029 (1 32.87%)
SCIP(0.56)
100-200
0,7184
0.7116 + 0.0053
0,6850 #: 0.0013
0.8508
= 0.0025
0.6803
0.0015
0.6788
(n 9.35%
(urobi().5))
100-200
0.7491
0.7495
0.0044
0.0004
0.7441
0.0000
0.7426
0.740 (e 1.09%))
Greody
150-300
L,1328
1,1330 4: 0.0011
1,1207
0.0019
1.1183 a. 0.0021
1.1201
0.0017
1,1182
2.64%)
CBC(1s)
150-300
1,0510
10088 : 0.0192
0.8973
2: 0.0886
0.8054
- 0.0:87
0. 0.7959
1 0.0482
0.7527 (r S1. 36.66%
SCIP(1s)
150-300
L.847
10867 4: 0.0027
1,0544
0.0017
1.0467
= 0.0016
L.0886 0,0012
1,043
9.07%)
Gus
150-300
1.1485
1,1486 0.0009
0.0008
1.1358 0.0011
1.1332 0.0006
1.49%)
Gready
200-400
1,4699
1,4065 + 0.0013
1.4537
0.0019
1.4533 + 0.0019
1.4552
+ 0.0013
1.4466 (r 2.84%
CBC Se)
200-400
1.4248
1.4088 :: 0.0219
1.2063
0.0475
11966
0.0575
1 0806 0.0786
1,4188
(r 30.0890)
SCIPU
200-400
1,3994
1.3952 0.0049
1.3636
0.0033
1.3608
0.0017
1.9629
1.35%
9.09%)
Gurobi(1 (1.5)
200-100
1.1889
1,4879 1: 0.0013
1.1754 4: 0.0022
1.1721 2 0.0018
1. 2097 0.0003
1.4684 (r 1.38%)
Gurobi (the SOTA commercial solver) (Gurobi Opumizztiinn 2020), SCIP (The SCIP Optimization
Suite 8.0, 202T), and CBC (an open-sourced MILP solver written in C++) (Forrest et al.. (0222. to find their vulnerabilities. These solvers are set the same appropriate time limit.
Calibrated time. In line with Nair al. (2020). we use calibrated time to measure running time of task solving to reduce the interference of backend running scripts and the instability of the server. The main idea is to solve a small calibration MIP continuously and use the average running time to measure the speed of the machine when solving different instances. Details are given in Appendix G
Attack model. The MC problem can achieve a no-worse optimum if we add new elements into certain sets, as we can cover more elements while not exceeding the threshold k. MC can be treated as a bipartite graph, where edges only exist between a set node and an element node inside the set. So our attack model is to add edges between set nodes and elements nodes, leading to a theoretically better optimum but can mislead the solvers. To reduce the action space, we only add edges for the unchosen sets, since adding edges for selected sets will not affect the solver's solution.
Dataset. For the MC problem, the distribution follows ORLIB The dataset consists of three set-element pairs 100-200, 150-300, and 200-400, each with 50 training and 20 testing samples.
Results and analysis. Tbl. 4 records the attack results of four target solvers. The RL based attack outperforms other methods across all cases in this scenario, showing the promising power of our feature extraction method and policy gradient model. Besides, the attackers have even found some instances for CBC where it cannot figure out feasible solutions under the given time limit, strongly demonstrating the vulnerability of the solvers. This effect also appears in the more challenging task Maximum Coverage with Separate Coverage Constraint MCSCC for Gurobi in Appendix C Typically, our attack model to MC problems is equivalent to modifying the objective coefficients of the original ILP model of MC problem, which might incur numerical issues for ILP solver such as unstable matrix factorization. Since we can access the source code of CBC solver and SCIP solver respectively, we find that the SCIP solver equipped with more modules improving numerical stability of solving process, such as scaling, presolving and primal heuristics, etc. Besides, SCIP also benefits from implementing more classes of branching policy and cutting planes that aim to improve the dual bound, than CBC. The experimental results are in line with the expectation for the tested ILP solvers, where CBC solver performs worse than SCIP solver in terms of both solution quality and robustness. Compared undoubtedly better in the perspective of both solution quality and robustness. One step further, we conduct experiments on tuning the hyperparameters of Gurobi improve its robustness in Tbl. [2
the open-sourced solvers, the commercial solver Gurobi performs
4 CONCLUSION
We propose Robust Combinatorial Optimization (ROCO), the first general framework to evaluate the robustness of combinatorial solvers on graphs without requiring optimal solutions or the differentiable property. Alleviating these two requirements makes generalized and flexible, helping us conduct an extensive evaluation of the robustness of 14 unique combinations of different solvers and problems, showing the effectiveness and potential of our methods. Moreover, we also provide insights to the robustness of solvers and conduct various experiments to improve their robustness, which we believe can encourage future works to develop more robust CO solvers.
http:///eeple..brus. wac..aacccc. htt......//maatttt//////////////

---

Published as a conference paper at ICLR 2023
REFERENCES
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. EJOR, 2021.
Christoph Buchheim and Jannis Kurtz. Robust combinatorial optimization under convex and discrete cost uncertainty. EURO Journal Computational Optimization, 6(3):211-238 2018.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. IEEE Symposium on Security and Privacy (SP), 2017.
Nicholas Carlini, Anish Athalye, Nicolas Papernot, Wieland Brendel, Jonas Rauber, Dimitris Tsipras, Ian Goodfellow, Aleksander Madry, and Alexey Kurakin. On evaluating adversarial robustness. arXiv preprint arXiv: arXiv: 190.:.0602000 2019.
Craig Chambers, Ashish Raniwala, Frances Perry, Stephen Adams, Robert Henry, Robert Bradshaw, and Nathan Weizenbaum. Flumejava: easy, efficient data-parallel pipelines. ACM Sigplan Notices, 45(6):363-375, 2010.
Ruoxin Chen, Zenan Li, Jie Li, Junchi Yan, and Chentao Wu. On collective robustness of bagging against data poisoning. In International Conference on Machine Learning, pp. 3299-3319 PMLR, 2022a.
Yiting Chen, Qibing Ren, and Junchi Yan. Rethinking and improving robustness of convolutional neural networks: shapley value-based approach in frequency domain. In NeurlPS, 2022b.
Jill Cirasella, David S Johnson, Lyle A McGeoch, and Weixiong Zhang. The asymmetric travel- ing salesman problem: Algorithms, instance generators, and tests. In Workshop on Algorithm Engineering and Experimentation, 2001.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In ICMI., 2018.
Uriel Feige. A threshold of In for approximating set cover. J. ACM, 45(4))633 jul 1998. ISSN 0004-5411.
John Forrest, Ted Ralphs, Haroldo Gambini Santos, Stefan Vigerske, Lou Hafer, John Forrest, Bjarn Kristjansson, jpfasano, EdwinStraver, Miles Lubin, rlougee, jpgoncall, Jan Willle,,em, h-i gassmann, Samuel Brito, Cristina, Matthew Saltzman, tosttost, Fumiaki MATSUSHIMA, and to st. coin- or/ebe: Release releases/2.10.7, January 2022. URL https:: /tt:://doiiio/ wwg/10. 5281 5904374
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Densan-adversarial training of neural networks. 15055 2016.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günne- mann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. ar 10942, 2021.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In ICLR, 2015.
Robert Grandl, Ganesh Ananthanarayanan. Srikanth Kandula, Sriram Rao, and Aditya Akella. Multi- resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Review, 44 (4):455-466, 2014.
Gurobi Optimization. Gurobi optimizer reference manual.
http://wwwwrrbb.coooo 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, 2016.
Keld Helsgaun. An extension of the tin-kernighan-i hellganu tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
10

---

Published as a conference paper at ICLR 2023
Dorit S. Hochbaum. Approximating Covering and Packing Problems: Set Cover. Vertex Cover, Independent Set, and Related Problems, pp. 143. PWS Publishing Co., USA, 1996. ISBN 0534949681.
Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In ICML, 2018.
Robin Jia and Percy Liang. Adversarial examples evaluating reading comprehension systems. In EMNLP, 2017.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In NeurIPS, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907, 2016.
Yeong-Das Dan Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. arXiv:2106. 11113,,,111,,..11111111111 2021.
Shen Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44 (10):2245-22) 2269, 1965.
Zhiyu Lin, Yifei Gao, and Jitao Sang. Investigating and explaining the frequency bias in image classification. IJCAI, 2022.
Gengyu Lyu, Songhe Feng, and Yidong Li. Partial multi-label learning via probabilistic graph matching mechanism. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 105-113, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Hongzi Mao, Malte Schwarzkopf. Shaileshh Bojja Venkatakrishnan. Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group on Data Communication, pp. 270-288. 2019.
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, al. Solving mixed integer programs using neural networks. arXiv:20/2.11339 2020.
Nina Narodytska and Shiva Prasad Kasiviswanathan. Simple black-box adversarial perturbations for deep networks. 161iv:1612.0666 2016.
Qibing Ren, Qingquan Bao, Runzhong Wang, and Junchi Yan. Appearance and structure aware robust deep visual graph matching: Attack, defense and beyond. In CVPR, 2022a.
Qibing Ren, Yiting Chen, Yichuan Mo, Qitian Wu, and Junchi Yan. Dice: Domain- attackk invariant causal learning for improved data privacy protection and adversarial robustness. In KDD, 2022b.
Bikas Saha, Hitesh Shah, Siddharth Seth, Gopal Vijayaraghavan, Arun Murthy, and Carlo Curino. Apache tez: unifying framework for modeling and building data processing applications. In ACM SIGMOD, 2015.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv: 2017.
Christian Szegedy. W. Zaremba, Ilya Sutskever, Joan Bruna, Erhan, I. Goodfellow, and R. Fergus. Intriguing properties of neural networks. arXiv:1312.6199. 2014.
The SCIP Optimization Suite 8.0, 2021. URL httph:tt///// www. http::::://wwww..ppppp....op org/

---

Published as a conference paper at ICLR 2023
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv:1705.07204, 2020.
Peter JM Van Laarhoven and Emile HL Aarts. Simulated annealing. In Simulated annealing: Theory and applications, pp. 7-15. Springer, 1987.
Nithin Varma and Yuichi Yoshida. Average sensitivity graph algorithms. In SODA, 2021.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. stat, 1050:20, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NeurlPS, 2015.
Runzhong Wang. Junchi Yan, and Xiaokang Yang. Combinatorial learning of robust deep graph matching: an embedding based approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Runzhong Wang, Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang. Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization graphs. NeurIPS, 2021.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's quadratic assignment problem with extension hypergraph and multiple-graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(9):5261-5279) 2022.
Darrell Whitley, A genetic algorithm tutorial. Statistics and computing, 4(2):65-83) 1994.
Marcus Brubaker Yash Sharma, Gavin Weiguang Ding. On the effectiveness of low frequency perturbations. In IJCAI, 2019.
Gal Yehuda, Moshe Gabel, and Assaf Schuster. It's not what machines can learn, it's what we cannot teach. In ICML, 2020.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-independent embedding and hungarian attention. In ICLR, 2020.
Jianming Zhu, Junlei Zhu, Smita Ghosh, Weili Wu, and Jing Yuan. Social influence maximization in hypergraph social networks. IEEE Transactions on Network Science and Engineering, 6(4): 801-811, 2019.
12

---

Published as a conference paper at ICLR 2023
A RELATED WORKS
Combinatorial optimization solvers. Traditional CO algorithms include but not limited to greedy
algorithms, heuristic algorithms like simulated annealing (SA) (Van Laarhoven & Aarts 1987).
Lin Mernighan-Hellee et al. 2022). SCIP (The SCIP Optimization Suite 8.0 2021), and Gurobi (Gurobi Optimization 2020).
(LKH3) (Helsgaun 2017). and branch-and-boungg solvers like CBC (Forrest
Besides, learning-basse based methods have also been proposed to tackle these problems. A mainstream approach using deep learning to predict the solution end-to-end, such as the supervised model Pointer Networks (Vinyals et al.] (2015), reinforcement learning models S2V-DQN (Khalil et al. 2017) and MatNet (Kwon et al. 20011. Though these methods did perform well on different types of CO problems, they not that robust and universal, as discussed in [Bengio et al. (2021), the solvers may get stuck around poor solutions in many cases. The sensitivity of CO algorithms is theoretically characterized in Varma & Yoshida (2011, however the metric in Varma & Yoshida (2021) requires optimal solutions which are usually unavailable in practice concerning the harhard challenge in CO.
Adversarial attack and defense for neural networks. Since the seminal study Szegedy al. (2014)
shows that small input perturbations can change model predictions, many adversarial attack methods have been devised construct such attacks. In general, adversarial attacks can be roughly divided into two categories; white-box attacks with access to the model gradients, e.g. Goodfellow et al. (2015); ; Madry et al. (2018); Carlini & Wagner (2017), and black-box, attacks, with only access the model predictions, e.g. ylas et al. (2018); Narodytska & Kasiviswanathan (2016). Besides image and text adversarial attacks (Jia Liang, 2017). given the importance of graph-related applications and the successful applications of graph neural networks (GNN) (Scarselli al.) [2008), more attention is recently paid to the robustness of GNNs (Dai et al. 2018). Orthogonal to designing more effective
attacks, there is interesting line of works that seek inspect the nature of attacks, such through
the frequency perspective (Chen et al., 20226] Lin et al.) 2022] Yash Sharma 2019).
In the mean time, many defense strategies like adversarial training Ganin et al. (2016); Tramer et al. (2020); Ren et al. (2022b) have also been proposed to counter this series of attack methods. Besides, graph matching (GM) is classic CO problem, [Ren et al. (2022a) shows how fulfill attack and defense on GM, which reveals the vulnerability deep GM by perturbing visual pixels and graph structure iteratively and improves the robustness of deep GM by separating appearance-similar nodes to be distributed more broadly.
B TRADITIONAL ATTACK ALGORITHM
As an example of traditional attack algorithm, we list the pseudo code of SA in Algorithm 2
Algorithm 2: Simulated Annealing (SA) Attack
Input: Input problem Q: solver fo: max number of actions K; action sample number M; Temperature decay AT; coefficient 3; bias eps.
Q" + Q: Q² + Q": T + 1; # initial temperature
for k - 1..K do
flag = False; # if action is available
for i < 1..M do
Random sample an edge (z, 3) in edge candidates of Q²=1; + add/delete the edge (a, y) in Qk=1, # new state by tentative action ops ); action acceptance probability
P exp( ()) fffo. -0
if |Random()) (0. 1) P then
flag TTue; Q+ Q Q" + Q+
break;
if flag False then
break;
T- AT:
Output: Problem instance g"
13

---

Published as a conference paper at ICLR 2023
Gurobi Solution Time(s)
Clean
Attacked
8
6
30-150-3K
60-300-6K
100-500-10K
Dataset Size
Figure 3: Gurobi's average time cost (no time limit) in solving clean or attacked MCSCC problems. Experiments run on 3 datasets (20 instances) of different sizes.
C EXPERIMENTS-TASS IV: MAXIMUM COVERAGE WITH SEPARATE COVERAGE CONSTRAINTS
We also study a more complicated version of the former MC problem: the maximum coverage problem with separate coverage constraint (MCSCC), which is NP-hard proved in Appendix F22 Specifically, the elements & can be classified into the black ones and the white ones W (i.e.
& W U B, W n B 0). And our goal is to select series of sets S C S to maximize the coverage of black element weights while covering no more than white elements. The problem be represented by bipartite graph, where edges only exist between set node and element node covered by the set. The problem can be formulated as:
Σ (b) x T[(b E U C+()))
max S'
BEB
S,ES'
(10)
s.t.
S'
U
C (S))
S.ES'
where w(.) denotes the weight of a certain element, C(.) denotes the set of elements covered by a set, and C+ (.) and C-((-) denotes the set of elements in C(+) with black and white labels, respectively.
Solvers. As an enhanced version of MC, the MCSCC problem is very challenging and here we propose three different solvers the target for attacking. First, the trivial Local algorithm iterates over the sets sequentially, adding any sets that will not exceed the threshold k. Second, we adopt more intelligent Greedy Average algorithm that always chooses the most cost-effective (the ratio of the increase of black element weights to the increase of number of covered white elements) set at each step until the threshold &s exceeded. Third, we formulate the problem into the standard ILP form (details in Appendix F.3) and solve it by Gurobi (Gurobi Optimization, 2020).
Attack model. Our attack model chooses to add non-existing black edges that connect sets black elements, which can lead to a theoretically better optimum since we can possibly cover more black elements while not exceeding the threshold Further, in order to reduce the action space, we only select the unchosen sets, otherwise it will be useless since adding edges for selected sets will not affect a solver's 's output solution. A successful attack example is shown in Fig. i Appendix
Dataset. There is lack of large-scale real-world datasets for MCSCC. Thus. keep the data distribution similar to the MC problem and randomly generate the dataset (Kwon et al. (021) for training. Specifically, the dataset consists of three configs of set-black element-white element: 30- 150-3K, 60-300-6K and 000-500-1KK, each with 50 training samples and 10 testing samples. More details about the dataset are presented in Appendix H
Results and analysis. Tbl the attack results on our simulated dataset. Both traditional and RI. approaches achieve significant attack effects, while RI. outperforms the others in most cases
14

---

Published as a conference paper at ICLR 2023
Table 5: Evaluation of solvers for MCSCC (notations are kept in line with MC in Table 4 Since MCSCC incorporates more constraints and is more challenging, our ROCO attackers show a more significant effect compared MC, suggesting that solvers may be more vulnerable on CO prob- lems that are inherently more challenging (e.g. with more complicated constraints). The greedy average algorithm is the most robust probably due its worst-case guarantee known as submodular- ity (Hochbaum T996).
Salver
Probleu Size. Asct-ib clem-df -eu elem.
Clean Weigle
Random
ROCO-RA
Altack Methed (Atucced (Aticcel Weigh!
ROCO-0G
ROCO-SA
ROCO-RI
Local Search
30-15003K
9.5713
9.6474 0.0825
9.8066 + 0.003T
3.6976-0000000
9.4800 = 0.0029
9.4861
(9.79%
Groddy Average
30-150--1 3K
180038
18.2541 + 0.1210
17.5101 0.0788
17.4351 + +-0.4114
17:5177
0.00M5
17.1414
9.2650
(unoh((a))
30-150--3 WK
18.9944
19.2237 + 0.1755
10.9206 + 0.2135
15:4152 + 0.3552
15,3055
0.3661
14.2740 ( 26.169)
Local Search
60-3000-6K
24.9913
25,0413 a 0.00225
24,8788
0.1300
24.7914 = 0.835
26.189 = 0.0075
218014 (r 42.54%)
Orraly Average
50-100-66
43.1625
43.1539 + 0.0475
12.7607
0.0386
42.7611 + 0.0475
42.7222
0.0085
42,1741
2,2050
(unale(2))
50-10006K
41.1828
41,8005 + 0.4007
38.2382 + 0.5159
31 37.5322
+ 0.4201
38.2916
0.3665
36J443
16.19%)
Local Search
100, 580 108,
22,9359
22,9334 1: 0.0662
22,7616 a: 0.1226
22,6598 a. 0.0183
22.7463
0.0206
22.5994
56.00%)
Grnaly Average
100-5000 IOK
51 193905
51,8005 + 0.0308
50.7481 0.0719
$0.5169 + 0.1747
60.6865
0.0413
50.881
L.615)
(unale(Sa)
100-5000 1OK
49.3236
52,8192
+ 0.5903
48.1875 + 0.5507
47.4356 + 0.4583
40:2013
0.2467
43.4866
(- 15.38%)
(especially for Gurobi). We can see from Tbl that the degradation of Gurobi after attack is much more obvious than that in MC, possibly because the computation progress of MCSCC can include more vulnerable steps than MC. Fig. [3] shows the average time cost (no time limit) for Gurobi in solving MCSCC problems. The figure illustrates that solving time on the attacked instances longer than those on the clean ones by large margin, proving the promising power of our attack framework.
D GRAPH EMBEDDING FOR SPECIFIC TASKS
We discuss specific graph embedding metries for different kinds of CO problems for reproducibility.
D.1 TASK I: DIRECTED ACYCLIC GRAPH SCHEDULING
Since the task is a directed acyclic graph, we use GCN to encode the state in the original graph and its reverse graph with inversely directed edges separately. Then we concatenate the two node embeddings and use an attention pooling layer to extract the graph-level embedding for Eq. 6
n [GCN, [G]]]GG
g AttPool(n).
(11)
D.2 TASK II: ASYMMETRIC TRAVELING SALESMAN PROBLEM
Since the graph is fully connected, we use GCN to encode the state in the graph. Then we use an attention pooling layer extract the graph-level embedding. Eq. 6 becomes:
n (GCN(G)), g AttPool(n).
(12)
D.3 TASK III: MAXIMUM COVERAGE
For the RL attack method, different from DAG and ATSP, MC has unique bipartite graph structure. Therefore, we resort to SAGEConv, which can handle bipartite data, for graph feature extraction. As input, we classify the nodes into two classes (subsets I, and elements T.) and associate them with two dimension one-hot tensors. Besides, we add one more dimension for element nodes, which records their weights. Eq. becomes:
n. SAGECOnv (Is, Ie), n, SAG Is) ge = AttPool, (nz), g. = AttPooll
(13)
D.4 TASK IV: MAXIMUM COVERAGE WITH SEPARATE COVERAGE CONSTRAINTS
The graph embedding mechanism for MCSCC is exactly the same MC since they can both be represented by a bipartite graph except that we add one more one-hot dimension to distinguish between black and white elements.
15

---

Published as a conference paper at ICLR 2023
E SUCCESSFUL ATTACK EXAMPLES
E. TASK I: DIRECTED ACYCLIC GRAPH SCHEDULING
A successful attack example is shown in Fig.
(5s, 0.6)
(5s, 0.6)
Attack
Delete AC
B
B
(2s,0.3 0.5)
035,
(4s, 0.4)
0.5)
(3s, 0.5)
(4s, 0.4)
Time 0
4
8
12
Time 0
4
8
12
Makespan = 11
Makespan 12
Optimal = 10
Optimal 10
Figure 4: DAG attack on Shortest Job First algorithm. The edges show sequential dependencies. The (3r, v) tuple of each node means running time (x:) and resource occupancy rate (z)).
E.2 TASK II: ASYMMETRIC TRAVELING SALESMAN PROBLEM
A successful attack example is shown in Fig.
3
D
C
D
C
4
4
Attack
7
2
8
5
3
3
3
Half AC
7
9
7
3
A
B
A
B
5
5
Solution: A-B-C-D-A
Solution: A-C-B-D-A
Distance 3 15
Distance = 2 + 3 7 + 17
Optimal 15
Optimal 15
Figure 5: ATSP attack on Nearest Neighbour algorithm. The directed edge represents the distance
between two nodes. The attack action edge AC will cause further distance.
E.3 TASK III: MAXIMUM COVERAGE AND TASK IV: MAXIMUM COVERAGE WITH SEPARATE COVERAGE CONSTRAINTS
Successful attack examples are shown Fig.
F FORMULAS AND PROOFS
F.1 No-WORSE OPTIMAL SOLUTION GUARANTEE
We will prove that the attack constrains can guarantee no-worse optimal solution.
Proposition 1. Given the clean CO problem Q and the instance Q obtained by the attacker.
16

---

Published as a conference paper at ICLR 2023
Sets
Elements
Sets
Elements
Elements
Black Elements
White Elements
Black
Sets
Sets
A
Attack
Attack
8
0
Add A2,44
Add
Solution: BCD
Solution:
Solution: BC
Solution: AB
elements Optimal
Cover elements Optimal
Cover 8eight=8+8+9-25
Cover Weight=7-7+9-23
Optimal=25
Optimal=25
Figure 6: Left: MC attack on Greedy algorithm. The threshold of the sets is and all the elements have unit weight. Attacks on edges A2 and A4 will cause lower covered weight. Right: MCSCC attack on Greedy Average algorithm. The threshold the white elements is and the value near the black element represents its weight. Attack edge Aa causes lower covered black element weight.
1. If the allacker removes some of the constraints or makes constraints easier to reach, which is defined as the first strategy loosening the constraints, the optimal solution will be no-worse.
If the attacker decreases the value of the objective function obtained from some feasible solutions, which is defined the second strategy lowering the cost, the optimal solution will be no-worse.
Proof. We define x* and as the optimal solution, X and X as the feasible solution set in Q and Q
According to the formulation in Eq
[ we have
min c(x, Q) s.t. (, Q) I 0, I,...! min c( Q) s.t. (5. Q S 0, 11 1,...,
(14)
(15)
The attacker modifies the constraints h; to h4 three ways: 1) Stay the same. For each same solution x, [x(x,, Q) = 1, Q). 2) Remove the constraint. The constraint (x, Q) no longer in Q. 3) Acquire lower value. For each same solution x, hx Q) S h; (x, Q). Hence, the less than zero inequality is easier achieve. Because if we have (x, Q) < O, there must be 1x Q) S.
Three parts of the constraints ensure each feasible solution x E X satisfies the constraints in Q still satisfies the constraints in Q. Therefore, we have X X X. Since the cost function does not change and x" E X, the optimal solution in new instance Q can at least the same. Mcanwhile, The new feasible solution set X may provide a better solution. conclusion, the optimal solution will be no-worse.
The attacker decreases the cost function in the new instance where c(x, Q) S c(x, Q) for each instance x. The constraints stay the same so that X. For x", there is c(x", Q) I c(x", Q) and x E X which means the optimal solution in Q will be no-worse.
F.2 MCSCC NP-HARD PROVEMENT
We prove that the decision problem of MCSCC is NP-complete, thus the optimization problem of MCSCC in our paper is NP-hard. For the sake of our proof, here we redefine MCSCC and give definition of traditional NP-Complete problem: Set Covering.
The decision problem of MCSCC. Given a series of sets element set consisted of white and black elements 3 = WUB. The sets cover certain elements (white C- R2) or black C+ (R2)) which have their weights w(e).. Does there exist a collection of these sets R' R to cover M black elements weight while influence more than white elements?
(RI, ..., Ra along with an
Set Covering. Given a set U of elements, a collection S,, S Sn subsets of U, and integer k does there exist collection of < k of these sets whose union equals U/?
17

---

Published as a conference paper at ICLR 2023
First, need to show that MCSCC is NP. Given collection of selected sets R' {R1, Rg....,,Ry R, we can simply traverse the set, recording the covered black and white ele- ments. Then, can assert whether the covered black element number is more than & and fraudulent monetary value is no less than m.
Since the certification process be done in O( NP-hardness, we can get it reduced from Set Covering.
tell that MCSCC is NP. Then, for
Suppose we have Set Covering instance, we construct equivalent MCSCC problem follows:
Create [U] black elements with weight I, corresponding to elements in Set Covering.
Create sets, C+ (R:)= S..
Connect each set to a different white element of weight 1.
Set the white element threshold kw equal to the set number threshold kg.
Set black element weight target M = -U]-
Suppose we find collection of which meet the conditions of MCSCC, then we select subsets in Set Covering S; iff we select Rj- The total number of subsets is no more than k (k,) since the influenced white element number is equal to [R']. The subsets also cover since the covered black element weight (each with amount 1) is no less than [U] Similarly, we can prove that we can find a suitable subset collection for MCSCC we have found a collection of subsets that meet the conditions of Set Covering. So we can induce that Set Covering Sp MCSCC
Thus, we have proved that the decision problem of MCSCC is NP-Complete
F.3 MCSCC ILP FORMULATION
As discussed in the main text, B denotes the set of black elements, W represents the set of white elements, S refers to the collection of sets and E denotes the element set. Using notations above, we can translate Eq. 10 into standard ILP form as follows:
max
YM X W[],,
s.t.
Σ
YI1
k
iEB
KEW
[
(16)
for i = 1....18,, (Y - (05))
X x I(i in EDD) 0O
where X[j] (0. 1) denotes set S, is chosen (1) not (0), Y[1 {0, shows whether element i has been covered by the chosen sets. Besides, W[i] E R records the weight of the elements while Elil C E is the corresponding elements of set Sj. The third equation ensures the element binary variable [[i] to be iff it has been covered by certain set (if ]X
and element i & Elj). then the formula in the second bracket is negative, ensuring Y[1 be else if element i is not covered by any chosen sets, then the second formula is positive and [[] must be 0).
G CALIBRATED TIME
Considering the instability of the server and the interference of other running programs, calibrated time is designed to evaluate the server speed within a small period of time. Specifically, we define the speed as the reciprocal of the Wall clock time to solve given calibration MIP. The calibration MIP is generated in the stable condition and solved K times to record the basic speed speed When evaluating the other instances, we will first evaluate the calibration MIP K times calculate the current speed speed K is the number of samples, which is set as 20 in our experiments.
To fairly measure the solvers' performance under different computational resources, take MC prob- lems as an example, given calibration MIP is also specified MC problem to design time limits for different server speeds. Specifically, the new time limit for the solver will be as:
New Time Limit speed
x Uniform Time Limit
(17)
speed now
18

---

Published as a conference paper at ICLR 2023
H MCSCC DATASET
Besides the distribution rules of MC, we generate the MCSCC dataset mainly by two rules: 1) The black element weights are uniformly distributed the range [0, 1]. The number of black elements is 5% of white elements. 3) The covered black element weights and wight element numbers of sets follow a Gaussian distribution with a large standard deviation, to enlarge the differences between sets.
0-1.5
1.5-3
3-4.5
4.5-6
8.0%
4.0%
6+
14.0%
41.0%
33.0%
Figure 7: The distribution of black element weights covered by different sets. The æ y pair in legends means the set can cover weights in range (a. yl.
Fig. shows the black element weights covered by different sets in a 100-500-10K problem instance. As see, few well-designed sets cover most weights while the others be regarded as complementary to these sets. This design enlarges the difference between the different quality of solutions, therefore promoting the potential be attacked.
EXPERIMENT SETUPS
Experiment environments. DAG and ATSP experiments are run on a GeForce RTX 2080Ti while MC and MCSCC experiments are run a GeForce RTX 3090 (20GB). We implement our models with Python 3.7, PyTorch 1.9.0 and PyTorch Geometric 1.7.2.
RL settings. Tbl. 6 records the hyperparameters for RL during the training process. Trust region clip factor is a parameter in PPO agent to avoid model collapse. We also adopt some common policy- gradient training tricks like reward normalization and entropy regularization during training processes.
Attacker byperparameters. For fair comparison different attackers and the consideration of RL in- set ensure similar evaluation time across different attack meth-
ference time, the hyperparameters ods. According to the time complexity we calculate Tbl. 7 here we specify the following parame- ters: number of iterations N, beam search size B and number of different actions M in each iteration.
DAG: ROCO-RA N 30; ROCO-OG B 3, M 9; ROCO-SA N 5, M 6; ROCO-RL 3.
ATSP: ROCO-RA N = 130; ROCO-OG B = 5, . = 25; ROCO-SA N = 13, A = 10; ROCO-RL 5.
MC: ROCO-RA N = 220; ROCO-OG = 6, M = 36; ROCO-SA SA N 22, M = 10: ROCO-RL B 6.
19

---

Published as a conference paper at ICLR 2023
Table 6: RL parameter configuration in tasks DAG, ATSP, MC and MCSCC.
Table 7: Comparison of our attackers. Random- ness means it will produce different results in different trials. Trained means whether the param- eters are tuned by a training set.
Parameters
DAG
ATSP
MC MCSCC
Actionst
20
10
Reward discount factor
0.95
0.95
0.95
Atlack Method
Ramdommess
Trained
Time Complexity
Trust region clip factor
0.1
0.1
0.1
GNN type
GCN
GCN
SAGEConN
ROCO-RA
OUNK) O(BMK) O(NMK)
GNN layerst
3
ROCO-OG
Learning
le-4
1e-3
le-3
ROCO-SA
Node feature dimensionst
64
20
16
O(BRK)
Table 8: The ratio of budget K average number of edges in different task. Each task has three datasets of different sizes, which is denoted by small, medium and large in the table.
Average Number of edges |اا] in three sizes
Tasks
Budget K
Ratio K/|E)
Small Size
Medium Size
Large Size
DAG
468
930
1386
1.44%
4.27%
ATSP
400
2500
10000
10
0.10%
2.50%
MC
1260
1873
2497
10
0.40%
0.79%
MCSCC
4680
9567
16171
10
0.06%
0.21%
MCSCC: ROCO-RA N = -50; ROCO-OG B 6, M 36; ROCO-SA N 25, M = 10; ROCO-RL. 6.
J ANALYSIS OF ATTACK BUDGET
Unnoticeable Property. The perturbation to the problem instance is conducted by modifications to the graph structure. To get non-trivial hard instances around clean examples, the attack is limited within given attack budget K, which means at most K edges be modified in graph. Tbl. compares our framework to classical works on adversarial attacks for images and graphs. Similar to the e-Perturb budget (Goodfellow et al. 2015) in image classification task and the number of edges modification (Dai et al. 20188 in graph classification task, we use the number of edges modification budget to satisfy the unnoticeable property. Tbl. shows the ratio budget K the average number of edges in these tasks. The low ratio shows that our modification to the original graph is minor. Apart from this, we also show the relation between the attack effect and the attack budget in the next paragraph.
Attack Percentage
Attack Percentage(96 (%)
100
Neighbour
20
10
15
20
10
Attack Budget K
Attack Budget
Figure 8: Relation between attack percentage to attack budget K in the DAG task with prob- lem size 50.
Figure Relation between attack percentage to attack budget K in the ATSP task with problem size 20.
Sensitivity to the Budget K. To evaluate sensitivity of the proposed method to the budget across different tasks, define attack percentage the ratio of the performance loss in current edge budget to the the performance loss in the budget upper bound. For example, in ATSP task, the budget upper bound is 10 and will get 0% attack percentage using 0 edge modification and 100% using
20

---

Published as a conference paper at ICLR 2023
Table 9: Comparison of different number of swapped node pairs the "step by step improvement" modification for Nearest Neighbour algorithm on the dataset ATSP-20. Lower clean tour length represents better original performance, while lower attacked tour length and robustness ratio denote better robustness.
Solver
Clean Tour Length
Attacked Tour Length J
Robustness Ratio J
Nearest Nrigghouu(Orrginaa))
1.9354
2.0867
42.97%
Nearest Neighbour(k = 3)
1.7519
1.8838
29.07%
Nearest Neighbour(k: 5)
1.7258
1. 1.8504
26.78%
Nearest Neighbour(k: =
1.7253
1.8462
26.50%
Table 10: Comparison of different initial city number 8 on the "different start state" modification for Furthest Insertion algorithm on the dataset ATSP-20.
Solver
Clean Tour Length
Attacked Tour Length
Robustness Ratio +
Furthest (nseriion
1.6092
1.6959
16.20%
Furthest Insertion(s 3)
1.5602
1.6246
11.31%
Nearest Neighbour(s = 10)
1.5207
1.5774
8.07%
Nearest Neighbour(s s 20)
1.5005
1.5504
6.23%
Table 11: Adversarial training(AT) for MatNet on dataset ATSP-20. MatNet-X means we use X fixed ATSP instances for training while MatNet-X-AY means we use X hard cases generated from the clean instances by our framework.
Data Type
MatNet-1000
MatNet-1000-AA
MatNer-10000
MatNet-10000-AT
MatNet
Clean instances
1.4687 1.4761
1.4691
1.4623
1.4626
1.4616
Hard instances
1.4742
1.4737
1.4703
1,4708
10 edge modification. Fig. show the relation between attack percentage to attack budget in different tasks. In Fig. 8] the three solvers all reach the high attack percentage using few budget. may be more appropriate to reduce the budget because of marginal utility. Corresponding this, it is possible for LKH3 to improve the attack performance as the budget rises shown in Fig, 9 Therefore, the sensitivity budget K can help set the appropriate attack budget in practice.
Attack Percentage(%)
Attack Percentage(%)
100
Greedy Lsujo.s
Local Search Greedy Avenge
SOP
Su
Gurobills:
0
8
10
2
8
10
Attack Budget
Attack Budget
Figure 10: Relation between attack percent- age to attack budget K in the MC task with problem size 100-200.
Figure 11: Relation between attack percent- age to attack budget in the MCSCC task with problem size 30-150-3k.
K ROBUSTNESS IMPROVEMENT
Apart from evaluating the robustness of the solvers, here provide some preliminary yet positive results on improving solvers' robustness, while full solution is indeed beyond the scope of this paper focus practical robustness evaluation.
21

---

Published as a conference paper at ICLR 2023
Table 12: Hyperparameter tuning for Gurobi on MC(100-200). We focus on tuning important hy- perparameters: MIPFocus and Heuristics through Gurobi's API, which are described more detailedly text.
Hyperparameter
Hard Example Weightt
Clean Weight
ROCO-RI.
Robustness Ratio
MIPFocus=O, Hcurstics=0.00
0.7414
0.7480
0.7418
0.83%
MIPFocus=O, Heurstics=0.05
0.7409
0.7491
0.7409
1.09%
MIPFocus=O, Hcurstics=0.10
0.7386
0.7483
0.7383
1.34%
MIPFocus=1, Heu0stics=0000
0.7488
0.7478
0.7430
0.64 %
MIPFocus= Heurstics=0.05
0.7472
0,7490
0.7427
0,84%
MIPFocus= Heurstics=0.10
0.7455
0,7480
0.7410
0,94%
MIPFocus=2, Heurstics=0.00
0,7466
0.7460
0.7395
0,87%
MIPFocus=2, Hcurstics=0.05
0.7448
0.7475
0.7398
1.03%
MIPFocus=2, Heurstics=0.10
0.7433
0.7466
0.7383
1.11%
Adversarial Training. We perform adversarial training (AT) for MatNet (fixed training data) on dataset ATSP-20. Tbl. presents main results on AT. Specifically, MatNet- 1000 denotes use 1000 fixed ATSP instances to train the MatNet, while MatNet- 100ct-10010111111 AT represents that we use 1000 hard instances generated by the ROCO-RL attacker adversarially train the MatNet. The table shows that after AT, MatNet achieves obviously better results on the hard instances, at the cost of bit performance degradation on the clean instances. However, AT cannot compensate for the insufficiency of training data, as we can see that the performance of MatNet-1100-AA is still worse than MatNet-11000 on the hard examples. The reason why we do not conduct AT on the original MatNet is that it trains for 2000 epochs, each with 10000 randomly generated ATSP instances, which too large a number for us generate adversarial samples. Notably, the results in the table are relatively close to each other which may introduce bias in the experiments. This implies that we may further explore other CO problems to test the effectiveness of AT, which we leave for the future work.
LKHddd robustness improvement. As we find from Tbl. 3 that LKH3 is the most robust solver for the ATSP problem, we try to adapt its randomization and optimization strategies to the Nearest Neighbour and the Furthest Insertion algorithm to promote their robustness.
First, we develop Nearest Neighbour (Step by step improvement). Instead of the well well-designed optimization method k-opt (Lin (965) of LKH3, here we just greedily swap a pair of nodes on the solution obained by Nearest Neighbour for k times. For each time we will enumerate all the node pairs and calculate the corresponding reduced tour length, then find the best pair to swap. We do experiments for different number of swaps k on the dataset ATSP20. The robustness ratios (the lower the better) in Tbl. 9 are calculated w.r.t. the incumbent optimal solution. The incumbent optimal tour length is 1. 1.4595 obtained by LKH3. We can find the clean tour length decreases, and the robustness increases with a larger value of k. Another interesting phenomenon is that the solver with k: and k 8 have similar clean tour lengths, while the latter is obviously more robust than the former. These results demonstrate that the optimization process does contribute greatly to the robustness of the solver.
Second, we develop Furthest Insertion (Different start state). The Furthest Insertion algorithm will be influenced by the initial city and generate different solutions accordingly. Therefore, we can set different cities as the initial city and choose the best solution as our result. We do experiments for different number of start states s on the dataset ATSP20. From Tbl. 10 we can find that the clean tour length decreases, and the robustness increases with larger value of which proves that randomization does contribute to the robustness of the solver.
Hyperparameter tuning. We use hard examples to tune the hyperparameters of Gurobi on the MC problem (problem size 100-200). We refer to Gurobi's Documentation in Guroobi Optimization (2020) and choose two important hyperparameters: MIPFocus and Heuristics, which are easily set by the python interface of Gurobi. Specifically, MIPFocus (integer, default O, set between 0 and 3) allows us to modify our high-level solution strategy. By default, the Gurobi MIP solver strikes a balance between finding new feasible solutions and proving that the current solution is optimal. A higher MIPFocus will focus on proving optimality more. Heuristics (double, default 0.05, set between and 1) determines the amount of time spent in MIP heuristies. Larger values produce more and better
22

---

Published as a conference paper at ICLR 2023
feasible solutions, at a cost of slower progress in the best bound. We generate 100 hard examples from the testing dataset and tune the two hyperparameters using grid search for MIPFocus E [0. 1, 2] and Heuristics E [0, 0.05, 0.10].
As wC can see from Tbl. 12, the robustness ratio (Clean Weight ROCO-RL) / Clean Weight declines almost the hard example weight (averaged over the cost value 100 hard examples) increases. This shows that tuning the Gurobi hyperparameters is indeed useful to promote its robustness. Moreover, we can see that the hard example weight is the largest when MIPFocus=1 and Heuristics=0.0, which shows that Gurobi needs to pay more attention to narrowing the optimal bound to better deal with the hard examples.
L GENERALIZABILITY
One potential drawback of ROCO is its scalability. Since the training of the proposed RL strategy requires calling of the solver at each timestep. the training process indeed takes a relative long time (taking at most one day in our largest dataset setting, acceptable compared to common RI. pipelines). However, the inference process is still efficient since we only need to take one forward pass with beam search. To resolve the concern that ROCO cannot scale to graphs real-world scenarios, we provide additional results to show ROCO-RL's generalizability from small to large graphs
Table 13:
Evaluation results of ROCO-RL's generalizability DAG. Each row denotes results on a testing size using models trained with different problem sizes, each column denotes testing a model trained certain problem size with different sizes of testing data. The robustness ratios calculated w.r.t. the incumbent optimal solution. Lower robustness ratios denote better robustness.
Solver Size: #job
Shortest Job First
Critical Path
Tetris
50
100
150
50
100
150
50
100
150
50
28.95%
28.59%
28.55%
15.34%
15.22%
14.86%
14.22%
13.67%
13.02%
100
26.79%
26.85%
26.99%
14.94%
15.22%
14.90%
11.57%
15.41%
14.29%
150
28.73%
28.63%
28.91%
16.02%
14.95%
15.58%
12.87%
15.53%
12.73%
300
28.10%
27.67%
27.26%
15.91%
16.16%
16.23%
13.09%
14.83%
12.38%
As we can see from Tbl. 13 the RL agents trained small graphs can be used to modify problems with larger graph sizes, achieving great performance degradation for different solvers. These results strongly support that ROCO can be trained on small graphs and then be used to measure robustness on large graphs.
M FURTHER DISCUSSIONS
Limitations. First of all, as our framework is designed for combinatorial optimization problems on graphs, needs non-trivial reformulation to fit into CO problems cannot encoded by graphs. Secondly, the principle of designing our attack action is based on the graph modification to achieve no-worse optimum, which may not be applicable to all CO problems.
Potential Negative Impacts. As we propose the first general framework to evaluate the robustness of combinatorial solvers on graphs, this may be used by unscrupulous people to attack different solvers, increasing the burden on engineers to cope with the malicious attacks.
Outlook. Our paradigm opens up new space for further research, including the aspects: 1) Utilizing the hard cases generated by our framework design defense models, such adversarial training and hyperparameter tuning. 2) Developing more general attack framework for CO problems that cannot be represented by graphs. 3) Besides our studied tasks, the attacking idea of loosening constraints and lowering costs is also generalizable Minimum Vertex Cover, which need further evaluation on their robustness.
wide range of CO problems such as Maximum Cut and
23


Reviews:
[{"review_id": "x7bEGQap0vy", "reviewer": "Reviewer_oJSV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work propose a new evaluation metric for evaluating the robustness of solvers on combinatorial optimization (CO) problems. The proposed evaluation metric is agnostic to optimal values, which may be hard to obtain in real world situations. As the proposed metric requires another problem instance with better optimal objective value but \"harder\" to solve, this work also proposed a RL-based approach, to modify the structure of the input graph which represents the underlying CO problem. It then evaluate the robustness of three combinatorial solvers (traditional solvers, learning based solver and specific MILP solver like Gurobi) using the proposed metric with the proposed approach on four combinatorial tasks: Directed Acyclic Graph Scheduling, Asymmetric Traveling Salesman Problem, Maximum Coverage, and Maximum Coverage with Separate Coverage Constraint. \n\nOverall, the proposed evaluation metric has some novelty over other existing metrics, but it needs problem-specific designs of how to modify the graph structure (e.g., add or remove edges, change edge length, etc). Also, the training of the proposed RL strategy requires call of the solver at each step, which may not be practical for real-world scenarios where the graphs may have thousands (or even more) of nodes. More important, I think this work would have more important contributions if it could utilize ROCO to provide more insights on what make one solver more robust than other solvers or what makes one solver more robust on a specific problem than other problems. Such follow-up experiments and analysis are important to tell the usefulness of ROCO and why it is evaluating the real robustness of the model.\n\n\n\n", "summary_of_the_review": "This paper studied the robustness of a combinatorial solver as a black box regardless of its differentiability. It developed a robustness metric that does not need the optimal solution by using another instance with no-worse optimal cost guarantee. It uses an RL-based approach to find such instances given some hand-designed relaxation rules given a specific problem. In the experimental section, this work conducted extensive experiments on 14 different combinations of solvers and variants of robust metrics. Yet, it lacks in-depth analyses of why and when a solver is more robust under this metric as well as how the proposed metric is evaluating the real robustness of the model. ", "strength_and_weaknesses": "Strength:\n-\n\n[+] This work tackles an important domain: how to evaluate the robustness of solvers for Combinatorial Optimization problems.\n\n[+] The proposed evaluation metric does not need the optimal value of the underlying CO problem instance and does not require the solver to be differentiable.\n\n---\nWeakness:\n-\n\n[-] I do not see much insight into why and when a solver would be more robust on a problem than other solvers or other problems from the current experimental results. This part is important in order to tell the usefulness of ROCO and why it is evaluating the real robustness of the model.\n\n[-] The proposed evaluation metric needs problem-specific designs of how to modify the graph structure (e.g., add or remove edges, change edge length, etc)in the attack model.\n\n[-] Sometimes it may be easier to degenerate the performance of good solvers than the bad ones especially when the good one is close to the optimal but the bad one is close to some baseline value, in this case, I think the proposed metric would favor the bad one as it could just perform equally bad on the original and modified instance.\n\n---\n\nMinor comments:\n- It would be better to compare the robustness using ratios rather than raw numbers for all tasks in the main paper. \n- The presentation of the work could be better if some terminology could be defined (earlier) such as \"attacker\" and \"no worse optimal\". costs\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iX9tM3DpNUP", "reviewer": "Reviewer_2fgV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This manuscript proposes a new method (called ROCO) to study robustness of algorithms/solvers for combinatorial optimization problems. It does not need the optimal solution, nor does it require a differnetiable solver.\n\nTo avoid the need for knowing the optimal solution, they modify the input instance in such a way that the optimal cannot become worse. For example, you can reduce edge weights or relax certain constraints. Then they re-run the solver on the new instance and expect that the solution will not produce worse objective values. How much worse it gets determines the level of non-robustness.\n\nThen they get to the problem of finding these \"hard\" instances for the solver. Their reinforcement learning-based method outperforms a few baselines (random edge selection, \"optimum guided\" via beam search, and simulated annealing). In their empirical study, they look at a few combinatorial optimization problems like task scheduling and max coverage.", "summary_of_the_review": "Decent paper with interesting practical results, though the empirical section and the initial motivation sections could be expanded with more insight.", "strength_and_weaknesses": "S1: The new metric does not need to know the optimum.\nS2: It treats the solver as black-box, so it also works with non-differentiable combinatorial optimization problems.\nS3: The RL-based approach works well in practice.\n\nW1: Why is this a good notion of robustness? It's not clear what robustness is supposed to achieve.\nW2: A robustness metric should perhaps produce a number between 0 and 1. While one can simply normalize with respect to the original solution, there is no discussion of the advantages or disadvantages.\nW3: There could be more discussion about relative robustness of the different solvers. For example, CBC performs poorly in terms of robustness on max cover instances. It also performs poorly in terms of quality compared to the other solvers. Is there more to read from this? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "V4xLOibTox9", "reviewer": "Reviewer_baVX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies to measure the robustness of combinatorial solvers. The solver is defined as non-robust if the CO problem has relaxed constraints while the solver obtains a worse solution. This paper proposes to modify the corresponding graph structure for the CO problem to relax its constraints, and measure the performance of the solver on the modified graph compared to that on the original graph.", "summary_of_the_review": "This paper studies a novel problem, i.e., the robustness of CO solvers, and provides an interesting framework that evaluates the robustness of various solvers on different tasks. More analysis of the evaluation results, elaboration of the applications of the attack model design, and more profound technical contributions are expected.", "strength_and_weaknesses": "Strength:\n\n1. The problem, i.e., the robustness of CO solvers, is novel, interesting, and important.\n2. The proposed framework evaluates different solvers and tasks extensively.\n\nWeaknesses:\n\n1. As an *evaluation* paper, the definition of robustness should be made clearer. I understand that the optimal solution is usually infeasible for NP-hard problems; however, a quantitative measure of robustness is still needed. For example, is the solver more robust with a lower (perturbed_solution - original_solution) absolute value or lower relative ratio (perturbed_solution - original_solution)/original_solution? And how to compare the robustness of two solvers if they get largely different original solutions?\n2. Can the evaluation results lead to some insights about the robustness of different solvers, i.e., greedy solvers, heuristic solvers, neural network solvers, etc.?\n3. Though the motivation to study the robustness of CO solvers is clear, more concrete examples/applications are needed to elaborate on why the attack model makes sense.\n4. The novelty mainly comes from the problem definition, while the technical contribution is a little bit limited. \n\nMinor: Page 5, the sentence above 3.2, edgesh -> edges", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5whQN8iHpn", "reviewer": "Reviewer_Agfm", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a framework and algorithms for verifying the robustness of combinatorial optimization solvers for graph problems. A key idea is to define a new criterion of successful attacks to the solver, defined without using the optimal solutions, whereas the previous work requires them. The paper then proposes some methods to implement the attacks. Among them, one attack is implemented based on reinforcement learning. Experimental results show the advantages of the RL-based attack against other proposed methods and the random naive method.", "summary_of_the_review": "The paper proposes a reasonable definition of the success of an attack for combinatorial optimization solvers over graphs.", "strength_and_weaknesses": "Strength:\n- A reasonable definition of the success of an attack for combinatorial optimization solvers\n- Several implementations of attacking are proposed and evaluated in experiments\n\n\nWeakness:\n- The problems are restricted to graph problems so far\n\nThe key idea of the paper is to propose a reasonable criterion of the success of an attack. The previous work needs an optimal solution, which is intractable in general. The current work does not have such a disadvantage and becomes more practical. \n\n\n\nMinor technical issue:\n- In Definition 1, there is no definition of \\tilde{x^*}.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster