HOPS: probabilistic subtree mining for small and large graphs

Pascal Welke, Florian Seiffarth, Michael Kamp, Stefan Wrobel

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Frequent subgraph mining, i.e., the identification of relevant patterns in graph databases, is a well-known data mining problem with high practical relevance, since next to summarizing the data, the resulting patterns can also be used to define powerful domain-specific similarity functions for prediction. In recent years, significant progress has been made towards subgraph mining algorithms that scale to complex graphs by focusing on tree patterns and probabilistically allowing a small amount of incompleteness in the result. Nonetheless, the complexity of the pattern matching component used for deciding subtree isomorphism on arbitrary graphs has significantly limited the scalability of existing approaches. In this paper, we adapt sampling techniques from mathematical combinatorics to the problem of probabilistic subtree mining in arbitrary databases of many small to medium-size graphs or a single large graph. By restricting on tree patterns, we provide an algorithm that approximately counts or decides subtree isomorphism for arbitrary transaction graphs in sub-linear time with one-sided error. Our empirical evaluation on a range of benchmark graph datasets shows that the novel algorithm substantially outperforms state-of-the-art approaches both in the task of approximate counting of embeddings in single large graphs and in probabilistic frequent subtree mining in large databases of small to medium sized graphs.

Original languageEnglish
Title of host publicationProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
EditorsJiliang Tang, B. Aditya Prakash
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages1275-1284
Number of pages10
ISBN (Electronic)9781450379984
DOIs
Publication statusPublished - 2020
EventACM International Conference on Knowledge Discovery and Data Mining 2020 - Virtual, Online, United States of America
Duration: 23 Aug 202027 Aug 2020
Conference number: 26th
https://dl.acm.org/doi/proceedings/10.1145/3394486 (Proceedings)
https://www.kdd.org/kdd2020/ (Website)

Conference

ConferenceACM International Conference on Knowledge Discovery and Data Mining 2020
Abbreviated titleKDD 2020
Country/TerritoryUnited States of America
CityVirtual, Online
Period23/08/2027/08/20
Internet address

Cite this