Graph Matching Via the Lens of Supermodularity
- 9 July 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 34 (5) , 2200-2211
Abstract
Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP–hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this article, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art.Keywords
Funding Information
- National Science Foundation (IIS-1908070)
This publication has 33 references indexed in Scilit:
- Global network alignment using multiscale spectral signaturesBioinformatics, 2012
- Fast Matrix Computations for Pairwise and Columnwise Commute Times and Katz ScoresInternet Mathematics, 2012
- Global alignment of protein–protein interaction networks by graph matching methodsBioinformatics, 2009
- A new graph-based method for pairwise global network alignmentBMC Bioinformatics, 2009
- Global alignment of multiple protein interaction networks with application to functional orthology detectionProceedings of the National Academy of Sciences, 2008
- Graph evolutionACM Transactions on Knowledge Discovery From Data, 2007
- Solving quadratic assignment problems using convex quadratic programming relaxationsOptimization Methods and Software, 2001
- An eigendecomposition approach to weighted graph matching problemsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1988
- Diagonal Equivalence to Matrices with Prescribed Row and Column SumsThe American Mathematical Monthly, 1967
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955