Graph pattern mining: consolidating models, systems, and abstractions
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Srinivasan Parthasarathy
Arlei Lopes da Silva
Ítalo Fernando Scotá Cunha
Vinícius Fernandes dos Santos
Wagner Meira Júnior
Arlei Lopes da Silva
Ítalo Fernando Scotá Cunha
Vinícius Fernandes dos Santos
Wagner Meira Júnior
Resumo
Mineração de padrões em grafos (MPG) se refere a uma classe de problemas envolvendo
o processamento de subgrafos extraídos de um único grafo maior. Aplicações para algoritmos de MPG incluem consultas por subgrafos com certas propriedades de interesse,
identificação de estruturas em redes biológicas, caracterização de redes sociais, entre outras. Desenvolver algoritmos de MPG é desafiador principalmente pela inerente presença
de sub-rotinas não-triviais lidando com conceitos complexos em teoria de grafos, como
identificação de isomorfismos. Neste contexto, sistemas de propósito geral para MPG
surgem como uma alternativa para melhorar a experiência de usuários com esses algoritmos. Entretanto, sistemas de propósito geral para MPG falham em prover um modelo
que seja de fácil entendimento e, ao mesmo tempo, qualificado para exprimir algoritmos
alternativos para um mesmo problema usando diferentes paradigmas de enumeração de
subgrafos, limitando a integração com fluxos de análise de dados atuais. Além disso,
como sistemas de MPG são tão heterogêneos no que se refere aos paradigmas suportados
e ambientes de execução, análises experimentais existentes são incapazes de diferenciar se
as diferenças encontradas no desempenho dos sistemas são melhor explicadas pelos algoritmos utilizados ou pelos detalhes de implementação. Nesta tese, propomos um modelo
para MPG baseado em primitivas, uma implementação distribuída escalável como prova
de conceito para o modelo e uma avaliação experimental extensiva dos paradigmas mais
usados por sistemas de MPG. Nós demonstramos empiricamente a efetividade de nossas
soluções ao observar um desempenho competitivo em relação às propostas existentes sem
sacrificar a expressividade dos algoritmos ou a capacidade de composição dos operadores.
Nossos resultados mostram ainda que nenhum paradigma é melhor em todo cenário de
aplicação e acreditamos que essa e outras de nossas descobertas podem guiar interessados
em direção a sistemas de MPG mais otimizados no futuro.
Abstract
Graph Pattern Mining (GPM) refers to a class of problems involving the processing of
subgraphs extracted from larger graphs. Applications to GPM algorithms include querying subgraphs with given properties of interest, identifying motif structures in biological
networks, characterizing social media, among others. GPM algorithms are challenging
to develop due to inherently subroutines that include non-trivial graph theory concepts
and methods such as isomorphism. General-purpose GPM systems emerge as a solution
to improve the user experience with such algorithms. However, general-purpose GPM
systems fail in providing a consistent model that is simple to understand and qualified to
express alternative algorithms for the same problem via different paradigms for subgraph
enumeration, limiting the integration with modern data analytics pipelines. Furthermore,
because GPM systems are so heterogeneous in terms of supported paradigms and computing architecture, existing experimental evaluations are unable to distinguish whether
performance differences are best explained by algorithmic strategies or implementation
details. In this work we propose a primitive-based model for GPM, a proof of concept
distributed implementation of that model, and an extensive experimentation analysis of
popular algorithmic paradigms used in GPM systems. We demonstrate empirically the
effectiveness of our model by showing competitive performance against state-of-the-art
systems without sacrificing the expressiveness of algorithms or the composability of operators. Our experimental results also show that no single paradigm is best for every application scenario, and we believe that our findings may guide practitioner towards
more optimized GPM systems in the future.
Assunto
Computação – Teses, Mineração de padrões em grafos – Teses, Sistemas distribuídos – Teses
Palavras-chave
Mineração de padrões em grafos, Sistemas distribuídos