Graph Clustering and Model Learning by Data Compression

Abstract

This paper uses a minimal representation criterion to formally define tasks of matching, classification, and interpretation of objects represented as graphs, as well as conceptual clustering of graphs, and supervised learning of structured concepts represented as probabilistic graphs. These definitions do not rely on acceptance thresholds, or other user selectable parameters. The resulting problems of combinatorial optimization are approximately solved by a fast graph matching heuristic, which is a key element of the described learning methods, that include forced learning of graph models, and two graph clustering methods: incremental, and agglomerative. These methods apply to usual directed graphs, and to recursively defined layered graphs. The presented methodology has been applied to real problems of concept learning, classification and interpretation of nonrigid shapes.