Fast node embeddings: learning ego-centric representations
Carregando...
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Nivio Ziviani
Fabricio Murai Ferreira
Rodrigo Coelho Barros
Fabricio Murai Ferreira
Rodrigo Coelho Barros
Resumo
O aprendizado de representações é um dos fundamentos de Deep Learning e permitiu avanços importantes em várias tarefas de Aprendizado de Máquina, como Tradução utilizando Redes Neurais, Respostas Automáticas para Perguntas e Reconhecimento de Fala. Trabalhos recentes propuseram novos métodos para aprender representações de nós e arestas em grafos. Vários desses métodos são baseados no algoritmo SkipGram. Eles processam um grande número de nós para produzir o contexto em que essas representações são aprendidas, com esses nós processados estando localizados numa vizinhança com distancia k de um nó raiz. Neste trabalho, é proposto um novo método, efetivo e eciente, para gerar embeddings para nós em grafos, o qual utiliza um número restrito de permutações da vizinhança direta (k = 10) de um nó como contexto para gerar seus embeddings, resultando em representações egocêntricas. Este trabalho apresenta uma avaliação detalhada mostrando que o método proposto supera métodos do estado da arte em seis datasets diferentes relacionados com os problemas predição de arestas e classicação de nós, sendo uma a três ordens de magnitude mais rápido que os baselines. O novo algoritmo apresentado também é avaliado numa tarefa de desambiguação de nomes de autores, mostrando que embeddings de nós podem ser utilizados com sucesso nessa tarefa. Finalmente, uma avaliação em detalhes das representações aprendidas é feita sob a ótica da assortatividade apresentada por elas, sendo assortatividade a tendência de nós similares estarem conectados.
Abstract
Representation learning is one of the foundations of Deep Learning and allowed important improvements on several Machine Learning tasks, such as Neural Machine Translation, Question Answering and Speech Recognition. Recent works have proposed new methods for learning representations for nodes and edges in graphs. Several of these methods are based on the SkipGram algorithm, and they usually process a large number of multi-hop neighbors in order to produce the context from which node representations are learned. In this paper, we propose an effective and also efficient method for generating node embeddings in graphs that employs a restricted number of permutations over the immediate neighborhood of a node as context to generate its representation, thus ego-centric representations. We present a thorough evaluation showing that our method outperforms state-of-the-art methods in six different datasets related to the problems of link prediction and node classification, being one to three orders of magnitude faster than baselines when generating node embeddings for very large graphs. We also evaluate our algorithm in an author name disambiguation task, showing that node embedding algorithms can be applied successfully to this problem. Finally, we further present an in-depth analysis of our algorithm in terms of the assortativity of the learned representations.
Assunto
Teoria dos grafos, Computação, Aprendizado do computador
Palavras-chave
Node Embeddings, Graphs, Learning Representations, Machine Learning