Source-linked AI summary
Substructure Discovery Using Minimum Description Length and Background Knowledge
D. J. Cook, L. B. Holder
TL;DR
Structural data can overwhelm researchers seeking meaningful concepts. SUBDUE uses minimum description length, approximate graph matching, and background knowledge to discover compressive substructures; experiments show these substructures can significantly reduce graph representation size.
Problem
The growing volume of structural data creates a need for techniques that can analyze it and discover concepts.
Method
SUBDUE discovers compressive substructures using minimum description length, computationally bounded inexact graph matching, and optional background knowledge.
Results
SUBDUE-discovered substructures can significantly reduce the data needed to represent input graphs across experiments.
Takeaways & Limitations
Minimum description length can provide hierarchical descriptions of structural regularities while supporting discovery of compressive substructures.
Takeaways & Limitations
The most compressive substructure is not always the most interesting or important one.
Abstract
from arXiv · showhide
The ability to identify interesting and repetitive substructures is an essential component to discovering knowledge in structural data. We describe a new version of our SUBDUE substructure discovery system based on the minimum description length principle. The SUBDUE system discovers substructures that compress the original data and represent structural concepts in the data. By replacing previously-discovered substructures in the data, multiple passes of SUBDUE produce a hierarchical description of the structural regularities in the data. SUBDUE uses a computationally-bounded inexact graph match that identifies similar, but not identical, instances of a substructure and finds an approximate measure of closeness of two substructures when under computational constraints. In addition to the minimum description length principle, other background knowledge can be used by SUBDUE to guide the search towards more appropriate substructures. Experiments in a variety of domains demonstrate SUBDUE's ability to find substructures capable of compressing the original data and to discover structural concepts important to the domain. Description of Online Appendix: This is a compressed tar file containing the SUBDUE discovery system, written in C. The program accepts as input databases represented in graph form, and will output discovered substructures with their corresponding value.
. Conclusions
The work shows that MDL-based substructure discovery identifies repetitive structural concepts across domains while compressing data representations. Inexact matching, background knowledge, and iterative replacement support deviation-tolerant and hierarchical discovery.
- Conclusions: MDL enables substructure discovery across a variety of structural-data domains.The discovered substructures represent concepts found in the data.
- Conclusions: Background knowledge can guide discovery, while inexact graph matching permits deviations among substructure instances.The matching approach supports similar rather than identical instances.
- Conclusions: Replacing discovered-substructure instances with concept definitions compresses data descriptions and supports hierarchically defined structures.Abstraction over repeated instances reduces representation complexity.
- Future work: Future work will combine structural discovery with concept discovery through a linear representation such as AutoClass and scale the system to larger structural databases.The planned system will use Subdue to compress AutoClass inputs and evaluate structures within generated classes.
Ac kno wledgemen ts
The authors acknowledge NASA grant support, circuit data provided by Mike Shay at National Semiconductor, project assistance, and reviewers’ insightful comments.
- The project was supported by a NASA grant.
- Mike Shay at National Semiconductor provided the circuit data.
- Surnjani Djoko and Tom Lai helped with the project, and the reviewers offered numerous insightful comments.