Clustering Node Attributed Networks with Graph Neural Networks and Self Learning

Resumo Técnico: Agrupamento de Redes de Nós Atribuídos com Redes Neurais de Grafos e Aprendizado Próprio

Formulação do Problema
O artigo aborda o problema de agrupamento (clustering) de nós em redes atribuídas, onde cada nó possui tanto conexões topológicas (arestas) quanto atributos de características. O objetivo é particionar o conjunto de nós em subconjuntos disjuntos (comunidades) que reflitam estruturas latentes, aproveitando conjuntamente a topologia da rede e os atributos dos nós. Crucialmente, o trabalho opera em um cenário totalmente não supervisionado, o que significa que não há rótulos de agrupamento de verdade (ground-truth) disponíveis durante o treinamento; os únicos dados de entrada são a estrutura do grafo, os atributos dos nós e o número alvo de clusters ($K$). Os autores observam que, embora o agrupamento conjunto seja intuitivamente superior ao uso apenas da topologia ou apenas dos atributos, projetar algoritmos que fundam efetivamente esses sinais — especialmente quando uma das fontes é ruidosa — não é uma tarefa trivial.

Metodologia: DCSL-GNN
Os autores propõem a Rede Neural de Grafos de Aprendizado Próprio de Contexto Dinâmico (DCSL-GNN), um framework que opera em rodadas iterativas para refinar as representações dos nós e as atribuições de clusters. O framework consiste em três módulos interconectados:

1. Geração de Contexto Dinâmico:

   • As Redes Neurais de Grafos (GNNs) padrão frequentemente sofrem de "sub-alcance" (under-reaching — profundidade insuficiente para capturar centros de cluster distantes) ou "super-suavização" (over-smoothing — perda de distintividade com muitas camadas). Para mitigar isso, a DCSL-GNN constrói um Grafo de Contexto ($G_c$) para cada rodada, que difere do grafo original.
   • Arestas Virtuais: O grafo de contexto introduz "arestas virtuais" que conectam nós aos vizinhos mais próximos do centro de massa de seu respectivo cluster (no espaço de representação). Isso permite que a informação dos centros de cluster se propague diretamente, contornando a necessidade de camadas profundas de GNN.
   • Caminhadas Aleatórias (Random Walks): O grafo de contexto é gerado via caminhadas aleatórias enviesadas. Em cada etapa, a caminhada segue uma aresta original (ponderada pela similaridade das representações dos nós da rodada anterior) ou salta via uma aresta virtual para um nó próximo a um centro de cluster.
   • Vizinhanças Baseadas em Importância: A vizinhança de um nó em $G_c$ é determinada pelas contagens de visitas de caminhadas aleatórias iniciadas a partir desse nó, utilizando um limiar baseado no percentil $k$ da distribuição de visitas. Isso garante que os nós mais influentes (mesmo que distantes no grafo original) tornem-se vizinhos diretos no grafo de contexto.

2. Embedding (Codificador GNN):

   • Um codificador GCN padrão processa o grafo de contexto $G_c$ e os atributos dos nós para gerar embeddings de nós.
   • Pesos de Arestas: As arestas em $G_c$ são ponderadas dinamicamente. Se os atributos dos nós conectados forem altamente similares (verificado por um limiar de coeficiente de silhueta $\beta$), o peso da aresta é inversamente proporcional à distância euclidiana entre seus atributos. Caso contrário, o peso permanece neutro (1).
   • Treinamento: Os parâmetros da GNN são treinados usando uma função de perda de triplet (triplet loss). Esta perda minimiza a distância entre um nó âncora e amostras positivas (nós no mesmo cluster) enquanto maximiza a distância para amostras negativas (nós em clusters diferentes).
   • Persistência de Parâmetros: Diferente do treinamento padrão, os pesos da GNN aprendidos na rodada $r$ são inicializados com os valores da rodada $r-1$, permitindo que o modelo refine seu entendimento ao longo do tempo sem precisar de um novo treinamento do zero.

3. Loop de Agrupamento e Aprendizado Próprio:

   • Os embeddings gerados são alimentados em um algoritmo K-means padrão para produzir as atribuições de clusters.
   • Essas novas atribuições de clusters são então usadas para atualizar os centros de cluster e os vieses de caminhada aleatória para a próxima rodada.
   • Isso cria um mecanismo de auto-reforço: melhores representações levam a melhores clusters, que por sua vez geram melhores grafos de contexto e representações para a rodada subsequente.

Principais Contribuições

• Framework Inovador: A introdução da DCSL-GNN, um framework totalmente não supervisionado que refina iterativamente as representações dos nós através de um loop de aprendizado próprio.
• Grafo de Contexto Dinâmico: Um mecanismo para construir um grafo de contexto que combina a topologia original com arestas virtuais para os centros de cluster, abordando efetivamente as limitações de profundidade das GNNs sem exigir camadas excessivas.
• Mecanismo de Aprendizado Próprio: Um processo iterativo onde os resultados de agrupamento de uma rodada influenciam diretamente a estrutura do grafo (contexto) e os pesos das arestas da próxima rodada, permitindo que o modelo desrua progressivamente e alinhe a topologia com os atributos.
• Robustez ao Ruído: A metodologia é projetada para aproveitar a fonte de informação mais confiável (seja a topologia ou os atributos) para corrigir a fonte mais ruidosa.

Resultados Experimentais
Os autores avaliaram a DCSL-GNN em dados sintéticos (Modelos de Bloco Estocástico Atribuídos) e em três conjuntos de dados de referência do mundo real (Cora, Citeseer, PubMed).

• Dados Sintéticos:

  • Eficácia do Aprendizado Próprio: Múltiplas rodadas de aprendizado próprio superaram consistentemente uma única rodada longa de treinamento (equivalente ao agrupamento clássico de GNN).
  • Tratamento de Ruído: O framework extraiu com sucesso informações da fonte confiável quando a outra era ruidosa. Por exemplo, quando a informação de rede era muito ruidosa ($p_I=0.2$) mas os atributos eram limpos, o desempenho melhorou ao longo das rodadas. Inversamente, quando os atributos eram ruidosos mas a rede era limpa, o modelo também convergiu bem. No entanto, quando ambas as fontes eram altamente ruidosas, o desempenho degradou para um chute aleatório, como esperado.
  • Comparação: A DCSL-GNN superou algoritmos que dependem apenas da estrutura de rede (Louvain) ou apenas dos atributos (K-means) em cenários onde nenhuma das fontes era perfeitamente informativa.

• Datasets Reais:

  • Citeseer: A DCSL-GNN alcançou a maior Informação Mútua Normalizada (NMI) entre todos os métodos de estado da arte comparados.
  • Cora e PubMed: O modelo apresentou um desempenho competitivo, mas não superou o estado da arte (MGCCN para Cora, SEComm para PubMed).
  • Limitação: Os autores atribuem o menor desempenho em Cora e PubMed parcialmente ao desequilíbrio de clusters. O modelo mostrou alta precisão para clusters dominantes, mas precisão desprezível para clusters menores, sugerindo um viés para grupos maiores na função objetivo.

Significância e Alegações
O artigo afirma que a DCSL-GNN oferece uma abordagem flexível para o agrupamento de grafos atribuídos que funde efetivamente a informação estrutural e de atributos sem supervisão. Os autores enfatizam que o aprendizado próprio de múltiplas rodadas é um componente crítico, pois permite que o modelo refine iterativamente o "contexto" no qual os nós são visualizados, levando a um agrupamento superior em comparação com abordagens de rodada única.

Os autores concluem modestamente que, embora o método seja altamente eficaz em cenários com clusters equilibrados ou níveis mistos de ruído (como demonstrado no Citeseer e nos dados sintéticos), ele enfrenta desafios com conjuntos de dados reais altamente desequilibrados. Eles afirmam que o framework demonstra o potencial de mecanismos de aprendizado próprio para melhorar as representações dos nós e a qualidade do agrupamento na ausência de dados rotulados, embora não alegue ser uma solução universal superior a todos os métodos existentes em todas as características de dataset.