グラフデータに対する教師なしAIトレーニングの新手法

```html 著者: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang 概要 ソーシャルネットワークやコミュニケーションネットワークなど、さまざまな情報ネットワークの内容の豊かさは、外部からの監督なしに高品質な表現表現を学習する前例のない可能性を提供します。本稿では、グラフ構造化データから埋め込み空間への豊富な情報を教師なしでどのように保存および抽出できるかを調査します。この目的のために、入力グラフと高レベルの隠れ表現との相関を測定する、グラフィカル相互情報（GMI）という新しい概念を提案します。GMIは、ベクトル空間からグラフ領域への従来の相互情報計算のアイデアを一般化します。そこでは、ノードの特徴とトポロジ構造の両方の側面からの相互情報の測定が不可欠です。GMIにはいくつかの利点があります。第一に、それは入力グラフの同型変換に対して不変です。これは、多くの既存のグラフ表現学習アルゴリズムにおける避けられない制約です。さらに、MINEなどの現在の相互情報推定方法によって効率的に推定および最大化できます。最後に、理論分析により、その正しさと合理性が確認されます。GMIの助けを借りて、入力とグラフニューラルエンコーダーの出力との間のGMIを最大化することによって訓練された教師なし学習モデルを開発します。 推論的および帰納的なノード分類とリンク予測に関するかなりの実験により、提案手法が最先端の教師なし手法を上回り、場合によっては教師あり手法のパフォーマンスさえも上回ることが示されています。 1 はじめに 多様な情報ネットワークの信頼性の高い定量的分析を達成するために、グラフ構造化データのための高品質な表現学習が、現在の魅力的なトピックの1つになっています。この目標に向けた最近の方法は、一般にグラフニューラルネットワーク（GNN）として分類されており、ノード分類 [ , , ]、リンク予測 [ , , ]、グラフアライメント [ , , ]、分子生成 [ , , ] など、多くの学習タスクで顕著な進歩を遂げています。収穫のある進歩にもかかわらず、既存のアプローチでGNNをトレーニングするには、通常、ある種の監督が必要です。疑いなく、ラベル情報は取得が困難であり（手動アノテーションまたは許可の支払い）、プライバシーポリシーにより取得不可能な場合さえあります。与えられたラベルの信頼性が時々疑問視されることは言うまでもありません。したがって、監督なしで高品質なグラフ表現を達成する方法は、多くの実用的なケースで必要とされており、これが本稿の研究の動機となっています。 35 42 50 26 27 49 12 19 43 4 5 46 収集したグラフ構造化データを注意深く調べると、それらは一般に、ソーシャルネットワーク、引用ネットワーク、コミュニケーションネットワークなどのさまざまなソースから取得され、膨大な量のコンテンツとリンク情報が存在することがわかります。たとえば、Twitter、Flickr、Facebookなどの多くのソーシャルプラットフォームのデータには、ユーザーの特徴（例：基本的な個人情報、テキスト、画像、IP）とその関係（例：同じアイテムの購入、友人であること）が含まれます。これらの豊富なコンテンツデータは、追加のガイダンスなしで後続のマイニングタスクをサポートするのに十分です。2つのエンティティが特徴で極端な類似性を示す場合、それらの間にリンクが存在する可能性が高い（リンク予測）であり、それらは同じカテゴリに属する可能性が高い（分類）です。2つのエンティティが両方とも同じエンティティにリンクしている場合、それらは同様の特徴を持つ可能性があります（推奨）。この意味で、情報ネットワークからできるだけ多くの情報を埋め込み空間に保存および抽出することは、監督の形態なしでマイニングタスクで望ましいパフォーマンスを発揮する高品質な表現表現の学習を促進します。教師なしグラフ表現学習は、特に野生の大量のラベルなしデータから恩恵を受けたい場合、ラベルからの自由さのために多くの場合、より有利な選択肢です。 グラフ内の豊富な情報を完全に引き継ぐために、本稿では、画像で機能するDeep Info-Maxメソッド [ ] の経験的成功に触発されて、相互情報（MI）最大化に基づいてグラフ埋め込みを実行します。有用な表現を発見するために、Deep InfoMaxは、エンコーダーの入力（つまり、画像）と出力（つまり、隠れベクトル）との間のMIを最大化するようにトレーニングします。グラフ領域でDeep InfoMaxを考慮すると、最初に解決すべき問題は、グラフと隠れベクトルの間のMIをどのように定義するかということです。ただし、グラフのトポロジは画像よりも複雑です（図 を参照）。課題の1つは、各ノードの隠れ表現とその近傍入力特徴との間のMI関数が対称性を満たすことを保証することです。つまり、近傍の順列に対して不変であることです。MIを考慮した最近の作業の1つであるDeep Graph Infomax（DGI）[ ]は、まず入力グラフと対応する破損グラフを埋め込み、次に読み取り関数を介してグラフの要約をベクトルとして要約し、最後に隠れ表現とこの要約ベクトルの間のMIを最大化します。破損グラフ（ネガティブサンプル）から入力グラフ（ポジティブサンプル）を区別することによって。図 は、DGIの理解しやすい概要を示しています。この種のMIの最大化は、入力ノードの特徴と隠れベクトルの間のMIの最大化と同等であることが証明されていますが、この同等性はいくつかの前提条件の下で保持されます。たとえば、読み取り関数は単射である必要がありますが、実際には制限が多すぎるようです。単射読み取り関数の存在を特定の設計によって保証できたとしても（たとえば、DeepSets [ ] で使用されるもの）、読み取り関数の単射能力は、外部の監督なしでトレーニングされた方法によっても影響を受けます。つまり、本来単射である関数でも、外部の監督なしでトレーニングされると単射でなくなるリスクがあります。そして、読み取り関数が単射でない場合、入力グラフの情報は、グラフのサイズが増加するにつれて要約ベクトルに含まれる情報が減少します。さらに、DGIは、粗いグラフ/パッチレベルのMI最大化にとどまります。したがって、DGIでは、エンコーダーが入力データから十分な情報を抽出できる保証はありません。なぜなら、隠れ表現とその元の入力との間を明示的に相関させないからです。 20 1 41 1 47 本稿では、読み取り関数や破損関数を使用せずに、グラフ構造の観点からMIを考慮する、より直接的な方法を提案します。エンコーダーの入力（つまり、入力近傍からなるサブグラフ）と出力（つまり、各ノードの隠れ表現）を直接比較することにより、MIを導出します。そして興味深いことに、理論的導出により、直接定式化されたMIは、各近傍特徴と隠れベクトルとの間の局所MIの重み付き合計に分解できることが示されています。このように、入力特徴を分解し、MI計算を扱いやすくしました。さらに、この形式のMIは、重みの値を調整すれば対称性を簡単に満たすことができます。詳細は§ を参照してください。上記のMIは主にノード特徴のレベルで測定されるため、特徴相互情報（FMI）と呼びます。 3.1 FMIに関する残りの2つの問題は、**1.**結合重みはまだ不明であり、**2.**トポロジ（つまり、エッジ特徴）を考慮していないことです。これらの2つの問題をさらに解決するために、FMIに基づいたグラフィカル相互情報（GMI）測定を定義します。特に、GMIは、FMIの重みを、表現空間内の各近傍とターゲットノードとの間の近接度として設定することにより、直感的な値割り当てを適用します。トポロジ情報を保持するために、GMIは、追加の相互情報項を介して、これらの重みを入力エッジ特徴とさらに相関させます。結果として得られるGMIはトポロジ的に不変であり、Mutual Information Neural Estimation（MINE）[ ]によっても計算可能です。本発明の主な貢献は以下のとおりです。 2 • ：従来のMI推定をグラフ領域に一般化し、それに応じて新しい概念のグラフィカル相互情報（GMI）を提案します。GMIは、読み取り関数によって引き起こされる潜在的なリスクから解放されます。なぜなら、入力グラフと高レベル埋め込みとの間のMIを直接的なパターンで考慮するからです。 概念 • ：理論的分析を通じて、GMIの扱いやすく計算可能な形式を提供し、GMI全体を局所MIの重み付き合計に分解します。MINEメソッドの助けを借りて、GMIの最大化はノードレベルで簡単に達成できます。 アルゴリズム • ：推論的および帰納的なものを含む、いくつかの一般的なノード分類およびリンク予測タスクでGMIの有効性を検証します。実験により、提案手法がさまざまなベンチマークで有望なパフォーマンスを発揮し、場合によっては教師あり手法を上回ることが示されています。 実験的発見 2 関連研究 本研究の焦点に沿って、次の2つの分野における先行研究を簡単にレビューします。**1.**相互情報推定、および**2.**グラフ上の表現学習のためのニューラルネットワーク。 。InfoMax原則 [ ] がニューラルネットワークの入力と出力との間のMIの最大化を提唱しているように、ICAアルゴリズム [ , ] など、多くの方法が教師なし特徴学習でMIのアイデアを採用しようとしています。それにもかかわらず、これらの方法は、高次元連続変数間のMIの計算の難しさから、ディープニューラルネットワークに簡単に一般化することはできません。幸いなことに、Mutual Information Neural Estimation（MINE）[ ] は、ディープニューラルネットワークのMIの推定を、統計ネットワークを分類器としてトレーニングすることで可能にします。これにより、共同分布からのサンプルと2つの確率変数の周辺分布の積からのサンプルを区別できます。具体的には、MINEはMIの正確なKLベースの定式化を使用しますが、非KL代替であるJensen-Shannonダイバージェンス（JSD）[ ]は、MIの正確な値について心配することなく使用できます。 相互情報推定 3 1 21 2 30 。グラフニューラルネットワーク（GNN）の急速な発展に伴い、近年、GNNに基づく多くのグラフ表現学習アルゴリズムが提案されており、従来のランダムウォークベースおよび因子分解ベースの埋め込みアプローチ [ , , , , ] よりも優れたパフォーマンスを発揮しています。一般的に、これらの方法は、教師ありカテゴリと教師なしカテゴリに分類できます。その中で、グラフ上の教師あり表現学習に関する豊富な文献があります [ , , , , ]。ネットワークアーキテクチャのバリエーションにもかかわらず、それらはしばしば現実的なシナリオでアクセスできないラベルの助けを借りて経験的な成功を収めています。この場合、教師なしグラフ学習方法 [ , , ] はより広い応用可能性を持っています。よく知られている方法は、教師なし設定でランダムウォークベースの目的によってGNNをトレーニングする帰納的フレームワークであるGraphSAGE [ ] です。そして最近、DGI [ ] は、MI最大化のアイデアをグラフ領域に適用し、教師なしパターンで強力なパフォーマンスを得ています。しかし、DGIは粗い粒度の最大化（つまり、グラフ/パッチレベルでのMIの最大化）を実装しており、入力グラフの繊細な情報を保持するのが困難です。さらに、DGIで使用される読み取り関数に課される条件は、実際には制限が多すぎるようです。対照的に、私たちは、読み取り関数の制限を排除し、エンコーダーの入力と出力との間のMIを直接最大化することによって、ノードレベルでグラフィカル相互情報最大化を達成することに焦点を当てています。提案手法によって導出された表現は、入力グラフ情報を保持する上でより洗練されており、ノード分類、リンク予測、推奨などの下流グラフマイニングタスクの可能性を保証します。 グラフ表現学習のためのニューラルネットワーク 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 グラフィカル相互情報：定義と最大化 さらに進む前に、まず本稿で使用する予備的な概念を提供します。G = (V, E) を 個のノード ∈ V とエッジ = ( , ) ∈ E を持つグラフとします。経験的確率分布Pを仮定するノード特徴は、 ∈ R × = { 1, · · · , } として与えられます。ここで、 ∈ R はノード の特徴を表します。隣接行列 ∈ R × はエッジ接続を表し、ここでエッジ に関連付けられた は実数または多次元ベクトル1である可能性があります。 N vi eij vi vj X N D x x N xi D vi A N N eij Aij グラフ表現学習の目標は、隠れベクトル = { 1, · · · , } = ( , ) がすべてのノードの高レベル表現を示すように、エンコーダー : R × × R × → R × ′ を学習することです。エンコーディングプロセスは、ノードごとに書き直すことができます。 H h hN f X A f N D N N N D これを示すために、ノード のエンコーダー が 層GNNである場合、 と をそれぞれその近傍のノード特徴と対応する隣接行列と定義します。特に、 は ≤ の ホップ近傍を含み、隣接行列に自己ループを追加するとノード 自体も含まれます。ここで、 と によって展開されたサブグラフをノード の と呼び、G と表します。サポートグラフの定義により、各ノードのエンコーディングは = (G ) = ( , ) となります。 i f l Xi Ai Xi k l k i Xi Ai i サポートグラフ i hi f i f Xi Ai Deep InfoMax [ ] では、エンコーダーのトレーニング目標は、入力と出力との間のMIを最大化することです。MIは、統計ネットワークをディスコリミネーターとして使用して、共同分布からのサンプルと周辺分布の積から抽出されたサンプルを分類することによって推定されます。自然に、Deep InfoMaxのアイデアをグラフに適用する場合、各ノードの隠れ表現 とサポートグラフG との間のMIを最大化する必要があります。このようなグラフィカルMIを ( ; G ) と表します。ただし、I (hi ; Gi )を定義することは簡単ではありません。困難は次のとおりです。 グラフィカル相互情報の定義における困難。 20 hi i I hi i • グラフィカルMIは、ノードインデックスに関して不変である必要があります。つまり、G とG′ が互いに同型である場合、 ( ; G ) = ( ; G′ ) となります。 i i I hi i I hi i • MI計算にMINEメソッドを採用する場合、MINEのディスコリミネーターは固定サイズの入力のみを受け入れます。これは、異なるG は通常異なる数のノードを含み、したがって異なるサイズであるため、G にとってはまだ実行不可能でした。 i i グラフィカル相互情報の定義の問題を回避するために、このセクションでは、ノード特徴のみに依存する特徴相互情報（FMI）の概念を紹介することから始めます。FMIの分解に着想を得て、次に、ノード特徴と 3.1 特徴相互情報 ノード特徴 の経験的確率分布を ( )、 の確率を ( )、共同分布を ( , ) と表します。情報理論によれば、 と との間のMIは次のように定義されます。 Xi p Xi hi p hi p hi Xi hi Xi 興味深いことに、 ( ; ) を計算するための相互情報分解定理があります。 I hi Xi 定理1（相互情報分解）。 ( | ) ( ; ) 条件付き確率p hi Xi が乗法的である場合（[ ] の乗法定義を参照）、Eq. で定義される大域的相互情報I 36 (1) hi Xi は、局所MIの重み付き合計として分解できます。すなわち、 ここで、xj はノードiのj番目の近傍であり、in はXi のすべての要素の数であり、重みwij は各jについて ≤ ≤ 1 を満たします。 1 wij 上記の定理を証明するために、まず2つの補題と1つの定義を導入します。 補題1。 任意の確率変数X、Y、およびZについて、 定理 での分解により、ディスコリミネーターの入力が常に同じサイズ（つまり、 ′ × ）になるペア（ 、 ）になるため、Eq. の右側をMINEを使用して計算できます。さらに、重みを調整して、入力グラフの同型変換を反映させることができます。たとえば、 がノード の1ホップ近傍のみを含む場合、すべての重みを同一に設定すると、異なる順序の入力ノードに対して同じMIが得られます。 1 D D hi xj (2) Xi i 分解の利点にもかかわらず、重みの正確な値を特徴付けるのは困難です。なぜなら、それらは ( ; ) の値とその下にある確率分布に関連しているからです。 I hi xj 自明な方法は、すべての重みを に設定することです。そうすると、Eq. の右側を最大化することは、 ( ; ) の下限を最大化することと同等になり、真のFMIもいくらか最大化されます。この方法に加えて、重みを学習可能なアテンションとして考慮することで、さらに強化されたソリューションを提供します。これは、次のサブセクションのトピックです。 1 (2) I hi Xi 定理 の分解から着想を得て、グラフのもう一方の側面（つまり、 3.2 トポロジを認識する相互情報 1 トポロジビュー）から学習可能な重みを構築しようとします。これにより、 の値がより柔軟になり、グラフの固有のプロパティを捉えることができます。最終的に、グラフィカル相互情報（GMI）の定義を導出します。 wij 定義2（グラフィカル相互情報）。 G = ( , ) 隠れベクトルhとそのサポートグラフ X A との間のMIは次のように定義されます。 ここで、 と の定義は定理1と同じです。 は隣接行列Aのエッジ重み/特徴であり、 (·) はシグモイド関数です。 xj in aij σ 直感的には、Eq. (10) の第1項の重みwij は、実験で扱われた重みは重み付けされていません。正式には、 ( ; ) = log + (1 − ) log(1 − ) 。(12) を計算します。すべての隠れベクトルHについてEq. (11) とEq. (12) の合計で ( ; ) を最大化することにより、完全な目的関数に到達します。局所MIの大域MIへの寄与を測定します。 ( ; ) の寄与を、表現 と との類似性（つまり、 = ( )）によって実装します。同時に、項 ( ; ) は、 とエッジ重み/特徴 との間のMIを最大化して、 がトポロジ関係に準拠するように強制します。この意味で、寄与の程度はトポロジ構造における近接性と一致し、 はノードjがノードiに「近い」ほど大きくなり、そうでない場合は小さくなるという事実として一般に受け入れられています。この戦略は、FMIがノード特徴のみに焦点を当てているという欠点を補い、局所MIが大域MIに適応的に寄与するようにします。この戦略におけるアテンションのアイデアをよりよく理解するには、アテンションベースのGCN [40] を参照してください。Eq. (10) の定義は一般的なケースに適用可能であることに注意してください。特定の状況では、効率のためにEq. (10) をわずかに変更できます。たとえば、重み付けされていないグラフ（つまり、エッジ値が接続されている場合は1、それ以外の場合は0）を扱う場合、第2のMI項I (wij ; aij )を負のクロスエントロピー損失に置き換えることができます。クロスエントロピーを最小化することもMI最大化に寄与し、より効率的な計算を提供します。詳細は次のセクションで説明します。全体として、Eq. (10) の定義にはいくつかの利点があります。第一に、この種のMIは入力グラフの同型変換に対して不変です。第二に、右側の各コンポーネントはMINEによって推定できるため、計算可能です。さらに重要なことに、GMIは、ノードとエッジの両方の特徴とエッジの隠れベクトルと入力特徴との間の明示的な相関を細かいノードレベルで考慮するため、元の入力情報をキャプチャする上でDGIよりも強力です。 I wij aij aij wij aij wij I hi Gi I hi xj hi hj wij σ hThj I wij aij wij aij wij wij 3.3 GMIの最大化 MINEの助けを借りて、Eq. の右側を直接最大化します。MINEは、KLダイバージェンスのドンスカー・バライフダン（DV）[ ]表現を使用して、共同分布と周辺分布の積との間のMIの下限を推定することに注意してください。MIの特定の値を得るよりもMIの最大化に焦点を当てているため、Jensen-Shannon MI推定器（JSD）[ ]およびNoise-Contrastive推定器（infoNCE）[ ]などの他の非KL代替手段を使用できます。経験的発見と[ ]の分析に基づいて、有効性と効率のために、この論文ではJSD推定器を使用します。なぜなら、infoNCE推定器はネガティブサンプリング戦略（ネガティブサンプルの数）に敏感であるため、固定の利用可能なメモリを持つ大規模データセットのボトルネックになる可能性があるからです。対照的に、JSD推定器はネガティブサンプリング戦略に影響されず、多くのタスクで優れたパフォーマンスを発揮するため、タスクに適しています。具体的には、Eq. の第1項の ( ; ) は次のように計算します。 (10) 10 30 31 20 (10) I hi xj ここで、D : × ′ → R は、パラメータ を持つニューラルネットワークによって構築されたディスコリミネーターです。 はP = Pからネガティブサンプリングされたものであり、 ( ) = (1 + ) はソフトプラス関数を表します。 w D D w x j sp x loд ex § で述べたように、実験で扱ったグラフは重み付けされていないため、JSD推定器を使用する代わりに、クロスエントロピーを計算することによって ( ; ) を最大化します。正式には、次のように計算します。 3.2 I wij aij すべての隠れベクトルHについてEq. (11) とEq. (12) の合計でI (hi ; Gi )を最大化することにより、GMI最適化の完全な目的関数に到達します。さらに、Eq. (11) と(12) のバランスをとるために、トレードオフパラメータを追加して、より柔軟にします。 4 実験 このセクションでは、2つの一般的なタスク、つまりノード分類（推論的および帰納的）とリンク予測でGMIのパフォーマンスを経験的に評価します。さらに、GMIと他の2つの教師なしアルゴリズム（EP-BおよびDGI）との比較は、その有効性をさらに示しています。また、t-SNEプロットの可視化を提供し、モデル深度の影響を分析します。 4.1 データセット 各タスクにおける提案手法の品質を評価するために、以前の研究 [ , , ] で一般的に使用されている4つまたは5つのベンチマークデータセットを採用します。詳細な統計を表 に示します。 16 25 41 1 分類タスクでは、Cora、Citeseer、およびPubMed [ ]2 は引用ネットワークであり、ノードはドキュメントを表し、エッジは引用を表します。各ドキュメントは、単語の袋表現ベクトルに関連付けられ、事前定義されたクラスのいずれかに属します。Kipf & Welling [ , ] の推論設定に従い、トレーニングはすべてのノードで実行され、1000個のテストノードが評価に使用されます。Reddit3 は、2014年9月中に作成された多数の相互接続されたReddit投稿で構成される大規模なソーシャルネットワークです[ ]。投稿はノードとして扱われ、エッジは同じユーザーがコメントしたことを意味します。 38 25 41 16 ![ 表1：実験で使用されたデータセットの統計。 ](https://cdn.hackernoon.com/images/InxBRjRIs6M1kdhuWcyNHiiUrxm1-eph3eec.jpeg) クラスラベルはコミュニティであり、目標は異なる投稿が属するコミュニティを予測することです。PPI3 は、さまざまな人間の組織に関連する複数のグラフを含むタンパク質間相互作用データセットです[ ]。位置遺伝子セット、モチーフ遺伝子セット、および免疫シグネチャはノード特徴と見なされ、各ノードには遺伝子オントロジーセットによって提供される合計121個のラベルがあります。さまざまなPPIグラフにわたるタンパク質機能を分類することが目標です。Hamiltonら[ ] の帰納的設定に従い、Redditでは、トレーニングのために最初の20日間に投稿された投稿をモデルにフィードしますが、残りはテストに使用されます（30％は検証に使用されます）。PPIでは、トレーニング用に20個のグラフ、検証用に2個、テスト用に2個です。RedditとPPIの場合、テストは未見（トレーニングされていない）ノードとグラフで実行されますが、最初の3つのデータセットは推論学習に使用されることに注意してください。 52 16 リンク予測タスクでは、BlogCatalog4はブロガーがお互いをフォローし、事前定義された6つのカテゴリの下にブログを登録するソーシャルブログウェブサイトです。ブログのタグはノード特徴として使用されます。Flickr4 は、ユーザーが他のユーザーと相互作用し、ソーシャルネットワークを形成する画像共有ウェブサイトです。ユーザーは9つの事前定義されたクラスで写真をアップロードし、興味を反映する添付タグを選択して属性情報を提供します。CoraとPPIの説明は省略します。Manciniら[15] の実験設定と評価指標に従い、一部のエッジが削除されたグラフが与えられた場合、これらの欠落しているリンクを予測することを目指します。Cora、BlogCatalog、およびFlickrの場合、エッジ削除後に残ったネットワークが接続されていることを確認しながら、20％、50％、および70％のエッジをランダムに削除し、損傷したネットワークをトレーニングに使用します。PPIについては、トレーニング中に見られなかったエッジの一部を、人為的なエッジ削除の代わりに予測ターゲットとして直接扱います。 4.2 実験設定 分類およびリンク予測タスクの両方で、以下のレイヤーごとの伝播規則を持つ標準的なグラフ畳み込みネットワーク（GCN）モデルをエンコーダーとして使用します。 エンコーダー設計。 ここで、Aˆ = D -1/2AD - 1/2A = A + In、Dii = Aij、H (1) および H (I + 1) は 番 l