License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.127
URN: urn:nbn:de:0030-drops-49819
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4981/
Go to the corresponding LIPIcs Volume Portal

Cohen, Sara ; Weiss, Yaacov Y.

Learning Tree Patterns from Example Graphs

pdf-format:
8.pdf (0.4 MB)

Abstract

This paper investigates the problem of learning tree patterns that return nodes with a given set of labels, from example graphs provided by the user. Example graphs are annotated by the user as being either positive or negative. The goal is then to determine whether there exists a tree pattern returning tuples of nodes with the given labels in each of the positive examples, but in none of the negative examples, and, furthermore, to find one such pattern if it exists. These are called the satisfiability and learning problems, respectively.

This paper thoroughly investigates the satisfiability and learning problems in a variety of settings. In particular, we consider example sets that (1) may contain only positive examples, or both positive and negative examples, (2) may contain directed or undirected graphs, and (3) may have multiple occurrences of labels or be uniquely labeled (to some degree). In addition, we consider tree patterns of different types that can allow, or prohibit, wildcard labeled nodes and descendant edges. We also consider two different semantics for mapping tree patterns to graphs. The complexity of satisfiability is determined for the different combinations of settings. For cases in which satisfiability is polynomial, it is also shown that learning is polynomial (This is non-trivial as satisfying patterns may be exponential in size). Finally, the minimal learning problem, i.e., that of finding a minimal-sized satisfying pattern, is studied for cases in which satisfiability is polynomial.

BibTeX - Entry

@InProceedings{cohen_et_al:LIPIcs:2015:4981,
  author =	{Sara Cohen and Yaacov Y. Weiss},
  title =	{{Learning Tree Patterns from Example Graphs}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{127--143},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Marcelo Arenas and Mart{\'i}n Ugarte},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4981},
  URN =		{urn:nbn:de:0030-drops-49819},
  doi =		{10.4230/LIPIcs.ICDT.2015.127},
  annote =	{Keywords: tree patterns, learning, examples}
}

Keywords: tree patterns, learning, examples
Collection: 18th International Conference on Database Theory (ICDT 2015)
Issue Date: 2015
Date of publication: 19.03.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI