Graph ML Shallow Embedding 備忘録

# 概要
networkxでgenerateした3つのundirected graphを使っていくつかのshallow embedding手法を確認したときの備忘録である。

- 実施期間: 2022年5月
- 環境：Ubuntu20.04 LTS
- パケージ：networkx, gem, node2vec

## 1. Shallow Embedding手法
Matrix factorization系の[HOPE(High-Order Proximity preserved Embedding)](https://paperswithcode.com/method/hope)とskip-gram系の[node2vec](https://arxiv.org/pdf/1607.00653.pdf)を使ってembeddingを行う。nodeやlinkのvectorized後活用は要件次第なのでここでは言及せず、representation効果を目視(2D)で確認するまでに留める。
相変わらずガラパゴス語のlectureはなく（そもそも探してもないが）、下記が勉強になる。

https://www.youtube.com/watch?v=r12qJZZVtqc&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=13

一部コードは下記から転用させて頂いた。

https://www.amazon.co.jp/gp/product/B092RF8NYM/ref=ppx_yo_dt_b_d_asin_title_o02?ie=UTF8&psc=1

パケージは前者に[gem](https://github.com/palash1992/GEM)を、後者に[node2vec](https://github.com/eliorc/node2vec)を使用する。
ただしnode2vecが期待するnetworkxは>=2.5でありgemのそれは2.4であるため共存させるとconflictが発生する。今回は最新の2.8を入れgemはダメ元だったが、本投稿程度であればgemの動作に問題はなかった。

importするパケージは下記となる。

```python
import numpy as np
import pandas as pd
# import pandas_profiling as pdp
import networkx as nx
import matplotlib.pyplot as plt
import plotly.express as px
import statistics
import powerlaw
import tqdm
from gem.embedding.hope import HOPE
from node2vec import Node2Vec
from node2vec.edges import AverageEmbedder
from node2vec.edges import HadamardEmbedder
```

## 2. グラフモデル
各graphについて下記の関数でザックリEDAする。

```python
def eda(G):
    num_nodes = len(G.nodes())
    num_edges = len(G.edges())
    degree_lst = [G.degree[n] for n in range(num_nodes)]
    degree_lst.sort()
    degree_arr = np.array(degree_lst)

    print(f'total_nodes: {num_nodes}')
    print(f'total_edges: {num_edges}')    # {np.sum(degree_lst)}')
    print(f'max_degree: {np.max(degree_lst)}')
    print(f'median_degree: {statistics.median(degree_lst)}')
    print('dencity = {:.5f}'.format(num_edges/(num_nodes*(num_nodes-1))))

    fit = powerlaw.Fit(degree_lst)
    print('ganma = {:.5f}'.format(fit.power_law.alpha))
    print(f'ganma(min): {fit.power_law.xmin}')

    hetero_param = sum(degree_arr**2)/num_nodes/(sum(degree_arr)/num_nodes)**2
    print('Heterogeneity param = {:.5f}'.format(hetero_param))
    
    df_st = pd.DataFrame({'node' : G.nodes(),
                    'centrality': nx.centrality.betweenness_centrality(G).values(),
                    'clustering': nx.clustering(G).values(),
                    'pagerank': nx.pagerank(G, alpha=0.9).values(),
                    'degree': np.array(nx.degree(G))[:, 1]})
    
    degree_lst = sorted(degree_lst, reverse=True)
    plt.subplots(figsize=(4, 4))
    plt.xscale("log")
    plt.xlabel("degree")
    plt.yscale("log")
    plt.ylabel("number of nodes")
    plt.plot(degree_lst)
    plt.show()
    
    return df_st
```


下記の3つのgraphについてembeddingを行う。
(A) Barbell
見た目わかりやすい、両端がclicueになっているGraph。

```python
G = nx.barbell_graph(m1=7, m2=4)
plt.subplots(figsize=(8, 8))
nx.draw_spring(G, nodelist=G.nodes(),
                   cmap=plt.cm.rainbow,
                   alpha=0.8, with_labels=True)
plt.show()

df_wk1 = eda(G)
```
![Screenshot from 2022-05-05 10-23-34.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/f9fa5985-7b78-d12e-fd2d-4506bec0ce77.png)
![Screenshot from 2022-05-05 10-24-26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/2060776e-0263-37dc-01a4-1c025386f6c2.png)

(B) SBM(Stochastic Block Model)
擬似的に生成したcommunityがどのように表現されるか確認する。
node 0~14, 15~29, 30~59がそれぞれcommunityを成す。

```python
sizes = [15, 15, 30]
probs = [[0.25, 0.05, 0.02], [0.05, 0.35, 0.07], [0.02, 0.07, 0.40]]
G = nx.stochastic_block_model(sizes, probs, seed=123)
plt.subplots(figsize=(12, 12))
nx.draw_spring(G, nodelist=G.nodes(),
                   cmap=plt.cm.rainbow,
                   alpha=0.8, with_labels=True)
plt.show()

df_wk1 = eda(G)
```
![Screenshot from 2022-05-05 10-22-18.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/c552f252-6da7-1788-b837-0f3f4e7279ee.png)
![Screenshot from 2022-05-05 10-25-14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/d4f7dba1-94a0-acaa-a8ac-2b10ca40f2b3.png)

(C) Barabasi Albert Graph
scale-freeなgraphがどのように表現されるか確認する。

```python
G = nx.barabasi_albert_graph(60, 6, seed=123)
plt.subplots(figsize=(12, 12))
nx.draw_spring(G, nodelist=G.nodes(),
                   cmap=plt.cm.rainbow,
                   alpha=0.8, with_labels=True)
plt.show()

df_wk1 = eda(G)
```
![Screenshot from 2022-05-05 10-26-47.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/9193bd2b-3895-a0e8-7777-fae3d5d1fa10.png)
![Screenshot from 2022-05-05 10-26-09.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/08856615-e5fa-bfa1-d3ba-03106021ca04.png)

## 3. HOPE
全node pair(v_source, v_target)間のsimilarity matrixはdirected graphに対応するためsource/target embeddingのconcatと対比(Loss)される。従い、例えばsource/target embedding matrixがそれぞれd=2の場合、similarity matrixのそれはd=2+2=4でなければならない。そのsimilarity matrixはlink predictionの各手法が適用可能だが、HOPEのpaperではAdamic-Adarが使用されているらしい。
Gにgraphを代入後、下記を実行する。

```python
gf = HOPE(d=4, beta=0.01)
gf.learn_embedding(G)
embeddings = gf.get_embedding()

# Plotlyで描画するためDataFrameにする
arr = embeddings[:,0:2]
df_wk2 = pd.DataFrame(data=arr, columns=['v0', 'v1'])
df_eda = pd.concat([df_wk1, df_wk2], axis=1, join='outer')
```
(A) Barbell
gf.get_embedding()の戻りは各nodeで2D+2D=4Dとなる。例えばBarbellではこのように戻る。

![Screenshot from 2022-05-05 11-27-06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/001cb43e-e254-fde3-8bb6-a7c9fa1ede4c.png)

undirected-graphのため、2D（1,2列目）と2D（3,4列目）の中身は等しくなり、各nodeは最初の２列で表現される。
directed-graphであれば4Dなので図で確認できない。

```python
fig = px.scatter(df_eda, x='v0', y='v1', text='node', color='degree')   # , hover_data=['node']
fig.update_traces(textposition='top center')
fig.show()
```
![Screenshot from 2022-05-05 12-31-00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/bc19725a-240d-04dc-356e-e022e7177b49.png)
barbell両端のclicueがv0方向で区分されている。

残り2graphは結果のみ掲載する。

(B) SBM
![Screenshot from 2022-05-05 12-01-55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/0b7153ff-0116-9436-5ba6-5027a2e7965b.png)
前述の通り、node 0~14, 15~29, 30~59がそれぞれcommunityを成しているが、おおよそ分離することができている。graph metricsは適当にdegreeとしたが、これもきれいに分けることができているように見える。

(C) Barabasi Albert Graph
![Screenshot from 2022-05-05 11-55-32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/8c621131-7a7f-3087-a9ac-2779a06e9888.png)
例えばPageRankによるランクは下記だが、図と比較するとv1方向に表現されていることがわかる。v0方向も意味ありげだが、何を表現しているかわからなかった。
![Screenshot from 2022-05-05 11-59-48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/b8e171df-3ce0-82ab-5e74-221765b99ce1.png)

```python
print('Top 10')
print(df_wk1.sort_values('pagerank', ascending=False).head(10))
print('\nBottom 10')
print(df_wk1.sort_values('pagerank').head(10))
```

## 4. Node2Vec
インスタンス作成時に入力Graphのトポロジに沿いランダムに横/縦方向に移動しながら(Breadth/Depth-First Search)、任意長のwalks(node列)を作成する。横/縦の選択確率は引数としてp,qパラメータで指定できるがDefaultが推奨されている。
![Screenshot from 2022-05-05 15-41-29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/016c07b5-d84b-f58e-0260-06b6ad0101a6.png)
![Screenshot from 2022-05-05 15-41-43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/cde76766-f2b3-04aa-ca5a-a2a5cdcfaeed.png)
参照：https://arxiv.org/pdf/1607.00653.pdf

このwalksをWord2VecにおけるDocumentsとしている。Document化したwalksはgensimのword2vecのskip-gramを使用し、構成nodes(wordsに相当)のvectorizeを行っている。従い、skip-gramで指定するパラメータを同様に指定する必要があるが、NLPを知っていればスッと理解できる。
ここでは目視確認のため2Dでembeddingするが、example.pyではnode数が100のrandom graphに対して下記のように設定している。

```python
graph = nx.fast_gnp_random_graph(n=100, p=0.5)
node2vec = Node2Vec(graph, dimensions=64, walk_length=30, num_walks=200, workers=4)
model = node2vec.fit(window=10, min_count=1, batch_words=4)
```

Gにgraphを代入後、下記を実行する。

```python
node2vec = Node2Vec(G, dimensions=2)
model = node2vec.fit(window=10)

df_wk2 = pd.DataFrame()
for x in G.nodes():
    v = model.wv.get_vector(str(x))
    df_wk2.loc[x, "v0"] = v[0]
    df_wk2.loc[x, "v1"] = v[1]
    df_wk2.loc[x, "v2"] = v[2]    
df_eda = pd.concat([df_wk1, df_wk2], axis=1, join='outer')
```

(A) Barbell
![Screenshot from 2022-05-05 14-45-55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/cdbffb66-fd1e-294e-cf4c-9377d1f821f7.png)

(B) SBM
![Screenshot from 2022-05-05 14-47-39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/990e4604-2b9d-3c79-7c8e-4bb88bb11277.png)

(C) Barabasi Albert Graph
![Screenshot from 2022-05-05 14-48-37.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/06d1e24a-4553-e54c-6c71-aaa09508feeb.png)
分かりづらいので3Dでembeddingし直した。

```python
fig = px.scatter_3d(df_eda, x='v0', y='v1', z='v2',
                    text='node', color='degree',height=500)
fig.update_traces(textposition='top center')
fig.show()
```
![Screenshot from 2022-05-05 15-01-38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/799f5dd1-cf6e-5ba3-237d-8ff538488903.png)
degreeの大きなNodeは中心に寄っているように見えるが、全体に判然としない。

## 5. Edge2Vec
node2vecパケージを使えばEdgesもembeddingできる。Node2Vecの流れでDoc2Vecに相当する。
nodeのmetricsは使えないのでLink Predictionのpreferential attachmentのスコアで代用する。
Gにgraphを代入後、下記を実行する。

```python
edges_embs = AverageEmbedder(keyed_vectors=model.wv)
# edges_embs = HadamardEmbedder(keyed_vectors=model.wv)
lst = []
for x in G.edges():
    preds = nx.preferential_attachment(G, [(x[0], x[1])])
    for _,_,p in preds:
        pa = p
    v = edges_embs[(str(x[0]), str(x[1]))]
    edgename = str(x[0]) + '-' + str(x[1])
    lst.append([edgename, pa, v[0], v[1]])

df_eda = pd.DataFrame(data = lst, columns = ['name', 'pa', 'v0', 'v1'])
```

(A) Barbell
![Screenshot from 2022-05-05 15-17-27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/068d45c5-ca85-9cb0-2d14-63b249b0ff3c.png)

(B) SBM
![Screenshot from 2022-05-05 15-18-15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/f04ea0ca-548c-5d2d-67d7-728f50b7a888.png)


(C) Barabasi Albert Graph
![Screenshot from 2022-05-05 15-15-43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/205257/3d466e06-356f-6aa5-4b20-d360205297f9.png)
Scale-free graphとPAの相性が良いので、PAで区別できているように見える。

以上