Frequent free tree discovery in graph data
Published 14 March 2004
Ulrich Rückert, Stefan Krämer
Citations72
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper is investigating the middle ground between these two extremes: mining free trees in graph data, and defining free trees and their canonical form, before presenting FreeTreeMiner, an algorithm making efficient use of this canonical form during search.
Abstract
In recent years, researchers in graph mining have been exploring linear paths as well as subgraphs as pattern languages. In this paper, we are investigating the middle ground between these two extremes: mining free (that is, unrooted) trees in graph data. The motivation for this is the need to upgrade linear path patterns, while avoiding complexity issues with subgraph patterns. Starting from such complexity considerations, we are defining free trees and their canonical form, before we present FreeTreeMiner, an algorithm making efficient use of this canonical form during search. Experiments with two datasets from the National Cancer Institute's Developmental Therapeutics Program (DTP), anti-HIV and anti-cancer screening data, are reported.
Keywords
Computer Science
gSpan: graph-based substructure pattern mining
2,030 Citations2003Xifeng Yan, Jiawei Han
A novel algorithm called gSpan (graph-based substructure pattern mining), which discovers frequent substructures without candidate generation by building a new lexicographic order among graphs, and maps each graph to a unique minimum DFS code as its canonical label.
Frequent subgraph discovery
1,063 Citations2002M. Kuramochi, George Karypis
The empirical results show that the algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though it has to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery.
Lecture notes in computer scienceAn Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data
1,029 Citations2000Akihiro Inokuchi, Takashi Washio +1 more
A novel approach named AGM to efficiently mine the association rules among the frequently appearing substructures in a given graph data set through the extended algorithm of the basket analysis is proposed.
JNCI Journal of the National Cancer InstituteNew Soluble-Formazan Assay for HIV-1 Cytopathic Effects: Application to High-Flux Screening of Synthetic and Natural Products for AIDS-Antiviral Activity
691 Citations1989O. S. Weislow, Rebecca Kiser +4 more
Journal of Artificial Intelligence ResearchSubstructure Discovery Using Minimum Description Length and Background Knowledge
481 Citations1994Diane J. Cook, Lawrence B. Holder
A new version of the SUBDUE substructure discovery system based on the minimum description length principle is described, which discovers substructures that compress the original data and represent structural concepts in the data.
Efficiently mining frequent trees in a forest
467 Citations2002Mohammed J. Zaki
This work presents TREEMinER, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list, and finds that TREEMINER outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties.
Mining molecular fragments: finding relevant substructures of molecules
438 Citations2003Christian Borgelt, Michael R. Berthold
An algorithm to find fragments in a set of molecules that help to discriminate between different classes of for instance, activity in a drug discovery context is presented, which results in substantially faster search by eliminating the need for frequent, computationally expensive reembeddings and by suppressing redundant search.
Journal of the American Chemical SocietyArtificial intelligence approach to structure-activity studies. Computer automated structure evaluation of biological activity of organic molecules
425 Citations1984Gilles Klopman
Quantitative Structure-Activity RelationshipsMULTICASE 1. A Hierarchical Computer Automated Structure Evaluation Program
314 Citations1992Gilles Klopman
A new algorithm, called MULTICASE, can automatically identify molecular sub-structures that have a high probability of being relevant or responsible for the observed biological activity of a learning set comprised of a mix of active and inactive molecules of diverse composition.
Machine LearningComplete Mining of Frequent Patterns from Graphs: Mining Graph Data
279 Citations2003Akihiro Inokuchi, Takashi Washio +1 more
This paper proposes a novel principle and its algorithm that derive the characteristic patterns which frequently appear in graph-structured data and can derive all frequent induced subgraphs from both directed and undirected graph structured data having loops having loops with labeled or unlabeled nodes and links.
Molecular feature mining in HIV data
225 Citations2001Stefan Krämer, Luc De Raedt +1 more
The application of Feature Mining techniques to the Developmental Therapeutics Program's AIDS antiviral screen database is presented, with the aim of detecting molecular substructures that are frequent in the active molecules, and infrequent in the inactives.
TreeFinder: a first step towards XML data mining
185 Citations2003Alexandre Termier, M.-C. Rousset +1 more
This paper considers the problem of searching frequent trees from a collection of tree-structured data modeling XML data, and shows that TreeFinder reaches completeness or falls short for a range of experimental settings.
Computing frequent graph patterns from semistructured data
167 Citations2003Natalia Vanetik, Ehud Gudes +1 more
A new algorithm for mining graph data is proposed, based on a novel definition of support, that can be useful for many applications, including: compact representation of source information and a road-map for browsing and querying information sources.
LiriasThe levelwise version space algorithm and its application to molecular fragment finding
135 Citations2001Luc De Raedt, Stefan Krämer
A tight integration of Mitchell's version space algorithm with Agrawal et al.'s Apriori algorithm with an important application in chemo-informatics, i.e. that of finding fragments of interest within a given set of compounds.
Lecture notes in computer scienceOptimized Substructure Discovery for Semi-structured Data
120 Citations2002Kenji Abe, Shinji Kawasoe +3 more
An efficient algorithm is presented that discovers the best labeled ordered trees that optimize a given statistical measure, such as the information entropy and the classification accuracy, in a collection of semi-structured data.
Indexing and mining free trees
109 Citations2004Y. Chi, Yining Yang +1 more
This work presents FreeTreeMiner, a computationally efficient algorithm that discovers all frequently occurring subtrees in a database of free trees and defines a novel representation, the canonical form, for rooted trees and extends the definition to free trees.
Lirias (KU Leuven)Feature Construction with Version Spaces for Biochemical Applications
81 Citations2001Stefan Krämer, Luc De Raedt
BioinformaticsA survey of the Predictive Toxicology Challenge 2000–2001
65 Citations2003Christoph Helma, Stefan Krämer
An evaluation of the most accurate models by toxicological experts showed, that it is still hard for domain experts to interpret the submitted models and to put them into relation with toxicological knowledge.
Faster subtree isomorphism
28 Citations2002Ron Shamir, Dekel Tsur
An O(~k/Sup 1.8//log k\ n) time algorithm is given for the subtree isomorphism problem, where k and n are the number of vertices in H and G respectively, which improves over the O(k/sup 1.5/n) algorithms of Chung and Matula.
SAR and QSAR in environmental researchFragment generation and support vector machines for inducing SARs
25 Citations2002Stefan Krämer, Eibe Frank +1 more
Experiments in the domains of carcinogenicity and mutagenicity prediction show that the minimum and the maximum frequency queries for fragments can be answered within a reasonable time, and that the predictive accuracy obtained using these fragments is satisfactory.
Environmental Health PerspectivesData quality in predictive toxicology: identification of chemical structures and calculation of chemical properties.
21 Citations2000Christoph Helma, Stefan Krämer +2 more
This paper discusses the potential sources of errors associated with the identification of compounds, the representation of their structures, and the calculation of chemical descriptors and proposes methods applicable to the routine quality control of large chemical datasets.
Generalized Version Space Trees.
8 Citations2003Ulrich Rückert, Stefan Krämer
Experiments with two data sets from the National Cancer Institute's Developmental Therapeutics Program indicate that generalized version space trees can boost inductive queries considerably while featuring moderately increased space requirements in comparison to a version space representation based on boundary sets.