「良い」グラフを生成するにはどうすればよいでしょうか?グラフ生成のための深い生成モデルの体系的なレビュー

https://www.zhuanzhi.ai/paper/a904f0aa0762e65e1dd0b8b464df7168

画像は説明です現実のさまざまなシナリオに現れるオブジェクトとその関係。グラフ生成は、この分野における重要な問題の 1 つであり、特定のグラフの分布を学習し、さらに新しいグラフを生成することが考慮されます。ただし、アプリケーションが広く普及しているため、豊富な歴史を持つグラフの生成モデルは伝統的に手作業で作成されており、グラフの一部の統計的特性しかモデル化できません。

グラフ生成のための深層生成モデルの最近の進歩は、生成されるグラフの忠実度を向上させるための重要なステップであり、新しいタイプのアプリケーションへの道を開きます。この文書では、グラフ生成のための深層生成モデルの分野における文献の広範な概要を提供します。まず,グラフ生成のための深い生成モデルの正式な定義と予備知識を与え,次に,無条件グラフ生成と条件付きグラフ生成のための深い生成モデルの分類をそれぞれ提案し,それぞれの既存の研究を比較分析した。これに続いて、この特定の領域における評価指標の概要が説明されます。最後に、深度マップ生成の応用を要約し、5 つの有望な研究の方向性を指摘します。

はじめに

グラフは現実世界のいたるところに存在し、ソーシャル ネットワーク、引用ネットワーク、生物学的ネットワークなどのオブジェクトとその関係を表します。交通網などグラフは、豊富な基礎となる値を含む複雑な構造を持つことも知られています[1]。この分野では多大な努力が払われ、その結果、さまざまなグラフ問題を処理するための豊富な文献と方法が生まれました。

これらの作業は 2 つのカテゴリに分類できます。 1) 特定のグラフのパターンを予測および分析する。 2) 与えられたグラフの分布を学習し、より新しいグラフを生成します。最初のタイプは、ノード分類、グラフ分類、リンク予測などの多くの研究領域をカバーします。過去数十年にわたり、この分野では多くの研究が行われてきました。最初のタイプの問題と比較すると、2 番目のタイプの問題は、この記事の焦点でもあるグラフ生成の問題に関連しています。

グラフ生成には、現実世界のグラフのモデリングと生成のプロセスが含まれており、ソーシャル ネットワークの理解など、いくつかの分野に応用できます [2]、[3]、[4] インタラクションダイナミクス、異常検出 [5]、タンパク質構造モデリング [6]、[7]、ソース コードの生成と翻訳 [8]、[9]、セマンティック解析 [10]。グラフの生成モデルの開発には幅広い用途があるため、豊富な歴史があり、ランダム グラフ、スモールワールド モデル、確率的ブロック モデル、ベイジアン ネットワーク モデルなど、アプリオリな構造に基づくよく知られたモデルが誕生しました。仮定 [11] グラフを生成します。これらのグラフ生成モデル [12]、[13]、[14] は、ランダム グラフ [15]、スモールワールド ネットワーク [16]、スケールフリー グラフ [12] など、事前に選択されたグラフ ファミリをモデル化することを目的としています。ただし、これらのランダム グラフ モデルは、その単純さと手作りの性質により、多くの場合、複雑な依存関係をモデル化する能力が限られており、グラフの一部の統計的特性しかモデル化できません。

これらの方法は通常、事前定義された原則が調整されているプロパティではうまく機能しますが、他のプロパティではうまく機能しないことがよくあります。たとえば、連絡先ネットワーク モデルはインフルエンザの流行には適合しますが、動的な機能接続には適合しません。しかし、精神疾患、サイバー攻撃、脳ネットワークにおけるマルウェアの拡散のメカニズムを説明するものなど、ネットワークの性質や生成原理は多くの分野でほとんど知られていません。別の例として、Erdos-Renyi のグラフには、多くの現実世界のネットワークに典型的なヘビーテール次数分布がありません。さらに、アプリオリな仮定を使用すると、グラフのアプリオリな知識が常に利用できない大規模な領域で、これらの従来の手法をさらに応用することが制限されます。

従来のグラフ生成技術の限界を考慮すると、未解決の重要な課題は、観察されたグラフのコレクションから生成モデルを直接学習できる方法を開発することであり、これはグラフ生成の改善となります。忠実性を保つための重要なステップ。これは、新薬の発見 [17]、[18] やタンパク質構造モデリング [19]、[20]、[21] など、新しいタイプのアプリケーションへの道を開きます。変分オートエンコーダ (VAE) [22] や敵対的生成ネットワーク (GAN) [23] などの深層生成モデルの最近の進歩は、グラフを生成するために提案されており、多くの深層学習モデルが形式化されています。深い生成モデル、これがこのレビューの焦点です。

深層マップ生成では、1 回限りのグラフ生成から逐次グラフ生成プロセスに至るまで、さまざまな深層生成学習戦略に適応するさまざまな高度な作業が実行されてきました。これらの手法は、機械学習、バイオインフォマティクス、人工知能、人間の健康、ソーシャル ネットワーク マイニングなどのさまざまな分野での取り組みを通じて、上記の課題の 1 つまたは複数に対処することを目的としています。ただし、異なる研究分野で開発された手法は、異なる語彙を使用し、異なる視点から問題にアプローチすることがよくあります。

さらに、開発されたグラフの深い生成モデルを検証するための標準的かつ包括的な評価手順が不足しています。この目的を達成するために、この文書では、グラフ生成のための深い生成モデルの系統的なレビューを提供します。その目的は、学際的な研究者が応用分野の問題を解決するために適切なテクノロジーを選択できるようにすることであり、さらに重要なことに、グラフ生成の研究者がグラフ生成の基本原理を理解し、ディープ グラフ生成の分野でオープンな研究の機会を特定できるようにすることです。私たちの知る限り、これはグラフ生成のための深い生成モデルの最初の包括的なレビューです。以下に、このレビューの主な貢献を要約します。

この論文では、問題設定とアプローチによって分類された、グラフ生成のための深い生成モデルの分類を提案します。利点、欠点、およびさまざまなサブカテゴリ間の関係が示されます。グラフ生成のための深い生成モデルと基本的な深い生成モデルが詳細に説明、分析、比較されます。

• ベンチマーク データセットおよび対応するグラフ生成タスクに関する深層生成モデルの既存の評価手順とメトリクスの結果を要約して分類します。
• グラフ深度生成モデルの既存のアプリケーション領域と、それらがこれらのアプリケーションにもたらす潜在的な利点と機会を紹介します。
• 私たちは、グラフ生成のための深層生成モデルの分野におけるいくつかの未解決の問題と有望な将来の研究の方向性を紹介します。

#グラフ生成のための無条件深度生成モデル

無条件深度マップ生成目標は次のとおりです。実分布 p(G) からサンプリングされた観察された実グラフのセットから深い生成モデルを介して分布 pmodel(G) を学習します。生成プロセスのスタイルに従って、これらの方法を 2 つの主な分岐に分けることができます: (1) 逐次生成: ノードとエッジを順番に生成する; (2) 1 回限りの生成: 行列表現に従って確率グラフ モデルを構築するノードとエッジを一度に生成します。グラフを生成するどちらの方法にも長所と短所があります。順次生成では、前の世代のローカルな決定を効率的に実行しますが、長期的な依存関係を維持するのが困難です。したがって、グラフの一部のグローバル プロパティ (スケールフリー プロパティなど) を含めることは困難です。さらに、シーケンス生成に関する既存の研究は、事前定義されたシーケンスの順序付けに限定されており、順列の役割は残されています。ワンショット生成方法では、複数の反復を通じてグラフ全体 (つまり、ノードとエッジ) を同時に生成および洗練することができ、それによってグラフのグローバル プロパティをモデル化できますが、ノード間のグローバルな関係を集合的にモデル化する必要があるため、時間がかかります。複雑さは通常 O(N2) を超えるため、ほとんどのメソッドを大きなグラフに拡張することが困難になります。

グラフ生成のための条件付き深度生成モデル

条件付き深度マップ生成の目標は、一連の観察された現実に基づいています。グラフ G とそれに対応する補助情報 (つまり、条件 y) は、条件付き分布 pmodel(G|y) を学習します。補助情報には、カテゴリ ラベル、セマンティック コンテキスト、他の配布スペースからのグラフなどが含まれます。無条件深度マップ生成と比較すると、マップ生成の課題に加えて、条件付き生成では、与えられた条件から特徴を抽出してマップの生成に統合する方法も考慮する必要があります。

したがって、既存の条件付き深度マップ生成モデルを系統的に導入するために、主にこれらのメソッドが条件を処理する方法について説明します。条件は任意の形式の補助情報であるため、図 1

# の分類ツリーの黄色の部分に示すように、条件はグラフ、シーケンス、セマンティック コンテキストの 3 つのタイプに分類されます。

以上が「良い」グラフを生成するにはどうすればよいでしょうか?グラフ生成のための深い生成モデルの体系的なレビューの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。