Graph algorithms are widely used for decision making and knowledge discovery. To ensure their effectiveness, it is essential that their output remains stable even when subjected to small perturbations to the input because frequent output changes can result in costly decisions, reduced user trust, potential security concerns, and lack of replicability. In this study, we consider the Lipschitz continuity of algorithms as a stability measure and initiate a systematic study of the Lipschitz continuity of algorithms for (weighted) graph problems. Depending on how we embed the output solution to a metric space, we can think of several Lipschitzness notions. We mainly consider the one that is invariant under scaling of weights, and we provide Lipschitz continuous algorithms and lower bounds for the minimum spanning tree problem, the shortest path problem, and the maximum weight matching problem. In particular, our shortest path algorithm is obtained by first designing an algorithm for unweighted graphs that are robust against edge contractions and then applying it to the unweighted graph constructed from the original weighted graph. Then, we consider another Lipschitzness notion induced by a natural mapping that maps the output solution to its characteristic vector. It turns out that no Lipschitz continuous algorithm exists for this Lipschitz notion, and we instead design algorithms with bounded pointwise Lipschitz constants for the minimum spanning tree problem and the maximum weight bipartite matching problem. Our algorithm for the latter problem is based on an LP relaxation with entropy regularization.
翻译:图算法被广泛应用于决策和知识发现。为确保它们的有效性,至关重要的是,即使在输入的微小扰动下,它们的输出也保持稳定,因为频繁的输出变化可能导致昂贵的决策、降低用户的信任、潜在的安全问题和无法复现的问题。在本研究中,我们将算法的Lipschitz连续性作为稳定性度量,并着手系统研究了加权图问题的Lipschitz连续性算法。根据我们如何将输出解嵌入到度量空间中,我们可以考虑几个Lipschitz连续性概念。我们主要考虑的是在权重缩放下不变的概念,并为最小生成树问题、最短路径问题和最大权重匹配问题提供Lipschitz连续算法和下界。特别地,我们的最短路径算法是通过首先设计一个对边缩减具有鲁棒性的无权图算法,然后将其应用到构造自原始加权图的无权图中而得到的。然后,我们考虑由将输出解映射到其特征向量的自然映射所引起的另一个Lipschitz连续性概念。结果证明,这个概念下不存在Lipschitz连续算法,我们相反地为最小生成树问题和二分图最大权重匹配问题设计了具有有界点Lipschitz常数的算法。我们的后者算法基于具有熵正则化的LP松弛。