Graph Embeddings実践ハンズオン

## Graph Embeddingsとは？

Graph Embeddingsは、グラフ構造（ノードとエッジの関係）を数値ベクトルに変換する技術です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/d3fe3a76-56ad-c70f-bfe6-bdd73c6bd39a.png)


### なぜ必要？

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/4a231102-b8ed-4457-34ec-3a5a853112e5.png)

1. **機械学習との相性**: 従来の機械学習モデルは固定長のベクトルを入力として期待します。Graph Embeddingsを使うことで、グラフデータを機械学習で扱いやすい形に変換できます。
2. **効率的な類似性計算**: ベクトル化することで、ノード間の類似度を簡単に計算できます。
3. **スケーラビリティ**: 大規模なグラフでも効率的に処理が可能です。
4. **特徴抽出**: グラフの構造的特徴を自動的に数値化できます。

### 主なアルゴリズム
- **Node2Vec**: グラフ上のランダムウォークでノードの文脈を学習（今回使用）
- **DeepWalk**: Word2Vecの考え方をグラフに応用した先駆的手法
- **LINE**: 1次と2次の近接性を考慮した埋め込み手法
- **Graph Neural Networks (GNN)**: ニューラルネットワークを使用した最新手法

### Node2Vecの仕組み
Node2Vecは以下のステップで動作します：
1. グラフ上でランダムウォークを実行し、ノードの系列を生成
2. 生成された系列をWord2Vecと同様の方法で学習
3. 各ノードを固定長のベクトルに変換

特徴的なのは、パラメータp（Return Parameter）とq（In-out Parameter）を使って、ランダムウォークの探索戦略を調整できる点です。

## 実装編

### 1. 環境準備
```python
!pip install node2vec
import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from node2vec import Node2Vec
from sklearn.manifold import TSNE
from sklearn.cluster import KMeans
```

### 2. データ準備とグラフ可視化
```python
# Zacharyのカラテクラブデータ
G = nx.karate_club_graph()

plt.figure(figsize=(10, 8))
nx.draw(G, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=10)
plt.title("カラテクラブネットワーク")
plt.show()

print(f"ノード数: {G.number_of_nodes()}")
print(f"エッジ数: {G.number_of_edges()}")
```

このデータセットは、実在した空手道場のメンバー間の交流関係を表しています。
- ノード：道場のメンバー（34人）
- エッジ：メンバー間の交流関係

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/b7de9ff5-62c4-4de5-3d86-564e2e01f8df.png)


### 3. Node2Vec適用

```python
# モデル設定
node2vec = Node2Vec(
    G, 
    dimensions=16,     # 出力ベクトルの次元数
    walk_length=10,    # 1回のランダムウォークの長さ
    num_walks=80,      # 各ノードからのウォーク回数
    p=1,              # Return Parameter
    q=1,              # In-out Parameter
    workers=4         # 並列処理数
)

# 学習
model = node2vec.fit(
    window=10,        # コンテキストウィンドウサイズ
    min_count=1,      # 学習に使用する最小出現回数
    batch_words=4     # バッチサイズ
)

# 結果確認
print("ノード0の埋め込みベクトル（最初の5次元）:")
print(model.wv['0'][:5])
```

#### パラメータの説明
- **dimensions**: 出力される埋め込みベクトルの次元数。大きすぎると過学習、小さすぎると情報損失。
- **walk_length**: 長いほど遠い関係も捉えられる。
- **num_walks**: 多いほど学習データが増える。
- **p (Return Parameter)**
  - 直前のノードに “戻る” 遷移をどの程度抑えるかを制御するパラメータ
  - p < 1 の場合、直前ノードへの「戻り」が起きやすくなる（ループしやすい）
  - p > 1 の場合、直前ノードに戻りにくくなる（遠くへ探索しやすい）
  - p = 1 で「戻り」に対してバイアスがかからない

- **q (In-out Parameter)**
  - ランダムウォークが BFS 的（近所を幅広く見る）か DFS 的（遠くへ踏み込みやすい）かを制御するパラメータ
  - q > 1 だと局所探索（BFS 寄り）になりやすい
  - q < 1 だとより遠くへ踏み込み（DFS 寄り）になりやすい
  - q = 1 で近距離・遠距離のバイアスなし

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/ed5b5878-1524-20c2-2e47-bc99cc930d56.png)

### 4. コミュニティ分析
```python
# 埋め込みベクトル取得
embeddings = np.zeros((G.number_of_nodes(), 16))
for i in range(G.number_of_nodes()):
    embeddings[i] = model.wv[str(i)]

# クラスタリング
kmeans = KMeans(n_clusters=3, random_state=42)
clusters = kmeans.fit_predict(embeddings)

# 可視化
plt.figure(figsize=(12, 8))
colors = ['#FF9999', '#99FF99', '#9999FF']
nx.draw(G, with_labels=True, 
        node_color=[colors[c] for c in clusters], 
        node_size=500)
plt.title("コミュニティ検出結果")
plt.show()

# クラスタごとのメンバー表示
for i in range(3):
    members = [n for n in range(len(clusters)) if clusters[n] == i]
    print(f"クラスタ{i}のメンバー: {members}")
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/0065f1bc-2c10-bea1-4e88-cb9c6c1d533a.png)


### 5. メンバー関係性の可視化
```python
# 2次元圧縮
tsne = TSNE(n_components=2, random_state=42)
node_pos = tsne.fit_transform(embeddings)

# プロット
plt.figure(figsize=(12, 8))
plt.scatter(node_pos[:, 0], node_pos[:, 1], 
           c=[colors[c] for c in clusters])

for i in range(G.number_of_nodes()):
    plt.annotate(str(i), (node_pos[i, 0], node_pos[i, 1]),
                xytext=(5, 5), textcoords='offset points')

plt.title("メンバー関係性マップ")
plt.show()
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/26f44761-063e-8237-a268-5e5859670b29.png)


### 6. 類似メンバー検索機能
```python
def find_similar_members(member_id):
    similar = model.wv.most_similar(str(member_id))
    print(f"\nメンバー{member_id}との関係性Top5:")
    for node, score in similar[:5]:
        print(f"メンバー{node}: 類似度 = {score:.3f}")

# 使用例
member_id = 0  # 0-33の間で変更可能
find_similar_members(member_id)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/b0877e29-4386-252c-8817-5bcbf04e9584.png)

## 実験してみよう！

1. パラメータの調整
   - p, qの値を変えてみる（例：p=0.5, q=2.0）
   - walk_lengthやnum_walksを変更
   - dimensionsを変えてみる

2. クラスタ数の変更
   - KMeansのn_clustersを2や4に変更
   - クラスタリング結果の解釈

3. 分析アイデア
   - 中心的なメンバーの特定
   - サブグループの発見
   - メンバー間の関係性予測

## 応用例

1. ソーシャルネットワーク分析
   - フォロー推薦
   - コミュニティ検出
   - インフルエンサー発見

2. 推薦システム
   - アイテム間の関係性モデリング
   - ユーザー行動の分析
   - 類似アイテムの検索

3. 生体ネットワーク
   - タンパク質相互作用の予測
   - 遺伝子ネットワークの解析
   - 疾病関連性の発見

4. 異常検知
   - 不正アクセスの検出
   - 異常取引の発見
   - システム異常の予測

## まとめ

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2648069/38497951-0d78-c767-af6d-e02fea41aa29.png)

- Graph Embeddingsを使うことで、複雑なグラフ構造を機械学習で扱いやすい形に変換できます
- Node2Vecは直感的で実装が簡単な手法です
- コミュニティ検出や類似性分析など、様々なタスクに応用可能です

## 参考文献
- [node2vec: Scalable Feature Learning for Networks](https://arxiv.org/abs/1607.00653)
- [NetworkXドキュメント](https://networkx.org/)
- [scikit-learnドキュメント](https://scikit-learn.org/)

## 付録：よくあるエラーと対処法

1. メモリエラー
   - walk_lengthやnum_walksを小さくする
   - バッチサイズを調整する

2. 収束しない
   - エポック数を増やす
   - 学習率を調整する

3. 精度が出ない
   - dimensionsを調整する
   - p, qのパラメータチューニング
   - データの前処理を見直す