Pith. sign in

REVIEW 5 major objections 5 minor 35 references

Knowledge-Guided Machine Learning for Stabilizing Near-Shortest Path Routing

T0 review · 5 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A neural network trained on data from three nodes of a single seed graph generalizes across random geometric graphs and beats greedy forwarding on near-shortest path accuracy.

desk verdict A plausible few-shot routing result that deserves a referee, but the zero-shot claim is under-validated and the theory is scaffolding rather than proof. read the letter →

arxiv 2509.06640 v1 pith:UMWN3DXP submitted 2025-09-08 cs.LG cs.NI

Yung-Fu Chen , Sen Lin , Anish Arora This is my paper · ORCID
classification cs.LGcs.NI
keywords few-shotlearninglocalroutingpolicyall-pairsnear-shortestpathgeometricrandomgraphsGreedyTensilezero-shotgeneralizationrankingmetricsself-stabilizing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that local routing for the all-pairs near-shortest path problem—finding a path between every node pair within a small factor of the shortest-path length—can be learned from a few samples taken from a single 50-node seed graph, and that the learned policy transfers without retraining to other uniform random geometric graphs. The key move is to inject domain knowledge into the learning: choose input features that are known to matter (distance to destination and node stretch), and choose a seed graph and nodes whose local neighbor ranking matches the globally optimal ranking. Under two sufficient conditions, Pointwise Monotonicity and RankPres, the paper proves that a DNN ranking metric is learnable from few samples and generalizes across nodes and graphs; Proposition 1 asserts that linear metrics over those features satisfy the conditions for almost all graphs, and the paper validates this empirically. The resulting GreedyTensile policy improves all-pairs near-shortest path accuracy over Greedy Forwarding by up to 12.22%, and the learned DNN can be interpreted as a low-complexity two-linear-action rule.

What carries the argument

The ranking metric m(fs(v), fa(u)) is the central object: a function of the current node's state features and a neighbor's action features that produces a score used to select the next forwarder. Two sufficient conditions carry the argument: Pointwise Monotonicity (the metric respects the pointwise ordering of feature vectors, making it learnable by a DNN) and RankPres (the local metric's neighbor ranking matches the global Q-value ranking, making the learned policy optimal). The paper instantiates m as a linear function of distance-to-destination d(u,D) and node stretch ns(O,D,u), selects a seed graph and a subsample of nodes with high ranking similarity, trains a DNN to approximate Q-value

What would settle it

On uniform random geometric graphs with 216 nodes and density 2, compute the true shortest-path Q-values and compare the neighbor ranking produced by m2 = -0.875*d(u,D) - 0.277*ns(O,D,u) against the optimal ranking. If the average ranking similarity falls substantially below the about-0.9 level reported for other densities, or if a GreedyTensile-S model trained as described shows no accuracy gain over Greedy Forwarding on those graphs, the Proposition 1 assumption and the zero-shot generalization claim would be falsified.

Watch

Extended reading notes

Core claim

The central claim is that sample-efficient, zero-shot generalizable routing is achievable for uniform random geometric graphs: a DNN trained on a few nodes (phi=3) of one seed graph learns a local forwarding policy that, for almost all graphs in the class, selects a neighbor that leads to a near-shortest path. The engine is a pair of sufficient conditions—Pointwise Monotonicity and RankPres—that let a local ranking metric stand in for the globally optimal Q-values; Proposition 1 asserts that linear metrics over distance-to-destination and node stretch satisfy these conditions for almost all nodes in almost all graphs. The paper validates Proposition 1 with ranking-similarity measurements, th

Load-bearing premise

The generalization argument rests on the assumption that, for almost every node in almost every graph in the class, a simple linear scoring rule ranks neighboring nodes in the same order as the true optimal routing scores; the paper checks this with ranking-similarity measurements for two hand-picked scoring rules rather than proving it.

Editorial extensions

If this is right

  • A single training effort on one seed graph suffices for routing on any uniform random geometric graph in the tested range, so topology changes require no retraining.
  • GreedyTensile's accuracy gain over Greedy Forwarding grows with density, making it most valuable in dense deployments where greedy forwarding was previously thought to be close to optimal.
  • The symbolic two-linear-action form lets the learned policy run with fewer than ten multiplications per forwarding decision, suitable for low-power or embedded nodes.
  • The reinforcement-learning variant achieves comparable generalization without access to optimal shortest-path values, extending the approach to settings where optimal labels are unavailable.
  • Because forwarding decisions depend only on local state, the policy is self-stabilizing after crashes or topology changes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: the same few-sample recipe may carry over to non-uniform or clustered node distributions, since the theory only needs a linear ranking metric with high RankPres similarity for that class; uniformity enters through the empirical validation of Proposition 1, not through the proof.
  • Inference: the two-linear-action interpretation suggests the DNN's decision boundary could be replaced by a closed-form threshold in (d(u,D), ns(O,D,u)) space, which might be derived analytically from the geometry of the elliptical search region.
  • Inference: seed-graph selection could be automated online by treating measured ranking similarity as a model-selection score, letting a deployment choose better seed graphs as it encounters them instead of relying on a pre-selected one.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper proposes knowledge-guided machine learning for the all-pairs near-shortest path (APNSP) problem on uniform random geometric graphs. A DNN is trained from a very small number of samples (ϕ=3 nodes) of a single seed graph to learn a local forwarding policy. Two feature sets are considered: distance-to-destination only, and distance-to-destination plus node stretch. The latter yields a new policy, GreedyTensile, claimed to zero-shot generalize across graph sizes 27–216 and densities 2–5 in Euclidean space (and also in hyperbolic space), improving APNSP accuracy over greedy forwarding by up to 12.22%. The paper also presents theoretical conditions, Pointwise Monotonicity and RankPres, intended to explain learnability and generalizability, and a symbolic two-linear-action interpretation of the learned policy.

Significance. If the empirical claim holds, this is a significant result: it suggests that a local routing policy can be learned from a tiny amount of data on a single graph and transferred across a parametric family of random geometric graphs, while remaining explainable and low-complexity. The rediscovery of Greedy Forwarding from a distance-only DNN is an elegant sanity check, and the symbolic interpretation is a useful contribution. However, the theoretical framework is largely definitional: the lemmas follow almost by construction from RankPres and Pointwise Monotonicity, and the load-bearing existence claim (Proposition 1) is only empirically validated with a hand-chosen linear metric. The central few-shot generalization claim is additionally supported by only a single seed graph and a single node subsample, with no variance analysis. These gaps are fixable but currently limit the paper's contribution.

major comments (5)
  1. [Appendix A.2 (proof of Lemma 1)] The proof asserts that 'Since H satisfies Pointwise Monotonicity, for this neighbor ordering, by definition, the outputs of H will also be in the same order as that of Q.' This does not follow from Definition 2, which constrains H only when the feature vectors are pointwise ordered. The Q-ordering of neighbors does not imply such a pointwise ordering. Additionally, H trained on a subset V' is not argued to reproduce m on all of V. This invalidates the cross-node generalizability argument as written and is load-bearing for the cross-graph generalization claim.
  2. [Proposition 1 and Appendix B] The existence of ranking metrics m1 and m2 satisfying RankPres and Pointwise Monotonicity is asserted for 'almost all nodes in almost all graphs', but no proof is provided. Appendix B selects m1 = -d(u,D) and m2 = -0.875 d(u,D) - 0.277 ns(O,D,u) and reports DCG-based ranking similarities. High SIM_G(m,Q*) is not equivalent to RankPres (Definition 3), and the weights in m2 are given without showing how they were obtained or whether they are stable across the tested configurations. Since Proposition 1 is the premise for Lemmas 1 and 2, either a rigorous derivation under the stated random graph model or a clear reframing as empirical evidence with confidence bounds is needed.
  3. [Section 6.2 and Abstract] The abstract claims that the distance-only DNN 'learns a policy that exactly matches the well-known Greedy Forwarding policy.' The experimental section only reports that 'the performance of all the learned policies exactly match the prediction accuracy of GF.' Accuracy equality does not imply policy identity: two policies can agree on overall accuracy across 80 graphs while differing on individual forwarding decisions. Please verify action-level agreement with GF, or soften the claim.
  4. [Section 6.2 and Table 3] The zero-shot generalization claim is based on one seed graph (size 50, density 5) and one subsample of ϕ=3 nodes. No variation across seed graphs or node subsets is reported, and the 80-graph averages have no error bars or confidence intervals. Given that Appendix B shows the seed graph selection matters (e.g., Figures 5 and 7), the reported 12.22% improvement may be specific to that seed. Please provide results over multiple seed graphs and multiple subsamples, with variance estimates, or otherwise justify representativeness of the chosen seed.
  5. [Theorem 1 (Section 4.1)] Theorem 1 states that Pointwise Monotonicity implies the existence of a DNN H that learns m from samples, but the proof is deferred to a citation to [24] without a self-contained construction. Since the DNN architecture used later has no explicit monotonicity constraints, it is not clear that the theorem applies to the actual learning procedure. Please provide an explicit argument or state the additional assumptions needed for the learned H to inherit the monotonicity of m.
minor comments (5)
  1. [Figure 3] Error bars or per-graph variance should be shown; with only averages over 80 graphs, the reader cannot assess the reliability of the reported improvements.
  2. [Appendix D.1] It is ambiguous whether the hyperbolic-space results use the same Euclidean-trained policy or a policy trained on hyperbolic seed graphs. Please clarify the training protocol for Figure 8.
  3. [Notation] The name 'Greedy Tensile' is written inconsistently as 'GreedyTensile' in most of the text and figures; please standardize.
  4. [Appendix B] The DCG definition uses zero-based indices in rel_A[i] but the DCG sum uses one-based indices; this is minor but should be cleaned up.
  5. [Equation (2)] The margin parameter ϵ is used in the definition of η but not introduced until later. Please define it at first use.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the learning-theoretic statements are conditional, the ranking-metric existence is empirically checked rather than derived from the target claim, and the empirical generalization results are measured on held-out graphs.

full rationale

The paper's core theory (Theorem 1, Lemmas 1-2, Theorem 2) is explicitly conditional: it states that IF a ranking metric m satisfies Pointwise Monotonicity and RankPres, THEN a DNN can learn m from limited samples and the resulting ranking matches the optimal Q-ranking. RankPres is defined as the agreement between m's ranking and Q's ranking, so the lemmas largely unpack the definition; this is a valid sufficient-condition argument, not a circular derivation of the target conclusion from itself. The load-bearing existence claim is Proposition 1, which is not proven but is empirically checked in Appendix B by measuring DCG ranking similarity for two concrete linear metrics: m1 = -d(u,D) and m2 = -0.875d(u,D)-0.277ns(O,D,u). Even though the m2 weights appear to be fitted to the same graph class, this evidence supports the antecedent of the conditional theory; it does not by itself define the learned DNN. The DNN is trained on actual optimal Q-values from a seed graph (Eq. 3), not on m2, so the reported APNSP accuracies on held-out graphs (sizes 27-216, densities 2-5) are independent measurements rather than fitted quantities. The distance-only DNN matching Greedy Forwarding is an empirical finding, not a renaming. The self-citation to QF-Geo [5] motivates the node-stretch feature and the elliptical-region reward, but Section 5.1 independently identifies node stretch via decision-tree and symbolic-regression feature selection, so the central claim does not reduce to that citation. The genuine limitations — Proposition 1 lacking a formal proof, DCG similarity being weaker than the strict RankPres condition, and no multi-seed variance reporting — are evidence/rigor concerns, not circularity. Thus the appropriate finding is no significant circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim relies on the empirical existence of a ranking metric (Proposition 1) which is validated only via fitted linear functions, and on the choice of a favorable seed graph. No new physical entities are postulated.

free parameters (3)
  • Ranking metric m2 weights = -0.875, -0.277
    Chosen to maximize ranking similarity SIM_G(m,Q*) in Appendix B.2; used to empirically validate Proposition 1.
  • Two-linear-action policy weights = Eq. 6: -0.01, -0.02, -0.01, -0.06, 0.03, -0.04, -0.15; threshold 1.02, 0.57, -0.69
    Fitted via linear regression to approximate the learned DNN in Appendix E.
  • Seed graph configuration = size 50, density 5
    Chosen based on Figure 7 as a 'good seed' with high SIM_G; the choice affects generalization and is not derived from first principles.
assumptions (4)
  • domain assumption Uniform random geometric graphs in Euclidean space represent wireless network topologies.
    Stated in Section 1 to justify applicability to real-world wireless networks.
  • domain assumption Elliptical Region for Bounded Search (from QF-Geo [5]) is valid for the graph class.
    Used to design the reward function in Section 3.2 and the node stretch feature.
  • ad hoc to paper Existence of a ranking metric m satisfying RankPres and Pointwise Monotonicity for almost all graphs in G (Proposition 1).
    Asserted in Section 4.3 and only empirically validated in Appendix B with fitted linear functions; it is the key premise for the theoretical generalizability guarantee.
  • standard math DNN can learn monotonic ranking (universal approximation with monotonicity) [24].
    Used in Theorem 1 proof, citing Sill's monotonic networks.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Knowledge-Guided Machine Learning for Stabilizing Near-Shortest Path Routing." pith.science (2026). https://pith.science/paper/UMWN3DXP

@misc{pith2026250906640,
  author       = {Pith},
  title        = {Pith review of: Knowledge-Guided Machine Learning for Stabilizing Near-Shortest Path Routing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UMWN3DXP}},
  note         = {Machine review of arXiv:2509.06640}
}
read the original abstract

We propose a simple algorithm that needs only a few data samples from a single graph for learning local routing policies that generalize across a rich class of geometric random graphs in Euclidean metric spaces. We thus solve the all-pairs near-shortest path problem by training deep neural networks (DNNs) that let each graph node efficiently and scalably route (i.e., forward) packets by considering only the node's state and the state of the neighboring nodes. Our algorithm design exploits network domain knowledge in the selection of input features and design of the policy function for learning an approximately optimal policy. Domain knowledge also provides theoretical assurance that the choice of a ``seed graph'' and its node data sampling suffices for generalizable learning. Remarkably, one of these DNNs we train -- using distance-to-destination as the only input feature -- learns a policy that exactly matches the well-known Greedy Forwarding policy, which forwards packets to the neighbor with the shortest distance to the destination. We also learn a new policy, which we call GreedyTensile routing -- using both distance-to-destination and node stretch as the input features -- that almost always outperforms greedy forwarding. We demonstrate the explainability and ultra-low latency run-time operation of Greedy Tensile routing by symbolically interpreting its DNN in low-complexity terms of two linear actions.

Figures

Figures reproduced from arXiv: 2509.06640 by the authors.

Figure 1
Figure 1. A comparison of different (machine learned) routing policies for the per-hop best forwarder prediction for all-pair near shortest path problem (APNSP). 2 Related Work 2.1 Feature Selection for Local Routing A classic feature for local routing comes from Greedy Forwarding [6], in which the distance to the destination node is used to optimize forwarder selection. It has been proven that this feature achieves nearly op… view at source ↗
Figure 2
Figure 2. Schema for solution using DNN to predict Q-value for selecting the routing forwarder. in the problem, the state transition is assumed to be deterministic. Specifically, each state s represents the features of a node v holding a packet associated with an origin-destination pair (O, D), and an action a ∈ A = nbr(v) indicates the routing behavior to forward the packet from node v to one of its neighbors u ∈ nbr(v), whe… view at source ↗
Figure 3
Figure 3. Average APNSP prediction accuracy across graph sizes with various ρ in Eu￾clidean space for Greedy Tensile policies. To evaluate the scalability and generalizability of the policies, we directly (i.e., without any adaptation) test the policies learned from the seed graph G∗ [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Distribution of SIMv(m, Q∗ ) given a uniform random graph in the Euclidean space with random seed (rnd), where m is the ranking metric for distance-to-destination d(u, D). In [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]
Figure 5
Figure 5. Figure 5: Distribution of SIMG(m, Q∗ ) across 100 uniform random graphs in the Eu￾clidean space, where m is the ranking metric for distance-to-destination d(u, D). (a) Size 50, Density 3, rnd=19 (b) Size 50, Density 5, rnd=19 (c) Size 100, Density 3, rnd=48 (d) Size 100, Den￾sit…
Figure 6
Figure 6. Figure 6: Distribution of SIMv(m, Q∗ ) given a uniform random graph in the Euclidean space with a random seed (rnd), where m is the ranking metric for distance-to￾destination d(u, D) and node stretch ns(O, D, u). in the Euclidean space. Note that in high density Euclidean graphs…
Figure 7
Figure 7. Figure 7: Distribution of SIMG(m, Q∗ ) across 100 uniform random graphs in the Eu￾clidean space, where m is the ranking metric for distance-to-destination d(u, D) and node stretch ns(O, D, u). B.2 Ranking Similarity with Distance-To-Destination and Node Stretch Input Features We…
Figure 8
Figure 8. Figure 8: Average APNSP prediction accuracy across graph sizes with various δ in hy￾perbolic space for Greedy Tensile policies. (a) GreedyTensile-S (b) GreedyTensile-RL [PITH_FULL_IMAGE:figures/full_fig_p025_8.png]
Figure 9
Figure 9. Figure 9: Average APNSP prediction accuracy across graph sizes with various ρ in Eu￾cldiean space for Greedy Tensile policies with and without graph subsampling. Evaluation Results. In hyperbolic space, we apply the same network configu￾ration as in [PITH_FULL_IMAGE:figures/ful…
Figure 10
Figure 10. Figure 10: The shape of ranking metrics of the Greedy Tensile DNN and its two-linear action Symbolic Approximation policy, given s(O, D, v) = 1.2 and d(v, D) = 4. The x and y axes represent s(O, D, u) and d(u, D), and the z axis is the ranking metric for routing. In this section…
Figure 11
Figure 11. Figure 11: APNSP prediction accuracy for the two-linear-action policy in Equation 6 versus the policies of Greedy Tensile (Supervised (ϕ = 3)) and greedy forwarding (GF) over graphs in the Euclidean space with size 50 and density in {2, 3, 4, 5}. The simplified two-linear-action…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 31 canonical work pages

  1. [24]

    Advances in neural information processing systems 10(1997)

    Sill, J.: Monotonic networks. Advances in neural information processing systems 10(1997)

    work page 1997

  2. [1]

    Computer Physics Communications196, 492–496 (2015)

    Aldecoa, R., Orsini, C., Krioukov, D.: Hyperbolic graph generator. Computer Physics Communications196, 492–496 (2015)

    work page 2015

  3. [2]

    In: Advances in Neural Information Processing Systems 35: Annual Conference on Neural Infor- mation Processing Systems (NeurIPS) (2022)

    Bi, J., Ma, Y., Wang, J., Cao, Z., Chen, J., Sun, Y., Chee, Y.M.: Learning general- izable models for vehicle routing problems via knowledge distillation. In: Advances in Neural Information Processing Systems 35: Annual Conference on Neural Infor- mation Processing Systems (NeurIPS) (2022)

    work page 2022

  4. [3]

    In: Classification, clustering, and data analysis: recent advances and applications, pp

    Billard, L., Diday, E.: Symbolic regression analysis. In: Classification, clustering, and data analysis: recent advances and applications, pp. 281–288. Springer (2002)

    work page 2002

  5. [4]

    Nature Communications1(1), 62 (2010)

    Boguná, M., Papadopoulos, F., Krioukov, D.: Sustaining the internet with hyper- bolic mapping. Nature Communications1(1), 62 (2010)

    work page 2010

  6. [5]

    QF-Geo: Capacity Aware Geographic Routing using Bounded Regions of Wireless Meshes

    Chen, Y.F., Parker, K.W., Arora, A.: QF-Geo: Capacity aware geographic routing using bounded regions of wireless meshes. arXiv preprint arXiv:2305.05718 (2023)

    work page Pith review arXiv 2023

  7. [6]

    Finn, G.G.: Routing and addressing problems in large metropolitan-scale internet- works. Tech. rep., University of Southern California Marina Del Rey Information Sciences Inst (1987)

    work page 1987

  8. [7]

    Information and Control10(5), 447–474 (1967)

    Gold, E.M.: Language identification in the limit. Information and Control10(5), 447–474 (1967)

    work page 1967

Show all 35 references
  1. [8]

    IEEE/ACM Transactions on Networking10(4), 477–486 (2002)

    Grossglauser, M., Tse, D.N.: Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Transactions on Networking10(4), 477–486 (2002)

    2002

  2. [9]

    In: Pro- ceedings of the 22nd ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining

    Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Pro- ceedings of the 22nd ACM SIGKDD International Conference on Knowledge Dis- covery and Data Mining. pp. 855–864 (2016)

    2016

  3. [10]

    Wireless Networks10, 389–399 (2004)

    Hekmat, R., Van Mieghem, P.: Interference in wireless multi-hop ad-hoc networks and its effect on network capacity. Wireless Networks10, 389–399 (2004)

    2004

  4. [11]

    IEEE Transactions on Communications34(1), 38–44 (1986)

    Hou, T.C., Li, V.: Transmission range control in multihop packet radio networks. IEEE Transactions on Communications34(1), 38–44 (1986)

    1986

  5. [12]

    arXiv preprint arXiv:2110.05291 (2021)

    Hudson, B., Li, Q., Malencia, M., Prorok, A.: Graph neural network guided lo- cal search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291 (2021)

    2021 arXiv

  6. [13]

    ACM Transactions on Information Systems (TOIS)20(4), 422–446 (2002)

    Järvelin, K., Kekäläinen, J.: Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems (TOIS)20(4), 422–446 (2002)

    2002

  7. [14]

    Nature406(6798), 845–845 (2000)

    Kleinberg, J.M.: Navigation in a small world. Nature406(6798), 845–845 (2000)

    2000

  8. [15]

    In: Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG 1999), Vancouver, Au- gust (1999)

    Kranakis, E.: Compass routing on geometric networks. In: Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG 1999), Vancouver, Au- gust (1999)

    1999

  9. [16]

    Manfredi, V., Wolfe, A., Zhang, X., Wang, B.: Learning an adaptive forwarding strategyformobilewirelessnetworks:Resourceusagevs.latency.In:Reinforcement Learning for Real Life (RL4RealLife) Workshop in the 36th Conference on Neural Information Processing Systems (NeurIPS) (2022)

    2022

  10. [17]

    In: 2021 IEEE 22nd International Sym- posium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)

    Manfredi, V., Wolfe, A.P., Wang, B., Zhang, X.: Relational deep reinforcement learning for routing in wireless networks. In: 2021 IEEE 22nd International Sym- posium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM). pp. 159–168 (2021)

    2021

  11. [18]

    Philosophical Transactions of the Royal Society A381(2251), 20220046 (2023)

    Muggleton,S.:Hypothesizinganalgorithmfromoneexample:theroleofspecificity. Philosophical Transactions of the Royal Society A381(2251), 20220046 (2023)

    2023

  12. [19]

    In: International Conference on In- ductive Logic Programming

    Muggleton, S.: Learning from positive data. In: International Conference on In- ductive Logic Programming. pp. 358–376. Springer (1996) Knowledge-Guided Machine Learning for APNSP xvii

    1996

  13. [20]

    arXiv preprint arXiv:1707.05005 (2017)

    Narayanan, A., Chandramohan, M., Venkatesan, R., Chen, L., Liu, Y., Jaiswal, S.: graph2vec: Learning distributed representations of graphs. arXiv preprint arXiv:1707.05005 (2017)

    2017 arXiv

  14. [21]

    IEEE Transactions on Communications32(6), 684– 694 (1984)

    Nelson, R., Kleinrock, L.: The spatial capacity of a slotted aloha multihop packet radio network with capture. IEEE Transactions on Communications32(6), 684– 694 (1984)

    1984

  15. [22]

    In: IEEE IN- FOCOM

    Papadopoulos, F., Krioukov, D., Boguná, M., Vahdat, A.: Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In: IEEE IN- FOCOM. pp. 1–9 (2010)

    2010

  16. [23]

    In: 2019 International Joint Conference on Neural Networks (IJCNN)

    Reis, J., Rocha, M., Phan, T.K., Griffin, D., Le, F., Rio, M.: Deep neural networks for network routing. In: 2019 International Joint Conference on Neural Networks (IJCNN). pp. 1–8. IEEE (2019)

    2019

  17. [25]

    IEEE Transactions on Communications32(3), 246–257 (1984)

    Takagi, H., Kleinrock, L.: Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications32(3), 246–257 (1984)

    1984

  18. [26]

    The Linux Foundation: PyTorch 2.6.0 (2025), https://pytorch.org/get- started/pytorch-2.x/

    2025

  19. [27]

    Communications of the ACM27(11), 1134–1142 (1984)

    Valiant, L.G.: A theory of the learnable. Communications of the ACM27(11), 1134–1142 (1984)

    1984

  20. [28]

    In: Proceedings of the thirtieth annual symposium on Computational geometry

    Verbeek, K., Suri, S.: Metric embedding, hyperbolic space, and social networks. In: Proceedings of the thirtieth annual symposium on Computational geometry. pp. 501–510 (2014)

    2014

  21. [29]

    ACM computing surveys (csur)53(3), 1–34 (2020)

    Wang, Y., Yao, Q., Kwok, J.T., Ni, L.M.: Generalizing from a few examples: A survey on few-shot learning. ACM computing surveys (csur)53(3), 1–34 (2020)

    2020

  22. [30]

    IEEE Transactions on Neural Networks and Learning Systems33(9), 5057–5069 (2021)

    Wu, Y., Song, W., Cao, Z., Zhang, J., Lim, A.: Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems33(9), 5057–5069 (2021)

    2021

  23. [31]

    In: Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems (NeurIPS)

    Xin, L., Song, W., Cao, Z., Zhang, J.: NeuroLKH: Combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem. In: Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems...

    2021

  24. [32]

    Xue, F., Kumar, P.R.: Scaling laws for ad hoc wireless networks: an information theoretic approach. Now Publishers Inc (2006) A Proofs for Learnability and Generalizability In this section, we provide the proof of the theorems of generalizability and learnability stated in Section 4

    2006

  25. [33]

    Proof of Theorem 1. Proof.The theorem follows directly from a construction [24] that demon- strates the learnability of neural networks when there exists a monotonic mapping,H, from the input vector to the output value. We note that Pointwise Monotonicity ofmalways holds for a...

  26. [34]

    Proof.Our objective is to learn from a sample subset⟨X V ′, YV ′⟩a DNN, H:f s ×f a →R, that satisfies RankPres property for all nodes in a graph

    Proof of Lemma 1. Proof.Our objective is to learn from a sample subset⟨X V ′, YV ′⟩a DNN, H:f s ×f a →R, that satisfies RankPres property for all nodes in a graph. Since there existsm()for which RankPres holds for all nodes, then from Theorem 1, a DNNH:f s ×f a →Rcan be learne...

  27. [35]

    Proof of Lemma 2. Proof.If there existsm()that satisfies RankPres property for the nodes in all graphs, then a DNNH:f s ×f a →Rcan be learned by using training samples from one or more nodes in one or more chosen seed graph(s)G∗. It is sufficient to learnHwith the training sam...

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.