Cover Image

Graph neural networks extrapolate out-of-distribution for shortest paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nerem, Robert R., Chen, Samantha, Dasgupta, Sanjoy, Wang, Yusu
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New bounds on the cohesion of complete-link and other linkage methods for agglomeration clustering
by: Dasgupta, Sanjoy, et al.
Published: (2024)

Which Algorithms Can Graph Neural Networks Learn?
by: Wittig, Solveig, et al.
Published: (2026)

Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations
by: Nerem, Robert R., et al.
Published: (2024)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks
by: Roy, Shubhajit, et al.
Published: (2023)

Faster negative length shortest paths by bootstrapping hop reducers
by: Huang, Yufan, et al.
Published: (2025)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
by: Maity, Binita, et al.
Published: (2024)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Performance bounds for nearest neighbor search with k-d trees
by: Bazzani, Marco, et al.
Published: (2026)

Deterministic Coreset for Lp Subspace
by: Chhaya, Rachit, et al.
Published: (2026)

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks
by: Abbe, Emmanuel, et al.
Published: (2022)

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)

Solving the all pairs shortest path problem after minor update of a large dense graph
by: Liu, Gangli
Published: (2024)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

Unrolled denoising networks provably learn optimal Bayesian inference
by: Karan, Aayush, et al.
Published: (2024)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
by: Chen, Hongjie, et al.
Published: (2024)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
by: Chen, Hongjie, et al.
Published: (2025)

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
by: Kasperski, Adam, et al.
Published: (2024)

Learning Augmented Graph $k$-Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Incremental (k, z)-Clustering on Graphs
by: Cruciani, Emilio, et al.
Published: (2026)

Expander Hierarchies for Normalized Cuts on Graphs
by: Hanauer, Kathrin, et al.
Published: (2024)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

On the query complexity of sampling from non-log-concave distributions
by: He, Yuchen, et al.
Published: (2025)

Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio
by: Yoshinaga, Toru, et al.
Published: (2026)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Space of Data through the Lens of Multilevel Graph
by: Caputo, Marco, et al.
Published: (2025)

GEFL: Extended Filtration Learning for Graph Classification
by: Zhang, Simon, et al.
Published: (2024)

Distribution Learning Meets Graph Structure Sampling
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

Dynamic Similarity Graph Construction with Kernel Density Estimation
by: Laenen, Steinar, et al.
Published: (2025)

Exact Learning of Weighted Graphs Using Composite Queries
by: Goodrich, Michael T., et al.
Published: (2025)

Learning on the Edge: Online Learning with Stochastic Feedback Graphs
by: Esposito, Emmanuel, et al.
Published: (2022)

DRESS: A Continuous Framework for Structural Graph Refinement
by: Velilla, Eduar Castrillo
Published: (2026)

Efficient distributional regression trees learning algorithms for calibrated non-parametric probabilistic forecasts
by: Duchemin, Quentin, et al.
Published: (2025)

Beyond Spectral Clustering: Probabilistic Cuts for Differentiable Graph Partitioning
by: Ghriss, Ayoub
Published: (2025)