Stability and Generalization of Graph Convolutional Neural Networks

https://arxiv.org/pdf/1905.01004.pdf

を読んだ。

問題設定

データセットと学習アルゴリズムを固定したときに、入力に対する予測の誤差の期待値を抑えるのではなく、その期待値と、有限個の入力での誤差の平均の差(Generalization Error)を抑える。

→何個ぐらいからなるデータセットを用意すればいいかがわかる

• Single Layer GCNNを考える。フィルターはの形をしている
• 固定されたグラフ上でのSemi-supervisedという設定
• つまり、データセット内の（頂点属性）のペアは未知の分布に従うからサンプルされたものだとする
• SGDで学習しているとする
• activation functionはリプシッツ連続かつリプシッツスムーズ
• loss関数もリプシッツ連続かつリプシッツスムーズ

証明の重要ポイント

• データセットの一要素が変わった場合を考える。このとき影響を受けるのはのみ。の差分による寄与と、その他の係数に分ける。

やばい点

でのオーダー表記が正しいのは、最大固有値が1より大きい場合であるがこれは一般に成り立たない。さらに悪いことにはのときには1以下なので困る。