Efficient and Robust Neural Combinatorial Optimization via Wasserstein-Based Coresets
Authors: Xu Wang
Fuyou Miao
Wenjie Liu
Yan Xiong
Venue: ICLR 2025 Poster (2025)
Keywords: Neural Combinatorial Optimization
Wasserstein-Based Metric
Coreset
Data compression
Primary area: learning on graphs and other geometries & topologies
TL;DR: We proposed an efficient framework for existing neural combinatorial optimization methods.

Abstract: Combinatorial optimization (CO) is a fundamental tool in many fields. 
Many neural combinatorial optimization (NCO) methods have been proposed to solve CO problems.
However, existing NCO methods typically require significant computational and storage resources, and face challenges in maintaining robustness to distribution shifts between training and test data.
To address these issues, we model CO instances into probability measures, and introduce Wasserstein-based metrics to quantify the difference between CO instances. 
We then leverage a popular data compression technique, \emph{coreset}, to construct a small-size proxy for the original large dataset.
However, the time complexity of constructing a coreset  is linearly dependent on the size of the dataset. Consequently, it becomes challenging when datasets are particularly large.
Further, we accelerate the coreset construction by adapting it to the merge-and-reduce framework, enabling parallel computing. Additionally, we prove that our coreset is a good representation in theory.
{Subsequently}, to speed up the training process for existing NCO methods, we propose an efficient training framework based on the coreset technique. We train the model on a small-size coreset rather than on the full dataset, and thus save substantial computational and storage resources. Inspired by hierarchical Gonzalez’s algorithm, our coreset method is designed to capture the diversity of the dataset, which consequently improves robustness to distribution shifts.
Finally, experimental results demonstrate that our training framework not only enhances robustness to distribution shifts but also achieves better performance with reduced resource requirements.

Published as a conference paper at ICLR 2025
EFFICIENT AND ROBUST NEURAL COMBINATORIAL OPTIMIZATION VIA WASSERSTEIN-BASER CORESETS
Xu Wang's & Fuyou Miao & Wenjie Liu' & Yan Xiong'
School of Computer Science and Technology. University of Science and Technology of China
Hefei National Laboratory, University of Science and Technology of China
wormšmail ustc.edu. en
mfy@ustc. edu. cn
1wj1217email wtt.e/mmmaa...e...em.mmmmmmaeeem wsw.sstcc.... edu.
yxiongeustc.edu
ABSTRACT
Combinatorial optimization (CO) is fundamental tool in many fields. Many neural combinatorial optimization (NCO) methods have been proposed solve CO problems. However, existing NCO methods typically require significant com- putational and storage resources, and face challenges in maintaining robustness to distribution shifts between training and test data. To address these issues, we model CO instances into probability measures, and introduce Wasserstein-bon based metrics quantify the difference between CO instances. We then leverage pop- ular data compression technique, coreset, to construct a small-size proxy for the original large dataset. However, the time complexity of constructing coreset is linearly dependent on the size of the dataset. Consequently, it becomes chal- lenging when datasets particularly large. Further, accelerate the coreset construction by adapting it to the merge-and-reduce framework, enabling parallel computing. Additionally, we prove that our coreset is good representation in the- ory. Subsequently, to speed the training process for existing NCO methods, we propose an efficient training framework based on the coreset technique. We train the model on small-size coreset rather than on the full dataset, and thus save substantial computational and storage resources. Inspired by hierarchical Gon- zalez's ' algorithm, our coreset method is designed to capture the diversity of the dataset, which consequently improves robustness to distribution shifts. Finally, experimental results demonstrate that our training framework not only enhances robustness to distribution shifts but also achieves better performance with reduced resource requirements.
INTRODUCTION
Combinatorial optimization (CO) a fundamental tool in many fields such as transportation (Con-
tardo et al. 2012 Veres & Moussa 2019), logistics (Laterre et al.) 2018) and manufacturing (Froger
et al. 2016 Dolgui et al. 2019; Liu et al. 2017). Numerous traditional exact (David Applegate
2006 Optimization 2020 or heuristic solvers (Croes 1958 Helsgaun 2017 Lamm et al.) 2016) have been designed by experts to solve these problems. However, the real-world CO problems are widespread and diverse, and may even undergo rapid changes over time. Moreover, even for fixed
CO problem, human experts may be hindered by limited domain knowledge and computational diffi- culty (many of these CO problems are NP-hard). As a result, in many situations, can be impractical to rely solely hand-craftee methods developed by experts.
To address these challenges, numerous Neural Combinatorial Optimization (NCO) methods have
been proposed, such constructive heuristics methods (Khalil et al. 2017 Kool et al. 20018 Kwon
et al.
2020 Hottung et al. 2020 Kim et al.] 2022] Joshi et al. 2019 Fu et al. 2021 Geisler
al.
2021:QQu al. [2022] Sun & Yang 2023
Luo al. [023]] Vinyals al. 2015 Bello al.
2016
Nazari et al. 2018 Deudon et al. 2018 Xin et al. 2020
2021 Kwon et al. 202 Kim
"Corresponding author.

---

Published as a conference paper at ICLR 2025
et al.
2021:
Cheng al., 2023]
Drakulic al., 2023) and improvement heuristics methods (Li
et al.
2018
d O Costa et al. 2020; Wu et al. [021; Chen & Tian 2019; Li et al. 2023]] Chen &
Tian
2019;
Hottung al. 2020 Joshi & Anand 2022 Joshi et al. 2019). These methods learn
heuristic solution strategies in a data-driven manner, thus dispensing with laborious manual design and expert knowledge; moreover, compared with traditional CO solvers, NCO methods benefit from accelerated inference speeds by utilizing modern GPU devices.
Despite their advantages, these methods often require large training datasets, which demands sub- stantial storage space and computational resources. Additionally, when training data and test data come from different distributions, enhancing the robustness distribution shift (Liang et al. 2023 Sun et al. (020) is also a challenge for existing NCO models. Therefore, training competitive model with limited resources while ensuring its robustness to distribution shifts an important and worthy problem to address.
To address these issues, we consider constructing good representation, coreser (Ros & Guillaume 2020), for the original huge dataset. Coreset is popular data compression technique, which can accelerate the training process by reducing dataset size while preserving the value. Roughly speak- ing, coreset is small-size proxy of the original dataset Q with respect to objective; the value of the objective evaluated on coresct can closely approximate the value evaluated on Q. Therefore, we can replace Q by coresct in the training phase, and thus save the storage space and computational resources significantly. Furthermore, our coreset method is inspired by hierarchical Gonzalez's 's al- gorithm (Gonzalez] 1985), and thus capture the diversity of the dataset. Consequently, benefiting from its diversity, the model based on our coreset method shows robustness to distribution shift.
The intuition behind our coreset technique can be likened preparing for exam. Training neural networks is similar to practicing exercises for an exam. While the number of available exercises (i.e., data) might be vast, we cannot be trained for all the exercises with limited time and energy (i.e.. storage and computational resources). Fortunately, the whole exercises are redundant; to get high score, doing all the exercises unnecessary, and we only need cover all categories of exercises. Based on the above intuitions, we need a small-size representation (i.e., coreset) for the whole exercises. To this end, three key steps are required: i) exploring a proper metric quantify the difference between CO instances; ii) constructing coreset for the original dataset; iii) designing an efficient training framework based on the coreset technique for existing NCO models.
Many CO problems, such as the Traveling Salesperson Problem (TSP) and Maximum Independent Set (MIS), can inherently induce a graph structure. By employing graph embedding techniques, we map these graph structures into set of points in Euclidean space. Thus, we model CO instances as probability measures (in section 3.1 Wasserstein distance is commonly used to quantify the difference between probability measures. However, solutions to CO problems such TSP remain invariant under rigid transformations such as translation, rotation, and reflection. In other words, a CO instance can generate multiple variants through these transformations; but they are inherently the same instance. Therefore, the distance between such instances should be zero. To capture this property, we introduce the Wasserstein distance under rigid transformations (RWD) to measure the difference between two CO instances.
Our contributions:
First, we model CO instances as probability measures, and introduce RWD to quantify the difference between two given CO instances.
Then, based on RWD, we design coreset algorithm to effectively compress data for train- ing acceleration; it saves substantial computational and storage resources. However, the time required to construct the coreset increases linearly with the size of the dataset, making it computationally expensive for extremely large datasets.
To further accelerate coreset construction, we adapt our coreset method to merge-and- reduce framework, enabling parallel computation. Moreover, we demonstrate that our coreset is a good representation theoretically.
Next, based our coreset method, we propose efficient training framework for acceler- ating the existing NCO training process. More specifically, we replace the original dataset with coreset to accelerate the training process; in the inference phase, test instances
2

---

Published as a conference paper at ICLR 2025
aligned along tree (i.e., T from Algorithm Dor before predicting their labels using the trained model.
The experimental results show that our training framework exhibits better performance and enhanced robustness distribution shifts.
1.1 OTHER RELATED WORKS
Here, we introduce several techniques that will be involved later.
Graph embedding technique represents the nodes and edges of graph in Euclidean space. The edge information is encoded within the Euclidean distances between points, reducing the need to handle complex graph structures directly, as point-to-point information suffices. Moreover, trans- forms the discrete graph into continuous Euclidean coordinates, which allows many techniques in Euclidean space to be used. Here are some widely used graph embedding methods. Laplacian Eigen- maps (Belkin & Niyogi, 2001) embed graph data into low-dimensional Euclidean space while preserving local neighborhood relationships. Multidimensional Scaling (MDS) (Borg Groenen 2007) focuses preserving pairwise distances between nodes in the graph. Isomap (Tenenbaum ct al. 2000) extends MDS by incorporating geodesic distances along the manifold, making it espe- cially useful for graphs with inherent nonlinear structures.
Hierarchical Gonzalez's algorithm (Murtagh & Contreras 2012) is a variant of Gonzalez's k- center algorithm for addressing hierarchical clustering problem. In this approach, clusters are recur- sively divided at different levels of granularity, yielding a tree structure for efficient querying. This algorithm prioritizes selecting
center points that are far apart from the previously chosen ones. This strategy leads to clusters well-spread across the data, effectively capturing the diversity of the dataset. This method is commonly used for summarizing large datasets. However, its time complex- ity exhibits a linear dependence on the size of the dataset, making it potentially time-consuming for extremely large datasets. To mitigate this issue, we integrate merge-and-reduue (Bentley & Saxe 1980 Har-Peled & Mazumdar 2004) technique to construct our coreset in Algorithm
PRELIMINARIES
Notations We define [m] := (1....,n} and denote the vector of ones by 1. The fz-norm is denoted by || Il. and |A| denotes the size of set A. Let R+ be the set of non-negative real numbers. Let (( be the probability measure space on Euclidean space Rd Matrices are denoted by bold capital letters, such C; Cúj is its element in the i-th row and j-th column. Similarly, we denote vectors by bold lowercase letters, such
(a1, .......,00... aT)² RR 0g is its i-th element.
Wasserstein distance (Peyré et al. 2017) is skilled at capturing the geometric structures of CO prob- lems, but it is sensitive to rigid transformations. To obtain the invariance property under rigid trans- formations, we consider the following conception: Wasserstein distance under rigid transformation (RWD).
Definition 2.1 (RWD). Let μ == Ei a222Y1 E byóy; E ((R)), where a, b E RT are their weight vectors and {ziheenn , (usbyet C Rd are their locations. Then, the Wasserstein distance under rigid transformation between y and is
1/2
W(
min PeIl(a.b),EEE()
Payla:: e(v,))1²
where I1(a, b) == {PER)) RAX P1 = p'1= is the coupling set, E(d) is the euclidean group Rdd, and Rdd +Rd is the rigid transformation.
Remark 2.2. i) If we fix as identity transformation, then RWD is degenerated as the Wasserstein distance; Wasserstein distance is a metric on P(Rd). ii) RWD is a specifically, (P(Rd), W) is metric space.
on P(R)); more
For simplicity, we do not distinguish between metric and semi-metric.
3

---

Published as a conference paper at ICLR 2025
Next, we formally define coreset technique. Let
i Q x O
+
R4,, (v,0) + E(p, 0)
(I)
be loss function, where A E θ is the model parameter and ja Q denotes CO instance. For any weighted set A C Q with weight function WA, we define ((A,0) 0) = EnEA W (()) E(1,, 0).
Definition 2.3 (Coreset). Let 0 measures with weight function wQ P((Rd) + I.... Let Znec with weight function ws is an e-coresel of Q ((S,0) E (1 e) ((,00) for all e
< and i be loss function. Let Q C P(R") be set of Sonegw@(rr wo(n) = Then, weighted set
Then, we introduce some basic properties that will used later. Doubling dimension (Chan et al, 2016) can describe the growth rate of the dataset with respect to some metric dist. Formally, the doubling dimension of metric space (Q, dist) is the smallest positive integer ddim such that ev- ery ball in (2, dist)) can be covered by 2ddim balls of half the radius. For example, the doubling dimension of the Euclidean space R is (dd).
The Lipschitz constant of function describes how fast it can change. The loss function is L- Lipschitz continuous with respect to dist on Q, if [e(,,, 0) Euu,, 0)1 < L. 2-dist(u,, u2) holds for all U1, U2 E Q,0 e
OUR METHODS
This section introduces our methods. Section 3.1
introduces RWD to quantify the difference between two CO instances. Section 3.2 constructs a small-size coreset for accelerating the training process. Section 3.3 accelerates coreset construction process by using merge-and-reduce framework; more- over, we theoretically demonstrate that our coreset is a good representation. Finally, in Section 3.4 we present our efficient framework for existing NCO methods.
3.1 METRICS FOR CO INSTANCES
Many CO problems can induce graph structures. We first extract the graph structure induced by the CO instance and represent by a graph metric space, where each point in this space reflects node- specific information, and edge relationships are captured through the corresponding shortest-pait metric. We then apply graph embedding techniques (in Section 1.1) to map this graph metric space into Euclidean space, aiming to preserve inter-point distances closely. In this embedding, each node in the original graph is represented as discrete point Euclidean space, and edge information encoded in Euclidean distances between these points. Ultimately, we represent the graph discrete set points in Euclidean space. Henceforth, we focus on the point set data in Euclidean space.
Given two CO instances, we represent the nodes of their corresponding graph structure as X {2r (Z)))))) Y jyj C Rd. Then, the CO instances modeled two probability measures = Ei= a.dze and v = == byógs (with ag = bj = 1 to represent equal node importance). Then, we can quantify the difference between and with metric RWD; that is, W(p, v/), where the ground distance between x E and y E Y is ||x yll as in Definition 2.1
Remark 3.1. i) By graph embedding technique, the nodes and edges of a graph structure are de- scribed by the locations and their ground distances in Euclidean space. ii) These CO problems are usually invariant after imposing rigid transformations on their nodes, and RWD can capture this characteristic well. In essence, the complexity of data space reduced under RWD metric. More specifically, we regard two CO instances as the same instance if their distance is zero. iii) The com- plete graph in Rd can be represented directly by a point set, without the need for gruph embedding techniques. iv) If we fixed the outer iteration number and the dimension d of data space constants, our RWD can be solved within (nn)) time by using the heuristic method in Algorithm
3.2 CORESET
Intuitively, our coreset aims to cover all the data by using relatively fewer and smaller balls, where all the balls have the same radius. This strategy be likened to preparing for an exam, where
4

---

Published as a conference paper at ICLR 2025
need to cover many categories of exercises possible with limited time and energy. For simplicity, we take RWD as an example to illustrate our methods. The metric RWD can also be replaced by Wasserstein distance, some other proper metrics on P(B*).
Spout unde
buffery, for
conpect method
Q2
conoset method
01
@
Q3
@
Accelerate the coreset construc- The red dots denote probability measures in dataset tion by using merge-and-reduce framework. O, and the solid red dot is the center of the ball r.ball.
Figure I: Grow nodes from root v with ddim 1. Figure 2:
Coreset construction Our algorithm is inspired by the hierarchical structure in (Ding et al. 2021 Krauthgamer Lee 2004 Har-Peled & Mendel 20055 Beygelzimer et al.) 2006). Given set of probability measures, we aim at clustering similar measures into small balls of radius r, and take the cluster centers to form our coreset. The coreset is finally reserved in the tree T shown in Figure
To construct such coreset, we first initialize an empty tree T. and set its root node as Vg. The root node has only one attribute buffer, and is initialized as buffer = Q. Our (non-root) node has four attributes: cluster, center, buffer and ball as shown in Figure [ The nodes grow in up-bottom manner recursively. Given a current node v, if r.buffer is an empty set, then stop adding children to it. If v. o.buffer is nonempty set, we add A min (/v bufferr, 22-ddim children node [1r] jE(K] to the current node more specifically, we run Gonzalez's 's algorithm rounds on bufuffrr. By this, we obtain l cluster centers center and their corresponding clusters o/ cluster. All the uy cly.ttr form partition of v. o.buffer; each ./..uus consists of points that are relatively close to its center v² center. For each set vn cluuttrrr, we partition into two sets v/ ball, vy buffer, where b/lball a RWD-based ball of radius r centered at measure vy center; formally, we can formulate them
a leaf node, and
of ball = {u E cluster W(a, u/ center) sr}
(3)
and
tyy.buffer = v/g cluster ball.
(4)
Finally, we obtain a tree T. The coreset S consists of all the center points u.center with weight |u.ball]. We show the coreset construction process in a more intuitive and comprehensible manner in Figure I The detailed descriptions are Algorithm
Time complexity and coreset size From (Ding et al.
2021) we know that the radius of the clusters will be halved after carrying out at most 22-d0mm rounds of Gonzalez's algorithm. Let R be the radius of dataset Q: that is, W(H, v) & 2R for any μr,
Q. Thus, the height of the tree in Algorithm i is at most Ollog ()) Let T(n) be the time for computing the distance (i.e., RWD) between two measures, where n is the size of the locations of measures. Since constructing every layer takes O(22-ddim) [Q] computations of RWD, the total time complexity for Algorithm [ is (222-ddim) [2] ((n) log Its time complexity increases linearly with the size of the dataset, making it computationally expensive for large datasets. The coreset is maintained in the tee T. The tree has ((22 daim ylog 3 nodes, thus the coreset size is O R
) dddim).
Remark 3.2. i) The output of Algorithm Algorithm@ooonnannn Containn a tree T and coreset S. The S is a representation of the original measure Q, which is used for speeding up the training process for existing NCO methods; while the tree T is prepared for aligning CO instances at the inference phase. ii) It is often not necessary to know the exact value of the doubling dimension in advance. Typically,
5

---

Published as a conference paper at ICLR 2025
Algorithm Algorithm for constructing coresets
Input: a set Q = (UttEENI C "PRI") of measures, doubling dimension ddim of @, radius
1: Initialize an empty tree T, and set its root node as t0:
2: Set bo.buuffr--- = Q:
b The root node ti only has an attribute buffer, and it not associated with any node.
3: Construct the nodes of T recursively follows: D is the current node.
4: if v. v.buffer is 0 then
5: The current node
leaf node, and stop adding children it;
6: else
7: Set k min w bufferr 2 22:ddim) and add k children node {tt} jE({] the current node es
8: Run Gonzalez's s algorithm & rounds v. bufffer. For each children node v/y, we set its attributions cluster, center, ball, buffer according to Equation (3) and Equation (4):
9: end if
10: Set S = [v.center is node of T} and set the weight as ws(n) |u.ball;;
Output:T,8
begin by experimenting with relatively small values, as demonstrated in our study where set the low doubling dimension as ddam = In practice, even if we cannot rigorously prove that the data satisfies low doubling dimension assumption, this generally does not impact the effectiveness of our experimental results. iii) All the v.ball consist of partition of Q.
3.3 ACCELERATE THE CORESET CONSTRUCTION PROCESS
In this subsection, we adapt our coreset method to merge-and-redeee framework (Bentley & Saxe, 1980 Har--Peled & Mazumdar 2004 Wang et al. (2021); ; by this, we offer technique to accelerate our coreset construction process by achieving parallel computing; moreover, can also be used to tackle streaming data.
Algorithm is a combination of our coreset method and the merge-and-reduce framework as shown 2-dddim), H = log; [ol and r' = म The height of the tree in in Figure We first set = O(( )
Figure is at most H, and it is generated in a bottom-up manner.
We perform reduce and merge procedures alternatively each epoch. More specifically, reduce means data compression; that is, we run Algorithm [ by taking (2), ddim, r') as input, and obtain the corresponding coreset Sh; merge means putting together the coresets Sh: that is, Q S After H epochs, we obtain the coreset @ and its corresponding tree T = TH+1.
Algorithm 2 Algorithm for accelerating the coreset construction process
Input: a set Q = {Hi)iE[N] C P(Rd) of measures, doubling dimension ddim of Q, radius
1: Set =0((()) (()))2 H = log O and r Qa Q:
πf
2: for h = 1, H do
3: reduce procedure
=
Partition ºh as Qh (mm,) O with O ((T) and my For every 2 we rum Algorithm by taking ( Q ddim, r') as input, and output (T,",S?):
4: merge procedure
5:
Qh+1 = Use(ma]S
6: end for
7: Set S = #11 and T = 1+,
Output:T,5
Time complexity Given that the input size of Algorithm is O()), and its output size is s. Then,
the tree induced by the merge-and-reduce framework has most H llog [ layers.

---

Published as a conference paper at ICLR 2025
Each layer of Algorithm performs multiple computations of Algorithm 1 in parallel. Hence, the time complexity of per layer O(22-dkimm. .7. .n)) log R. Consequently, the overall time complexity of Algorithm is ( T (n)) log B log = 1 which is independent on the dataset size.
Communication complexity Our coreset is subset of the original dataset, allowing to transmit only the indexes of the CO instance items rather than the data items themselves. This significantly reduces transmission costs. As result, the additional transfer complexity introduced by our merge- and-reduce framework in Algorithm 2 is, in practice, minimal and unlikely to pose a substantial overhead.
Moreover, the coreset size of Algorithm 2 remains consistent with that in Algorithm | to retain only the tree structure of the final layer in practice.
it is sufficient
good representation Next, we show that the coreset S is a good representation of the original huge dataset Q in the following theorem.
Theorem 3.3. Assume is L-Lipschitz continuous on (Q. RWD) and there exists E R. such that ((2,)) 2 for all 8 E ②. Let ddim be the doubling dimension of with respect to RWD, and R be the radius of Q. Then, by setting r -.. both Algorithm | and Algorithm 2 can generate an O(( B)2 (-2dddmmm) size c-coreset S for the dataset Q: that is, for every 0, it holds that {(S,)) (1=))- (Q.
shows that for every parameter 0 E θ, the value of the loss function e evaluated on small-size coreset S can approximate the value the original dataset Q within O(c) relative error. Therefore, Theorem 3.3 demonstrates that our small-size coresct is a good representation for the original huge dataset Q with respect the objective l.
Proof. Due to limited space, we only give the proof sketch here. More details are in Appendix. First, we prove that by taking (2, ddim, as input, the coreset constructed by Algorithm [ can cover the dataset Q by small balls of radius r by using mathematical induction. Then, we obtain that the value difference of the loss function between the data itself and its representation small by Lipschitz continuous property. Third, by setting some parameters properly, we turn the additive error into a relative error and obtain an e-coreset S.
3.4 AN EFFICIENT FRAMEWORK
Here, we introduce an efficient framework to train a comparative model by using limited resources for existing NCO methods. We first feed the original dataset Q into Algorithm] or Algorithm [ and obtain the coreset S and tree T. The original dataset Q is replaced by small-size coreset S in the training phase. Thus, it saves the storage and computing resources significantly in the training phase. The probability measure /s in our coreset S has its own weight wis (1)), which helps it represent the original dataset well. However, to capture the diversity better, we usually regard these data as equally important; that is, to improve the robustness to distribution shifts in experiments, we set their weights as ws |
Training phase
Data compression
backward
by Algorithm
5
focuanl
Inference phase
T
Aliga test instances by Algorithm
Figure 3: An efficient framework for accelerating existing NCO methods. The Algorithm I can be replaced by Algorithm and Algorithm is in Appendix.
7

---

Published as a conference paper at ICLR 2025
Meanwhile, in the inference phase, first align the test instances along tree T, which aims to find a rigid transformation such that
min ((e(n), eVESS
(5)
where (:;-) the Wasserstein distance and e(n) Eiegn! agde(z.) for any v = y We offer a heuristic method (i.e., Algorithm 4 in Appendix) for the alignment as described Equa- tion (5). Thanks to the tree structure maintained by T. we can finish the alignment for test instance within ( log((S)) T())) time. This particularly efficient practice since k usually small. Without this tree structure, we would potentially need to align the test instance with every training data, which could significantly more conscmnn..
Remark 3.4. By combining our coreset technique in the training phase and the alignment process in the test phase, we essentially reduce the complexity of data. Intuitively, if the model can solve an instance well, then
solve similar instances well under metric RWD. Furthermore, our frame- work can be applied to other problems that inherently involve graph structure. This demonstrates its general applicability across various domains where graph-based analysis is pertinent.
Remark 3.5. i) Our coreset only needs be computed once, after which it can be used repeatedly to train different models and fine-tune parameters. ii) Even if the coreset computation time- consuming, it still valuable as helps save storage space. iii) Our alignment process serves as an optional enhancement to improve performance rather than mandatory step.
Table Comparison uniform sampling and our coreset method using TSP100-2D-V(0, 1) as the training dataset on test data TSP100-2D from different distributions.
Greedy
Greedy+2-opt
Sample size
Method
Test distribution
Length (1)
Time (4)
Length (4)
Time (1)
(o,, 1)
20.39
386
18.61
384
128000
Org
4
76.41
374
67.39
388
4(0, 10)
89.29
372
79.82
385
N)0,
22.34
378
18.92
387
US
490,49)
101.95
379
69.28
395
100,
119.78
380
82.59
395
1(0,1)
22.21
372
18.87
379
4003
CS
4"0,42)
80.63
372
67.92
379
4(0,10)
94.73
373
80.64
377
N
22.18
359
18.88
363
CS-aligned
N)0,49)
80.66
362
67.91
358
4(0,10)
94.94
361
80.53
360
N)0,1)
22.12
377
18.87
388
US
N00,49)
83.17
377
68.13
378
4(0,10)
97.31
377
80.80
387
1)
21.79
366
18.84
383
8245
CS
N30,49)
78.72
372
67.79
378
4(0,10)
92.99
374
80.35
377
I(0,
21.80
360
18,86
359
CS-aligned
N20,42)
78.50
361
67.82
358
4(0,10)
93,04
355
80.42
361
110,1)
21.99
390
18.87
377
US
N"),49)
80.78
384
67.94
379
400,
95.01
369
80.60
379
1)
21.57
372
18.81
382
12951
CS
77.80
369
67.58
379
4(00 10)
92.01
378
80.23
375
1)0.
21.50
361
18.79
358
CS-aligned
(0,44
77.67
362
67.57
357
10,
92.01
358
80.21
359
8

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTS WITH TSP
We take TSPI00 as an example to show the advantages of our coreset method. All experiments are conducted on an NVIDIA 1,20 GPU. Due to limited space, further experiments (including TSP training on uniformly sampled data (Kool et al. 2018), the MIS problem (Ahn et al. 2020)) and Capacitated Vehicle Routing Problem (CVRP) (Nazari et al. 2018) are presented in the Appendix
Table Comparison uniform sampling and our coresct method using TSP100-2D-W 1) as the training dataset test data of varying sizes. We fix the sample size 12951.
Greedy
Greedy+2-opt
TSP size
Method
Test distribution
Length (4)
Time (J)
Length (L)
Time (L)
N(0, 1)
33.69
109
27.14
112
US
(2)
125.99
108
96.70
112
U(0,10)
145.41
109
113.39
112
N(0,1)
30.75
107
26.69
110
TSP200
CS
49)
110.48
109
94.84
111
10),10)
129.77
107
111.47
109
1(0,
30.77
77
26.68
79
CS-aligned
N)),49)
110.99
78
94.59
79
100,
129.28
76
111.49
78
N(0,
59.81
1012
43.41
1020
US
N(0,49)
237.72
1012
154.28
1022
4(0,
263.66
1015
180.75
1022
N(0,1)
49.11
1012
42.25
1016
TSP500
CS
N(0,49)
178.56
1010
149.50
1016
400,
208.36
1011
174.93
1016
N(0,
49.38
680
42.26
683
CS-aligned
N)
178.88
679
149.63
682
400,10)
208.77
678
175.03
682
N(0,1)
94.71
2823
61.72
2848
US
N(0,49)
382.77
4224
219.16
2847
100,
426.61
4215
255.95
4254
N(O,1)
69.76
2823
59.59
2833
TSP1000
CS
NO0,49
252.92
4224
210.71
2832
4(0,
299.80
4215
246.57
4234
N(0,1)
69.96
2825
59.57
2832
CS-aligned
N(0.4
253.63
2821
210.81
2830
400,
300.03
2812
246.61
2827
Dataset We apply our method on TSP100-2D/3D Euclidean instances. The labels of TSP100-2D instances obtained by using the LKH-3 heuristic solver (Helsgaun) 2017); each coordinate of the nodes in a TSP instance generated by 10, where x is randomly sampled either from a normal distribution NiO, o²) or uniform sampling (0, 10). Our training data, TSPI00-2D-N(O., 1) and TSP100-3D-N((0, 1), consists of 125,000 instances generated by the normal distribution AN 1) and 3000 instances by the uniform distribution 4(0, 10). Indeed, the distribution of the training dataset is very close to the normal distribution (O. Hence, we regard the test data sampled from distribution (00, 1) as having no distribution shift. The test data are sampled from a single distribution, either a normal distribution uniform distribution. Specifically, we sample 1280 test data items for TSP100, and 128 test data items for other cases. Obviously, uniform distribution has the highest entropy and thus the highest diversity. For these Gaussian distributions, the larger the variance, the larger the diversity.
As for the TSP100-3D dataset, we can directly extend the 2D instances to 3D instances by appending a third coordinate with value of zero. Let X {av (arhen) C R are the nodes an instance. We apply random rotation transformation on X; that is, e(X) = {e(xx))een
"ode he found Corese12025

---

Published as a conference paper at ICLR 2025
NCO solver. The detailed parameter settings are in Appendix. To quantify the performance of different methods, we use two criteria: the average tour length (Length) and the total runtime (Time). The term "Greedy" refers to the greedy decoding method of DIFUSCO, and "2-opt" is a post-processing used to improve solutions. The terms US,CS and CS-aligned represent uniform sampling, coreset without alignment, and our coreset with alignment, respectively. We take the model trained on the full dataset with 128000 data items baseline.
Setting We use the DIFUSCO (Sun & Yang 2023)
Table Comparison uniform sampling and our coresct method using TSP100 1-P10000D-W(... as the training dataset test data TSPLIB RRinelt [ 1991).
Greedy
Greedy+2-opt
Sample size
Method
Test distribution
Length (4)
Time (L)
Length (4)
Time (4)
128000
Org
N
129.35
108
112.23
106
US
N(0,
190.79
109
115.87
108
4003
CS
N(
153.08
107
113.56
108
CS-aligned
1(
152.70
103
113.71
105
US
N(0,1)
166,40
106
114.47
108
8245
CS
N(0,1)
140.49
107
113.04
106
CS-aligned
N(0,
140.18
104
112.91
104
US
N(O,1)
162.19
107
114.31
107
12951
CS
1)0,
133.63
106
112.45
105
CS- -lignigeed
1)
133.14
103
112.52
110
Results of TSP100-2D Tables [ to present the results on training dataset TSPI00-2D-NT 1).
The training datasets are generated by the uniform sampling and our coreset technique respectively. The results show that both our method and uniform sampling method perform better as the sample size increases. Meanwhile, the sample size decreases, the advantage of our methods compared to uniform sampling becomes increasingly evident.
Moreover, Tables 1 and demonstrate that method is robust distribution shift. Specifically, the training data is sampied from a normal distribution. (O0, 1), while the test data are sampled from normal distributions N (o, 1). (0, 42) and uniform distribution (1 10). The test distributions NO0, 42) and (0,0 10) are sigmificantly different from the training distribution (00 1), which rep- resent substantial distribution shifts. The results Tables and show that our method consistently outperforms the baselines, demonstrating its robustness to distri shifts.
Furthermore, Table 2 shows that models trained on our coreset can generalize better to larger prob- lem sizes such as TSP2000 TSP500 and TSP1000. Moreover, Table 3 confirms that our method outperforms other approaches on the TSPLIB dataset.
Results of TSP100-3D Tables to 10 show the results training dataset TSPI00-3D-NV0. 1). For the test data without distribution shift (i.e., (0,, 1)), our method has comparable performance; for the test data occurring distribution shift (i.e., (000, 42) and U(0, 10)), method has better performance. Moreover, our coresct with alignment version performs better in the TSP-3D case. From Tables
and 10 alignment can perform better for higher dimension dataset (i.c., TSP- 3D). Thus, the alignment version promising for tackling high-dimensional data. (The details are in Appendix.)
CONCLUSION AND FUTURE WORK
In this paper, we introduce an efficient training framework for NCO problems based on our coreset method. More specifically, we replace the original huge dataset with our coreset during the training phase. In the test phase, we first align the test instances with the data in our coreset, and then feed them into existing NCO models. Our framework enables the development of comparable models with limited computational and storage resources: additionally, it exhibits robustness distribution shifts. Moreover, in future work, we will extend our method to other situations that can induce graph structures.
10

---

Published as a conference paper at ICLR 2025
6 ACKNOWLEDGEMENT
I would like to express my sincere gratitude to ChatGPT for assisting in refining the language and clarity of this paper. am also deeply grateful for the support from Innovation Program for Quan- tum Science and Technology (202 200IID0302902)) Hi-tech project(231-08-01 and Anhui Province University Natural Science Research Project (0033HH55110))
REFERENCES
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Learning what defer for maximum independent sets. In International Conference on Machine Learning, pp. 134-144. PMLR, 2020.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, 14, 2001.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint
2016.
Jon Louis Bentley and James B Saxe. Decomposable searching problems i. static-to-dynamic trans- formation. Journal of Algorithms, 1(4):301-358, 1980.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Pro- ceedings of the 23rd international conference on Machine learning, pp. 97-104, 2006.
Ingwer Borg and Patrick JF Groenen. Modern multidimeenionaa scaling: Theory and applications.
Springer Science & Business Media, 2007.
Vladimir Braverman, Vincent Cohen-Addad, H-C Shaofeng Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for core- sets. In 2022 IEEE 63rd Anmual Symposium on Foundations of Computer Science (FOCS), pp- 462-473. IEEE Computer Society, 2022.
T-H Hubert Chan, Anupam Gupta, Bruce M Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. ACM Transactions on Algorithms (TALG), 12(4):1-22, 2016.
Ke Chen. coresets for k-median and k-means clustering metric and euclidean spaces and their applications. SIAM Journal Computing, 39(3):923-995 924494799777 2009.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 32, 2019.
Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learn- ing to aolve large-scale tsp instances. In International Conference on Artificial Intelligence and Statistics, pp. 1219-1231. PMLR, 2023.
Claudio Contardo, Catherine Morency, and Louis-Martin Rousseau. Balancing dynamic public bike-sharing system, volume 4. Cirrelt Montreal, 2012.
Georges A Croes. method for solving traveling-salesman problems. Operations research, 6(6): 791-812, 1958.
Marco Cuturi. Sinkhorn distances: Lightspeed computation optimal transport. Advances in neural information processing systems, 26, 2013.
Paulo R d O Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian conference on machine learning, pp. 480. PMLR, 2020.
Vasek Chvátal William Cook David Applegate, Robert Bixby. Concorde tsp solver. https:// www. ma th. hww.chhwwweerrroo..caaa////ooooe
html, 2006.

---

Published as a conference paper at ICLR 2025
Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Marke Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming. Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delfi, The Netherlands, June 26-29, 2018, Proceedings 15, pp. 170-181. Springer, 2018.
Hu Ding, Tan Chen, Fan Yang, and Mingyue Wang. A data-dependent algorithm for querying earth mover's ' distance with low doubling dimensions. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 630-638. SIAM, 2021.
Alexandre Dolgui, Dmitry Ivanov, Suresh P Sethi, and Boris Sokolov. Scheduling in production, supply chain and industry 4.0 systems by optimal control: fundamentals, state-of-the-an and applications. International journal of production reseurch, 57(2):41 1--422, 2019.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Marc Andreoli. BQ-NCO:
Bisimulation quotienting for efficient neural combinatorial optimization. In Thirty-seventh Con-
ference on Neural Information Processing Systems, 2023. URL
Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent is better than by sinkhorn's 's algorithm. In Interna- tional conference machine learning, pp. 1367-1376. PMLR, 2018.
Paul Erd6s and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci, 5:17-61, 1960.
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 569-578, 2011.
Aurélien Froger, Michel Gendreau, Jorge E Mendoza, Éric Pinson, and Louis-Martin Rousseau. Maintenance scheduling in the electricity industry: A literature review. European Journal of Operational Research, 251()):695-766, 2016.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474-7482, 2021.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günnemann. Generalization of neural combinatorial solvers through the lens of adversarial robustness. In International Conference Learning Representations, 2021.
Teofilo F Gonzalez. Clustering minimize the maximum intercluster distance. Theoretical com- puter science, 38:293-306, 1985.
John C Gower and Garmt B Dijksterhuis. Procrustes problems, volume 30. OUP Oxford, 2004.
Sergey Guminov, Pavel Dvurechensky, and Alexander Gasnikov. On accelerated alternating mini- mization. 2020.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 291-300, 2004.
Sariel Har-Peled and Manor Mendel. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the twenty-firs annual symposium Computational geometry, pp. 150-158, 2005.
Keld Helsgaun. An extension of the lin-kernighan hn--kernighan-hhlggaun helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12, 2017.
André Hottung, Bhanu Bhandari. and Kevin Tiemeyy Learning latent search space for routing prob- lems using variational autoencoders. In International Conference on Learning Representations, 2020.
12

---

Published as a conference paper at ICLR 2025
Jiawei Huang, Ruomin Huang, Wenjie Liu, Nikolaos Freris, and Hu Ding. A novel sequential coreset method for gradient descent algorithms. In International Conference on Machine Learning, pp- 4412 4422. PMLR, 2021.
Lingxiao Huang, Shaofeng H-C Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering. In The Eleventh International Conference Learning Representations, 2022.
Arun Jambulapati, Aaron Sidford, and Kevin Tian. direct tilde (1)(p/epsiln)) iteration parallel algorithm for optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
Chaitanya K. Joshi and Rishabh Anand. Recent advances in deep learning for rout- ing problems. In ICLR Blog Track, 2022. URL https:://cci--booctttaa
wtt.:iii//22/////2 deep- hrrp://eree....oooooooooooooooor ing- ggithub. http://2222003255ereeeeeeeeeeene for rout
https://iclr-
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
Minsu Kim, Jinkyoo Park, et al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34: 10110011-14430 2021.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural com- binatorial optimization. Advances in Neural Information Processing Systems, 35:1936-1949, 2022.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
Robert Krauthgamer and James R Lee. Navigating nets: simple algorithms for proximity search. In SODA, volume 4, pp. 798-807, 2004.
Ycong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188-11988 2020.
Yeong- Kwon, Jinho Choo, I1joo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5144 2021.
Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 138-150 SIAM, 2016.
Laterre, Fu, MK Jabri, AS Cohen, D Kas, Hajjar, TS Dahl, A Kerkeni, and Beguir. Ranked reward: Enabling self-play reinforcement learning for combinatorial optimization. Advances in Neural Information Processing Systems 31 (NeurIPS 2018), 2018.
Yin Tat Lee and Aaron Sidford. Efficient inverse maintenance and faster algorithms for linear pro- gramming. In 2015 IEEE 56th annual symposium on foundations of computer science, pp. 230- 249. IEEE, 2015.
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances neural information processing systems, 31, 2018.
Jian Liang, Ran He, and Tieniu Tan. A comprchensive survey on test-time adaptation under distri- bution shifts. arXiv preprint arXiv:2303. 15361, 2023.
13

---

Published as a conference paper at ICLR 2025
Tianyi Lin, Nhat Ho, and Michael Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In International Conference on Machine Learning, pp. 00.3998899999 PMLR, 2019.
Ruiwu Liu, Xiaocen Li, and Kit S Lam. Combinatorial chemistry in drug discovery. Current opinion in chemical biology, 38:117-126 2017.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. SIAM Journal on Computing, (0::STOC19-269, 2022.
Fionn Murtagh and Pedro Contreras. Algorithms for hierarchical clustering: an overview. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(1):86-9)) 97, 2012.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
Gurobi Optimization. Gurobi optimizer reference manual. https://www/ hwtp:/twwww..b.o.ooooo.......... com/ 2020.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport. Center for Research in Eco- nomicy and Statistics Working Papers, (2017-86), 2017.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combina- torial optimization problems. Advances in Neural Information Processing Systems, 35:25531- 25546, 2022.
Gerhard Reinelt. Tsplib traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
Frédéric Ros and Serge Guillaume. Sampling techniques for supervised unsupervised tasks. Springer, 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-time train- ing with self-supervision for generalization under distribution shifts. In International conference on machine learning, pp. 9229-9248 PMLR, 2020.
Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based based diffusion solvers for combinatorial opti- mization. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023. URL net ftt
gVV
Joshua B Tenenbaum, Vin de Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction, science, 290(5500);2319 2323,, 2000.
Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. Advances in Neural Information Processing Systems, 33:997-1009, 2020.
Matthew Veres and Medhat Moussa. Deep learning for intelligent transportation systems: A survey of emerging trends. IEEE Transactions on Intelligent transportation systems, 21(3):315--3168, 2019.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in neural informa- fion processing systems, 28, 2015.
Zixiu Wang, Yiwen Guo, and Hu Ding. Robust and fully-dynamic coreset for continuous-and bounded learning (with outliers) problems. Advances Neural Information Processing Systems, 34:14319-14331, 2021.
14

---

Published as a conference paper at ICLR 2025
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problems. IEEE transactions on neural networks and learning systems, 33(9):5057-5069, 2021.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models for solving routing problems. IEEE Trunsactions on Industrial Informatics, 17()):861-48711 2020.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 12042- 12049, 2021.
15

---

Published as a conference paper at ICLR 2025
A OTHER PRELIMINARIES
Lemma A.1 (Generalized triangle inequaliiex((aaaryyeey et al. 2022 the following inequalities hold for any t t 1:
Given three points b, c,
dist (ais? 1 (1+t) dist (a. c) + (1 + dist (b, c):
(a,t? - dist (b, e $ t dist? (a, c) + & dist (a, b).
Definition A.2 (Wasserstein distance (Peyré et al. 2017 Let μ = = a.02,. V= byyn
P(RR), where a, E R4 are their weights and { a2 de(n) (yg}eetn C Rd are their locations. Given cost matrix C E R2x= with Cij =112 - vill" the Wasserstein distance between μ and is
1/2
W ((,
min PelI(a.b)
(P.C)
where II(a, b) (P R
P1 = a. 1 b} is the coupling set and is the vector of ones.
A.1
OTHER RELATED WORKS
NCO
The existing NCO methods can be categorized into two types: constructive heuristics (Khalil
et al.
2017 Kool et al. 2018 Kwon et al.
2020 Hottung et al. [0200] Kim et al.
2022 Joshi 2022]Joshi
al.
2019
Fu et al.] 2021 Geisler et al. 2021 Qiu et al.
2002]
Sun & Yang
2023
Luo et al.
2023
Vinyals a 2015 Bello et al. 2016 Nazari et al.
2018
Deudon al. 2018
Xin et al.
2020
2021 K Kwon et al. 2021 1 Kim et al. 2021 Cheng et al.
2023
Drakulic et al. 2023
and improvement
heuristics (Li et al. 2018|
O Costa al.] 2020; Wu et al.)
[021] Chen & Tian
2019
Li et al.,
2023 Chen & Tian 2019 Hottung et al. 2020 Joshi & Anand 2022] Joshi et al. 2019) methods;
the former can be further divided into two subtypes: autoregressive methods and -oo-autoreerrssivve
methods. The autoregressive methods grow partial solution to a complete solution incrementally, and the non-autoregressive methods directly predict a heatmap. The improvement heuristic methods often work by iteratively improving a feasible initial solution.
Coreset Coreset is popular data compression technique for clustering Chen 2009); Feldman &
Langberg (201T); Braverman al. (2022), regression Tukan al. (2020) and optimization Huang et al. (2022): : Wang et al. (202) D.. More relevant, Huang et al. Huang et al. (2021) proposed a sequen- tial coreset optimization problems with the Lipschitz smoothness property. Wang et al. (Wang learning (Shalev-Shwartz & Sen-David 2014). However, these methods cannot offer an efficient method for aligning CO in- stances with training data in the inference phase.
et al. 2021) designed a coreset method for
Optimal transportation (OT) Discrete Wasserstein distance is special case of OT, thus it can be computed by standard OT solvers. recent years, lot of algorithms have been proposed solve OT problem. For example, interior point method can compute e-aapproximation value for OT with ((x²)) time in practice (Peyré al. 2017 Ö(n2.5) in theory (Lee & Sidford 2015). To ob- tain an e L-aaproxxmmation solution of OT, Sinkhorn algorithm takes Onn² /E2 time Dvurechensky al. 2018 Lin et al. 2019) by solving the entropic regularization OT (Cuturi 2013); the accel-
erated version of Sinkhorn algorithm yields Ö(n time (Guminov et al. 2020 especially,
based on area-convexity and dual extrapolation, Jambulapati et al. (2019) achieved Onn /e4) time complexity.
B OTHER ALGORITHMS
Algorithm for computing RWD
We define two discrete probability measures
12
Σ 0:02.: Σ
bydy, P(RR)),
(6)
j=1
16

---

Published as a conference paper at ICLR 2025
where b E Ry are their weights and (Talve()) fuy IR their locations; 5 is the Dirac delta function. We denote the Wasserstein distance between a and by ((a, B).
The aim of Algorithm B is to find rigid transformation such that W(a, 3) = W(e o a, 9)- We initialize ā a. We solve W(a, 9) by updating the coupling and rigid transformation
alternatively. Specifically, we first obtain coupling P by computing W ( 9) according to the method in Jambulapati et al. 2019). Then, we fix P, and compute arg min, Wp(eoa,8)
We partition the rigid transformation e into translation transformation e and orthogonal trans- E2 61- The translation transformation can be updated as 6 E E Piyl/s -i= Eø=1 PiyTz. For fixed c1, P. computing the optimal orthogonal trans-
formation C2 that is,
formation 62 is an orthogonal Procrustes problem (Gower & Dijksterhuis 2004). More specifically, first obtain M Eis Pajaayy. and apply singular value decomposition M UDVT then,
have
= UV
Algorithm 3 Algorithm for RWD
Input:a, B
1: 0, ===a"
2: for < Talign do
3: t= t1;
4: >> update coupling P
Obtain coupling by computing W according the method in (Jambulapati et al.
2019):
5:
update translation transformation e₁ and orthogonal transformation 62
Compute é = >x= Σ/=1 PiyUy - > > 2j=1 Payat;
Compute E2 = UV according to Equation 7 and set = 62 61;
â Σi= (e0()))
6: end for Output:P,
Time complexity of Algorithm We compute the RWD by alternating between optimizing the coupling matrix and the rigid transformation, which is heuristic method. We assuming that the point dimension and the number of iterations Talign are constants. For computing the coupling matrix, we solve an OT problem within Ó(?)) time Jambulapati et al. 2019). The rigid transfor- mation obtained by solving an orthogonal Procrustes problem, which has time complexity of O nd d3). Thus, the overall complexity of this heuristic method remains Ö(n²).
Algorithm for alignment Here, introduce our alignment algorithm. We first initialize the current node v as the root node vo. Then, we walk from the root node to a leaf node by selecting the most similar measure with the test instance μ.
Algorithm 4 Algorithm for alignment
Input: the tree T, CO instance μ
1: 0p The current node initialized root node vo-
2: Initialize target by any measure in coreset S.
is the corresponding coreset maintained in tree
3: Select the child r' that is closest to under metric RWD.
4: Set v'.
5: if e' < W(u, target) then
6: target = v' center;
7: end if
8: If v is not a leaf, jump to Line
Output:largel
17

---

Published as a conference paper at ICLR 2025
V/
V1
V4
V5
Figure 4: The illustration for error.
C OMITED PROOFS
Proof of Theorem 3.3 The proof sketch listed here. First, we prove that by taking (2, ddim, r) as input, the coreset constructed by Algorithm 2 can cover the dataset Q by small balls of radius r by using mathematical induction. Then, we obtain that the value difference of the loss function between the data itself and its representation is small by Lipschitz continuous property. Third, by setting some parameters properly, we turn the additive error into a relative error, and obtain an e-coreset S.
Given probability measure y E Q, we assume that its corresponding ball center in the h-th epoch Vh-
Claim C.1. W vn) S 12. , H
Proof. The error is grown in manner illustrated in Figure Next, prove this claim by using mathematical induction.
Base Case: For the case h in the 1-st epoch, have W 21) S 2 37
Induction step: For the case h = m, in the m-th epoch, we assume that
W vm S m²
(8)
H
Then, according to the generalized triangle inequalities in Lemma A. we have
W (p, +1+ S (1 + (H, vm + (1 }) (² vm+1).
(9)
Since the radius of small ball in Figure is at most H7 we have (²(mm, vm+1) < the the induction hypothesis and setting t =
Hz. By using
2²
we have
2
22 (m 112
p2
W 1m- S (1 + m
m²
+ (1+m)
(10)
H2
H2
H2
Till now, prove the case h m
Let v = un the representation of in Algorithm (2, 2
According to Claim
C.I
we have
Next, since loss function is I--Lipschitz continuous with respect to RWD on Q, we have
(e(,,0) - ([1,00] S.. L.T.
(11)
((220) ((S,) <
Σ wo(n) (( e(v,0)) Σ wo(m) b.r b-r= (12)
HER
where S is the corresponding representation Q, and have wo(2)= = E, wo(w) according to Definition 2.1
18

---

Published as a conference paper at ICLR 2025
Finally, we have ((Q.0)
0) 2 % by setting 2. obtain the coreset property
|((2,) se ((((,0))
(13)
D FULL EXPERIMENTS WITH TSP
We take TSPI00 as an example show the advantages of our coreset method. All experiments are conducted on an NVIDIA L20 GPU. We take the NCO [Sn & Yang 2023) our backbone solver, and set its training epoch as 20.
Dataset We apply method TSP100-2D/3D Euclidean instances. The labels of TSP100-2D instances are obtained by using the LKH-3 heuristic solver (Helsgaun) (017]); each coordinate the nodes in a TSP instance generated by x% where æ is randomly sampled either from normal distribution (0, o²) or uniform sampling U(0, 10). Our training data, TSP100-2D-N 1) and ISPI00-3D-V(0, 1), consists of 125,000 instances generated by the normal distribution N/ and 3000 instances by the uniform distribution U(0, 10). While the training dataset TSP100-2D- u(, 10) consists of 128000 instances generated by uniform distribution (0, 10).
Indeed, the distributions of the training dataset SEP100-2D-NOO0 1) and TSP100-3D- 1) are very close to the normal distribution (0, 1). Hence, we regard the test data sampled from distri- bution (0,1 1) as having no distribution shift. The test data are sampled from single distribution, either a normal distribution or uniform distribution. Specifically, we sample 1280 test data for TSP100, and 128 test data for other cases. Obviously, the uniform distribution has the highest en- tropy and thus the highest diversity. For these Gaussian distributions, the larger the variance, the larger the diversity.
As for the TSP 100-3D dataset, we can directly extend the 2D instances to 3D instances by appending third coordinate with value of zero. Let X {aaheen) R the nodes of instance. We apply random rotation transformation on X; that is. e(X) == {e(z:))ve(or Intuitively, this TSP100-3D dataset has the same intrinsic complexity under metric RWD, which is the low doubling dimension in our assumption.
Table 4: Time statistics for different phases of training TSP100- 1).
Method
Sample size
Labeling time
Coreset Time Training Time
Total time
Org
128000
4709
28563
33272
4003
147
1894
2041
US
8245
304
2862
3166
12951
475
4014
4489
4003
145
691
1731
2567
CS
8245
305
1086
2747
4138
12951
474
1283
3751
5508
NCO solver. The model DIFUSCO with Greedy decoding solves TSP instances in an end-to-end manner. We set the learning rate 0.0002 and the batch size 64. The diffusion step performed 50 times in inference phase. We use the cosine schedule described in (Sun & Yang 2023). To quantify the performance of different methods, we use two criteria: the average tour length (Length) and the total runtime (Time). The term "Greedy" refers to the greedy decoding method of DIFUSCO, and "2-opt" is a post- processing used to improve solutions. The terms US,CS and CS-aligned represent uniform sampling, our coreset without alignment, and our coreset with alignment, respectively. We use the results on the full dataset with 128000 data baseline. In experiments, we first construct a coreset S, and then take [S] samples by uniform sampling as training datasets.
Setting We the DIFUSCO (Sun & Yang 2023
Results of TSP100-2D Tables 4 to present the results on training dataset TSP100-2D-N (0,1)). The training datasets are generated by the uniform sampling and coreset technique respectively.
19

---

Published as a conference paper at ICLR 2025
Table Comparison of uniform sampling and our coreset method using TSP100-2D-V(0..1) as
the training dataset on test data TSP100-2D from different distributions.
Greedy
Greedy+2-opt
Sample size
Method
Test distribution
Length (4)
Time (4)
Length (t)
Time (1)
1)
20.39
386
18.61
384
2
42.41
381
37.47
387
128000
Org
(20,42)
76.41
374
67.39
388
N(0,8²)
87.18
379
77.86
388
400
89.29
372
79.82
385
1(0,
22.34
378
18.92
387
2(0,
51.59
376
38.25
388
US
NO0,43)
101.95
379
69.28
395
(0),82)
118.83
379
80.38
402
400
119.78
380
82.59
395
1)0.1)
22.21
372
18.87
379
N
44.94
379
37.80
378
4003
CS
80.63
372
67.92
379
N1),82)
92.63
367
78.47
378
400,10)
94.73
373
80.64
377
22.18
359
18.88
363
2(0,2
45.00
357
37.80
362
CS-aligned
NO0,49)
80.66
362
67.91
358
N0)
92.59
362
78.41
358
4(0,10)
94.94
361
80.53
360
1
22.12
377
18.87
388
22
45.59
381
37.86
389
US
42),42)
83.17
377
68.13
378
N
95.16
380
78.81
385
4(0,10)
97.31
377
80.80
387
1
21.79
366
18.84
383
2)
43.72
373
37.73
378
8245
CS
N
78.72
372
67.79
378
(
90.44
371
78.36
380
410,10)
92.99
374
80.35
377
1)
21.80
360
18.86
359
22)
43.77
354
37.73
356
CS-aligned
420,42)
78.50
361
67.82
358
((0,8
90.54
350
78.32
359
400,10)
93.04
355
80.42
361
10,
21.99
390
18.87
377
20)
44.77
376
37.81
384
US
(3),42)
80.78
384
67.94
379
(2),82)
93.16
373
78.52
381
4100 10)
95.01
369
80.60
379
N
21.57
372
18.81
382
2
43.14
371
37.66
388
12951
CS
77.80
369
67.58
379
N(0,8²)
89.63
371
78.18
408
1(0,10)
92.01
378
80.23
375
1
21.50
361
18.79
358
2
43.18
361
37.66
364
CS-aligned
N(0.42)
77.67
362
67.57
357
82)
89.60
357
78.18
361
40,
92.01
358
80.21
359
20

---

Published as a conference paper at ICLR 2025
The results show that both method and uniform sampling method perform better the sample size increases. Meanwhile, as the sample size decreases, the advantage our methods compared to uniform sampling becomes increasingly evident.
Moreover, Tables and 6 demonstrate that our method is robust to distribution shift. Specifically, the training data is sampled from normal distribution (O, 1), while the test data is sampled from normal distributions (0, 1), (0, 42) and a uniform distribution 24(0, 10). The test distributions significantly different from the training distribution (00, 1), which rep- resent substantial distribution shifts. The results in Tables and and
(0, 4²) and (0, 10)
show that our method consistently outperforms the baselines, demonstrating its robustness distribution shifts.
Furthermore, Table shows that models trained on our coreset can generalize better to larger prob- lem sizes such as TSP200, TSP500 and TSPI000. Moreover, Table 7 confirms that our method outperforms other approaches on the TSPLIB dataset. Table shows the time efficiency of our coreset method.
Table 6: Comparison of uniform sampling and our coresct method using TSP 100-2D-N 1) as the training dataset on test data of varying sizes. We fix the sample size as 12951.
Greedy
Greedy+2-opt
TSP size
Method
Test distribution
Length (4)
Time (J)
Length (V)
Time (L)
(0,
29.85
107
26.61
111
22)
60.87
109
53.38
110
TSP-200
Org
4
109.70
110
94.90
111
(7)
123.39
110
108.41
110
4(0, 10)
126.99
107
111.50
111
N(0,
50.55
1012
42.38
1018
2(0,
102.65
1012
84.89
1018
TSP-500
Org
2
184.40
1012
150.47
1018
8))
204.53
1010
171.14
1014
410,
210.70
1012
175.41
1016
1)
77.15
2826
60.56
2840
2))
157.12
2826
121.45
2839
TSP-1000 Org
N2)
281.64
4224
214.55
2833
N(),8
310.94
4218
243.77
4242
(00
317.55
4218
249.28
4236
1)
33.69
109
27.14
112
2
69.77
109
54.28
112
US
N20
125.99
108
96.70
112
N(0,8²)
143.76
109
110.64
113
4(0,
145.41
109
113.39
112
1(0,1)
30.75
107
26.69
110
2)
62.08
109
53.36
112
TSP-200
CS
N(0,42)
110.48
109
94.84
111
N(0,82)
127.06
107
108.76
111
400.
129.77
107
111.47
109
1(0,1)
30.77
77
26.68
79
N(0.2
61.87
76
53.38
79
CS-aligned
N(0,42)
110.99
78
94.59
79
N(0,82)
126.69
76
108.42
79
4(0,
129.28
76
111.49
78
I)0,1)
59.81
1012
43.41
1020
126.00
1013
86.76
1022
US
N(0,42)
237.72
1012
154.28
1022
(0)
261.79
1013
176.13
1022
4(00 10)
263.66
1015
180.75
1022
Continued next page
TSP-500
21

---

Published as a conference paper at ICLR 2025
continued from previous page
Greedy
Greedy+2-opt
TSP size
Method
Test distribution
Length (4)
Time (4)
Length (V)
Time (L)
N(0,
49.11
1012
42.25
1016
(2)
99.58
1012
84.60
1019
CS
N))
178.56
1010
149.50
1016
N))
205.86
1012
170.54
1016
4(0,10)
208.36
1011
174.93
1016
1)
49.38
680
42.26
683
N(0,2
99.66
680
84.52
684
CS-aligned
N(
178.88
679
149.63
682
N(0,8²)
204.42
678
170.62
682
10)
208.77
678
175.03
682
1)
94.71
2823
61.72
2848
N00
199.22
2825
123,56
2849
US
N20,42)
382.77
4224
219.16
2847
N))
421.29
4218
249.08
4258
100
426.61
4215
255.95
4254
1
69.76
2823
59.59
2833
141.06
2825
119.64
2832
TSP-1000 CS
NO0,42)
252.92
4224
210.71
2832
N(0,8²)
293.49
4218
240.42
4236
100,
299.80
4215
246.57
4234
1(0,1)
69.96
2825
59.57
2832
2)
140.95
2822
119.39
2833
CS-aligned
N(0,42)
253.63
2821
210.81
2830
((0,82)
293.82
2815
240.11
2826
10)
300.03
2812
246.61
2827
Table 7: Comparison of uniform sampling and coreset method using TSPP100-DD-V((0.) as
the training dataset on test data TSPLIB (Riinel, 1991).
Greedy
Greedy+2-opt
Sample size
Method
Test distribution
Length (4)
Time (4)
Length (1)
Time (1)
128000
Org
N/0,
129.35
108
112.23
106
US
N10,
190.79
109
115.87
108
4003
CS
N(0,
153.08
107
113.56
108
CS-aligned
1)
152.70
103
113.71
105
US
NI0,1)
166.40
106
114.47
108
8245
CS
N(0.1)
140.49
107
113.04
106
CS aligned
N(0.1)
140.18
104
112.91
104
US
162.19
107
114.31
107
12951
CS
NIO,
133.63
106
112.45
105
CS-aligned
N(O,
133.14
103
112.52
110
Results of TSP100-3D-N(0.11 Tables 8 to 10 show the results of TSP100-3D-NV Table
illustrates the overall acceleration improvement. For the test data without distribution shift, method has comparable performance; for the test data occurring distribution shift, our method has better performance. Moreover, our coreset with alignment version performs better in the TSP-3D case. From Tables and I0] alignment can perform better for higher dimension dataset (i.c., TSP- 3D). Thus, the alignment version is promising for tackling nigh-dimennsioal data.
22

---

Published as a conference paper at ICLR 2025
Table
Time statistics for different phases of training on TSP100-3D-N 1).
Method
Sample size
Labeling time
Coreset Time
Training Time
Total time
Org
128000
4940
30671
35611
4103
160
2102
2262
US
7960
307
2729
3036
12058
466
3514
3980
4103
159
1012
2080
1379
CS
7960
309
1177
2712
4198
12058
463
1675
3493
5631
Table 10:
Comparison uniform sampling and our coreset method with
training dataset TSP 1551100-3D-NO00 test data of varying sizes. We fix the sample size as 12058.
Greedy
TSP size
Method
Test distribution
Alignment time (4)
Length (4)
Time (4)
(O 1)
30.02
77
(00,
61.03
76
TSP-200
Org
(2)
109.78
77
(2),82)
126.15
76
4(0,
128.35
77
1)
48.66
682
(
101.71
682
TSP-500
Org
(70,42)
184.94
682
(0)
210.36
680
4(0, 10)
212.62
683
1)0.1)
69.08
2828
2
144.10
2826
TSP-1000
Org
(00,43)
264.58
2824
82)
303.02
2821
u(0, 10)
313.23
2818
1)
32.30
76
22)
67.81
77
US
N(0,42)
130.76
77
N()
152.74
77
4(0,10)
153.90
77
100,
32.72
76
2(0,
66.08
76
TSP-200
CS
N(),4²)
120.64
78
N(0,82)
139.91
77
4(0,10)
142.84
77
1)0,1)
33.25
76
2(0,22)
69.79
75
CS-aligned
N(0,42)
118.44
77
N))
135.90
77
10
100,10)
138.27
76
12
I)
58,45
682
N((,22))
127.53
681
US
N((,
264.93
682
N((0,82)
316.73
681
4( 10)
318.39
680
(0,
59,69
682
Continued on next page
TSP-500 CS
23

---

Published as a conference paper at ICLR 2025
continued from previous page
Greedy
TSP size
Method
Test distribution
Length (4)
Time (4)
(0 22)
122.24
681
N(0,4*)
231.96
682
82),
266.08
677
4(0, 10)
268.75
680
N(0,1)
56.47
682
16
22)
121.33
681
19
CS-aligned
N(0,42)
205.45
682
N(0,82)
238.14
681
26
400,
245.01
681
30
(0,,1)
86.01
2828
2
191.39
2828
US
4²)
397.40
2825
8²)
470.55
2820
4(0,10)
550.11
2819
I)0,1)
86.37
2826
240,
181.84
2827
TSP-1000 CS
N))
342.64
2822
N)),8²)
395.66
2820
4(0,10)
441.82
2818
1(0,1)
86.87
2828
236
270,
186.88
2823
433
CS-aligned
N20,4
320.68
2825
624
())
372.34
2820
861
u(0, 10)
383.92
2819
980
Then, we take TSP-3D as an example to compare the performance of the random heuristic alignment method (CS-rand-ee aand-aligned) with our proposed alignment method (CS-al (CS-aligned).
As shown in Table I1 the results demonstrate that the CS-rand-aligned method performs similarly the unaligned approach, providing little improvement, In contrast, our alignment method signifi- cantly enhances performance, confirming its practical effectiveness.
Comparison of rand alignment ASSrran--aligned and our alignment (CS-aligned) method with training dataset TSP100-3D- (0, 1) on test data of varying sizes. We fix the sample size as 12058.
Table 11:
Greedy
TSP size
Method
Test distribution
Alignment time (J)
Length (L)
Time (L)
US
4(0, 10)
100.41
37
CS
4(0, 10)
95.27
36
TSP-100
CS-aligned
U(0, 10)
94.13
37
CS-rand-aligned
4(0, 10)
95.62
37
11
US
U(0, 10)
153.90
77
CS
27(0, 10)
142.84
TSP-200
CS-aligned
47(0, 10)
138.27
76
12
CS-rand-aligned
10)
144.84
17
US
U(0, 10)
318.39
680
CS
U(0, 10)
268.75
680
TSP-500
CS-aligned
4(00100
245.01
681
30
CS-rand-
44 10)
255.92
674
23
US
27(0. 10)
550.11
2819
CS
27(0, 10)
441.82
2826
TSP-1000
CS-aligned
10)
383.92
2818
980
Continued on next page
24

---

Published as a conference paper at ICLR 2025
continued from previous page
Greedy
TSP size
Method
Test distribution
Length (L) Time (L)
CS-rand-aligned
4(00 10)
429.90
2817
493
Results of TSP100-2D-((0,, 10) Tables 12 to 15 present the results training dataset TSP100- 2D-U((0, 10). The training datasets are generated by the uniform sampling and our coreset technique respectively. Table [2 clearly demonstrates the overall acceleration improvement. All the results show that both our method and uniform sampling method perform better as the sample size increases. For both the test data with distribution shift and without distribution shift, our method consistently shows better performance. Table [4 further illustrates that our method can generalize to large- scale TSP problems better. Table T5 confirms that our method outperforms other approaches on the TSPLIB dataset.
Results of TSPP0003D--2(00,000 10) 2D-U(0,, 10).
Tables 16 and 17
present the results on training dataset TSP100-
E FULL EXPERIMENTS WITH MIS
Dataset For Maximal Independent Set (MIS), we train our model on ER-[90-100] dataset (Erdós & Rényi 1960), where [Rn[n-N] means that the graph contains n to nodes. We set the connection probability as 0.15 as in (Sun & Yang 2023). The labels of our MIS datasets are obtained by using the KaMIS2 solver. Our training dataset of MIS consists of 128000 ER-[90-100) instances. We evaluate our method on ER-[90-100], [R-[400-500], ER-[900- 1000] and SATLIB.
Setting We use the DIFUSCO (Sun & Yang 2023) as our NCO solver. To quantify the perfor- mance of different methods, we use two criteria: the average size of the independent set (Size) and the total runtime (Time). The term "Greedy" refers to the greedy decoding method of DIFUSCO, and "Sampling"" the sampling decoding. The terms US and CS represent uniform sampling and our coreset method, respectively. We use the results on the full dataset with 128000 data as a baseline.
Results of MIS Tables 18
20 and 27 present the results on training dataset ER-[90- 190- The
training datasets are generated by the uniform sampling and our coresct technique respectively. Table 18 clearly demonstrates the overall acceleration improvement. All the results show that both method and uniform sampling method perform better the sample size increases. Table 27 demonstrates that our method can generalize to large-scale ER problems better. Table 20002200hhh show that the performance of our method and uniform sampling method is similar on SATLIB.
F FULL EXPERIMENTS WITH CVRP
In this section, we take CVRP100 example to show the advantages of our coreset method. All experiments of CVRP are conducted on NVIDIA GeForce RTX 3090 GPU. We take the NCO (Luo) al. 2023) as backbone solver, and set its training epoch as 20.
Dataset We apply our method on CVRP100 Euclidean instances. The labels of CVRP100 in- stances are obtained by using the LKH-3 heuristic solver (Helsgaun) (017);: each coordinate of the nodes in a CVRP instance is generated by x%1, where is randomly sampled either from a normal distribution (O, a2) or uniform sampling 2d 1). Our training data CVRP100-N 0.12) con- sists of 125,000 instances generated by the normal distribution (0 0.1²) and 3000 instances by the uniform distribution U( 1). While the training dataset CVRP100-Z((0,, 1) consists 128000 instances generated by uniform distribution (((
Indeed, the distributions of the training dataset CVRPI00-N 0.13) is very close to the normal distribution 0.13). Hence, regard the test data sampled from distribution (V 0.13) as having no distribution shift. The test data are sampled from a single distribution, either a normal distribution uniform distribution. Specifically, sample 1280 test data for CVRP100, and 128
25

---

Published as a conference paper at ICLR 2025
Table Comparison of uniform sampling and our coreset method using TSP100-3D-V(O.1U 1) as
the training dataset on test data TSP100-3D from different distributions.
Greedy
Sample size
Method
Test distribution
Alignment time (4)
Length (4)
Time (4)
1)
20.80
364
2%)
42.25
366
128000
Org
(20,42)
76.57
362
((0,8
88.45
360
10)
90.55
358
1(0,
24.92
480
(00
49.96
482
US
NO),49)
96.60
483
N(0,8
116.65
482
10)
119.78
481
1)
24.89
364
24)
50.46
384
4103
CS
42)
106.35
360
N)
109.12
360
100
111.63
353
N(0,1)
23.36
479
2
N(0.22)
47.00
480
CS-aligned
NV0,49)
91.94
479
7
NO0.83)
106.50
482
9
100,
108.81
483
11
1
23.62
477
2
48.32
477
US
N2),42)
92.92
484
())
111.98
479
100,10)
115.62
481
1)
23.41
362
2))
47.10
361
7960
CS
N20,42)
86.20
362
())
99.50
365
4(0,10)
101.25
359
1(0,1)
22.83
476
12
220.23)
46.06
474
14
CS-aligned
N20,42)
85.71
483
16
())
97.61
480
17
400.10)
99.10
481
19
1(0,
22.10
360
24
45.52
368
US
N2
84.28
368
N)),82)
98.57
372
10)
100.40
367
1)
22.10
371
20)
44.40
362
12058
CS
N(0.42)
80.47
361
NO0.82)
93.00
361
4(0
95.25
362
1(001)
22.30
396
20)
44.80
371
22
CS-aligned
N(0.42)
79.96
388
23
(0)
92.28
377
4(0, 10)
94.13
366
26
26

---

Published as a conference paper at ICLR 2025
Table 12:
Time statistics for different phases of training on TSP100-2D-U(O, 10).
Method
Sample size
Labeling time
Coreset Time
Training Time
Total time
Org 128000
4883
27686
32569
4003
153
2387
2540
US
8245
315
3217
3532
12951
495
3578
4073
4003
154
859
2331
3344
CS
8245
315
841
3217
4373
12951
493
1293
3516
5302
Table 13: Comparison uniform sampling and our coreset method using TSP100-2D-2((0,) 10) as
the training dataset test data TSP100-2D from different distributions.
Greedy
Greedy42-opt
Sample size
Method
Test distribution
Length (4)
Time (4)
Length (4)
Time (4)
128000
Org
U(0, 10)
86.77
358
79.53
353
US
4100 10)
100.62
355
80.97
375
4003
CS
10),
97.69
461
80.94
383
CS-aligned
4(0
97.71
363
80.95
369
US
U(0, 10)
92.66
352
80.33
365
8245
CS
410, 10)
93.12
381
80.38
372
CS-ali Cllgnnee
4000
93.27
351
80.41
354
US
100,
91.98
362
80.34
367
12951
CS
10)
92.33
354
80.23
356
CS aligned
(0)
92.39
360
80.28
367
Table 14: Comparison of uniform sampling and our coreset method using TSP100-2D-<((0 10) as the training dataset on test data of varying sizes. We fix the sample size as 12951.
Greedy
Greedy+2-opt
TSP size
Method
Test distribution
Length (4)
Time (4)
Length (4)
Time (4)
TSP-200
Org
((0010)
125.06
72
110.89
73
TSP-500
Org
4400, 10)
195.68
675
172.19
677
TSP-1000
Org
10)
276.69
2815
241.59
2824
4(0, 10)
130.05
76
111.71
TSP-200
CS
1(),
129.52
75
111.31
81
CS-aligned
4(0,10)
129.95
77
111.35
76
US
4(0,10)
238.46
677
177.30
682
TSP-500
CS
4(0,10)
221.76
677
175.94
682
CS-aligned
4(0,10)
221.72
675
175.89
683
US
U(0,10)
434.16
2811
254.37
2837
TSP-1000
CS
10)
346.71
2811
251.40
2831
CS CS-aligned
4(0
347.46
2813
251.35
2833
27

---

Published as a conference paper at ICLR 2025
Table 15: Comparison of uniform sampling and our coreset method using TSP100-2D-2((0,10) 10) as
the training dataset on test data TSPLIB Reimell 1991b.
Greedy
Greedy+2-opt
Sample size
Method
Test distribution
Length (4)
Time (4)
Length (L)
Time (4)
128000
Org
((0,1) 1)
125.39 .39
102
110.90
104
US
4(0, 10)
183.71 71
104
115.21
110
4003
CS
10)
164.81
106
114.50
108
CS- CS-aligned
4(0,10)
166.04
105
114.41
103
US
I0)
161.75
I07
II3.69
107
8245
CS
4(0, 10)
132.06
103
111.52
111
CS-alignn aSligie
10)
145.90
103
112.86
103
US
10)
157.10
113.98
105
12951
CS
10)
140.97
104
112.96
106
CS eSlaaieeed
10(
141.81
501
112.81
110
Table 16:
Comparison uniform sampling and our coreset method using TSPI00-3D-2((0, 10) as
the training dataset test data TSP100-3D from different distributions.
Greedy
Sample size
Method
Test distribution
Length (4)
Time (1)
128000
Org
4(0, 10)
87.84
350
US
U(0 10)
108.74
350
4122
CS
U(0, 10)
108.45
352
CS-aligned
1(0,10)
106.11
381
10)
95.78
360
8245
CS
100,
98.53
347
CS-aligned
10)
97.89
358
US
1(0,10)
93.38
364
12951
CS
10)
93.15
348
CS CS-aligned
U(0,10)
92.91
354
Table 17: Comparison of uniform sampling and coreset method using TSP100-3D-U((0, 10) as the training dataset on test data of varying sizes. We fix the sample size as 12951.
Greedy
TSP size
Method
Test distribution
Length (4)
Time (L)
TSP-200
Org
4400
125.98
73
TSP-500
Org
24(0, 10)
210.15
674
TSP-1000
Org
24(0, 10)
313.00
2818
US
u(0, 10)
145.67
78
TSP-200
CS
u(0, 10)
144.27
76
CS-alignt -Slaligned
U(0, 10)
143.46
75
US
U(0, 10)
302.16
674
TSP-500
CS
u(0, 10)
244.63
676
CS CS-aligned
4(0. 10)
236.33
689
US
u(0, 10)
535.90
2815
TSP-1000
CS
u(0, 10)
367.04
2812
CS- -S-aligned
10)
308.71
2816
28

---

Published as a conference paper at ICLR 2025
Table 18: Time statistics for different phases of MIS.
Method
Sample size
Labeling time
Coreset Time
Training Time
Total time
Org
128000
102600
16762
119362
3973
3184
I726
4910
US
8001
6413
2503
8916
12417
9953
3400
13353
3973
4007
2263
3227
9497
8001
7322
2424
5031
14777
12417
11032
2511
7011
20554
Table 19: Comparison of uniform sampling and our coreset method with training dataset ER-[90-
100] on test data from different distributions.
Greedy
Sampling
Sample size
Method
Test distribution
Size (1)
Time (4)
Size (t)
Time (4)
ER-[v90-100]
22.34
64
23.27
70
128000
Org
ER-[400-500]
34.66
134
36.69
551
ER-[700-800]
37.51
393
40.06
1463
ER-[v90-100]
19.57
64
21.34
319
US
ER-[400-500]
27.84
134
29.48
552
ER-[700-800]
30.30
391
32.23
1469
3973
ER-[v90-100)
19.77
63
21.49
72
CS
ER-[400-500]
27.99
135
29.85
558
ER-[700-800]
30.61
392
32.38
1524
ER-[v90-100)
20.38
64
22.33
70
US
ER-[400-500]
28.81
135
30.59
554
ER-[700-8001
31.28
393
32.77
1471
8001
ER-[v90-100)
20.25
64
22.27
73
CS
ER-[400-500]
29.59
134
31.91
549
ER-[700-800]
32.23
393
33.93
1460
ER-[V90-100)
20.80
63
22.30
71
US
ER-[400-500]
30.36
135
32.55
549
ER-[700-800]
32.30
393
34.25
1458
12417
ER- ER-[v90-100]
21.04
63
22.55
70
[RR04000500]
31.00
135
33.11
548
ER- (RR0770-800]
32.96
393
35.59
1462
Table Comparison of uniform sampling and our coreset method with training dataset ER-[90-
100] on test data SATLIB.
Greedy
Sampling
Sample size
Method
Test distribution
Size (t)
Time (1)
Size (t)
Time (4)
128000
Org
ER-[V90-100]
22.34
64
23.27
70
US
SATLIB
1015.64
120
1022.81
490
3973
CS
SATLIB
1015.31
122
1021.24
518
US
SATLIB
410.61
296
413.49
898
8245
CS
SATLIB
409.87
299
413.34
902
US
SATLIB
410.32
304
413.55
906
12417
CS
SATLIB
410.83
297
414.04
900
29

---

Published as a conference paper at ICLR 2025
Table 21: Comparison of uniform sampling and our coreset method with training dataset CVRPI00-
(0, 0.1²) on test data from different distributions.
Sample size
Method
Test distribution
RRC-budget (1)
Length (4)
Gap (4)
Time (4)
0
17.64
6.34%
3
50
16.58
-0.02%
45
128000
Org
CVRP100
100
16.43
-0.96%
86
200
16.30
-1.70%
162
500
16.18
-2.43%
397
0
19.56
17.91%
3
50
17.85
7.64%
45
US
CVRP100
100
17.57
5.96%
86
200
17.30
4.28%
500
17.03
2.71%
397
4437
0
19.16
15.51%
50
17.65
6.41 %
45
CS
CVRP100
100
17.38
4.78%
86
200
17.15
3.38%
163
500
16.91
2.01%
400
0
18.77
13.18%
50
17.35
4.62%
47
US
CVRP100
100
17.13
3.27%
91
200
16.92
2.01%
172
500
16.71
0.75%
423
8082
0
18.49
11.51%
3
50
17.19
3.66%
45
CS
CVRP100
100
16.98
2.38%
88
200
16.78
1.19%
168
500
16.60
0.06%
413
0
18.65
12.47%
50
17.24
3.95%
47
US
CVRP100
100
17.01
2.59%
90
200
16.82
1.43%
170
500
16.63
0.25%
415
12175
0
18.53
11.72%
50
17.18
3.56%
47
CS
CVRP100
100
16.96
2.23%
90
200
16.77
1.13%
170
500
16.58
-0.01%
415
30

---

Published as a conference paper at ICLR 2025
test data for other cases. Obviously, the uniform distribution has the highest entropy and thus the highest diversity. For these Gaussian distributions, the larger the variance, the larger the diversity.
Results of CVRP100 Tables 21 23 present the results training dataset CVRPI00-N 0.1²). The training datasets are generated by the uniform sampling and our coreset technique respectively. The results show that both our method and uniform sampling method perform better as the sample size increases. For both the test data with distribution shift and without distribution shift, our method consistently shows better performance. Table 22 further illustrates that our method can generalize to large-scale CVRP problems better. Table 23 shows the performance the CVRPLIB dataset.
Tables 24 to 26 present the results on training dataset CVRP100-U((, 1). The training datasets are generated by the uniform sampling and our coreset technique respectively. The results show that both our method and uniform sampling method perform better as the sample size increases. For both the test data with distribution shift and without distribution shift, method consistently shows better performance. Table 25 further illustrates that our method can generalize to large-scale CVRP problems better. Table 26 shows the performance the CVRPLIB dataset.
Table 22: Comparison of uniform sampling and coreset method with training dataset CVRP100-NV 0.12) on test data of varying sizes. We fix the sample size 12175.
Sample size
Method
Test distribution
RRC-budget (1)
Length (J)
Gap (1)
Time (1)
0
22.70
12.52%
50
21.50
6.60%
26
CVRP200
100
21.34
5.77%
200
21.16
4.90%
105
500
20.96
3.88%
256
0
41.68
11.95%
50
40.23
8.06%
179
128000
Org
CVRP500
100
39.91
7.20%
298
200
39.64
6.48%
604
500
39.32
5.62%
1628
0
44.62
20.29%
73
50
42.74
15.25%
895
CVRP1000
100
42.36
14.22%
1810
200
41.81
12.72%
3672
500
41.19
11.04%
9108
0
24.17
19.80 %
2
50
22.79
12.97%
26
US
CVRP200
100
22.52
11.61%
50
200
22.24
10.27%
108
500
21.89
8.52%
263
12175
0
24.00
18.97%
50
22.60
12.03%
25
CS
CVRP200
100
22.36
10.83%
48
200
22.13
9.71%
105
500
21.75
7.84%
256
45.23
21.50%
50
43.40
16.58%
173
US
CVRP500
100
42.84
15.06%
288
200
42.39
13.85%
584
500
41,82
12.32%
1579
12175
0
45.10
21.15%
50
43.19
16.00% %
173
CS
CVRP500
100
42.73
14.78%
287
200
42.28
13.56 %
583
500
41.64
11.85%
1576
Continued on next page
31

---

Published as a conference paper at ICLR 2025
Table 22: Comparison of uniform sampling and our coreset method with training dataset CVRPI00-V(O. 0.12) on test data of varying sizes. We fix the sample size 12175.
Sample size
Method
Test distribution
RRC-budget (4)
Length (J)
Gap (1)
Time (4)
0
53.01
42.91%
74
50
49.42
33.23%
897
US
CVRP1000
100
48.81
31.60%
1819
200
47.95
29.28%
3708
500
46.91
26.48%
9180
12175
0
51.88
39.88%
50
48.24
30.06%
892
CS
CVRP1000
100
47.71
28.64%
1805
200
47.00
26.71%
3672
500
46.12
24.34%
9108
Table 23: Comparison of uniform sampling and our coreset method with training dataset CVRP100-
NO 0.12) on test data CVRPLib.
Sample size
Method
Test distribution
RRC-budget (4)
Length (4)
Gap (4)
Time (+)
913.17
16.48%
1
50
787.20
0.41%
4
128000
Org
CVRPLib
100
787.20
0.41%
7
200
787.20
0.41%
12
500
787.20
0.41%
29
0
927.95
18.36% %
50
868.66
10.80%
US
CVRPLib
100
864.51
10.27%
200
844.59
7.73%
14
500
844.59
7.73%
33
4437
0
950.06
21.18%
50
841.93
7.39%
CS
CVRPLib
100
837.50
6.82%
200
837.50
6.82%
14
500
834.28
6.41% %
32
971.82
23.96%
50
867.72
10.68%
US
CVRPLib
100
796.05
1.54%
200
796.05
1.54%
13
500
787.81
0.49%
30
8082
0
917.07
16.97%
50
829.60
5,82%
CS
CVRPLib
100
829.60
5.82%
200
823.85
5.08%
13
500
791.81
1.00%
30
0
1016.27
29.63 %
50
865.31
10.37%
US
CVRPLib
100
865.31
10.37%
200
858.44
9.49%
500
858.44
9.49%
30
12175
0
917.09
16.98%
50
811.18
3,47%
CS
CVRPLib
100
810.27
3.35%
200
806.12
2.82%
13
500
806.12
2.82%
30
32

---

Published as a conference paper at ICLR 2025
Table 24: Comparison of uniform sampling and coreset method with training dataset CVRP100-
2(0 1) on test data from different distributions.
Sample size
Method
Test distribution
RRC-budget (4)
Length (4)
Gap (4)
Time (4)
0
17.35
4.64%
3
50
16.36
-1.38%
47
128000
Org
CVRP100
100
16.22
-2.18%
90
200
16.13
-2.75%
170
500
16.02
-3.40%
418
0
18.48
11.43
50
17.15
3.39%
44
US
CVRP100
100
16.93
2.08%
200
16.74
0.93%
161
500
16.57
-0.10%
396
4697
0
18.44
11.20%
50
17.10
3.10%
CS
CVRP100
100
16.89
1.85%
85
200
16.70
0.69%
161
500
16.53
00.4%
0
18.22
9.83%
50
16.91
1.96%
US
CVRP100
100
16.71
0.78%
83
200
16.55
-0.21%
158
500
16.39
-1.17%
389
7694
0
18.16
9.52%
50
16.91
1.97%
45
CS
CVRP100
100
16.72
0.82%
86
200
16.56
-0.18%
162
500
16.40
-1.10%
400
0
18.03
8.70%
50
16.82
1.41%
45
US
CVRP100
100
16.64
0.34%
86
200
16.50
-0.54%
162
500
16.35
-1.43%
395
12033
0
18.01
8.59%
50
16.81
1.36%
CS
CVRP100
100
16.62
0.21% %
84
200
16.48
-0.64%
160
500
16.34
-1.55%
39
Table 25: Comparison of uniform sampling and our coreset method with
training dataset CVRP100-(((,)) 1) on test data of varying sizes. We fix sample size as 12033.
Sample size
Method
Test distribution
RRC-budget (4)
Length (4)
Gap (1)
Time (L)
22.41
11.08
50
21.20
5.08%
36
CVRP200
100
21.05
4.36%
68
200
20.93
3.76%
145
500
20.75
2.88%
353
0
41.01
10.16%
50
39.69
6.61%
190
128000
Org
CVRP500
100
39.42
5,87%
319
200
39.16
5.20%
645
500
38.91
4.51%
1730
O
43.09
16.19%
73
Continued on next page
CVRP1000
33

---

Published as a conference paper at ICLR 2025
Table 25: Comparison of uniform sampling and our coreset method with training dataset CVRP100-Z((0, 1) on test data of varying sizes. We fix the sample size as 12033.
Sample size
Method
Test distribution
RRC-budget (4)
Length (1)
Gap (4)
Time (4)
50
37.09
11.85%
904
100
41.17
11.00%
1828
200
40.76
9.90%
3708
500
40.29
8.63%
9216
0
23,29
13.45%
50
21.98
8.94%
28
US
CVRP200
100
21.75
7.82 %
54
200
21.57
6.91 %
115
500
21.33
5.72%
281
12033
20.17
14.97% %
50
21.93
8.70%
29
CS
CVRP200
100
21.75
7.83%
54
200
21.59
7.04%
116
500
21.30
5,50%
282
0
37.23
16.76%
2
50
41.77
12.19%
177
US
CVRP500
100
41.38
11.15%
296
200
41.02
10.18%
598
500
40.51
8,82%
1620
12033
0
43.19
16.02% %
2
50
41.66
11.89% %
176
CS
CVRP500
100
41.25
10.81 %
295
200
40.88
9.80 %
597
500
40.40
8.52%
1609
0
48.20
29.96%
73
50
46.12
24.33%
907
US
CVRP1000
100
45.67
23.14%
1847
200
45.04
21.43%
3816
500
44.29
19.42%
9324
12033
0
48.24
30.05%
73
50
45.89
23.73%
899
CS
CVRP1000
100
45.50
22.66 %
1820
200
44.87
21.02%
3672
500
44.07
18.82%
9180
34

---

Published as a conference paper at ICLR 2025
Table 26: Comparison of uniform sampling and our coreset method with training dataset CVRP100-
(4(0) 1) on test data CVRPLib.
Sample size
Method
Test distribution
RRC-budget (4)
Length (4)
Gap (4)
Time (4)
0
856.40
9.24%
50
797.45
1.72%
128000
Org
CVRPLib
100
797.45
1.72%
10
200
797.45
1.72%
20
500
797.45
1.72%
47
0
902.29
13.09%
50
846.35
7.95%
5
US
CVRPLib
100
838.10
6.90%
200
838.10
6.90%
14
500
838.10
6.90%
32
4697
0
1020.05
30.10%
50
809.93
3,30%
4
CS
CVRPLib
100
797.45
1.72%
200
797.45
1.72%
14
500
797.45
1.72%
0
1096.32
39.84%
50
846.93
8.03%
US
CVRPLib
100
846.93
8.03%
7
200
846.93
8.03%
13
500
846.93
8.03%
32
8082
0
866.09
10.47%
50
789.79
0.74%
4
CS
CVRPLib
100
789.79
0.74%
7
200
789.79
0.74%
13
500
789.79
0.74%
31
0
864.85
10.31 %
50
830.51
5.93%
4
US
CVRPLib
100
797.45
1.72%
200
797.45
1.72%
14
500
797.45
1.72%
32
12033
0
965.89
23.20%
50
816.14
4.10%
CS
CVRPLib
100
809.71
3.28 %
200
799.16
1.93%
13
500
787.20
0.41 %
32
Table 27: Comparison of uniform sampling and our coreset method with different graph embedding techniques test data from different distributions. CS-spring is the embedding technique based
on force-directed representation; CS-spectral is the spectral embedding technique; CS-MDS the emhedding technique based multidimensional scaling.
Sample size
Method
Test distribution
Size (f)
Time (1)
ER-[400-500)
27.40
133
4010
US
ER-[700-800
30.36
392
ER-[1400-1500)
34.05
1361
ER-[400-500]
28.46
135
3973
CS-spring
ER-[700-800)
30.89
389
ER-[1400-1500)
34.25
1361
ER-[400-500]
27.68
132
8001
CS-spectral
ER- ER-[700-800]
30.43
391
ER[[1400-1500]
34.14
1362
ER-(400)500)
28.43
132
12417
CS-MDD
E
31.10
389
ER- ER-[1400 (1400-1500)
34.52
1361
35


Reviews:
[{"review_id": "Tcqm9hmRfI", "reviewer": "Reviewer_SBLn", "summary": "The paper presents a novel approach to enhance neural combinatorial optimization (NCO) by introducing Wasserstein-based coresets, which efficiently compress large datasets into smaller, representative proxies. By modeling combinatorial optimization (CO) instances as probability measures and utilizing a specialized Wasserstein distance under rigid transformations (RWD), the authors quantify differences between CO instances effectively. To address the computational challenges of constructing coresets for large datasets, they adapt the merge-and-reduce framework, enabling parallel processing and theoretical guarantees of representation quality. Additionally, the proposed training framework leverages these coresets to reduce computational and storage requirements while maintaining and even improving robustness to distribution shifts between training and testing data. Experimental results on Traveling Salesperson Problem (TSP) and Maximum Independent Set (MIS) instances demonstrate that their method outperforms uniform sampling and other existing techniques, achieving better performance and enhanced robustness with reduced resource usage.", "questions": "Does the proposed merge-and-reduce framework to accelerate coreset construction introduce additional practical overhead due to increased data transfer costs (via partitioning and merging) and possible synchronization delays?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper effectively addresses key challenges in neural combinatorial optimization (NCO) by introducing Wasserstein-based coresets that reduce dataset size without compromising essential information. The use of Wasserstein distance under rigid transformations (RWD) provides a robust metric for comparing combinatorial optimization instances, enhancing the method's ability to handle distribution shifts. By adapting the merge-and-reduce framework, the authors achieve scalable and parallelizable coreset construction, making the approach feasible for large datasets. Theoretical guarantees ensure that the coresets accurately represent the original data, while the proposed training framework demonstrates reductions in computational and storage requirements. Experimental results on the Traveling Salesperson Problem (TSP) and Maximum Independent Set (MIS) depict the method's superior performance and increased robustness compared to uniform sampling.", "weaknesses": "While the paper presents a rigorous analysis of Wasserstein-based coresets to enhance NCO, it exhibits several weaknesses. In particular, the English language is somewhat poor, leading to unclear statements $-$ for instance, \"Therefore, how to train a competitive model by using limited resources while guaranteeing its robustness to distribution shift is a deserving problem\" is awkwardly phrased. Technically, the justification for modeling combinatorial optimization instances as probability measures using Rigid Wasserstein Distance (RWD) seems incomplete, especially since the assumptions like low doubling dimension may not hold in practical, high-dimensional settings (e.g., problems with large graphs or high-dimensional feature spaces). Despite the reduced algorithmic complexity, it is unclear whether the proposed merge-and-reduce framework (to accelerate the coreset construction algorithm) may introduce additional practical overhead due to the increased cost of data transfer (via partitioning and merging) and possible synchronization delays.", "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": "", "extra_scores": {}}, {"review_id": "rpmdScyuES", "reviewer": "Reviewer_CqAL", "summary": "In this article, the author(s) develop a framework for accelerating neural combinatorial optimization (CO) methods. The basic idea is to construct a small-size coreset to represent the whole data set, and only train models on the coreset. The coreset is constructed based on a clustering algorithm and the Wasserstein distance under rigid transformations (RWD).", "questions": "See the \"Weaknesses\" section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The overall motivation of this article is clear. Efficiently solving CO problems are of great importance, and this article provides a potential direction.", "weaknesses": "1. Although the main topic of this article is about combinatorial optimization (CO) problems, it seems that the whole article ignores the structure and discreteness of CO problems, and only considers their graph embedding. Then the author(s) only consider objects that lie in an Euclidean space, which leaves me the impression that the proposed method is developed for continuous problems, and CO only appears in the preprocessing stage (i.e., converting a CO instance into a continuous object). I am not sure if this is the proper way to deal with CO problems, but at least the author(s) should discuss the relationship between the original CO problem and the embedding. For example, is there any information loss after converting into embeddings? Are the results sensitive to the choice of embedding methods?\n\n2. I think the equation in Definition 2.1 is incorrect. The $C_{ij}$ term should be $P_{ij}$, and the cost matrix $C$ is never used.\n\n3. It seems that the Wasserstein distance under rigid transformation (RWD) is a core component of the proposed method, but I do not see the method to compute it. In Remark 3.1, the author(s) claim that RWD can be solved within $\\tilde{O}(n^2)$ time, but I do not see why. Computing RWD should be much more difficult than the classical optimal transport (OT), as it involves optimization over an additional object $e$. But even for OT, I wonder how the complexity $\\tilde{O}(n^2)$ can be achieved without using approximation methods such as the entropic regularization, as it is well known that a linear programming solver for OT takes $O(n^3\\log(n))$ [1].\n\n4. If computing RWD is expensive, then I wonder whether it is meaningful to construct the coreset at all. The author(s) are suggested comparing the cost of training on the whole data set and the cost of constructing the coreset plus the time of training on the coreset.\n\n[1] Pele, O., & Werman, M. (2009). Fast and robust earth mover's distances. In 2009 IEEE 12th international conference on computer vision.", "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": "", "extra_scores": {}}, {"review_id": "ZZETYuTYhm", "reviewer": "Reviewer_wmHE", "summary": "The authors represent CO instances as probability measures and utilize a variant of Wasserstein distance that accounts for rigid transformations, allowing the model to better handle similar instances.\n\nThey construct a small, representative subset of the original data using hierarchical clustering. This process is optimized using a \"merge-and-reduce\" framework, enabling parallel computing and faster training times.\n\nThe proposed framework replaces large datasets with the coreset for training, reducing computational and storage needs. For inference, the framework aligns test data along a hierarchical tree, which further accelerates the process.\n\nThrough experiments on tasks such as the Traveling Salesperson Problem (TSP), the authors demonstrate that the coreset-based framework achieves robust performance and efficiency gains, especially under distribution shifts.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality\n\nThis paper introduces a novel approach to neural combinatorial optimization (NCO) by leveraging Wasserstein-based coresets to address resource and robustness challenges in training models for combinatorial optimization problems. The originality stems from: 1. Modeling combinatorial optimization instances as probability measures and applying the Wasserstein distance under rigid transformations (RWD) is innovative. This framework addresses the challenges of data redundancy and distribution shifts, providing a fresh perspective in the NCO space. 2. While coresets are common in clustering and other machine learning tasks, adapting this technique for combinatorial optimization with merge-and-reduce frameworks for accelerated parallel computing is both creative and practical.\n\nQuality\n\nThe paper is well-executed, with rigorous theoretical foundations and a thoughtful experimental setup: 1. The authors provide a solid mathematical foundation for the proposed coreset construction, including formal definitions, theoretical guarantees, and proof sketches that validate the coreset’s ability to represent large datasets with minimal error. 2. The experiments cover various TSP instances under both uniform sampling and coreset techniques, testing robustness to distribution shifts and different dimensions (2D and 3D) with insightful comparisons across sample sizes and distributions. This comprehensive approach substantiates the paper's claims.\n\nClarity\n\nThe paper is well-structured and communicates its ideas effectively: 1. The paper follows a clear progression from defining the problem and introducing the method to presenting experimental results. Definitions, such as the RWD and coreset construction, are introduced at appropriate points, aiding understanding. 2. Algorithmic steps are outlined in detail, making it easier to understand implementation specifics, especially for constructing coresets.\n\nSignificance\n\nThis work has substantial potential significance for both research and practical applications: 1. By enabling training on compact coresets, the paper addresses one of the most significant limitations in neural combinatorial optimization—computational inefficiency with large datasets. This is a notable advancement that could make NCO more feasible in real-world, large-scale applications like logistics, robotics, and manufacturing. 2. The paper’s robustness improvements are important for applications where data distributions vary, making it applicable across domains where data acquisition is not consistently distributed or is prone to changes over time.", "weaknesses": "1. The coreset construction approach offers impressive results in reducing data size while preserving accuracy. A deeper discussion on the trade-offs between dataset compression and accuracy loss would be beneficial. Although error bounds are mentioned, it would strengthen the paper if experiments explicitly analyzed performance degradation as coreset size is reduced.\n\n2. It’s unclear how the coreset method performs across diverse types of CO instances (e.g., sparse vs. dense graphs or varying clustering characteristics). Adding experiments with different dataset properties could clarify the method’s robustness and practical applicability.\n\n3.  Aligning instances under rigid transformations for each test instance could be computationally expensive, especially for larger datasets or higher-dimensional instances (e.g., TSP-3D and beyond). Although a heuristic for alignment is provided, it would be helpful to quantify the computational cost and compare it to baseline methods.\n\n4. The paper does not include a performance comparison between exact and heuristic alignment. Such an evaluation would help clarify the practical efficiency and accuracy trade-offs of the heuristic.\n\n5. The experimental validation focuses heavily on TSP or MIS dataset, which, while effective, may limit the generalizability claims. While these are well-known CO problems, the approach could benefit from validation on other types of CO tasks with varying structures, such as graph partitioning problems. Since these problems exhibit different graph characteristics, they would better demonstrate the adaptability of the coreset method.\n\n6. Current experiments primarily focus on tour length and runtime as evaluation metrics. Additional measures, such as robustness to noise or perturbations in the data, could further demonstrate the coreset’s value in handling real-world data variability.\n\n7. The merge-and-reduce framework is crucial for scaling the coreset method, but the paper provides limited guidance on its implementation and scalability implications: Although the paper briefly mentions time complexity, a more detailed breakdown of the merge-and-reduce framework’s complexity across layers and for different dataset sizes would be helpful.\n\n8. There is limited discussion on how the framework’s parallelization could be optimized or applied to larger datasets. This discussion would be especially useful for practitioners seeking to apply the method in large-scale real-world settings.\n\n9. While the paper claims improved robustness to distribution shifts through the use of coresets, this aspect is not rigorously analyzed or compared. The paper could benefit from quantifying the robustness improvements by comparing the method’s performance across significantly different distributions and measuring accuracy decay.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)