Resumen Técnico: Un Algoritmo Basado en Gradiente No Monótono para la Factorización de Matrices No Negativas Simétricas y el Agrupamiento de Grafos

1. Planteamiento del Problema

La Factorización de Matrices No Negativas Simétricas (Symmetric NMF) busca aproximar una matriz simétrica no negativa $V \in \mathbb{R}^{n \times n}$ como $V \approx WW^T$, donde $W \in \mathbb{R}^{n \times r}_+$ es un factor rectangular no negativo. Este problema es central para el agrupamiento de grafos (graph clustering) y el aprendizaje automático, ya que es equivalente al agrupamiento K-means y capaz de agrupar datos de grafos no lineales.

Si bien los métodos estándar de NMF (factorizando $V \approx WH$) cuentan con algoritmos bien establecidos, la Symmetric NMF presenta desafíos únicos. La función objetivo $f(W) = \frac{1}{2}\|V - WW^T\|^2$ es cuártica y no convexa. Históricamente, los métodos de gradiente proyectado (PG) para Symmetric NMF se han considerado inferiores a los enfoques de Mínimos Cuadrados No Negativos Alternos (ANLS) (por ejemplo, SymANLS) debido a su lenta convergencia y baja robustez. Los métodos PG existentes suelen tener dificultades con los problemas de escalabilidad y la curvatura específica del problema simétrico, lo que lleva a una dependencia de métodos de orden superior más costosos computacionalmente, como los enfoques basados en Newton o la pesada secuencia de resolución de mínimos cuadrados de ANLS.

2. Metodología

Los autores introducen SNMPBB (Symmetric Nonmonotone Projected Barzilai-Borveu), una novedosa adaptación de los métodos de gradiente proyectado no monótonos diseñada específicamente para Symmetric NMF. La metodología aborda las limitaciones de las extensiones ingenuas mediante tres mecanismos principales:

2.1. Acoplamiento Basado en Penalización

En lugar de establecer ingenuamente $H = W^T$ y reducir el problema a una sola variable (lo que restringe los grados de libertad), SNMPBB mantiene dos variables, $W$ y $H$, y las acopla mediante una penalización cuadrática. La función objetivo se define como:
$$f(W, H; \lambda) = \frac{1}{2}\|V - WH\|^2 + \frac{\lambda}{2}\|W - H^T\|^2$$
donde $\lambda \geq 0$ es un parámetro de penalización. Esta formulación permite el uso de actualizaciones de gradiente estándar de NMF mientras se impone la simetría a través de los términos de penalización derivados de la penalización.

2.2. Marco de Trabajo de Gradiente Proyectado No Monótono Barzilai-Borwein (NMPBB)

El algoritmo utiliza un esquema de proyección de dos etapas y tamaños de paso adaptativos:

1. Tamaño de Paso Adaptativo: Emplea el tamaño de paso Barzilai-Borwein (BB), adaptado para problemas de valores matriciales utilizando el producto interno de Frobenius. El tamaño de paso $\alpha_k$ se calcula como $\langle S_{k-1}, S_{k-1} \rangle / \langle S_{k-1}, Y_{k-1} \rangle$, donde $S$ y $Y$ representan los cambios en las iteraciones y los gradientes, respectivamente. Esto aproxima el comportamiento de tipo Newton con un costo de primer orden.
2. Proyección de Dos Etapas:
   • Primero, se computa un punto de prueba $Z_k$ utilizando un paso de gradiente proyectado estándar con un factor de escala automática $\rho_0$ relacionado con la constante de Lipschitz del gradiente.
   • Segundo, se forma una dirección de descenso $D_k$ proyectando desde $Z_k$ utilizando el tamaño de paso BB.
3. Búsqueda de Línea No Monótona: A diferencia de los métodos tradicionales que requieren un descenso monótono en cada iteración, SNMPBB utiliza una búsqueda de línea no monótona. Compara el nuevo valor de la función contra un valor de referencia $F_k$, que es un promedio ponderado de valores de función recientes. Esta relajación permite al algoritmo escapar de los mínimos locales y manejar paisajes no convexos de manera más efectiva. Se aplica un factor de relajación $\phi$ para amplificar el paso de descenso.

2.3. Extensiones

• Graph-SNMPBB: Para el agrupamiento de grafos, el método incorpora la regularización del Laplaciano del grafo para abordar los problemas de agrupamiento suave (soft-clustering) y mejorar la calidad de los grupos. El objetivo incluye un término $\frac{\gamma}{2}\text{tr}(HLH^T)$, donde $L$ es el Laplaciano del grafo.
• LAI-SNMPBB: Para manejar problemas a gran escala, el método integra la metodología de Entrada de Bajo Rango Aproximado (LAI). La matriz de entrada $V$ se aproxima mediante un sondeo aleatorio (randomized sketching) ($V \approx AB$). Crucialmente, los autores demuestran que el cálculo del tamaño de paso BB permanece invariante ante este error de aproximación porque el sesgo introducido por la aproximación se cancela en la diferencia de gradientes utilizada para el paso BB.

3. Análisis Teórico

El artículo proporciona garantías de convergencia rigurosas:

• Convergencia Global: Se demuestra que SNMPBB converge globalmente a puntos estacionarios de primer orden. La prueba se basa en la convexidad de la función objetivo con respecto a una variable (cuando la otra está fija) y la continuidad de Lipschitz del gradiente.
• Preservación de la Curvatura: Para la variante LAI, el análisis demuestra que la información de curvatura de Barzilai-Borwein se preserva a pesar de la aproximación de bajo rango de $V$. El sesgo del gradiente introducido por la aproximación es constante con respecto a las actualizaciones de las variables y, por lo tanto, no afecta el cálculo del tamaño de paso.
• Límites de Error: La brecha residual entre la solución LAI y la solución óptima está acotada por el doble del error de aproximación del sustituto de bajo rango.

4. Resultados Experimentales

Los autores evaluaron SNMPBB y sus variantes contra métodos de vanguardia (SymANLS, SymNewton, PGD y LAI-SymPGNCG) en conjuntos de datos sintéticos y del mundo real.

• Datos Sintéticos: En matrices sintéticas densas, SNMPBB logró una aceleración de 6x sobre SymANLS y una aceleración de 2x sobre SymNewton para valores residuales similares. La ventaja de rendimiento de SNMPBB creció significativamente a medida que el rango $r$ aumentaba, resaltando la escalabilidad de los métodos de primer orden en comparación con la complejidad $O(n^2r^2)$ o $O(n^3r^3)$ de los métodos de Mínimos Cuadrados Alternos y Newton.
• Pruebas de Referencia de Agrupamiento de Grafos: En seis conjuntos de datos del mundo real (incluyendo COIL20, Isolet, MNIST, ORL, Reuters y TDT2), Graph-SNMPBB igualó o superó la precisión de agrupamiento de SymANLS, mientras que convergió sustancialmente más rápido. Las ventajas fueron más pronunciadas en conjuntos de datos de texto de alta dimensión y dispersos (Reuters, TDT2) y conjuntos de datos de imágenes con estructuras visuales fuertes (MNIST, COIL20).
• Rendimiento de Gran Escala LAI: En 34 matrices de SuiteSparse, LAI-SNMPBB superó al estado del arte LAI-SymPGNCG tanto en tiempo de ejecución como en la calidad del residuo final.
  • Un hallazgo clave fue que limitar las iteraciones del descenso de gradiente interno a 3–5 pasos (parada temprana) evitó el sobreajuste al error de aproximación de bajo rango, actuando como un mecanismo de regularización implícito. Esto resultó en una mejor generalización y una convergencia más rápida en comparación con la ejecución de los bucles internos hasta la convergencia total.

5. Significado y Reivindicaciones

El artículo sostiene que los métodos de gradiente proyectado para Symmetric NMF han sido históricamente subestimados. Al integrar búsquedas de línea no monótonas, tamaños de paso Barzilai-Borwein y acoplamiento basado en penalización, los autores demuestran que los algoritmos de gradiente de primer orden pueden ser significativamente más efectivos de lo que se creía.

Las contribuciones primarias son:

1. SNMPBB: La primera adaptación de los métodos de Barzilai-Borwein proyectados no monótonos a Symmetric NMF, demostrando que los algoritmos de gradiente pueden superar a los establecidos enfoques de Mínimos Cuadrados Alternos y basados en Newton tanto en velocidad como en precisión.
2. Graph-SNMPBB: Una extensión que aplica con éxito la regularización del Laplaciano del grafo para mejorar el rendimiento del agrupamiento en pruebas de referencia del mundo real.
3. LAI-SNMPBB: Una variante escalable para problemas grandes que preserva la información de curvatura BB bajo la aproximación de bajo rango y utiliza la parada temprana como una estrategia de regularización.

El trabajo concluye que, con las adaptaciones adecuadas (escalado de curvatura, estrategias de globalización y regularización), los métodos de primer orden ofrecen un equilibrio efectivo entre eficiencia computacional, escalabilidad y calidad de la solución para la factorización de matrices simétricas y el agrupamiento de grafos.