Understanding the search space of methods for automatically designing graph neural networks

Abstract

Dados estruturados em formato de grafos têm se tornado cada vez mais disponíveis, e devido à sua ubiquidade, têm se tornado objeto de estudo em várias áreas de pesquisa. Dada a ausência da noção de sequência entre elementos em um grafo, algoritmos de Aprendizado de Máquina (ML, em inglês) têm historicamente enfrentado dificuldades em trabalhar com este tipo de dados. Métodos especializados para grafos têm ganhado atenção da comunidade de pesquisa recentemente, especialmente as Redes Neurais para Grafos (GNNs, em inglês), que têm sido extensivamente utilizadas em dados reais, alcançando resultados estado-da-arte em tarefas como projeto de circuitos, recomendação de filmes e detecção de anomalias.

Uma gama de modelos de GNN foi proposta recentemente, e escolher o melhor modelo para cada tarefa tem se tornado uma tarefa complicada e propensa a erros. Objetivando mitigar este problema, trabalhos recentes têm investigado estratégias para aplicar Busca de Arquitetura Neurais (NAS, em inglês) - um conjunto de métodos projetados para automaticamente configurar redes neurais, que têm obtido muito sucesso em Redes Neurais Convolucionais (CNNs, em inglês), que lidam com imagens - para modelos de GNN. GNNs automaticamente configuradas têm alcançado bons resultados em performance, superando redes configuradas por humanos. Porém, a literatura de NAS para GNNs ainda está em seus estágios iniciais, e métodos que foram aplicados com sucesso para NAS em CNNs, ainda não foram testados para GNNs.

O foco deste trabalho é conduzir uma análise comparativa compreensiva de um Algoritmo Evolucionario proposto, contra um algoritmo de Aprendizado por Reforço da literatura, e uma Busca Aleatória como baseline, considerando 7 datasets reais, e dois espaços de busca. É demonstrado que a Busca Aleatória é tão efetiva quanto outros métodos mais complexos, em encontrar boas arquiteturas de GNN. Outro achado interessante é de que todos os três métodos convergem bem cedo na busca (utilizando aproximadamente 10% da cota). A hipótese é de que isto acontece devido à presença de Neutralidade no espaço (regiões do espaço em que todas as soluções tem valores de performance parecidas).

Em uma segunda etapa do trabalho, o foco é em conduzir uma avaliação visual e analítica extensa de um dos espaços de busca da literatura, usando técnicas de redução de dimensionalidade e Fitness Landscape Analysis (FLA). É demonstrado que o espaço de busca para NAS em GNNs apresenta grande "Buscabilidade" (i.e. não é difícil para algoritmos explorar o espaço e encontrar boas soluções) e "Neutralidade" (i.e. existem várias regiões do espaço em que a performance de soluções vizinhas é relativamente igual). A hipótese é de que, no futuro, métodos menos computacionalmente custosos possam ser empregados para esta tarefa sem perda de generalidade.