A dynamical systems approach to weighted graph matching. (English) Zbl 1204.05084
Summary: Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Bloch, A. M.; Brockett, R. W.; Crouch, P. E., Double bracket equations and geodesic flows on symmetric spaces, Communications on Mathematical Physics, 187, 357-373 (1997) · Zbl 0884.58079 |
| [2] | Brockett, R. W., Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems, Linear Algebra and Its Applications, 146, 79-91 (1991) · Zbl 0719.90045 |
| [3] | Brockett, R. W., Least squares matching problems, Linear Algebra and its Applications, 122-124, 761-777 (1989) · Zbl 0676.90055 |
| [4] | Chu, M. T., Matrix differential equations: A continuous realization process for linear algebra problems, Nonlinear Analysis, 18, 1125-1146 (1992) · Zbl 0773.34007 |
| [5] | Chu, M. T.; Driessel, K. R., The projected gradient method for least squares matrix approximations with spectral constraints, SIAM Journal on Numerical Analysis, 27, 1050-1060 (1990) · Zbl 0704.65025 |
| [6] | Cortes, J.; Martinez, S.; Bullo, F., Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions, IEEE Transactions on Automatic Control, 51, 8, 1289-1298 (2006) · Zbl 1366.93400 |
| [7] | Faye, A.; Roupin, F., A cutting planes algorithm based upon a semidefinite relaxation for the quadratic assignment problem, Lecture Notes in Computer Science, 3669, 850-861 (2005) · Zbl 1142.90470 |
| [8] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of np-completeness (1979), W. H. Freeman & Co: W. H. Freeman & Co New York, NY · Zbl 0411.68039 |
| [9] | Godsil, C.; Royle, G., Algebraic graph theory (2001), Springer-Verlag: Springer-Verlag New York, NY · Zbl 0968.05002 |
| [10] | Gold, S.; Rangarajan, A., A graduated assignment algorithm for graph matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, 18, 4, 377-388 (1996) |
| [11] | Helmke, U.; Moore, J. B.; Brockett, R. W., Optimization and dynamical systems (1996), Springer-Verlag: Springer-Verlag New York, NY |
| [12] | Hillier, F. S.; Lieberman, G. J., Introduction to mathematical programming (1995), McGraw-Hill: McGraw-Hill New York, NY · Zbl 0155.28202 |
| [13] | Horn, R. A.; Johnson, C. R., Matrix analysis (1985), Cambridge University Press · Zbl 0576.15001 |
| [14] | Jadbabaie, A.; Lin, J.; Morse, A. S., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, 48, 6, 988-1001 (2003) · Zbl 1364.93514 |
| [15] | Mesbahi, M., On state-dependent dynamic graphs and their controllability properties, IEEE Transactions on Automatic Control, 50, 3, 387-392 (2005) · Zbl 1365.93045 |
| [16] | Muhammad, A.; Egerstedt, M., Connectivity graphs as models of local interactions, Journal of Applied Mathematics and Computation, 168, 1, 243-269 (2005) · Zbl 1075.05083 |
| [17] | Olfati-Saber, R., & Murray, R. M. (2003). Agreement problems in networks with directed graphs and switching topology. In Proceedings of the 42nd IEEE conference on decision and control; Olfati-Saber, R., & Murray, R. M. (2003). Agreement problems in networks with directed graphs and switching topology. In Proceedings of the 42nd IEEE conference on decision and control |
| [18] | Rangarajan, A.; Mjolsness, E., A lagrangian relaxation network for graph matching, IEEE Transactions on Neural Networks, 7, 6, 1365-1381 (1996) |
| [19] | Smith, S. L., & Bullo, F. (2006). Target assignment for robotic networks: Asymptotic performance under limited communication. In Proceedings of the American control conference; Smith, S. L., & Bullo, F. (2006). Target assignment for robotic networks: Asymptotic performance under limited communication. In Proceedings of the American control conference |
| [20] | Tanner, H. G.; Jadbabaie, A.; Pappas, G. J., Flocking in fixed and switching networks, IEEE Transactions on Automatic Control, 52, 5, 863-868 (2007) · Zbl 1366.93414 |
| [21] | Umeyama, S., An eigendecomposition approach to weighted graph matching problems, IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 5, 695-703 (1988) · Zbl 0678.05049 |
| [22] | Wolkowicz, H., Semidefinite programming approaches to the quadratic assignment problem, (Nonlinear assignment problems: Algorithms and applications (combinatorial optimization) (2000), Kluwer: Kluwer Norwell, MA), 143-174 · Zbl 1038.90045 |
| [23] | Zavlanos, M. M., & Pappas, G. J. (2006). A dynamical systems approach to weighted graph matching. In Proceedings of the 45th IEEE conference on decision and control; Zavlanos, M. M., & Pappas, G. J. (2006). A dynamical systems approach to weighted graph matching. In Proceedings of the 45th IEEE conference on decision and control |
| [24] | Zavlanos, M. M.; Pappas, G. J., Potential fields for maintaining connectivity of mobile networks, IEEE Transactions on Robotics, 23, 4, 812-816 (2007) |
| [25] | Zavlanos, M. M.; Pappas, G. J., Dynamic assignment in distributed motion planning with local coordination, IEEE Transactions on Robotics, 24, 1, 232-242 (2008) |
| [26] | Zavlanos, M. M., & Pappas, G. J. (2007). Distributed formation control with permutation symmetries. In Proceedings of the 46th IEEE conference on decision and control; Zavlanos, M. M., & Pappas, G. J. (2007). Distributed formation control with permutation symmetries. In Proceedings of the 46th IEEE conference on decision and control |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
