UMass Machine Learning and Friends Lunch | Main / Matching Embedding And Clustering For Graphs And Data

Many machine learning problems on data can naturally be formulated as problems on graphs. For example, dimensionality reduction and visualization are related to graph embedding. Given a sparse graph between N high-dimensional data nodes, how do we faithfully embed it in low dimension? We present an algorithm that improves dimensionality reduction by extending the Maximum Variance Unfolding method. But, given only a dataset of N samples, how do we construct a graph in the first place? The space to explore is daunting with 2^(N^2) graphs to choose from yet two interesting subfamilies are tractable: matchings and b-matchings. By placing distributions over matchings and using loopy belief propagation, we efficiently infer the optimal graph. Higher order inference over matchings is also efficient via fast Fourier algorithms. Matching not only has intriguing algebraic properties, it also leads to improvements in graph reconstruction, graph embedding, graph labeling, and graph partitioning. We show results on text, network and image data. Time permitting, we will show results on location data from millions of tracked mobile users which lets us discover patterns of human behavior, networks of places and networks of people.