Title: An efficiently computable subgraph pattern support measure: Counting independent observations
Authors: Wang, Yuyi ×
Ramon, Jan
Fannes, Thomas #
Issue Date: 9-May-2013
Publisher: Kluwer Academic Publishers
Series Title: Data Mining and Knowledge Discovery vol:27 issue:3 pages:444-477
Abstract: Graph support measures are functions measuring how frequently a given subgraph pattern occurs in a given database graph. An important class of support measures relies on overlap graphs. A major advantage of overlap-graph based approaches is that they combine anti-monotonicity with counting the occurrences of a subgraph pattern which are independent according to certain criteria. However, existing overlap-graph based support measures are expensive to compute. In this paper, 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. We study the anti-monotonicity and other properties of this new measure, and relate it to the statistical power of a sample of embeddings in a network. We show experimentally that, in contrast to earlier overlap-graph based proposals, our support measure makes it feasible to mine subgraph patterns in large networks.
ISSN: 1384-5810
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
dmkd.pdfOA article Published 514KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science