Spectral Theory and Heuristics for Graph Clustering and Embedding

Abstract

A teoria espectral em grafos considera propriedades dos grafos através da análise do espectro de matrizes relacionais, como a matriz de modularidade. No contexto de detecção de comunidades, algoritmos espectrais têm alcançado resultados satisfatórios, apesar de terem alguns desafios a serem superados. Um deles é a exigência de informação prévia sobre o número de comunidades de um determinado grafo.

A detecção de comunidades e de embedding de vértices são problemas clássicos de grafos que tradicionalmente têm sido abordados como problemas independentes na literatura. Mais recentemente, abordagens de embedding de comunidades foram introduzidas para combinar estratégias de detecção de comunidades com embedding de vértices. Algoritmos espectrais, apesar de fornecerem embeddings de vértices através de decomposição espectral, ainda precisam ser explorados na literatura no contexto de embeddings de comunidades. Até onde sabemos, não existe um algoritmo espectral baseado na maximização da modularidade para definir embedding de comunidades. Além disso, também faltam trabalhos que explorem os atributos dos vértices como informações adicionais para produzirem embeddings de comunidades. Nesta Tese, são apresentados quatro métodos espectrais hibridizados com heurísticas para detectar comunidades e identificar embeddings de comunidades em redes.

Primeiro, são explorados os trade-offs entre os termos da medida de modularidade, abordando-a como um problema bi-objetivo. Para resolver este problema, desenvolvemos o MOSpecG como um algoritmo evolutivo e espectral que, além de encontrar comunidades, também possui uma interpretação geométrica, relevante para o problema de embeddings de comunidades. Em seguida, abordamos a detecção de comunidades em redes de voos por meio de uma melhoria em um algoritmo multinível da literatura para incluir uma fase de refinamento. Nesse algoritmo, também avaliamos uma estratégia espectral como um critério de parada adicional para sua fase de contração.

Finalmente, são propostos dois algoritmos espectrais, chamados SpecRp e SpecNMF, para fornecer embeddings de comunidades em redes. Ambos os algoritmos se beneficiam da interpretação geométrica de um algoritmo espectral de detecção de comunidades com overlapping apresentado nesta Tese, inspirados no MOSpecG. O SpecRp incorpora atributos de vértices e condições de proximidade de vértices no grafo de entrada, possibilitando que a detecção de comunidades forneça embeddings de comunidade, enquanto SpecNMF é baseado em uma estratégia iterativa da literatura. Destacamos que SpecRp superou o atual estado da arte na classificação de vértices.

Spectral theory in graphs regards graph properties through the spectrum analysis of relational matrices, such as the modularity matrix.In the context of community detection, spectral-based algorithms have achieved satisfactory results, despite having some challenges to overcome. One of them is the requirement of prior information on the number of communities of a given graph.

Community detection and node embedding are classical graph problems that had traditionally been approached as independent problems in the literature. More recently, community embedding approaches were introduced to combine community detection with node embedding. Spectral algorithms, despite providing vertex embeddings by the eigen-decomposition, have yet to be further explored in the literature in the context of community embeddings. To the best of our knowledge, there is no spectral algorithm based on modularity maximization to the community embedding problem. Moreover, there is also a lack of works exploring node attributes as additional inputs for producing community embeddings. In this Thesis, we introduce four spectral-based methods hybridized with heuristics to detect communities and find community embedding in networks.

We first explore the trade-offs between the terms of the well-known modularity measure by approaching it as a bi-objective problem. To address this problem, we introduced MOSpecG as a spectral-based evolutionary algorithm that, in addition to finding communities, also has a geometrical interpretation, relevant for the community embedding problem. We then approached the detection of communities in flight networks by enhancing a multilevel algorithm from the literature with a refinement phase and evaluated a spectral-based strategy as an additional stopping criterion for its coarsening phase.

Finally, we proposed two spectral-based algorithms, called SpecRp and SpecNMF, to provide community embeddings in networks. Both of these algorithms benefit from the geometrical interpretation of a spectral-based overlapping community detection algorithm we introduced in this Thesis, inspired in MOSpecG. SpecRp incorporates node attributes and vertex proximity conditions into the input graph, allowing the community detection to provide community embeddings, whereas SpecNMF is based on an interactive strategy from the literature. We highlight that SpecRp outperformed the current state-of-the-art on node classification.