Metric Graph Kernels via the Tropical Torelli Map
This work addresses graph comparison problems in machine learning, particularly for applications like urban road network classification, though it appears to be an incremental improvement with a novel geometric approach.
The authors tackled the problem of graph comparison by proposing new graph kernels based on metric graph geometry and topology rather than conventional combinatorial features, achieving superior performance over existing methods in label-free settings on synthetic and real-world benchmarks.
We propose new graph kernels grounded in the study of metric graphs via tropical algebraic geometry. In contrast to conventional graph kernels that are based on graph combinatorics such as nodes, edges, and subgraphs, our 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 that represent different underlying spaces. We develop efficient algorithms for computing these kernels and analyze their complexity, showing that it depends primarily on the genus of the input graphs. Empirically, our kernels outperform existing methods in label-free settings, as demonstrated on both synthetic and real-world benchmark datasets. We further highlight their practical utility through an urban road network classification task.