Incremental Frequent Subgraph Mining on Large Evolving Graphs

Ehab Abdelhamid, Mustafa Canim, Mohammad Sadoghi, Bishwaranjan Bhattacharjee, Yuan-Chi Chang, Panos Kalnis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


Frequent subgraph mining is a core graph operation used in many domains. Most existing techniques target static graphs. However, modern applications utilize large evolving graphs. Mining these graphs using existing techniques is infeasible because of the high computational cost. We propose IncGM+, a fast incremental approach for frequent subgraph mining on large evolving graphs. We adapt the notion of 'fringe' to the graph context, that is, the set of subgraphs on the border between frequent and infrequent subgraphs. IncGM+ maintains fringe subgraphs and exploits them to prune the search space. To boost efficiency, IncGM+ stores a number of selected embeddings to avoid redundant expensive subgraph isomorphism operations. Moreover, the proposed system supports batch updates. Our results confirm that IncGM+ outperforms existing methods, scales to larger graphs and consumes less memory.
Original languageEnglish (US)
Title of host publication2018 IEEE 34th International Conference on Data Engineering (ICDE)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages2
ISBN (Print)9781538655207
StatePublished - Oct 25 2018

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'Incremental Frequent Subgraph Mining on Large Evolving Graphs'. Together they form a unique fingerprint.

Cite this