🕝 🤵🏼 💩 Repräsentative Leistungsbeschränkungen und Verallgemeinerungsfehlerschätzung für graphische neuronale Netze 🚶🏼 👨🏼‍🌾 🐿️

Gegenwärtig ist einer der Trends bei der Untersuchung grafischer neuronaler Netze die Analyse der Funktionsweise solcher Architekturen, der Vergleich mit nuklearen Methoden, die Bewertung der Komplexität und die Verallgemeinerungsfähigkeit. All dies hilft, die Schwächen bestehender Modelle zu verstehen und schafft Raum für neue.

Die Arbeit zielt darauf ab, zwei Probleme zu untersuchen, die mit graphischen neuronalen Netzen verbunden sind. Zunächst geben die Autoren Beispiele für Diagramme, die sich in ihrer Struktur unterscheiden, jedoch sowohl für einfache als auch für leistungsfähigere GNNs nicht zu unterscheiden sind . Zweitens haben sie den Generalisierungsfehler für graphneurale Netze genauer als die VC-Grenzen begrenzt.

Einführung

Graphneurale Netze sind Modelle, die direkt mit Graphen arbeiten. Mit ihnen können Sie Informationen über die Struktur berücksichtigen. Ein typisches GNN enthält eine kleine Anzahl von Schichten, die nacheinander angewendet werden, wobei die Scheitelpunktdarstellungen bei jeder Iteration aktualisiert werden. Beispiele für gängige Architekturen: GCN , GraphSAGE , GAT , GIN .

Der Prozess der Aktualisierung von Vertex-Einbettungen für jede GNN-Architektur kann durch zwei Formeln zusammengefasst werden:

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

wo AGG üblicherweise eine Funktion invariant Permutationen ist ( Summe , Mittelwert , max etc.), COMBINE ist eine Funktion, kombiniert die Darstellung eines Scheitels und seine Nachbarn.

Berechnungsbaum für zweischichtiges GNN am Beispiel von Knoten A. Quelle: https://eng.uber.com/uber-eats-graph-learning/

Fortgeschrittenere Architekturen können zusätzliche Informationen wie Kantenmerkmale, Kantenwinkel usw. berücksichtigen.

Der Artikel berücksichtigt die GNN-Klasse für das Diagrammklassifizierungsproblem. Diese Modelle sind wie folgt aufgebaut:

Erstens sind Eckpunkte Einbettungen unter Verwendung von L Schritten von Graphfaltungen
(, 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 , , , , $\ Winkel 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} ^ {\ 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 \ links (f \ links (G \ rechts), y \ rechts) = y \ links (2f \ links (G \ rechts) - 1 \ rechts) + \ links (1 - y \ rechts) \ links (1 - 2 f \ left (G \ right) \ right)$ - , $p \ left (f \ left (G \ right), y \ right) <0$ .

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

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

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

, :