Motivations of the Trip
The use of a graph-based pattern representation induces the need to formulate the main operations required in Pattern Recognition in terms of operations on graphs: classification, usually intended as the comparison between an object and a set of prototypes, and learning, which is the process for obtaining a model of a class starting from a set of known samples, are among the key issues that must be addressed using graph-based techniques.
Forty years have passed since the first papers on this topic appear in Pattern Recognition literature: a lot of research effort has been devoted to explore this challenging field and some approaches have been meanwhile consolidated. These notes aren’t a scientific paper but some considerations inspiring my future talk at gbr 2013 conference, a little trip in the word of graphs aimed at better knowing treasures and outstanding locations.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Auwatanamongkol, S.: Inexact graph matching using a genetic algorithm for image recognition. Pattern Recognition Letters (PRL) 28(12), 1428–1437 (2007)
Bagdanov, A.D., Worring, M.: First order gaussian graphs for efficient structure classification. PR 36(6), 1311–1324 (2003)
Bai, X., Latecki, L.: Path similarity skeleton graph matching. IEEE Trans. on PAMI 30(7), 1282–1292 (2008)
Bengoetxea, E., Larrañaga, P., Bloch, I., Perchant, A., Boeres, C.: Inexact graph matching by means of estimation of distribution algorithms. PR 35(12), 2867–2880 (2002)
Bergamasco, F., Albarelli, A.: A graph-based technique for semi-supervised segmentation of 3D surfaces. PRL (2012) (in press)
Borzeshi, E.Z., Piccardi, M., Riesen, K., Bunke, H.: Discriminative prototype selection methods for graph embedding. PR (2012)
Bourbakis, N., Yuan, P., Makrogiannis, S.: Object recognition using wavelets, L-G graphs and synthesis of regions. PR 40(7), 2077–2096 (2007)
Bunke, H., Dickinson, P., Irniger, C., Kraetzl, M.: Recovery of missing information in graph sequences by means of reference pattern matching and decision tree learning. PR 39(4), 573–586 (2006)
Bunke, H., Riesen, K.: Improving vector space embedding of graphs through feature selection algorithms. PR 44(9), 1928–1940 (2011)
Bunke, H., Riesen, K.: Recent advances in graph-based pattern recognition with applications in document analysis. PR 44(5), 1057–1067 (2011)
Bunke, H., Riesen, K.: Towards the unification of structural and statistical pattern recognition. PRL 33(7), 811–825 (2012)
Caelli, T., Kosinov, S.: Inexact graph matching using eigen-subspace projection clustering. IJPRAI 18(3), 329–354 (2004)
Caetano, T., McAuley, J., Cheng, L., Le, Q., Smola, A.: Learning graph matching. IEEE Trans. on PAMI 31(6), 1048–1058 (2009)
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in Pattern Recognition. IJPRAI 18(3), 265–298 (2004)
Conte, D., Foggia, P., Jolion, J.M., Vento, M.: A graph-based, multi-resolution algorithm for tracking objects in presence of occlusions. PR 39(4), 562–572 (2006)
Culp, M., Michailidis, G.: Graph-based semisupervised learning. IEEE Trans. on PAMI 30(1), 174–179 (2008)
Czech, W.: Invariants of distance k-graphs for graph embedding. PRL 33(15), 1968–1979 (2012)
Dhillon, I., Guan, Y., Kulis, B.: Weighted graph cuts without eigenvectors: A multilevel approach. IEEE Trans. on PAMI 29(11), 1944–1957 (2007)
Dickinson, P.J., Kraetzl, M., Bunke, H., Neuhaus, M., Dadej, A.: Similarity measures for hierarchical representations of graphs with unique node labels. IJPRAI 18-3(3), 425–442 (2004)
Dickinson, P.J., Bunke, H., Dadej, A., Kraetzl, M.: Matching graphs with unique node labels. Pattern Analysis & Applications 7, 243–254 (2004)
Duchenne, O., Bach, F., Kweon, I.S., Ponce, J.: A tensor-based algorithm for high-order graph matching. IEEE Trans. on PAMI 33(12), 2383–2395 (2011)
Ducournau, A., Bretto, A., Rital, S., Laget, B.: A reductive approach to hypergraph clustering: An application to image segmentation. PR 45(7), 2788–2803 (2012)
Emms, D., Wilson, R.C., Hancock, E.R.: Graph matching using the interference of continuous-time quantum walks. PR 42(5), 985–1002 (2009)
Felzenszwalb, P., Zabih, R.: Dynamic programming and graph algorithms in computer vision. IEEE Trans. on PAMI 33(4), 721–740 (2011)
Fernandez-Madrigal, J.A., Gonzalez, J.: Multihierarchical graph search. IEEE Trans. on PAMI 24(1), 103–113 (2002)
Ferrer, M., Karatzas, D., Valveny, E., Bardaji, I., Bunke, H.: A generic framework for median graph computation based on a recursive embedding approach. CVIU 115(7), 919–928 (2011)
Ferrer, M., Valveny, E., Serratosa, F.: Median graph: A new exact algorithm using a distance based on the maximum common subgraph. PRL 30(5), 579–588 (2009)
Ferrer, M., Valveny, E., Serratosa, F.: Median graphs: A genetic approach based on new theoretical properties. PR 42(9), 2003–2012 (2009)
Ferrer, M., Valveny, E., Serratosa, F., Riesen, K., Bunke, H.: Generalized median graph computation by means of graph embedding in vector spaces. PR 43(4), 1642–1655 (2010)
Foggia, P., Percannella, G., Sansone, C., Vento, M.: A graph-based algorithm for cluster detection. IJPRAI 22(5), 843–860 (2008)
Fränti, P., Virmajoki, O., Hautamaki, V.: Fast agglomerative clustering using a k-nearest neighbor graph. IEEE Trans. on PAMI 28(11), 1875–1881 (2006)
Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Analysis & Applications 13, 113–129 (2010), doi:10.1007/s10044-008-0141-y
Gauzere, B., Brun, L., Villemin, D.: Two new graphs kernels in chemoinformatics. PRL (2012) (in press)
Gerstmayer, M., Haxhimusa, Y., Kropatsch, W.: Hierarchical interactive image segmentation using irregular pyramids. In: Jiang, X., Ferrer, M., Torsello, A. (eds.) GbRPR 2011. LNCS, vol. 6658, pp. 245–254. Springer, Heidelberg (2011)
Gibert, J., Valveny, E., Bunke, H.: Feature selection on node statistics based embedding of graphs. PRL 33(15), 1980–1990 (2012)
Gibert, J., Valveny, E., Bunke, H.: Graph embedding in vector spaces by node attribute statistics. PR 45(9), 3072–3083 (2012)
Gonzalez-Diaz, R., Ion, A., Iglesias-Ham, M., Kropatsch, W.G.: Invariant representative cocycles of cohomology generators using irregular graph pyramids. CVIU 115(7), 1011–1022 (2011)
Gori, M., Maggini, M., Sarti, L.: Exact and approximate graph matching using random walks. IEEE Trans. on PAMI 27(7), 1100–1111 (2005)
Guigues, L., Le Men, H., Cocquerez, J.P.: The hierarchy of the cocoons of a graph and its application to image segmentation. PRL 24(8), 1059–1066 (2003)
Günter, S., Bunke, H.: Self-organizing map for clustering in the graph domain. PRL 23(4), 405–417 (2002)
Günter, S., Bunke, H.: Validation indices for graph clustering. PRL 24(8), 1107–1113 (2003)
Hagenbuchner, M., Gori, M., Bunke, H., Tsoi, A.C., Irniger, C.: Using attributed plex grammars for the generation of image and graph databases. PRL 24(8), 1081–1087 (2003)
Hancock, E.R., Wilson, R.C.: Pattern analysis with graphs: Parallel work at bern and york. PRL 33(7), 833–841 (2012)
He, L., Han, C.Y., Everding, B., Wee, W.G.: Graph matching for object recognition and recovery. PR 37(7), 1557–1560 (2004)
Hidović, D., Pelillo, M.: Metrics for attributed graphs based on the maximal similarity common subgraph. IJPRAI 18(3), 299–313 (2004)
Hu, W., Hu, W., Xie, N., Maybank, S.: Unsupervised active learning based on hierarchical graph-theoretic clustering. IEEE Trans. on SMC-B 39(5), 1147–1161 (2009)
Jain, B.J., Obermayer, K.: Graph quantization. CVIU 115(7), 946–961 (2011)
Cesar Jr., R.M., Bengoetxea, E., Bloch, I., Larrañaga, P.: Inexact graph matching for model-based recognition: Evaluation and comparison of optimization algorithms. PR 38(11), 2099–2113 (2005)
Justice, D., Hero, A.: A binary linear programming formulation of the graph edit distance. IEEE Trans. on PAMI 28(8), 1200–1214 (2006)
Kammerer, P., Glantz, R.: Segmentation of brush strokes by saliency preserving dual graph contraction. PRL 24(8), 1043–1050 (2003)
Kang, H.W.: G-wire: A livewire segmentation algorithm based on a generalized graph formulation. PRL 26(13), 2042–2051 (2005)
Kim, D.H., Yun, I.D., Lee, S.U.: Attributed relational graph matching based on the nested assignment structure. PR 43(3), 914–928 (2010)
Kim, J.S., Hong, K.S.: Colortexture segmentation using unsupervised graph cuts. PR 42(5), 735–750 (2009)
Kokiopoulou, E., Frossard, P.: Graph-based classification of multiple observation sets. PR 43(12), 3988–3997 (2010)
Kokiopoulou, E., Saad, Y.: Enhanced graph-based dimensionality reduction with repulsion laplaceans. PR 42(11), 2392–2402 (2009)
Kostin, A., Kittler, J., Christmas, W.: Object recognition by symmetrised graph matching using relaxation labelling with an inhibitory mechanism. PRL 26(3), 381–393 (2005)
Lezoray, O., Elmoataz, A., Bougleux, S.: Graph regularization for color image processing. CVIU 107(12), 38–55 (2007)
Lin, L., Liu, X., Zhu, S.C.: Layered graph matching with composite cluster sampling. IEEE Trans. on PAMI 32(8), 1426–1442 (2010)
Liu, J., Wang, B., Lu, H., Ma, S.: A graph-based image annotation framework. PRL 29(4), 407–415 (2008)
Lladós, J., Sánchez, G.: Graph matching versus graph parsing in graphics recognition: A combined approach. IJPRAI 18(3), 455–473 (2004)
Luo, B., Wilson, R.C., Hancock, E.R.: Spectral embedding of graphs. PR 36(10), 2213–2230 (2003)
Luo, B., Wilson, R.C., Hancock, E.R.: A spectral approach to learning structural variations in graphs. PR 39(6), 1188–1198 (2006)
Ma, F., Bajger, M., Slavotinek, J.P., Bottema, M.J.: Two graph theory based methods for identifying the pectoral muscle in mammograms. PR 40(9), 2592–2602 (2007)
Macrini, D., Dickinson, S., Fleet, D., Siddiqi, K.: Bone graphs: Medial shape parsing and abstraction. CVIU 115(7), 1044–1061 (2011)
Macrini, D., Dickinson, S., Fleet, D., Siddiqi, K.: Object categorization using bone graphs. CVIU 115(8), 1187–1206 (2011)
Mantrach, A., van Zeebroeck, N., Francq, P., Shimbo, M., Bersini, H., Saerens, M.: Semi-supervised classification and betweenness computation on large, sparse, directed graphs. PR 44(6), 1212–1224 (2011)
Martínez, A.M., Mittrapiyanuruk, P., Kak, A.C.: On combining graph-partitioning with non-parametric clustering for image segmentation. CVIU 95(1), 72–85 (2004)
Massaro, A., Pelillo, M.: Matching graphs by pivoting. PRL 24(8), 1099–1106 (2003)
Maulik, U.: Hierarchical pattern discovery in graphs. IEEE Trans. on SMC-C 38(6), 867–872 (2008)
de Mauro, C., Diligenti, M., Gori, M., Maggini, M.: Similarity learning for graph-based image representations. PRL 24(8), 1115–1122 (2003)
Neuhaus, M., Bunke, H.: Self-organizing maps for learning the edit costs in graph matching. IEEE Trans. on SMC-B 35(3), 503–514 (2005)
Neuhaus, M., Bunke, H.: Edit distance-based kernel functions for structural pattern classification. PR 39(10), 1852–1863 (2006)
Neuhaus, M., Bunke, H.: Automatic learning of cost functions for graph edit distance. Information Sciences 177(1), 239–247 (2007)
Qiu, H., Hancock, E.R.: Graph matching and clustering using spectral partitions. PR 39(1), 22–34 (2006)
Qiu, H., Hancock, E.R.: Graph simplification and matching using commute times. PR 40(10), 2874–2889 (2007)
Raveaux, R., Adam, S., Héroux, P., Trupin, É.: Learning graph prototypes for shape recognition. CVIU 115(7), 905–918 (2011)
Raveaux, R., Burie, J.C., Ogier, J.M.: A graph matching method and a graph matching distance based on subgraph assignments. PRL 31(5), 394–406 (2010)
Riesen, K., Bunke, H.: Graph classification by means of lipschitz embedding. IEEE Trans. on SMC-B 39(6), 1472–1483 (2009)
Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing 27(7), 950–959 (2009)
Riesen, K., Bunke, H.: Graph classification based on vector space embedding. IJPRAI 23, 1053–1081 (2009)
Riesen, K., Bunke, H.: Reducing the dimensionality of dissimilarity space embedding graph kernels. Engineering Applications of Artificial Intelligence 22, 48–56 (2009)
Robles-Kelly, A., Hancock, E.: Graph edit distance from spectral seriation. IEEE Trans. on PAMI 27(3), 365–378 (2005)
Robles-Kelly, A., Hancock, E.R.: String edit distance, random walks and graph matching. IJPRAI 18(3), 315–327 (2004)
Robles-Kelly, A., Hancock, E.R.: A graph-spectral method for surface height recovery. PR 38(8), 1167–1186 (2005)
Robles-Kelly, A., Hancock, E.R.: A riemannian approach to graph embedding. PR 40(3), 1042–1056 (2007)
Rohban, M.H., Rabiee, H.R.: Supervised neighborhood graph construction for semi-supervised classification. PR 45(4), 1363–1372 (2012)
Rota Bulò, S., Pelillo, M., Bomze, I.M.: Graph-based quadratic optimization: A fast evolutionary approach. CVIU 115(7), 984–995 (2011)
Ruberto, C.D.: Recognition of shapes by attributed skeletal graphs. PR 37(1), 21–31 (2004)
da, S., Torres, R., Falcão, A., da, F., Costa, L.: A graph-based approach for multiscale shape analysis. PR 37(6), 1163–1174 (2004)
Sanfeliu, A., Alquézar, R., Andrade, J., Climent, J., Serratosa, F., Vergés, J.: Graph-based representations and techniques for image processing and image analysis. PR 35(3), 639–650 (2002)
Sanfeliu, A., Serratosa, F., Alquezar, R.: Second-order random graphs for modeling sets of attributed graphs and their application to object learning and recognition. IJPRAI 18(3), 375–396 (2004)
Sanromà, G., Alquézar, R., Serratosa, F.: A new graph matching method for point-set correspondence using the em algorithm and softassign. CVIU 116(2), 292–304 (2012)
Santo, M.D., Foggia, P., Sansone, C., Vento, M.: A large database of graphs and its use for benchmarking graph isomorphism algorithms. PRL 24(8), 1067–1079 (2003)
Scheinerman, E.R., Tucker, K.: Modeling graphs using dot product representations. Computational Statistics 25, 1–16 (2010)
Sebastian, T., Klein, P., Kimia, B.: Recognition of shapes by editing their shock graphs. IEEE Trans. on PAMI 26(5), 550–571 (2004)
Serratosa, F., Alquezar, R., Sanfeliu, A.: Synthesis of function-described graphs and clustering of attributed graphs. IJPRAI 16(6), 621–655 (2002)
Serratosa, F., Alquézar, R., Sanfeliu, A.: Function-described graphs for modelling objects represented by sets of attributed graphs. PR 36(3), 781–798 (2003)
Shang, F., Jiao, L., Wang, F.: Graph dual regularization non-negative matrix factorization for co-clustering. PR 45(6), 2237–2250 (2012)
Shiga, M., Mamitsuka, H.: Efficient semi-supervised learning on locally informative multiple graphs. PR 45(3), 1035–1049 (2012)
Skomorowski, M.: Syntactic recognition of distorted patterns by means of random graph parsing. PRL 28(5), 572–581 (2007)
Solé-Ribalta, A., Serratosa, F.: Models and algorithms for computing the common labelling of a set of attributed graphs. CVIU 115(7), 929–945 (2011)
Solnon, C.: AllDifferent-based filtering for subgraph isomorphism. Artificial Intelligence 174, 850–864 (2010)
Sumengen, B., Manjunath, B.: Graph partitioning active contours (gpac) for image segmentation. IEEE Trans. on PAMI 28(4), 509–521 (2006)
Tang, H., Fang, T., Shi, P.F.: Nonlinear discriminant mapping using the laplacian of a graph. PR 39(1), 156–159 (2006)
Tang, J., Jiang, B., Zheng, A., Luo, B.: Graph matching based on spectral embedding with missing value. PR 45(10), 3768–3779 (2012)
Tao, W., Chang, F., Liu, L., Jin, H., Wang, T.: Interactively multiphase image segmentation based on variational formulation and graph cuts. PR 43(10), 3208–3218 (2010)
Torsello, A., Hancock, E.R.: Graph embedding using tree edit-union. PR 40(5), 1393–1405 (2007)
Ullmann, J.R.: Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J. Exp. Algorithmics 15, 1.6:1.1–1.6:1.64 (2011)
Wan, M., Lai, Z., Shao, J., Jin, Z.: Two-dimensional local graph embedding discriminant analysis (2dlgeda) with its application to face and palm biometrics. Neurocomputing 73(13), 197–203 (2009)
Wang, B., Pan, F., Hu, K.M., Paul, J.C.: Manifold-ranking based retrieval using k-regular nearest neighbor graph. PR 45(4), 1569–1577 (2012)
Wang, J.T., Zhang, K., Chang, G., Shasha, D.: Finding approximate patterns in undirected acyclic graphs. PR 35(2), 473–483 (2002)
Wilson, R., Hancock, E., Luo, B.: Pattern vectors from algebraic graph theory. IEEE Trans. on PAMI 27(7), 1112–1124 (2005)
Wilson, R.C., Zhu, P.: A study of graph spectra for comparing graphs and trees. PR 41(9), 2833–2841 (2008)
van Wyk, B., van Wyk, M.: Kronecker product graph matching. PR 36(9), 2019–2030 (2003)
van Wyk, B., van Wyk, M.: A pocs-based graph matching algorithm. IEEE Trans. on PAMI 26(11), 1526–1530 (2004)
van Wyk, M.A., van Wyk, B.J.: A learning-based framework for graph matching. IJPRAI 18(3), 355–374 (2004)
Xiao, B., Hancock, E.R., Wilson, R.C.: Graph characteristics from the heat kernel trace. PR 42(11), 2589–2606 (2009)
Xiao, Y., Dong, H., Wu, W., Xiong, M., Wang, W., Shi, B.: Structure-based graph distance measures of high degree of precision. PR 41(12), 3547–3561 (2008)
Xu, N., Ahuja, N., Bansal, R.: Object segmentation using graph cuts based active contours. CVIU 107(3), 210–224 (2007)
Yan, F., Christmas, W., Kittler, J.: Layered data association using graph-theoretic formulation with application to tennis ball tracking in monocular sequences. IEEE Trans. on PAMI 30(10), 1814–1830 (2008)
Yan, S., Xu, D., Zhang, B., Zhang, H.J., Yang, Q., Lin, S.: Graph embedding and extensions: A general framework for dimensionality reduction. IEEE Trans. on PAMI 29(1), 40–51 (2007)
Yang, F., Kruggel, F.: A graph matching approach for labeling brain sulci using location, orientation, and shape. Neurocomputing 73(13), 179–190 (2009)
Yang, L.: Building k-edge-connected neighborhood graph for distance-based data projection. PRL 26(13), 2015–2021 (2005)
You, Q., Zheng, N., Gao, L., Du, S., Wu, Y.: Analysis of solution for supervised graph embedding. IJPRAI 22(7), 1283–1299 (2008)
Yu, G., Peng, H., Wei, J., Ma, Q.: Mixture graph based semi-supervised dimensionality reduction. Pattern Recognition and Image Analysis 20, 536–541 (2010)
Zampelli, S., Deville, Y., Solnon, C.: Solving subgraph isomorphism problems with constraint programming. Constraints 15, 327–353 (2010)
Zanghi, H., Ambroise, C., Miele, V.: Fast online graph clustering via Erdos-Rényi mixture. PR 41(12), 3592–3599 (2008)
Zanghi, H., Volant, S., Ambroise, C.: Clustering based on random graph model embedding vertex features. PRL 31(9), 830–836 (2010)
Zaslavskiy, M., Bach, F., Vert, J.P.: A path following algorithm for the graph matching problem. IEEE Trans. on PAMI 31(12), 2227–2242 (2009)
Zhang, C., Wang, F.: A multilevel approach for learning from labeled and unlabeled data on graphs. PR 43(6), 2301–2314 (2010)
Zhang, F., Hancock, E.R.: Graph spectral image smoothing using the heat kernel. PR 41(11), 3328–3342 (2008)
Zhao, H., Robles-Kelly, A., Zhou, J., Lu, J., Yang, J.Y.: Graph attribute embedding via riemannian submersion learning. CVIU 115(7), 962–975 (2011)
Zhi, R., Flierl, M., Ruan, Q., Kleijn, W.: Graph-preserving sparse nonnegative matrix factorization with application to facial expression recognition. IEEE Trans. on SMC-B 41(1), 38–52 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vento, M. (2013). A One Hour Trip in the World of Graphs, Looking at the Papers of the Last Ten Years. In: Kropatsch, W.G., Artner, N.M., Haxhimusa, Y., Jiang, X. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2013. Lecture Notes in Computer Science, vol 7877. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38221-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-38221-5_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38220-8
Online ISBN: 978-3-642-38221-5
eBook Packages: Computer ScienceComputer Science (R0)