mits58のメモ

メモ　参考にしないでください

A Simple Proof of the Universality of Invariant/Equivariant Graph Neural Networks

読んでいる（ちゃんと理解していない）

arxiv.org

Invariant や Equivariant とは？

まず、グラフ上の問題をグラフデータの組 (G_i, y_i) から、下記の仮説を探す問題と定義する。（機械学習的にこれは自然やんな）

h:\mathcal{G} \rightarrow \mathcal{Y}\ \mathrm{s.t.}\ h(G_i) \sim y_i

この時、\mathcal{Y} に当たる集合は色々考えられるが、 \mathbb{R} や、 \mathbb{R}^{(V(G))_k} を取り上げる。それぞれグラフ、ノードに対する問題に対応している。（毒性あるなら1とか、あるノード同士が同じコミュニティなら1とかそんなかんじ）

同型なグラフに対して違う形の入力（頂点順序を入れ替えて、同じように辺を張ったグラフとか）が与えられた時、違う値を返して来ると辛い気持ちになります。ということで、それぞれ対応する仮説 h に対し、「同型なグラフに対しては同じ値を返す性質」を定義します。それが、Invariant や Equivariant ってことらしい。

じゃあこの論文は何したの？

Tensorized Graph Neural Networks というモデル（表記ゆれしてるけどこっちが正しい？ちゃんと調べないとなぁ）が、先程の invariant や equivariant を持つ関数に対し universality を持つことを示しています。

気持ち？

Stone-Weierstrassの定理を用いて証明しているらしい。これはざっくり言ってしまうと、ある空間上に定められた連続関数が任意精度で一様に近似できるってことらしい。

で、対応する隣接行列のようなものが張る空間を考えて、それ上で編集距離を導入して、Stone-Weierstrassの定理を満たすことを示してるらしい。

 

雑感

  • Tensorized Graph Neural Networksについて調べないとなぁ
  • https://arxiv.org/abs/1905.04943 今年のNeurIPSやんワロタ（気になる論文リストにはぶちこんでた）
  • この論文を読んだモチベとして、「どんな h が学習できるの？」と思ったんだけど、同型なグラフに対して同じ値を返すならセーフだった
  • あと、グラフサイズ無限大に飛ばした時に無限大になる値なら学習できるみたいな話も聞いたけどそれなんだろ……ちゃんと証明読むとわかる？　いや、うーん……今やってはいけない（真顔）