Análisis de principios de la red convolucional de gráficos (GCN)
Graficar redes convolucionales implica dos conceptos muy importantes: gráfico y convolución. El método de convolución tradicional muestra un gran poder en el espacio de datos europeo, pero falla en el espacio de datos no europeo. Una razón importante es que el método de convolución tradicional no puede mantener la "invariancia de traducción" en el espacio de datos no europeo. Para generalizar la convolución a gráficos topológicos con estructuras de datos no euclidianas como Graph, nació GCN. Antes de comprender profundamente los entresijos de GCN: creo que debemos tener una idea de los siguientes conceptos de antemano:
Enlace del artículo Clasificación semisupervisada con redes convolucionales de gráficos
1 Matriz laplaciana de Rapp y sus variantes
Dado un gráfico simple con el número de nodos, es la matriz de grados, es la matriz de adyacencia, entonces la matriz laplaciana se puede expresar de la siguiente manera: <. /p>
1. Transformada de Fourier tradicional
Cuando el objeto de transformación es una variable discreta, calcular la integral equivale a calcular el producto interno, es decir,
Aquí es la función característica del legendario y algo misterioso operador laplaciano (el operador laplaciano es un operador diferencial de segundo orden en el espacio euclidiano, cómo se ve después de quitarle la composición).
¿Por qué dices esto? Esto se debe a que, según la definición general de ecuación característica, es una transformación en sí misma, es un vector característico o función característica y es un valor propio. Tomamos la segunda derivada de la función base, se puede ver que es la función característica de la transformación.
En Graph, la matriz laplaciana se puede descomponer espectralmente (descomposición propia), y la matriz compuesta por sus vectores propios es. Según la definición de la ecuación característica, podemos obtener. Por comparación podemos encontrar que es equivalente a, es equivalente a. Por lo tanto, se puede escribir la transformada de Fourier en Graph
A partir de la idea básica de la transformada de Fourier, la esencia de la transformada de Fourier es convertirla en un conjunto de coordenadas bajo una base ortogonal Representa una transformación lineal. , y las coordenadas son los resultados de la transformada de Fourier. La siguiente figura es el tamaño del componente de proyección en la primera base.
Generalizamos la transformada de Fourier en el Gráfico a la forma matricial mediante la multiplicación de matrices:
es el vector propio del nodo en el Gráfico, y podemos obtener la transformada de Fourier en el Gráfico Formato:
.
Aquí está la transpuesta de la matriz propia compuesta por los vectores propios de la matriz laplaciana de Graph. Entre las excelentes propiedades de la matriz laplaciana, conocemos la composición del vector propio de la matriz laplaciana. matriz, es decir, satisface, por lo que la forma de transformada de Fourier inversa de Graph es, y la forma de matriz es la siguiente:
Hasta ahora hemos extendido la transformada de Fourier tradicional a Graph a través de analogía La transformada de Fourier de . A continuación, usaremos la transformada de Fourier como puente para que Convolution y Graph se diviertan.
En el prefacio, aprendimos sobre el famoso teorema de convolución: la transformada de Fourier de una función convolucional es el producto de su transformada de Fourier, es decir, la convolución de las dos es su transformada de Fourier La transformación inversa de :
Sustituimos la fórmula de la transformada de Fourier en el Gráfico obtenido en el apartado anterior para obtener:
Es el producto de Hamada, que significa multiplicación punto por punto.
Generalmente lo consideramos como la característica de nodo del gráfico de entrada y como un núcleo de convolución entrenable y de parámetros compartidos para extraer las características espaciales del gráfico topológico. Para comprender mejor el núcleo de convolución, reescribimos la fórmula anterior como:
Quizás algunas personas tengan dudas sobre la transformación de la fórmula anterior. La prueba es realmente muy simple. Si está interesado, consulte. la respuesta de este encuestado en GCN Prueba de ecuación - Zhihu
Hasta ahora, hemos derivado el prototipo de GCN.
1. GCN de primera generación
El núcleo de la operación de convolución es un núcleo de convolución que se puede entrenar y comparte parámetros, por lo que el GCN de primera generación convierte directamente la fórmula anterior en diagonal. Los elementos en se reemplazan con parámetros. Primero se inicializa la asignación y luego se ajustan los parámetros propagando el error hacia atrás.
Entonces el GCN de primera generación quedó así:
Es el vector de representación de las características de cada nodo en el Gráfico y es la salida de cada nodo después de la convolución del GCN. Cada nodo en el Gráfico debe pasar por la convolución del núcleo de convolución para extraer su espacio topológico correspondiente y luego propagarse a la siguiente capa a través de la función de activación.
Las deficiencias del GCN de primera generación también son obvias, e incluyen principalmente los siguientes puntos:
2. El GCN de segunda generación
Frente a los parámetros de el GCN de primera generación tiene demasiadas deficiencias y el GCN de segunda generación ha realizado mejoras específicas. Dado que la transformada de Fourier en Graph es una función de valores propios, también se puede escribir como, usando un polinomio de orden k para mejorar el núcleo de convolución:
Sustituyéndolo se puede obtener:
Entonces el GCN de segunda generación se ve así:
Se puede ver que el resultado final de la simplificación del GCN de segunda generación no requiere descomposición matricial y transforma directamente la matriz laplaciana. Los parámetros son , y k es generalmente mucho menor que la cantidad de nodos en Graph. Por lo tanto, en comparación con el GCN de primera generación, la cantidad de parámetros del GCN de segunda generación es significativamente menor que la del GCN de primera generación. lo que reduce la complejidad del modelo. Para los parámetros, primero se inicializan y luego se actualizan según la propagación del error hacia atrás. Pero aún es necesario calcularlo, y la complejidad del tiempo sí lo es.
Además, sabemos que para la k-ésima potencia de una matriz, podemos conectar los nodos al nodo central k-hop , es decir, si el elemento en es 0 significa Gráfico Si un nodo en puede llegar a otro nodo después de k saltos. El k aquí en realidad representa el tamaño del campo receptivo del núcleo de convolución. El nodo central se actualiza agregando los nodos vecinos. dentro del k-hop de cada nodo central. La representación característica de, y el parámetro es el peso del k-ésimo vecino.
Continuará.
1. En la convolución del gráfico de dominio espectral, realizamos una descomposición propia en la matriz laplaciana del gráfico. La descomposición de características en el espacio de Fourier nos ayuda a comprender la estructura del subgrafo subyacente. ChebyNet y GCN son arquitecturas típicas de aprendizaje profundo que utilizan convolución de dominio espectral.
2. La convolución espacial actúa sobre la vecindad del nodo. Agregamos los vecinos k-hop del nodo para obtener la representación de características del nodo. La convolución en el dominio espacial es más simple y eficiente que la convolución en el dominio espectral. GraphSAGE y GAT son representantes típicos de la convolución espacial.
Referencias
1. /
3. /yyl424525/article/details/100058264