Exact Learning of Finite Unions of Graph Patterns from Queries

Abstract

A linear graph pattern is a labeled graph such that its vertices have constant labels and its edges have either constant or mutually distinct variable labels. An edge having a variable label is called a variable and can be replaced with an arbitrary labeled graph. Let ${\mathcal GPC}$ be the set of all linear graph patterns having a structural feature ${\mathcal C}$ like “having a tree structure”, “having a two-terminal series parallel graph structure” and so on. The graph language GLc ( g ) of a linear graph pattern g in ${\cal GP}({\mathcal C})$ is the set of all labeled graphs obtained from g by substituting arbitrary labeled graphs having the structural feature ${\mathcal C}$ to all variables in g . In this paper, for any set ${\cal T_*}$ of m linear graph patterns in ${\cal GP}({\mathcal C})$ , we present a query learning algorithm for finding a set S of linear graph patterns in ${\cal GP}({\mathcal C})$ with $\bigcup_{g\in{\cal T_*}}GLc{(g)}=\bigcup_{f\in S}GLc{(f)}$ in polynomial time using at most m  + 1 equivalence queries and O ( m ( n  +  n ^2)) restricted subset queries, where n is the maximum number of edges of counterexamples, if the number of labels of edges is infinite. Next we show that finite sets of graph languages generated by linear graph patterns having tree structures or two-terminal series parallel graph structures are not learnable in polynomial time using restricted equivalence, membership and subset queries.