2025/05/17 by Yueqi Cao, Anthea Monod, Cao, Yueqi +1 · 1 citation
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Methodology (stat.ME)
paper · pdf · doi:10.48550/arxiv.2505.12129
openalex publication_date 2025/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the first graph kernels for metric graphs via tropical algebraic geometry. In contrast to conventional graph kernels based on graph combinatorics such as nodes, edges, and subgraphs, our metric graph kernels are purely based on the geometry and topology of the underlying metric space. A key characterizing property of our construction is its invariance under edge subdivision, making the kernels intrinsically well-suited for comparing graphs representing different underlying metric spaces. We develop efficient algorithms to compute our kernels and analyze their complexity, which depends primarily on the genus of the input graphs rather than their size. Through experiments on synthetic data and selected real-world datasets, we demonstrate that our kernels capture complementary geometric and topological information overseen by standard combinatorial approaches, particularly in label-free settings. We further showcase their practical utility with an urban road network classification task.