Dr. Tim Oates
University of Maryland Baltimore County
Title: Stochastic Graph Grammars: Representations and Algorithms
Many important domains are naturally described relationally, often using graphs in which nodes correspond to entities and edges to relations. Stochastic graph grammars compactly represent probability distributions over graphs and can be learned from data, such as a set of graphs corresponding to proteins that have the same function. This talk will start as a tutorial - introducing the two most common representations of graph grammars - and then give way to a discussion of some of our recent work on learning and reasoning with graph grammars. I will show that a stochastic graph grammar can be used to efficiently compute the probability mass functions of the number of nodes, the number of edges, and the degree of a node selected uniformly at random from a graph sampled from the distribution defined by the graph grammar. Both the expectation and variance of these quantities can be computed from the mass functions. Empirical results with standard synthetic grammars and a grammar from the domain of AIDS research demonstrate the accuracy of our methods. I will also present an overview of what is known about the learnability of both graph grammar parameters and productions, including our PEGG algorithm for maximum likelihood parameter estimation.
©2010, Department of Mathematical Sciences
Last Modified: February 26, 2009