4.4 Perturbation de matrices

Nous avons déjà mentionné que le spectral clustering repose sur la propriété suivante: si une matrice \(M\) est perturbée légèrement, p.ex. en additionnant un bruit \(H\), alors le spectre de la matrice \(\tilde M=M+H\) est proche de celui de \(M\). Or, un graphe \(G\) structuré en quasi-cliques, disons de nombre \(k\), peut être considéré comme la perturbation d’un graphe avec \(k\) vraies cliques, i.e. \(k\) composantes connexes, auquel on a ajouté quelques arêtes. Et donc on s’attend à ce que le spectre de \(G\) soit proche du spectre d’un graphe à \(k\) composantes connexes. En particulier, on s’attend à la présence de \(k\) valeurs propres très proches de 0, et les vecteurs propres associés contiennent de l’information sur les clusters.

4.4.1 Théorie de perturbation

La théorie de perturbation de matrice étudie l’impact d’une perturbation sur le spectre d’une matrice. Le théorème de Davis-Kahan (Theorem VII.3.1 dans Bhatia (1997)) donne une borne pour la différence des espaces propres de matrices symétriques perturbées.

Nous avons besoin d’introduire une notion de différence entre deux sous-espaces vectoriels. En théorie de perturbation on utilise des angles. Soient \(\mathcal V\) et \(\tilde{\mathcal V}\) deux sous-espaces vectoriels de \(\mathbb R^n\) de dimenion \(k\) et \(m\), resp. Soient \(U\) et \(\tilde U\) deux matrices dont les colonnes forment des bases orthonormées de \(\mathcal V\) et \(\tilde{\mathcal V}\), resp. On définit alors l’ensemble d’angles principaux associés à \(\mathcal V\) et \(\tilde{\mathcal V}\) comme les valeurs \(\Theta\) telles que \(\cos(\Theta)\) sont les valeurs singulières de la matrice \(U^T\tilde U\).

Exemple. Si \(k=m=1\), le cosinus de l’angle principal est l’angle habituel entre deux vecteurs.

Enfin, on définit une distance entre les espaces \(\mathcal V\) et \(\tilde{\mathcal V}\) par \[d(\mathcal V, \tilde{\mathcal V}) = \|\sin(\Theta)(\mathcal V, \tilde{\mathcal V})\|,\] où \(\sin(\Theta)\) est la matrice diagonale dont les éléments diagonaux sont le sinus des angles principaux \(\Theta\).

Theorem 4.5 (Davis-Kahan) Soient \(M,H\in\mathbb R^{n\times n}\) symétriques.

• Notons \(\tilde M=M+H\).

• Soit \(S\subset \mathbb R\) un intervalle.

• Notons \(\sigma(M)\) l’ensemble de valeurs propres de \(M\) et \(\sigma_S(M)=\sigma(M)\cap S\).

• Notons \(\delta\) la distance entre \(S\) et les valeurs propres de \(M\) dans \(\bar S\), i.e. \(\sigma_{\bar S}(M)\), par \[\delta=\min\left\{|\lambda-s|:\lambda\subset \sigma_{\bar S}(M) \text{ et } s\in S \right\}.\]

• Notons \(\mathcal V\) l’espace propre correspondant aux valeurs propres \(\sigma_S(M)\) de \(M\) dans \(S\).

• De même, notons \(\tilde{\mathcal V}\) l’espace propre associé aux valeurs propres \(\sigma_S(\tilde M)\).

Alors, \[\begin{equation} d(\mathcal V,\tilde{\mathcal V})\leq\frac{\|H\|}{\delta}. \tag{4.3} \end{equation}\]

 

En (4.3) la norme matricielle dans le terme à droite peut être la norme de Frobenius définie par \[\|A\|_F= \sqrt{\sum_{i,j} A_{i,j}^2}=\sqrt{\text{Trace}(A^TA)}= \sqrt{\sum_i \sigma_i^2(A)},\] où \(\sigma_i(A)\) désignent les valeurs singulières de \(A\)), ou la norme 2 pour matrices donnée par \[\|A\|_2=\sigma_{\max}(A).\]

Si on note \(U\in\mathbb R^{n\times k}\) la matrice dont les colonnes sont les vecteurs propres de \(M\) associés aux valeurs propres dans \(\sigma_S(M)\), alors \(\mathcal V\) est le sous-espace vectoriel engendré par les colonnes de \(U\). De même, soit \(\tilde U\) la matrice formée par les vecteurs propres de \(\tilde M\) associés aux valeurs propres dans \(\sigma_S(\tilde M)\). On trouve alors les angles principaux de \(\mathcal V\) et \(\tilde{\mathcal V}\) à travers les valeurs singulières de la matrice \(U^T\tilde U\).

Pour le spectral clustering on s’intéresse aux vecteurs propres proches de 0, mais le théorème s’applique à n’importe quel intervalle \(S\) de valeurs propres.

4.4.2 Perturbation de graphe

Pour appliquer le théorème au spectral clustering, considérons un graphe idéal \(G\) avec \(k\) composantes connexes de matrice d’adjacacence \(A\) et matrice laplacienne non normalisée \(L\) (les calculs sont plus simples dans le cas du laplacien non normalisé que pour les autres laplaciens). Puis on ajoute quelques arêtes au graphe \(G\) pour obtenir un graphe perturbé, note \(\tilde G\). Cette perturbation peut être décrite par la matrice d’adjacence \(H\) qui contient les nouvelles arêtes. Notons \(\tilde A=A+H\) la matrice d’adjacence de \(\tilde G\) et \(\tilde L\) sa matrice laplacienne. Enfin, notons \(\lambda_1\leq \dots\leq \lambda_n\) et \(\tilde\lambda_1\leq \dots\leq \tilde\lambda_n\) les valeurs propres de \(L\) et \(\tilde L\), resp.

Maintenant il faut choisir l’intervalle \(S\) du théorème. Dans le spectral clustering on s’intéresse aux \(k\) plus petites valeurs propres. Il faut alors choisir \(S\) tel que cet intervalle contient à la fois les \(k\) plus petites valeurs propres de \(L\) et de les \(k\) plus petites valeurs propres de \(\tilde L\). Or, dans le cas du graphe idéal \(G\), on a \(\lambda_1= \dots= \lambda_k=0\), à cause des \(k\) composantes connexes. Quant à \(\tilde G\), si la perturbation a connecté certaines composantes entre eux, alors \(\tilde\lambda_k>0\). On devrait alors choisir \(S=[0,\varepsilon]\), où \(\varepsilon>0\) est petite. On voit bien que, plus le eigengap \(\lambda_{k+1}-\lambda_k\) est petit, plus le choix de \(\varepsilon\) est délicat.

Alors, d’après le théorème de Davis-Kahan, la différence entre les \(k\) premiers vecteurs propres de \(L\) et de \(\tilde L\) est petite: \[d(\mathcal V,\tilde{\mathcal V})\leq\frac{\|\tilde L-L\|}{\lambda_{k+1}-\varepsilon}.\]

Le dénominateur \(\lambda_{k+1}-\varepsilon\) est proche du eigengap, qui autant plus grand que la structure du graphe \(G\) en \(k\) clusters est pertinente.

Quant au numérateur, on a \[\begin{align*} \tilde L-L&=\tilde D-\tilde A -D+A\\ &=D-D_H- A-H -D+A\\ &=D_H-H=:L_H, \end{align*}\] où \(D_H\) est la matrice de degrés de la perturbation \(H\) et \(L_H\) la matrice laplacienne non normalisée de \(H\).

Exemple. Dans le cas d’un graphe binaire, si la perturbation du graphe consiste à ajouter une seule arête, alors \(H\) est une matrice symétrique avec des 0 partout et deux entrées égales à 1. A une permutation des lignes et des colonnes près, le laplacien associé est \[L_H=\begin{pmatrix} 1 &-1&0&\cdots\\ -1&1&0&\cdots\\ 0&0&0&\\ \vdots&&&0 \end{pmatrix}.\] Donc, on a \(\|L_H\|_F=2\). Plus généralement, si on ajoute \(p\) arêtes à des noeuds différents (on augmente le degré d’un noeud au plus de 1), le laplacien est tel que \(\|L_H\|_F=2\sqrt p\).

 

Le théorème de Davis-Kahan montre que si le eigengap est trop petit, alors la borne explose. De même, si la perturbation \(H\) est importante, la borne devient très large et les \(k\) premiers vecteurs propres de \(L\) et \(\tilde L\) risquent d’être très différents et l’algorithme de \(k\)-means ne pourra pas détecter les clusters correctement.

4.4.3 Commentaires

Peut-on utiliser directement la matrice d’adjacence ?

Toute matrice symétrique, diagonale par bloc a la propriété qu’il existe une base de vecteurs propres qui sont zéros en dehors des blocs et non-nul à l’intérieur. Cela laisse penser qu’on pourrait directement diagonaliser la matrice d’adjacence \(A\) pour faire du spectral clustering. En revanche, ça ne marche pas.

En fait, il faut savoir distinguer entre les vecteurs propres qui portent l’information sur le clustering (qui sont des combinaisons linéaires des vecteurs indicateurs de classe \(\mathbb 1_{C_l}\)) et les autres. Donc, l’ordre des valeurs propres du laplacien est très important afin de pouvoir d’identifier les bons vecteurs propres. Quant à la matrice d’adjacence, il n’y pas d’ordre.

Performance de l’algorithme \(k\)-means

Pour que l’algorithme \(k\)-means identifie bien les clusters quand on l’applique sur les lignes de la matrice composée de vecteurs propres du laplacien, il est important que la différence entre une vraie valeur non nulle et une valeur qui est un zéro perturbé soit significative.

Pour le laplacien non normalisé \(L\), dans le cas idéal d’un graphe à \(k\) composantes connexes, les vecteurs propres sont composés de 0 et de 1 (ce sont les vecteurs indicateurs \(\mathbb 1_{C_m}\)). Donc, ici il n’y a pas de problème, car la différence entre 0 et 1 est nette. Cette version du spectral clustering est alors bien justifiée par la théorie de perturbation.

En revanche, les vecteurs propres du laplacien normalisé \(L_N\) dans le cas d’un graphe à \(k\) composantes connexes sont des vecteurs de la forme \(D^{1/2}\mathbb 1_{C_m}\). Donc, si les degrés varient beaucoup et notamment si le graphe contient des noeuds à très faible degré, alors la différence entre un zéro perturbé et une vraie valeur non nulle peut ne pas être évidente. Afin de contourner ce problème, Ng, Jordan, and Weiss (2001) introduisent la renormalisation des lignes de \(U\), car dans le cas idéal, les lignes de \(U\) ne contiennent qu’une seule valeur non nulle. En revanche, cette astuce ne conduit pas toujours au bon résultat.

Consistance du spectral clustering

La conistance du spectral clustering a été également étudiée pour différentes algorithmes. Luxburg, Belkin, and Bousquet (2008) montrent que le spectral clustering normalisé basé sue \(L_N\) a de bien meilleures propriétés théoriques que le non normalisé. Quant au spectral clustering basé sur \(L_{\rm abs}\), des conditions sous lesquelles il est consistent sont données dans Rohe, Chatterjee, and Yu (2011).

Lei and Rinaldo (2015) analyse le cas où on diagonalise directement la matrice d’adjacence. Ils montrent la convergence du clustering pour des graphes sparses.

References

Bhatia, Rajendra. 1997. Matrix Analysis. Graduate Texts in Mathematics, 169. New York: Springer-Verlag.

Lei, Jing, and Alessandro Rinaldo. 2015. “Consistency of Spectral Clustering in Stochastic Block Models.” The Annals of Statistics 43 (1): 215–37.

Luxburg, Ulrike von, Mikhail Belkin, and Olivier Bousquet. 2008. “Consistency of Spectral Clustering.” The Annals of Statistics 36 (2): 555–86.

Ng, Andrew Y., Michael I. Jordan, and Yair Weiss. 2001. “On Spectral Clustering: Analysis and an Algorithm.” In Advances in Neural Information Processing Systems, 849–56. MIT Press.

Rohe, K., S. Chatterjee, and B. Yu. 2011. “Spectral Clustering and the High-Dimensional Stochastic Blockmodel.” Annals of Statistics 39 (4): 1878–1915.