類似グラフの厳密な生成のためのReLUネットワーク

Abstract

あるソースグラフから指定されたグラフ編集距離の範囲に制約されたグラフを生成することは、有機化学情報学（cheminformatics）、ネットワークの異常合成（network anomaly synthesis）、構造化データの拡張（structured data augmentation）などの応用において重要である。分子設計やネットワーク擾乱（perturbation）の解析を含む領域で、このような制約付き生成モデルへの需要が高まっているにもかかわらず、グラフ編集距離が上界の範囲でグラフを生成できることを理論的に保証するために必要なニューラルアーキテクチャは、ほとんど未検討のままである。さらに、既存のグラフ生成モデルは主にデータ駆動であり、学習データの利用可能性と品質に大きく依存している。その結果、生成されたグラフが望ましい編集距離の制約を満たさない可能性がある。本論文では、これらの課題に対し、与えられたグラフから所定のグラフ編集距離の範囲でグラフを生成できるReLUニューラルネットワークを理論的に特徴付けることで解決する。具体的には、一定の深さで、O(n^2 d) のサイズをもつReLUネットワークの存在を示す。これらは、入力グラフに n 個の頂点があるとき、編集距離 d の範囲でグラフを決定論的に生成し、生成グラフの妥当性を保証しつつ学習データへの依存を排除する。実験評価により、提案ネットワークが、最大 1400 頂点のインスタンスおよび編集距離上限 140 までの範囲で有効な（妥当な）グラフを正常に生成できることが示された。一方、ベースラインの生成モデルは、所望の編集距離を満たすグラフを生成できない。これらの結果は、妥当性が保証されたコンパクトな生成モデルを構築するための理論的基盤を提供する。