👨🏼‍💼 🛠️ 🍬 Contraintes de puissance représentatives et estimation des erreurs de généralisation pour les réseaux de neurones graphiques 👩🏽‍🤝‍👨🏾 🍕 🗓️

À l'heure actuelle, l'une des tendances dans l'étude des réseaux de neurones graphiques est l'analyse du fonctionnement de telles architectures, la comparaison avec les méthodes nucléaires, l'évaluation de la complexité et la capacité de généralisation. Tout cela aide à comprendre les faiblesses des modèles existants et crée de l'espace pour de nouveaux.

Le travail vise à étudier deux problèmes liés aux réseaux de neurones graphiques. Premièrement, les auteurs donnent des exemples de graphes dont la structure est différente, mais impossible à distinguer pour les GNN simples et plus puissants . Deuxièmement, ils ont lié l'erreur de généralisation pour les réseaux de neurones graphiques plus précisément que les limites VC.

introduction

Les réseaux de neurones graphiques sont des modèles qui fonctionnent directement avec des graphiques. Ils vous permettent de prendre en compte des informations sur la structure. Un GNN typique comprend un petit nombre de couches qui sont appliquées séquentiellement, mettant à jour les représentations de sommets à chaque itération. Exemples d'architectures populaires: GCN , GraphSAGE , GAT , GIN .

Le processus de mise à jour des plongements de sommets pour toute architecture GNN peut être résumé par deux formules:

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

où AGG est généralement une fonction invariante aux permutations ( somme , moyenne , max etc.), COMBINE est une fonction qui combine la représentation d'un sommet et de ses voisins.

Arbre de calcul pour GNN à deux couches utilisant l'exemple du nœud A. Source: https://eng.uber.com/uber-eats-graph-learning/

Les architectures plus avancées peuvent prendre en compte des informations supplémentaires telles que les caractéristiques des bords, les angles des bords, etc.

L'article considère la classe GNN pour le problème de classification des graphes. Ces modèles sont structurés comme ceci:

Premièrement, les sommets peuvent être intégrés en utilisant L étapes de convolutions de graphe
(, 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 , , , , $\ angle A_1B_1C_1$ $\ angle \ underline {A} _1 \ underline {B} _1 \ underline {C} _1$ .

DimeNet

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

GNN

. , , .

GNN, :

DimeNet
message- $m_ {uv} ^ {\ gauche (l \ droite)}$ $\ Phi_ {uv}$ $\ underline {m} _ {uv} ^ {\ left (l \ right)} = \ underline {f} \ left (m_ {uv} ^ {\ left (l \ right)}, \ Phi_ {uv} \ right )$
$\ gauche (c_v \ gauche (i \ droite), t_ {i, v} \ droite)$ , 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 \ gauche (f \ gauche (G \ droite), y \ droite) = y \ gauche (2f \ gauche (G \ droite) - 1 \ droite) + \ gauche (1 - y \ droite) \ gauche (1 - 2 f \ gauche (G \ droite) \ droite)$ - , $p \ gauche (f \ gauche (G \ droite), y \ droite) <0$ .

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

$loss _ {\ 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 loss _ {\ gamma} \ left (-p \ left (f \ left (G_j \ droite), y_j \ droite) \ droite)$

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

, :