BEGIN:VCALENDAR
VERSION:2.0
PRODID:ECMLPKDD-MB
BEGIN:VEVENT
DTSTAMP;TZID=Europe/Dublin:20180826T200000
UID:_ecmlpkdd_DAMI-D-16-00198
DTSTART;TZID="Europe/Dublin":20180913T110000
DTEND;TZID="Europe/Dublin":20180913T112000
LOCATION:Hogan
TRANSP:TRANSPARENT
SEQUENCE:1
DESCRIPTION:Counting the number of times a pattern occurs in a database is a fundamental data mining problem. It is a subroutine in a diverse set of tasks ranging from pattern mining to supervised learning and probabilistic model learning. While a pattern and a database can take many forms, this paper focuses on the case where both the pattern and the database are graphs (networks). Unfortunately, in general, the problem of counting graph occurrences is #P-complete. In contrast to earlier work, which focused on exact counting for simple (i.e., very short) patterns, we present a sampling approach for estimating the statistics of larger graph pattern occurrences. We perform an empirical evaluation on synthetic and real-world data that validates the proposed algorithm, illustrates its practical behavior and provides insight into the trade-off between its accuracy of estimation and computational efficiency.
SUMMARY:Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model
CLASS:PUBLIC
END:VEVENT
END:VCALENDAR