Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Neural Processing Letters
Published in: Neural Processing Letters 2/2018

09-11-2017

On the Impact of Using Utilities Rather than Costs for Graph Matching

Authors: Kaspar Riesen, Andreas Fischer, Horst Bunke

Published in: Neural Processing Letters | Issue 2/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The concept of graph edit distance constitutes one of the most flexible graph matching paradigms available. The major drawback of graph edit distance, viz. the exponential time complexity, has been recently overcome by means of a reformulation of the edit distance problem to a linear sum assignment problem. However, the substantial speed up of the matching is also accompanied by an approximation error on the distances. Major contribution of this paper is the introduction of a transformation process in order to convert the underlying cost model into a utility model. The benefit of this transformation is that it enables the integration of additional information in the assignment process. We empirically confirm the positive effects of this transformation on five benchmark graph sets with respect to the accuracy and run time of a distance based classifier.
previous article Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces
next article A Temporal Dependency Based Multi-modal Active Learning Approach for Audiovisual Event Detection

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
2
The assignment problem can also be formulated as finding a matching in a complete bipartite graph and is therefore also referred to as bipartite graph matching problem.
 
3
Applying the greedy assignment on utilities rather than costs means that we replace \(\underset{\forall j }{\arg \min }\) by \(\underset{\forall j }{\arg \max }\), of course.
 
Literature
1.
Achatz H, Kleinschmidt P, Paparrizos K (1991) Applied geometry and discrete mathematics, chap. A dual forest algorithm for the assignment problem. AMS 1–11 (1991)
2.
3.
Ambauen R, Fischer S, Bunke H (2003) Graph edit distance with node splitting and merging and its application to diatom identification. In: Hancock E, Vento M (eds) Proceedings of 4th International workshop on graph based representations in pattern recognition, LNCS 2726. Springer, pp 95–106
4.
5.
Berretti S, Del Bimbo A, Vicario E (2001) Efficient matching and indexing of graph models in content-based retrieval. IEEE Trans Pattern Anal Mach Intell 23(10):1089–1105CrossRef
6.
Boeres M, Ribeiro C, Bloch I (2004) A randomized heuristic for scene recognition by graph matching. In: Ribeiro C, Martins S (eds) Proceedings of 3rd workshop on efficient and experimental algorithms, LNCS 3059. Springer, pp 100–113
7.
Bougleux S, Brun L, Carletti V, Foggia P, Gauzere B, Vento M (2017) Graph edit distance as a quadratic assignment problem. Pattern Recognit Lett 87(1):38–46CrossRef
8.
Bunke H, Allermann G (1983) Inexact graph matching for structural pattern recognition. Pattern Recognit Lett 1:245–253CrossRef
9.
Burkard R, Dell’Amico M, Martello S (2009) Assignment problems. Society for Industrial and Applied Mathematics, Philadelphia, PA, USACrossRef
10.
Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Int J Pattern Recognit Artif Intell 18(3):265–298CrossRef
11.
Cordella L, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 26(20):1367–1372CrossRef
12.
Cortes X, Serratosa F (2015) Learning graph-matching edit-costs based on the optimality of the oracle’s node correspondences. Pattern Recognit Lett 56:22–29CrossRef
13.
Eshera M, Fu K (1984) A graph distance measure for image analysis. IEEE Trans Syst Man Cybern (Part B) 14(3):398–408CrossRef
14.
Eshera M, Fu K (1984) A similarity measure between attributed relational graphs for image analysis. In: Proceedings of 7th international confernece on pattern recognition, pp 75–77
15.
Fankhauser S, Riesen K, Bunke H (2011) Speeding up graph edit distance computation through fast bipartite matching. In: Jiang X, Ferrer M, Torsello A (eds) Proceedings of 8th international workshop on graph based representations in pattern recognition, LNCS 6658, pp 102–111CrossRef
16.
Fischer A, Plamandon R, Savaria Y, Riesen K, Bunke H (2014) A Hausdorff heuristic for efficient computation of graph edit distance. In: Fränti P, Brown G, Loog M, Escolano F, Pelillo M (eds) Proceedings of international workshop on structural and syntactic pattern recognition, LNCS 8621, pp 83–92
17.
Foggia P, Percannella G, Vento M (2014) Graph matching and learning in pattern recognition in the last 10 years. Int J Pattern Recognit Artif Intell 28(1):1450001MathSciNetCrossRef
18.
Gärtner T, Horvath T, Wrobel S (2010) Graph kernels. Springer, Berlin, pp 467–469
19.
Gauzere B, Bougleux S, Riesen K, Brun L (2014) Approximate graph edit distance guided by bipartite matching of bags of walks. In: Fränti P, Brown G, Loog M, Escolano F, Pelillo M (eds) Proceedings of international workshop on structural and syntactic pattern recognition, LNCS 8621, pp 73–82
20.
Gauzere B, Brun L, Villemin D (2011) Two new graph kernels and applications to chemoinformatics. In: Jiang X, Ferrer M, Torsello A (eds) Proceedings of 8th international workshop on graph based representations in pattern recognition, pp 112–121CrossRef
21.
Gregory L, Kittler J (2002) Using graph search techniques for contextual colour retrieval. In: Caelli T, Amin A, Duin R, Kamel M, de Ridder D (eds) Proceedings of the joint IAPR international workshop on structural, syntactic, and statistical pattern recognition, LNCS 2396, pp 186–194
22.
Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100–107CrossRef
23.
Jones W, Chawdhary A, King A (2015) Revisiting volgenant-jonker for approximating graph edit distance. In: Liu C, Luo B, Kropatsch W, Cheng J (eds.) Proceedings of 10th international workshop on graph based representations in pattern recognition, LNCS 9069, pp 98–107
24.
Jonker R, Volgenant A (1987) A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38:325–340MathSciNetCrossRef
25.
Justice D, Hero A (2006) A binary linear programming formulation of the graph edit distance. IEEE Trans Pattern Anal Ans Mach Intell 28(8):1200–1214CrossRef
26.
27.
28.
Levenshtein V (1966) Binary codes capable of correcting deletions, insertions and reversals. Sov Phys Dokl 10(8):707–710MathSciNet
29.
30.
Neuhaus M, Bunke H (2004) A probabilistic approach to learning costs for graph edit distance. In: Kittler J, Petrou M, Nixon M (eds) Proceedings of 17th international conference on pattern recognition, 3, pp 389–393
31.
Neuhaus M, Bunke H (2005) Self-organizing maps for learning the edit costs in graph matching. IEEE Trans Syst Man Cybern (Part B) 35(3):503–514CrossRef
32.
33.
Neuhaus M, Bunke H (2007) Bridging the gap between graph edit distance and kernel machines. World Scientific, SingaporeCrossRef
34.
Neuhaus M, Riesen K, Bunke H (2006) Fast suboptimal algorithms for the computation of graph edit distance. In: Yeung DY, Kwok J, Fred A, Roli F, de Ridder D (eds) Proceedings of 11th international workshop on strucural and syntactic pattern recognition, LNCS 4109, pp 163–172
35.
36.
Riesen K (2016) Structural pattern recognition with graph edit distance. Springer, BerlinMATH
37.
Riesen K, Bunke H (2008) IAM graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo N et al (ed) Structural, syntactic, and statistical pattern recognition, LNCS 5342, pp 287–297
38.
Riesen K, Bunke H (2009) Approximate graph edit distance computation by means of bipartite graph matching. Image Vis Comput 27(4):950–959CrossRef
39.
Riesen K, Bunke H (2010) Graph classification and clustering based on vector space embedding. World Scientific, SingaporeCrossRef
40.
Riesen K, Fankhauser S, Bunke H (2007) Speeding up graph edit distance computation with a bipartite heuristic. In: Frasconi P, Kersting K, Tsuda K (eds) Proceedings of 5th international workshop on mining and learning with graphs, pp 21–24
41.
Riesen K, Ferrer M, Dornberger R, Bunke H (2015) Greedy graph edit distance. In: Perner P (ed) Proceedings 11th international conference on machine learning and data mining in pattern recognition, LNAI 9166, pp 1–14CrossRef
42.
Riesen K, Ferrer M, Fischer A, Bunke H (2015) Approximation of graph edit distance in quadratic time. In: Liu C, Luo B, Kropatsch W, Cheng J (eds) Proceedings of 10th international workshop on graph based representations in pattern recognition, LNCS 9069, pp 3–12
43.
Riesen K, Fischer A, Bunke H (2014) Computing upper and lower bounds of graph edit distance in cubic time. In: Gayar N, Schwenker F, Suen C (eds) Proceedings of international workshop on artificial neural networks in pattern recognition, LNAI 8774, pp 129–140
44.
Riesen K, Fischer A, Bunke H (2014) Improving graph edit distance approximation by centrality measures. In: Proceedings of 22nd international conference on pattern recognition, pp 3910–3914
45.
Riesen K, Fischer A, Bunke H (2016) Approximation of graph edit distance by means of a utility matrix. In: Schwenker F, Abbas H, El Gayar N, Trentin E (eds) Proceedings of 7th IAPR TC3 workshop on artificial neural networks in pattern recognition, LNCS 9896. Springer, pp 185–194
46.
Riesen K, Neuhaus M, Bunke H (2007) Bipartite graph matching for computing the edit distance of graphs. In: Escolano F, Vento M (eds) Proceedings of 6th international workshop on graph based representations in pattern recognition, LNCS 4538, pp 1–12
47.
Rossi L, Torsello A, Hancock E (2013) A continuous-time quantum walk kernel for unattributed graphs. In: Kropatsch W, Artner N, Haxhimusa Y, Jiang X (eds) Proceedings of 9th international workshop on graph based representations in pattern recognition, pp 101–110CrossRef
48.
Sanfeliu A, Fu K (1983) A distance measure between attributed relational graphs for pattern recognition. IEEE Trans Syst Man Cybern (Part B) 13(3):353–363CrossRef
49.
50.
Serratosa F (2014) Fast computation of bipartite graph matching. Pattern Recognit Lett 45:244–250CrossRef
51.
Serratosa F (2015) Speeding up fast bipartite graph matching through a new cost matrix. Int J Pattern Recognit Artif Intell 29(2):1550010MathSciNetCrossRef
52.
Serratosa F, Cortés X, Solé-Ribalta A (2012) On the graph edit distance cost: properties and applications. Int J Pattern Recognit Artif Intell 26(5):126MathSciNet
53.
Serratosa F, Solé-Ribalta A, Cortes X (2011) Automatic learning of edit costs based on interactive and adaptive graph recognition. In: Jiang X, Ferrer M, Torsello A (eds) Proceedings of 8th international workshop on graph based representations in pattern recognition, LNCS 6658, pp 152–163CrossRef
54.
Sorlin S, Solnon C (2005) Reactive tabu search for measuring graph similarity. In: Brun L, Vento M (eds) Proceedings of 5th international workshop on graph-based representations in pattern recognition, LNCS 3434. Springer, pp 172–182
55.
56.
Tsai W, Fu K (1979) Error-correcting isomorphism of attributed relational graphs for pattern analysis. IEEE Trans Syst Man Cybern (Part B) 9(12):757–768CrossRef
57.
Tsai W, Fu K (1983) Subgraph error-correcting isomorphisms for syntactic pattern recognition. IEEE Trans Syst Man Cybern (Part B) 13:48–61MathSciNetCrossRef
58.
Metadata
Title
On the Impact of Using Utilities Rather than Costs for Graph Matching
Authors
Kaspar Riesen
Andreas Fischer
Horst Bunke
Publication date
09-11-2017
Publisher
Springer US
Published in
Neural Processing Letters / Issue 2/2018
Print ISSN: 1370-4621
Electronic ISSN: 1573-773X
DOI
https://doi.org/10.1007/s11063-017-9739-7

Other articles of this Issue 2/2018

Neural Processing Letters 2/2018 Go to the issue

OriginalPaper

Method for Meteorological Early Warning of Precipitation-Induced Landslides Based on Deep Neural Network

OriginalPaper

Approximate Solutions of Initial Value Problems for Ordinary Differential Equations Using Radial Basis Function Networks

OriginalPaper

First-Order Sensitivity Analysis for Hidden Neuron Selection in Layer-Wise Training of Networks

OriginalPaper

A New Conjugate Gradient Method with Smoothing Regularization Based on a Modified Secant Equation for Training Neural Networks

OriginalPaper

Theoretical Foundations for the Alpha-Beta Associative Memories: 10 Years of Derived Extensions, Models, and Applications

OriginalPaper

Exploring Implicit Semantic Constraints for Bilingual Word Embeddings