Structural Knowledge Discovery in Chemical and Spatio-Temporal Databases

AAAI 1999

TL;DR

This paper introduces SUBDUE, a graph-based relational discovery system, to extract structural knowledge from complex datasets like chemical compounds and spatio-temporal events. By applying SUBDUE to chemical toxicity and aviation safety/earthquake databases, the authors demonstrate its ability to uncover meaningful patterns that attribute-value systems miss, paving the way for more insightful data analysis.

What Problem Does This Paper Address?

Traditional knowledge discovery systems often rely on attribute-value representations, which can be limiting when dealing with data that has inherent relational structures. Many real-world domains, such as chemical molecules (where atoms are related by bonds) and spatio-temporal databases (where events are linked by proximity in space and time), are fundamentally relational. Extracting meaningful insights from these complex, interconnected datasets requires methods that can understand and leverage these relationships. This paper addresses the challenge of discovering structural patterns in such relational domains, going beyond simple attribute-based correlations.

Methods

The core of this work is the SUBDUE system, a graph-based relational discovery algorithm. SUBDUE operates on input data represented as graphs, where vertices and edges can be labeled. The system performs a beam search through the space of possible subgraphs within the input graph. The search is guided by the Minimum Description Length (MDL) principle, aiming to find subgraphs (substructures) that can effectively compress the original data. These substructures represent recurring patterns and, therefore, structural knowledge. SUBDUE's novelty lies in its ability to discover these structural patterns directly from relational data, unlike systems that require data to be pre-processed into a first-order logic format. The authors also mention experimenting with a new concept-learning version of SUBDUE that focuses on compressing positive data while ignoring negative data, aiming for competitive performance with existing concept-learning ILP systems.

Datasets

The paper evaluates SUBDUE on two main types of datasets:

  • Chemical Compounds: Data from the National Toxicology Program (ntp-server.niehs.nih.gov) was used to identify structural patterns associated with carcinogenicity. The dataset was split into a training set of 268 compounds and a testing set of 30 compounds.
  • Spatio-Temporal Databases:
    • Aviation Safety Reporting System (ASRS) database: This dataset contains reports describing incidents that could affect aviation safety, with 74 fields per record.
  • Earthquake database: This dataset comprises records of seismic events, each with 35 fields. For both spatio-temporal datasets, events were represented as vertices with attribute-labeled directed edges. Additionally, near_in_distance and near_in_time relational edges were added to augment the graphs, with empirically selected thresholds to avoid overwhelming the search.

Key Insights and Ideas

  • Relational Structure is Key: The paper strongly advocates for the importance of relational information in knowledge discovery, demonstrating that attribute-value systems are insufficient for domains with inherent structural relationships.
  • SUBDUE's Versatility: The system proves effective across diverse relational domains, from the intricate structures of chemical compounds to the temporal and spatial relationships of real-world events.
  • Discovering Hidden Correlations: SUBDUE can uncover patterns that are not immediately obvious, such as a specific bromine substructure being highly indicative of carcinogenicity or a recurring depth pattern in earthquakes suggesting geological faults.
  • Compression as a Measure of Knowledge: The MDL principle provides a principled way to identify significant substructures by finding those that best compress the data, effectively capturing recurring, informative patterns.

Key Results

  • Chemical Toxicity: SUBDUE identified a substructure containing a bromine atom that was present in a significantly higher proportion of carcinogenic training compounds (134/143) compared to non-carcinogenic ones (24/125). This pattern held up in the testing set (15/19 vs. 4/11), showing strong predictive power.
  • Aviation Safety: In the ASRS domain, SUBDUE found a substructure related to "damage" events using the near_in_distance relation. This suggests that damage-related incidents tend to be localized, prompting further investigation in those specific regions.
  • Earthquakes: For earthquake data, SUBDUE discovered a substructure linking earthquakes at a similar depth (33km) via the near_in_distance relation. This finding, corroborated by a geologist, points to a potential fault line in the area.
  • Performance: The authors state that the preliminary results of their new concept-learning version of SUBDUE are competitive with predominantly concept-learning ILP systems.

Limitations and Future Work

  • Limitations: The paper acknowledges that the empirical selection of distance and time thresholds for spatio-temporal relations was necessary to avoid overloading the graph search. This suggests that parameter tuning might be a factor in performance.
  • Future Work: The authors plan to continue analyzing these and other structural domains. They aim to compare SUBDUE's performance against competing ILP systems and domain-specific approaches more extensively. The development of a concept-learning version of SUBDUE is also an ongoing area of research. Source code for the SUBDUE system is available, encouraging further exploration and application.

Summary updated

BibTeX
@inproceedings{1999structural,
  title = {{Structural Knowledge Discovery in Chemical and Spatio-Temporal Databases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure