Monday, March 18, 2013 at 16h30 in Celestijnenlaan 200A (auditorium 00.225)**Pattern mining and learning from network data**

by Yuyi Wang (PhD student DTAI)

For pattern mining from network data, support measures are functions measuring how frequently a given pattern occurs in a given network. An important class of support measures relies on overlap graphs. These support measures have statistical advantages. However, existing overlap-graph based support measures are expensive to compute. We propose a new support measure which is based on a new notion of independence. We show that our measure is the solution to a sparse linear program, which can be computed efficiently using interior point methods. An important motivation for the s-measure comes from its usefulness in a learning theory result we discuss in the second part of this presentation. When learning from network data, the assumption that training examples are drawn independently does not hold anymore. A straightforward method to solve this problem is that we first find a maximal independent set from the networked examples, then perform learning algorithms on these independent examples. Though many existing theoretical results can be directly used to analyze this method, it is inherently expensive to find a large independent set. We propose a weighting method based on the support measure mentioned above for learning using the networked examples, and establish some Bernstein-type inequalities for theoretical analysis.