A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver

We appreciate the reviewer gmJz's insightful questions and constructive feedbacks.

[Acronyms] Thank you for the suggestion. We will ensure all acronyms are properly defined upon first use and provide a reference table in the final version. For example, "VRPs" stands for Vehicle Routing Problems, "LKH" for Lin-Kernighan-Helsgaun and "HGS" for Hybrid Genetic Search, etc.

[Typos] We appreciate the attention to typos. We identified and will correct errors such as "manioflds" (line 123), "hypersphereical" (line 124), "$n$ nodes" (line 185). The cardinal of $V$ on page 4 is indeed $n+1$ and we will correct it. Besides, in Table 6 (Appendix.3), we notice that for the row indexed by "R102", two columns are mis-highlighted at same time. We have checked all tables and will make sure all bold values are correctly used.

[Comments on curvature figure] In Figure 4 (Appendix.1), we show node curvatures on 10 OOD tasks. It shows that almost every node in the dataset has either negative or positive curvature and the average curvature suggests that each task contains geometry patterns. For Figure 5-10 (Appendix.3), we provided corresponding comments in "curvature analysis" part (Appendix.1), where shallow layers and deeper layers present different curvatures. We will move this analysis directly into these figure captions in the final version.

[Why is transition non-smooth] The transition between different curvature spaces is non-smooth primarily due to the incompatibility of geometric structures among different subspaces. In specifics, hyperbolic and spherical spaces have fundamentally different distance metrics. In details, the geodesic distance in hyperbolic space grows exponentially when $|\kappa|$ ($\kappa$ here denotes negative curvature of hyperbolic space) increases. While on the other hand, the distance in spherical space is bounded. This discrepancy may introduce unexpected disturbance in feature transformation. In Figure 5-10 (Appendix.3), we visualize the curvature information of different subspaces layer by layer. From the results in these figures, the shallow layers tend to process features in hyperbolic spaces while deeper layers choose to process features via spherical spaces. The transitions between hyperbolic space and spherical space usualy happen around layer 2 and layer 3. The inferior features caused by non-smooth transition will severly affect deeper layers' learning ability. To mitigate this, we apply techniques similar to Mix-Up[1] where previous layer's features was infused into deeper layers. This can guide deeper layers gradually move into new curvature spaces.

[Settings of hyperparameters] Table 5 (Appendix.2) lists our detailed settings of hyperparameters and we strictly follow prior works[2,3]: 5,000 training epochs, batch size of 128, and 20,000 instances per epoch from 6 VRPs. Fine-tuning uses 10,000 instances per epoch for 10 epochs with the same batch size. We employ Adam optimizer with learning rate 1e-4, decayed by 10 after 4,500 epochs. Feature space (128 dimensions) is split into 8 subspaces of 16 dimensions, initialized at 0. Number of attention heads and encoder layers are 8 and 6, respectively.

[Number of parameters in our method] For embedder, we insert two mixed-curvature modules for depot and customer node, respectively. For each layer of encoder, we insert one mixed-curvature module for processing feautres from previous layer. The comparisons between baselines and mixed-curvature versions are listed as follows:

From table, compared with original backbones, the number of parameters is inreased by 3.57%~10.56%. We will emphasize these changes in the final version.

[Computational cost] To compare the computational cost with baseline models like POMO-MTL and MVMOE, we list the running time here. From results in the table, running time of our model increases a little bit compared to backbones. Taking (n=100) as example, Mixed-POMO-MTL, Mixed-MVMOE-L and Mixed-MVMOE introduce 10.72%, 7.68%, 7.56% costs to backbones, respectively. These show that mixed-curvature modules bring moderate costs, which would not cause serious inference burden.

[Ablation] We conduct ablation studies on MVMOE and results are shown here. We can see that Mix-Up can improve performances.

[1]Pomo: Policy optimization with multiple optima for reinforcement learning. NIPS, 2020.

[2]Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024.

[3]mixup: Beyond empirical risk minimization. ICLR, 2018.

We would like to express our sincere gratitude to the reviewer qtXz for detailed and valuable suggestions and comments.

[Dimension of $X$] Since graph is discrete, Ollivier-Ricci metric is used for measuring curvature based on edges weights, which doesn't require dimensions of inputs. This is different from curvature on 3-dimension smooth manifolds. Our $X$ only consists of two dimensions (coordinates) for calculating curvatures. Since some nodes don't have features like time-windows and backhauls, these features will separately appear in encoder. We will make this clear in the final version.

[Instance augmentation method] We follow POMO-MTL[1] and MVMOE[2], applying greedy rollout with 8× instance augmentation for fair comparisons, where best solutions for each instance are obtained by solving multiple (8×) equivalent instances. Those equivalent instances are acquired by rotating or clipping the original instances[7]. We will clarify this in the final version.

[Vector diagram] We have created a new vector diagram (here) that will replace the original Figure 2 in the final version.

[Clarification for motivations] Following [1,2], settings of VRPs are based on Euclidean space. However, the underlining data structures are graphs and they produce certain kinds of complex structures (e.g., node clustering, scattering) which can be approximated by tree-like or cycle-like patterns[4,5,6]. As pointed out in[4,6], to capture these nuances and variations from datas, Riemannian manifolds provide us with a more flexible and effective framework. Though graph is discrete, which is usually different from Riemannian manifolds that are smooth and continuous, we can use some discrete analogs (e.g., the Ollivier-Ricci curvature used for visualizations in Figure 1) to get some senses.

Recall definitions in Equation 15,16 (Appendix.1), the node curvature is calculated based on edge weights of neighbour nodes. So, given a graph $G$ and two nodes $u$ and $v$, the positive Ollivier-Ricci curvature $\kappa(u,v)$ indicates that $u$ and $v$ share many common points in their neighbours. In other words, if random walks $A$ and $B$ start from $u$ and $v$ respectively, then $A$ and $B$ are more likely to meet with each other in a few steps. In this case, paths on $G$ tend to collapse together. Similarly, the negative curvature indicates that paths on $G$ tend to diverge and spread out. Such kinds of behaviours are quite similar to those of geodesics on Riemannian manifolds where initially parallel geodesics will converge and diverge on Spherical and Hyperbolic Spaces, respectively. From these, Ollivier-Ricci curvature can be treated as a discrete analogy of curvature on continuous domain and its outputs strongly reflect the existence of non-uniform structures in datas, which motivates us to leverage Riemannian manifold spaces for creating a feature space that preserves the underlying node distances and relative positions more faithfully.

From Table 3 (Appendix.3), the calculated distortion rates (defined in Equation 9) of different models show that Riemannian manifolds have done a better job of preserving original distances among nodes in feature space compared with other baselines, which is more desirable since neural solvers for VRPs heavily rely on the quality of produced hidden features to select next node.

To summarize, graphs used in VRPs often contain intricate relations that can't directly be viewed as flat structures. Though graph is discrete, we can utilize neural networks to firstly embed graph into continuous embeddings and apply curved manifolds to fit the underlining geometric structures, which can let model enjoy much stronger abilities to detect and capture fine-grained information from the inputs.

[How to set $D$ and $C$ in indivisible case] In our case, $D=128$ and $C=8$ so each subspace has 16 dimensions. When $D$ is not divisible by $C$, we need to manually design the dimension of each subspace. For instance, when $D=127$ and $C=8$, the first 7 subspaces can have 16 dimensions and last one has 15 dimensions (other choices are also allowed as long as the summation of subspaces' dimensions is equal to $D$). We follow POMO-MTL[1] and MVMOE[2] where $D$ is always divisible by $C$. But this can be explored in future (e.g., using neural architecture search[3] to decide dimensions of subspaces).

[1]Multi-task learning for routing problem with cross-problem zero-shot generalization. KDD, 2024.

[2]Mvmoe: Multi-task vehicle routing solver with mixture-of-experts. ICML, 2024.

[3]Neural architecture search: A survey. JMLR, 2019.

[4]Learning mixed-curvature representations in product spaces. ICLR, 2018.

[5]Hyperbolic graph neural networks. NIPS, 2019.

[6]Constant curvature graph convolutional networks. ICML, 2020.

[7]Pomo: Policy optimization with multiple optima for reinforcement learning. NIPS, 2020.

We sincerely thank the reviewer dd5d for the valuable comments and suggestions. We provide the point-to-point responses below to address the concerns.

[Figures to show curvatures of inputs] Figure 1 visualizes the curvature information on 6 training tasks. We use 1,000 VRP instances (size 50) to record the frequency of node curvatures via Ollivier-Ricci curvature[1] (briefly introduced in Appendix.1). Histograms in Figure 1 show that each task consists of nodes with either positive or negative curvatures with a tendancy towards negative curvature. Similar conclusions also hold for another 10 OOD tasks and we report their histograms in Figure 4 (Appendix.1). These all validate our motivation in introducing mixed-curvature space into pre-training stage.

[Clarification for operations in Figure 2] Each curvature subspace needs exponential mapping $Exp(\cdot)$ and logarithmic mapping $Log(\cdot)$ for feature transformation. The subspace $C$ also needs $Log(\cdot)$ but it was omitted for brevity. We have created a complete one here and will update it in final version.

[Mixed-curvature VS non-Euclidean space] The Euclidean space is flat and has zero curvature. Conversely, non-Euclidean space acquires non-zero valued curvature. The mixed-curvature space consists of multiple subspaces with possible different curvatures. In our case, the original 128-dimension feature space is split into 8 subspaces (16 dimensions) and each is assigned with a learnable curvature.

[How do subspaces look like] In Appendix.3, we visualize curvature information of subspaces in embedder and encoder layer under different settings. For POMO-MTL based architectures, we visualize both scales (n=50, 100) in Figure 5 and Figure 6 (Appendix.3), respectively. Similarly, we show results for MVMOE-Light and MVMOE in Figure 7,8 (Appendix.3) and Figure 9,10 (Appendix.3), respectively. From the results, one can observe a common phenomena: the shallow layers favor low-curvature/hyperbolic space while deeper layers favor high-curvature/spherical space, illustrating how features evolve through layers.

[Computation efficiency] We provide running time of baselines and models with mixed-curvature modules here. As we can see, time increase is moderate and it doesn't cause significant burdens. Moreover, the recent work[2] can avoid mapping operations by fully exploitting geometric properties of certain manifolds, and we can explore it to further reduce the computation in future.

[More details for methodology] We acknowledge the concern regarding the imbalance between the Preliminary and Methodology section. We agree that the methodology section requires greater detail and clarity. In the final version, we will add following details and make it more informative:

1.How to process inputs

Following the prior works[3], we first project raw inputs into high-dimensional Euclidean space and then transform them into mixed-curvature space via $Exp^{\kappa}(\cdot)$.

2.How curvatures affect Exp($\cdot$) and Log($\cdot$)

The curvature is vital for $Exp(\cdot)$ and $Log(\cdot)$. Given a curvature $\kappa$:

2.1 Hyperbolic Model ($\kappa < 0$)

• Exponential Map:

  $\exp_p(v) = p \oplus_{\kappa} \left(\tanh\left(\sqrt{-\kappa} \frac{\lambda_p \|v\|}{2} \right) \frac{v}{\|v\|} \right),\quad p\in \mathcal{M}, v \in T_{v}\mathcal{M}$

• Logarithmic Map:

  $\log_p(q) = \frac{2}{\lambda_p \sqrt{-\kappa}} \tanh^{-1}(\sqrt{-\kappa} \|p \oplus_{\kappa} (-q)\|) \frac{p \oplus_{\kappa} (-q)}{\|p \oplus_{\kappa} (-q)\|},\quad p,q \in \mathcal{M}$

where $p$ is point on manifold $\mathcal{M}$, $v$ denotes point on tangent space $T_{v}\mathcal{M}$ and $q$ denotes a point on $\mathcal{M}$. $\lambda_p$ here is the hyperbolic metric: $\frac{2}{1 - \kappa \|p\|^2}$.

2.2 Spherical Model ($\kappa > 0$)

• Exponential Map:

  $\exp_p(v) = \cos(\sqrt{\kappa} \|v\|) p + \sin(\sqrt{\kappa} \|v\|) \frac{v}{\|v\|}$

• Logarithmic Map:

  $\log_p(q) = d_{\mathbb{\kappa}}(p, q) \frac{q - \cos(d_{\mathbb{\kappa}}(p, q)) p}{\|q - \cos(d_{\mathbb{\kappa}}(p, q)) p\|},\quad d_{\mathbb{\kappa}}(p,q)=\frac{1}{\sqrt{\kappa}} \cos^{-1}(\kappa \cdot \langle p, q \rangle)$

2.3 Effects of $\kappa$

For hyperbolics, if $|\kappa|$ increases, the metric $\lambda_p$ will decrease thus distance between two points will become larger and points on the manifold acquire stronger tendancy to spread out. For sphericals, enlarging $|\kappa|$ will lead to shrinkage on the distance, which means points on sphere become closer together.

[1]Ricci curvature of markov chains on metric spaces. JFA, 2009.

[2]Hypformer: Exploring efficient transformer fully in hyperbolic space. KDD, 2024.

[3]Hyperbolic vision transformers: Combining improvements in metric learning. CVPR, 2022.