Anthea Monod: Topological Graph Kernels from Tropical Geometry

Abstract.

We introduce a new class of graph kernels for machine learning with metric graphs based on tropical geometry and the graph topologies. Unlike traditional graph kernels that are defined by graph combinatorics (nodes, edges, subgraphs), our approach considers only the geometry and topology of the underlying metric space. A key property of our construction is its invariance under edge subdivision, making the kernels intrinsically well-suited for comparing graphs that represent different underlying spaces. Our kernels are efficient to compute and depend only on the graph genus rather than the size. In label-free settings, our kernels outperform existing methods, which we showcase on synthetic, benchmarking, and real-world road network data. Joint work with Yueqi Cao (KTH Sweden).