Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model - Archive ouverte HAL Access content directly
Journal Articles Data Mining and Knowledge Discovery Year : 2018

Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model

(1) , (2) , (3) , (1)
1
2
3

Abstract

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.
Fichier principal
Vignette du fichier
ravkic-dami18.pdf (1.84 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01725971 , version 1 (07-03-2018)

Identifiers

Cite

Irma Ravkic, Martiň Znidaršič, Jan Ramon, Jesse Davis. Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model. Data Mining and Knowledge Discovery, 2018, pp.36. ⟨10.1007/s10618-018-0553-2⟩. ⟨hal-01725971⟩
182 View
236 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More