Fast and scalable algorithms for mining subgraphs in a single large graph

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F20%3A10245623" target="_blank" >RIV/61989100:27240/20:10245623 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/61989100:27740/20:10245623

Výsledek na webu

<a href="https://www.sciencedirect.com/science/article/pii/S0952197620300397" target="_blank" >https://www.sciencedirect.com/science/article/pii/S0952197620300397</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.engappai.2020.103539" target="_blank" >10.1016/j.engappai.2020.103539</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Fast and scalable algorithms for mining subgraphs in a single large graph

Popis výsledku v původním jazyce

Mining frequent subgraphs is an important issue in graph mining. It is defined as finding all subgraphs whose occurrences in the dataset are greater than or equal to a given frequency threshold. In recent applications, such as social networks, the underlying graphs are very large. Algorithms for mining frequent subgraphs from a single large graph have been developing rapidly lately. Among all such algorithms, GraMi is considered the state-of-the-art. However, GraMi still consumes a lot of time and memory in the mining of a large graph. In this paper, we propose two effective strategies to optimize the GraMi algorithm, which help to increase performance as well as reduce memory consumption during execution. Firstly, GraMi only lists all frequent subgraphs, without computing the support of each mined subgraph. This is disadvantageous in decision support systems, which require information about the support of all subgraphs. Therefore, we optimize GraMi to compute the support values during the mining process. Secondly, we apply the strategy of sorting all edges in graphs by their frequencies, which means that edges with low frequencies will be mined first, and vice versa. This sorting strategy can reduce the number of possibly infrequent subgraph candidates, especially on large subgraphs that are usually derived from those edges with high frequency. Thirdly, we apply a parallel processing technique, in which each frequent edge is executed simultaneously in a separate thread, and improve our parallel strategy by combination with the sorting strategy. Our experiments were performed on three real datasets and the results showed that the performance, as well as memory requirements, are better than those of the original GraMi algorithm.

Název v anglickém jazyce

Fast and scalable algorithms for mining subgraphs in a single large graph

Popis výsledku anglicky

Mining frequent subgraphs is an important issue in graph mining. It is defined as finding all subgraphs whose occurrences in the dataset are greater than or equal to a given frequency threshold. In recent applications, such as social networks, the underlying graphs are very large. Algorithms for mining frequent subgraphs from a single large graph have been developing rapidly lately. Among all such algorithms, GraMi is considered the state-of-the-art. However, GraMi still consumes a lot of time and memory in the mining of a large graph. In this paper, we propose two effective strategies to optimize the GraMi algorithm, which help to increase performance as well as reduce memory consumption during execution. Firstly, GraMi only lists all frequent subgraphs, without computing the support of each mined subgraph. This is disadvantageous in decision support systems, which require information about the support of all subgraphs. Therefore, we optimize GraMi to compute the support values during the mining process. Secondly, we apply the strategy of sorting all edges in graphs by their frequencies, which means that edges with low frequencies will be mined first, and vice versa. This sorting strategy can reduce the number of possibly infrequent subgraph candidates, especially on large subgraphs that are usually derived from those edges with high frequency. Thirdly, we apply a parallel processing technique, in which each frequent edge is executed simultaneously in a separate thread, and improve our parallel strategy by combination with the sorting strategy. Our experiments were performed on three real datasets and the results showed that the performance, as well as memory requirements, are better than those of the original GraMi algorithm.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE

ISSN

0952-1976

e-ISSN

—

Svazek periodika

90

Číslo periodika v rámci svazku

90

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

12

Strana od-do

—

Kód UT WoS článku

000528194400032

EID výsledku v databázi Scopus

—