Metric Graph Kernels via the Tropical Torelli Map
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Convex Relaxation of the Ambrosio--Tortorelli Elliptic Functionals for the Mumford-Shah Functional
In this paper, we revisit the phase-field approximation of Ambrosio and Tortorelli for the Mumford--Shah functional. We then propose a convex relaxation for it to attempt to compute globally optimal solutions rather than…
The Real Tropical Geometry of Neural Networks
We consider a binary classifier defined as the sign of a tropical rational function, that is, as the difference of two convex piecewise linear functions. The parameter space of ReLU neural networks is contained as a semi…
Compound and Parallel Modes of Tropical Convolutional Neural Networks
Convolutional neural networks (CNNs) are foundational to many state-of-the-art computer vision systems, yet their reliance on multiplication-intensive computations poses challenges for deployment on resource-constrained …
Tropical Geometric Tools for Machine Learning: the TML package
In the last decade, developments in tropical geometry have provided a number of uses directly applicable to problems in statistical learning. The TML package is the first R package which contains a comprehensive set of t…
Density EstimationThe Geometry of Thought: Disclosing the Transformer as a Tropical Polynomial Circuit
We prove that the Transformer self-attention mechanism in the high-confidence regime ($β\to \infty$, where $β$ is an inverse temperature) operates in the tropical semiring (max-plus algebra). In particular, we show that …