On the influence of node centralities on graph edit distance for graph classification. (English) Zbl 1437.68137
Liu, Cheng-Lin (ed.) et al., Graph-based representations in pattern recognition. 10th IAPR-TC-15 international workshop, GbRPR 2015, Beijing, China, May 13–15, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9069, 231-241 (2015).
Summary: Classical graph approaches for pattern recognition applications rely on computing distances between graphs in the graph domain. That is, the distance between two graphs is obtained by directly optimizing some objective function which consider node and edge attributes. Bipartite Graph Matching was first published in a journal in 2009 and new versions have appeared to speed up its runtime such as the Fast Bipartite Graph Matching. This algorithm is based on defining a cost matrix between all nodes of both graphs and solving the node correspondence through a linear assignment method. To construct the matrix, several local structures can be defined from the simplest one (only the node) to the most complex (a whole clique or eigenvector structure). In this paper, we propose five different options and we show that the type of local structure and the distance defined between these structures is relevant for graph classification.
For the entire collection see [Zbl 1361.68010].
For the entire collection see [Zbl 1361.68010].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68T10 | Pattern recognition, speech recognition |
Keywords:
graph edit distance; bipartite graph matching; fast bipartite graph matching; Levenshtein distanceReferences:
| [1] | 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. Pattern Recognition 35(3), 639-650 (2002) · Zbl 1009.68178 · doi:10.1016/S0031-3203(01)00066-8 |
| [2] | Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty Years Of Graph Matching In Pattern Recognition. IJPRAI 18(3), 265-298 (2004) |
| [3] | Vento, M.: 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.) GbRPR 2013. LNCS, vol. 7877, pp. 1-10. Springer, Heidelberg (2013) · Zbl 1382.68212 · doi:10.1007/978-3-642-38221-5_1 |
| [4] | Hancock, E.R., Wilson, R.C.: Pattern analysis with graphs: Parallel work at Bern and York. Pattern Recognition Letters 33(7), 833-841 (2012) · doi:10.1016/j.patrec.2011.08.012 |
| [5] | Serratosa, F., Cortés, X., Solé-Ribalta, A.: Component Retrieval based on a Database of Graphs for Hand-Written Electronic-Scheme Digitalisation. Expert Systems With Applications, ESWA 40, 2493-2502 (2013) · doi:10.1016/j.eswa.2012.10.071 |
| [6] | Solé, A., Serratosa, F., Sanfeliu, A.: On the Graph Edit Distance cost: Properties and Applications. International Journal of Pattern Recognition and Artificial Intelligence 26(5) (2012) |
| [7] | Serratosa, F., Alquézar, R., Sanfeliu, A.: Estimating the Joint Probability Distribution of Random Vertices and Arcs by Means of Second-Order Random Graphs. In: Caelli, T.M., Amin, A., Duin, R.P.W., Kamel, M.S., de Ridder, D. (eds.) SPR 2002 and SSPR 2002. LNCS, vol. 2396, pp. 252-262. Springer, Heidelberg (2002) · Zbl 1073.68798 · doi:10.1007/3-540-70659-3_26 |
| [8] | Ferrer, M., Valveny, E., Serratosa, F.: Median graphs: A genetic approach based on new theoretical properties. Pattern Recognition 42(9), 2003-2012 (2009) · Zbl 1192.68571 · doi:10.1016/j.patcog.2009.01.034 |
| [9] | Ferrer, M., Valveny, E., Serratosa, F.: Median graph: A new exact algorithm using a distance based on the maximum common subgraph. Pattern Recognition Letters 30(5), 579-588 (2009) · doi:10.1016/j.patrec.2008.12.014 |
| [10] | Serratosa, F., Alquézar, R., Sanfeliu, A.: Estimating the Joint Probability Distribution of Random Vertices and Arcs by Means of Second-Order Random Graphs. In: Caelli, T.M., Amin, A., Duin, R.P.W., Kamel, M.S., de Ridder, D. (eds.) SPR 2002 and SSPR 2002. LNCS, vol. 2396, pp. 252-262. Springer, Heidelberg (2002) · Zbl 1073.68798 · doi:10.1007/3-540-70659-3_26 |
| [11] | Serratosa, F., Sanfeliu, A.: Function-Described Graphs applied to 3D object recognition. In: Del Bimbo, A. (ed.) ICIAP 1997. LNCS, vol. 1310, pp. 701-708. Springer, Heidelberg (1997) · doi:10.1007/3-540-63507-6_263 |
| [12] | Serratosa, F.: Fast Computation of Bipartite Graph Matching. Pattern Recognition Letters 45, 244-250 (2014) · doi:10.1016/j.patrec.2014.04.015 |
| [13] | Serratosa, F.: Speeding up Fast Bipartite Graph Matching trough a new cost matrix, International Journal of Pattern Recognition and Artificial Intelligence 29(2) (2015) |
| [14] | Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput. 27(7), 950-959 (2009) · doi:10.1016/j.imavis.2008.04.004 |
| [15] | Munkres, J.: Algorithms for the assignment and transportation problems. Journal of the Society for Industrial & Applied Mathematics 5, 32-38 (1957) · Zbl 0083.15302 · doi:10.1137/0105003 |
| [16] | Jonker, R., Volgenant, T.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325-340 (1987) · Zbl 0607.90056 · doi:10.1007/BF02278710 |
| [17] | Cortés, X., Serratosa, F.: An Interactive Method for the Image Alignment problem based on Partially Supervised Correspondence. Expert Systems With Applications 42(1), 179-192 (2015) · doi:10.1016/j.eswa.2014.07.051 |
| [18] | Serratosa, F., Cortés, X.: Interactive Graph-Matching using Active Query Strategies. Pattern Recognition 48, 1360-1369 (2015) · Zbl 1374.68476 · doi:10.1016/j.patcog.2014.10.033 |
| [19] | Riesen, K., Bunke, H., Fischer, A.: Improving Graph Edit Distance Approximation by Centrality Measures. In: International Congress on Pattern Recognition (2014) |
| [20] | Cortés, X., Serratosa, F.: Learning Graph-Matching Edit-Costs based on the Optimality of the Oracle’s Node Correspondences. Pattern Recognition Letters (2015) |
| [21] | Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, Cybernetics and Control Theory 10, 707-710 (1966) · Zbl 0149.15905 |
| [22] | Peris, G., Marzal, A.: Fast Cyclic Edit Distance Computation with Weighted Edit Costs in Classification. In: ICPR 2002, vol. 4, pp. 184-187 (2002) |
| [23] | Riesen, K. · doi:10.1007/978-3-540-89689-0_33 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
