😳 🌀 💇🏿 Restricciones de potencia representativas y estimación de errores de generalización para redes neuronales de gráficos 💜 🎡 🙂

En la actualidad, una de las tendencias en el estudio de las redes neuronales de grafos es el análisis del funcionamiento de dichas arquitecturas, la comparación con los métodos nucleares, la evaluación de la complejidad y la capacidad de generalización. Todo esto ayuda a comprender los puntos débiles de los modelos existentes y crea espacio para otros nuevos.

El trabajo tiene como objetivo investigar dos problemas relacionados con las redes neuronales gráficas. En primer lugar, los autores dan ejemplos de gráficos que tienen una estructura diferente, pero que no se pueden distinguir para GNN simples y más potentes . En segundo lugar, limitaron el error de generalización para las redes neuronales de gráficos con mayor precisión que los límites de VC.

Introducción

Las redes neuronales gráficas son modelos que funcionan directamente con gráficas. Le permiten tener en cuenta información sobre la estructura. Un GNN típico incluye una pequeña cantidad de capas que se aplican secuencialmente, actualizando las representaciones de vértices en cada iteración. Ejemplos de arquitecturas populares: GCN , GraphSAGE , GAT , GIN .

El proceso de actualización de las incrustaciones de vértices para cualquier arquitectura GNN se puede resumir mediante dos fórmulas:

$a_v ^ {t + 1} = AGG \ left (h_w ^ t: w \ in \ mathcal {N} \ left (v \ right) \ right) \\ h_v ^ {t + 1} = COMBINAR \ left (h_v ^ t, a_v ^ {t + 1} \ right),$

donde AGG suele ser una función invariante a las permutaciones ( suma , media , max , etc.), COMBINE es una función que combina la representación de un vértice y sus vecinos.

Árbol de cálculo para GNN de dos capas utilizando el ejemplo del nodo A. Fuente: https://eng.uber.com/uber-eats-graph-learning/

Las arquitecturas más avanzadas pueden considerar información adicional, como características de borde, ángulos de borde, etc.

El artículo considera la clase GNN para el problema de clasificación de gráficos. Estos modelos están estructurados así:

Primero, los vértices se pueden incrustar usando L pasos de convoluciones de gráficos
(, sum, mean, max)

GNN:

(LU-GNN). GCN, GraphSAGE, GAT, GIN
CPNGNN, , 1 d, d - ( port numbering)
DimeNet, 3D-,

LU-GNN

G G LU-GNN, , , readout-, . CPNGNN G G, .

CPNGNN

, “” , CPNGNN .

S₈ S₄ , , ( ), , , CPNGNN readout-, , . , .

CPNGNN G₂ G₁. , DimeNet , , , , $\ ángulo A_1B_1C_1$ $\ ángulo \ subrayado {A} _1 \ subrayado {B} _1 \ subrayado {C} _1$ .

DimeNet

DimeNet G₄ , G₃, . , . , G₄ G₃ S₄ S₈, , , DimeNet S₄ S₈ .

GNN

. , , .

GNN, :

DimeNet
message- $m_ {uv} ^ {\ left (l \ right)}$ $\ Phi_ {uv}$ $\ underline {m} _ {uv} ^ {\ left (l \ right)} = \ underline {f} \ left (m_ {uv} ^ {\ left (l \ right)}, \ Phi_ {uv} \ right )$
$\ left (c_v \ left (i \ right), t_ {i, v} \ right)$ , c - i- v, t - .

:

$h_{v}^{\left( l + 1 \right)} = f \left( h_{v}^{\left( l \right)}, \underline{m}_{c_v\left( 1 \right)v}^{\left( l \right )}, t_{1, v}, ..., \underline{m}_{c_v\left( d \left( v \right ) \right)v}^{\left( l \right )}, t_{ d \left( v \right ), v} \right )$
readout-

: LU-GNN,

$h_v^{l + 1} = \phi \left( W_1x_v + W_2 \rho \left( \sum_{u \in \mathcal{N} \left( v \right)} g\left( h_u^l \right)\right) \right),$

$\phi,\ g,\ \rho$ - , x_v - v, , $\rho \left(0\right) = 0,\ \forall v: \lVert x_v \rVert_2 \le B_x,\ \forall x \in \mathbb{R}^r: \lVert \phi \left( x \right ) \rVert_{\infty} \le b < \infty,\ \phi\left( 0 \right ) = 0,\ g\left( 0 \right ) = 0$ . , $\phi,\ g,\ \rho$ $C_{\phi},\ C_{g},\ C_{\rho}$ , $\lVert W_1 \rVert_2 \le B_1,\ \lVert W_2 \rVert_2 \le B_2$ . $W_1,\ W_2,\ \phi,\ g,\ \rho$ GNN.

. $\beta$ $\lVert \beta \rVert_2 \le B_{\beta}$ .

$f\left(G\right)$ - GNN $y \in \{0, 1\}$ , $p \ left (f \ left (G \ right), y \ right) = y \ left (2f \ left (G \ right) - 1 \ right) + \ left (1 - y \ right) \ left (1 - 2 f \ izquierda (G \ derecha) \ derecha)$ - , $p \ left (f \ left (G \ right), y \ right) <0$ .

, $a = -p \ left (f \ left (G \ right), y \ right)$ , $\ mathbb {I} \ left [\ right]$ - :

$pérdida _ {\ gamma} \ left (a \ right) = \ mathbb {I} \ left [a> 0 \ right] + (1 + \ frac {a} {\ gamma}) \ mathbb {I} \ left [a \ in \ left [\ gamma, 0 \ right] \ right].$

GNN $\ {G_j, y_j \} _ {j = 1} ^ m$ :

$\ hat {\ mathcal {R}} \ left (f \ right) = \ frac {1} {m} \ sum_ {j = 1} ^ m pérdida _ {\ gamma} \ left (-p \ left (f \ left (G_j \ derecha), y_j \ derecha) \ derecha)$

, , , , GNN . , (GNN, ), , , .

, :