Revisiting FastMap: New Applications
This work addresses efficiency and applicability challenges in graph embedding and machine learning for AI researchers and practitioners, presenting incremental improvements and new applications of the FastMap method.
The paper tackles the problem of generating Euclidean embeddings for graphs efficiently and applies them to solve various graph-theoretic problems in AI, achieving near-linear time complexity for approximations of graph-based distances. It also introduces FastMapSVM, a learning framework combining FastMap with SVMs, and applies it to predict satisfiability in Constraint Satisfaction Problems and classify seismograms in Earthquake Science.
FastMap was first introduced in the Data Mining community for generating Euclidean embeddings of complex objects. In this dissertation, we first present FastMap to generate Euclidean embeddings of graphs in near-linear time: The pairwise Euclidean distances approximate a desired graph-based distance function on the vertices. We then apply the graph version of FastMap to efficiently solve various graph-theoretic problems of significant interest in AI: including facility location, top-K centrality computations, community detection and block modeling, and graph convex hull computations. We also present a novel learning framework, called FastMapSVM, by combining FastMap and Support Vector Machines. We then apply FastMapSVM to predict the satisfiability of Constraint Satisfaction Problems and to classify seismograms in Earthquake Science.