Structure induction by lossless graph compression
<|reference_start|>Structure induction by lossless graph compression: This work is motivated by the necessity to automate the discovery of structure in vast and evergrowing collection of relational data commonly represented as graphs, for example genomic networks. A novel algorithm, dubbed Graphitour, 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.<|reference_end|>
@article{peshkin2007structure,
    title={Structure induction by lossless graph compression},
    author={Leonid Peshkin},
    journal={In proceedings of the Data Compression Conference, 2007, pp 53-62,
  published by the IEEE Computer Society Press},
    year={2007},
    doi={10.1109/DCC.2007.73},
    archivePrefix={arXiv},
    eprint={cs/0703132},
    primaryClass={cs.DS cs.IT cs.LG math.IT}
}