Metric Graph Kernels via the Tropical Torelli Map

Yueqi Cao, Anthea Monod

TL;DR

This paper introduces the first graph kernels designed specifically for metric graphs (graphs with continuous edge lengths) by leveraging the tropical Torelli map from tropical algebraic geometry. Unlike traditional combinatorial kernels, these new kernels are invariant under edge subdivision, making them uniquely suited for comparing continuous geometric spaces—like urban road networks—based purely on their underlying topology and geometry.

What Problem Does This Paper Address?

Traditional graph kernels are built on discrete combinatorics: they count nodes, edges, or specific subgraph patterns. However, many real-world networks, such as urban road networks or biological vascular systems, are better modeled as metric graphs where the lengths of the edges carry vital geometric information.

A major flaw of standard graph kernels in this setting is their sensitivity to edge subdivision (splitting an edge by inserting a new node). For example, adding a new landmark along a street shouldn't change our structural perception of a city's road layout, but it completely alters traditional graph metrics.

Refining a road network by adding landmarks doesn't alter its underlying geometry.

This paper addresses the lack of graph kernels that can natively handle continuous edge lengths and remain invariant under such refinements, allowing for a true geometric and topological comparison of metric spaces.

Methods

The authors bridge tropical algebraic geometry and information geometry to create a novel framework:

  1. The Tropical Torelli Map: They map each metric graph to a flat torus (known as the tropical Jacobian variety). Computationally, for a graph with distinct edge lengths, this translates to finding a unique Symmetric Positive Definite (SPD) matrix $Q$ based on the graph's 1-homology group (its independent cycles) and a minimal spanning tree.
  2. Handling Genus Mismatches: Graphs with different numbers of cycles (genus) yield matrices of different sizes. To compare them, the authors embed these matrices into a larger, common space of Positive Semi-Definite (PSD) matrices via zero-padding or random principal submatrix selection.
  3. Two New Kernels:
  4. Tropical Torelli-Wasserstein (TTW) Kernel: Uses the Bures-Wasserstein distance, which is invariant under orthogonal transformations and naturally aligns with the geometric structure of the tropical Jacobian.
  5. Tropical Torelli-Euclidean (TTE) Kernel: A simpler, computationally efficient alternative using the standard Euclidean distance (Frobenius norm), which is mathematically guaranteed to be positive definite.

Datasets

The framework was evaluated on two distinct types of data:

  • TUDataset Benchmarks: 23 standard graph datasets (e.g., MUTAG, PROTEIN, IMDB-BINARY, FRANKENSTEIN) stripped of their original labels and augmented with random edge weights to simulate label-free, geometric settings.
  • Urban Road Networks (URNs): A newly curated set of 8 datasets extracted from OpenStreetMap (OSM) representing real-world metric graphs from cities worldwide. These are categorized into four structural patterns: gridiron (e.g., Chicago), linear (e.g., Nanchang), chaotic (e.g., Omdurman), and tributary (e.g., London).
Examples of different urban road network patterns at a small scale.

Key Insights and Ideas

  • Complexity is Driven by Topology, Not Size: The computational complexity of computing the tropical Torelli map depends primarily on the graph's genus (the number of independent cycles) rather than the raw number of nodes or edges. This makes the method exceptionally fast for large but sparse graphs.
  • Subdivision Invariance: Because the kernel relies on the inner product of the 1-homology group, splitting an edge into smaller segments yields the exact same matrix representation. This ensures the kernel measures the continuous space itself, not how it happens to be discretized.
  • The Tree Limitation: A fascinating quirk of this approach is that any graph without cycles (a tree) has a genus of 0 and maps to a trivial zero matrix. Consequently, the kernel views all trees as identical, highlighting a clear boundary between cycle-based topology and tree-based structures.

Key Results

  • Superiority in Label-Free Settings: On the label-free TUDataset benchmarks, the TTE and TTW kernels consistently outperformed classical kernels (like Shortest Path or Weisfeiler-Lehman), proving that geometric and topological features provide a powerful classification signal when combinatorial labels are missing.
  • Robustness on Large Scale Road Networks: In the Urban Road Network classification task, traditional kernels frequently suffered from "Out of Memory" (OOM) errors due to the massive size of the graphs. In contrast, the TTE and TTW kernels easily handled the data, with TTW achieving up to 94.5% accuracy on certain datasets.
  • Clear Geometric Clustering: Kernel PCA visualizations demonstrated that the proposed kernels successfully cluster different urban layouts into distinct, identifiable groups.
Kernel PCA dimension reduction showing clear separation of urban road network types.

Limitations and Future Work

  • The Tree Problem: Because trees have a genus of 0, the tropical Torelli map is trivial for them. The authors note that incorporating tree-like information into the kernel framework is a primary direction for future research.
  • No Support for Attributes: The current method is purely geometric and topological; it does not incorporate node/edge labels or attributes. Developing a principled way to integrate continuous functions over the metric space remains an open challenge.
  • Benchmark Scarcity: There is currently a lack of standard benchmark datasets explicitly designed for metric graphs, as many common graph datasets (like molecular graphs) do not possess true geometric edge lengths.

Summary updated

Abstract

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.
BibTeX
@misc{cao2025metric,
  author = {Yueqi Cao and Anthea Monod},
  title = {{Metric Graph Kernels via the Tropical Torelli Map}},
  year = {2025},
  eprint = {2505.12129},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.12129},
}
Figure