"Structure induction by lossless graph compression"

Leonid Peshkin
Center for Biomedical Informatics
Harvard Medical School

In Proceedings of DCC 2007 - Data Compression Conference, Snowbird, UT, USA

Abstract:
=========

This work is motivated by the necessity to automate the discovery of structure in vast 
and ever-growing collection of relational data commonly represented as graphs, for 
example genomic networks. A novel algorithm, dubbed <EM>Graphitour</EM>, for structure 
induction by lossless graph compression is presented and illustrated by a clear and 
broadly known case of nested structure in a DNA molecule. 
This work extends to graphs some well established approaches to grammatical inference 
previously applied only to strings. The bottom-up graph compression problem is related 
to the maximum cardinality (non-bipartite)  maximum cardinality matching problem.
The algorithm accepts a variety of graph types including directed graphs and graphs 
with labeled nodes and arcs. 
The resulting structure could be used for representation and classification of graphs.