Efeitos do coarsening na classificação de grafos k-partidos

Abstract

Com a quantidade de dados gerados no mundo ultrapassando a capacidade humana de avaliação, métodos de classificação automática de conteúdo se tornam cada vez mais relevantes. Grafos são uma forma de representação genérica de representação de entidades e suas interações, e podem ser aplicados praticamente em todo tipo de problema, principalmente em sua versão heterogênea. Por esse motivo é um dos temas que mais tem crescido no número de pesquisas na área de machine learning. Porém, essa mencionada quantidade de dados, resulta em grafos com elevado número de vértices e arestas, também gerando problemas nas questões de armazenamento e escalabilidade dos algoritmos aplicados a eles. Neste trabalho, é proposta a utilização de técnicas de coarsening, para reduzir o tamanho desses grafos como forma de endereçar estes problemas. Essa abordagem é bem estabelecida nas áreas de visualização e de particionamento de grafos, e já foi provada recentemente válida para problemas de classificação em grafos homogêneos. As questões investigadas neste trabalho dizem respeito aos níveis de economia de armazenamento e tempo de classificação proporcionados pelo coarsening, em comparação com os impactos causados pela redução dos grafos, em métricas de qualidade de classificação (Accuracy, Precision, Recall e F-score). O procedimento proposto foi avaliado em centenas de milhares de grafos, variando o número de vértices de entrada no intervalo de 15 a 100 mil vértices, com diferentes esquemas. Foram investigados os impactos também da quantidade de arestas intra-comunitárias e da esparsidade dos grafos nas citadas métricas. Quanto à economia de recursos, as reduções nos grafos apresentaram resultados expressivos, onde reduções de 20% no número de vértices chegam em economias de armazenamento de mais de 1/3, além de tornar as classificações cerca de duas vezes mais rápidas. Em contraste a isso, quanto à perda na qualidade das classificações, destaca-se como fato positivo a baixa perda apresentada para reduções em torno de 20%, com variações médias de 1.72±0.54%, 0.55 ± 0.17%, 1.78 ± 0.55%, 2.36 ± 0.77%, em relação ao grafo original, para as métricas de Accuracy, Precision, Recall e F-score, respectivamente. Com especial destaque para a perda da métrica de Precision, que, além de níveis médios baixos, apresentou uma relativa estabilidade com a variação dos tamanhos dos grafos, variando menos de 4% na comparação entre grafos de 2 mil e de 100 mil vértices. Esses resultados mostram que o coarsening tem grande potencial para gerar versões reduzidas dos grafos, reduzindo a quantidade de memória necessária para seu armazenamento e o tempo necessário para se classificá-los, sem, no entanto, resultar em perdas expressivas de qualidade.