面白いデータを探して

適当に書く。間違えていたら教えてください。

Graph Convolutionを実装してみる

Graph Convolutional Networkを実装してみました。

Graph Convolutionについて

Graph Convolutionはグラフ構造の上に定義された畳み込み演算です。これを重ねたものをGraph Convolutional Network(以下GCN)原著論文は下のURLです。
https://arxiv.org/abs/1609.02907

です。日本語での解説は以下のページなどが詳しいです。

今回の実装内容

今回はGCNの中でも"Variational graph auto-encoder"*1で提案されている"Non-probabilistic graph auto-encoder (GAE) model"を実装しました。要するに、グラフに対するConvolutional auto-encoderです。

デコーダーはエンコーダーの出力 Z = \mathrm{GCN}(X)に対して出力を

 A' = \sigma (Z Z^\mathrm{T})

で定義します。( \sigma()シグモイド関数)。これを元のグラフの隣接行列 Aに近づけます。

GCN側については各層( i層目)は以下のような計算を行います。

 H_{i+1} = \sigma (\tilde{A} H_i W_i)

ここで \tilde{A} = D^{-\frac{1}{2}} A D^{-\frac{1}{2}}( Aは隣接行列、 Dは次元行列)で H_i i層目の出力、 W_i i層目の重みです。

今回の実装では2層のConvolution層からなるGCNを実装してみます。すなわち

 A' = \tilde{A} \sigma (\tilde{A} X W_1) W_2

となり、lossは
 ||A - A'||^2_2

となります。

inputの X単位行列(各ノードのone hot表現)とし、drop outなどは使いませんでした。
また、対象としてはkarate clubという小規模なグラフを使いました。

コード

# -*- coding: utf-8 -*-

import tensorflow as tf
import networkx as nx
# %matplotlib inline
import matplotlib.pyplot as plt
import math
import numpy as np

# karate club graphの描画

G = nx.karate_club_graph()
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos=pos)
plt.show()
# クラスごとに色分け
color = list()
for node in G.nodes:
  if G.node[node]["club"] == "Mr. Hi":
    color.append("r")
  elif G.node[node]["club"] == "Officer":
    color.append("b")
nx.draw_networkx(G, pos=pos, node_color=color)
plt.show()

# A~の準備
# networkxで行列を出すとscipy.sparseで出力されます
A = nx.adjacency_matrix(G).astype("float32")
D = nx.laplacian_matrix(G).astype("float32") + A
for i in range(G.number_of_nodes()):
  D[i, i] = 1 / math.sqrt(D[i, i])
A_chil_ = D.dot(A.dot(D))

# scipy.sparse -> tf.SparseTensorへの変換のための関数
def convert_sparse_matrix_to_sparse_tensor(X):
    coo = X.tocoo()
    indices = np.mat([coo.row, coo.col]).transpose()
    return tf.SparseTensor(indices, coo.data, coo.shape)

# GCN layerを出力する関数
def GCN_layer(A, layer_input, W, activation):
  if activation == None:
    return tf.matmul(tf.sparse.matmul(A, layer_input), W)
  else:
    return activation(tf.matmul(tf.sparse.matmul(A, layer_input), W))

d = 2 # 最終出力の次元
hidden_size = 8 # 1層目の出力サイズ
learning_rate = 1e-3 # 学習率

# モデル定義
X = tf.placeholder(tf.float32, shape=[G.number_of_nodes(), G.number_of_nodes()])
A_chil = convert_sparse_matrix_to_sparse_tensor(A_chil_)
W_1 = tf.Variable(tf.random_normal([G.number_of_nodes(), hidden_size]), dtype=tf.float32)
W_2 = tf.Variable(tf.random_normal([hidden_size, d]), dtype=tf.float32)

L1 = GCN_layer(A_chil, X, W_1, tf.nn.relu)
L2 = GCN_layer(A_chil, L1, W_2, None)

A_rec = tf.sigmoid(tf.matmul(L2, tf.transpose(L2)))

loss = tf.nn.l2_loss(tf.sparse.add(-1 * A_rec, A_chil))
train = tf.train.AdamOptimizer(learning_rate).minimize(loss)

# 学習部分
epoch = 1000
x = np.identity(G.number_of_nodes(), dtype="float32")
with tf.Session() as sess:
  sess.run(tf.global_variables_initializer())
  loss_list = list()
  for e in range(epoch):
    # 学習
    tloss, _ = sess.run([loss, train], feed_dict={X:x})
    loss_list.append(tloss)
    # 学習結果の出力
    if (e+1) % 100 == 0:
      emb = sess.run(L2, feed_dict={X:x})
      fig, ax = plt.subplots()
      for i in range(G.number_of_nodes()):
        ax.scatter(emb[i][0], emb[i][1], color=color[i])
      plt.title("epoch" + str(e+1))
      plt.show()
      plt.title("epoch" + str(e+1))
      nx.draw_networkx(G, pos=emb, node_color=color)
      plt.show()
# lossの推移を見る
plt.plot(list(range(epoch)), loss_list)
plt.title("loss")
plt.show()

実行結果

f:id:netres:20190104154128p:plain
loss
lossの推移についてはこんな感じ。

f:id:netres:20190104154204p:plain
200 epoch回したときのエンコーダーの出力
200 epoch回したときの感じだとまだ良くわからない。

f:id:netres:20190104154258p:plain
700エポック回したときのエンコーダーの出力
700エポック回したときの結果。割と構造情報を捉えられている気がする。

実行時間はgoogle colabのアクセラレータをgpu設定で2秒かからないくらい。cpuでも5秒かからないくらいだった。

まとめ

今回は簡単にGCNを実装してみた。テキスト分類など色々なタスクに応用されてきているそうなので、時間を見て試してみようと思う。

*1:Kipf, Thomas N., and Max Welling. "Variational graph auto-encoders." arXiv preprint arXiv:1611.07308 (2016).