nips nips2013 nips2013-282 nips2013-282-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Muse, Guillermo Sapiro
Abstract: Graph matching is a challenging problem with very important applications in a wide range of fields, from image and video analysis to biological and biomedical problems. We propose a robust graph matching algorithm inspired in sparsityrelated techniques. We cast the problem, resembling group or collaborative sparsity formulations, as a non-smooth convex optimization problem that can be efficiently solved using augmented Lagrangian techniques. The method can deal with weighted or unweighted graphs, as well as multimodal data, where different graphs represent different types of data. The proposed approach is also naturally integrated with collaborative graph inference techniques, solving general network inference problems where the observed variables, possibly coming from different modalities, are not in correspondence. The algorithm is tested and compared with state-of-the-art graph matching techniques in both synthetic and real graphs. We also present results on multimodal graphs and applications to collaborative inference of brain connectivity from alignment-free functional magnetic resonance imaging (fMRI) data. The code is publicly available. 1
Almohamad, H. and Duffuaa, S. A linear programming approach for the weighted graph matching problem. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 15(5):522–525, 1993. Barab´ si, A. and Albert, R. Emergence of scaling in random networks. Science, 286(5439):509–512, a 1999. Bertsekas, D. and Tsitsiklis, J. Parallel and Distributed Computation: Numerical Methods. Prentice Hall, 1989. Chiquet, J., Grandvalet, Y., and Ambroise, C. Inferring multiple graphical structures. Statistics and Computing, 21(4):537–553, 2011. Conte, D., Foggia, P., Sansone, C., and Vento, M. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(03):265–298, 2004. Craddock, R.C., James, G.A., Holtzheimer, P.E., Hu, X.P., and Mayberg, H.S. A whole brain fMRI atlas generated via spatially constrained spectral clustering. Human Brain Mapping, 33(8):1914– 1928, 2012. Erd˝ s, P. and R´ nyi, A. On random graphs, I. Publicationes Mathematicae, 6:290–297, 1959. o e Fiori, Marcelo, Mus´ , Pablo, and Sapiro, Guillermo. Topology constraints in graphical models. In e Advances in Neural Information Processing Systems 25, pp. 800–808, 2012. Fiori, Marcelo, Mus´ , Pablo, Hariri, Ahamd, and Sapiro, Guillermo. Multimodal graphical models e via group lasso. Signal Processing with Adaptive Sparse Structured Representations, 2013. Kuhn, H. W. The Hungarian method for the assignment problem. Naval Research Logistic Quarterly, 2:83–97, 1955. Lin, Z., Liu, R., and Su, Z. Linearized alternating direction method with adaptive penalty for lowrank representation. In Advances in Neural Information Processing Systems 24, pp. 612–620. 2011. Loh, P. and Wainwright, M. Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses. In Advances in Neural Information Processing Systems 25, pp. 2096–2104. 2012. Newman, M. Networks: An Introduction. Oxford University Press, Inc., New York, NY, USA, 2010. Nooner, K. et al. The NKI-Rockland sample: A model for accelerating the pace of discovery science in psychiatry. Frontiers in Neuroscience, 6(152), 2012. Seshadhri, C., Kolda, T.G., and Pinar, A. Community structure and scale-free collections of Erd˝ so R´ nyi graphs. Physical Review E, 85(5):056109, 2012. e Umeyama, S. An eigendecomposition approach to weighted graph matching problems. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 10(5):695–703, 1988. Varoquaux, G., Gramfort, A., Poline, J.B., and T., Bertrand. Brain covariance selection: better individual functional connectivity models using population prior. In Advances in Neural Information Processing Systems 23, pp. 2334–2342, 2010. Varshney, L., Chen, B., Paniagua, E., Hall, D., and Chklovskii, D. Structural properties of the caenorhabditis elegans neuronal network. PLoS Computational Biology, 7(2):e1001066, 2011. Vogelstein, J.T., Conroy, J.M., Podrazik, L.J., Kratzer, S.G., Harley, E.T., Fishkind, D.E., Vogelstein, R.J., and Priebe, C.E. Fast approximate quadratic programming for large (brain) graph matching. arXiv:1112.5507, 2012. Yuan, M. and Lin, Y. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B, 68(1):49–67, 2006. Yuan, M. and Lin, Y. Model selection and estimation in the Gaussian graphical model. Biometrika, 94(1):19–35, February 2007. Zaslavskiy, M., Bach, F., and Vert, J.P. A path following algorithm for the graph matching problem. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 31(12):2227–2242, 2009. 9