グラフ機械学習の特徴伝播を用いた欠損データの再構築

この論文で紹介されている特徴伝播​​は、グラフ機械学習アプリケーションで欠落している特徴を処理するための効率的でスケーラブルな方法です。シンプルですが、驚くほどうまく機能します。

グラフ ニューラル ネットワーク (GNN) モデルでは通常、各ノードに完全な特徴ベクトルがあると想定されます。次のような形式の2層GCNモデル[1]を例に挙げる。

Z = A σ(AXW₁) W₂

モデルの 2 つの入力は、グラフ構造をエンコードする (正規化された) 隣接行列 A と、ノード機能を行として持つ特徴行列 X であり、出力はノード埋め込み Z です。 GCN の各レイヤーは、ノード特徴変換 (学習可能なマトリックス W₁ および W₂ によってパラメーター化される) を実行し、変換された特徴ベクトルを隣接ノードに伝播します。ここで重要な概念は、GCN は X 内のすべてのエントリが観測されていると想定していることです。

ただし、実際のシナリオでは、一部のノード機能が欠落していることがよくあります。たとえば、年齢や性別などの人口統計情報は、ソーシャル ネットワーク ユーザーのごく一部にしか公開されない場合がありますが、コンテンツ機能は通常、最もアクティブなユーザーにのみ表示されます。たとえば、レコメンデーション システムでは、すべての製品に完全な説明が関連付けられているわけではなく、状況はさらに悪化しています。デジタル プライバシーに対する人々の意識が高まるにつれて、ユーザーの明示的な同意がなければ取得できないデータがますます増えています。

上記の説明によれば、特徴行列には欠損値があり、既存の GNN モデルのほとんどは直接適用できません。最近のいくつかの研究では、欠損した特徴を処理できるGNNモデルが導出されている（例：[2-3]）が、これらのモデルは欠損した特徴率が高い（> 90％）場合に問題があり、数百万以上のエッジを持つグラフに拡張できない。

Maria Gorinova、Ben Chamberlain（Twitter）、Henry Kenlay、Xiaowen Dong（オックスフォード）が共同執筆した新しい論文[4]では、特徴伝播（FP）[4]がシンプルでありながら効率的で驚くほど効果的な解決策として提案されています。 つまり、FP はグラフ上の既知の特徴を伝播することによって、欠落している特徴を再構築します。 再構築された特徴は、任意の GNN に入力して、ノード分類やリンク予測などの下流のタスクを解決することができます。

機能伝播フレームワーク。 入力は、ノード機能が欠落しているグラフです (左)。 最初のステップでは、特徴伝播により、グラフ内の既知の特徴を反復的に拡散することで、欠落している特徴を再構築します (中央)。 その後、グラフと再構築されたノードの特徴が下流の GNN モデルに送られ、予測が生成されます (右)。

伝播の手順は非常に簡単です。まず、未知の特徴が任意の値で初期化されます[5]。 特徴は、（正規化された）隣接行列を適用することによって伝播され、その後、既知の特徴は実際の値にリセットされます。 固有ベクトルが収束するまで、これら2つの操作を繰り返します[6]。

特徴伝播は、特徴が欠けているグラフを学習するためのシンプルで驚くほど強力な方法です。 フィーチャの各座標は個別に扱われます (x は X の列を表します)。

FP は、データの同質性 (「滑らかさ」) の仮定から導き出すことができます。つまり、近隣のデータは類似した固有ベクトルを持つ傾向があります。 均質性のレベルは、ノードの特徴とその近傍の特徴の平均との二乗差を測定する二次形式であるディリクレ エネルギーを使用して定量化できます。ディリクレエネルギーの勾配フロー[7]は、既知の特徴を境界条件として持つ熱拡散方程式のグラフである。 FPは拡散方程式の離散化として単位ステップサイズの明示的なフォワードオイラー法を使用して得られる[8]。

機能伝播の反復的な適用がさらに適用されるにつれて、スカラー ノード機能がどのように進化するかの例を示すアニメーション。 未知の特徴はゼロに初期化されますが、指定されたグラフ上のディリクレ エネルギーを最小化する値にすぐに収束します。

特徴伝播はラベル伝播（LP）[9]に似ている。 主な違いは、LP はグラフ内の既知のラベルを伝播することによって各ノードのクラスを直接予測する特徴に依存しない方法であるのに対し、FP は最初に欠落しているノードの機能を再構築し、それを下流の GNN に供給するために使用されることです。 これにより、FP は観測された特徴を活用し、すべてのベンチマークで LP を上回るパフォーマンスを発揮できるようになります。 実際には、ラベルを持つノードのセットと機能を持つノードのセットが必ずしも完全に重複しないことが多いため、2 つの方法を直接比較できるとは限りません。

7 つの標準ノード分類ベンチマークを使用して FP の広範な実験検証を実行します。このベンチマークでは、ノード機能の可変部分がランダムに削除されます (チャネルごとに独立して)。 FPに続いて2層GCNを適用すると、特徴の再構築において単純なベースラインや最近の最先端の方法[2-3]よりも大幅に優れた性能を発揮します。

FP は、特徴欠落率が高い (> 90%) 場合に特に顕著であり、他のすべての方法では問題が発生する傾向があります。 たとえば、特徴の 99% が失われた場合でも、FP では、すべての特徴が存在する同じモデルと比較して、平均で約 4% の相対精度しか失われません。

Cora データセットにおけるさまざまな特徴欠損率のノード分類精度 (ほとんどの GNN の標準である 0% から極端なケースの 99% まで)。

FP のもう 1 つの重要な機能は、そのスケーラビリティです。他の方法では、数百万のエッジを持つグラフを超えて拡張することはできませんが、FP では 10 億のエッジを持つグラフまで拡張できます。 著者らは、約 10 億のノードと 100 億のエッジを持つ Twitter 内部グラフ上で、単一のマシンを使用して 1 時間以内にこれを実行しました。

FP+GCNと最新の最先端手法GCNMFおよびPaGNN [2-3]の実行時間（秒）。 FP+GCN は他の 2 つの方法よりも 3 倍高速です。 GCNMF は OGBN-Arxiv でメモリ不足 (OOM) に悩まされていますが、GCNMF と PaGNN は OGBN-Products (約 1 億 2,300 万エッジ) で OOM に悩まされています。この場合、FP の再構築部分 (ダウンストリーム モデルのトレーニングなし) には約 10 秒しかかかりません。

FP の現在の制限の 1 つは、異好性グラフ、つまり隣接するグラフの特性が異なるグラフではうまく機能しないことです。 これは驚くべきことではありません。なぜなら、FP は均質性仮定 (拡散方程式を介してディリクレ エネルギーを最小化する) から導かれるからです。 FP では、異なる特徴チャネルは相関していないと想定されますが、現実にはそうなることはほとんどありません。 ただし、より複雑な拡散メカニズムに置き換えることで、両方の制約を満たすことは可能です。

99% の特徴が欠落している場合の、さまざまな同質性レベルの合成グラフ上のノード分類精度 (0 は非常に異質、1 は非常に同質)。 FP は、高均質性設定では完全な特徴量とほぼ同じパフォーマンスを発揮しますが、低均質性設定では両者のギャップが大きく、FP のパフォーマンスは、欠落している特徴量がゼロに置き換えられた単純なベースラインまで低下します。

現実世界のアプリケーションでは広く使用されているにもかかわらず、ノード機能が欠落しているグラフでの学習は、ほとんど未開拓の研究分野です。 特徴伝播モデルは、ノード特徴が欠落しているグラフでの学習を改善するための重要なステップですが、この設定での学習の理論的能力について深い疑問も生じます。 FP のシンプルさとスケーラビリティ、そして、極端に特徴が欠落している状態でも、より複雑な方法に比べて驚くほど良好な結果が得られることから、FP は大規模な産業用アプリケーションに適しています。