Résumé Technique : Un Algorithme de Gradient Non Monotone pour la Factorisation de Matrices Symétriques Non Négatives et le Clustering de Graphes

1. Énoncé du Problème

La Factorisation de Matrices Symétriques Non Négatives (Symmetric NMF) cherche à approximer une matrice symétrique non négative $V \in \mathbb{R}^{n \times n}$ sous la forme $V \approx WW^T$, où $W \in \mathbb{R}^{n \times r}_+$ est un facteur rectangulaire non négatif. Ce problème est central pour le clustering de graphes et l'apprentissage automatique, car il est équivalent au clustering K-means et capable de traiter le clustering de données de graphes non linéaires.

Bien que la NMF standard (factorisant $V \approx WH$) dispose d'algorithmes bien établis, la Symmetric NMF présente des défis uniques. La fonction objectif $f(W) = \frac{1}{2}\|V - WW^T\|^2$ est quartique et non convexe. Historiquement, les méthodes de gradient projeté (PG) pour la Symmetric NMF ont été considérées comme inférieures aux approches par Moindres Carrés Non Négatifs Alternés (ANLS) (par exemple, SymANLS) en raison d'une convergence lente et d'une faible robustesse. Les méthodes PG existantes peinent souvent face aux problèmes d'échelle et à la courbure spécifique du problème symétrique, ce qui conduit à dépendre de méthodes d'ordre supérieur plus coûteuses comme les approches basées sur Newton ou la séquence de résolutions de moindres carrés de l'ANLS, très lourde en calculs.

2. Méthodologie

Les auteurs introduisent SNMPBB (Symmetric Nonmonotone Projected Barzilai-Borove), une nouvelle adaptation des méthodes de gradient projeté non monotones spécifiquement conçue pour la Symmetric NMF. La méthodologie répond aux limites des extensions symétriques naïves par trois mécanismes de base :

2.1. Couplage par Pénalité

Au lieu de définir naïvement $H = W^T$ et de réduire le problème à une seule variable (ce qui restreint les degrés de liberté), SNMPBB maintient deux variables, $W$ et $H$, et les couple via une pénalité quadratique. La fonction objectif est définie comme :
$$f(W, H; \lambda) = \frac{1}{2}\|V - WH\|^2 + \frac{\lambda}{2}\|W - H^T\|^2$$
où $\lambda \geq 0$ est un paramètre de pénalité. Cette formulation permet l'utilisation des mises à jour de gradient standards de la NMF tout en imposant la symétrie via les termes de pénalité dérivés de la pénalité.

2.2. Cadre Nonmonotone Projected Barzilai-Borwein (NMPBB)

L'algorithme utilise un schéma de projection en deux étapes et des tailles de pas adaptatives :

1. Taille de Pas Adaptative : Il emploie la taille de pas Barzilai-Borwein (BB), adaptée aux problèmes de type matrice en utilisant le produit de Frobenius. La taille de pas $\alpha_k$ est calculée comme $\langle S_{k-1}, S_{k-1} \rangle / \langle S_{k-1}, Y_{k-1} \rangle$, où $S$ et $Y$ représentent respectivement les changements dans les itérés et les gradients. Cela approxime un comportement de type Newton au coût d'un premier ordre.
2. Projection en Deux Étapes :
   • Un point d'essai $Z_k$ est calculé en utilisant une étape de gradient projeté standard avec un facteur d'échelle automatique $\rho_0$ lié à la constante de Lipschitz du gradient.
   • Ensuite, une direction de descente $D_k$ est formée en projetant depuis $Z_k$ en utilisant la taille de pas BB.
3. Recherche de Pas Non Monotone : Contrairement aux méthodes traditionnelles exigeant une décroissance monotone à chaque itération, SNMPBB utilise une recherche de pas non monotone. Elle compare la nouvelle valeur de la fonction par rapport à une valeur de référence $F_k$, qui est une moyenne pondérée des valeurs de fonction récentes. Cette relaxation permet à l'algorithme d'échapper aux minima locaux et de gérer plus efficacement les paysages non convexes. Un facteur de relaxation $\phi$ est appliqué pour amplifier l'étape de descente.

2.3. Extensions

• Graph-SNMPBB : Pour le clustering de graphes, la méthode incorpore une régularisation par le Laplacien du graphe pour traiter les problèmes de clustering "soft" et améliorer la qualité des clusters. L'objectif inclut un terme $\frac{\gamma}{2}\text{tr}(HLH^T)$, où $L$ est le Laplacien du graphe.
• LAI-SNMPBB : Pour gérer les problèmes à grande échelle, la méthode intègre la méthodologie de l'Entrée à Bas Rang Approchée (LAI - Low-rank Approximate Input). La matrice d'entrée $V$ est approximée via un sketching aléatoire ($V \approx AB$). Crucialement, les auteurs prouvent que le calcul de la taille de pas BB reste invariant à cette erreur d'approximation car le biais introduit par l'approximation s'annule dans la différence de gradient utilisée pour l'étape BB.

3. Analyse Théorique

L'article fournit des garanties de convergence rigoureuses :

• Convergence Globale : Il est prouvé que SNMPBB converge globalement vers des points stationnaires du premier ordre. La preuve repose sur la convexité de l'objectif par rapport à une variable (lorsque l'autre est fixée) et la continuité de Lipschitz du gradient.
• Préservation de la Courbure : Pour la variante LAI, l'analyse démontre que l'information de courbure de Barzilai-Borwein est préservée malgré l'approximation de bas rang de $V$. Le biais du gradient introduit par l'approximation est constant par rapport aux mises à jour de variables et n'affecte donc pas le calcul de la taille de pas.
• Bornes d'Erreur : L'écart résiduel entre la solution LAI et la solution optimale est borné par deux fois l'erreur d'approximation du substitut de bas rang.

4. Résultats Expérimentaux

Les auteurs ont évalué SNMPBB et ses variantes contre des méthodes de pointe (SymANLS, SymNewton, PGD, et LAI-SymPGNCG) sur des jeux de données synthétiques et réels.

• Données Synthétiques : Sur des matrices synthétiques denses, SNMPBB a obtenu une accélération de 6x par rapport à SymANLS et une accélération de 2x par rapport à SymNewton pour des valeurs résiduelles similaires. L'avantage de performance de SNMPBB a augmenté de manière significative à mesure que le rang $r$ augmentait, soulignant la scalabilité des méthodes de premier ordre par rapport à la complexité $O(n^2r^2)$ ou $O(n^3r^3)$ des méthodes de Moindres Carrés Alternés et de Newton.
• Benchmarks de Clustering de Graphes : Sur six jeux de données réels (incluant COIL20, Isolet, MNIST, ORL, Reuters, et TDT2), Graph-SNMPBB a égalé ou dépassé la précision de clustering de SymANLS tout en convergeant nettement plus vite. Les avantages étaient plus prononcés sur les jeux de données textuels de haute dimension et parcimoniers (Reuters, TDT2) ainsi que sur les jeux de données d'images avec de fortes structures visuelles (MNIST, COIL20).
• Performance LAI à Grande Échelle : Sur 34 matrices SuiteSparse, LAI-SNMPBB a surpassé l'état de l'art LAI-SymPGNCG tant en temps d'exécution qu'en qualité du résidu final.
  • Une conclusion clé fut que limiter les itérations de descent de gradient interne à 3–5 étapes (arrêt précoce) empêchait le surapprentissage de l'erreur d'approximation de bas rang, agissant comme un mécanisme de régularisation implicite. Cela a permis une meilleure généralisation et une convergence plus rapide par rapport à l'exécution des boucles internes jusqu'à convergence complète.

5. Signification et Revendications

L'article affirme que les méthodes de gradient projeté pour la Symmetric NMF ont été historiquement sous-estimées. En intégrant des recherches de pas non monotones, des tailles de pas Barzilai-Borwein et un couplage par pénalité, les auteurs démontrent que les algorithmes de gradient de premier ordre peuvent être nettement plus efficaces qu'on ne le pensait.

Les principales contributions sont :

1. SNMPBB : La première adaptation des méthodes de Barzilai-Borwein projetées non monotones à la Symmetric NMF, prouvant que les algorithmes de gradient peuvent surpasser les approches établies de Moindres Carrés Alternés et de Newton en termes de vitesse et de précision.
2. Graph-SNMPBB : Une extension qui applique avec succès la régularisation par le Laplacien du graphe pour améliorer les performances de clustering sur des benchmarks réels.
3. LAI-SNMPBB : Une variante scalable pour les problèmes de grande taille qui préserve l'information de courbure BB sous l'approximation de bas rang et utilise l'arrêt précoce comme stratégie de régularisation.

Le travail conclut qu'avec des adaptations appropriées (mise à l'échelle de la courbure, stratégies de globalisation et régularisation), les méthodes de premier ordre offrent un équilibre efficace entre efficacité computationnelle, scalabilité et qualité de solution pour la factorisation de matrices symétriques et le clustering de graphes.