Learning Unordered Tree Contraction Patterns in Polynomial Time

摘要

In this paper, we present a concept of edge contraction-based tree-structured patterns as a graph pattern suited to represent treestructured data. A tree contraction pattern (TC-pattern) is an unordered tree-structured pattern common to a given tree-structured data, which is obtained by merging every uncommon connected substructure into one vertex by edge contraction. In this paper, in order to establish an algorithmic foundation for the discovery of knowledge from tree-structured data, we show that TC-patterns are learnable in polynomial time.