Rapidly Computing Approximate Graph Convex Hulls via FastMap

Given an undirected edge-weighted graph G and a subset of vertices S in it, the graph convex hull CH_S^G of S in G is the set of vertices obtained by the process of initializing CH_S^G to S and iteratively adding until convergence all vertices on all shortest paths between all pairs of vertices in CH_S^G of one iteration to constitute CH_S^G of the next iteration. Computing the graph convex hull has applications in shortest-path computations, active learning, and in identifying geodesic cores in social networks, among others. Unfortunately, computing it exactly is prohibitively expensive on large graphs. In this paper, we present a FastMap-based algorithm for efficiently computing approximate graph convex hulls. FastMap is a graph embedding algorithm that embeds a given undirected edge-weighted graph into a Euclidean space in near-linear time such that the pairwise Euclidean distances between vertices approximate the shortest-path distances between them. Using FastMap’s ability to facilitate geometric interpretations, our approach invokes the power of well-studied algorithms in Computational Geometry that efficiently compute the convex hull of a set of points in Euclidean space. Through experimental studies, we show that our approach not only is several orders of magnitude faster than the exact brute-force algorithm but also outperforms the state-of-the-art approximation algorithm, both in terms of generality and the quality of the solutions produced.