Use of embedding concatenation and ensemble to improve node classification on graphs

Abstract

Artificial intelligence (AI) is a powerful tool that can be used in several different fields to solve many problems, and its use has been increasing every year. However, traditional machine learning (ML) algorithms have a specific limitation: their input format. Since they expect the input to be in vectors and matrices, data that is best represented by graphs can not be easily used to train ML models, even though they could often be the best alternative researchers have. This hurdle inspired the creation of a set of algorithms for a process called embedding, which maps graph data to a vector space, allowing the data to be fed to ML methods with ease. Embedding, however, does not yield a perfect representation since there is an inherent trade-off in the process. Embedding algorithms have to choose to preserve one out of two characteristics of a graph: community (the neighborhood of each node) or structure (the role each node has in the graph structure). Algorithms have to focus on one aspect over the other or attempt to balance them in the representation, resulting in shallower preservation of both. This means essential aspects of a graph can be lost in translation, which can yield bad results purely because of the type of representation chosen. It can also mean that the results could improve by making the graph representation more complete. Inspired by this observation, we propose a combination of two ideas aiming at improving the representation of graph data to be used in ML algorithms. The first is a simple concatenation of three types of embeddings, each using a different embedding strategy, and the second is the use of a bootstrap aggregation ensemble for the task. To evaluate these approaches, we run experiments on six datasets comparing the performance of the proposed approaches against simple classifiers trained on each embedding separately. Our results suggest that, while the concatenation does not have the best results, it constantly gets very close to it in all tested datasets, which does not happen with individual embeddings.

Inteligência artifical (IA) é uma ferramenta poderosa que pode ser usada em diferentes áreas para resolver vários tipos de problemas, e seu uso vem aumentando a cada ano. Porém, algoritmos tradicionais de aprendizado de máquina (AM) possuem uma limitação específica: o formato de entrada dos dados. Como eles esperam que a entrada esteja na forma de vetores e matrizes, dados que são melhor representados por um grafo não podem ser facilmente utilizados para treinar modelos de AM, mesmo quando podem ser a melhor alternativa para pesquisadores. Esse obstáculo inspirou a criação de um conjunto de algoritmos para um processo chamado embedding, que mapeia dados de um grafo em um espaço vetorial, permitindo que esses dados sejam passados para modelos de AM com facilidade. Embeddings, no entanto, não geram uma representação perfeita, já que existe uma relação inversa inerente ao processo. Os algoritmos precisam escolher preservar uma de duas características de um grafo: comunidade (a vizinhança de cada nodo) ou estrutura (o papel que cada nodo tem na estrutura do grafo). Eles precisam focar em um aspecto em detrimento do outro, ou precisam tentar balanceá-los na representação, resultando em uma preservação pior de ambos. Isso significa que aspectos importantes de um grafo podem se perder, o que pode gerar resultados ruins para uma tarefa de classificação ou de predição apens por causa do tipo de representação escolida. Isso também pode significar que os resultados podem melhorar caso a representação do grafo seja mais completa. Inspirados pelo conceito, propomos a combinação de duas ideias para tentar melhorar a representação de grafos para serem usados em algoritmos de aprendizado de máquinas. A primeira é uma concatenação simples de três tipos de embedding, cada um focando em uma característica específica, e a segunda é o uso de um ensemble boostrap aggregation para a tarefa. Para avaliar as abordagens, nós rodamos experimentos com seis conjuntos de dados copmarando a performance das abordagens propostas com a de clasificadores simples treinados em cada embedding separadamente. Nossos resultados mostram que, apesar de a concatenação não ter os melhores resultados, ela constamentemente fica perto dos melhores em todos os datasets testados, o que não ocorre com embeddings individuais.