Design and Analysis of Efficient Class-oriented Graph Mining Systems

我们的研究目标是开发一个有效的图模式设计系统，以便从图结构的数据中进行高效的数据挖掘。(1)树收缩模式(简称TC-模式)是给定的无序树共有的无序树结构模式，它是通过边收缩将每个不常见的连通子结构合并成一个顶点而得到的。我们证明了TC-模式的一个重要子类是由正数据归纳推断的多项式时间。此外，我们还讨论了TC-模式学习问题的优化形式，并给出了优化问题难以计算的条件。(2)引入上下文确定正则形式图系统(FGS)作为一种有效的图模式设计系统，并在MAT学习框架下提出了一种学习上下文确定正则FGS的多项式时间算法。

Our object of this research is to develop an effective graph pattern designing system for efficient data mining from graph-structured data. During this research period, the following results mainly were obtained.(1) A tree contraction pattern (TC-pattern) is an unordered tree-structured pattern common to given unordered trees, which is obtained by merging every uncommon connected substructure into one vertex by edge contraction. We show that an important subclass of TC-patterns is polynomial-time inductively inferable from positive data. Moreover, we discuss the optimization versions of the learning problems for TC-patterns, and give the conditions under which the optimization problems are hard to compute.(2) We introduce context-deterministic regular formal graph systems (FGS) as one of the effective graph pattern designing systems, and propose a polynomial time algorithm for learning the class of context-deterministic regular FGSs in the framework of MAT learning.