Substructure Discovery Using Minimum Description Length and Background Knowledge

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 minimumdescription 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.

• Publication year

  1993

• Venue

  Journal of Artificial Intelligence Research

• Publication date

  1993-08-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1613/JAIR.43arXiv cs/9402102
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Unifying Learning Methods by Colored Digraphs

  1993cited by this paper
• AutoClass: a Bayesian classification system

  1993cited by this paper
• Discovery of Inexact Concepts from Structural Data

  1993cited by this paper
• Spatial Analogy and Subsumption

  1992cited by this paper
• Book Review: Pattern Recognition: statistical, structural and neural approaches

  1992cited by this paper
• Learning Engineering Models with the Minimum Description Length Principle

  1992cited by this paper
• A Minimal Encoding Approach to Feature Discovery

  1991cited by this paper
• Concept formation in structured domains

  1991cited by this paper
• Grammatical Inference Based on Hyperedge Replacement

  1990cited by this paper
• Graph Clustering and Model Learning by Data Compression

  1990cited by this paper
• Empirical Substructure Discovery

  1989cited by this paper
• Some Experiments in Applying Inductive Inference Principles to Surface Reconstruction

  1989cited by this paper
• Inferring Decision Trees Using the Minimum Description Length Principle

  1989cited by this paper
• Part Segmentation for Object Recognition

  1989cited by this paper
• Discrete mathematical structures for computer science

  1988cited by this paper
• Structural Methods in Pattern Recognition

  1986cited by this paper
• A Self-Organizing Retrieval System for Graphs

  1984influential reference
• Inexact graph matching for structural pattern recognition

  1983cited by this paper
• Learning from Observation: Conceptual Clustering

  1983cited by this paper
• Syntactic pattern recognition and applications

  1983cited by this paper
• Understanding Line drawings of Scenes with Shadows

  1975cited by this paper
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters

  1971cited by this paper
• Learning structural descriptions from examples

  1970cited by this paper
• Laws of organization in perceptual forms.

  1938influential reference

• Neural Graduated Assignment for Maximum Common Edge Subgraphs

  2025cites this paper
• Causal DAG Summarization (Full Version)

  2025cites this paper
• Scalable Substructure Discovery Algorithm For Homogeneous Multilayer Networks

  2025influential citation
• Causal DAG Summarization

  2025cites this paper
• Fast Subgraph Matching by Dynamic Graph Editing

  2024cites this paper
• Model repair supported by frequent anomalous local instance graphs

  2024cites this paper
• MLN-Subdue: Substructure Discovery In Homogeneous Multilayer Networks

  2024influential citation
• IVE: Accelerating Enumeration-Based Subgraph Matching via Exploring Isolated Vertices

  2024cites this paper
• Substructure Discovery in Heterogeneous Multilayer Networks

  2024cites this paper
• Graph Stream Compression Scheme Based on Pattern Dictionary Using Provenance

  2024cites this paper
• SCHENO: Measuring Schema vs. Noise in Graphs

  2024cites this paper
• Sturgeon-GRAPH: Constrained Graph Generation from Examples

  2023cites this paper
• DomainNet: Homograph Detection and Understanding in Data Lake Disambiguation

  2023cites this paper
• Unexpected Attributed Subgraphs: a Mining Algorithm

  2023cites this paper
• Mining Association Rules from a Single Large Graph

  2023influential citation
• An efficient approach for faster matching of approximate patterns in graphs

  2023cites this paper
• KG-MDL: Mining Graph Patterns in Knowledge Graphs with the MDL Principle

  2023cites this paper
• Isomorphisms Between Dense Random Graphs

  2023cites this paper
• Identification of co-existing embeddings of a motif in multilayer networks

  2022cites this paper
• Assessing Hierarchies by Their Consistent Segmentations

  2022cites this paper
• Sequential pattern mining on chemical bonding database in the bioinformatics field

  2022cites this paper
• Semantic Image Collection Summarization With Frequent Subgraph Mining

  2022influential citation
• Summarizing Labeled Multi-Graphs

  2022influential citation
• Interesting Patterns From COVID‐19 Dataset Using Graph‐Based Statistical Analysis for Preventive Measures

  2021cites this paper
• Efficient Graph Summarization using Weighted LSH at Billion-Scale

  2021cites this paper
• A Heuristic Algorithm to Compute a Subgraph for TSP Based on Frequency Quadrilaterals

  2021cites this paper
• Finding Motifs in Knowledge Graphs using Compression

  2021cites this paper
• PSpan: Mining Frequent Subnets of Petri Nets

  2021cites this paper
• Multi-relation Graph Summarization

  2021cites this paper
• Graph Similarity Description: How Are These Graphs Similar?

  2021cites this paper
• Ensemble Distributed Search-FSGM-CRD Compressed Cache Algorithm for Large Datasets

  2021cites this paper
• Dynamic Graph Learning Convolutional Networks for Semi-supervised Classification

  2021cites this paper
• DECOUPLING-BASED APPROACH TO CENTRALITY DETECTION IN HETEROGENEOUS MULTILAYER NETWORKS by KIRAN MUKUNDA

  2021cites this paper
• GAWD: graph anomaly detection in weighted directed graph databases

  2021influential citation
• Frequent Pattern Mining in Continuous-Time Temporal Networks

  2021cites this paper
• GraphMDL+: interleaving the generation and MDL-based selection of graph patterns

  2021cites this paper
• Compressing Graph Data by Leveraging Domain Independent Knowledge

  2021influential citation
• Online summarization of dynamic graphs using subjective interestingness for sequential data

  2020cites this paper
• An alternative topic model based on Common Interest Authors for topic evolution analysis

  2020cites this paper
• Utility-Based Graph Summarization: New and Improved

  2020cites this paper
• Mining Top-k pairs of correlated subgraphs in a large network

  2020cites this paper
• Detecting Anomalous Graphs in Labeled Multi-Graph Databases

  2020cites this paper
• The minimum description length principle for pattern mining: a survey

  2020cites this paper
• Motif Discovery Algorithms in Static and Temporal Networks: A Survey

  2020influential citation
• GraphMDL : sélection de motifs de graphes avec le principe MDL

  2020cites this paper
• Scalable and Interpretable Graph Modeling with Graph Grammars Thesis Proposal

  2020cites this paper
• Summarizing Complex Graphical Models of Multiple Chronic Conditions Using the Second Eigenvalue of Graph Laplacian: Algorithm Development and Validation

  2020cites this paper
• Finding Key Structures in MMORPG Graph with Hierarchical Graph Summarization

  2020cites this paper
• Optimized Candidate Generation for Frequent Subgraph Mining in a Single Graph

  2020cites this paper
• SOME OBSERVATION OF ALGORITHMS DEVELOPED FOR ANOMALY DETECTION

  2020cites this paper
• Fast and efficient parallel breadth-first search with power-law graph transformation

  2020cites this paper
• An Approach For Concept Drift Detection in a Graph Stream Using Discriminative Subgraphs

  2020cites this paper
• Connecting the Dots: Event Graph Schema Induction with Path Language Modeling

  2020cites this paper
• GraphMDL: Graph Pattern Selection Based on Minimum Description Length

  2020cites this paper
• Adaptive Multi-model Approaches to Pattern Set Mining

  2020cites this paper
• Prefix Tree Based MapReduce Approach for Mining Frequent Subgraphs

  2019cites this paper
• A graph mining-based methodology for discovering and visualizing high-level knowledge for building energy management

  2019cites this paper
• Time-Varying Water Quality Analysis with Semantical Mining Technology

  2019cites this paper
• Summarizing Complex Graphical Models of Multiple Chronic Conditions Using the Second Eigenvalue of Graph Laplacian: Algorithm Development and Validation (Preprint)

  2019cites this paper
• An advanced review on text mining in medicine

  2019cites this paper
• Efficient frequent subgraph mining on large streaming graphs

  2019cites this paper
• Title Comparing biological networks via graph compression

  2019cites this paper
• An updated dashboard of complete search FSM implementations in centralized graph transaction databases

  2019cites this paper
• Extraction de motifs spatio-temporels : co-localisations, séquences et graphes dynamiques attribués. (Mining spatio-temporal patterns: colocations, sequences and dynamic attributed graphs)

  2019cites this paper
• Capturing Binary Graphs

  2019cites this paper
• A Review on Design Pattern Detection

  2019cites this paper
• Supervised Learning for Demospongiae Identification using Graph Mining Technique

  2019cites this paper
• Crowdsourcing service requirement oriented requirement pattern elicitation method

  2019cites this paper
• Modeling Graphs with Vertex Replacement Grammars

  2019influential citation
• Aggregated search in Distributed Graph Databases

  2019cites this paper
• Summarizing Dynamic Graphs using MDL

  2019cites this paper
• Leveraging Compression-Based Graph Mining for Behavior-Based Malware Detection

  2019cites this paper
• Mining significant trend sequences in dynamic attributed graphs

  2019cites this paper
• Why Multilayer Networks Instead of Simple Graphs? Modeling Effectiveness and Analysis Flexibility and Efficiency!

  2019cites this paper
• Discovery of Functional Motifs from the Interface Region of Oligomeric Proteins Using Frequent Subgraph Mining

  2019cites this paper
• Mining the Enriched Subgraphs for Specific Vertices in a Biological Graph

  2019cites this paper
• PSM-Flow: Probabilistic Subgraph Mining for Discovering Reusable Fragments in Workflows

  2018cites this paper
• A New Multigraph Transformation Method for Frequent Approximate Subgraph Mining

  2018cites this paper
• Automatic discovery of concepts and actions

  2018cites this paper
• ( k , p )-Planar Graphs A Generalization of Planar Representations for Cluster Graphs

  2018cites this paper
• A Descriptive Tolerance Nearness Measure for Performing Graph Comparison

  2018cites this paper
• Query Processing on Attributed Graphs

  2018cites this paper
• Humble Data Management to Big Data Analytics/Science: A Retrospective Stroll

  2018cites this paper
• Utility-Driven Graph Summarization

  2018cites this paper
• Prioritized Relationship Analysis in Heterogeneous Information Networks

  2018cites this paper
• Controversy Rules - Discovering Regions Where Classifiers (Dis-)Agree Exceptionally

  2018cites this paper
• GBTM: Graph Based Troubleshooting Method for Handling Customer Cases Using Storage System Log

  2018cites this paper
• Approximate Query Algorithm Based on Graph Topological Relation

  2018cites this paper
• Optimization-Driven Emergence of Deep Hierarchies with Applications in Data Mining and Evolution

  2018cites this paper
• Algorithm Selection for Maximum Common Subgraph

  2018cites this paper
• Discovering Communities and Anomalies in Attributed Graphs

  2018cites this paper
• Structural graph learning in real-world digital forensics

  2018cites this paper
• Counting motifs in dynamic networks

  2018cites this paper
• SparkFSM: A Highly Scalable Frequent Subgraph Mining Approach using Apache Spark

  2018cites this paper
• Observations from Parallelising Three Maximum Common (Connected) Subgraph Algorithms

  2018cites this paper
• Reducing large graphs to small supergraphs: a unified approach

  2018cites this paper
• Representative frequent approximate subgraph mining on multi-graph collections

  2018influential citation
• Large Scale Graph Matching(LSGM): Techniques, Tools, Applications and Challenges

  2017cites this paper
• Summarizing Static and Dynamic Big Graphs

  2017cites this paper
• Geographic Information Systems and Geomatics

  2017cites this paper