[李宏毅2020ML / DL] P18-19グラフニューラルネットワーク| NN4G、DCNN、MoNet、GraphSAGE、GAT、GIN、ChedNet、GCN

P18 19 Graph Neural Network Nn4g

私は2年間のMLの経験があります。この一連のコースは、主に欠陥をチェックするために使用され、私が知らないいくつかの詳細を記録します。

誰かがすでにメモを取っています（非常に難しい、強くお勧めします）： https://github.com/Sakura-gh/ML-notes

このセクションの対応する注記：なし

概要

• 前書き
• ロードマップ
• タスク、データセット、およびベンチマーク
• 空間ベースのGNN
• グラフ信号処理とスペクトルベースのGNN
• グラフの生成
• NLPのGNN

畳み込みを使用してノードを特徴空間に埋め込む方法は？

2つのアイデアがあります：

• 解決策1：畳み込み（コアレーション）の概念をグラフに一般化する>>空間ベースの畳み込み
• 解決策2：信号処理における畳み込みの定義に戻る>>スペクトルベースの畳み込み

ロードマップ

タスク、データセット、およびベンチマーク

タスク：

• 半教師ありノード分類
• 回帰
• グラフ分類
• グラフ表現学習
• リンク予測
  
  
  
  共通データセット：
• CORA：引用ネットワーク。 2.7kノードと5.4kリンク
• TU-MUTAG：平均18ノードの188分子

空間ベースのGNN

上の画像は、空間ベースのGNNの一般的な考え方を示しており、隣接ノードを使用して畳み込みを更新しています：

• 最初に集計
• もう一度読みます。

NN4G（グラフ用ニューラルネットワーク）

NN4Gの場合：

• まず、入力レイヤーの埋め込み
• その後、ノードの隣接ノードを追加し、重みを掛けて、独自の機能を追加します（wˉ1⋅x3 bar {w} _1 cdot x_3にˉ1。⋅バツ3。）。
• 次に、（下の図に示すように）読み取り、各レイヤーの特徴を合計し、平均を取り、次に異なる重みを掛けて、それらを追加します。

DCNN（拡散-畳み込みニューラルネットワーク）

DCNNの場合、最初のレイヤーの各ノードを次のように処理します。

• 次のようにh 3 0 h_3 ^ 0h30。、各固有値を平均化するために、オブジェクトはすべてであり、現在のノードですPoint at distance 1。

2番目のレイヤーの場合、距離は2です。

h 3 0 = w 3 0 M E A N（d（3、⋅）= 1）h_3 ^ 0 = w_3 ^ 0 MEAN（d（3、 cdot）= 1）h30。=に30。MISにN（（d（（3、⋅）。=1）。
h 3 1 = w 3 1 M E A N（d（3、⋅）= 2）h_3 ^ 1 = w_3 ^ 1 MEAN（d（3、 cdot）= 2）h31。=に31。MISにN（（d（（3、⋅）。=二）。

その後、各レイヤーについて、ノード固有値のベクトル点が行ごとに行列に積み上げられます。

そのロードアウトを図に示します。

MoNET（混合モデルネットワーク）

• ノードの「距離」に関する測定値を定義します
• 隣接する特徴を単純に合計（平均化）するのではなく、加重和（平均）を使用します。

前のモデルとの違い：このモデルは、各ネイバーの重要性が異なると見なし、ネイバー間の重みを考慮します。

ここでは、「度」を使用して、隣接するエッジ間のエッジの重みを定義します。u（x、y）u（x、y）u（（バツ、Y）。。

GraphSAGE（サンプルとaggreGatE）

• トランスダクティブ設定とインダクティブ設定の両方で機能します
• GraphSAGEは、ネイバーからノード機能を埋め込む方法を学習します

ネイバーを平均に加算すること、機能を最大プーリングとして使用すること、および順序の影響を排除するためにLSTMにさまざまな順序を入力することについて話すことに加えて。

GAT（グラフアテンションネットワーク）

• 入力：ノード機能h = {h⃗1、h⃗2、…、h⃗N}、h⃗i∈RF mathbf {h} = left { vec {h} _ {1}、 vec {h} _ { 2}、 ldots、 vec {h} _ {N} right }、 vec {h} _ {i} in mathbb {R} ^ {F}h={{h 1。、h 二。、..。、h N。}、h 私。∈RF
• エネルギーを計算する：eij = a（Wh⃗i、Wh⃗j）e_ {ij} = a left（ mathbf {W} vec {h} _ {i}、 mathbf {W} vec {h} _ { j} right）です私j。=に（（にh 私。、にh j。）。
• 注意スコア（隣人以上）

αij=exp⁡（LeakyReLU（a→T [Wh⃗i∥Wh⃗j]））∑k∈Niexp⁡（LeakyReLU（a→T [Wh⃗i∥Wh⃗k]）） alpha_ {ij} = frac { exp left（ text {LeakyReLU} left（ overrightarrow { mathbf {a}} ^ {T} left [ mathbf {W} vec {h} _ { i} | mathbf {W} vec {h} _ {j} right] right） right）} { sum_ {k in mathcal {N} _ {i}} exp left（ text {LeakyReLU} left（ overrightarrow { mathbf {a}} ^ {T} left [ mathbf {W} vec {h} _ {i} | mathbf {W} vec {h} _ {k} right] right） right）}a私j。=∑に∈N私。。exp（（LeakyReLU（（に T[にh 私。∥にh に。]）。）。exp（（LeakyReLU（（に T[にh 私。∥にh j。]）。）。。

ノードを計算するには、最初に異なる隣接ノードの注意を計算し、2つのノードのエネルギーを計算します。これは、重み付けの重みとして使用されます。以下に示すように。

このGATはより一般的に使用されます

GIN（グラフ同型ネットワーク）

• GNNは、WL同型テストと同じくらい強力です。
• 理論的な証明が提供されました

この研究はいくつかの理論的証拠を提供し、結論は次のとおりです。

• 更新するときは、次の式を使用するのが最適ですh v（k）h_v ^ {（k）}hv（（に）。。更新（ネイバーを追加してから、独自の倍数を追加）
• 平均または最大の代わりに合計

hv（k）=MLP⁡（k）（（1 + ϵ（k））⋅hv（k − 1）+ ∑u∈N（v）hu（k − 1））h_ {v} ^ {（k） } = operatorname {MLP} ^ {（k）} left（ left（1+ epsilon ^ {（k）} right） cdot h_ {v} ^ {（k-1）} + sum_ { u in mathcal {N}（v）} h_ {u} ^ {（k-1）} right）hv（（に）。。=MLP（（に）。⎝⎛。（（1+ϵ（（に）。）。⋅hv（（に-1）。。+u∈N（（v）。∑。hu（（に-1）。。⎠⎞。

平均または最大の代わりに合計を使用するのはなぜですか？ 次の図は、平均と最大のいくつかの反例を示しています。

グラフ信号処理とスペクトルベースのGNN

グラフを畳み込むことができることを願っています。一般的な考え方は、グラフとフィルターを変更して、2つを直接乗算できるようにすることです。This involves some changes in the signal and system courses.

信号とシステム

N-dimベクトル空間

信号は、N次元ベクトルのセットと見なすことができます。線形空間のこのベクトルは、次の複数の基底ベクトルで構成されていますsynthesis

A⃗= ∑ k = 1 N a k v ^ k vec {A} = sum_ {k = 1} ^ N a_k hat {v} _kに =に=1∑N。にに。v^に。

必要な場合analysis特定の基底ベクトルとは、内積を行う必要があります。

a j = A ^⋅v^ j a_j = hat {A} cdot hat {v} _jにj。=に^⋅v^j。

さらに、基底ベクトルが直交（直交）であると仮定します。

v ^i⋅v^ j =δij hat {v} _i cdot hat {v} _j = delta_ {ij}v^私。⋅v^j。=d私j。

フーリエ級数表現

時間領域では、sinとcosの基底ベクトルが一般的に使用されます。

周期信号の場合、フーリエ級数に展開できます。
x（t）= ∑ k =-∞∞anyω0t= ∑ k =-∞∞akϕ k（t）x（t）= sum_ {k =- infty} ^ { infty} a_ {k } e ^ {jk omega_ {0} t} = sum_ {k =- infty} ^ { infty} a_ {k} phi_ {k}（t）バツ（（t）。=に=-∞∑∞。にに。ですjにω0。t=に=-∞∑∞。にに。ϕに。（（t）。

a k ϕ k（t）a_ {k} non_ {k}（t）にに。ϕに。（（t）。：j次高調波成分

計算にはさまざまな方法がありますa k a_kにに。サイズ。

2つのドメインでの信号表現

時間領域ベース

A⃗= ∑ iaiv⃗i vec {A} = sum_ {i} a_i vec {v} _iに =私∑。に私。v 私。

X（T）=∫ - ∞∞X（τ）δ（T - τ）DτX（T）= INT _ { - inftyの} ^ { inftyの} X（）デルタ（T- ） D バツ（（t）。=∫-∞∞。バツ（（τ）。d（（t-τ）。dτ

さらに、同じグループの信号を異なる基準で表すこともできます。これは、次の形式で記述できます。

x（t）= 12π∫−∞∞X（jω）ejωtdωx（t）= frac {1} {2 pi} int ^ { infty} _ {- infty} X （j omega）e ^ {j omega t} d omegaバツ（（t）。=二円周率1。∫-∞∞。バツ（（jω）。ですjωtdω

。 。 。 = ∑ k（。。。b k）u⃗k... = sum_k（。。。b_k） vec {u} _k。。。=に∑。（（。。。bに。）。u に。

周波数領域ベース

A⃗= ∑ kbku⃗k vec {A} = sum_ {k} b_k vec {u} _kに =に∑。bに。u に。

x（t）= 12π∫−∞∞X（jω）ejωtdωx（t）= frac {1} {2 pi} int ^ { infty} _ {- infty} X （j omega）e ^ {j omega t} d omegaバツ（（t）。=二円周率1。∫-∞∞。バツ（（jω）。ですjωtdω

X（T）=∫ - ∞∞X（τ）δ（T - τ）DτX（T）= INT _ { - inftyの} ^ { inftyの} X（）デルタ（T- ） D バツ（（t）。=∫-∞∞。バツ（（τ）。d（（t-τ）。dτ

。 。 。 = ∑ i（。。。a i）v⃗i... = sum_ {i}（。。。a_i） vec {v} _i。。。=私∑。（（。。。に私。）。v 私。

フーリエ変換

フーリエ変換は、その基礎を分析するプロセスを指します。

スペクトルグラフ理論

上記のように、グラフ理論では、臨界行列と次数行列を含む3つの行列を宣言する必要があります。各ノードには独自のsignal。があります。

各ノードのベクトルまたは定数は、このノードの信号として理解できます。

Tulaplace's expansion theorem、can Positive semi-definite matrix L分割に基づく。例は次のとおりです。

頂点ドメイン信号

最初にDとAに基づいてLを計算し、次にLをに分割しますΛラムダΛ対U UU。

In U, the number of rows represents the node the number of columns represents the 'frequency' in the signal.

下図のように描きます。

なぜこのように「頻度」を理解するのですか？議論を始めましょう。

離散時間フーリエ基底

信号では、周波数が高いほど、2つの隣接するポイント間の信号の変化が大きくなります。

頂点周波数の解釈

最終的なLf値は、実際にはそれ自体のエネルギーの倍数から隣接するエネルギーの合計を引いたものであることがわかります。

次の図に示すように、このエネルギーは意味をなすために2乗する必要があります。

信号エネルギーの変化は、実際にはノードが滑らかであるかどうかを表していることがわかります。

元の画像に戻ると、次のことがわかります。

• いわゆるエネルギー差はλi lambda_iλ私。；
• λ= 0 ラムダ= 0λ=0DC成分の場合DC component。

特別な例：20ノードの折れ線グラフ

この特定の例では、周波数が高いほど、エネルギー差が大きくなることがわかります。

信号のグラフフーリエ変換

上の図に示すように、右側の信号処理と同様に実行しますU T x U ^ T xUTバツの内積演算は、実際には各周波数analysisで実行されます。したがって、スペクトル領域にマッピングされます。

信号の逆グラフフーリエ変換

時間領域に戻る信号処理についても同じことが言えます。

示されているように、Treat the node as a value on the horizontal axis in the time domain, and add up the parts of each frequency。として計算されますx =U⋅x^ x = U cdot hat {x}バツ=U⋅バツ^。

フィルタリングと問題

私たちが構築したものfilterは、ひずみマッピングの頻度にも基づいています。以下に示すように。

実際の計算では、y ^ =gθ（Λ）x ^ 帽子{y} = g_ シータ（ラムダ）帽子{x}Y^。=gθ。（（Λ）。バツ^各周波数のフィルタリングされた値を取得します。

以下に示すように、私たちはついにy ^ 帽子{y}Y^。掛けるU UU、逆フーリエ変換を行い、各ノードに対応する値に戻ります。

トレーニングする最後のパラメーターは、このフィルターの値です。次のように。

しかし、問題は次のとおりです。

• 同様gθ（L）= l o g（I + L）g_ theta（L）= log（I + L）gθ。（（L）。=lまたはg（（私+L）。この関数をフィルター関数として使用する場合、Then the parameter size of the filter will change as the input changes (100,000 nodes, then 100,000 filter parameters)；
• さらに、下の図に示すように、学習したくないことを学習します（gの係数がL N L ^ NLN、その後、すべてのフィルタリングには全体的な状況が含まれます、no Localize Up）。

ChebNet

上記の2つの問題を解決すると、フィルターを修正してローカライズできます。

ただし、この計算時間のコストは高すぎます。

It uses a very magical method, as shown in the figure below, to solve the problem of calculating time cost.

上に示したように、最初にa Chebyshev polynomial多項式関数を宣言します。これに基づいて、g関数を変更します。

関数を多項式関数にラップします。意味は次のとおりです。

関数をラップすることは、多項式を編成することと同じです。上記の高校の数学の問題では、多項式の計算がはるかに簡単になります。

T関数自体の性質に基づいて、次のように導出できます。

上記のように、計算は大幅に簡略化されます。

要約すると、数学的証明に関係なく、私たちが学ばなければならないのはフィルターのθです。

GCN

GCNは最も一般的に使用されており、比較的シンプルで直感的なものです。

GCNの背後にある数学的導出は、上記のとおりです。ここで、

• ChebNetのKを1として扱います
• そして、単純化するために多くの近似を行いました
• そして、より少ないパラメータを追求するために、それは自己設定されたパラメータ間の関係を宣言しますθ=θ0 '=-θ1' theta = theta_0 '=- theta_1'θ=θ0′。=-θ1′。
• そしてa renormalization trickを作りました。

GCNはそれを要約します：

• 隣接ノードを合計してから、オフセットを追加します
• 次に、活性化関数を介して、ニューラルネットワークの次の層が取得されます。

タスク、データセット、ベンチマーク-結果

プレーンなGCNはあまり良くないことがわかります。しかし、いくつかの変種は非常に強力です。




層の数が増え、GCNが悪化しました。

GCNへの適用

GCNの層が多いほど、問題が発生する可能性が高くなることが証明されています。

@inproceedings{ Oono2020Graph, title={Graph Neural Networks Exponentially Lose Expressive Power for Node Classification}, author={Kenta Oono and Taiji Suzuki}, booktitle={International Conference on Learning Representations}, year={2020}, url={https://openreview.net/forum?id=S1ldO2EFPr} }

この問題を解決する方法は？誰かが提案したdrop edge方法：

• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification

グラフの生成

グラフ生成の3つの方法について簡単に説明しました。

概要