Cortes de Grafo Ponderados sem Eigenvetores: Uma Abordagem Multinível

Uma variedade de algoritmos de agrupamento foi recentemente proposta para lidar com dados que não são linearmente separáveis; agrupamento espectral e k-means com kernel são dois dos principais métodos. Neste artigo, discutimos uma equivalência entre as funções objetivas usadas nesses métodos aparentemente diferentes - em particular, um objetivo geral de k-means com kernel ponderado é matematicamente equivalente a um objetivo de agrupamento de grafo ponderado. Nós exploramos essa equivalência para desenvolver um algoritmo multinível rápido e de alta qualidade que otimiza diretamente vários objetivos de agrupamento de grafo ponderado, como o popular corte de razão, corte normalizado e critérios de associação de razão. Isso elimina a necessidade de qualquer computação de eigenvetores para problemas de agrupamento de grafo, o que pode ser proibitivo para grafos muito grandes. Métodos anteriores de particionamento de grafo multinível, como o Metis, sofreram com a restrição de clusters de tamanhos iguais; nosso algoritmo multinível remove essa restrição utilizando k-means com kernel para otimizar cortes de grafo ponderados. Resultados experimentais mostram que nosso algoritmo multinível supera um algoritmo de agrupamento espectral de ponta em termos de velocidade, uso de memória e qualidade. Demonstramos que nosso algoritmo é aplicável a tarefas de agrupamento em grande escala, como segmentação de imagem, análise de rede social e análise de rede gênica.