Learning from A Single Graph is All You Need for Near-Shortest Path Routing

This paper addresses the All-Pairs Near-Shortest Path (APNSP) problem using the Markov Decision Process (MDP) framework and proposes a DNN-based approach to learning the local forwarding policy by predicting the Q-values. The neural network model takes the state features and action features as input, which include the distance information of the current state (node) and the next state (one neighbor of the current node). The models are trained based on supervised learning, where the samples are collected from a seed graph. In addition, the authors provide theory results to demonstrate the generalization properties of the model. Experiments have been shown to evaluate the scalability and generalizability of the proposed approach.

This paper looks at the (near-)shortest path routing problem on geometric random graphs in Euclidean and hyperbolic metric spaces. Each instance of the problem consists of a graph and a pair of source and destination nodes. There are two settings, one where the input feature for each node is simply the (Euclidean/hyperbolic) distance to the destination and one where each node additionally receives its stretch factor (essentially how far the node lies off of the straight line distance between the source and destination nodes) as input. The authors train a neural network to calculate a score independently for each neighbour of a node, so that the highest score (Q-value) neighbour can be chosen as the next location towards the destination. The input for the scoring network is the node itself and one of its neighbours. By repeating the scoring for each neighbour, a step can be taken, and by repeating these steps multiple times, a path can be formed from the source to the destination node. The authors show that their neural network with just the distance to the destination as input is able to learn the greedy policy of always choosing the neighbour that is nearest to the destination. They also show that their neural network can outperform greedy when the stretch factor is also provided. Their network is able to learn effective policies with very little training data.

The authors use neural networks to solve the problem of finding (approximately) shortest paths in geometric graphs using only local information.

They consider graphs obtained by sampling a number of points in Euclidean or hyperbolic space, and connecting with an edge any two points whose distance is smaller than a fixed threshold. In such graphs, they consider routing algorithms that given current node u, and knowing that we are going from s to t, pick the next node v from neighbors of u based only on information about s, t, and u (and not about the whole graph). A classic heuristic of this kind, called Greedy Forwarding, simply picks the neighbour that minimizes the geometric distance to target t.

The authors propose a more elaborate approach for routing. They associate with each node v two features that depend on the source and target: 1) geometric distance from target d(v,t) and 2) stretch (d(s,v)+d(v,t))/d(s,t). Then, they train a neural network that takes as input features of two neighboring nodes u, v and outputs an approximation of the so-called Q-value. The Q-value is supposed to be high if it is a good routing decision to go to node v when being at node u, and in practice it is simply the negative length of the shortest path from v to the target. Then, to perform the actual routing, one has to evaluate the model on all neighbors of the current node and pick the one that gave the highest output value.

The network is trained using either supervised learning or RL, using only a small sample of nodes from a single graph. Both approaches generalize well and beat the Greedy Forwarding method. The metric used for evaluating routing approaches is the percentage of node pairs for which the evaluated approach finds a path with length within a multiplicative constant from the true shortest path length. I have not found information on what the constant is.

The authors also analyze what the network has learned. If only the distance feature is used, the network learns to mimic the Greedy Forwarding algorithm (which is nice, but not very surprising, see, e.g., "A new dog learns old tricks (...)" ICLR'19 paper). When both features are used, the network's behavior can be approximated with a piecewise linear function with only 2 pieces.

This work presents a novel idea of deriving local routing policies using MDP formulation and small set of random graphs in Euclidean and hyperbolic metric spaces. The idea is supported by theories and their proof. The local routing policy can be trained by two methods: 1) supervised learning with shortest path distance known or 2) deep reinforcement learning. Experimental results show that the trained policy outperforms the greedy routing algorithm.

This paper studies the problem of finding approximate all-pair shortest paths for 2D Euclidean and Hyperbolic random graphs. Specifically, the shortest paths should be returned in a localized way, such that given source and destination s and t and an intermediate vertex v, it returns the next “hop” from v towards the nearly-shortest path to the destination.

The motivation to consider the two types of random graphs is that they are good models for capturing sensor networks and social networks.

At a high level, the proposed method is for every vertex v find a ranking of the neighbors of v using DNN. The crucial claim is that, if there exists a good enough linear ranking metric, then simply learning on a single seed graph would generalize to all graphs. Then the next step is to construct such a ranking metric for the two special graph families (i.e., Euclidean and Hyperbolic). The step of finding a ranking metric is via heuristic methods that are tested in the experiments.

The authors consider the problem of learning a local routing policy in a graph. This policy uses only information available at a node and its surrounding nodes. The authors present some results regarding conditions under which it is possible to learn the optimal ranking policy given a set of features. The authors formulate the routing problem as a deterministic Markov decision process, and propose a supervised learning procedure that estimates the optimal Q-values of a seed graph. The authors provide some computational experiments comparing the effectiveness of this procedure to a reinforcement learning approach and a greedy forwarding approach.

We thank all the reviewers for the insightful comments. Below we first clarify several common questions about our theoretical results and then provide a detailed response to each reviewer.

[RankPres property]

We agree with the reviewers that RankPres property is a strong assumption in theory. However, we would like to point out that our theory is mainly developed to explain the superior generalization performance of the learned neural network model in practice. In fact, in our algorithm design and also stated in Appendix B, we consider the ranking metric based on distance for greedy forwarding and distance and node stretch for our algorithm. By comparing the order of $m$ and the order of $Q^*$ based on DCG, we show in Figure 4-11 that RankPres property indeed holds for most nodes and most graphs across different size and density/average node degree, which is the reason that the learned neural network can generalize well across different graphs. Therefore, we seek to use our theoretical results to explain why generalization is possible when RankPres property holds. But in practice, good generalization performance can still be achieved even if this property only holds for most nodes and graphs, as demonstrated in our experimental results

[Interpretation of “learnable”]

Theorems 0, 1, and 2 assume (perfect) correlation of the local ranking metric $m: f_{s} \times f_{a} \rightarrow \mathbb{R}$ and the global ranking metric $Q^*$ across nodes and graphs. In Theorem 1 (respectively, 2), our objective is to learn a function, $m’: f_{s} \times f_{a} \rightarrow Q$, that maximizes the number of nodes satisfying the RankPres property in a graph (respectively, across random graphs of some sort). Note that $m$ and $m’$ achieve the same ranking order across nodes and graphs.

[Interpretation and correctness of Theorem 1 and 2]

In Theorem 1, if there exists $m()$ that satisfies the RankPres property for all nodes, then some function $m’: f_{s} \times f_{a} \rightarrow Q$ can be learned with a subset of nodes $V'$, where $V^′ \subseteq V$ and $|V^′| \geq 1$. Note that it is sufficient to learn $m’$ with the training samples derived at least from one node $v$ with the highest degree (degree($v$)>1) and that satisfies the RankPres property for all nodes. Thus both $m$ and $m’$ can serve as an optimal ranking policy. The proof is as follows.

[Monotonicity of the learned function]

RankPres implies that given $Q^*$ values for any node $v$ and its neighbors $u_1$, $u_2$, … to have an increasing order, $m(f_{s}(O, D, v), f_{a}(O, D, u_1))$, $m(f_{s}(O, D, v), f_{a}(O, D, u_2))$, … are in the same increasing order. Let us learn a function $m’: f_{s} \times f_{a} \rightarrow Q$ for some nodes $v’ \in V’$ such that $m’$ is monotonic non-decreasing, which is feasible cf. [1], for nodes $v’$ and its neighbors with respect to their increasing $Q^*$ values. Now test the function $m’$ on some nodes $v’’ \in V \setminus V’$ and its neighbors $u1’’$, $u2’’$, …. Without loss of generality, let us assume that $m(f_{s}(O, D, v’’), f_{a}(O, D, u_1’’))$, $m(f_{s}(O, D, v’’), f_{a}(O, D, u_2’’))$, … are in monotonic non-decreasing order. Since $m’$ is monotonic non-decreasing, for this neighbor ordering, by definition their $Q$ values (i.e., the output of the function $m’$ will also preserve the same order. Hence, both $m()$ and $m’()$ preserve the RankPres property for all the nodes.

[1] Sill, Joseph. "Monotonic networks." Advances in Neural Information Processing Systems 10 (1997).

In Theorem 2, if there exists $m()$ that satisfies the RankPres property for the nodes in all graphs, then a function $m’: f_{s} \times f_{a} \rightarrow Q$ can be learned by using training samples from one or more nodes in one or more chosen seed graph(s) $G^*$. It is sufficient to learn $m’()$ with the training samples derived at least from a node with the highest degree in the seed graph $G^*$. Both $m()$ and $m’()$ can serve as the optimal ranking policy.

[Linearity of the ranking metric]

We thank the reviewers to bring up the assumption on linearity of the ranking metric. In fact, the ranking metric $m()$ can be linear or nonlinear. Our results hold as long as $m()$ is monotonic and we will remove the assumption on linear $m()$. So instead of using linear regression, we apply neural networks to learn $m’()$ to maximize the number of nodes that achieve optimal routing for a given pair $(O, D)$ by using $m’()$. This is illustrated by Figure 3 which shows the nonlinearity of $m’()$ learned for the GreedyTensile policy. Besides, the learned ranking metric using neural networks outperforms the one using linear regression in terms of the APNSP prediction accuracy.

The authors study the problem of learning local routing strategies in a graph. In particular, they first reformulate the problem as a deterministic Markov decision process then provide a learning algorithm for it. They also provide theoretical and experimental results showing the effectiveness of their algorithm.

Overall, the paper contains some interesting ideas but it is not ready for publication at this stage. More specifically, the reviewers highlighted the following weaknesses:

• The assumption in the theoretical results are too strong and a bit hard to parse

• The presentation of the mathematical results should be improved

• The comparison with previous work is not particularly satisfying

Reject