Mining frequent patterns in evolving graphs

Cigdem Aslay, Muhammad Anis Uddin Nasir, Gianmarco De Francisci Morales, Aristides Gionis

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

12 Sitaatiot (Scopus)

Abstrakti

Given a labeled graph, the frequent-subgraph mining (FSM) problem asks to find all the k-vertex subgraphs that appear with frequency greater than a given threshold. FSM has numerous applications ranging from biology to network science, as it provides a compact summary of the characteristics of the graph. However, the task is challenging, even more so for evolving graphs due to the streaming nature of the input and the exponential time complexity of the problem. In this paper, we initiate the study of the approximate FSM problem in both incremental and fully-dynamic streaming settings, where arbitrary edges can be added or removed from the graph. For each streaming setting, we propose algorithms that can extract a high-quality approximation of the frequent k-vertex subgraphs for a given threshold, at any given time instance, with high probability. In contrast to the existing state-of-the-art solutions that require iterating over the entire set of subgraphs for any update, our algorithms operate by maintaining a uniform sample of k-vertex subgraphs with optimized neighborhood-exploration procedures local to the updates. We provide theoretical analysis of the proposed algorithms and empirically demonstrate that the proposed algorithms generate high-quality results compared to baselines.

AlkuperäiskieliEnglanti
OtsikkoCIKM 2018 - Proceedings of the 27th ACM International Conference on Information and Knowledge Management
ToimittajatNorman Paton, Selcuk Candan, Haixun Wang, James Allan, Rakesh Agrawal, Alexandros Labrinidis, Alfredo Cuzzocrea, Mohammed Zaki, Divesh Srivastava, Andrei Broder, Assaf Schuster
KustantajaACM
Sivut923-932
Sivumäärä10
ISBN (elektroninen)9781450360142
DOI - pysyväislinkit
TilaJulkaistu - 17 lokakuuta 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaACM International Conference on Information and Knowledge Management - Torino, Italia
Kesto: 22 lokakuuta 201826 lokakuuta 2018
Konferenssinumero: 27

Conference

ConferenceACM International Conference on Information and Knowledge Management
LyhennettäCIKM
Maa/AlueItalia
KaupunkiTorino
Ajanjakso22/10/201826/10/2018

Sormenjälki

Sukella tutkimusaiheisiin 'Mining frequent patterns in evolving graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä