基于树嵌入的受限跳数网络设计

Nov, 2020

Tree Embeddings for Hop-Constrained Network Design

Bernhard Haeupler, D Ellis Hershkowitz, Goran Zuzic

TL;DR通过使用 “部分树度量”，我们将有限的跳限制问题转化为在树上的无限制跳问题，并且给了许多经典网络设计问题的第一个多对数双标准逼近。这些问题包括斯特纳森林、组斯特纳树、组斯特纳森林、大宗购买网络设计以及在线和迭代多个问题。

Abstract

network design problems aim to compute low-cost structures such as routes, trees and subgraphs. Often, it is natural and desirable to require that these structures have small hop length or hop diameter. Unfortunately, optimization problems with hop constraints are much harder and less

network design problems hop-constrained distances partial tree metrics poly-logarithmic bicriteria approximations classic network design problems

发现论文，激发创造

力导向图嵌入与跳数距离

本研究提出了一种新颖的力导向图嵌入方法，利用稳定的加速度动力学公式来嵌入节点，以保留图拓扑和结构特征，实现了高性能的图处理和分析任务，相比最先进的无监督嵌入技术具有竞争性的性能。

Sep, 2023

中央生成树问题

基于欧几里得空间中的数据，本研究提出了一个新的优化问题 ——“（分支）中心生成树”，它包含了之前提到的所有定义作为特例，并从理论和实践两个方面证明了（分支）中心生成树相对于数据中的噪声更具鲁棒性，并更适合以其骨架来总结数据集。此外，本研究还提出了一种应对 NP 难优化问题的启发式方法，并在生物学的单细胞 RNA 表达数据和植物的 3D 点云数据上进行了展示。

Apr, 2024

从树到连续嵌入再回归：双曲线分层聚类

该研究提出了一种名为 HypHC 的方法，将传统的基于启发式算法的相似性层次聚类问题转化为一个离散优化问题，并通过连续松弛技术获得全局最优解，该方法通过超蜂窝嵌入实现了离散树到连续表示的映射，并采用解码算法通过叶节点嵌入到树状图的映射，实现了连续优化用于搜索离散二进制树的空间。

Oct, 2020

学习分层嵌入的双曲包含锥

在机器学习中，通过保留相关网络属性的低维嵌入学习图表示是一类重要的问题。本文提出了一种嵌入有向无环图的新方法，使用证明能够更好地模拟树状结构的双曲空间，并使用一组嵌套的测地凸锥来定义分层关系，并证明这些蕴含锥体在欧几里得和双曲空间中均具有一种优化的形式，而且它们可以规范地定义嵌入学习过程。实验显示，我们的方法在表示能力和泛化方面都比最近的强有力的基线有显着的改进。

Apr, 2018

自适应符号嵌入的树编辑距离学习：补充材料和结果

该论文提出了一种基于嵌入的新型度量学习方法，通过嵌入树节点向量来学习编辑距离，使欧几里得距离支持类别判别并提高分类准确率，该方法在包括计算机科学、生物医学和自然语言处理数据集的六个基准数据集上优于目前树形度量学习技术的最新技术。

May, 2018

HyperAid: 超几何空间中用于树拟合和分层聚类的去噪

该论文提出了一种基于超 bolic 空间的新方法（HyperAid），用于将 tree-metrics 适应到噪声数据，并通过引入边权重来提高适应性，该方法在边缘增强树和最短距离计量表示的合成数据，以及 Zoo，Iris，Glass，分割和 SpamBase 等实际数据集上效果显著优于现有方法。

May, 2022

使用树来近似计算 1-Wasserstein 距离

本篇论文介绍了一种基于树状嵌入的 Wasserstein 距离的计算方式，通过 L1 正则化方法来学习树的边缘权重，并通过 Lasso-based 回归问题实现最短路径距离的表示，从而近似计算 1-Wasserstein 距离。通过实验结果，证明了这种方法可以准确地近似 1-Wasserstein 距离。

Jun, 2022

对等节点分层：此权重网络中发现层次结构的实用算法

本文介绍了 Agony 排名算法的若干扩展，包括权重图和层级数限制，通过与容量流问题的联系和启发式算法加速求解，同时也证明了任何凸惩罚下的最小层级问题都可以多项式时间解决，而以任何凹惩罚优化最小层级问题都是 NP - 难的问题。

Feb, 2019

定向树的收敛传播算法

本文介绍了一种基于树分解算法的信息传递方法，用于解决基于图的模型中的优化问题，并保证收敛于全局最优解。

Jun, 2012

最短路径与最小斯坦纳树间的查询决策回归

对于一个具有未知权重的图，如果我们知道一些节点子集关联的最小 Steiner 树，那么我们能否找到一对节点的最短路径？本文研究了这样一个原型问题，称为具有任务转换的查询 - 决策回归，重点关注最短路径问题和最小 Steiner 树问题。我们提供了关于构建评分模型的可实现假设空间设计的理论洞察，并提出了两个有原则的学习框架。我们的实验研究显示，这样的问题可以在统计显著性的程度上得到较好的解决。

Feb, 2024