実例で動かすグラフアルゴリズムとグラフデータベース、04_ノードEmbedding：グラフ機械学習へ

第一回：
https://qiita.com/s_zh/items/3b183e258bcd6506e8cb
第二回：
https://qiita.com/s_zh/items/1b193758965a491e79bc
第三回：
https://qiita.com/s_zh/items/75b129f8279e290fe705

[ファイルはこちら](https://raw.githubusercontent.com/lightondust/topics_by_jupyter_notebook/master/neo4j_graph_04_embedding.ipynb)。

今回使うNode Embedding LibraryはNeo4j Sandboxには搭載されておらず、実行するには無料のNeo4j DesktopかComunity版をインストールする必要があります。

# Node Embeddingについて

今まではPageRankやLouvainアルゴリズムを使って重要なノードを見つけたり、つながりの強いグループを見つけたりしました。

一方でノードやリレーションシップの特徴量を抽出できれば、従来の機械学習手法を適応しやすくなります。例えばアカウントをさまざまな視点で分類したり、属するグループだけではなくアカウント間の関係を数値化したり、グループ間の関係を数値化したり、可視化したりするなど行うことができます。

特別に他の特徴量を用意しなくても繋がりさえあれば全体から見た場合の特徴量を使うことができるのはカラム志向に対してグラフ志向でデータを捉える利点の１つだと思います。

Node Embeddingはノードの特徴を表すベクトルを算出します。NLPで有名なWord2Vecも一種のNode Embeddingとして捉えることもできます。基本的な考え方としてはノード間のリンクを再現できるように各ノードにベクトルを割り当てます。

今回はNeo4j Data Science LibraryのNode Embeddingについて見てみます。

# Neo3j Graph Data Science LibraryとNode Embedding

Neo4j Graph Data Science Libraryはα版でNode Embeddingアルゴリズムを提供しています。

https://neo4j.com/docs/graph-data-science/current/algorithms/node-embeddings/

アルゴリズムの種類としてはWord2Vec流のNode2Vec、ノード属性を活用できるグラフニューラルネットワーク流のGraphSage、そして高速のRandom Projectionが用意されています。

https://neo4j.com/developer/graph-data-science/graph-embeddings/#supported-graph-embeddings

ここではNode2Vecを使います。

# Node Embeddingの算出 

グラフは前回まで使っていた政治家のみのネットワークを流用します。
作成する場合は次のように行います。

```
CALL gds.graph.create.cypher( 
    'follow-net-politicians', 
    'MATCH (g:Group)--(u:User) WITH DISTINCT u RETURN id(u) AS id', 
    'MATCH (:Group)--(u:User)-[r:FOLLOW]->(u2:User)--(:Group) WITH DISTINCT r, u, u2 RETURN id(u) AS source, id(u2) AS target')
```

10次元（node2vec）と3次元(node2vec3d)、4次元(node2vec4d)のEmbeddingをそれぞれ計算して、属性として保存します。
次元数の選び方に関しては、一般的なWord2Vecは数十万〜数百万の単語（ノード）を100~300次元へ落とし込むのが１つの目安になります。
今回は300程度のアカウントなので、あまり高次元にすると過学習が起きやすくなってしまいます。

```
CALL gds.alpha.node2vec.write('follow-net-politicians', 
{embeddingSize: 10,
writeProperty: 'node2vec'})
```

```
CALL gds.alpha.node2vec.write('follow-net-politicians', 
{embeddingSize: 3,
writeProperty: 'node2vec3d'})
```

```
CALL gds.alpha.node2vec.write('follow-net-politicians', 
{embeddingSize: 4,
writeProperty: 'node2vec4d'})
```

# 検証 

作成したEmbeddingを見てみます


```python
import plotly.express as px
import numpy as np
```


```python
from neo4j import GraphDatabase
from tqdm.notebook import tqdm
import json

import pandas as pd
```


```python
auth_path = './data/neo4j_graph/auth.json'
with open(auth_path, 'r') as f:
    auth = json.load(f)

# ローカルの場合は通常 uri: bolt(or neo4j)://localhost:7687, user: neo4j, pd: 設定したもの
# サンドボックスの場合は作成画面から接続情報が見られます
uri = 'neo4j://localhost:7687'
driver = GraphDatabase.driver(uri=uri, auth=(auth['user'], auth['pd']))
```


```python
# Sandboxの場合はこんな感じ
# uri = 'bolt://54.175.38.249:35275'
# driver = GraphDatabase.driver(uri=uri, auth=('neo4j', 'spray-missile-sizing'))
```

## 3d


```python
dim_no = 3
```


```python
with driver.session() as session:
    res = session.run('''
    MATCH (u:User)--(:Group)
    WITH DISTINCT u
    RETURN u.screenName as screen_name, u.name as name, u.louvainCommunityUndirected as community, u.node2vec3d as embedding
    ''')
```


```python
res_df = pd.DataFrame([r.data() for r in res])
res_df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>screen_name</th>
      <th>name</th>
      <th>community</th>
      <th>embedding</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>tadamori_oshima</td>
      <td>大島理森</td>
      <td>3</td>
      <td>[-0.20086176693439484, 0.9452930688858032, 1.1...</td>
    </tr>
    <tr>
      <td>1</td>
      <td>YAMASHITA_OK</td>
      <td>山下たかし</td>
      <td>3</td>
      <td>[-0.3143966794013977, 0.4608628451824188, 1.31...</td>
    </tr>
    <tr>
      <td>2</td>
      <td>andouhiroshi</td>
      <td>あんどう裕(ひろし)衆議院議員(自民党 京都６区 )</td>
      <td>3</td>
      <td>[-0.03988641873002052, 0.4570828974246979, 1.2...</td>
    </tr>
    <tr>
      <td>3</td>
      <td>jimin_koho</td>
      <td>自民党広報</td>
      <td>3</td>
      <td>[-0.564670205116272, 0.5222573280334473, 1.403...</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Matsukawa_Rui</td>
      <td>松川るい =自民党=</td>
      <td>3</td>
      <td>[-0.5284397602081299, 0.6824808716773987, 1.36...</td>
    </tr>
  </tbody>
</table>
</div>



Node Embeddingは関係のの近いノードを近い方向に配置し、ノードの重要性（出現頻度など）を絶対値に反映しているので、可視化する時にすべてのベクトルの大きさを１に揃えたほうがわかりやすいです。


```python
def renorm_vector(v):
    norm = np.sqrt(sum([c**2 for c in v]))
    return np.array(v) / norm
```


```python
ax_columns = ['x{}'.format(i) for i in range(1, dim_no+1)]

# res_df[ax_columns] = res_df.embedding.apply(pd.Series)

res_df[ax_columns] = res_df.embedding.apply(lambda x: pd.Series(renorm_vector(x)))
```


```python
res_df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>screen_name</th>
      <th>name</th>
      <th>community</th>
      <th>embedding</th>
      <th>x1</th>
      <th>x2</th>
      <th>x3</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>tadamori_oshima</td>
      <td>大島理森</td>
      <td>3</td>
      <td>[-0.20086176693439484, 0.9452930688858032, 1.1...</td>
      <td>-0.132467</td>
      <td>0.623415</td>
      <td>0.770588</td>
    </tr>
    <tr>
      <td>1</td>
      <td>YAMASHITA_OK</td>
      <td>山下たかし</td>
      <td>3</td>
      <td>[-0.3143966794013977, 0.4608628451824188, 1.31...</td>
      <td>-0.220553</td>
      <td>0.323301</td>
      <td>0.920235</td>
    </tr>
    <tr>
      <td>2</td>
      <td>andouhiroshi</td>
      <td>あんどう裕(ひろし)衆議院議員(自民党 京都６区 )</td>
      <td>3</td>
      <td>[-0.03988641873002052, 0.4570828974246979, 1.2...</td>
      <td>-0.030714</td>
      <td>0.351969</td>
      <td>0.935508</td>
    </tr>
    <tr>
      <td>3</td>
      <td>jimin_koho</td>
      <td>自民党広報</td>
      <td>3</td>
      <td>[-0.564670205116272, 0.5222573280334473, 1.403...</td>
      <td>-0.352781</td>
      <td>0.326283</td>
      <td>0.876975</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Matsukawa_Rui</td>
      <td>松川るい =自民党=</td>
      <td>3</td>
      <td>[-0.5284397602081299, 0.6824808716773987, 1.36...</td>
      <td>-0.327500</td>
      <td>0.422967</td>
      <td>0.844892</td>
    </tr>
  </tbody>
</table>
</div>



ここで比較するために以前計算していたクラスタリングを取得しています。
各クラスタに入っているノード数は次のようになります。


```python
res_df.community = res_df.community.astype('category')
res_df.community.value_counts()
```




    174    127
    3      107
    169     66
    120     29
    257     17
    Name: community, dtype: int64




```python
fig = px.scatter_3d(res_df,  
                    x="x1",  
                    y="x2",   
                    z='x3', 
                    text="name",  
                    color='community',  
                    log_x=False,  
                    size_max=60)

fig.update_traces(textposition='top center')

fig.update_layout(
    height=800,
    title_text=''
)

fig.show()
```


```python
# plotを保存する場合
html_path = './data/neo4j_graph/politician_03_3dembedding.html'
with open(html_path, 'w') as f:
    f.write(fig.to_html())
```

![politician_04_3d.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/d02b7ce2-dc2b-8dd2-18bb-6b97b3ec9836.png)



おおむね自民党系と民主党系が左右に固まり、維新系が真ん中にある構図が変わりませんでした。
一方でマイナークラスタはトップ３に埋もれる形になりました。
これは元データに対して次元圧縮をしすぎたため、表現力が足りないためと思われます。


```python
# figf = px.data.gapminder().query("year==2007 and continent=='Americas'")

# fig = px.scatter(res_df,  
#                  x="x1", 
#                  y="x2", 
#                  text="name", 
#                  color='community', 
#                  log_x=False, 
#                  size_max=60)

# fig.update_traces(textposition='top center')

# fig.update_layout(
#     height=800,
#     title_text=''
# )

# fig.show()
```

## 4d

では4dでどうなるかをみてみます。


```python
dim_no = 4
```


```python
with driver.session() as session:
    res = session.run('''
    MATCH (u:User)--(:Group)
    WITH DISTINCT u
    RETURN u.screenName as screen_name, u.name as name, u.louvainCommunityUndirected as community, u.node2vec4d as embedding
    ''')
```


```python
res_df = pd.DataFrame([r.data() for r in res])
res_df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>screen_name</th>
      <th>name</th>
      <th>community</th>
      <th>embedding</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>tadamori_oshima</td>
      <td>大島理森</td>
      <td>3</td>
      <td>[-0.9669536352157593, -0.4772112965583801, -0....</td>
    </tr>
    <tr>
      <td>1</td>
      <td>YAMASHITA_OK</td>
      <td>山下たかし</td>
      <td>3</td>
      <td>[-0.944596529006958, -0.29907843470573425, -0....</td>
    </tr>
    <tr>
      <td>2</td>
      <td>andouhiroshi</td>
      <td>あんどう裕(ひろし)衆議院議員(自民党 京都６区 )</td>
      <td>3</td>
      <td>[-0.9364525675773621, -0.093632273375988, -0.8...</td>
    </tr>
    <tr>
      <td>3</td>
      <td>jimin_koho</td>
      <td>自民党広報</td>
      <td>3</td>
      <td>[-1.0234124660491943, -0.5828015208244324, -0....</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Matsukawa_Rui</td>
      <td>松川るい =自民党=</td>
      <td>3</td>
      <td>[-0.9714489579200745, -0.48148995637893677, -0...</td>
    </tr>
  </tbody>
</table>
</div>



Node Embeddingは関係のの近いノードを近い方向に配置し、ノードの重要性（出現頻度など）を絶対値に反映しているので、可視化する時にすべてのベクトルの大きさを１に揃えたほうがわかりやすいです。


```python
def renorm_vector(v):
    norm = np.sqrt(sum([c**2 for c in v]))
    return np.array(v) / norm
```


```python
ax_columns = ['x{}'.format(i) for i in range(1, dim_no+1)]

# res_df[ax_columns] = res_df.embedding.apply(pd.Series)
res_df[ax_columns] = res_df.embedding.apply(lambda x: pd.Series(renorm_vector(x)))

res_df.community = res_df.community.astype('category')
```


```python
res_df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>screen_name</th>
      <th>name</th>
      <th>community</th>
      <th>embedding</th>
      <th>x1</th>
      <th>x2</th>
      <th>x3</th>
      <th>x4</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>tadamori_oshima</td>
      <td>大島理森</td>
      <td>3</td>
      <td>[-0.9669536352157593, -0.4772112965583801, -0....</td>
      <td>-0.626852</td>
      <td>-0.309364</td>
      <td>-0.545948</td>
      <td>-0.461835</td>
    </tr>
    <tr>
      <td>1</td>
      <td>YAMASHITA_OK</td>
      <td>山下たかし</td>
      <td>3</td>
      <td>[-0.944596529006958, -0.29907843470573425, -0....</td>
      <td>-0.678253</td>
      <td>-0.214749</td>
      <td>-0.628372</td>
      <td>-0.314651</td>
    </tr>
    <tr>
      <td>2</td>
      <td>andouhiroshi</td>
      <td>あんどう裕(ひろし)衆議院議員(自民党 京都６区 )</td>
      <td>3</td>
      <td>[-0.9364525675773621, -0.093632273375988, -0.8...</td>
      <td>-0.736264</td>
      <td>-0.073616</td>
      <td>-0.657714</td>
      <td>-0.141094</td>
    </tr>
    <tr>
      <td>3</td>
      <td>jimin_koho</td>
      <td>自民党広報</td>
      <td>3</td>
      <td>[-1.0234124660491943, -0.5828015208244324, -0....</td>
      <td>-0.691638</td>
      <td>-0.393866</td>
      <td>-0.530964</td>
      <td>-0.290831</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Matsukawa_Rui</td>
      <td>松川るい =自民党=</td>
      <td>3</td>
      <td>[-0.9714489579200745, -0.48148995637893677, -0...</td>
      <td>-0.671192</td>
      <td>-0.332670</td>
      <td>-0.580522</td>
      <td>-0.319101</td>
    </tr>
  </tbody>
</table>
</div>




```python
fig = px.scatter_3d(res_df,  
                    x="x1",  
                    y="x2",   
                    z='x4', 
                    text="name",  
                    color='community',  
                    log_x=False,  
                    size_max=60)

fig.update_traces(textposition='top center')

fig.update_layout(
    height=800,
    title_text=''
)

fig.show()
```

![politician_04_4d_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/e15d129f-aca1-4427-72e3-ed898a6cf803.png)

角度を変えて

![politician_04_4d_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/fcbcf27e-3ef7-6df1-9d31-85e4983cd421.png)

自民系は比較的に固まっていて、民主形はかなり広がりがあり、維新系は自民寄りになっていることが見て取れます。

## 10d

10dのEmbeddingでクラスタリングしてみます。


```python
from sklearn.cluster import KMeans
```


```python
with driver.session() as session:
    res = session.run('''
    MATCH (u:User)--(:Group)
    WITH DISTINCT u
    RETURN u.screenName as screen_name, u.name as name, u.louvainCommunityUndirected as community, u.node2vec as embedding
    ''')
```


```python
res_df = pd.DataFrame([r.data() for r in res])
```


```python
ax_columns = ['x{}'.format(i) for i in range(1, 11)]

# res_df[ax_columns] = res_df.embedding.apply(pd.Series)

res_df[ax_columns] = res_df.embedding.apply(lambda x: pd.Series(renorm_vector(x)))
```


```python
res_df.head()
```




<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>screen_name</th>
      <th>name</th>
      <th>community</th>
      <th>embedding</th>
      <th>x1</th>
      <th>x2</th>
      <th>x3</th>
      <th>x4</th>
      <th>x5</th>
      <th>x6</th>
      <th>x7</th>
      <th>x8</th>
      <th>x9</th>
      <th>x10</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>tadamori_oshima</td>
      <td>大島理森</td>
      <td>3</td>
      <td>[0.8451248407363892, -0.3527873158454895, 0.79...</td>
      <td>0.461382</td>
      <td>-0.192599</td>
      <td>0.433067</td>
      <td>-0.204804</td>
      <td>-0.220397</td>
      <td>-0.109164</td>
      <td>0.262750</td>
      <td>0.550687</td>
      <td>-0.237711</td>
      <td>-0.176773</td>
    </tr>
    <tr>
      <td>1</td>
      <td>YAMASHITA_OK</td>
      <td>山下たかし</td>
      <td>3</td>
      <td>[-0.21574953198432922, -0.9915562868118286, 0....</td>
      <td>-0.103789</td>
      <td>-0.477001</td>
      <td>0.165211</td>
      <td>-0.106283</td>
      <td>-0.260988</td>
      <td>-0.330459</td>
      <td>0.587693</td>
      <td>0.288013</td>
      <td>-0.341218</td>
      <td>0.032010</td>
    </tr>
    <tr>
      <td>2</td>
      <td>andouhiroshi</td>
      <td>あんどう裕(ひろし)衆議院議員(自民党 京都６区 )</td>
      <td>3</td>
      <td>[0.48249784111976624, -0.26339074969291687, -0...</td>
      <td>0.340378</td>
      <td>-0.185809</td>
      <td>-0.154462</td>
      <td>-0.271198</td>
      <td>-0.215974</td>
      <td>-0.281920</td>
      <td>0.519558</td>
      <td>0.533754</td>
      <td>-0.059092</td>
      <td>-0.260310</td>
    </tr>
    <tr>
      <td>3</td>
      <td>jimin_koho</td>
      <td>自民党広報</td>
      <td>3</td>
      <td>[0.44367820024490356, -0.663674533367157, 0.38...</td>
      <td>0.236184</td>
      <td>-0.353295</td>
      <td>0.203981</td>
      <td>-0.113193</td>
      <td>-0.199367</td>
      <td>-0.334902</td>
      <td>0.628517</td>
      <td>0.415378</td>
      <td>-0.167158</td>
      <td>-0.132505</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Matsukawa_Rui</td>
      <td>松川るい =自民党=</td>
      <td>3</td>
      <td>[0.19990792870521545, -0.42390283942222595, 0....</td>
      <td>0.115597</td>
      <td>-0.245123</td>
      <td>0.126030</td>
      <td>-0.102652</td>
      <td>-0.334126</td>
      <td>-0.305738</td>
      <td>0.538014</td>
      <td>0.570700</td>
      <td>-0.282578</td>
      <td>0.002598</td>
    </tr>
  </tbody>
</table>
</div>




```python
res_df.community = res_df.community.astype('category')
res_df.community.value_counts()
```




    174    127
    3      107
    169     66
    120     29
    257     17
    Name: community, dtype: int64



Louvainと比較するためにクラス多数を同じ５とします。


```python
k_m = KMeans(n_clusters=5)
```


```python
embedding_arr = np.array([l for l in res_df.embedding])
embedding_arr.shape
```




    (346, 10)




```python
k_m.fit_predict(embedding_arr)
res_df['k_community'] = res_df.embedding.apply(lambda x: k_m.predict(np.array(x).reshape(1, -1))[0])
```


```python
for i in res_df.k_community.value_counts().items():
    print(i)
    print(res_df[res_df.k_community == i[0]].community.value_counts())
```

    (0, 130)
    174    110
    257      9
    169      9
    3        2
    120      0
    Name: community, dtype: int64
    (1, 117)
    3      100
    169     12
    257      2
    174      2
    120      1
    Name: community, dtype: int64
    (2, 62)
    169    43
    174    12
    257     4
    120     2
    3       1
    Name: community, dtype: int64
    (3, 35)
    120    26
    3       4
    257     2
    169     2
    174     1
    Name: community, dtype: int64
    (4, 2)
    174    2
    257    0
    169    0
    120    0
    3      0
    Name: community, dtype: int64


概ね自民、民主、維新系のまま、すこし趣の違う感じになりました。

### クラスタ数について

Embeddingしてからクラスタリングを行う利点のひとつはクラスタ数を調整できることです。
ここでは各クラス多数におけるフィット具合を見てみます。


```python
import matplotlib.pyplot as plt
```


```python
models = []
for i in tqdm(range(2, 30)):
    k_m = KMeans(n_clusters=i)
    k_m.fit(embedding_arr)
    models.append(k_m)
```


    HBox(children=(IntProgress(value=0, max=28), HTML(value='')))


    



```python
x = [i for i in range(2, 30)]
y = np.array([k.inertia_ for k in models])
# plt.plot(x, y)
# plt.plot([i for i in range(2, 15)], np.log(np.array([k.inertia_ for k in models])))

px.line(x=x, y=y)
```

![politician_04_kmean.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/239303/e16cd6ff-aef5-9d61-26a9-a43de80c7e09.png)


このグラフはこれは各点が自分が所属しているクラスタの中心までの距離の平均を表していて、クラスタ数が多くなれば距離が減りますが、その分粒度が細かくなります。
クラスタ数を増やしても距離があまり減らなくなるところが一般的にいいとされています。
この場合だと５と１０になるでしょうか。