👨‍👧‍👧 👆🏽 💏 グラフニューラルネットワークの代表的な電力制約と一般化誤差の推定 😙 📠 🥫

現在、グラフニューラルネットワークの研究における傾向の1つは、そのようなアーキテクチャの動作の分析、核法との比較、複雑さの評価、および一般化能力です。これはすべて、既存のモデルの弱点を理解するのに役立ち、新しいモデルのためのスペースを作成します。

この作業は、グラフニューラルネットワークに関連する2つの問題を調査することを目的としています。最初に、著者は、構造は異なるが、単純なGNNとより強力なGNNの両方で区別できないグラフの例を示します。次に、VC境界よりも正確にグラフニューラルネットワークの一般化エラーを制限しました。

前書き

グラフニューラルネットワークは、グラフを直接操作するモデルです。それらはあなたが構造についての情報を考慮に入れることを可能にします。一般的なGNNには、順次適用される少数のレイヤーが含まれ、反復ごとに頂点表現が更新されます。人気のあるアーキテクチャの例：GCN、GraphSAGE、GAT、GIN。

GNNアーキテクチャの頂点埋め込みを更新するプロセスは、次の2つの式で要約できます。

$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} \右）、$

ここAGGは通常置換（の機能不変である合計、平均、最大等）、COMBINE頂点およびその近傍の表現を組み合わせた関数です。

ノードAの例を使用した2層GNNの計算ツリー。出典：https：//eng.uber.com/uber-eats-graph-learning/

より高度なアーキテクチャでは、エッジフィーチャ、エッジ角度などの追加情報が考慮される場合があります。

この記事では、グラフ分類問題のGNNクラスについて説明します。これらのモデルは次のように構成されています。

まず、頂点はグラフ畳み込みのLステップを使用して埋め込むことができます
(, 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 , , , , $\角度A_1B_1C_1$ $\角度\下線{A} _1 \下線{B} _1 \下線{C} _1$ .

DimeNet

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

GNN

. , , .

GNN, :

DimeNet
message- $m_ {uv} ^ {\左（l \右）}$ $\ 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.

. $\ベータ$ $\ lVert \ beta \ rVert_2 \ le B _ {\ beta}$ .

$f \左（G \右）$ - 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 \左（G \右）\右）$ - , $p \左（f \左（G \右）、y \右）<0$ .