Graph embedding using tree edit-union
- 31 May 2007
- journal article
- Published by Elsevier BV in Pattern Recognition
- Vol. 40 (5), 1393-1405
- https://doi.org/10.1016/j.patcog.2006.09.006
Abstract
In this paper we address the problem of how to learn a structural prototype that can be used to represent the variations present in a set of trees. The prototype serves as a pattern space representation for the set of trees. To do this we construct a super-tree to span the union of the set of trees. This is a chicken and egg problem, since before the structure can be estimated correspondences between the nodes of the super-tree and the nodes of the sample tree must be to hand. We demonstrate how to simultaneously estimate the structure of the super-tree and recover the required correspondences by minimizing the sum of the tree edit-distances over pairs of trees, subject to edge consistency constraints. Each node of the super-tree corresponds to a dimension of the pattern space, and for each tree we construct a pattern vector in which the elements of the weights corresponding to each of the dimensions of the super-tree. We perform pattern analysis on the set of trees by performing principal components analysis on the vectors. The method is illustrated on a shape analysis problem involving shock-trees extracted from the skeletons of 2D objects.Keywords
This publication has 23 references indexed in Scilit:
- Central Clustering of Attributed GraphsMachine Learning, 2004
- First order Gaussian graphs for efficient structure classificationPattern Recognition, 2003
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003
- Dominant sets and hierarchical clusteringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Normalized cuts and image segmentationIeee Transactions On Pattern Analysis and Machine Intelligence, 2000
- Combinatorial search versus genetic algorithms: A case study based on the generalized median graph problemPattern Recognition Letters, 1999
- Genetic operators for hierarchical graph clusteringPattern Recognition Letters, 1998
- Learning Bayesian networks: The combination of knowledge and statistical dataMachine Learning, 1995
- Learning Graph Models of ShapePublished by Elsevier BV ,1988