Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Neural Processing Letters
Erschienen in: Neural Processing Letters 2/2018

09.11.2017

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

verfasst von: Kaspar Riesen, Andreas Fischer, Horst Bunke

Erschienen in: Neural Processing Letters | Ausgabe 2/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces
Nächster Artikel A Temporal Dependency Based Multi-modal Active Learning Approach for Audiovisual Event Detection

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
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.
 
Literatur
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.
Koopmans T, Beckmann M (1975) Assignment problems and the location of economic activities. Econometrica 25:53–76MathSciNetCrossRef
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.
Neuhaus M, Bunke H (2007) Automatic learning of cost functions for graph edit distance. Inf Sci 177(1):239–247MathSciNetCrossRef
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.
Orlin J (1985) On the simplex algorithm for networks and generalized networks. Math Program Stud 24:166–178MathSciNetCrossRef
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.
Srinivasan V, Thompson G (1977) Cost operator algorithms for the transportation problem. Math Program 12:372–391MathSciNetCrossRef
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.
Metadaten
Titel
On the Impact of Using Utilities Rather than Costs for Graph Matching
verfasst von
Kaspar Riesen
Andreas Fischer
Horst Bunke
Publikationsdatum
09.11.2017
Verlag
Springer US
Erschienen in
Neural Processing Letters / Ausgabe 2/2018
Print ISSN: 1370-4621
Elektronische ISSN: 1573-773X
DOI
https://doi.org/10.1007/s11063-017-9739-7

Weitere Artikel der Ausgabe 2/2018

Neural Processing Letters 2/2018 Zur Ausgabe

OriginalPaper

Developmental Network: An Internal Emergent Object Feature Learning

OriginalPaper

On the Weighted Pseudo-Almost Periodic Solution for BAM Networks with Delays

OriginalPaper

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

OriginalPaper

Global Asymptotic Periodic Synchronization for Delayed Complex-Valued BAM Neural Networks via Vector-Valued Inequality Techniques

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

Neuer Inhalt

    Bildnachweise