線形代数の盲点を解く：行列はグラフ、グラフは行列。エンコーディングで複雑現象を単純化

import numpy as np
import networkx as nx

# グラフを定義：2ノード、1エッジ
G = nx.Graph()
G.add_edge(0, 1)

# グラフ → 行列（隣接行列）に変換
A = nx.to_numpy_array(G)
print(A)
# 出力:
# [[0. 1.]
#  [1. 0.]]

# 行列 → グラフに戻す
G2 = nx.from_numpy_array(A)
print(list(G2.edges()))
# 出力: [(0, 1)]

import scipy.linalg as la
import numpy as np

# ラプラシアン行列の計算
def graph_laplacian(G):
    A = nx.to_numpy_array(G)
    D = np.diag(A.sum(axis=1))  # 次数行列
    L = D - A
    return L

# 5ノードのサンプルグラフ
G = nx.karate_club_graph()
L = graph_laplacian(G)

# 固有値分解（スペクトラル分析）
eigenvalues, eigenvectors = la.eigh(L)

# 2番目に小さい固有値（Fiedler値）= グラフの連結性の強さ
fiedler_value = eigenvalues[1]
print(f"Fiedler値（連結性）: {fiedler_value:.4f}")

# 対応する固有ベクトル = スペクトラルクラスタリングの基底
fiedler_vector = eigenvectors[:, 1]
# 符号に基づいてノードを2クラスタに分類
clusters = (fiedler_vector > 0).astype(int)
print(f"クラスタ割り当て: {clusters[:10]}")

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.data import Data

# グラフデータの定義
# edge_index: エッジリスト（2×E テンソル）
edge_index = torch.tensor([[0, 1, 1, 2],
                            [1, 0, 2, 1]], dtype=torch.long)

# ノード特徴量（4ノード、各3次元）
x = torch.tensor([[-1, 0, 1],
                   [0, 1, -1],
                   [1, -1, 0],
                   [0, 0, 1]], dtype=torch.float)

# グラフオブジェクトの生成
data = Data(x=x, edge_index=edge_index)

# 2層GCNの定義
class GCN(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.conv1 = GCNConv(3, 16)   # 3次元 → 16次元
        self.conv2 = GCNConv(16, 2)    # 16次元 → 2クラス

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

model = GCN()
# このGCNConvの内部では隣接行列との行列積が実行されている

import numpy as np
import networkx as nx

def power_iteration_pagerank(G, damping=0.85, max_iter=100, tol=1e-6):
    """
    PageRankを冪乗法で実装
    G: 有向グラフ（networkx.DiGraph）
    damping: 減衰係数（デフォルト 0.85）
    """
    n = len(G.nodes())
    nodes = list(G.nodes())
    node_idx = {node: i for i, node in enumerate(nodes)}

    # 遷移行列の構築（列方向が正規化されたリンク先）
    A = np.zeros((n, n))
    for node in G.nodes():
        out_edges = list(G.out_edges(node))
        if out_edges:
            for _, target in out_edges:
                A[node_idx[target]][node_idx[node]] = 1.0 / len(out_edges)
        else:
            # ダングリングノード：全ノードに均等にリンク
            A[:, node_idx[node]] = 1.0 / n

    # Googleマトリックス（テレポーテーション項を追加）
    M = damping * A + (1 - damping) / n * np.ones((n, n))

    # 冪乗法（固有ベクトルを反復計算）
    rank = np.ones(n) / n
    for i in range(max_iter):
        new_rank = M @ rank
        # 収束判定
        if np.linalg.norm(new_rank - rank) < tol:
            print(f"収束: {i+1} 回の反復")
            break
        rank = new_rank

    return {nodes[i]: rank[i] for i in range(n)}

# サンプルの有向グラフでテスト
G = nx.DiGraph()
G.add_edges_from([("A", "B"), ("A", "C"), ("B", "C"), ("C", "A")])
ranks = power_iteration_pagerank(G)
for node, score in sorted(ranks.items(), key=lambda x: -x[1]):
    print(f"  {node}: {score:.4f}")
# C: 0.3879  ← 最も重要（複数からリンク）
# A: 0.3292
# B: 0.2829

import scipy.sparse as sp
import numpy as np

# 疎行列（CSR形式）でのグラフ表現
# 100万ノード、10万エッジのスパースグラフ
n_nodes = 1_000_000
rows = np.random.randint(0, n_nodes, size=100_000)
cols = np.random.randint(0, n_nodes, size=100_000)
data = np.ones(100_000)

# CSR（Compressed Sparse Row）形式
A_sparse = sp.csr_matrix((data, (rows, cols)), shape=(n_nodes, n_nodes))

# 密行列での必要メモリ: 10^12 bytes = 1TB（float32の場合）
# 疎行列での実際のメモリ: 約2.4MB
print(f"密行列の理論メモリ: {n_nodes**2 * 4 / 1e9:.0f} GB")
print(f"疎行列の実際メモリ: {A_sparse.data.nbytes / 1e6:.1f} MB")

# ラプラシアン計算も疎行列のまま実行
degree = np.array(A_sparse.sum(axis=1)).flatten()
D_sparse = sp.diags(degree)
L_sparse = D_sparse - A_sparse
# O(n+e) メモリで大規模グラフを処理可能