畳み込みニューラルネットワークは「グラフ」構造化データを処理できないのですか?この記事でその答えが分かります

この記事で紹介する論文は、ICML2016でのグラフへのCNNの応用に関する論文です。 ICML は機械学習のトップカンファレンスです。この記事の内容「<< グラフ用 CNN の学習>>」も理論的にも実用的にも大きな価値があります。グラフのデータ構造にあまり詳しくない場合は、まずこの記事の最後にある関連する基礎知識の紹介を参照することをお勧めします。

CNN は、コンピューター ビジョン (CV) や自然言語処理などの分野で最先端の成果を達成しています。これらの分野のデータはユークリッド データと呼ぶことができます。CNN はこのデータ構造を効率的に処理し、そこに含まれる特徴表現を探索できます。

いわゆるユークリッドデータとは、グリッド、シーケンスなどに似たデータのことを指します。たとえば、画像は 2D グリッドデータと見なすことができ、音声信号は 1D グリッドデータと見なすことができます。しかし、実際の処理問題には、ソーシャルマルチメディアネットワークデータ、化学組成（Chemical Compound）構造データ、生物学的遺伝子タンパク質（Protein）データ、ナレッジグラフ（Knowledge Graphs）データなど、非ユークリッドデータがまだたくさんあります。このタイプのデータはグラフ構造データに属します。 CNN などのニューラル ネットワーク構造では、このようなデータを効果的に処理できません。したがって、この論文が解決しようとする問題は、CNN を使用してグラフ構造データを効率的に処理する方法です。

この論文で提案されているアルゴリズムは非常に単純で、グラフ構造のデータを CNN が効率的に処理できる構造に変換するというものです。処理プロセスは主に 2 つのステップに分かれています。1. グラフ構造から代表的なノード シーケンスを選択します。2. 選択した各ノードの畳み込み近傍フィールドを見つけます。次にアルゴリズムの詳細を詳しく紹介します。

この論文では、画像を特殊な種類のグラフ、つまり各ピクセルがグラフ内のノードとなるグリッド グラフとして扱います。したがって、この記事の動機は主に、画像に対する CNN の適用を一般的なグラフに一般化したいという願望から来ていると思います。

それではまず、画像における CNN の応用について見てみましょう。図3に示すように、左側の図はニューラルネットワーク層における画像の畳み込み演算処理を示しています。最下層は入力特徴マップ（または元の画像）であり、畳み込み演算によって畳み込み特徴マップとして出力されます（ここでは 3*3 畳み込みカーネル、つまり記事の受容野 = 9 を表します）。図3の畳み込み演算で示されているように、下層の9つのピクセルが重み付けされて上層の1つのピクセルにマッピングされます。図3の右側の図を見ると、左側の図の下層の入力データがグラフの観点から示されています。畳み込みのある領域は、中心ノードとその領域内のノード セットと見なすことができ、最終的に重み付けされて値にマッピングされます。したがって、下部の入力特徴マップは、画像を表すために正方グリッドマップ内の一連のノードを決定し、正規化された近傍マップを構築するものと見なすことができます（この近傍マップは、畳み込みカーネルの領域、つまり受容野です）。

このように説明すると、論文の図 1 に示されているように、4 x 4 の画像は実際には 4 つのノード (図の 1、2、3、4) を持つグラフとして表すことができ、各ノードには畳み込みカーネルと同じサイズの近傍フィールドも含まれます。したがって、この画像の畳み込みは、実際には、これら 4 つのノードで構成されるグラフのフィールドの畳み込みです。次に、一般的なグラフ データの場合、ノードを選択し、関連する固定サイズ (畳み込みカーネルと同じサイズ) のドメインを解決して、CNN 畳み込みを使用してグラフの特徴表現を取得するだけです。

なお、図4(b)は図4(a)のノード近傍を示しており、受容野は畳み込みカーネルと同じ大きさのベクトルに空間位置の順に左から右、上から下の順にマッピングされ、畳み込みが行われる。しかし、一般的な地図帳では、画像内に空間的な位置情報がありません。これは、グラフデータを処理する過程で解決する必要がある問題でもあります。

上記の説明に基づいて、この論文では主に次の 3 つのことを行います。1. 適切なノードを選択する。2. 各ノードの近傍を確立する。3. グラフ表現からベクトル表現への単一のマッピングを確立して、同様の構造的特徴を持つノードがベクトル内の同様の位置にマッピングされるようにする。アルゴリズムは 4 つのステップに分かれています。

1. ノードシーケンスの選択

まず、入力グラフの場合、選択するノードの数を表す幅 w (アルゴリズム 1 で定義) を決定する必要があります。実際には、それは受容野の数です (実際、ここでは、ノード受容野が畳み込まれるたびに、畳み込みのストライド = カーネル サイズになることを意味します)。では、ノードはどのように選択するのでしょうか?

実際、論文ではグラフ内のノードのソートラベルに基づいて選択するように書かれていますが、この記事ではソート方法についての詳しい情報は提供されていません。採用されている主な方法は中心性です。私の個人的な理解では、ポイントが中心的であればあるほど、より重要になります。ここでの中心位置は空間的な概念ではなく、関係におけるポイントの重要性を測定する概念です。簡単な例を挙げて説明しましょう。図 5 に示すように、2 つのグラフは実際には同じグラフを表しています。赤でマークされた 2 つの異なるノードの中心位置関係を比較してみましょう。比較プロセス中に、ノードと他のすべてのノード間の距離関係を計算します。隣接する 2 つのノード間の距離は 1 であると仮定します。

図 5 の左側の赤いノードには、直接接続されているノードが 4 つあるため、距離は +4 です。わずかに離れた、つまり隣接するノードが 3 つあり、距離は +6 です。さらに隣接するノードが 3 つあり、距離は +9 です。最後に、最も左側にあるノードは +4 です。したがって、ノードの合計距離は 23 であることがわかります。同様に、右側のノードの距離は 3+8+6+8=25 になります。すると、ノードを選択するときに、左側のノードが最初に選択されることは明らかです。

もちろん、これは単にノードをソートして選択する方法であり、その問題点も非常に明白です。この論文ではこの研究の詳細な説明は提供されませんでした。

2. ノードの近隣アセンブリを見つける

次に、畳み込み演算を実行するために、選択されたノードごとに受容野が決定されます。ただし、その前に、まず各ノードの近傍フィールドを見つけ、それから受容フィールド内のノードを決定します。受容野のサイズが k であると仮定すると、各ノードには明らかに 2 つの状況があります。隣接ノードの数が k 未満であるか、隣接ノードが多すぎるかです。これについては次の章で説明します。

図に示すように、6 つのノードが選択されます。各ノードについて、最初に直接隣接するノード (1 近傍と呼ばれる) を検索します。それでも不十分な場合は、間接的に隣接するノードを追加します。 1 近傍で十分な場合は、まずすべてを候補エリアに配置し、次のステップで正規化によって最終的な選択を行います。

3. グラフの正規化

近傍アセンブル プロセスの前のステップで、ノードが合計 N 個のノードを持つドメインを取得したと仮定します。その場合、N の数は k と等しくならない可能性があります。したがって、正規化プロセスは、ラベルを並べ替えてそれらを選択し、その順序でベクトルにマッピングすることです。

このノードの隣接ノードの数が不十分な場合は、すべてが直接選択され、不十分な場合はダミーノードが追加されますが、それでもソートする必要があります。数 N を超える場合は、ソートに従って後ろのノードを切り捨てる必要があります。図 7 は、ノードの選択から受容野の解決までのプロセス全体を示しています。正規化ソート後、ベクトルにマッピングできます。したがって、このステップで最も重要なことは、ノードをソートすることです。

図 8 に示すように、任意のノードの受容野を解決するプロセスを示します。ここでの畳み込みカーネルのサイズは 4 なので、このノード自体を含めて最終的に 4 つのノードを選択する必要があります。したがって、これらのノードにはラベルを付ける必要があります。もちろん、さまざまな方法がありますが、ラベルを付ける最良の方法は何でしょうか?図 7 に示すように、実際には、これらの 7 つのノードから 4 つのノードを選択すると、4 つのノードを含むグラフのセットが形成されます。著者は次のように考えています。特定のラベルの下で、セットから 2 つのグラフをランダムに選択し、ベクトル空間でのグラフ間の距離とグラフ空間でのグラフ間の距離の期待差を計算します。この期待値が小さければ、ラベルが優れていることを意味します。具体的な表現は以下のとおりです。

最適なラベルを取得した後、ノードを順番に順序付けられたベクトルにマッピングし、図 6 の右端に示すように、ノードの受容野を取得できます。

4. 畳み込みアーキテクチャ

この記事では、入力をベクトルに変換し、畳み込み演算に使用できる 2 層の畳み込みニューラル ネットワークを使用します。具体的な操作は図9に示されています。

まず、最下層の灰色のブロックはネットワークの入力です。各ブロックはノードの受容野領域を表し、これも先ほど解いた 4 つのノードです。ここで、an は各ノードのデータの次元を表します (ノードがカラー画像の場合は 3 次元、テキストの場合は単語ベクトルになります...ここではデータの次元が n であることを示します)。ピンク色のものは畳み込みカーネルを表し、カーネル サイズは 4 ですが、幅はデータの次元と同じである必要があります。したがって、各ノードボリュームシーズンの後に値が取得されます。畳み込みのストライドは 4 です。つまり、1 つのノードで畳み込みが実行されるたびに、ストライド = 4 が次のノードに渡ることになります。 （注：論文の図1では、（a）ではストライド=1ですが、（b）の構造に変換されるとストライド=9になります）。畳み込みカーネルの数は M であり、畳み込み後に得られる特徴マップのチャネル数が M であることを示しているため、最終結果は V1...VM となり、これがグラフの特徴表現となります。これを使用すると、分類または回帰タスクを実行できます。

基本的な質問:

グラフの基本的な概念：主に頂点と辺で構成されています。隣接行列 A があります。その中のノードを特徴 (Feat) で表すと、下の右図のようになります。