Abstract
Efficiently storing and retrieving complex structural data remains a significant challenge in computational science. This paper, originally presented at AAAI 1984, introduces a graph retrieval system that organizes data into a hierarchy based on the "subgraph-of" relationship. By representing all data as subsets of a single "universal graph," the system enables rapid structural searches and autonomously discovers meaningful patterns without explicit supervision.
Introduction
Searching through databases of structural information, such as molecular diagrams or circuit layouts, is computationally expensive. Tasks like finding every molecule containing a specific chemical ring involve solving the subgraph isomorphism problem, which is NP-complete. Standard databases excel at matching scalar values but falter with structural queries, including exact matches, supergraph/subgraph searches, and similarity matches. Robert Levinson's work addresses this by proposing a system that organizes graphs into a self-structuring knowledge base rather than treating them as isolated data points.
System Architecture
The system's efficiency stems from two primary architectural innovations: the Universal Graph and a hierarchical partial ordering.
The Universal Graph
Instead of storing each graph independently, the system maintains a single "Universal Graph." Every data item is represented as a specific subset of nodes within this overarching structure. This mapping allows the system to substitute expensive graph isomorphism checks with faster linear set operations. For instance, if Graph A's node set is a subset of Graph B's in the universal representation, it is a strong candidate for being a subgraph, eliminating approximately 20% of traditional node-by-node comparisons.
Hierarchical Partial Ordering
The system organizes all known graphs into a hierarchy based on the "subgraph-of" relation. This hierarchy ranges from "primitives" (individual atoms or labels) at the bottom to the Universal Graph at the apex. Intermediate nodes represent "concepts"—subgraphs that appear within the data.
Retrieval is performed via a two-phase algorithm:
- Phase 1 (Bottom-Up): Identifies "immediate predecessors," the largest subgraphs of the query already present in the database.
- Phase 2 (Top-Down): Identifies "immediate successors," the smallest supergraphs containing the query.
Concept Discovery and Self-Optimization
A key feature of this system is its ability to "learn" and optimize its own structure. As new graphs are added, the system identifies frequently occurring subgraphs. In chemical datasets, the system autonomously discovered functional groups such as arene, ether, and phenol because they emerged as critical nodes in the partial ordering. By inserting these discovered concepts into the hierarchy, the system creates a more balanced search tree, significantly reducing the number of comparisons required for future queries.
Evaluation and Results
The system was primarily evaluated using organic chemistry data, starting with a database of 600 complete structures, 50 intermediate concepts, and 100 primitives.
- Search Efficiency: In a database of 200 concepts, a typical query required only about 25 node-by-node searches, a vast improvement over linear scanning.
- Structural Insight: The system derived generalizations from reaction data, enabling it to suggest chemical precursors for molecules not yet in the database.
Conclusion and Future Work
While the 1984 results were promising, the author noted several areas for expansion. These included automating the discovery of "relaxed matching" equivalence classes (e.g., treating Chlorine and Bromine similarly) and improving the heuristics for "close match" searches. Furthermore, the scalability of the Universal Graph approach to millions of compounds remains a subject for modern investigation.
Summary updated