The Average Mixing Matrix Signature

详细信息    查看全文

• 关键词：Graph characterisation ; Structural descriptor ; Quantum walks ; Average mixing matrix
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10029
• 期：1
• 页码：474-484
• 全文大小：1,718 KB
• 参考文献：1.Albarelli, A., Bergamasco, F., Rossi, L., Vascon, S., Torsello, A.: A stable graph-based representation for object recognition through high-order matching. In: 2012 21st International Conference on Pattern Recognition (ICPR), pp. 3341–3344. IEEE (2012)
  2.Aubry, M., Schlickewei, U., Cremers, D.: The wave kernel signature: a quantum mechanical approach to shape analysis. In: 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 1626–1633. IEEE (2011)
  3.Bai, L., Rossi, L., Torsello, A., Hancock, E.R.: A quantum Jensen-Shannon graph kernel for unattributed graphs. Pattern Recogn. 48(2), 344–355 (2015)CrossRef
  4.Duchenne, O., Joulin, A., Ponce, J.: A graph-matching kernel for object categorization. In: 2011 IEEE International Conference on Computer Vision (ICCV), pp. 1792–1799. IEEE (2011)
  5.Godsil, C.: Average mixing of continuous quantum walks. J. Comb. Theor. Ser. A 120(7), 1649–1662 (2013)MathSciNet CrossRef MATH
  6.Kempe, J.: Quantum random walks: an introductory overview. Contemp. Phys. 44(4), 307–327 (2003)MathSciNet CrossRef
  7.Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)MathSciNet CrossRef MATH
  8.Riesen, K., Bunke, H.: Graph Classification and Clustering Based on Vector Space Embedding. World Scientific Publishing Co., Inc., Hackensack (2010)CrossRef MATH
  9.Rossi, L., Torsello, A., Hancock, E.R.: Measuring graph similarity through continuous-time quantum walks and the quantum Jensen-Shannon divergence. Phys. Rev. E 91(2), 022815 (2015)MathSciNet CrossRef
  10.Rossi, L., Torsello, A., Hancock, E.R., Wilson, R.C.: Characterizing graph symmetries through quantum Jensen-Shannon divergence. Phys. Rev. E 88(3), 032806 (2013)CrossRef
  11.Suau, P., Hancock, E.R., Escolano, F.: Analysis of the schrödinger operator in the context of graph characterization. In: Hancock, E., Pelillo, M. (eds.) SIMBAD 2013. LNCS, vol. 7953, pp. 190–203. Springer, Heidelberg (2013)CrossRef
  12.Sun, J., Ovsjanikov, M., Guibas, L.: A concise and provably informative multi-scale signature based on heat diffusion. In: Computer graphics forum, vol. 28, pp. 1383–1392. Wiley Online Library (2009)
  13.Torsello, A., Rossi, L.: Supervised learning of graph structure. In: Pelillo, M., Hancock, E.R. (eds.) SIMBAD 2011. LNCS, vol. 7005, pp. 117–132. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-24471-1_​9 CrossRef
  14.Yao, B., Fei-Fei, L.: Action recognition with exemplar based 2.5D graph matching. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012. LNCS, vol. 7575, pp. 173–186. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-33765-9_​13 CrossRef
  15.Yi, Y., Lin, M.: Human action recognition with graph-based multiple-instance learning. Pattern Recogn. 53(C), 148–162 (2016)CrossRef
  
• 作者单位：Luca Rossi (18)
  Simone Severini (19)
  Andrea Torsello (20)
  
  18. School of Engineering and Applied Science, Aston University, Birmingham, UK
  19. Department of Computer Science, University College London, London, UK
  20. DAIS, Università Ca’ Foscari Venezia, Venice, Italy
  
• 丛书名：Structural, Syntactic, and Statistical Pattern Recognition
• ISBN：978-3-319-49055-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10029

文摘

Laplacian-based descriptors, such as the Heat Kernel Signature and the Wave Kernel Signature, allow one to embed the vertices of a graph onto a vectorial space, and have been successfully used to find the optimal matching between a pair of input graphs. While the HKS uses a heat diffusion process to probe the local structure of a graph, the WKS attempts to do the same through wave propagation. In this paper, we propose an alternative structural descriptor that is based on continuous-time quantum walks. More specifically, we characterise the structure of a graph using its average mixing matrix. The average mixing matrix is a doubly-stochastic matrix that encodes the time-averaged behaviour of a continuous-time quantum walk on the graph. We propose to use the rows of the average mixing matrix for increasing stopping times to develop a novel signature, the Average Mixing Matrix Signature (AMMS). We perform an extensive range of experiments and we show that the proposed signature is robust under structural perturbations of the original graphs and it outperforms both the HKS and WKS when used as a node descriptor in a graph matching task.