State of the art of graph-based data mining
ACM SIGKDD Explorations NewsletterPublished 1 July 2003
Takashi Washio, Hiroshi Motoda
Citations446
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 article introduces the theoretical basis of graph based data mining and surveys the state of the art of graph-based data mining.
Abstract
The need for mining structured data has increased in the past few years. One of the best studied data structures in computer science and discrete mathematics are graphs. It can therefore be no surprise that graph based data mining has become quite popular in the last few years.This article introduces the theoretical basis of graph based data mining and surveys the state of the art of graph-based data mining. Brief descriptions of some representative approaches are provided as well.
Keywords
Computer Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
Fast algorithms for mining association rules
10,739 Citations1998Rakesh Agrawal, Ramakrishnan Srikant
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.
The Journal of Logic ProgrammingInductive Logic Programming: Theory and methods
1,550 Citations1994Stephen Muggleton, Luc De Raedt
The most important theories and methods of Inductive Logic Programming, a new discipline which investigates the inductive construction of first-order clausal theories from examples and background knowledge, are surveyed.
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.
Journal of Medicinal ChemistryStructure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. Correlation with molecular orbital energies and hydrophobicity
872 Citations1991Asim K. Debnath, Rosa L. Lopez de Compadre +3 more
A review of the literature yielded data on over 200 aromatic and heteroaromatic nitro compounds tested for mutagenicity in the Ames test and a quantitative structure-activity relationship (QSAR) has been derived for 188 congeners, showing that chemicals possessing three or more fused rings possess much greater mutagenic potency than compounds with one or two fused rings.
Diffusion Kernels on Graphs and Other Discrete Input Spaces
732 Citations2002Risi Kondor, John Lafferty
This paper proposes a general method of constructing natural families of kernels over discrete structures, based on the matrix exponentiation idea, and focuses on generating kernels on graphs, for which a special class of exponential kernels called diffusion kernels are proposed.
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.
Communications of the ACMA database perspective on knowledge discovery
470 Citations1996Tomasz Imieliński, Heikki Mannila
The concept of data mining as a querying process and the first steps toward efficient development of knowledge discovery applications are discussed.
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.
ACM SIGKDD Explorations NewsletterA survey of kernels for structured data
450 Citations2003Thomas Gärtner
This survey describes several approaches of defining positive definite kernels on structured instances directly on the basis of areal vector space and thus in a single table.
Data Mining and Knowledge DiscoveryDiscovery of frequent DATALOG patterns
309 Citations1999Luc De Raedt, Hannu Toivonen
WARMR is presented, a general purpose inductive logic programming algorithm that addresses frequent query discovery: a very general DATALOG formulation of the frequent pattern discovery problem.
Discovering generalized episodes using minimal occurrences
309 Citations1996Heikki Mannila, Hannu Toivonen
A general and flexible framework of specifying classes of generalized episodes that are recurrent combinations of events satisfying certain conditions is presented, which can be instantiated to a wide variety of applications by selecting suitable primitive conditions.
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.
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.
Applied IntelligenceGraph-based induction as a unified learning framework
86 Citations1994Kenichi Yoshida, Hiroshi Motoda +1 more
A graph-based induction algorithm that extracts typical patterns from colored digraphs is described that enables the uniform treatment of these two learning tasks to solve complex learning problems such as the construction of hierarchical knowledge bases.
Structural Machine Learning with Galois Lattice and Graphs
80 Citations1998Michael Liquiere, Jean Sallantin
This paper defines a formal approach to learning from examples described by labelled graphs and constructs a Galois lattice for any description language provided that the two operations of comparison and generalization are determined for that language.
Faster association rules for multiple relations
71 Citations2001Siegfried Nijssen, Joost N. Kok
Using an implementation that is coined FARMER, it is shown that indeed a speed-up is obtained and that, using these ideas, the performance is much more comparable to original association rule algorithms.
An assessment of submissions made to the predictive toxicology evaluation challenge
36 Citations1999Ashwin Srinivasan, Ross D. King +1 more
An assessment of machine learning (ML) submissions made to the Predictive Toxicology Evaluation Challenge suggests that ML techniques have been able to respond -not fully, but nevertheless substantially -to the PTE Challenge.