用热带几何构建度量图核，更精准比较复杂网络结构。
Metric Graph Kernels via the Tropical Torelli Map
- 基于热带几何与拓扑，而非传统节点边关系。
- 对边细分不变，适合不同尺度的度量空间比较。
- 适用于城市道路等无标签网络分类任务。
我们首次通过热带代数几何引入度量图核。与依赖节点、边和子图的常规图核不同，我们的方法完全基于底层度量空间的几何与拓扑特性。其核心特性是边细分不变性，使核天然适用于比较代表不同度量空间的图。我们开发了高效算法计算这些核，并分析其复杂度，主要取决于输入图的亏格而非规模。在合成数据和部分真实数据集上的实验表明，该核能捕捉传统组合方法忽略的互补几何与拓扑信息，尤其在无标签场景下表现突出。我们进一步展示了其在城市道路网络分类任务中的实际应用价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。