Abstract
This paper deals with algorithms for detecting graph isomorphism (GI) properties. The GI literature consists of numerous research directions, from highly theoretical studies (e.g. defining the GI complexity class) to very practical applications (pattern recognition, image processing). We first present the context of our work and provide a brief overview of various algorithms developed in such disparate contexts. Compared to well-known NP-complete problems, GI is only rarely tackled with general-purpose combinatorial optimization techniques; however, classical search algorithms are commonly applied to graph matching (GM). We show that, by specifically focusing on exploiting isomorphism properties, classical GM heuristics can become very useful for GI. We introduce a polynomial graph extension procedure that provides a graph coloring (labeling) capable of rapidly guiding a simple-but-effective heuristic toward the solution. The resulting algorithm (GI-Ext) is quite simple, very fast and practical: it solves GI within a time in the region of O(|V|3) for numerous graph classes, including difficult (dense and regular) graphs with up to 20.000 vertices and 200.000.000 edges. GI-Ext can compete with recent state-of-the-art GI algorithms based on well-established GI techniques (e.g. canonical labeling) refined over the last three decades. In addition, GI-Ext also solves certain GM problems, e.g. it detects important isomorphic structures induced in non-isomorphic graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Auwatanamongkol, S.: Inexact graph matching using a genetic algorithm for image recognition. Pattern Recogn. Lett. 28(12), 1428–1437 (2007)
Babai, L., Erdos, P., Selkow, M.: Random graph isomorphism. SIAM J. Comput. 9(3), 628–635 (1980)
Babai, L., Grigoryev, D.Y., Mount, D.M.: Isomorphism of graphs with bounded eigenvalue multiplicity. In: Fourteenth Annual ACM Symposium on Theory of Computing, pp. 310–7324 (1982)
Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 171–183. ACM, New York, NY, USA (1983)
Bengoetxea, E., Larrańaga, P., Bloch, I., Perchant, A., Boeres, C.: Inexact graph matching by means of estimation of distribution algorithms. Pattern Recogn. 35(12), 2867–2880 (2002)
Booth, K.S.: Isomorphism testing for graphs, semigroups, and finite automata are polynomially equivalent problems. SIAM J. Comput. 7(3), 273–279 (1978)
Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recogn. Lett. 18(8), 689–694 (1997)
Bunke, H.: Recent developments in graph matching. In: Proc. 15th International Conference on Pattern Recognition, vol. 2, pp. 117–124 (2000)
Cesar, R.M., Bengoetxea, E., Bloch, I., Larra naga, P.: Inexact graph matching for model-based recognition: evaluation and comparison of optimization algorithms. Pattern Recogn. 38(11), 2099–2113 (2005)
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18(3), 265–298 (2004)
Conte, D., Foggia, P., Vento, M.: Challenging complexity of maximum common subgraph detection algorithms: a performance analysis of three algorithms on a wide database of graphs. J. Graph Algorithms Appl. 11(1), 99–143 (2007)
Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367–1372 (2004)
Corneil, D.G., Gotlieb, C.C.: An efficient algorithm for graph isomorphism. J. Assoc. Comput. Mach. 17(1), 51–64 (1970)
Darga, P.T., Liffiton, M.H., Sakallah, K.A., Markov, I.L.: Exploiting structure in symmetry detection for CNF. In: Proceedings of the 41st Annual Conference on Design Automation, pp. 530–534. ACM, New York, NY, USA (2004)
Darga, P.T., Sakallah, K.A., Markov, I.L.: Faster symmetry discovery using sparsity of symmetries. In: Proceedings of the 45th Annual Conference on Design Automation, pp. 149–154. ACM, New York, NY, USA (2008)
De Santo, M., Foggia, P., Sansone, C., Vento, M.: A large database of graphs and its use for benchmarking graph isomorphism algorithms. Pattern Recogn. Lett. 24(8), 1067–1079 (2003)
Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In: STOC ’80: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pp. 236–243. ACM (1980)
Fortin, S.: The graph isomorphism problem. Technical Report TR96–20, University of Alberta, Edmonton, Canada (1996)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness, pp. 154–161,202. W.H. Freeman & Co., New York, NY, USA (1979)
Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 18(4), 377–387 (1998)
Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation. Oper. Res. 39(3), 378–406 (1991)
Junttila, T., Kaski, P.: Engineering an efficient canonical labeling tool for large and sparse graphs. In: Applegate, D., et al. (eds.) Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, pp. 135–149. SIAM (2007)
Kincaid, R.K.: A molecular structure matching problem. Comput. Oper. Res. 24(1), 25–35 (1997)
Kirkpatric, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Levi, G.: A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcolo 9(4), 341–352 (1973)
López-Presa, J.L., Fernández Anta, A.: Fast algorithm for graph isomorphism testing. In: SEA. LNCS, vol. 5526, pp. 221–232 (2009)
Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci 25(1), 42–65 (1982)
Luo, B., Hancock, E.R.: Structural graph matching using the EM algorithm and singular value decomposition. IEEE Trans. Pattern Anal. Mach. Intell. 23, 1120–1136 (2001)
McKay, B.D.: Practical graph isomorphism. Congressus Numerantium 30, 45–87 (1981)
Messmer, B.T., Bunke, H.: A new algorithm for error-tolerant subgraph isomorphism detection. IEEE Trans. Pattern Anal. Mach. Intell. 20(5), 493–504 (1998)
Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput.-Aided Mol. Des. 16(7), 521–533 (2002)
Sammoud, O., Solnon, C., Ghédira, K.: Ant algorithm for the graph matching problem. In: Raidl, G.R., et al. (eds.) Evocop. LNCS, vol. 3448, pp. 213–223. Springer (2005)
Sanfeliu, A., Fu, K.S.: Distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. 13(3), 353–362 (1983)
Schmidt, D.C., Druffel, L.E.: A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. J. Assoc. Comput. Mach. 23(3), 433–445 (1976)
Singh, M., Chatterjee, A., Chaudhury, S.: Matching structural shape descriptions using genetic algorithms. Pattern Recogn. 30(9), 1451–1462 (1997)
Ullmann, J.R.: An algorithm for subgraph isomorphism. J. Assoc. Comput. Mach. 23, 31–42 (1976)
Wang, Y.K., Fan, K.C., Horng, J.T.: Genetic-based search for error-correcting graph isomorphism. IEEE Trans. Syst. Man Cybern. Part B 27(4), 588–597 (1997)
Williams, M.L., Wilson, R.C., Hancock, E.R.: Deterministic search for relational graph matching. Pattern Recogn. 32(7), 1255–1271 (1999)
Wiskott, L., Fellous, J.M., Krüger, N., von der Malsburg, C.: Face recognition by elastic bunch graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 19(7), 775–779 (1997)
Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. J. Math. Sci. 29(4), 1426–1481 (1985)
Zhang, K., Statman, R., Shasha, D.: On the editing distance between unordered labeled trees. Inf. Process. Lett. 42(3), 133–139 (1992)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Porumbel, D.C. Isomorphism Testing via Polynomial-Time Graph Extensions. J Math Model Algor 10, 119–143 (2011). https://doi.org/10.1007/s10852-010-9145-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-010-9145-x