Classements et cycles cachés

Le corrigé construit d’abord la décomposition gradient/cycle, puis le problème de moindres carrés et enfin la décomposition de Hodge discrète.

I — Gradients et circulations

1. Si $e$ est orientée de $i$ vers $j$, sa colonne dans $B$ contient $-1$ en ligne $i$ et $+1$ en ligne $j$. Donc

$$(B^\top p)_e=p_j-p_i.$$

Un gradient mesure ainsi une différence de potentiel entre les extrémités de l’arête.

Pour un flot $x$, la coordonnée $(Bx)_i$ est la somme des valeurs des arêtes entrant en $i$ moins la somme des valeurs des arêtes sortant de $i$. Avec notre convention de signes, il s’agit du bilan net entrant au sommet $i$.

2. Par définition de la transposée,

$$\langle B^\top p,x\rangle=(B^\top p)^\top x=p^\top Bx=\langle p,Bx\rangle.$$

Si $x\in\ker B$, alors $Bx=0$, donc $\langle B^\top p,x\rangle=0$ pour tout $p$. Ainsi

$$\operatorname{Im}(B^\top)\perp\ker B.$$

3. Chaque colonne de $B$ contient un $-1$ et un $+1$, donc

$$B^\top\mathbf1=0.$$

Réciproquement, si $B^\top p=0$, alors pour toute arête $i\to j$,

$$p_j-p_i=0.$$

Deux sommets adjacents portent donc la même valeur. Le graphe étant connexe, on peut relier n’importe quels deux sommets par un chemin : toutes les coordonnées de $p$ sont égales. Ainsi

$$\ker(B^\top)=\operatorname{Vect}(\mathbf1).$$

Le théorème du rang donne

$$\operatorname{rg}B=\operatorname{rg}(B^\top)=n-1,$$

puis

$$\dim\ker B=m-\operatorname{rg}B=m-n+1.$$

4. Les deux sous-espaces sont orthogonaux d’après la question 2. De plus

$$\dim\operatorname{Im}(B^\top)+\dim\ker B=(n-1)+(m-n+1)=m.$$

Ils forment donc une somme directe égale à $\mathbb R^m$ :

$$\mathbb R^m=\operatorname{Im}(B^\top)\mathbin{\overset\perp\oplus}\ker B.$$

Tout flot $x$ s’écrit de manière unique

$$x=B^\top p+c, \qquad Bc=0.$$

La composante $B^\top p$ est unique, même si le potentiel $p$ lui-même ne l’est qu’à une constante additive près.

[IDÉE] La dimension $m-n+1$ est déjà révélatrice : un arbre connexe a $m=n-1$ et ne possède aucun flot cyclique non nul ; chaque arête ajoutée au-delà d’un arbre crée une direction cyclique supplémentaire.

II — Le meilleur score global

5. Le vecteur $B^\top p$ est le projeté orthogonal de $y$ sur $\operatorname{Im}(B^\top)$ si et seulement si

$$r=y-B^\top p\in\operatorname{Im}(B^\top)^\perp.$$

Or, d’après la question 2,

$$\operatorname{Im}(B^\top)^\perp=\ker B.$$

Ainsi la condition équivaut à $Br=0$, soit

$$B(y-B^\top p)=0.$$

On obtient les équations normales

$$BB^\top p=By.$$

L’espace $\operatorname{Im}(B^\top)$ est de dimension finie ; le projeté orthogonal de $y$ sur cet espace existe donc. D’après la première partie de la question, tout potentiel $p$ représentant ce projeté fournit une solution des équations normales : celles-ci admettent donc au moins une solution.

Si $p$ et $q$ sont deux solutions,

$$BB^\top(q-p)=0.$$

Alors

$$0=(q-p)^\top BB^\top(q-p)=\|B^\top(q-p)\|^2,$$

donc $B^\top(q-p)=0$ et, par la question 3,

$$q-p\in\operatorname{Vect}(\mathbf1).$$

Parmi tous les représentants $p+\lambda\mathbf1$, une unique valeur de $\lambda$ impose $p_1+\cdots+p_n=0$. Il existe donc une unique solution normalisée.

6. Comme $L=BB^\top$,

$$L^\top=(BB^\top)^\top=BB^\top=L.$$

De plus, pour tout $p$,

$$p^\top Lp=p^\top BB^\top p=\|B^\top p\|^2\geqslant0.$$

Chaque coordonnée de $B^\top p$ associée à une arête $i\to j$ vaut $p_j-p_i$, d’où

$$p^\top Lp=\sum_{\{i,j\}\in E}(p_j-p_i)^2.$$

On a $Lp=0$ si et seulement si $p^\top Lp=0$, donc si et seulement si $B^\top p=0$. Ainsi

$$\ker L=\operatorname{Vect}(\mathbf1).$$

Enfin, $L_{ii}$ est la somme des carrés des coefficients de la ligne $i$ de $B$ : c’est le nombre d’arêtes incidentes à $i$, donc son degré. Pour $i\neq j$, le produit scalaire des lignes $i$ et $j$ vaut $-1$ si une arête les relie et $0$ sinon.

7. Inverser l’orientation de l’arête $e$ revient à multiplier la colonne $e$ de $B$ par $-1$. Si $D$ est la matrice diagonale égale à l’identité sauf en position $e$, où elle vaut $-1$, la nouvelle incidence est

$$B'=BD.$$

Les mêmes données physiques sont représentées par $y'=Dy$. Alors

$$B'y'=BDDy=By, \qquad B'B'^\top=BDDB^\top=BB^\top.$$

Les équations normales sont donc inchangées. Le score normalisé $p$ est le même. Le résidu change seulement de coordonnées :

$$y'-B'^\top p=D(y-B^\top p),$$

et $D$ est orthogonale, donc sa norme est inchangée.

III — Un exemple : quatre objets et une préférence cyclique

8. Dans l’ordre des arêtes $12,13,14,23,24,34$,

$$B= \begin{pmatrix} -1&-1&-1&0&0&0\\ 1&0&0&-1&-1&0\\ 0&1&0&1&0&-1\\ 0&0&1&0&1&1 \end{pmatrix}.$$

Un produit direct donne

$$BB^\top= \begin{pmatrix} 3&-1&-1&-1\\ -1&3&-1&-1\\ -1&-1&3&-1\\ -1&-1&-1&3 \end{pmatrix}.$$

9. On calcule

$$By=(-12,-4,4,12)^\top.$$

Pour $K_4$,

$$L=4I_4-J,$$

où $J$ est la matrice dont tous les coefficients valent $1$. Sur l’hyperplan des vecteurs de somme nulle, $Jp=0$, donc $Lp=4p$. La solution normalisée est ainsi

$$p=(-3,-1,1,3)^\top.$$

Le gradient associé vaut

$$B^\top p=(2,4,6,2,4,2)^\top,$$

et le résidu est

$$c=(1,-1,0,1,0,0)^\top.$$

Ses trois composantes non nulles concernent les arêtes $12$, $13$ et $23$ : elles forment la circulation

$$1\to2\to3\to1.$$

Le classement global est cohérent avec $4>3>2>1$, mais les données contiennent en plus une petite préférence cyclique entre $1$, $2$ et $3$.

10. On vérifie directement que

$$Bc=0.$$

De plus

$$\|c\|^2=3, \qquad \|y\|^2=9+9+36+9+16+4=83.$$

Donc

$$\frac{\|c\|^2}{\|y\|^2}=\frac3{83}\approx3,6\%.$$

Cette proportion mesure ici la part quadratique de l’information qui n’est pas expliquée par un classement global par scores.

IV — Cycles locaux, cycles globaux : une décomposition de Hodge

11. Considérons une colonne de $C$, c’est-à-dire le bord d’un triangle orienté. À chacun de ses trois sommets, une arête du bord entre et une autre sort. Le bilan est donc nul en chaque sommet : $B$ appliqué à cette colonne vaut $0$. Ainsi

$$BC=0.$$

Par conséquent

$$\operatorname{Im}C\subset\ker B.$$

Enfin, pour tous $p$ et $u$,

$$\langle B^\top p,Cu\rangle=\langle p,BCu\rangle=0,$$

d’où

$$\operatorname{Im}(B^\top)\perp\operatorname{Im}C.$$

[IDÉE] L’identité $BC=0$ traduit ici un fait très concret : parcourir entièrement un cycle triangulaire ne crée ni source ni puits à ses sommets.

12. Posons

$$F=\operatorname{Im}(B^\top)+\operatorname{Im}C.$$

Les deux termes sont orthogonaux, donc la somme est directe. Un vecteur $x$ appartient à $F^\perp$ si et seulement si

$$x\perp\operatorname{Im}(B^\top) \qquad\text{et}\qquad x\perp\operatorname{Im}C.$$

La première condition équivaut à $Bx=0$, la seconde à $C^\top x=0$. Ainsi

$$F^\perp=\ker B\cap\ker C^\top=H.$$

Dans l’espace euclidien $\mathbb R^m$,

$$\mathbb R^m=F\mathbin{\overset\perp\oplus}F^\perp.$$

On obtient donc

$$\mathbb R^m =\operatorname{Im}(B^\top) \mathbin{\overset\perp\oplus}\operatorname{Im}C \mathbin{\overset\perp\oplus}H.$$

13. Pour le triangle $123$ orienté $1\to2\to3\to1$, le bord a pour coordonnées, dans l’ordre $12,13,14,23,24,34$,

$$(1,-1,0,1,0,0)^\top.$$

C’est exactement le résidu $c$.

Les bords de $123$, $124$ et $134$ sont linéairement indépendants : dans une combinaison linéaire nulle, les coefficients des arêtes $23$, $24$ et $34$ imposent successivement la nullité des trois coefficients de combinaison. Leur espace engendré est donc de dimension au moins $3$.

Or, pour $K_4$, $n=4$ et $m=6$, donc

$$\dim\ker B=m-n+1=3.$$

Comme $\operatorname{Im}C\subset\ker B$, on a nécessairement

$$\operatorname{Im}C=\ker B.$$

Ainsi

$$H=\{0\}.$$

Tous les cycles sont ici engendrés par des cycles triangulaires locaux.

14. Pour le carré, $n=4$ et $m=4$, donc

$$\dim\ker B=m-n+1=1.$$

Un flot constant égal à $1$ lorsqu’on suit le cycle $1\to2\to3\to4\to1$ a divergence nulle : à chaque sommet, une unité entre et une unité sort. Il est non nul, donc il engendre $\ker B$.

Aucun triangle n’étant sélectionné, $C=0$ et donc $\ker C^\top=\mathbb R^m$. Ainsi

$$H=\ker B.$$

Le cycle est global : il entoure le trou du carré et ne peut pas être écrit comme somme de circulations autour de triangles, puisqu’il n’existe aucune face triangulaire dans le modèle.

Dans la première décomposition, tout résidu était simplement « cyclique ». L’ajout de la matrice $C$ distingue maintenant les cycles locaux, engendrés par les triangles sélectionnés, des cycles harmoniques qui subsistent à l’échelle globale. Cette distinction est exactement celle qui rend la décomposition utile au-delà d’un simple calcul de projection.

Sources

[SOURCE] L.-H. Lim, Hodge Laplacians on Graphs, SIAM Review 62(3), 2020 : Lien direct.

[SOURCE] X. Jiang, L.-H. Lim, Y. Yao et Y. Ye, Statistical Ranking and Combinatorial Hodge Theory, Mathematical Programming 127, 2011 : Lien direct.