Given a matrix D describing the pairwise dissimilarities of a data set, a common task is to embed the data points into Euclidean space. The classical multidimensional scaling (cMDS) algorithm is a widespread method to do this. However, theoretical analysis of the robustness of the algorithm and an indepth analysis of its performance on nonEuclidean metrics is lacking. In this paper, we derive a formula, based on the eigenvalues of a matrix obtained from D, for the Frobenius norm of the difference between D and the metric Dcmds returned by cMDS. This error analysis leads us to the conclusion that when the derived matrix has a significant number of negative eigenvalues, then ∥D−Dcmds∥F, after initially decreasing, willeventually increase as we increase the dimension. Hence, counterintuitively, the quality of the embedding degrades as we increase the dimension. We empirically verify that the Frobenius norm increases as we increase the dimension for a variety of nonEuclidean metrics. We also show on several benchmark datasets that this degradation in the embedding results in the classification accuracy of both simple (e.g., 1nearest neighbor) and complex (e.g., multilayer neural nets) classifiers decreasing as we increase the embedding dimension.Finally, our analysis leads us to a newmore »
Embedding Directed Graphs in Potential Fields Using FastMapD
Embedding undirected graphs in a Euclidean space has many computational benefits. FastMap is an efficient embedding algorithm that facilitates a geometric interpretation of problems posed on undirected graphs. However, Euclidean distances are inherently symmetric and, thus, Euclidean embeddings cannot be used for directed graphs. In this paper, we present FastMapD, an efficient generalization of FastMap to directed graphs. FastMapD embeds vertices using a potential field to capture the asymmetry between the pairwise distances in directed graphs. FastMapD learns a potential function to define the potential field using a machine learning module. In experiments on various kinds of directed graphs, we demonstrate the advantage of FastMapD over other approaches. Errata: This version of the paper corrects a programming mistake, resulting in even better experimental results than those reported in the original paper.
 Award ID(s):
 1724392
 Publication Date:
 NSFPAR ID:
 10179965
 Journal Name:
 Symposium on Combinatorial Search (SoCS)
 Sponsoring Org:
 National Science Foundation
More Like this


Bojanczyk, M. et (Ed.)Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n, and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n^α for α > 0, with high probability reconstructs the vertex positions with a maximum error of O(n^β) where β = 1/2(4/3)α, until α ≥ 3/8 where β = 0 and the error becomes O(√{log n}). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and shortrange estimates based on the number of common neighbors. We extend our results to the surface of the sphere in ℝ³ and to hypercubes in any constant dimension.

In this paper, we study stable coordination in multi agent systems with directed interactions, and apply the results for distributed topology control. Our main contribution is to extend the wellknown potentialbased control framework orig inally introduced for undirected networks to the case of net works modeled by a directed graph. Regardless of the particular objective to be achieved, potentialbased control for undirected graphs is intrinsically stable. Briefly, this can be explained by the positive semidefiniteness of the graph Laplacian induced by the symmetric nature of the interactions. Unfortunately, this energy finiteness guarantee no longer holds when a multiagent system lacks symmetry in pairwise interactions. In this context, our contribution is twofold: i) we formalize stable coordination of multiagent systems on directed graphs, demonstrating the graph structures that induce stability for a broad class of coordination objectives; and ii) we design a topology control mechanism based on a distributed eigenvalue estimation algorithm to enforce Lyapunov energy finiteness over the derived class of stable graphs. Simulation results demonstrate a multiagent system on a directed graph performing topology control and collision avoidance, corroborating the theoretical findings.

Understanding the structure of minorfree metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “smallcomplexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minorfree metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ϵ, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ϵ factor, of total weight at most Oϵ(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion ϵD. Namely, given a minorfree graph G=(V,E,w) of diameter D, and parameter ϵ, we construct a distribution D over dominating metric embeddings into treewidthOϵ(log n) graphs such that ∀u,v∈V, Ef∼D[dH(f(u),f(v))]≤dG(u,v)+ϵD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minorfree metrics; (2) themore »

In this paper, we propose to solve the directed graph embedding problem via a two stage approach: in the first stage, the graph is symmetrized in one of several possible ways, and in the second stage, the soobtained symmetrized graph is embeded using any stateoftheart (undirected) graph embedding algorithm. Note that it is not the objective of this paper to propose a new (undirected) graph embedding algorithm or discuss the strengths and weaknesses of existing ones; all we are saying is that whichever be the suitable graph embedding algorithm, it will fit in the above proposed symmetrization framework.