Some Links Between Formal Concept Analysis and Graph Mining
Abstract
This chapter presents a formal model to learning from examples represented by labelled graphs. This formal model is based upon lattice theory and in particular Galois lattices. We widen the domain of formal concept analysis, by the use of the Galois lattices model with structural descriptions of examples and concepts. The operational implementation of our model, called "Graal" (for GRAph And Learning) constructs a Galois lattice for any description language provided that the operations of comparison and generalization are determined for that language. These operations exist in the case of labelled graphs satisfying an partial order relation (homomorphism). This paper is concerned as well with the known problems regarding propositionalization (i.e. the transformation of a structural description in a propositional description). Using classical lattice results, we have a formal model for the transformation of a structural machine learning problem into a propositional one.
Keywords
mining graph data
cyclic pattern kernels
densest subgraph problem
frequent subgraph mining
frequent subgraphs
frequent connected subgraphs
graph mining algorithm
rightmost extension
discovered subgraphs
frequent graphs
frequent graph patterns
subgraph extraction
cousin extension
discovery using minimum description length
exact graph matching
canonical label
mutagenesis dataset
entity resolution
graph drawing techniques
pattern growth approach
best substructure
subdue system
frequent substructures
overlapping subgraphs
singular vector value
Domains
Artificial Intelligence [cs.AI]
Loading...