Abstract
Although it is agreed that the Volgenant-Jonker (VJ) algorithm provides a fast way to approximate graph edit distance (GED), until now nobody has reported how the VJ algorithm can be tuned for this task. To this end, we revisit VJ and propose a series of refinements that improve both the speed and memory footprint without sacrificing accuracy in the GED approximation. We quantify the effectiveness of these optimisations by measuring distortion between control-flow graphs: a problem that arises in malware matching. We also document an unexpected behavioural property of VJ in which the time required to find shortest paths to unassigned nodes decreases as graph size increases, and explain how this phenomenon relates to the birthday paradox.
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
Balasn, E., Miller, D., Pekny, J., Toth, P.: A parallel shortest augmenting path algorithm for the assignment problem. JACM 38(4), 985–1004 (1991)
Bourquin, M., King, A., Robbins, E.: BinSlayer: Accurate Comparison of Binary Executables. In: Proceedings of Program Protection and Reverse Engineering Workshop. ACM (2013)
Burkard, R.E., Cela, E.: Linear Assignment Problems and Extensions. Springer (1999)
Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty Years of Graph Matching in Pattern Recognition. International Journal of Pattern Recognition and Artificial Intelligence 18(3), 265–298 (2004)
Gao, X., Xiao, B., Tao, D., Li, X.: A Survey of Graph Edit Distance. Pattern Analysis and Applications 13(1), 113–129 (2010)
Jonker, R., Volgenant, A.: A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38(4), 325–340 (1987)
Myers, R., Wison, R.C., Hancock, E.R.: Bayesian graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(6), 628–635 (2000)
Riesen, K., Bunke, H.: Approximate Graph Edit Distance computation by means of Bipartite Graph Matching. Image and Vision Computing 27(7), 950–959 (2009)
Serratosa, F.: Fast computation of bipartite graph matching. Pattern Recognition Letters 45, 244–250 (2014)
Serratosa, F., Cortés, X.: Edit Distance Computed by Fast Bipartite Graph Matching, pp. 253–262 (2014)
Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing Stars: On Approximating Graph Edit Distance. VLDB Endowment 2(1), 25–36 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Jones, W., Chawdhary, A., King, A. (2015). Revisiting Volgenant-Jonker for Approximating Graph Edit Distance. In: Liu, CL., Luo, B., Kropatsch, W., Cheng, J. (eds) Graph-Based Representations in Pattern Recognition. GbRPR 2015. Lecture Notes in Computer Science(), vol 9069. Springer, Cham. https://doi.org/10.1007/978-3-319-18224-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-18224-7_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18223-0
Online ISBN: 978-3-319-18224-7
eBook Packages: Computer ScienceComputer Science (R0)