|
Title:
|
ORDERED GRAPH PATTERNS WHICH ARE POLYNOMIAL TIME INDUCTIVELY INFERABLE FROM POSITIVE DATA |
|
Author(s):
|
Takahiro Hino, Yusuke Suzuki, Tomoyuki Uchida, Tetsuhiro Miyahara |
|
ISBN:
|
978-989-8704-04-7 |
|
Editors:
|
Philip Powell, Miguel Baptista Nunes and Pedro Isaías |
|
Year:
|
2014 |
|
Edition:
|
Single |
|
Keywords:
|
Machine learning, Graph mining, Inductive inference |
|
Type:
|
Full Paper |
|
First Page:
|
263 |
|
Last Page:
|
270 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Ordered graphs, each of whose vertices has a unique order on edges incident to the vertex, can represent graph structured data such as Web pages, TeX sources, CAD, and map data. First in order to design computational machine learning for such data, we introduce an ordered graph pattern g with ordered graph structures and structured variables and its ordered graph pattern language GL(g) as the set of all ordered graphs obtained from g by replacing structured variables in g with arbitrary ordered graphs. The minimal language problem for the class OGPL = {GL(g) | g is an ordered graph pattern} is, given a set S of ordered graphs, to find an ordered graph pattern g such that GL(g) is minimal among all ordered graph pattern languages, that contain all ordered graphs in S. Second, we give a polynomial time algorithm for solving the minimal language problem for OGPL. Hence, we show that the class OGPL is polynomial time inductively inferable from positive data. Finally, we implement the proposed algorithm on a computer and evaluate the algorithm by reporting experimental results. |
|
|
|
|
|
|
