Generalized Median Graph via Iterative Alternate Minimizations - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Generalized Median Graph via Iterative Alternate Minimizations

Graph médian généralisé via des minimisations alternées.

(1) , (1) , (2) , (1)
1
2

Abstract

Computing a graph prototype may constitute a core element for clustering or classification tasks. However, its computation is an NP-Hard problem, even for simple classes of graphs. In this paper, we propose an efficient approach based on block coordinate descent to compute a generalized median graph from a set of graphs. This approach relies on a clear definition of the optimization process and handles labeling on both edges and nodes. This iterative process optimizes the edit operations to perform on a graph alternatively on nodes and edges. Several experiments on different datasets show the efficiency of our approach.
Calculer un graphe prototype peut constituer une étape centrale pour des méthodes de clustering ou de classification. Toutefois, ce calcul est NP-difficile même pour des classes de graphes simples. Nous proposons dans ce papier une approche efficace basée sur une minimisation alternée pour calculer le graphe médian d'un ensemble. Cette approche s'appuie sur une définition claire du processus d'optimisation et inclue l'étiquetage à la fois des nœuds et des arêtes. Ce processus itératif optimise les opérations à effectuer alternativement sur les sommets et les arêtes. Plusieurs expériences sur des jeux de données différents montrent l'efficacité de notre approche.
Fichier principal
Vignette du fichier
gbr19median.pdf (343.66 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02162838 , version 1 (24-06-2019)

Identifiers

Cite

Nicolas Boria, Sébastien Bougleux, Benoit Gaüzère, Luc Brun. Generalized Median Graph via Iterative Alternate Minimizations. IAPR International workshop on Graph-Based Representation in Pattern Recognition, Donatello Conte, Jean-Yves Ramel,, Jun 2019, Tours, France. pp.99-109, ⟨10.1007/978-3-030-20081-7_10⟩. ⟨hal-02162838⟩
34 View
67 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More