It is known that MinFVS is NP-hard for bigraphs while it can be solved in $O(n^5)$ time for chordal bipartite graphs, in $O(n^2m)$ time for convex graphs, and in $O(nm)$ time for permutation graphs.

らしい。すご（やっぱそんなにうれしくねえ）

2019-08-12

Pre-training Graph Neural Networks

https://arxiv.org/pdf/1905.12265.pdf

読んだ。大抵のGNNのタスクはnode classificationだけど、化学や生物の分野だとlocal similarityやgraph全体の特徴が重要になることが多い。この論文では、自然言語処理で行われるような、Context PredictionやMasking, Negative SamplingなどをGNNに持ち込んで、pre-trainingに成功したとのこと。

Context Prediction

node embeddingsを用いて、近傍のstructureを推定する

Masking

node, edge attributesをmaskして、GNNにそれを予測させる

BERTは同様の方法でめっちゃpre-trainしてるみたい。

Graph-level

Domain-specificな他taskで学習するか、graph edit distance / graph structure similarityなどについてself-trainingするか

2019-08-11

Macでcupyをインストールする

えー。また競プロとは全然関係のない記事です。同じことをやっていそうな人が少なくてエラーが出てこなかったのでまとめます。

手順1: CUDA対応MacBook Proを購入する

えー。MacBook Mid 2012-2014 15 inchしか対応していないと思います。しかも15 inchじゃないとだめです。頑張りましょう。ぼくは2012年のにしました。

手順2: OSを戻す

2019年8月時点で、macos Mojaveに対応しているCUDA driverがないので、Mojave以前にOSを戻す必要があります。cmd+R+shift+optionでインターネットリカバリをして、一度Lionを経由して、Sierra (10.12.6)にしました。多分High Sierraだと無理です。

CUDA driverとCUDA Toolkitをいれる。

www.nvidia.com

developer.nvidia.com

9.0以降のものはcompute_70以降のNVCC対応なんですが、cupyのインストール時にnvcc fatal : Unsupported gpu architecture 'compute_70'と怒られることになりそうなので、8系を入れます。8系はSierraまでしか対応していないです。

古いバージョンのCommand Line Toolを入れる

https://developer.apple.com/download/more/

こちらからダウンロードできます。Xcode CLT (Command Line Tools) 7.3を入れました。

pip install cupy

LDPATHを調整する

hondou.homedns.org

が天才すぎる。

#!/bin/sh
for file in $1/*
do
  b=`basename $file`
  ln -vs $file /usr/local/lib/$b
done

を作って、

$ ./hoge.sh /Developer/NVIDIA/CUDA-8.0/lib

する。

これでいけるかと思います。cp.arange(10)とかやるとカーネルが呼び出されるはずなのでこれがちゃんと動くとオッケーです。

2019-08-11

mdj982ゼミまとめ

Quadratic Assignment Problem (NP-hard)

Given $C, D \in \mathbb{R}^{n\times n}$ , $\min (X^TCX)\cdot D$ ( $X \in \mathrm{Perm}_n \subset \mathbb{R}^{n \times n}$ )

ただし $A\cdot B$ は $A$ と $B$ の要素ごとの積の和

Graph Isomorphism

図は省略するが、同型なグラフ $G, H$ があったときに、頂点のラベル付けの置換行列を $X$ とすると、 $X^TA_GX = A_H$ はとなる。

同型なら $\max_X (X^TA_HX) \cdot A_G = 2|E|$ となる。

Subgraph Isomorphism

頂点の個数が違っていたとしてもdummyの頂点を用意していて頂点数を揃える。

$X^TA_HX$ と $A_G$ を比較したときに、1が0に対応するのだけ許さないことにする。

HがGのsubgraphなら $\max_X (X^T A_H X) \cdot A_G = 2|E_H|$ となる。

誘導部分グラフ同型

隣接行列を拡張。辺がない頂点間を $-\infty$ とする隣接行列を考える。対角成分は0で、dummyの頂点を含む $(i, j)$ も0

HがGの誘導部分グラフなら $\max_X (X^T A_H X) \cdot A_G = 2|E_H|$ となる。

縮約

縮約があるものだと難しい

QAPのソルバー

heuristicsで1e6オーダーまでできるらしい

APX-hardなのでheuristics強い。

Graph Edit Distance

erase edge
erase vertex
add edge
add vertex

ここまでで同型なグラフを作る。各頂点/辺に関してコストが違っていてもよい。QAPのように、事前にdummyの頂点 $\varepsilon$ を追加しておくと、頂点を消す操作は、 $\varepsilon$ へ投げる操作、頂点を加える操作は、 $\varepsilon$ から頂点をもってくる操作に対応する。

$\phi$ に関するコスト（mappingに関するコスト）

$(X^TCX)\cdot D = \sum_i \sum_j (\sum_k \sum_l C_{kl}X_{ki}X_{lj}D_{ij})$

と展開され、 $(k, l)$ を $(i, j)$ にマッピングするコストは $C_{kl}D_{ij}$ となる。

辺の属性が2値であるならば、 $1, -1$ をコストとして振り分けてやると、同じ属性ならば $1$ , 違う属性なら $-1$ になって便利

max-cutのformulationと似ていそう

2019-08-10

On Asymptotic Behaviors of Graph CNNs from Dynamical Systems Perspective

https://arxiv.org/pdf/1905.10947.pdf

PFNで著者と話したのでメモ

GCNの表現能力についての問題。畳み込みの際に用いる $I - \tilde{L}$ の特異値が小さい場合、レイヤー数に対して指数的に表現能力が落ちてしまうという問題。

f:id:xuzijian629:20190810021145p:plain

連結成分数に対応して大きさが決まる特定の空間 $\mathcal{M}$ で、それの要素は、 $N$ 頂点のベクトルが取りうる特徴量(のsubset)を表すが、 $i, j$ が同じ連結成分に所属し、次数が同じ場合、それらの特徴量が一致してしまうというような $\mathcal{M}$ が存在し、特異値が小さい場合に、GCNのイテレーションを繰り返すたびに、この固有空間との距離が一定の割合以下に縮んでしまうということを証明したっぽい。

2019-08-07

Graph Matching Networks for Learning the Similarity of Graph Structured Objects

https://arxiv.org/pdf/1904.12787.pdfを読む。

Contribution

GNNで1つのグラフを入力とし、similarity判定に使えるvectorを出力する方法
Graph Matching Networkと呼ばれる、入力は2つのグラフで、出力がそのsimilarity scoreのネットワークを提唱。Cross-graph attention mechanismというらしい。まあ要は2つのグラフ間でいろいろやっている。計算量は $O(n_1 n_2)$ なのでさすがにだいぶ遅いが、精度はかなりすごいらしい

Experiments

Synthetic graph edit-distanceを学習する
binary function similarity search
mesh retrieval (何これ)

Notes

Weihuaのやつはisomorphism testであってsimilarityではなさそう（WL kernel, similarity判定にはそれほど強くないのか？←Globalなsimilarityには確かに弱そう）
Related Workがおもしろい。Similarity basedなkernelがいくつか紹介されている。walks or paths (Borgwardt & Kriegel), limited-sized substructures (Horváth et al. 2004) , subtree (Shervashidze & Borgwardt 2009)など
kernelはhand-craftedなので大変だねという話
Metric Learningというのがあるらしい。2点間の距離を学習するらしい

Deep Graph Similarity Learning

Embedding models

要はベクトルを出力するモデル。事前に各グラフについてベクトル化しておくとクエリごとが楽。Encoder, Propagator, Aggregatorにわかれる。

f:id:xuzijian629:20190807053029p:plain f:id:xuzijian629:20190807053032p:plain

Encoder: 頂点ラベル（イテレーションごとに異なる）、辺ラベル（イテレーション間で同じ）を初期化

Propagator: $f_{message}$ とは、頂点 $j$ から頂点 $i$ へ向かう情報であり、2頂点のラベルと、辺ラベルでupdate。頂点ラベルは、その頂点のラベルとその頂点に向かうすべての頂点からのメッセージでupdate

Aggregator: $T$ イテレーションのあと、各ノードの特徴量をaggregateする。aggregateという単語ややこしいな

Graph Matching Networks

Embedding modelのpropagatorにおいて $f_{match}$ というのが増えた。2つのグラフの $2 n_1 n_2$ 個の組合せについて $f_{match}$ を計算する。ノードラベルのアップデートには、メッセージの他に、これらの情報を加えてアップデートする。 f:id:xuzijian629:20190807055128p:plain

感想

例によってなんでうまくいくか全然イメージできないな。まあうまくいかないイメージもできないんだけど。discriminative powerについてWL test以外の観点から調べてみたさがある

2019-08-01

NeurIPSレビューと課題

S2V-DQNがZhuwenの論文に書かれていたよりもずっと強力であることがわかった。

細かく追えていないがaggregateがGNNよりも一般的に見えるし普通にGNNより強いのでは？という気分になってきた。

Weightedの場合も自然にエンコードできるのは強そう。

ところでGNNのWeighted対応版を知らないけどうまくやるにはわりとdrasticな転換が必要そう。

Exploiting Edge Features for Graph Neural Networksという論文があったので読んでいきたい。

機械学習の論文を書くにあたって気をつけること

state-of-the-artを大幅に更新しないとやっぱり見てもらえなさそう
トレードオフを明記するべき。自分のアルゴリズムはどういったケースに弱いか
アルゴリズム自体に革新性がないとやっぱりきつそう

Joeの精進記録

旧：競プロ練習記録

平面グラフで高速に動作するアルゴリズムで一般グラフの場合を学習する

Max-Cut

平面グラフでもNP-hardな問題

Feedback Vertex Set