Empirical and theoretical analysis of relational concept learning using a graph-based representation

We introduce a graph-based relational concept learning approach and its implementation in the SubdueCL system. We describe three approaches of learning systems that use a graph representation: the Galois Lattice, Conceptual Graphs, and Subdue. The study of these systems gave us significant insight on how the concept-learning task is conducted in a graph-based system and also on how we can elaborate a theoretical analysis of our system. In the theory part we performed a PAC learning analysis of our system where we found that it is possible to PAC learn single-graphs with our approach using a polynomial number of examples. For the case of learning multiple graphs in DNF, the number of examples needed is exponential, but with experimental results we show that SubdueCL does not need that many examples to learn. We also compared our graph-based concept learning approach to the Galois lattice formal framework, which attempts to constrain the search space to polynomial size. We show that SubdueCL also creates a Galois lattice except that SubdueCL's lattice may add graphs which are super-graphs of others while removing graphs that are not connected. Then, we present SubdueCL, our graph-based concept learner, and show some experimental results including a comparison of SubdueCL with the Inductive Logic Programming systems FOIL and Progol. Results show that SubdueCL is competitive with logic-based learners using structural data. Results in an artificial domain show that SubdueCL learns successfully in training example graphs of various size, density and noise. In the case of noise (when the positive concept also exists in the negative graphs), SubdueCL learns several more specific graphs found in the positive graphs, but not in the negative graphs. In the case of density, SubdueCL tends to learn more sub-graphs (to represent the concept) as the graph density increases. Results from the theoretical and empirical analyses indicate that our graph-based approach to concept learning is efficient and effective.