Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Mining Frequent Patterns in Evolving Graphs
KTH, School of Electrical Engineering and Computer Science (EECS). (SCS)ORCID iD: 0000-0001-5872-7809
(English)Manuscript (preprint) (Other academic)
Abstract [en]

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 appli- cations 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 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 emprically demonstrate that the proposed algorithms generate high-quality results compared to baselines.

Keywords [en]
Fully Dynamic Algorithms, Sampling, Frequent Pattern Mining
National Category
Other Engineering and Technologies
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-223354OAI: oai:DiVA.org:kth-223354DiVA, id: diva2:1183526
Note

QC 20170412

Available from: 2018-02-17 Created: 2018-02-17 Last updated: 2018-04-12Bibliographically approved

Open Access in DiVA

KDD2018(765 kB)13 downloads
File information
File name FULLTEXT01.pdfFile size 765 kBChecksum SHA-512
50a90bd6d87cdcf40dd8282c2a91be87d336164e4cf79a57982d79e15026cc568b25607e9380bd0deb7c7af7cb730110871f9c71360eb5ee10203388cf4112a3
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nasir, M. Anis U.
By organisation
School of Electrical Engineering and Computer Science (EECS)
Other Engineering and Technologies

Search outside of DiVA

GoogleGoogle Scholar
Total: 13 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 133 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf