Weilingsi チームは、グラフ同型性の下での同変性と高い計算効率を備えた「自然グラフ ネットワーク」メッセージ パッシング メソッドを提案しました。

最近、ウェリングスチームによる研​​究では、グラフの局所的な対称性を研究することで新しいアルゴリズムが提案されました。このアルゴリズムは、異なるエッジで異なるカーネルを使用するため、ネットワークはローカルおよびグローバルのグラフ同型性において同変となり、表現しやすくなります。

一般的に言えば、従来のニューラル メッセージ パッシング アルゴリズムはメッセージの順列に対して不変であり、したがって情報がネットワーク内をどのように流れるかは考慮しません。

最近、アムステルダム大学の機械学習教授であり、クアルコムテクノロジーの副社長であるマックス・ウェリング氏のチームが、グラフの局所的な対称性を研究することで、より一般的なアルゴリズムを提案しました。このアルゴリズムは、異なるエッジで異なるカーネルを使用するため、ネットワークはローカルおよびグローバルのグラフ同型性において等しい変化を示し、表現が容易になります。

論文アドレス: https://arxiv.org/abs/2007.08349v1

具体的には、研究者らは初等的カテゴリー理論を用いて、多くの明示的に同変なニューラルネットワークを自然グラフネットワーク（NGN）として形式化し、そのカーネルが2つの関数間の自然な変換であることを示した。

また、複数のベンチマークで優れたパフォーマンスを実現する等変メッセージ ネットワークを使用してパラメーター化された自然ネットワークのグラフ例も提供します。

次に、この論文の具体的な内容を見ていきましょう。

自然グラフネットワーク

グラフ上にニューラル ネットワークを構築するためのまったく異なる戦略は、グラフ畳み込みニューラル ネットワークまたはメッセージ パッシング ネットワークを使用することです (Kipf および Welling、2016 年、Gilmer ら、2017 年)。研究者たちは、このタイプの方法をローカルグラフネットワーク (LIGN) と呼んでいます。

最も単純な形式では、各ノードの特徴 v_p を持つこれらの変換グラフ信号 v は、以下の式 2 に示すように、単一の共有線形変換 W を使用してグラフのエッジに渡されます。

ここで、E はグラフのエッジ セットです。このような畳み込みアーキテクチャは、線形変換を計算する計算コストがエッジの数に比例して増加するため、グローバル アプローチよりも計算効率が優れていることがよくあります。

既存のメッセージ パッシング ネットワークの限界を克服し、同時に高い計算効率を維持するため、研究者らは、重みがグラフ構造によって決定される新しいタイプのメッセージ パッシング ネットワークを提案しました。

つまり、研究者らは式 2 を改良し、次の式 3 を得ました。

線形カーネルは各グラフの各エッジで異なります。明らかに、そのようなカーネルのすべてが等価ネットワークにつながるわけではありません。次に、研究者らはカーネル空間を定義する方法を詳しく紹介しました。

グローバルおよびローカルグラフ対称性

研究者はグラフGのノードN_Gを表すために整数配列を使用した。つまり、

グラフ内のエッジは整数ペアで表され、エッジの集合はε(G)なので、エッジ(p,q)∈ε(G)となります。

グラフ G と G' は、矢印表記 p→q を持つ有向グラフである場合に類似または同型です。言い換えると、グラフ同型性はノードをノードに、エッジをエッジにマッピングします。同型性の特殊な種類は自己同型性であり、ノードの順序のみが変わり、エッジのセットは同じままです。定義により、グループ内の自己同型は自己同型群と呼ばれます。

特徴

等変ニューラル ネットワークが表現可能なカーネルを持つためには、ノード p の特徴ベクトル v_p を変換する必要があります。これは、ノード p が固定メッセージ パッシング ネットワークのように変更されないままになるのではなく、何らかのグローバル対称性によって p' にマッピングされるためです。研究者らは、局所ノード対称性の下での固有ベクトルの変換規則を再定義した。

局所的等価性

エッジ (p,q) 上のカーネルは、p 点のベクトル空間 V_p から q 点のベクトル空間 V_q へのマッピングです。カーネルの局所同値性は、局所同型辺の空集合が存在する場合、

の場合、これを行うと、次の 2 つのケースと同じ効果が得られます。

信号をpからp'に渡し、カーネルK^(G')_p'q'を適用します。

まずカーネル K^G_pq を適用し、次に q を q' に変換します。

詳細は以下の図 6 に示されています。

したがって、次の式4が必要になります。

グラフニューラルネットワークのメッセージパラメータ化

同値性は、同型近傍を持つエッジ間で重みを共有することのみを必要とするため、定理では、各同型クラスのエッジ近傍の分類パラメータを使用して、同値カーネルの空間をパラメータ化できます。

実際、ソーシャル グラフなどのグラフは非常に異質であり、同型のエッジはほとんどなく、重みを共有する必要もほとんどないため、学習と一般化も困難です。

これはメッセージpをqに送信することで解決できます。

関数として再解釈する

ここで、G_pq はエッジ近傍、v_p は点 p の固有値（v_p 内で非線形に一般化可能）、K はメッセージ ネットワークに基づくニューラル ネットワークです。

下の図 7 は、メッセージ パッシング プロセスをグラフ畳み込みとして示しています。

カテゴリー理論

機械学習で広く使用されている式 1 などのグローバル対称性に対する同変制約は、最近、ローカル対称性またはゲージ対称性に拡張されました。

しかし、これらの形式にはグラフの動的な局所対称性が含まれていないため、より一般的な言語が必要です。

この目的のために、研究者らは、もともと代数的位相幾何学から開発され、最近ではより広範囲の問題のモデリングツールとして使用されているカテゴリー理論を使用しました。カテゴリー理論の構造は、自然ネットワークと呼ばれる同変メッセージ パッシング ネットワークを構築するための優れたフレームワークを提供し、研究者はこれを「自然ネットワーク」と呼んでいます。

実験

20面体MNIST

この方法のグローバル対称性との等価性を実験的に検証し、不変メッセージ パッシング ネットワーク (GCN) での表現可能性を高めるために、二十面体上に投影された MNIST を分類します。

以下の表 1 の最初の列は、固定投影でのトレーニングとテストの精度を示しています。 2 番目の列では、研究者はランダムな 20 面体対称変換による投影で同じモデルをテストしました。

結果は、NGN が GCN よりも優れていることを示し、同等の精度はモデルが完全に等変であることを示しています。

グラフ分類

研究者らは、2015年にYanardag氏とVishwanathan氏によって提案された5つの生物学的データセットと3つのソーシャルグラフを含む8つの標準グラフ分類ベンチマークでGCNメッセージパラメータ化を使用してモデルを評価しました。

具体的には、研究者らは 10 倍のクロス検証法を使用し、以下の表 2 に示すように、10 倍の場合に最高の平均精度を示しました。

実験結果によると、ほとんどのデータセットにおいて、本研究で提案された局所等変法の性能は、全体等変法の性能に劣らないことが示されています。