Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/ESBF-B5UMC8
Tipo: | Dissertação de Mestrado |
Título: | Fast node embeddings: learning ego-centric representations |
Autor(es): | Tiago Pimentel Martins da Silva |
Primeiro Orientador: | Adriano Alonso Veloso |
Primeiro Coorientador: | Nivio Ziviani |
Primeiro membro da banca : | Nivio Ziviani |
Segundo membro da banca: | Fabricio Murai Ferreira |
Terceiro membro da banca: | 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 |
Idioma: | Inglês |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/ESBF-B5UMC8 |
Data do documento: | 26-Fev-2018 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
tiagopimentelmartinsdasilva.pdf | 1.42 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.