Lipschitz Continuous Algorithms for Graph Problems

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 from 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.

Authors

• Soh Kumabe
• Yuichi Yoshida

Keywords

• Weight measurement
• Shortest path problem
• Systematics
• Perturbation methods
• Approximation algorithms
• Knowledge discovery
• Extraterrestrial measurements
• Lipschitz Continuous
• Algorithm For Problem
• Graph Problems
• Changes In Frequency
• Shortest Path
• Maximum Weight
• Matching Problem
• Spanning Tree
• Maximum Matching
• Graph Algorithms
• Unweighted Graph
• Linear Programming Relaxation
• Entropy Regularization
• Path Length
• Estimation Algorithm
• Weight Vector
• Edge Weights
• Directed Graph
• Earth Mover’s Distance
• Total Variation Distance
• Source Vertex
• Contractive
• Recursive Algorithm
• Approximate Ratio
• Line Samples
• Earth Mover
• Sensitive Definition
• Complete Bipartite Graph
• Lipschitz continuity
• Sensitivity