Resumo Técnico: Um Algoritmo de Gradiente Não Monotônico para Fatoração de Matrizes Não Negativas Simétricas e Agrupamento de Grafos

1. Definição do Problema

A Fatoração de Matrizes Não Negativas Simétricas (Symmetric NMF) busca aproximar uma matriz simétrica não negativa $V \in \mathbb{R}^{n \times n}$ como $V \approx WW^T$, onde $W \in \mathbb{R}^{n \times r}_+$ é um fator retangular não negativo. Este problema é central para o agrupamento de grafos (graph clustering) e aprendizado de máquina, sendo equivalente ao agrupamento K-means e capaz de agrupar dados de grafos não lineares.

Embora a NMF padrão (fatorando $V \approx WH$) possua algoritmos bem estabelecidos, a Symmetric NMF apresenta desafios únicos. A função objetivo $f(W) = \frac{1}{2}\|V - WW^T\|^2$ é quártica e não convexa. Historicamente, os métodos de gradiente projetado (PG) para Symmetric NML foram considerados inferiores aos abordagens de Mínimos Quadrados Alternados Não Negativos (ANLS) (ex: SymANLS) devido à convergência lenta e baixa robustez. Os métodos PG existentes frequentemente enfrentam problemas de escalonamento e a curvatura específica do problema simétrico, levando a uma dependência de métodos de ordem superior mais custosos, como abordagens baseadas em Newton ou a sequência computacionalmente pesada de resoluções de mínimos quadrados do ANLS.

2. Metodologia

Os autores introduzem o SNMPBB (Symmetric Nonmonotone Projected Barzilai-Borwein), uma nova adaptação de métodos de gradiente projetado não monotônicos especificamente projetada para Symmetric NMF. A metodologia aborda as limitações das extensões ingênuas através de três mecanismos principais:

2.1. Acoplamento Baseado em Penalidade

Em vez de definir ingenuamente $H = W^T$ e reduzir o problema a uma única variável (o que restringe os graus de liberdade), o SNMPBB mantém duas variáveis, $W$ e $H$, e as acopla via uma penalidade quadrática. A função objetivo é definida como:
$$f(W, H; \lambda) = \frac{1}{2}\|V - WH\|^2 + \frac{\lambda}{2}\|W - H^T\|^2$$
onde $\lambda \geq 0$ é um parâmetro de penalidade. Esta formulação permite o uso de atualizações de gradiente padrão de NMF enquanto impõe a simetria através dos termos de penalidade derivados da penalidade.

2.2. Estrutura de Barzilai-Borwein Projetado Não Monotônico (NMPBB)

O algoritmo utiliza um esquema de projeção de dois estágios e tamanhos de passo adaptativos:

1. Tamanho de Passo Adaptativo: Emprega o tamanho de passo Barzilai-Borwein (BB), adaptado para problemas de valores matriciais usando o produto interno de Frobenius. O tamanho do passo $\alpha_k$ é computado como $\langle S_{k-1}, S_{k-1} \rangle / \langle S_{k-1}, Y_{k-1} \rangle$, onde $S$ e $Y$ representam as mudanças nos iterados e nos gradientes, respectivamente. Isso aproxima o comportamento de Newton com custo de primeira ordem.
2. Projeção de Dois Estágios:
   • Primeiro, um ponto de teste $Z_k$ é computado usando um passo de gradiente projetado padrão com um fator de escala automático $\rho_0$ relacionado à constante de Lipschitz do gradiente.
   • Segundo, uma direção de descida $D_k$ é formada projetando a partir de $Z_k$ usando o tamanho de passo BB.
3. Busca de Linha Não Monotônica: Ao contrário dos métodos tradicionais que exigem decréscimo monotônico em cada iteração, o SNMPBB utiliza uma busca de linha não monotônica. Ele compara o novo valor da função contra um valor de referência $F_k$, que é uma média ponderada de valores de função recentes. Esta relaxação permite que o algoritmo escape de mínimos locais e lide com superfícies não convexas de forma mais eficaz. Um fator de relaxação $\phi$ é aplicado para amplificar o passo de descida.

2.3. Extensões

• Graph-SNMPBB: Para agrupamento de grafos, o método incorpora regularização de Laplaciano de grafo para abordar problemas de agrupamento suave (soft-clustering) e melhorar a qualidade do agrupamento. A função objetivo inclui um termo $\frac{\gamma}{2}\text{tr}(HLH^T)$, onde $L$ é o Laplaciano do grafo.
• LAI-SNMPBB: Para lidar com problemas de larga escala, o método integra a metodologia de Entrada de Baixo Rank Aproximado (LAI). A matriz de entrada $V$ é aproximada via sketching aleatório ($V \approx AB$). Crucialmente, os autores provam que o cálculo do tamanho de passo BB permanece invariante a esse erro de aproximação porque o viés introduzido pela aproximação se cancela na diferença de gradiente usada para o passo BB.

3. Análise Teórica

O artigo fornece garantias rigorosas de convergência:

• Convergência Global: É provado que o SNMPBB converge globalmente para pontos estacionários de primeira ordem. A prova baseia-se na convexidade da função objetivo em relação a uma variável (quando a outra é fixa) e na continuidade de Lipschitz do gradiente.
• Preservação de Curvatura: Para a variante LAI, a análise demonstra que a informação de curvatura de Barzilai-Borwein é preservada apesar da aproximação de baixo rank de $V$. O viés do gradiente introduzido pela aproximação é constante em relação às atualizações das variáveis e, portanto, não afeta o cálculo do tamanho do passo.
• Limites de Erro: O gap residual entre a solução LAI e a solução ótima é limitado por duas vezes o erro de aproximação do substituto de baixo rank.

4. Resultados Experimentais

Os autores avaliaram o SNMPBB e suas variantes contra métodos de estado da arte (SymANLS, SymNewton, PGD e LAI-SymPGNCG) em conjuntos de dados sintéticos e do mundo real.

• Dados Sintéticos: Em matrizes sintéticas densas, o SNMPBB alcançou uma aceleração de 6x sobre o SymANLS e uma aceleração de 2x sobre o SymNewton para valores residuais similares. A vantagem de desempenho do SNMPBB cresceu significamente conforme o rank $r$ aumentava, destacando a escalabilidade dos métodos de primeira ordem em comparação com a complexidade $O(n^2r^2)$ ou $O(n^3r^3)$ dos métodos de Mínimos Quadrados Alternados e Newton.
• Benchmarks de Agrupamento de Grafos: Em seis conjuntos de dados do mundo real (incluindo COIL20, Isolet, MNIST, ORL, Reuters e TDT2), o Graph-SNMPBB igualou ou excedeu a precisão de agrupamento do SymANLS, enquanto convergiu substancialmente mais rápido. As vantagens foram mais pronunciadas em conjuntos de dados de texto esparsos e de alta dimensão (Reuters, TDT2) e conjuntos de dados de imagem com fortes estruturas visuais (MNIST, COIL20).
• Desempenho de Larga Escala LAI: Em 34 matrizes SuiteSparse, o LAI-SNMPBB superou o estado da arte LAI-SymPGNCG tanto em tempo de execução quanto na qualidade final do resíduo.
  • Um achado fundamental foi que limitar as iterações de gradiente descendente interno a 3–5 passos (parada antecipada/early stopping) evitou o overfitting ao erro de aproximação de baixo rank, atuando como um mecanismo de regularização implícito. Isso resultou em melhor generalização e convergência mais rápida em comparação com a execução de loops internos até a convergência total.

5. Significância e Alegações

O artigo afirma que os métodos de gradiente projetado para Symmetric NMF têm sido historicamente subestimados. Ao integrar buscas de linha não monotônicas, tamanhos de passo Barzilai-Borwein e acoplamento baseado em penalidade, os autores demonstram que algoritmos de gradiente de primeira ordem podem ser significativamente mais eficazes do que anteriormente compreendido.

As principais contribuições são:

1. SNMPBB: A primeira adaptação de métodos de Barzilai-Borwein projetados não monotônicos para Symmetric NMF, provando que algoritmos de gradiente podem superar abordagens estabelecidas de Mínimos Quadrados Alternados e baseadas em Newton tanto em velocidade quanto em precisão.
2. Graph-SNMPBB: Uma extensão que aplica com sucesso a regularização de Laplaciano de grafo para melhorar o desempenho de agrupamento em benchmarks do mundo real.
3. LAI-SNMPBB: Uma variante escalável para problemas grandes que preserva a informação de curvatura BB sob aproximação de baixo rank e utiliza a parada antecipada como uma estratégia de regularização.

O trabalho conclui que, com as adaptações apropriadas (escalonamento de curvatura, estratégias de globalização e regularização), os métodos de primeira ordem oferecem um equilíbrio eficaz entre eficiência computacional, escalabilidade e qualidade de solução para fatoração de matrizes simétricas e agrupamento de grafos.