Significado de la inversa de la matriz laplaciana

Question

Dado un grafo no dirigido $G = (V,E)$ , dejemos que $\bf A$ y $\cal L_{\bf A}$ denotan su matriz de adyacencia y su matriz laplaciana, respectivamente. $\cal L_{\bf A}(i,i)$ es el grado del vértice ${{\bf{v}}_i}$ y $\mathcal L_{\bf A}(i,j) = -1$ si vértices ${{\bf{v}}_i}$ y ${{\bf{v}}_j}$ están conectados.

Sé que la matriz laplaciana es exactamente el operador discreto de Laplace. Dada una función $\phi : V \to \Bbb R$ y suponiendo que $\bf A$ está indexado por $\bf v$ es decir, $\bf A$$ (i,j) = 1$ si vértices ${{\bf{v}}_i}$ y ${{\bf{v}}_j}$ están conectadas, entonces

$$\Delta \phi=\cal L_{\bf A}{\phi(\bf v)}$$

Lo que necesito saber es el significado de la inversa (o pseudoinversa si no es invertible) del Laplaciano. ¿Hay alguna interpretación significativa de la Laplaciano inverso ? ¿Existe alguna significado concreto para $\mathcal L^{-1}_{\bf A}(i,j)$ ?

Answer 1

Una respuesta es en términos de duración del trayecto distancia . Sea $C_{ij}$ denotan la longitud esperada de un paseo aleatorio sobre el grafo que comienza en el nodo $i$ pasando por el nodo $j$ y volver al nodo $i$ . Sea $P$ denotan la proyección ortogonal contra el vector constante. Sea $L$ denota el laplaciano del grafo.

Entonces $L^\dagger \propto PCP$ .

Porque $L^\dagger$ es semidefinida positiva y $L^\dagger \mathbf 1 = \mathbf 0$ Esto hace que $C$ una matriz de distancia euclidiana, y podemos calcular las entradas utilizando $$ C_{ij} \propto (L^\dagger)_{ii} + (L^\dagger)_{jj} - 2 (L^\dagger)_{ij} ~~.$$ (La constante de proporcionalidad es la suma de todos los grados de los nodos)

Las coordenadas euclidianas obtenidas a partir de $C$ proporcionan una incrustación "espectral" del grafo, a veces similar pero distinta de la típica que utiliza los vectores propios del Laplaciano. Von Luxburg habla de ello en su tutorial sobre agrupación espectral.

Answer 2

Obtuve gran parte de esta intuición leyendo "Online Learning over Graphs" de Herbster et. al. $L^+$ puede considerarse como el núcleo reproductor del espacio de Hilbert H de funciones de valor real sobre los vértices del grafo: $$f: V \to R^n$$ equipado con el producto interior $$\langle f,g \rangle = f^T L g.$$ Dado que f vive en un espacio de Hilbert equipado con un producto interior, podemos utilizar el teorema de la Representación de Riesz para concluir que la evaluación funcional de f en cualquier vértice, $f(v_i)$ al ser un funcional lineal, puede representarse como un producto interno: $$f(v_i)=<K_i,f>=K_iLf.$$ El pseudoinverso $L^+$ satisface esta propiedad, lo que puede comprobarse observando que $$f_i=L^+_iLf_i.$$

Aprendizaje en línea sobre grafos: La pseudoinversa del laplaciano de grafos es un objeto clave en los algoritmos de aprendizaje en línea para grafos. Como es habitual, podemos obtener más intuición sobre el laplaciano de grafos y los objetos matemáticos relacionados utilizando el concepto de conductancia (no es casualidad que la versión continua del laplaciano aparezca en la ecuación del calor). Si pensamos en f como una cierta distribución de calor sobre los nodos (estoy usando distribución aquí en el sentido amplio, de modo que no necesita ser normalizada), podemos pensar en $Lf$ aproximadamente como el flujo inducido en cada uno de los nodos por esa distribución sobre el grafo. Dando un paso más, el teorema del representador, a saber, que $f(v_i)=L^+_iLf$ podría interpretarse como que el calor en cada vértice puede expresarse en términos o derivarse del flujo a través de cada vértice.

Así que cualitativamente podemos decir algunas cosas. Que si L envía una distribución de calor f sobre cada nodo a un flujo a través de cada vértice, entonces $L^+$ envía alguna definición de flujos sobre el gráfico de vuelta a alguna distribución de calor que lo hubiera inducido. Nótese que, intuitivamente, si el grafo está desconectado esta distribución no debería ser única, ya que las constantes arbitrarias añadidas a las distribuciones en cada una de las componentes conectadas no afectarán al flujo inducido a través del grafo. Matemáticamente, esto se afirma observando que $$L^+=L^{-1}$$ si todos los valores propios de L son distintos de cero, que es exactamente cuando el grafo está conectado.

Volviendo a la aplicación de aprendizaje en línea, podemos utilizar la fila i-ésima de $L^+$ como sigue. Primero tenemos conjeturas para todos los nodos. A continuación, actualizamos nuestras conjeturas con el conocimiento de ciertos valores (utilizando la proyección, por ejemplo) y deseamos saber cómo afecta esta actualización a nuestra conjetura para el vértice i. Para ello, traducimos nuestra "distribución de calor" actualizada a un flujo actualizado a través de todos esos nodos, calculando $Lf$ . A continuación, utilizando este flujo actualizado, $L^+_iLf=<L^+_i,f>$ nos indicará la i-ésima componente de la distribución que habría producido este nuevo flujo. Es decir, es una estimación actualizada del valor en el vértice i.

EDITAR:

También pasé por alto el hecho de que el "producto interior" no es en realidad un verdadero producto interior como se ha dicho, ya que si $f^*$ es un vector propio de L correspondiente a un valor propio de 0, entonces $<f^*,f^*>=0$ . Por lo tanto, debemos restringir nuestras funciones para que estén en el subespacio de H abarcado por los vectores propios que tienen valores propios distintos de cero. En términos de la analogía del calor, esto significa que sólo podemos mirar a las distribuciones de calor que inducen algún flujo sobre el gráfico (más el vector cero, por supuesto) con el fin de tener un espacio de producto interno real.

Answer 3

La respuesta de Eugene Scvarts puede ampliarse utilizando el documento El análisis de componentes principales de un gráfico, y sus relaciones con la agrupación espectral por Marco Saerens Francois Fouss Luh Yen y Pierre Dupont.

Este trabajo muestra que el análisis de componentes principales con la pseudoinversa Laplaciana como matriz de covarianza conserva al máximo la distancia de conmutación. Así, la pseudoinversa de Laplacian es una matriz de covarianza para el gráfico.

Obsérvese que esta interpretación también ofrece una forma alternativa de entender la agrupación espectral, como se explica en Tutorial sobre agrupación espectral por Ulrike von Luxburg.