4.1 Matrices laplaciennes de graphe

On vient de dire que la matrice d’adjacence d’un graphe composé de communautés, est une matrice presque diagonale par blocs à une permutation des lignes et des colonnes près. Or, pour des raisons liées à l’ordre des valeurs propres de la matrice, le clustering spectral ne diagonalise pas la matrice d’adajcence du graphe, mais plutôt une version normalisée de celui-ci: une matrice laplacienne du graphe \(G\). Il y a plusieurs définitions de matrices laplaciennes d’un graphe, ici nous n’en considérerons que certaines.

Dans la suite, \(G\) est un graphe valué et non dirigé, de matrice d’adjacence valuée \(A\) (taille \(n\times n\)) dont les entrées sont positives \(A_{ij}\ge 0\). On note \(D\) la matrice des degrés définie comme la matrice diagonale de taille \(n\) dont la diagonale vaut \((d_1,\dots, d_n)\), où \(d_i\) est le degré valué du noeud \(i\) dans \(G\), i.e. \(d_i=\sum_{j}A_{ij}=\sum_{j}A_{ji}\) est la somme des poids des arêtes issues de \(i\). Le cas d’un graphe binaire est un cas particulier du cas général que l’on décrit ici.

Pour tout vecteur (colonne) \(u \in \mathbb R^n\), on note \(u^\intercal\) le vecteur (ligne) transposé de \(u\). On note \(\mathbb{1}\) le vecteur dont toutes les coordonnées valent 1 et \(I\) la matrice identité. Les valeurs propres d’une matrice seront ordonnées de façon croissante, en respectant les multiplicités. Ainsi, les ‘\(k\) premiers vecteurs propres’ désignent les \(k\) vecteurs propres associés aux \(k\) plus petites valeurs propres.

Rappels: une matrice \(L\) symétrique réelle est diagonalisable dans une base orthogonale de vecteurs propres et possède \(n\) valeurs propres réelles. Si la matrice est en plus positive (i.e. pour tout \(u\in \mathbb R^n,\) on a \(u^\intercal L u \ge 0\)) alors les valeurs propres sont positives.

Nous commençons par définir la matrice laplacienne de graphe la plus simple et par donner ses propriétés spectrales, i.e. des valeurs propres et vecteurs propres associés.

4.1.1 Laplacien non normalisé

Definition 4.1 (Laplacien non normalisé) On définit la matrice laplacienne non normalisée \(L\) d’un graphe par \[ L = D- A. \]

Theorem 4.1 (Spectre de \(L\)) La matrice \(L\) vérifie les propriétés suivantes

Pour tout vecteur \(u \in \mathbb R^n\) on a \[\begin{equation} u^\intercal L u = \frac 1 2 \sum_{i,j=1}^n A_{ij} (u_i-u_j)^2. \tag{4.1} \end{equation}\]
La matrice \(L\) est symétrique et semi-définie positive.
La plus petite valeur propre de \(L\) est 0 et le vecteur propre associé est \(\mathbb{1}\).
La matrice \(L\) possède \(n\) valeurs propres réelles positives, notées \(0=\lambda_1\le \lambda_2\le \dots \le \lambda_n\).

Proof. Par définition du laplacien \(L=D-A\) et de la matrice des degrés \(D\), on a pour tout \(u \in \mathbb R^n\),
\[\begin{align*} u^\intercal L u &= u^\intercal D u - u^\intercal A u \\ &= \sum_{i=1}^n u_i ^2 d_i - \sum_{i,j} u_i A_{ij} u_j\\ &= \frac 1 2 \Big( \sum_{i=1} ^n d_i u_i^2 - 2\sum_{i,j} u_i u_j A_{ij} +\sum_{j=1}^n d_j u_j^2\Big)\\ & = \frac 1 2 \sum_{i,j} A_{ij}(u_i-u_j)^2, \end{align*}\] car \(\sum_j A_{ij}=d_i\) et \(\sum_{i} A_{ij}=d_j\). Ceci prouve le point 1.

Comme \(D\) et \(A\) sont symétriques, la matrice \(L=D-A\) l’est aussi. D’après (4.1), on a pour tout \(u\in \mathbb R^n,u^\intercal L u \ge 0\), donc \(L\) est semi-définie positive. En conséquence, ses valeurs propres sont réelles et positives, on les note \(\lambda_1\le \lambda_2\le \dots \le \lambda_n\). Enfin, par définition de \(L\), on voit que \(\mathbb{1}\) est un vecteur propre, associé à la valeur propre 0, puisque \(\sum_{i}A_{ij}=d_i\).

Remarque.

Si le graphe a des boucles, alors la diagonale de \(A\) n’est pas nulle. Pourtant, le laplacien \(L=D-A\), où \(D\) est la matrices de degrés toujours défini comme la matrice diagonale dont les entrées sont la somme des lignes de \(A\), a le même spectre que celui du graphe sans boucles. Et donc on pourra appliquer la méthode de spectral clustering associé au laplacien non normalisé. Mais attention, cette remarque n’est pas du tout valable pour les laplaciens qui vont suivre. Donc, il est préférable de bien faire attention à la diagonale de \(A\).

Theorem 4.2 (Nombre de composantes connexes de \(G\) et spectre de \(L\)) Soit \(G\) un graphe valué dont les poids des arêtes sont positifs et \(L\) la matrice laplacienne non normalisée associée. Alors la multiplicité de 0 en tant que valeur propre de \(L\) est exactement le nombre de composantes connexes du graphe \(G\). Notons \(C_1,\dots,C_k \subset \{v_1,\dots, v_n\}\) ces composantes connexes et \(\mathbb{1}_{C_1}, \dots , \mathbb{1}_{C_k}\) les vecteurs indicatrices des composantes définis par \(\mathbb{1}_{C_l}(i)=1\) si \(v_i\in C_l\) et \(\mathbb{1}_{C_l}(i)=0\) sinon. Alors l’espace propre associé à la valeur propre 0 est engendré par \(\mathbb{1}_{C_1}, \dots , \mathbb{1}_{C_k}\).

Proof. On commence par considérer le cas \(k=1\) d’une seule composante connexe dans le graphe. Si \(u\in \mathbb R^n\) est un vecteur propre de \(L\) associé à la valeur propre 0, on a \(Lu=0\) et d’après (4.1), \[ u^\intercal L u = 0 = \sum_{i,j} A_{ij} (u_i-u_j) ^2. \] Puisque \(A_{i,j}\ge 0\), la somme est nulle seulement si tous ses termes sont nuls, i.e. seulement si pour tout \(1\le i,j\le n\) on a \(A_{ij} (u_i-u_j) ^2=0\). Si l’arête \(\{v_i,v_j\}\in E\) alors le poids \(A_{ij}\) est non nul et nécessairement \(u_i=u_j\). Donc le vecteur propre \(u\in \mathbb R^n\) est constant sur les coordonnées correspondant à des noeuds connectés dans le graphe. Par définition d’une composante connexe (tous les noeuds dans la composante sont connectés), et puisqu’on a une seule composante connexe (cas \(k=1\)), on a \(u_i=\text{constante}\) pour tout \(i\in \{1,\dots,n\}\). Donc \(u\) est proportionnel à \(\mathbb{1}\), i.e. le vecteur \(\mathbb{1}\) engendre l’espace propre associé à la valeur propre 0.

Si \(k \ge 2\). Soient \(C_1,\dots,C_k \subset \{v_1,\dots, v_n\}\) les composantes connexes du graphe \(G\). Sans perte de généralité, on peut supposer que les noeuds de \(V\) sont ordonnés selon la composante à laquelle ils appartiennent. Alors, la matrice d’adjacence \(A\) a une forme diagonale par blocs (puisque si \(v_i,v_j\) ne sont pas dans la même composante connexe, alors \(A_{ij}=0\)). En conséquence, \(L=D-A\) a aussi une forme diagonale par blocs \[ L= \begin{pmatrix} L_1 & & & \\ & L_2 & &\\ & & \ddots&\\ &&& L_k \end{pmatrix} . \] Chacun des blocs \(L_i\) (de taille \(n_i\times n_i\)) est une matrice laplacienne, associé au sous-graphe \(G_i=(C_i,E_i)\subset G\) induit par la \(i\)-ème composante connexe \(C_i\) (de cardinal \(n_i\)) de \(G\). L’ensemble des valeurs propres de \(L\) (= spectre de \(L\)) est la réunion des spectres de chaque \(L_i\) et les vecteurs propres correspondants sont formés par les vecteurs propres de \(L_i\), augmentés de coordonnées nulles aux positions des autres blocs. Comme pour chaque sous-graphe \(G_i\), on a une seule composante connexe, le résultat précédent nous dit que l’espace propre associé à la valeur propre 0 de \(L_i\) est engendré par \(\mathbb{1}_{C_i}\) (dans \(\mathbb R^{n_i}\)). On obtient donc que l’espace propre associé à la valeur propre 0 de \(L\) est engendré par les vecteurs \(\mathbb{1}_{C_1}, \dots , \mathbb{1}_{C_k}\) (en tant que vecteurs de \(\mathbb R^n\) cette fois).

L’étude du spectre du laplacien d’un graphe permet donc de déterminer simplement le nombre de composantes connexes de ce graphe.

Le laplacien \(L\) est intéressant, car on peut faire facilement des calculs de spectre et l’interpréter. Cependant pour le clustering il ne donne pas les meilleurs résultats numériques possibles et on lui préfère des versions normalisées.

4.1.2 Laplacien normalisé

Definition 4.2 (Lapalcien normalisé) Pour un graphe sans noeud isolé, i.e. la matrice de degrés \(D\) est inversible, on définit la matrice laplacienne normalisée par \[\begin{align*} L_{N} = I -D^{-1/2} A D^{-1/2}. \end{align*}\]

Notons que dans la littérature, il existe d’autres définitions de laplacien normalisé.

Rappels.

Comme \(D\) est une matrice diagonale, la matrice \(D^{-1/2}\) est une matrice dont les éléments diagonaux valent \(1/\sqrt{d_i}\) (ce n’est pas vrai si \(D\) n’est pas diagonale !).
La multiplication à gauche par une matrice diagonale revient à multiplier les vecteurs lignes de la matrice, tandis qu’une multiplication à droite multiplie les vecteurs colonnes. Ainsi, \(D^{-1/2} A D^{-1/2}\) est la matrice dont chaque entrée \(i,j\) vaut \(A_{ij}/\sqrt{d_id_j}\). Ainsi, \[ L_N = \begin{pmatrix} 1 &&\\ & \ddots & - \frac{A_{ij}}{\sqrt{d_i d_j} }\\ & &1 \end{pmatrix}. \] C’est une matrice symétrique (puisque \(A\) l’est et \(D\) est diagonale).

Theorem 4.3 (Spectre de \(L_{N}\)) La matrice laplacienne normalisée vérifie les propriétés suivantes:

Pour tout \(u\in \mathbb R^n\), \[ u^\intercal L_{N} u = \frac 1 2 \sum_{1\le i,j\le n } A_{ij} \Big( \frac {u_i} {\sqrt{d_i} }- \frac{u_j}{\sqrt{d_j}}\Big)^2 . \]
0 est valeur propre de \(L_{N}\), de vecteur propre associé \(D^{1/2}\mathbb{1}\).
La matrice \(L_{N}\) est une matrice semi-définie positive qui possède \(n\) valeurs propres réelles positives.

Proof. Soit \(u \in \mathbb R^n\), on a \[\begin{align*} u^\intercal L_{N} u &= u^\intercal ( I -D^{-1/2} A D^{-1/2}) u = \sum_{i=1}^n u_i^2 - \sum_{1\le i,j\le n } u_i u_j \frac{A_{ij}} {\sqrt{d_i d_j}} \\ & = \frac 1 2 \Big( \sum_{i=1}^n u_i^2 - 2 u_i u_j \frac{A_{ij}} {\sqrt{d_i d_j}}+ \sum_{j=1}^n u_j^2 \Big) \\ & = \frac 1 2 \sum_{1\le i,j\le n } A_{ij} \Big( \frac {u_i} {\sqrt{d_i} }- \frac{u_j}{\sqrt{d_j}}\Big)^2 , \end{align*}\] car \(\sum_j A_{ij}= d_i\) et \(\sum_{i}A_{ij}=d_i\). On a donc prouvé le point 1.

On a \(L_{N} D^{1/2}\mathbb{1}= D^{1/2}\mathbb{1}-D^{-1/2}A \mathbb{1}= D^{1/2}\mathbb{1}-D^{-1/2}(d_1,\dots,d_n)^\intercal = D^{1/2} (\mathbb{1} - \mathbb{1})=0\), donc \(0\) est valeur propre de \(L_{N}\) associé au vecteur propre \(D^{1/2}\mathbb{1}\).

D’après le point 1, \(L_{N}\) est semi-définie positive donc ses valeurs propres sont réelles et positives.

La multiplicité de la valeur propre 0 du laplacien normalisé est reliée au nombre de composantes connexes du graphe.

Theorem 4.4 (Nombre de composantes connexes de \(G\) et spectre de \(L_{N}\)) Soit \(G\) un graphe valué dont les poids des arêtes sont positifs et \(L_{N}\) sa matrice laplacienne normalisée. Alors la multiplicité de la valeur propre 0 de \(L_{N}\) est égale au nombre de composantes connexes du graphe \(G\). Si on note \(C_1,\dots,C_k \subset \{v_1,\dots, v_n\}\) ces composantes connexes et \(\mathbb{1}_{C_1}, \dots , \mathbb{1}_{C_k}\) les vecteurs indicatrices des composantes, alors l’espace propre associé à la valeur propre 0 est engendré par les vecteurs \(D^{1/2}\mathbb{1}_{C_1}, \dots , D^{1/2}\mathbb{1}_{C_k}\).

Proof. En exercice.

4.1.3 Laplacien \(L_{\text{abs}}\)

Definition 4.3 (Laplacien \(L_{\text{abs}}\)) On définit la matrice laplacienne \(L_{\text{abs}}\) par \[ L_{\text{abs}} = D^{-1/2} A D^{-1/2} = I - L_{N}. \]

Proposition 4.1 (Relation entre les spectres de \(L_{\text{abs}}\) and \(L_N\)) Notons \(0=\lambda_1\le \lambda_2\le \dots \le \lambda_n\) les valeurs propres de \(L_N\).

Alors les valeurs propres de \(L_{\text{abs}}\) sont \(1-\lambda_n \leq \ldots \le 1-\lambda_2 \le 1-\lambda_1=1\).

Definition 4.4 (Graphe biparti) Un graphe \(G=(V,E)\) est dit biparti, s’il existe un partitionnement des noeuds \(V\) en deux groupes \(C_1\) et \(C_2\) tel que toutes les arêtes dans \(E\) sont des interactions entre un noeud dans \(C_1\) et un noeud dans \(C_2\). Autrement dit, pour \(k\in\{1,2\}\), si \(v_1, v_2\in C_k\), alors \(\{v_1,v_2\}\notin E\).

Proposition 4.2 1. Un graphe est biparti si et seulement si le spectre de \(L_{\text{abs}}\) est symétrique.

Un graphe connexe est bipartie si et seulement si \(\lambda_{\min}(L_{\text{abs}})= - \lambda_{\max}(L_{\text{abs}})\).

Proof. Admis.

Exercice. Soit \(G=(V,E)\) un graphe biparti. Après rénuméroation des noeuds, notons \(C_1=\{1,\dots,n_1\}\) et \(C_2=\{n_1+1,\dots,n_1+n_2\}\) le partionnement de noeuds tels que pour tout \(k\in\{1,2\}\), si \(v_1, v_2\in C_k\), alors \(\{v_1,v_2\}\notin E\).

Pour \(u\in\mathbb R^n\), notons \(u_{(1)}=(u_1,\dots,u_{n_1})^T\in\mathbb R^{n_1}\) et \(u_{(2)}=(u_{n_1+1},\dots,u_{n})^T\in\mathbb R^{n_2}\).

Soient \(u\in\mathbb R^n\) un vecteur propre de \(L_{\text{abs}}\) associé à la valeur propre \(\lambda\).

Montrer que si \(\lambda\neq0\), alors \(\tilde u:=(-u_{(1)}^T, u_{(2)}^T)^T\) est vecteur propre associé à la valeur propre \(\tilde \lambda:=-\lambda\).

Remarque.

Pour les laplaciens \(L\) et \(L_N\) ce sont les petites valeurs propres qui contiennent l’information intéressante sur les composantes connexes, alors que pour le laplacien \(L_{\text{abs}}\) les plus grandes comme les plus petites valeurs propres porte de l’information sur la topologie du graphe. Nous verrons que la méthode de spectral clustering basée sur le laplacien \(L_{\text{abs}}\) regarde les plus grandes valeurs propres en valeur absolue. Ainsi on arrive à capturer à la fois des communautés et des structures biparties.