Mind Your Solver! On Adversarial Attack and Defense for Combinatorial Optimization
Authors: Han Lu
Zenan Li
Runzhong Wang
Qibing Ren
Junchi Yan
Zhigang Hua
Gan Liu
JUN ZHOU
Xiaokang Yang
Venue: ICLR 2022 Submitted (2022)
Keywords: Adversarial Attack
Combinatorial Optimization
Reinforcement Learning

Abstract: Combinatorial optimization (CO) is a long-standing challenging task not only in its inherent complexity (e.g. NP-hard) but also the possible sensitivity to input conditions. In this paper, we take an initiative on developing the mechanisms for adversarial attack and defense towards combinatorial optimization solvers, whereby the solver is treated as a black-box function and the original problem's underlying graph structure (which is often available and associated with the problem instance, e.g. DAG, TSP) is attacked under a given budget. Experimental results on three real-world combinatorial optimization problems reveal the vulnerability of existing solvers to adversarial attack, including the commercial solvers like Gurobi. In particular, we present a simple yet effective defense strategy to modify the graph structure to increase the robustness of solvers, which shows its universal effectiveness across tasks and solvers. 

Under review as a conference paper at ICLR 2022
MIND YOUR SOLVER! ON ADVERSARIAL ATTACK AND DEFENSE FOR COMBINATORIAL OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Combinatorial optimization (CO) is a long-standing challenging task not only its inherent complexity (e.g. NP-hard) but also the possible sensitivity to input conditions. In this paper, we take an initiative on developing the mechanisms for adversarial attack and defense towards combinatorial optimization solvers, whereby the solver is treated as a black-box function and the original problem's 's underlying graph structure (which is often available and associated with the prob- lem instance, e.g. DAG, TSP) is attacked under a given budget. Experimental results on three real-world combinatorial optimization problems reveal the vulner- ability of existing solvers to adversarial attack, including the commercial solvers like Gurobi. In particular, we present simple yet effective defense strategy modify the graph structure to increase the robustness of solvers, which shows its universal effectiveness across tasks and solvers.
INTRODUCTION
The combinatorial optimization (CO) problems are widely studied due to their importance in prac- tice (e.g. job scheduling, routing, matching, etc). In the last century, a variety of heuristic meth- ods (Van Laarhoven & Aarts, 1987; Whitley, 1994) are proposed to tackle these standing and often NP-hard problems. Driven by the recent development of deep learning and reinforcement learning, many learning-based methods (Khalil et al., 2017; Mao et al., 2019; Kwon et al., 2021) are also developed in this area, which show promising potential often for their cost-efficiency.
Despite the success of solvers in various combinatorial optimization tasks, few attention has been paid to the vulnerability and robustness of combinatorial solvers, regardless of whether they are learning based not. A line of relevant works aims at handling combinatorial optimization under uncertainty (Buchheim & Kurtz, 2018). However, to our best knowledge, ensuring the robustness of combinatorial solvers with slightly modified problem instances remains relatively unexplored. It is worth noting that many CO problems can be essentially formulated as graph problem (Khalil al., 2017; Bengio al., 2020), hence it is attractive and natural to modify the problem instance by modifying the graph structure, to generate more test cases for solvers. In fact, vulnerability can often be an inherent challenge for CO solvers since the problem is often strong nonlinear and NP-hard. From this perspective, consider attack and defense CO solvers in the following aspects.
From the attack side, developing attack models can be useful for thoroughly evaluating a solver's ro- bustness. The solvers may be more fragile than the general impression: for traditional learning-free solvers, in some cases, their heuristics and hyperparameters may not universal and stable enough such that small change problem condition graph structure may deteriorate the performance notably. This also holds for recent machine learning based solvers as the model may be overfit and the objective landscape be complex due to the inherent difficulty of discrete CO problems.
As a result, is imperative to develop defense mechanisms and techniques to improve the robustness of CO solvers, either for sarming-based models traditional ones, especially if the approach can be in black-box mode without knowing the details of the solvers. In particular, it is even desirable develop out-of-box defense mechanism. Our hope is that this may be realized when the problem instance change' involves only graph structure variation which is often the case.
Readers may argue that there are little deliberate attacks to CO solvers, while one can regard such attacks as the problem instance variation which can often happen in real-world e.g. when the network takes small daily change Directed Acyclic Graph (DAG) and Fraud Coverage problems will be studied in our experiments.

---

Under review as a conference paper at ICLR 2022
Table 1: Comparing our framework (ROCO) with FGSM (Goodfellow et al., 2015) and RL-
S2V (Dai et al., 2018). e-perturb. means the change of one pixel should be bounded in B-hop neighbourhood means the new attack edges can only connect two nodes with distance less than B.
Method
Data
Task
Attack target
Attack cost
Ättack principle
Defense tech. invisible change adversarial Training random drop symmetric RL
FGSM
image
classitication
pixels
Perturb.
RL-S2V
graph
classification
edges (connectivity)
edge # B-hop neighbour
ROCO
CO instance
CO solution
edges (constraints)
edge #
no worse optimum
To this end, we present Robust Combnaotorial Optimization (ROCO), a framework for testing and improving the robustness of given combinatorial optimization solver. Table I compares our frame- work to classical works in images and graphs. Our attacker limits the number of attacked edges in the graph and guarantees that the optimal solution must not become worse. Our defender en- sures that the new solution is also feasible for the pre-defended problem. The overview of ROCO framework is summarized in Fig. 1. In summary, this paper makes the following contributions:
1) Given the fact that combinatorial problems can often be represented by underlying graphs, we propose to perform adversarial attacks toward CO solvers deteriorate their solution quality. To our best knowledge, this is the pioneering work that formally studies adversarial attacks on combi- natorial solvers, though their vulnerability has been occasionally recognized by the community.
2) We propose ROCO, an adversarial framework that consists of both attack and defense models on top of CO solvers. We design our attack models with both learning- -basin and traditional simulated annealing methods by slightly modifying the graph structures (e.g. add, delete or modify edges). To increase the robustness of the combinatorial solvers, we further propose defense mechanism against attacks. Our attack and defense models are applicable to solvers regardless of learning-based or not.
3) We implement and apply our adversarial attack and defense models to three common combi- natorial optimization tasks: Directed Acyelic Graph Scheduling, Asymmetric Traveling Salesman Problem and Fraud Coverage. The experimental results on black-box attack/defense show the effec- tiveness and generality of our approach. The source code will be made public available.
2 RELATED WORK
Combinatorial optimization. As widely studied problem, there exist many traditional algorithms for CO, including but not limited to greedy algorithms, heuristic algorithms like simulated anneal- ing (SA) (Van Laarhoven & Aarts, 1987) or Lin- HelsaahanHHelsaam (LKH3) (Helsgaun, 2017), as well as commercial solvers like Gurobi (Gurobi Optimization, 2020). Besides, driven by the re- cent development of deep learning and reinforce learning, many learning-based methods have also been proposed to tackle these problems. A mainstream approach using deep learning is to predict the solution end-to-end, such as the supervised model Pointer Networks (Vinyals et al., 2015), rein- forcement learning models S2V-DQN (Khalil et al., 2017) and MatNet (Kwon et al., 2021). Though these methods did perform well on different types of COPs, they are not that robust and universal, as discussed in (Bengio al., 2020), the solvers may get stuck around poor solutions in many cases. Different from works (Moon et al., 2019; Zang et al., 2020) which apply CO for attack against neural networks, we take an initiative on the adversarial attack and defense on CO.
Adversarial attack and defense. Since the seminal study (Szegedy et al., 2014) showed that small input perturbations can change model predictions, many adversarial attack methods have been de- vised to 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 Madry et al., 2018; Carlini & Wagner, 2017), and black-box attacks, with only access to the model predictions, e.g. (Ilyas 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 et al., 2008), more attentions are recently paid to the robustness of GNNs. In the mean time, many defense strategies like adversar- ial training (Ganin et al., 2016; Tramèr et al., 2020) have also been proposed to counter this series of attack methods. Since CO problems can usually be encoded by a graph structure and inspired by (Dai et al., 2018), which develops an RL based attack policy towards GNNs, we propose a novel and flexible attack and defense framework for CO solvers using both heuristic and RL methods.
al., 2015;
Note that the recent adversarial graph matching (GM) network show how to fulfill attack or defense via perturbing regularizing geometry property on the GM solver. (Zhang et al., 2020) degrades the
2

---

Under review as a conference paper at ICLR 2022
Original graph
Attacked graph
Defensed graph
CO Pro
graph encoding
Allat c/8
Defender: Sym metric EL
Iterate K actions
Iterate actionn
Black bux Solver
Black-box Solver
Black-bok
Solver
Reward
Reward
Objective
Attacked Objective
Defensed Objective
Overview of our attack and defense framework ROCO for CO solvers. ROCO targets on the CO problems which can be encoded by graph (often holds in practice). Here delete/add the edges in the encoded graph represents delete/add constraints in CO. Symmetrie RI. denotes that the defender and attacker share the same structure with symmetric reward and action space.
Figure 1:
quality of GM by perturbing nodes to more dense regions while (Ren et al., 2021) improves robust- ness by separating nodes to be distributed more broadly. However, the techniques are deliberately tailored to the specific problem and can hardly generalize to the general CO problems. Meanwhile they work a white box mode while we aim to develop more flexible black box models.
COMBINATORIAL OPTIMIZATION WITH ATTACK AND DEFENSE
3.1 PROBLEM FORMULATION
In general, traditional CO problem Q defined graph 9 (V, E) can be formulated as:
min f(x(g) s.t. (x 9) S 0, = 1, I....,
(1)
where denotes the decision variable, f(x()) represents the target function w.r.t. the specific CO problem and (x, 9) denotes the set of constraints (usually encoded in graphs). However, due to the NP-hard nature (which is often the case in CO), it can be infeasible find the optimal solution within polynomial time. Therefore, we denote a different solver S (which gives the feasible solution ((S(Q)))) to approach the global optimum f (Q).
It is worth noting that the optimum (Q) of Eq. will become no worse if we loosen part of the constraints since the previous decision variable is still feasible under the new setting. Intuitively, we may expect the solver to give better (at least the same) solution on the new problem Q'. However, we will show in this paper that many solvers are vulnerable to such perturbations and their solutions can become worse under our attacks, despite the loose bound ("( < (Q).
Given a solver S and an original problem Q represented by a graph G, the adversarial attacker is asked to modify the graph G into g' to attack the solver S, such that:
f(S(Q')gg) - f(S(Q))9)
max g'
8.1.
g'= hence Q -+ ((Q) T(G
Here T(.-) + {0, 13 is an equivalency indicator (Dai et al., 2018) that tells whether graphs G and g' satisfy a specified constraint. In short, the above equation tells that the attacker is aiming at making small modifications the original graph, loosening the constraints while making the solver solution as bad as possible
In this paper, concretely our attacker g is allowed modify edges (e.g. adding or removing edges) from G to construct the new graph. Accordingly, we define the equivalency indicator as:
T(G,9')
(EIEBEE)JU(E - E) S K)
(3)
which ensures that the attacker can modify no more than edges the original graph.
On the other hand, it is imperative to develop defense mechanism for against the above attacks. Notice that the attack methods we mentioned before have some degree of symmetry (adding/deleting edges),
simply do reverse operations for defense. For example, if we relax the constraints by removing edges while worsening the solver's solution, then we can add some edges (constraints) and get better solution (that is, the symmetry). Besides, the new solution under stronger constraints
3

---

Under review as a conference paper at ICLR 2022
(54,
(Ss, 0.6)
(5s, 0.6)
A
Attack Delete AC
Defense Add BC
(2s, 0.5)
(3s,
(4s, 0.4)
(.5,0.5)
(35, 0.5)
(4s, 0.4)
(2s, 0.5)
(3s, 0.5)
(46, 0.4)
Time 0
12
Time
8
12
Time 0
12
Finish time = 10 Figure 2: Attack and defense on applying Shortest Job First algorithm for solving DAG.The edges show the dependencies. (z, y) each node means run time (x) and resource occupancy rate (ÿ).
Finish time
Finish 12
surely feasible for the original graph (then we can use it in the original graph to get f(S(Q))))) Hence, the problem can be formulated as:
min
(4)
s.t.
d(=, hence Q - Q', H2 S for 1...., T(G.9)=
here the constraints Hg' ensure that the feasible space of g' is subset of G.
Concrete Examples. Fig. 2 shows the attack and defense of the Shortest Job First algorithm on DAG (TSP and FC examples in Appendix A). We remove an edge but get a worse finish time (objective the smaller the better). Then we add an edge for defense, which leads to a better solution.
In this paper, focus black-box attack and defense, which means have no idea the solver. This setting is practical especially considering there are plenty of commercial solvers c.g. Gorubi and CPLEX etc. We leave white box attack and defense for future work.
3.2 ATTACK VIA GRAPH MODIFICATION
We devise both reinforce learning (RL) and heuristic based attackers. For RL, the popular Proximal Policy Optimization (PPO) (Schulman et al., 2017) framework is adopted. We also design three traditional heuristic attackers: random sampling, optimum-guiit search and simulated annealing.
3.2.1 REINFORCE LEARNING BASED ATTACK
Eq. treated the learning objective and we resort to reinforcement learning (RL) to optimize G' in a data-driven manner. In general, we modify the graph structure and compute f(S(Q"))))) alternatively, getting rewards that will be fed into the PPO framework and train the agent iteratively.
MDP Formulation. Given an instance (S, 9), with total modification budget, we model the attack via sequential edge modification as a Finite Horizon Markov Decision Process (MDP).
State. The current graph G (i.e. the graph G' after i actions) is treated as the state, whose nodes and edges encode both current input and constraints. The original graph G" is the starting state.
Action. As mentioned in Sec. 3.1, the attacker is allowed to add/delete edges in the graph. So a single action at time step l is a E AA C E*, Here our action space A is usually a subset of all the edges E* because we restrict the action space (i.e. abandon some useless edge candidates) according to the previous solution S(Q²) to speed up our algorithm. Furthermore, we decompose the action space (O(VP)) + O(VV)) by transforming the edge selection into two node selections: first selecting the starting node, then the ending node.
Reward. The new graph gh++1 results in a new CO problem Qi+11 whose objective becomes f [((()+1)] The reward is the increase of the objective:
r = ((S(Q*+)))
f(S(Q*))g*)
(5)
Terminal. Once the agent modifies edges or edge candidates become empty, the process stops.
PPO Design. The input and constraints of CO problem usually tightly encoded in the graph structure. Thus, our PPO agent (i.e. the actor and the critic) should behave according to the graph features. Specifically, We resort the Graph Neural Networks (GNN) for graph embedding:
GN ), g AuPPoolnn
4

---

Under review as a conference paper at ICLR 2022
where the matrix (with the size of node number x embedding dim) is the node embedding, and an attention pooling layer is used to extract a graph level embedding g. The GNN model can differ by the CO problem. After graph feature extraction, we design the corresoonding actor and critic net:
Critic. The critic predicts the value of each state G*. Since aims reward maximization, a max pooling layer is adopted over all node features which are concatenated (denoted by [-II-D) with the graph embedding g, fed into a network (e.g. ResNet block (He et al., 2016)) for value prediction:
V((*) = ResNeti (MaxPooll()
Actor As mentioned Sec. 3.2.1, the edge selection is implemented by selecting the start and end node. The action scores are computed using two independent ResNet blocks, and a Softmax layer is added to regularize the scores into probabilities within [0. as follows:
P(ai) = softmax (oftmaa((esNett((11313)
((a2)a)) softmax (Resaextteeeeeeee [aniinaaa]]l g))
(8)
where n n[a1] denotes the embedding for node a₁ We add the feature vector of the selected start node for the end node selection. For training, actions are sampled w.r.t. their probabilities. For testing, beam search is adopted to find the optimal solution: actions with top- probabilities are chosen for each graph in the last time step, and only those actions with top-B rewards will be reserved for the next search step (see Alg. I for details).
3.2.2 HEURISTIC ALGORITHM T 1: Attack framework by iterative edge manipulation (RL version)
Traditional heuristic algorithms are also stud- ied, with three attack algorithms as follows.
Input: Input graph 9; solver S; max number of actions K; beam size B.
Random sampling. In each iteration, an edge is randomly chosen to be modified in the graph and it repeats for K iterations. We run N attack trials and choose the best solution. can reflect the robustness of solvers with the cost of time complexity O(NK).
G 9; G" +- G; set initial state
for 15.61..1 do
for <- 1..B do
beam search for graphs last step Select (a1, with top-B probabilities;
Predict P(ai). ((az(a)) on G 1
for each (b, a1, 02) pair do
optimum-guidedd search (OG-Search). It focuses finding the optimum solution dur-
g' a'(baa, aaa,,,n .a)) <- modify edge (a1, aa) in gk 1; new state by tentative action f (b, a1, 02)) > f(S]G" then
ing each iteration. We use beam search to maintain the best current states and randomly sample M different actions from the candidates to generate next states. The number of iterations is set to be no more than K. Its time complexity is ((BK)).
g + (b, 01, 02) ) # update the optimal attacked graph
Sort g'(..s)) w.r.t. their solutions by decreasing order; # select top-B graphs for next step G + Gi..B:
Simulated Annealing (SA). Simulated an- nealing (Van Laarhoven comes from the idea of anncaling and cool- ing used in physics for particle crystallization. In our scenario, a higher temperature indicates a higher probability of accepting worse solution, allowing to jump of the local optimum. As the action number increases and the temperature decreases, we will be more conservative and tend to re- ject the bad solution. The detailed process is shown in Appendix B and we will repeat the algorithm for N times. SA is a fine-tuned algorithm and we can use grid search to find the best parameter to fit the training set. Its time complexity is OKN
Output: Optimal Attacked Graph G*
Aarts, 1987)
Table 2: Comparison of attack models. Ran- dom means it will produce different results in different trials. Finetune means the algo- rithm can be tuned by training set.
Table 2 concludes the attacking methods property and time complexity. Since the former three algo- rithms are inherently stochastic, we will run them multiple times to calculate the mean and standard deviation for fair comparison.
Technique Random OG-Search
Random
Finetune
Time ONK)) O(BM)) MN
SA /
3.3 DEFENSE VIA GRAPH MODIFICATION We adopt RL as the defender and treat Eq. 4 as the learning objective. The defense MDP formulation is just the same as Sec. 3.2.1 except that we set [[S(@)][)) [(S(Q++1)]e) and use the symmetric action of the attacker. It is worth noting
RL
O(BMK)
5

---

Under review as a conference paper at ICLR 2022
Table 3: DAG attack results of Ratio (%) 1 Std. Baseline denotes mean finish time (real time
should x 5000) on test set. Ratio represents time improvement after attack w.r.t. baselines. The larger the ratio, the better attack performance the adversarial attack method achieve. Random, OG- search, SA are tested for 10 trials to calculate the mean and std.
TPC-
Attack Method (Ratio = Sid)
Solver
Baseline
jobé
Random
OGarch
RL
Shortest Job First
50
20.9228
1.08 0.12
1:33
1.54=0.00 0.07
1.11
Critical Path
50
17.3900
8.13 1: 0.44
9.03 1: 0.25
9.58
0.15
9.26
Tetris (Grandl al., 2014)
50
16.4538
11.57 + 0.60
12.05 + 0.80
14.02 + 0.52
14.22
Shortest Job Fast
100
38,3202
0.26 = 0.03
0.41 1 0.04
u.48 = 0.02
0.54
Critical Path
100
32.0355
8.57 0.28
8,98 0.27
9.13 0.02
9.24
Tetris (Gmndl et al,, 2014)
100
30.3722
13.27 + 0.36
12.60 + 0.73
14.70 + 0.49
15.41
Shortest Job First
150
57.1554
0.84 0.07
1.12 1. 0.08
1.30 0.05
1.35
Critical Path
150
48.7963
5.33 0.37
6.27 + 0.37
6.65
0.12
6.85
Totris (Grandl ct al., 2014)
150
44.9376
11.21 + 0.85
11.41 = 0.90
13,04 + 0.26
12.73
Table 4: DAG attack and defense results of Time J and Ratio (%) J. The solvers' solutions are
recorded and the all the ratio is computed by the solved finish time w.r.t. Normal solution.
Solver
Mode
jobif-50
50
job#
100
jobs=
150
Time]
Ratio..
Time.
Ratiol.
Time_]
Ratio
Shortest Job First
Normal
20.9228
0.00
38.3202
0.00
57.1554
0.00
Shortest Job First
Attack
21.2093
1.37
38.5335
0.55
57.9326
1.36
Shortest Job First
Defense
20.9151
-0.04
38.0470
-0.71
57.4370
Critical Puth
Normal
17.3900
0.00
32.0355
0.00
48.7963
0.00
Critical Path
Attack
18.9782
9.13
34.9976
9.25
52. 1519
6.88
Critical Path
Defense
18.4335
6.00
33.4258
4.34
49.9011
2.26
Tetris (Grandl al,, 201-4)
Normal
16.4538
0.00
30.3722
0.00
44.9376
0,00
Tetris (Grandl et al., 2014)
Attack
18.7944
14.22
35.0321
15.34
50.6415
12.69
Tetris (Grandl et al., 2014)
Defense
17.7033
7.59
34,2604
12.80
49.2008
9.49
that the defense RL agent can not only play defensive role against the attacked problem instance, but can also help further improve the solution of normal instances, as will be shown in some of our experiments. We leave more in-depth analysis and corresponding approach design for future work.
EXPERIMENTS AND RESULTS
We conduct experiments on three representative tasks: Directed Acyelic Graph Scheduling, Asym- metric Traveling Salesman Problem and Fraud Coverage. The former two problems are popular problems in CO. The third problem is originated from a real-world transaction dataset. The detailed graph embedding for the three tasks is shown in Appendix C. In Appendix G, provide the train- ing and evaluation parameters of different solvers for fair time comparison and reproducibility. All experiments are run RTX 2080Ti and RTX 3090 (see Appendix H for the detailed testhed).
4.1 TASK I: DIRECTED ACYCLIC GRAPH SCHEDULING
Task scheduling for heterogeneous systems and various jobs is popular problem due its practical importance. Many systems formulate the job stages and their dependencies as a Directed Acyclic Graph (DAG) (Saha et al., 2015; Chambers et al., 2010; Zaharia al., 2012). 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 finish time of the jobs i.e. we should finish all jobs as soon as possible.
Solvers. We choose three popular heuristic solvers as our attack targets. First, the Shortest Job First algorithm chooses the jobs greedily with minimum completion time. Second, the Critical Path algorithm analyzes the bottleneck and finishes the jobs in the critical path sequence. Third, the Tetris (Grandl et al., 2014) scheduling algorithm models the jobs as 2-dimension blocks in the Tetris games according to their finish time and resource requirement.
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 or better than the original one since there are less restrictions. As result, in the DAG scheduling tasks, the attack model is to selectively remove existing edges.
Defense model. We propose to add non-existing edges on the input graph associated with the CO problem, and obviously the new solution under more constraints is still feasible for the original CO problem. The motivation is to help tune the graph structure to be more suitable for heuristic

---

Under review as a conference paper at ICLR 2022
algorithms. To reduce the action space, propose pre-process the node pairs that already have dependencies and remove the corresponding edges in the candidate set.
Dataset. We use the TPC-H dataset (attp: composed of business-orientee queries and concurrent data modification. Many DAGs have tens even hundreds of stages with different duration and numbers of parallel tasks. As each DAG in TPC-H dataset represents a computation job, we gather the DAGs randomly and generate three different datasets, TPC-H-50, TPC-H-100, TPC-H-150, of each containing 50 training and 10 testing samples. Each DAG node has two properties: execution time and resource requirement.
detochhddefallt asp), which is
Results for attack. Table 3 reports the results of our four attack methods, where RL outperforms other learning-fre methods in most cases, illustrating the correctness of our feature extraction techniques and training framework. It worth noting that even the sim- plest random attack can cause significant performance degradation to the CO solvers, showing their vulnera- bility and the effectiveness of the attack framework.
Made
Nornal
Albakk
Defense
Results for attack and defense. Table and Fig. show the results of attack and defense experiments DAG. In general, the defense model can compensate for the damage of the attack and lutions than the baseline in some cases. It's also worth noting that for some instances, the edges removed in the attack stage will be added back in the defense.
Figure 3: Finish time | as DAG objective score (mean and std by 10 trials) among three modes: attack, defense and nor- mal: schedule 100 jobs from TPC-H. At- tack will incur worse score than in normal mode, which can be remedied by defense.
obtain better
4.2 TASK I: ASYMMETRIC TRAVELING SALESMAN PROBLEM
The classic traveling salesman problem (TSP) is to find the shortest cycle to travel across all the cities. Here we tackle the even challenging asymmetric TSP (ATSP) for its generality.
Solvers. Four algorithms are treated as our attack targets: i) Nearest Neighbour greedily adds the nearest city to the tour. ii) Furthest Insertion finds the city with the furthest distance to the existing cities in the tour and inserts it. iii) Lin- Kermighnn Heuristic (LKH3) (Helsgaun, 2017) (7) is the traditional SOTA TSP solver. iv) Matrix Encoding Networks (MatNet) (Kwon al., 2021) claims as SOTA learning- baaneng-bassed solver for ATSP and flexible flow shop (FFSP).
Attack model. The attack is to choose an edge and half its value, after which we will get better theoretical optimum. To reduce the action space, we will not select the edges in the current path predicted by the solver at the last time step.
Defense model. First we calculate the optimal path by the solver and add these edges to the candi- date set. The action is to modify an edge's ss weight by doubling the distance of that edge in order to encourage the solver to explore other paths.
Dataset. It comes from (Kwon et al., 2021) consisting of 'tmat' class ATSP instances which have the triangle inequality and are widely studied by the operation research community (Cirasella et al., 2001). We solve the ATSP of three sizes, 20, and 100 cities. The distance matrix fully con- nected and asymmetric, and each dataset consists of 50 training samples and 20 testing samples.
Results for attack. Table 5 reports the attack results of four target solvers, In general, the learning- based solvers (e.g. MatNet) or those with intrinsic randomness (c.g. LKH3) show stronger robust- ness to the attacks. Furthermore, it is notable that the RL based attack outperforms in most cases.
Results for attack and defense. Table 6 shows that the defense model works well on ATSP. In addition to making up the degeneration by attack, in some cases it even obtains shorter total distance.
4.3 TASK III: FRAUD COVERAGE
Our last problem instance refers to Fraud Coverage (FC), which is an emerging NP-Complete (de- tails in Appendix D.1) problem abstracted from real life: the growing online transactions have also spawned criminals and scams. The transactions can be classified into black (fraudulent) events and white (normal) events W. To block fraud events, the bank system designs series of rules R to

---

Under review as a conference paper at ICLR 2022
Table 5: ATSP attack results of Ratio (%) f = Std. Baseline denotes mean tour length on test set.
Result is the mean ratio on all test instances computed by the solved tour length w.r.t. basclines.
Baseline
Attack Method
Solver
City#
x10f
Random
OG-Search
SA
RL
Nearest Neighbour
20
1,9354
10.09 0.79
9.34 1.67
10.28
12.94
Furthest Insertion
20
1.6092
5.35 = 0.65
3,18=022
6.78
0.71
8.56
LKH3 (Helsgaun, 2017)
20
1.4595
0.03 + 0.02
0.08 = 0.03
0.10
+: 0.07
0.11
MatNet (Kwon al,, 2021)
20
1.4616
0.40 0.08
0.46-000
0.46 0.06
0.65
Nearest Neighbour
50
2.2247
6.21 0.37
8.06 7.02=0.43
10.26
Furthest Insertion
50
1.9772
1.15 0.36
3.51 0.63
4.35 0.45
6.97
LKH3 (Helsgaun, 2017)
50
1.6621
0.19 0.04
0:21 0.04
0.37 0.06
0.35
MatNet (Kwon et al., 2021)
50
1.6915
1.39 = 0.07
1.71=0006
2.01 - 0.07
2.15
Nearest Neighbour
100
2.1456
4.02 0.46
3.33 0.71
3.81 0.552
5.02
Furthest Insertion
100
1,9209
2.88 0.46
2.97 0.58
3.35 + 0.33
4.87
LKH3 (Helsgaun, 2017)
100
1.5763
0.40 0.04
0.54 0.03
0.39 + 0.02
0.63
Mat (Kwon et al., 2021)
100
1.6545
1.37 0.06
1.63 0.03
1.79 0.04
1.98
Table 6: ATSP attack and defense results of Distance + and Ratio (%) 4. The solutions are
recorded and the ratio computed by the solved tour length w.r.t. normal solution.
ATSP-20
ATSP:50
ATSP-100
Solver
Mode
Distance.
Ratiol
Distance|
Ratiel
Distance
Ratio!
Nearest Neighbour
Normal
1.9354
0.00
2,2247
0.00
2.1456
0.00
Nearest Neighhour
Attack
2.1366
10.40
2.4264
9.07
2.2439
4,58
Nearest Neighbour
Defense
1,7564
-9.25
2,2069
-0.80
2,0319
-5.30
Furthest Insertion
Normal
1,692
0.00
1.9772
0.00
1.9272
0.00
Furthest Insertion
Attack
1,7088
6.19
2.0957
5.99
1.9963
3.58
Furthest Insertion
Defense
1,5210
-5.48
1.9558
-1.08
1.8990
-I -1.46
LKH3 (Holsgaun, 201")
Normal
14595
0.00
1.6621
0.00
1,5763
0.00
LKH3 (Helsgaun, 2017)
Attack
14598
1.6671
0.30
1.5867
0.66
LKH3
(Hlllsaan, 2017)
Defense
1,4955
0.00
1.6610
0.07
1.5744
-0.12
MatNet [Kwon et al, )021)
Naraal
LJ617
1,6913
1,6315
0.00
MatNet (Kwon et al., 2021)
Attack
1,4708
0.62
1.7261
2.04
1.6841
1.79
MatNet (Kwon et al., 2021)
Defense
1.4591
-0.18
1.6696
-1.29
1.6185
-2.18
identify transactions as either black or white events. The goal is to select subset of rules R C R to maximize the coverage of fraudulent monetary values while affecting no more than K white events. The problem can be represented by a bipartite graph, where any edge exists between a rule node and an event node only when the event is deemed as black by the rule. Formally:
max R
Σ (b) BEB
I(b
(C)))))
s.t. U C (ri) NER
where w-()) denotes the monetary value of a certain transaction event, C(.) denotes the set of events covered by a rule that are deemed as black events, and C++ (-) and C (-) denotes the subset of events in C(-) with true labels being black and white, respectively.
Solvers. As emerging real-world CO task, the FC problem is very challenging and here propose three different solvers as the target for attacking. First, the trivial Local algorithm which iterates over the rules sequentially, adding any rules that will not exceed the threshold. Second, more intelligent Greedy Average algorithm that always chooses the most cost-effective (the ratio of the increase of black event money values the increase of number of covered white events) rule each step until the constraint isn't 't satisfied. Third, we formulate the problem into standard ILP form (details in Appendix D.2) and solve it by Gurobi.
Attack model. Intuitively, when a white event is mislabeled as a black event, the FC problem will achieve an equal or better optimum (Q),, since we can possibly cover more white events while not exceeding the threshold. In our attack model, we focus on the attack toward the edges rather than the nodes. We choose to add non-existing black edges that connect rules to black events, which leads to theoretically better optimum and can potentially mislead the solvers. Further, in order to reduce action space, we only select the unchosen rules, otherwise will be useless since adding edges for selected rules would not affect a solver's 's output solution. Here we report the attack method on adding black edges and present the results for attacking black nodes in the Appendix F.I.
Defense model. Similar the attack method, as defense we remove the existing black edges that connect rules to black events. To reduce action space, we select the rules chosen in the prior solution, since deleting black edges for the unchosen rules will not change the solution.
Dataset. We analyze the distribution of transaction amounts and rule coverage of the real dataset, then generate series of simulated data for experiments. The distribution of events amount and the
8

---

Under review as a conference paper at ICLR 2022
Table FC attack results of Ratio (%) 1 1 Std. The Gurobi time limit is shown brackets w.r.t. different data sizes (it should be long enough to give feasible solution but not too long for attack).
Baseline the average original solution of the solvers on test set. The ratio here is the mean of ratios on all test instances computed by the solved FC monetary value w.r.t. baselines.
problem size:
Attack Method (Ranio + Std)
Baseline
rulef-eventt
Random
OG-Search
SA
RL
Local Search
30:3K
9,5713
1:
0.77
4
Greedy Average
30-3K
18.0038
2.72 + 0.16
3.17
2.70 0.22
4.79
Gurobi(1s) Is)
30-3K
18.8934
10.41 1.13
18.42 + 1.88
18.99
1.95
50.68
Local Search
60-66
24.9913
0.80 0.14
Greedy Average
60-6K
43,1625
0.91 + 0.09
0.93
1.02 + 0.09
2.29
Gurohi(2))
60 6K
41.1828
7.15 +: 0.84
9.35 4.002
7,02 4 0.89
100,00
Local Search
100-103 TOK
22,9359
0.76 0.08
1.23
0.83 0.09
1.55
Greedy Average
100-
51,3905
1.25 + 0.14
1.70
1.37 + 0.08
1.61
Gurobit5s)
100-10K
49.3296
6.33 4: 0.70
7.69 4 0.96
4.26
0.48
92.01
Table 8: FC attack and defense results of Fraud$ 1 and Ratio (%) 1. The solvers' solutions are
recorded and the ratio is computed by the solved FC monetary value (FraudS) w.r.t. Normal solution.
rule#=30, eventH=3K
rulc#=601, event#=6K
10lo
Solver
Mode
Fraud51
Ratio
Fraud51
Ratio
Fraud$1
Ratiot
Local Search
Normal
9.5713
0.00
24.9913
0.00
22.9359
0.00
Local Search
Attack
9.4638
-1.12
24.8038
-0.75
22,6930
-1.06
Local Scarch
Defense
10.0680
5.19
25.8300
3.36
23.7252
3.44
Greedy Average
Normal
18.0038
0.00
43.1625
0.00
51.3905
0.00
Greedy Averge
Attack
17.1256
-488
42.3911
-1.79
50.5651
-1.61
Greedy Average
Defense
17.6850
-1.77
42.8371
-0.75
51.0684
-0.63
Gurobi
Normal
18.8934
0.00
41.1828
0.00
49.3296
0.00
Gurobi
Attack
2.7194
-85.61
2.2218
-94.60
4.6731
90.53
Gurobi
Defense
17.2712
-8.59
42.1617
2.38
51.2941
3.98
rule coverage is shown in Appendix E. The dataset consists of three rule-event pairs 30-3K, 60-6K and 100-10K, each with 50 training samples and 20 testing samples.
Results for attack. Table shows the attack results our simulated dataset. We can observe that both heuristic and RL approaches have yielded significant attack effects, while RL outperforms the others most cases (especially for Gurobi, in many cases it is not even possible to give a feasible solution within time after employing RL attacks).
Results for attack and defense. Table 8 records the results of attack and defense experiments on FC prob- lems. Experiments are conducted on the same test set.
Artack Defonce
Curois solutan limel
In general, the defender can compensate for the dam- age of attack effectively and obtain an even better so- lution than the baseline in some cases. Besides, as a
commercial solver, Gurobi should be able to obtain op- timal solutions if in sufficient time (assuming we have unlimited computational resources). So we record the time for Gurobi to find the optimal solution under at- tack and defense. The result is shown in Fig. 4, where Gurobi's solution time after attack (defense) signifi- cantly increases (decreases). This inspires us attack toward the solvers' solution time in future work.
1000
rules
Figure 4: Gurobi's mean time cost in solv- ing FC problems. Run experiments on datasets (20 instances) of different sizes.
CONCLUSION AND OUTLOOK
We have presented general adversarial attack and defense framework called ROCO top of combinatorial solvers. For attack, we devise both RI and traditional heuristic attackers to modify the underlying graph structure of combinatorial problems. Mcanwhile, defense mechanism to modify the ill-posed problem in a reversed way to increase the robustness of combinatorial solvers. Experiments show the effectiveness of our paradigm and techniques.
propose simple yet effective
The proposed paradigm opens up large space for further research, at least in the following aspects: 1) new attack/defense techniques beyond graph structure but also node/edge attribute; 2) iterative adversarial training for defense model, especially for learning- based solvers (at least in the sense of tailored data augmentation); 3) white-box attack/defense when the solver information is known.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d'horizon, 2020.
Christoph Buchheim and Jannis Kurtz. Robust combinatorial optimization under convex and discrete cost uncertainty. EURO Journal on Computational Optimization, 6(3):211-236, 2018.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness neural networks. 2017
IEEE Symposium Security and Privacy (SP), pp. 39-57, 2017.
Craig Chambers, Ashish Raniwala, Frances Perry, Stephen Adams, Robert R Henry, Robert Brad- shaw, and Nathan Weizenbaum. Flumejava: easy, efficient data-parallel pipelines. ACM Sigplan Notices, 45(6):363-3775 2010.
Jill Cirasella, David 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, pp. 32-59. Springer, 2001.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack graph structured data. In International conference on machine learning(ICML), pp. 1115-1124. PMLR. 2018
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversann training of neural net- works, 2016.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. International Conference on Learning Representations (ICLR), 2015.
Robert Grandl, Ganesh Ananthanarayanan, Srikanth Kandula, Sriram Rao, and Aditya Akella. Multi-resource packing for cluster schedulers. ACM SIGCOMM Computer Communication Re- view, 44(4):455-466, 2014.
Gurobi Optimization. Gurobi optimizer reference manual. http: /tt::///wwwwww gurobi com, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition( (CVp)) pp. 770-778, 2016.
Keld Helsgaun. An extension of the lin-kernghhan-helsgan tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
Andrew Iyyas, Logan Engstrom, Anish Athalye, and Jessy Lin. Black-box adversarial attacks with limited queries and information. In International Conference on Machine Learning(ICMI) pp-
2137-2146. PMLR, 2018.
Robin Jia and Percy Liang. Adversarial examples for evaluating reading comprehension systems. In Empirical Methods in Natural Language PretiugeePrrreeee Prucessing(EMNLP) 2017.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in Neural Information Processing Systems(NIPS),, 30: 6348-6358 2017.
Yeong-Dac Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. arXiv preprint arXiv:2106.111 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations//CLLN 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 Data Communication, pp. 270-288. 2019.
10

---

Under review as a conference paper at ICLR 2022
Seungyong Moon, Gaon An, and Hyun Oh Song. Parsimonious black-box adversarial attacks via efficient combinatorial optimization, 2019.
Nina Narodytska and Shiva Prasad Kasiviswanathan. Simple black-box adversarial perturbations for deep networks, 2016.
Jiaxiang Ren, Zijie Zhang, Jiayin Jin, Xin Zhao, Sixing Wu, Yang Zhou, Yelong Shen, Tianshi Che, Ruoming Jin, and Dejing Dou. Integrated defense for resilient graph matching. In ICML, pp- 8982 8997, 2021.
Bikas Saha, Hitesh Shah, Siddharth Seth, Gopal Vijayaraghavan, Arun Murthy, and Carlo Curino. Apache tez: A unifying framework for modeling and building data processing applications. In Proceedings of the 2015 ACM SIGMOD international conference on Management of Data, pp- 1357-1369, 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, 2017.
Christian Szegedy, W. Zaremba, Ilya Sutskever, Joan Bruna, D. Erhan, Goodfellow, and R. Fergus. Intriguing properties of neural networks. CoRR, abs/1312.6199, 2014.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc-
Daniel. Ensemble adversarial training; Attacks and defenses, 2020.
Peter JM Van Laarhoven and Emile HI. Aarts. Simulated annealing. In Simulated annealing: Theory and applications, pp. 7-15. Springer, 1987.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in Neural Infor- mation Processing Systems(N/PS),, 28:2692-27006 2700, 2015.
Darrell Whitley, A genetic algorithm tutorial. Statistics and computing, 4(2):65-85, 1994.
Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael Franklin, Scott Shenker, and Ion Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. 9th {USENIX} Symposium on Networked Sys- lems Design and Implementation (NSDI) 12), pp. 15-28, 2012.
Yuan Zang, Fanchao Qi, Chenghao Yang, Zhiyuan Liu, Meng Zhang, Qun Liu, and Maosong Sun. Word-level textual adversarial attacking as combinatorial optimization. Proceedings of the 58th Anmual Meeting the Association for Computational Linguistics, 2020. doi: 20.1863/v1/2020.
acl-main.540, URL http: /xx doi. org/ 0 /8653/ vl /2020 acl-mai mma inmiin... 540.
Zijie Zhang, Zeru Zhang, Yang Zhou, Yelong Shen, Ruoming Jin, and Dejing Dou. Adversarial attacks on deep graph matching. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin (eds.), NeurlPS, pp.
Curran Associates, Inc., 2020.

---

Under review as a conference paper at ICLR 2022
APPENDIX
A EXAMPLES FOR ATSP AND FC
To have more intuitive understanding of the attack and defense ATSP and FC, provide two examples here. Fig. 5 displays attack and defense effect on Nearest Neighbour algorithm of an ATSP instance. Fig. 6 displays the attack and defense effect Greedy algorithm of an FC instance with white event threshold 5.
3
D
4
Attack Half AC
Defense Double CB
7
4
7
2
3
5
3
9
3
3
B
1
1
Solution: A-B-C-D-A
Solution: A-C-B-D-A
Solution: A-C-D-B-A Distance= 2 4 3 = 10
Distance= 3 + 4 5
Distance= 3 1
Figure 5: ATSP attack and defense Nearest Neighbour algorithm. The attack action edge AC will cause further distance. The defense action on edge CB will help the algorithm improve the solution, even better than the origin.
White Rules
White Events
Rules
Black Events
White Events
Rules
Black Events
7
Attack
Defense
Add Aa
Remove De
8
9
Solution:BCD
Solution:AD
Solution:ABC Fraud$-74748+8-30
Fraud$=8+8+9925
Figure 6: FC attack and defense on Greedy algorithm. The attack action on edge Aa will cause lower fraudulent monetary value. The defense action edge De will help the algorithm improve the solution, even better than the origin.
12

---

Under review as a conference paper at ICLR 2022
B HEURISTIC ATTACK ALGORITHM
As heuristic attack example, we list the pseudo code of SA Algorithm 2.
Algorithm 2: Simulated Annealing (SA) Attack
Input: Input graphs 9; solver S; max number of actions K; action sample number M; Temperature decay AT; coefficient (.
go 9: 9 go; T 1; # initial temperature
for k 4 1..K do
flag False; # if action is available
for i - 1. do
Random sample an edge (z. y) in edge candidates of G
g' f- add/delete the edge (ar, y) in Gh- # new state by tentative action
P = exp( - ((S1g ((Sps==))tpppp # action acceptance probability
Random(O, 5 then
flag = True; g g': gh
break;
flag = False then
break;
7- AT:
Output: Graph g*
C GRAPH EMBEDDING FOR SPECIFIC TASKS
C.I 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 reverse graph with inversely directed edges separately. Then we concatenate the two node embedding and use attention pooling layer to extract the graph-level embedding for Eq. 6:
n
AttPool(n).
C.2 TASK II: ASYMMETRIC TRAVELING SALESMAN PROBLEM
Considering the graph is fully connected, we use GCN to encode the state the graph. Then we use an attention pooling layer extract the graph-level embedding. Eq. 6 becomes:
(GCN())), AttPool(n).
C.3 TASK III: FRAUD COVERAGE
For the RL attack method, different from DAG and TSP, FC has a unique bipartite graph structure. Therefore, resort SAGECony, which handle bipartite data, for graph feature extraction. As input, we classify the nodes into three classes (rules, black events and white events) and associate them with three dimension one-hot tensors. Besides, we add one more dimension for event nodes, which records their amounts. Eq. 6 becomes:
n = SAGEConv, (Ir, Ie), n, SAGEConv2(4e:
(10)
ge = Attooll (na), g. AuPool2(n,)
13

---

Under review as a conference paper at ICLR 2022
D FORMULAS AND PROOFS
D.1 FC NP-COMPLE PROVEMENT
For the sake of our proof, here we redefine FRAUD-COVERAGE and give the definition of an existing NPC problem: SET-COVER.
Given set of rules R along with an event set consisted of white and black events W B. Rules are corresponding to certain events (white (r)) or black B(r)) which have their amounts w(e). Does there exist collection of these rules to cover 2 M fraudulent monetary value while influence no more than white events?
FRAUD-COVERAGE.
SET-COVER. Given set U of elements, collection S2...... Sm of subsets of U, and an integer k, does there exist a collection of < k of these sets whose union equal to U?
First, we need to show that FC is NP. Given set of selected rules R {ri, ....... I'm J. could simply traverse the set, recording the covered black and white events. Then, we can assume whether the covered black events number is more than & and fraudulent monetary value is no less than
Since the certification process could be done in O(n)), we could tell that FC is NP. Then, for NP- hardness, we could get reduced from CCT-COVER.
Suppose we have a SET-COVER instance, we construct an equivalent FC problem as follows:
Create [ black events, each with amount 1.
Create rules, set (rrx) S
Connect each rule a different white event of amount
Set the white events threshold kw equal to the set number threshold kg-
Set fraudulent monetary target m = |U
Suppose find of rules which meet the conditions of FC, then select subsets S; iff
select r;- The total number of rules (subsets) is no more than (k,) since the influenced white events number is equal to RR. The subsets also cover U since the covered white event money (each with amount I) is no less than (U] Similarly, we can prove that we can find suitable rule set for FC if we have found a of subsets that meet the conditions of SET-COVERAGE So we can induce that SET-COVER Sp
Thus, we prove that FC NP-Complete.
D.2 FC ILP FORMULATION
As discussed in the main text, B denotes the set of black events, W represents the set of white events, R refers to the rule set and & denotes the event set. Using notations above, we could translate Eq. 9 into standard ILP form as follows:
max
Σ Y
s.t.
Σ ΣY < K EW
NE
[R|
(1I)
for i = 1.......... [8), (Y - 0.5)
Σ
Xb x I(i in E(J) 0
where X[i]] E {0, 1} denotes whether rule j is chosen or not, Y| E {0, 1} shows whether event i has been covered by the chosen rules. Besides, Wi]] E R records the amount of the events while E[i] C E is the corresponding events of rule j. The third equation ensures the event binary to be 1 iff it has been covered by the rule set (if =X
1 and event i Elj,, then the formula in the second bracket negative, ensuring Y[i] to be I; else if event is not covered by any chosen rules, then the second formula is positive and Y[i) must be 0).
14

---

Under review as a conference paper at ICLR 2022
E FRAUD COVERAGE DATASET
The Fraud Coverage dataset is generated according to the real data. We normalize the amount of each event to [0, 1]. Fig. 7 shows the distribution of the amount larger than 0.1 of a rule 100-evett 1OK instance. Most events small transactions and show a long-tail distribution format while fraud events tend to obey the long-tail distribution and are close to the uniform distribution when the amounts are larger than 0.1. Fraudsters often tend to cheating larger amounts and disregarding the small transactions may account for this phenomenon. Fig. 8 shows fraudulent monetary value cover- age of different strategies. It follows the real condition that few well-designed rules can cover most fraud events. The other rules can be regarded as complementary to the main rules. Different rules do not show some obvious patterns on the distributed number of events. For example, the fraudulent monetary value detected is not linearly related to the distributed events. Different rules may also cover the same fraud events and normal events, which makes the problem complex (Appendix D.I). That's why need to select suitable rule set.
1-3
350
Fraud events
3-4.5
4.56
300
8.0%
6+
ovents
250
1..%%
200
150
100
33.0%
0
0.2
0.4
0.6
0.8
1.0
Fraudulent monetory
Figure 7: FC dataset fraudulent monetory value Figure The distribution of fraudulent mone- tary value covered by different rules. The pair means the rules can detect amount in range [xr v/.
distribution of a 100-10K instance.
F ADDITIONAL EXPERIMENT RESULTS
F.1 TABLES
As discussed in Sec. 4.3, we propose 2 attack methods towards the FC solvers. The experiment results 'adding black edges' are shown in the main text. And the results of the W2B attack method are shown in Table 9.
Table 9; FC Node attack results of Ratio (%), Baseline is the average original solution of the
solvers on test set. We use RL as our attack method and the ratio here the mean ratios on all test instances computed by the solved FC monetary value w.r.t. baselines.
Rule#- Eventt# (Baseline, Ratio)
Solver
30-3K
60-6K
100-10K
Local Search
9.5713, 0.54%
24.9913, 1.15%
22,9359, 0.75%
Greedy Average
18.0038, 0.11%
43.1 0.27%
51,3905, 0.18%
Gurobi
18.8934, 41 .47%
41,1828, 78.59%
49.3296, 69.84%
F.2 FIGURES
Fig. 9 and 10 summarize the attack and defense results of TSP and FC experiments.
15

---

Under review as a conference paper at ICLR 2022
3.00
Mode
Mode
Normal Attack Defense
2.75
Attack
2,50
2.25
trouds
40
2.00
35
1.75
MoANet
NN
Furthest
Local
Gurobi
GA
Figure 9: Box diagram for TSP attack and de- Figure 10: Box diagram for FC attack and de- fense results. We run experiments on 20 testing fense results. We run experiments on 20 testing instances which traverse 50 cities from 'tmat'. instances that contain 60 rules and 6000 events. Three solvers are chosen as our targets and their Three solvers are chosen as our targets and their solution distance are shown in the figure.
solution fraudS are shown in the figure.
G EXPERIMENT PARAMETERS
Reinforcement learning model settings. Table 10 records the parameters for RL during the training process. Trust region clip factor is parameter in PPO agent to avoid model collapse. We also adopt some common
training tricks like reward normalization and entropy regularization
during training processes.
Table 10: RL parameter configuration in tasks GED, ATSP and FC
Parameters
DAG
ATSP
FC
Actions#
20
20
10
Reward discount factor
0.95
0.95
0.95
Trust region clip factor
0.1
0.1
0.1
GNN type
GCN
GCN
SAGEConv
GNN layers#
Learning rate
le-4
1e-3
1e-3
Node feature dimensions#
20
16
Attackers evaluation setting. For fair comparison of different attackers Random, OG-search, SA and RI, we set the parameters to ensure similar evaluation time. According to the time complexity discuss in Table 2, we specify the following parameters: number of iterations N, beam search size B and number of different actions M in each iteration.
DAG Random N 30; OG-search B M SA N 5, M 6; RL B 3, M 9;
TSP Random N = 130; OG-search = 5, M = 25; SA N = 13, M = 10; RL B = 5, M 25;
FC: Random N 220; OG-search B M 36; SA N 22, M 10; RL B 6, M 36;
H EXPERIMENT ENVIRONMENTS.
DAG and TSP experiments are run GeForce RTX 2080Ti (11GB) and Intel(R) Core(TM) i7- 7820X CPU 3.60GHz. FC experiments are run on GeForce RTX 3090 (20GB) and AMD Ryzen Threadripper 3970X 32-Core Processor. Our environment configurations are as follows:
Ubuntu 20.04
CUDA 11.2
Pyhton 3.7
Pytorch 1.9.0
Pytorch Geometrie 1.7.2
16


Reviews:
[{"review_id": "sXuG8Sj1jLg", "reviewer": "Reviewer_SYfi", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper studies adversarial attacks and defenses against algorithms for combinatorial optimization problems. The authors frame the problem, introduce RL-based algorithms for attack and defense, and present computational experiments.\n", "summary_of_the_paper": "I will give the authors credit for introducing a novel problem to study, but they do not do a sufficient job motivating why the problem is an interesting or important one. At a high level I can buy the story they are trying to tell, but this really needs to be tied closely with a compelling (and, ideally, well studied) application  area. Without this, the claim in the introduction that \"it is imperative to develop defense mechanisms\" are unjustified. It is not clear to me that scheduling or TSP are problems where you would typically encounter adversarial inputs, and if the authors have concrete cases to illustrate this, please highlight them. If Fraud Coverage is a well-studied or established problem, provide citations to this effect.\n\nBeyond the motivation of the problem itself, it is also not clear to me why the attack model studied in the paper is the \"right\" one. The authors should spend more time making a convincing case why their model is a plausible one. Again, this justification will need to be tied with a (compelling) application.\n\nOther comments:\n* p2: \"Combnaotorial\"\n* The formalism for combinatorial optimization presented on page 3 is unlike any I have seen before. How should we understand what the x variables correspond to: binary indicators on e.g. edges? If so, where are the explicit binary constraints? It is also not clear to me what it means for the constraints to be \"usually encoded in graphs\".\n* What does it mean to \"loosen part of the constraint h_i\"? Please introduce more formality about what h_i are, what loosen means, etc. \n* I find it interesting that the FC attack against Gurobi essentially seems to find ways to make the problems extremely difficult to solve, as opposed to degrading the solution quality (though that may also occur). I wonder if the authors can gain any insight into what the attack is doing here.", "summary_of_the_review": "The authors did not do a sufficient job motivating why the problem or model were interesting or important.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "ocU7ZHxW0n", "reviewer": "Reviewer_pi8H", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "$\\textbf{Strengths}$\n-\tEnhancing the robustness of combinatorial optimization solver is an interesting and timely problem.\n-\tUnder the proposed scheme, the presented attack and defense methods are reasonable. \n\n$\\textbf{Weaknesses}$\n-\tThe main weakness is that the considered attack-defense scheme seems to be problematic. From the very beginning, I am confused about the definition of an attack. In my opinion, an attack on the CO-solver should try to prevent the CO-solver from producing a high-quality solution to the *original input* (but not the perturbed input). But the proposed attack method aims to maximize $f(S(Q^{‘}|G^{‘}))$ rather than $f(S(Q^{‘}|G))$. \n-\tSimilarly, the effect of the defense should be measured by the quality of the solution to the original input, which is however unknown to the defender because it has been perturbed by the attacker. In such a sense, if the defender knows the attacker’s strategy, they can mitigate the attack by identifying the removed edge; otherwise, unless an input distribution is known, there seems no meaningful defense method. \n-\tAssuming the proposed attack-defense scheme is reasonable, the proposed reinforcement methods are reasonable but do not contribute new techniques.\n-\tIn experiments, maybe I missed something, but I did not see the setting of the number (K) of edges that are allowed to be changed; to me, experimenting with different K is necessary. In addition, only three fixed graphs are considered for DAG scheduling, and for demonstrating its statistical significance, it is better to experiment with a collection of random instances and examine the average performance. \n\nIt would be better if the paper could elaborate on the following questions:\n- Why strong nonlinearity and NP-hardness can cause the vulnerability defined in this paper?\n- What does it mean by saying that the parameters are universal?\n- From the attacker’s standpoint, what is the purpose of setting $f(Q^{‘})\\geq f^*(Q)$? I do not see that such a setting can result in a better attack. \n- Relaxing the candidate space does not necessarily mean that the solver should perform better, because the performance is measured with respect to the optimal solution which can have a better objective value in the relaxed space. For example, if we relax the metric space to general space, some problems can exhibit stronger approximation hardness. \n\n", "summary_of_the_paper": "This paper presents a framework of adversarial attack and defense for solvers to combinatorial optimization problems. In particular, the attacker can modify the problem instance by removing graph edges, while the defense side seeks to add edges to mitigate the attacking effect. The paper presents attack methods based on reinforcement learning and heuristic methods, and proposes a defense method based on reinforcement learning. Experimental studies are provided on three combinatorial problems.", "summary_of_the_review": "This paper considers an interesting problem, but the adopted settings need better justifications, and the proposed methods are unfortunately not novel. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": "Iasr8sgc2w", "reviewer": "Reviewer_CZdE", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Concerns:\n- The defined *robustness*, *adversarial attack* and *defense* in this paper are not reasonable. The paper considers the differences between $f(S(Q^\\prime)|G^\\prime)$ and $f(S(Q)|G)$ as the robustness of a solver, which makes little sense. It is common that a small perturbation in the graph can make the optimal result of a CO problem change a lot, but this is an intrinsic property of CO problem, and is unrelated to the *robustness* of a solver. A reasonable definition of *robustness* can be $-(f(S(Q)|G)-f^*)$, where $f^*$ is the ground truth optimal value. Then the attack is to find some $G$ that makes some solvers find sub-optimal solutions that are far from the ground truth optimum.\n- For the *defense*, \n    - What does \"the defense RL agent can not only play a defensive role against the attacked problem instance, but can also help further improve the solution of normal instances\" mean? I think modifying the graph itself to get better results is unacceptable for CO tasks. After modification, the problem becomes a different problem, and the solution to it means little to the original problem.\n    - For Eq.4, how can the defender access the original graph $G$ to be part of its objective? If the original graph is accessible, then no other actions are meaningful as we should directly adopt the original graph.\n- The scope of the claims in this paper are too broad and should be narrowed down to specific tasks and solvers that the proposed ROCO can work on. For a trivial example, the shortest path finding problem is a combinatorial optimization problem with deterministic, optimal and efficient solver. The Bellman Ford method or Dijkstra method for it are deterministically robust and should not be able to be attacked in any ways.\n- The proposed solutions have limited novelty.\n\nMinor:\n- Should it be $f(S(Q^\\prime)|G^\\prime) -f(S(Q^\\prime| G))$ in Eq.4?", "summary_of_the_paper": "This paper studies the adversarial attacks and defenses problem of combinatorial optimization problems. The paper presents ROCO framework, to conduct attack and defense by maximizing/minimizing the difference between the calculated optimum values between the perturbed graph and the original graph. Both RL-based and heuristics-based solutions are proposed and implemented on three combinatorial optimization tasks.", "summary_of_the_review": "My main concern is about the problem setting. I think the definition of *robustness*, *adversarial attack* and *defense* about CO in this paper are unreasonable. By modifying the original graph in CO tasks, the problem becomes a different problem and the solution lose its meaning to the original problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HXP95yp7d-Q", "reviewer": "Reviewer_Pdsc", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "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": "Overall, I like the challenge that authors aim to tackle a lot. The problem is highly important and studying robustness of comb. opt. solvers is highly important. Moreover, the paper is easy follow (even though, the notation is rather confusing; see below).\n\nHowever, there are some major problems with the paper:\n\n1: The main problem is indeed the actual problem formulation of Eq. (2). This equation is not helpful in studying the robustness of the solvers. Note that the underlying graph G' (resp. Q') is different -- thus, also the objective function of the optimization problem when feeding in this new input *should likely change*. Put differently: Eq. (2) is merely identifying two problem instances G and G' which lead to different objective function values. It does not tell anything about the robustness of the solvers. \n \n[Side note: One might argue that the authors aim for small modifications to G and, thus, the objective function value should also change only slightly. However, in particular for NP-hard comb. opt. problems such assumption is not correct. Indeed, small changes in the input can lead to larger changes in the output. In this case, this is not an issue of the non-robustness of the solver but inherent to the problem setting.]\n\nGiven this, all follow up experiments and insights are, unfortunately, not helpful.\n\nIf we want to study robustness of the solvers, it would be more appropriate to analyze whether the prediction of the solver is correct when feeding in G -- but incorrect when feeding in G' (in whatever sense correctness is measured). In the current formulation, though, this is not captured at all.\n\n2: The definitions/notations are rather confusing: Q is used as a problem defined on a graph G. What exactly is Q? It seems to be fully determined by G (see Eq. 2). But why is the solver then operating on Q and not G? And what exactly does then the conditioning on G mean?\n\nMoreover, if Q is fully determined via G (resp Q' via G'), how does Eq. 4 make sense? Here the solver is applied on Q' but conditioned on G. How is this possible?\n\nFinally, in some cases f is operating on S(Q) -- at other places f is directly operating on Q, i.e. f(Q). I would appreciate to fix these notations.\n\n3: Experiments: As mentioned above, I am convinced that the current experiments are not helpful in investigating the robustness of solvers as claimed by the authors. \n\nBesides that, I found the attack to the TSP unclear. The authors state that they \"choose an edge and half its value\". However, in the model definition they only define edge addition and deletion. Either the authors should update their model description or perform a different kind of experiment.\n\n4: The paper strongly relates their motivation, model, and experiments to graph attacks/defenses. However, the related work on this is very weak. There is a huge literature on these topics which should be discussed more carefully. In particular, I was wondering, why a simple gradient -based attack (relaxing the discrete nature of the data) was not used as comparison.\n\n5: Regarding technical novelty: The authors are highly inspired by other graph based (RL) attacks. Thus, the novelty in this regard is limited as well.\n", "summary_of_the_paper": "The authors aim to study the robustness of combinatorial optimization solvers (in particular ones that are based on learning). They treat the task as a graph problem and perform attacks on the underlying graph structure. Additionally, they aim to propose a defense mechanism. Finally, experiments on three different tasks are performed.", "summary_of_the_review": "The paper aims to tackle an important problem. However, the introduced model definition (Eq. 2) is incorrect / not helpful in this regard. Thus, unfortunately, the conclusions drawn are very questionable. Moreover, notations, related work, and experiments needs improvements.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper aims at developing mechanisms for adversarial attack and defense towards combinatorial optimization solvers, where the solver is treated as a black-box function and the original problem’s underlying graph structure is attacked under a given budget. While the reviewers found the problem novel and interesting, they are not convinced by the problem formulation and the proposed solutions, as well as the experimental setup. Some of the points that the reviewers brought up during the discussion include: (i) the attack to the TSP does not follow the main paper's attack principle of adding and deleting edges, (ii), in general, it has not been explained why all these modification are really "relaxations", (iii) the notations are very confusing, and (iv) while authors' response on loosening the constraints makes sense, but the experiments (i.e., the TSP problem setting) in this work are not consistent with such clarification. Addressing the above points will significantly improve the manuscript.
Decision: Reject