Name
Title | ||
|---|---|---|
An efficiently computable subgraph pattern support measure: counting independent observations. |
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. |
Year | DOI | Venue |
|---|---|---|
2013 | https://doi.org/10.1007/s10618-013-0318-x | Data Min. Knowl. Discov. |
Keywords | DocType | Volume |
Graph mining,Frequency counting,Overlap graph,Linear program,Variance on sample estimates | Journal | 27 |
Issue | ISSN | Citations |
3 | 1384-5810 | 4 |
PageRank | References | Authors |
0.42 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuyi Wang | 1 | 11 | 3.69 |
| Jan Ramon | 2 | 955 | 66.16 |
| Thomas Fannes | 3 | 5 | 0.77 |