A Persistent Weisfeiler–Lehman Procedure for Graph Classification

Persistent Homologyをまったく知らない人は先にhttps://xuzijian629.hatenadiary.jp/entry/2019/07/20/192722を読んでください。

Super Simplified Overview

f:id:xuzijian629:20190720203406p:plain

あまりに本質な画像なんですが、グラフのNodeにWeisfeiler-Lemanの方法に従ってラベルを付けていき、 $h$ 回目のイテレーションにおける、各辺の重みをmultisetの距離（後ほど定義）で与えてやり、重み付きラベル付きグラフを構成する。こうしてできたグラフについてPersistent Homologyを考えてやり、ラベル付きバーコードを生成することで、連結成分やサイクルの情報を含んだグラフの情報が得られる。

Weisfeiler-Lehman Stabilization

WLの詳細は省くが、 $h$ 回目のイテレーションにおける特徴量ベクトルは、色 $i = 1, \ldots, m$ のラベルがこの時点でいくつ存在するかまとめた長さ $m$ のベクトルで与えられる。グラフ $G$ の特徴量ベクトルは、各イテレーションの結果の長さ $m$ のベクトルをconcatして得られる。

有名な話だけどWL testでは区別できないグラフもある。より表現力を強めるためにトポロジカルな情報を含めたいというのがこの論文のモチベーション

Topological Features

位相空間 $M$ について、 $k$ 次元のtopological featureとは、ホモロジー群 $H_k(M)$ のことを指す。とくに、 $k = 0, 1$ についてはそれぞれconnected components, cyclesと名前がついている。明らかに、同型なグラフはこれらの要素数が同じになる。