Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph emb...

Full description

Saved in:
Bibliographic Details
Published in:Pattern recognition 2010-04, Vol.43 (4), p.1642-1655
Main Authors: Ferrer, M., Valveny, E., Serratosa, F., Riesen, K., Bunke, H.
Format: Article
Language:English
Subjects:
Algorismes computacionals
Algorithms and architectures for advanced scientific computing
Algorísmica i teoria de la complexitat
Anàlisi numèrica
Applied sciences
Computer algorithms
Computer science
control theory
systems
Exact sciences and technology
Graph embedding
Graph matching
Information systems. Data bases
Information theory
Information, signal and communications theory
Informàtica
Informàtica teòrica
Matemàtiques i estadística
Median graph
Memory organisation. Data processing
Modelització matemàtica
Percepció de les estructures
Processament de dades
Software
Telecommunications and information theory
Vector spaces
Weighted mean of graphs
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.
ISSN:0031-3203
1873-5142
DOI:10.1016/j.patcog.2009.10.013