Beyond frequencies: Graph Pattern mining in multi-weighted graphs

Giulia Preti, Davide Mottin, Matteo Lissandrini, Yannis Velegrakis

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

7 Citationer (Scopus)

Abstract

Graph pattern mining aims at identifying structures that appear frequently in large graphs, under the assumption that frequency signies importance. Several measures of frequency have been proposed that respect the apriori property, essential for an e-cient search of the patterns. This property states that the number of appearances of a pattern in a graph cannot be larger than the frequency of any of its sub-patterns. In real life, there are many graphs with weights on nodes and/or edges. For these graphs, it is fair that the importance (score) of a pattern is determined not only by the number of its appearances, but also by the weights on the nodes/edges of those appearances. Scoring functions based on the weights do not generally satisfy the apriori property, thus forcing many approaches to employ other, less ecient, pruning strategies to speed up the computation. The problem becomes even more challenging in the case of multiple weighting functions that assign dierent weights to the same nodes/edges. In this work, we provide ecient and eective techniques for mining patterns in multi-weight graphs. We devise both an exact and an approximate solution. The rst is characterized by intelligent storage and computation of the pattern scores, while the second is based on the aggregation of similar weighting functions to allow scalability and avoid redundant computations. Both methods adopt a scoring function that respects the apriori property, and thus they can rely on eective pruning strategies. Extensive experiments under dierent parameter settings prove that the presence of edge weights and the choice of scoring function aect the patterns mined, and hence the quality of the results returned to the user. Finally, experiments on datasets of dierent sizes and increasing numbers of weighting functions show that, even when the performance of the exact algorithm degrades, the approximate algorithm performs well and with quite good quality.

OriginalsprogEngelsk
TitelAdvances in Database Technology - EDBT 2018 : 21st International Conference on Extending Database Technology, Proceedings
RedaktørerMichael Bohlen, Reinhard Pichler, Norman May, Erhard Rahm, Shan-Hung Wu, Katja Hose
Antal sider12
ForlagOpenProceedings.org
Publikationsdato1 jan. 2018
Sider169-180
ISBN (Elektronisk)9783893180783
DOI
StatusUdgivet - 1 jan. 2018
Udgivet eksterntJa
Begivenhed21st International Conference on Extending Database Technology, EDBT 2018 - Vienna, Østrig
Varighed: 26 mar. 201829 mar. 2018

Konference

Konference21st International Conference on Extending Database Technology, EDBT 2018
Land/OmrådeØstrig
ByVienna
Periode26/03/201829/03/2018
NavnAdvances in Database Technology - EDBT
Vol/bind2018-March

Fingeraftryk

Dyk ned i forskningsemnerne om 'Beyond frequencies: Graph Pattern mining in multi-weighted graphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater