Abstract
In structural pattern recognition, given a set of graphs, the computation of a Generalized Median Graph is a well known problem. Some methods approach the problem by assuming a relation between the Generalized Median Graph and the Common Labelling problem. However, this relation has still not been formally proved. In this paper, we analyse such relation between both problems. The main result proves that the cost of the common labelling upper-bounds the cost of the median with respect to the given set. In addition, we show that the two problems are equivalent in some cases.
We acknowledge financial support from the FET programme within the EU FP7, under the SIMBAD project (contract 213250), from Consolider Ingenio 2010 project (CSD2007-00018) and from the CICYT project (DPI2010-17112).
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
Jiang, X., Müunger, A., Bunke, H.: On median graphs: Properties, algorithms, and applications. IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1144–1151 (2001)
Dickinson, P.J., Bunke, H., Dadej, A., Kraetzl, M.: Matching graphs with unique node labels. Pattern Anal. Appl. 7(3), 243–254 (2004)
Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. In: Proc. VLDB Endow., vol. 2(1), pp. 25–36 (August 2009)
Ferrer, M., Serratosa, F., Sanfeliu, A.: Synthesis of Median Spectral Graph. In: Marques, J.S., Pérez de la Blanca, N., Pina, P. (eds.) IbPRIA 2005, Part II. LNCS, vol. 3523, pp. 139–146. Springer, Heidelberg (2005)
Ferrer, M., Serratosa, F., Valveny, E.: Evaluation of Spectral-Based Methods for Median Graph Computation. In: Martí, J., Benedí, J.M., Mendonça, A.M., Serrat, J. (eds.) IbPRIA 2007, Part II. LNCS, vol. 4478, pp. 580–587. Springer, Heidelberg (2007)
Ferrer, M., Valveny, E., Serratosa, F., Riesen, K., Bunke, H.: Generalized median graph computation by means of graph embedding in vector spaces. Pattern Recognition 43(4), 1642–1655 (2010)
Hlaoui, A., Wang, S.: Median graph computation for graph clustering. Soft Computing - A Fusion of Foundations, Methodologies and Applications 10, 47–53 (2006)
Jain, B.J., Wysotzki, F.: Central clustering of attributed graphs. Machine Learning 56, 169–207 (2004)
Jain, B., Obermayer, K.: Elkan’s k-Means Algorithm for Graphs. In: Sidorov, G., Hernández Aguirre, A., Reyes García, C.A. (eds.) MICAI 2010, Part II. LNCS, vol. 6438, pp. 22–32. Springer, Heidelberg (2010)
Solé-Ribalta, A., Serratosa, F.: Graduated Assignment Algorithm for Finding the Common Labelling of a Set of Graphs. In: Hancock, E.R., Wilson, R.C., Windeatt, T., Ulusoy, I., Escolano, F. (eds.) SSPR&SPR 2010. LNCS, vol. 6218, pp. 180–190. Springer, Heidelberg (2010)
Solé-Ribalta, A., Serratosa, F.: Models and algorithms for computing the common labelling of a set of attributed graphs. Comput. Vis. Image Underst. 115(7), 929–945 (2011)
Justice, D., Hero, A.: A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence 28, 1214 (2006)
Mukherjee, L., Singh, V., Peng, J., Xu, J., Zeitz, M., Berezney, R.: Generalized median graphs and applications. Journal of Combinatorial Optimization 17, 21–44 (2009)
Solé-Ribalta, A.: Multiple graph matching and applications. PhD thesis, Universitat Rovira i Virgili (2012)
Wong, A.K.C., You, M.: Entropy and distance of random graphs with application to structural pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence (5), 599–609 (1985)
Edwards, A., Cavalli-Sforza, L.: A method for cluster analysis. Biometrics 21, 362–375 (1965)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rebagliati, N., Solé-Ribalta, A., Pelillo, M., Serratosa, F. (2012). On the Relation between the Common Labelling and the Median Graph. In: Gimel’farb, G., et al. Structural, Syntactic, and Statistical Pattern Recognition. SSPR /SPR 2012. Lecture Notes in Computer Science, vol 7626. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34166-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-34166-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34165-6
Online ISBN: 978-3-642-34166-3
eBook Packages: Computer ScienceComputer Science (R0)