III: Small: A Submodular Framework for Scalable Graph Matching with Performance Guarantees

University Of Virginia Main Campus, Charlottesville VA

Investigators

Abstract

Graphs are a natural and convenient abstraction for modeling structures arising in a broad spectrum of science and engineering disciplines. In many applications, a key problem is to align a pair of graphs (or "embed" one into the other). This is known as graph matching, and it frequently emerges in machine vision (e.g., landmark matching), learning (knowledge graphs), and graph mining; computational biology (protein-protein interactions); social sciences (social / organizational networks); and electronic circuit layout verification, to name a few areas. Graph matching is a computationally demanding problem, yet modern applications easily generate graphs with millions of vertices. In that regime, there is a pressing need for approximation algorithms which are both theoretically sound and highly scalable. This project considers graph matching from a fresh perspective -- through the lens of submodular optimization. The proposed research will yield exciting new theoretical and methodological insights that will also inform other walks of combinatorial optimization and its applications. In parallel with the research activities, the PIs will contribute to state-wide efforts to broaden participation in computing, via guest lectures in introductory engineering courses, and teaming up with a nonprofit that trains K-12 teachers to empower them to teach coding and computational thinking. Existing graph matching approximations based on relaxing the combinatorial constraints either do not scale well, or fail to provide performance guarantees (except in special cases). None of these directly tackles the combinatorial nature of the problem; the conventional wisdom being that the difficulty stems from the constraints, not the cost function. In preliminary work, the PIs have established that graph matching can be equivalently reformulated as minimizing a submodular function over the intersection of a pair of partition matroids. Using this preliminary result as a stepping stone, this project is focused on designing successive submodular approximation algorithms that feature both theoretical performance guarantees and scalability; hard and soft graph matching (via continuous extension); validation using real-world data; and leveraging the practical insights gained through validation to close the loop and drive further methodological and algorithmic developments. Breaking from the mold, the approach embraces combinatorial optimization using a judicious combination of discrete and continuous optimization tools which promises to go a long way towards improving the state-of-art for this fundamental problem. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.