この存在を知らなくて, gcp上ではvimで編集してた.

Hostnameに外部IPアドレス入れてユーザ名指定して, ~/.sshの中にあるkeyのpathを書けば普通にいけたらしい.

これでawsと同じようにgcp内でもatom開けるようになった.

良かった良かった.

2018-11-15

SpotLight: Detecting Anomalies in Streaming Graphs

KDD 2018 | SpotLight: Detecting Anomalies in Streaming Graphs

読んだ.

2018-10-07

Neural Relational Inference for Interacting Systems

タイトル : Neural Relational Inference for Interacting Systems

著者
- Thomas N. Kipf (1)
- Ethan Fetaya (2, 3)
- Kuan-Chieh Wang (2, 3)
- Max Welling (1, 4)
- Richard Zemel (2, 3, 4)

University of Amsterdam
University of Toronto
Vector Institute
Canadian Institute for Advanced Research (CIFAR)

↓本論文

https://arxiv.org/pdf/1802.04687.pdf (ICML2018)

概要

いくつかの物体から構成されているグループと見なせるような動的な物体 (粒子とか?)の相互作用を予測する.

その際に, グループに対して潜在的なグラフネットワークを構築し, その潜在的なグラフ (以下潜在グラフ)上でVAEとグラフニューラルネットワーク (GCNと何が違うのかはあまり分からない, 多分一緒.) を使って推論を行う.

教師なしで学習するが, 優れた性能を示した.

背景

物理学, 生物学, スポーツなどの分野での動的システムは個々の物体が複雑に相互作用しているグループと見なせる.

大抵の場合, 個々の物体間に介在している仕組みは分かっていないので, 難しい.

例としてバスケとかは明らかに他の人に影響されながら個々人の動画が行われている.

頑張ったら''この動きは, この人がこうしたから起きました''といったような説明ができるかもしれない.

他の分野にも応用できるような相互作用の仕組みを明らかにする方法を考えたい.

提案手法

f:id:banana_88:20180824141844p:plain

提案モデルの入出力は以下.

入力
- N個の物体のある時刻tまでの軌道 (速度や位置)
出力
- エッジタイプ (エッジタイプは相互作用のクラスターに相当)

モデルは, 大きく2つに分けられる.

グループの軌道から潜在的な相互作用 (潜在グラフ)を構築するEncoderと, 潜在グラフと時刻tでの物体の情報から時刻t+1での物体の動きを予測するDecoderから成る.

VAE同様にencoderからdecoderに渡す時にサンプリングする過程もある. サンプリングするのは, 以下でも説明するが, エッジの潜在確率変数をサンプリングする.

VAEのモデルとして, 提案モデルを定式化すると, 以下の目的関数を最適化する.

$\begin{equation} \mathcal L = \mathbb{E}_{q_{\phi}(\bf z|x)}[\rm log \it p_{\theta}(\bf x|z)]-\rm KL[\it q_{\theta}(\bf {z|x})|| \it p_{\theta}(\bf {z})], \end{equation}$

ここで, $\bf {x}$ , $\bf {z}$ はそれぞれ, 入力される物体の軌道及び潜在グラフのエッジを表す. 例えば $\bf {z}_{ij}$ は物体 $i, j$ 間のエッジの確率分布になっている (エッジが複数種類考慮されていることに注意).

Encoder

Encoderは入力 $\bf {x}$ について, 物体 $j$ (頂点)に対する埋め込みを作り, 頂点→枝→頂点→枝とし,

得られた枝の特徴量を $\rm softmax$ 関数に通して, 事後分布とする.

頂点→枝→頂点→枝で特徴量を伝搬することで, グラフ全体の特徴量, すなわち相互作用を考慮することが出来る.

頂点→枝のみでは, それは出来ない.

Sampling

今回の手法の場合, エッジの種類を表すone hot ベクトルをサンプリングしてくる, すなわちサンプリングが離散的な値になるので, そのままだと逆伝搬して学習できない.

よって, ここでは離散分布を連続分布に近似する手法, Gumble Softmaxを用いる. 最近結構使われている.

詳細は以下.

[1611.01144] Categorical Reparameterization with Gumbel-Softmax

[1611.00712] The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables

続きはまた気が向いたらまとめる.

実験

参考

2018-09-17

メモ

http://www.kdd.org/kdd2018/accepted-papers/view/large-scale-learnable-graph-convolutional-networks

http://pengcui.thumedialab.com/papers/NE-Hierarchical.pdf

https://www.comp.nus.edu.sg/~xiangnan/papers/sigir18-bipartiteNE.pdf

2018-08-24

Semi-Supervised Classification with Graph Convolutional Networks

タイトル : Semi-Supervised Classification with Graph Convolutional Networks

著者
- Thomas N. Kipf (1)
- Max Welling (1, 2)

1 University of Amsterdam

2 Canadian Institute for Advanced Research (CIFAR)

ICLR2017

Graph系でよく見かける人たち.

↓本論文 [1609.02907] Semi-Supervised Classification with Graph Convolutional Networks (ICLR 2017)

概要

グラフ上のノードを分類する問題で, ラベルが一部にしかついていないような問題を考える. これはグラフの半教師付き学習の枠組みに入る. これまではラベルの情報はグラフラプラシアン正則化として、損失関数の中に入れられていた.

$\begin{equation} \mathcal L = \mathcal L_{0}+\lambda\mathcal L_{reg}, \ \ \ \ \ with \ \mathcal L_{reg} = \sum_{i,j}{A_{ij}||f(X_i)-f(X_j)}||^{2}=f(X)^{T}\Delta f(X), \end{equation}$

$\mathcal L_{0}$ はラベルがついてる部分の損失関数. 注目すべきなのは正則化項として隣接頂点が同じラベルじゃなければペナルティが与えられてる点で, これは隣接頂点は同じラベルになるだろうっていう仮定の正則化だが, 実際ノード間のエッジは必ずしも類似性を表現してるわけではないから, あまりよくない制約を入れてしまっていることになる. そこで,本論文では, グラフ上に直接ニューラルネットワークを構築して損失関数に明示的にグラフベースの正則化を入れない方法を提案する. 提案手法はスペクトラルグラフコンボリューションの一次近接性に着想を得ているらしい →

[0912.3848] Wavelets on Graphs via Spectral Graph Theory (全く読んでいない. ←読んだ(2018年12月), 重要なところはchebyshevの多項式を使って, グラフラプラシアンの対角化を避けて対角化する内容を提案した論文(多分))

(グラフにおける近接性の話は時々でてくる.

Understanding Large Social Networks

[1503.03578] LINE: Large-scale Information Network Embedding この辺りが有名 ) 提案手法は高速で, 大規模実行可能, 半教師付き学習として分類精度及び速度でSOTAを上回る.

背景

ノードの分類問題は重要だけど,ラベルをちょっとしか持ってない場合があり,そういう問題に取り組む.

提案手法

色々な手法が紹介されているが, ここでは論文内で最も優れているとされた手法を載せる.

$\begin{equation} Z = \tilde{D}^{\frac{1}{2}}\tilde{A}\tilde{D}^{\frac{1}{2}}X\Theta, \end{equation}$

ここで, $\tilde{A}, \tilde{D}$ はそれぞれ $\begin{equation}\tilde{A}=A+I_{N}, \tilde{D_{ii}}=\sum_{j}{\tilde{A}_{ij}}, \end{equation}$ で、 $A$ はグラフの隣接行列, $I_{N}$ は単位行列 (グラフ的に考えると, 各ノードの自己ループを表す行列).

$\Theta$ は $C×F$ のパラメータ, $Z$ は $N×F$ の単純に出力結果 ( $C$ が各ノードの特徴ベクトルの次元, $F$ がクラス数, $N$ がサンプル数).

一応これでも何をやってるかは大体分かるが, 多分以下の式の方が分かりやすい. 本論文中で実際に用いられたアーキテクチャ.

$\begin{equation} Z = f(X,A) = \rm{softmax}(\hat{A}\rm{ReLU}(\hat{A}XW^{(0)})W^{(1)}), \end{equation}$

ここで, $\begin{equation} \hat{A} = \tilde{D}^{\frac{1}{2}}\tilde{A}\tilde{D}^{\frac{1}{2}} \end{equation}$ で, これは前もって計算しとく.

各 $W$ は重みパラメータで, 以下の目的関数を小さくするために最適化する.

$\begin{equation} \mathcal L = -{\displaystyle \sum_{l \in \mathcal Y_{L}}}{\displaystyle \sum_{f=1}^{F}}{Y_{lf}\rm{ln}\it{Z_{lf}}}, \end{equation}$

ここで, $\mathcal Y_{L}$ はラベル付きノード集合. 以下論文の画像. f:id:banana_88:20180822204317p:plain

すごい単純に解釈すると, ネットワーク内でそれぞれのノードに各層で共通の重みパラメータを与えてることが, 高速化と大規模実行可能に繋がってると言っている (多分).

実験

実験で用いたデータセットは以下.

引用ネットワークと知識グラフを使っている. f:id:banana_88:20180823163951p:plain

実験結果は以下. f:id:banana_88:20180823164224p:plain

これまでのグラフラプラシアンに基づく方法は, エッジがノードの類似性を示しているという仮定を置いていた (すなわちノード間にエッジがあればその2つのノードは似ているはずという仮定). またDeepWalkとかnode2vecとかもランダムウォークして特徴生成する過程と訓練する過程が分断されてしまって, それぞれ独立に最適化してしまっているという問題があった. 提案手法ではこれらの問題点を克服し, 性能と速度両方の面で優れていた.