cs224w-notes 完整教學

Repository: https://github.com/snap-stanford/cs224w-notes Stars: 323 | Forks: 75 | 主要語言: CSS（Jekyll 靜態網站；核心內容為 Markdown 講義） 授權: MIT License Homepage: https://snap-stanford.github.io/cs224w-notes/ 最後更新: 2026-07-02

1. 專案概覽 (Project Overview)

1.1 這是什麼

cs224w-notes 是史丹佛大學 CS224W: Machine Learning with Graphs（圖機器學習） 課程的官方講義筆記庫，由該課程的助教（TA）群持續撰寫與維護。這門課由 Jure Leskovec 教授開設，是圖神經網路（Graph Neural Network; GNN）與網路科學（Network Science）領域公認的入門聖經課程之一，全球有大量線上自學者透過公開的講義與投影片來學習這個領域。

這個 repository 的本質不是一個程式碼函式庫或工具，而是一套用 Markdown 撰寫、透過 Jekyll 編譯成靜態網頁的結構化教材。它把一學期的課程內容（約 16 講）整理成三大主題：

1. Preliminaries（基礎概念）：圖的基本表示、網路量測、隨機圖模型、Motif 與 Graphlet
2. Network Methods（網路方法）：結構角色分析、頻譜分群（Spectral Clustering）、影響力最大化、疫情偵測、PageRank、級聯行為
3. Machine Learning with Networks（圖上的機器學習）：訊息傳遞與節點分類、節點表示學習（node2vec 等）、圖神經網路（GCN/GraphSAGE/GAT）、圖生成模型（GraphRNN）

1.2 研究團隊與動機

作者群是 Stanford SNAP（Stanford Network Analysis Project）實驗室（Jure Leskovec 主持）指導下的 CS224W 歷屆助教。動機非常直接：課程投影片（slides）資訊量大但缺乏敘事性的文字說明，學生（尤其是自學者）需要一份可以逐段閱讀、附有推導過程與直覺解釋的文字版講義。因此這份筆記強調：

• 用完整的段落敘述取代條列式投影片
• 保留關鍵數學推導（用 $$...$$ 語法撰寫的 LaTeX 公式）
• 搭配課程投影片中的圖示（assets/img/）輔助理解
• 開放社群貢獻（PR 修正錯字、補充章節可獲得額外課程加分，這是史丹佛課程一個很有趣的誘因設計）

1.3 解決什麼問題、為什麼重要

圖結構資料（graph-structured data）無所不在：社交網路、分子結構、知識圖譜、交通路網、推薦系統中的使用者-商品二部圖等。傳統深度學習（CNN 處理網格、RNN 處理序列）無法直接套用在這種不規則、無固定順序的拓撲結構上。CS224W 這門課、以及這份筆記，系統性地回答了「如何在圖上做機器學習」這個問題，從最古典的網路科學方法（PageRank、社群偵測）一路講到現代圖神經網路（GCN、GraphSAGE、GAT、GraphRNN）。

對想要跨入 GNN 領域的研究者或工程師而言，這份筆記的重要性在於：它是少數把理論推導與直覺解釋平衡得很好的免費教材，且持續被引用、被翻譯、被許多其他課程與教學專案引用為標準參考資料。

1.4 在 snap-stanford 生態系中的定位

snap-stanford 組織下有多個相關但分工不同的專案：

也就是說，cs224w-notes 扮演「地基」的角色——它教你為什麼要這樣設計模型，其他工具則回答「怎麼寫程式碼實作」。

1.5 相關論文引用

筆記中大量引用該領域的奠基性論文，包括（節錄自 GNN 章節的 Reference 區塊）：

• Battaglia et al., 2018《Relational inductive biases, deep learning, and graph networks》
• Hamilton et al., 2017《Representation learning on graphs: Methods and applications》（GraphSAGE 原始論文作者之一）
• Veličković et al., 2018《Graph Attention Networks》（GAT）
• Kipf & Welling, 2017《Semi-Supervised Classification with Graph Convolutional Networks》（GCN，筆記中雖未逐字列出但公式即出自此文）
• Grover & Leskovec, 2016《node2vec: Scalable Feature Learning for Networks》
• You et al., 2018《GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models》

2. 核心架構 (Core Architecture)

2.1 Repository 結構總覽

這是一個 Jekyll 靜態網站專案，資料夾分工清楚地把「內容」與「呈現」分離：

 1cs224w-notes/
 2├── index.md                                  # 課程總目錄（Table of Contents）
 3├── preliminaries/                            # 主題一：基礎概念
 4│   ├── introduction-graph-structure.md
 5│   ├── measuring-networks-random-graphs.md
 6│   └── motifs-and-structral-roles_lecture.md
 7├── network-methods/                          # 主題二：網路方法
 8│   ├── pagerank.md
 9│   ├── spectral-clustering.md
10│   ├── influence-maximization.md
11│   ├── outbreak-detection.md
12│   └── network-effects-and-cascading-behavior.md
13├── machine-learning-with-networks/           # 主題三：圖機器學習
14│   ├── message-passing-and-node-classification.md
15│   ├── node-representation-learning.md
16│   ├── graph-neural-networks.md
17│   └── graph-generative-models.md
18├── assets/img/                               # 課程投影片截圖、示意圖
19├── _layouts/, _includes/, _sass/, css/        # Jekyll 排版（Tufte CSS 風格）
20├── _config.yml, _data/options.yml            # Jekyll 設定
21├── Makefile                                   # 本地建置指令
22└── README.md                                  # 貢獻指南

2.2 內容組織的資料流

flowchart TD
    A["index.md
課程總目錄"] --> B["preliminaries/
基礎概念"]
    A --> C["network-methods/
網路方法"]
    A --> D["machine-learning-with-networks/
圖機器學習"]

    B --> B1["圖結構表示"]
    B --> B2["網路量測與隨機圖"]
    B --> B3["Motif / Graphlet"]

    C --> C1["結構角色 RolX"]
    C --> C2["頻譜分群"]
    C --> C3["影響力最大化"]
    C --> C4["疫情偵測 CELF"]
    C --> C5["PageRank / SimRank"]
    C --> C6["級聯行為 SEIZ"]

    D --> D1["訊息傳遞與節點分類"]
    D --> D2["節點表示學習
DeepWalk / node2vec / TransE"]
    D --> D3["圖神經網路
GCN / GraphSAGE / GAT"]
    D --> D4["圖生成模型
GraphRNN"]

    B3 -.鋪墊.-> C1
    C1 -.鋪墊.-> D1
    D2 -.鋪墊.-> D3
    D3 -.鋪墊.-> D4

這張圖說明了整份講義的知識依賴順序：先建立圖的基本語言（preliminaries），再學習不需要深度學習就能分析網路的古典方法（network-methods），最後進入以神經網路為核心的現代方法（machine-learning-with-networks）。這個順序本身就是課程設計哲學的體現——先懂圖，再懂學習。

2.3 建置系統架構

flowchart LR
    subgraph src["內容層"]
        MD["*.md 講義原始碼
(YAML front matter + Markdown + LaTeX)"]
    end
    subgraph build["建置層"]
        JK["Jekyll 靜態網站產生器"]
        LQ["Liquid 模板引擎
(marginnote/sidenote include)"]
    end
    subgraph out["輸出層"]
        SITE["_site/ 靜態 HTML"]
        GHP["GitHub Pages
snap-stanford.github.io/cs224w-notes"]
    end

    MD --> JK
    JK --> LQ
    LQ --> SITE
    SITE -->|git push 觸發| GHP

設計哲學分析：作者選擇 Jekyll 而非其他框架（如 Hugo、Docusaurus），核心原因是 GitHub Pages 原生支援 Jekyll，可以做到「push Markdown 到 master branch 即自動部署」，零額外 CI 設定成本。這對一個由多屆助教接力維護、貢獻者流動率高的教學專案來說是最務實的選擇——降低貢獻門檻遠比追求最新技術棧重要，這與 AIKT 專案「簡化優先、CLI 優先」的工程哲學不謀而合。

排版採用 Tufte CSS 風格（marginnote.html、sidenote.html、marginfigure.html 這些 include），這是 Edward Tufte 提倡的「側邊註記」排版法，讓補充說明、圖表可以放在正文旁邊而不打斷閱讀節奏——非常適合這種公式密集、需要邊讀邊看圖的教材。

3. 安裝與設定 (Installation & Setup)

3.1 情境一：只想閱讀講義（99% 使用者的需求）

完全不需要安裝任何東西，直接開啟已編譯好的網站：

1# 直接瀏覽線上版本
2open https://snap-stanford.github.io/cs224w-notes/

或者，如果你只是想把 Markdown 原始碼拉下來離線閱讀（不需要 Jekyll 渲染，任何 Markdown 檢視器都能看，只是數學公式不會渲染）：

1git clone https://github.com/snap-stanford/cs224w-notes.git
2cd cs224w-notes
3# 用任何支援 Markdown 的編輯器打開，例如 VS Code + Markdown Preview Enhanced 外掛
4code machine-learning-with-networks/graph-neural-networks.md

3.2 情境二：本地建置 Jekyll 網站（想貢獻內容或離線測試）

環境需求：

• Ruby ≥ 2.7（Jekyll 是用 Ruby 寫的）
• Bundler（Ruby 套件管理工具）
• 不需要 GPU、不需要 Python（這點與典型的 GNN 程式碼庫非常不同）

完整安裝步驟：

 1# 1. 安裝 Ruby（macOS 建議用 rbenv 而非系統內建 Ruby）
 2brew install rbenv ruby-build
 3rbenv install 3.2.2
 4rbenv local 3.2.2
 5
 6# 2. 安裝 Jekyll 與 Bundler
 7gem install jekyll bundler
 8
 9# 3. clone repo 並安裝相依套件
10git clone https://github.com/snap-stanford/cs224w-notes.git
11cd cs224w-notes
12bundle install
13
14# 4. 移除舊的編譯輸出（若存在）
15rm -rf _site/
16
17# 5. 啟動本地開發伺服器
18jekyll serve
19# 或使用 repo 內的 Makefile（若有定義對應 target）
20make
21
22# 6. 開啟瀏覽器
23open http://localhost:4000

3.3 常見問題排解

3.4 「資料集」在哪裡

必須澄清一個常見誤解：這個 repo 不含任何實作程式碼，也不含資料集。它是純理論講義。若要動手實作筆記中提到的演算法（PageRank、node2vec、GCN 等），需要另外準備資料，常見選擇：

• NetworkX 內建的玩具圖（karate_club_graph() 等）
• PyTorch Geometric (PyG) 的內建資料集（Cora、Citeseer、PubMed）
• Open Graph Benchmark (OGB)：snap-stanford/ogb 提供的大規模標準化資料集
• SNAP Datasets：https://snap.stanford.edu/data/ ，與 snap-stanford/snap 函式庫配套

4. 核心概念詳解 (Key Concepts)

這個章節挑選講義中三個最核心、也最常被問到的概念，用類比方式拆解。

4.1 概念一：為什麼圖不能直接餵進 CNN/RNN？

類比：CNN 假設輸入是一張「規則棋盤」——每個像素都有固定的上下左右鄰居；RNN 假設輸入是一條「隊伍」——每個字都有明確的前後順序。但一個社交網路裡，「你的朋友」這件事既沒有固定數量（有人 5 個朋友、有人 5000 個），也沒有天生的排列順序（先列出誰、後列出誰都一樣）。這正是筆記中提到的**「Permutation Invariance（排列不變性）」**要求：不管你怎麼幫節點編號、怎麼排列鄰居的順序，模型算出來的節點嵌入（embedding）都必須是同一個結果。

graph TD
    subgraph grid["CNN 的世界：規則網格"]
        P1["像素"] --- P2["像素"]
        P2 --- P3["像素"]
        P1 --- P4["像素"]
    end
    subgraph graphworld["GNN 的世界：不規則圖"]
        N1["節點A
3個鄰居"] --- N2["節點B"]
        N1 --- N3["節點C"]
        N1 --- N4["節點D"]
        N2 --- N5["節點E
1個鄰居"]
    end

4.2 概念二：訊息傳遞（Message Passing）的直覺

筆記中 GNN 一章的核心公式：

$$ h_v^{k} = \sigma\left(W_k\sum_{u\in N(v)}\frac{h_u^{k-1}}{|N(v)|} + B_kh_v^{k-1}\right) $$

直覺解釋：想像每個節點是一個開會的人，每一輪（layer）大家都會「聽取」自己所有鄰居上一輪發言的平均意見（$$\sum_{u\in N(v)} h_u^{k-1}/|N(v)|$$），再混合自己原本的想法（$$B_k h_v^{k-1}$$），形成這一輪的新想法（$$h_v^k$$）。經過 $$K$$ 輪這樣的「開會」，每個節點的最終想法就融合了距離它 $$K$$ 步之內所有節點的資訊——這就是為什麼 GNN 的層數又叫做「感受野（receptive field）半徑」。

graph TD
    L0A["Layer 0: A 的原始特徵"] --> L1A["Layer 1: A 融合 B,C,D"]
    L0B["Layer 0: B 的原始特徵"] --> L1A
    L0C["Layer 0: C 的原始特徵"] --> L1A
    L0D["Layer 0: D 的原始特徵"] --> L1A
    L1A --> L2A["Layer 2: A 融合了 2 跳內所有節點資訊"]

4.3 概念三：淺層編碼器（Shallow Encoder）為何不夠用

筆記中列出 DeepWalk / node2vec 這類方法的四個限制，這也是 GNN 誕生的動機：

1. 不 scale：每個節點都要學一個獨立的嵌入向量，節點數一多，參數量爆炸
2. inductive 能力差：訓練好的模型看到一個全新節點（訓練時不存在）就束手無策
3. 不使用節點特徵：只用網路拓撲，忽略節點本身的屬性資訊（例如使用者的個人資料）
4. 無法搭配任意損失函數彈性訓練：本質上是矩陣分解的變形，訓練目標固定

用一個類比理解：淺層編碼器像是「死背每個人的臉」——來一個新面孔就完全不認識；GNN 則是學會「辨識臉部特徵的規則」——即使是沒見過的人，也能透過眼睛、鼻子、嘴巴的相對關係去判斷。

4.4 概念四：PageRank 的隨機衝浪者模型

$$ r_j = \sum_{i \to j} \frac{r_i}{d_i} $$

類比：想像一個網路衝浪者，每次都從目前的網頁隨機點擊一個超連結跳到下一頁，永遠這樣跳下去。經過無限久的時間，這個衝浪者停留在某個網頁的機率分布，就是這個網頁的 PageRank 分數。一個網頁如果被很多「本身也很重要」的網頁指向，它的分數就越高——這是一個遞迴定義，用冪迭代法（Power Iteration）求解。

flowchart LR
    A["網頁 A
r=0.4"] -->|"1/2 權重"| B["網頁 B"]
    A -->|"1/2 權重"| C["網頁 C"]
    D["網頁 D
r=0.3"] -->|"全部權重"| B
    B -->|"更新後"| B2["r_B = r_A/2 + r_D"]

4.5 概念五：影響力最大化（Influence Maximization）與次模性（Submodularity）

筆記中 network-methods 章節介紹了一個很有意思的組合最佳化問題：在一個社交網路中，如果只能挑選 $$k$$ 個人作為「種子使用者」去推廣一個產品（透過口碑擴散影響朋友），該選哪 $$k$$ 個人才能讓最終被影響的人數最多？

直覺類比：想像你只有 3 張免費體驗券要送出去，送給「朋友很多、且朋友之間彼此不太重疊」的人，會比送給「彼此都是同一群朋友」的人擴散效果更好——因為後者會造成大量「重複影響」的浪費。這正是講義中**次模性（submodularity）**這個數學性質的直覺：新增一個種子節點帶來的邊際效益，會隨著已選種子集合變大而遞減（「邊際效益遞減」）。

$$ f(S \cup {v}) - f(S) \geq f(T \cup {v}) - f(T), \quad \text{若 } S \subseteq T $$

這個性質保證了一個簡單的貪婪演算法（Hill Climbing）——每一步都選「當下能帶來最大邊際效益」的節點——可以得到至少 $$(1 - 1/e) \approx 63%$$ 最佳解的保證，這是次模函數最佳化理論中最著名的結果之一（Nemhauser et al., 1978）。

flowchart TD
    S0["空集合 S={}"] -->|"選節點A
邊際效益=10"| S1["S={A}"]
    S1 -->|"選節點B
邊際效益=6
(比選A時的效益低，因部分朋友重疊)"| S2["S={A,B}"]
    S2 -->|"選節點C
邊際效益=3
(遞減效應持續)"| S3["S={A,B,C}"]

4.6 概念六：疫情偵測中的 CELF 演算法——如何讓貪婪演算法「跑得動」

上述貪婪演算法有個致命問題：每一步都要重新計算「加入每個候選節點後的邊際效益」，若圖有 $$n$$ 個節點、要選 $$k$$ 個種子，複雜度是 $$O(k \cdot n \cdot \text{模擬成本})$$，在大圖上完全不可行。

筆記中 outbreak-detection.md 介紹的 CELF（Cost-Effective Lazy Forward selection） 演算法，利用次模性的「邊際效益只會遞減、不會遞增」這個性質做了一個聰明的優化：維護一個以邊際效益排序的優先佇列，每一輪只需要重新計算佇列最前面那個節點的邊際效益（因為其他節點的邊際效益不可能比它在更大集合下的估計還高），若重算後它仍是最大就直接選它，不需要重算所有候選者。這個「lazy evaluation（懶惰評估）」技巧讓演算法實務上可以快上 700 倍以上，卻仍保有跟原始貪婪演算法完全相同的 $$(1-1/e)$$ 理論保證——這是「用資料結構換取速度、但不犧牲理論保證」的一個經典範例，也是這份講義中最能體現「演算法設計巧思」的段落之一。

5. 使用方式與程式碼範例 (Usage & Code Examples)

由於原始 repo 本身不含程式碼，本章節提供依照筆記理論獨立實作的可執行範例，幫助讀者把講義中的數學公式轉成程式碼，驗證理解是否正確。

5.1 範例一：PageRank 冪迭代法（對應 network-methods/pagerank.md）

 1"""
 2基礎 PageRank 實作：對應 cs224w-notes 的 Link Analysis 章節
 3不依賴任何第三方圖函式庫，純 NumPy 示範遞迴定義如何用冪迭代法求解
 4"""
 5import numpy as np
 6
 7def pagerank(adjacency: np.ndarray, damping: float = 0.85,
 8             max_iter: int = 100, tol: float = 1e-8) -> np.ndarray:
 9    """
10    adjacency: n x n 的鄰接矩陣，adjacency[i][j] = 1 表示 i -> j 有超連結
11    damping: 阻尼係數（隨機跳轉機率的補數），課程慣例用 0.85
12    """
13    n = adjacency.shape[0]
14    out_degree = adjacency.sum(axis=1)
15    out_degree[out_degree == 0] = 1  # 避免 dead end 除以零
16
17    # 轉移機率矩陣：M[j][i] = 1/d_i，若 i -> j
18    M = (adjacency / out_degree[:, None]).T
19
20    r = np.ones(n) / n  # 初始均勻分布
21    for iteration in range(max_iter):
22        r_next = damping * M @ r + (1 - damping) / n
23        if np.linalg.norm(r_next - r, ord=1) < tol:
24            print(f"收斂於第 {iteration} 輪迭代")
25            break
26        r = r_next
27    return r
28
29
30if __name__ == "__main__":
31    # 建一個簡單的 4 個網頁的連結圖
32    #   A -> B, C
33    #   B -> C
34    #   C -> A
35    #   D -> C
36    adj = np.array([
37        [0, 1, 1, 0],  # A
38        [0, 0, 1, 0],  # B
39        [1, 0, 0, 0],  # C
40        [0, 0, 1, 0],  # D
41    ])
42    scores = pagerank(adj)
43    for name, score in zip("ABCD", scores):
44        print(f"網頁 {name}: PageRank = {score:.4f}")
45    # 預期：C 因為被 A, B, D 都指向，分數應該最高

執行結果解讀：C 節點會拿到最高分，因為它是全圖唯一被三個節點共同指向的「熱門節點」，這直接對應講義中「重要節點會被重要節點指向」的遞迴定義。

5.2 範例二：簡化版 node2vec 隨機遊走取樣（對應 node-representation-learning.md）

 1"""
 2node2vec 的核心：帶偏差的二階隨機遊走 (biased 2nd-order random walk)
 3本範例示範 p, q 參數如何控制 BFS-like（結構相似）vs DFS-like（社群相似）的遊走傾向
 4"""
 5import random
 6import networkx as nx
 7
 8def biased_walk(G: nx.Graph, start: str, walk_length: int,
 9                 p: float = 1.0, q: float = 1.0) -> list:
10    """
11    p: return parameter，越大越不容易走回上一個節點（鼓勵探索）
12    q: in-out parameter，越大越傾向留在附近（BFS-like，捕捉結構角色）
13       越小越傾向往外走（DFS-like，捕捉社群歸屬）
14    """
15    walk = [start]
16    prev = None
17
18    for _ in range(walk_length - 1):
19        curr = walk[-1]
20        neighbors = list(G.neighbors(curr))
21        if not neighbors:
22            break
23
24        if prev is None:
25            # 第一步沒有「前一步」資訊，均勻取樣
26            next_node = random.choice(neighbors)
27        else:
28            weights = []
29            for nxt in neighbors:
30                if nxt == prev:
31                    weights.append(1.0 / p)          # 走回頭路
32                elif G.has_edge(nxt, prev):
33                    weights.append(1.0)               # 鄰居也是 prev 的鄰居 -> BFS-like
34                else:
35                    weights.append(1.0 / q)            # 更遠的節點 -> DFS-like
36            total = sum(weights)
37            probs = [w / total for w in weights]
38            next_node = random.choices(neighbors, weights=probs, k=1)[0]
39
40        walk.append(next_node)
41        prev = curr
42
43    return walk
44
45
46if __name__ == "__main__":
47    G = nx.karate_club_graph()  # 經典的空手道俱樂部社群網路資料集
48    walk_bfs_like = biased_walk(G, start=0, walk_length=10, p=1, q=2)
49    walk_dfs_like = biased_walk(G, start=0, walk_length=10, p=1, q=0.5)
50    print("BFS-like（q>1，偏向結構角色相似）遊走路徑:", walk_bfs_like)
51    print("DFS-like（q<1，偏向社群歸屬相似）遊走路徑:", walk_dfs_like)
52    # 這些遊走序列接下來會被當成「句子」餵進 Skip-gram (word2vec) 模型
53    # 訓練出每個節點的向量表示，這就是 node2vec 完整流程的前半段

5.3 範例三：用 PyTorch 從零實作講義中的 GCN 公式

 1"""
 2對照 machine-learning-with-networks/graph-neural-networks.md 中的公式：
 3H^(l+1) = sigma( H^l W0^l + A_tilde H^l W1^l )， A_tilde = D^(-1/2) A D^(-1/2)
 4用最精簡的 PyTorch 程式碼「逐行對應」筆記推導，而非直接呼叫 PyG 的封裝好的 GCNConv
 5"""
 6import torch
 7import torch.nn as nn
 8import torch.nn.functional as F
 9
10
11class GCNLayer(nn.Module):
12    def __init__(self, in_dim: int, out_dim: int):
13        super().__init__()
14        self.W0 = nn.Linear(in_dim, out_dim, bias=False)  # 對應自身特徵的權重 B_k
15        self.W1 = nn.Linear(in_dim, out_dim, bias=False)  # 對應鄰居聚合的權重 W_k
16
17    def forward(self, H: torch.Tensor, A_tilde: torch.Tensor) -> torch.Tensor:
18        # H: [num_nodes, in_dim]，A_tilde: [num_nodes, num_nodes] 正規化後的鄰接矩陣
19        self_term = self.W0(H)
20        neighbor_term = self.W1(A_tilde @ H)
21        return F.relu(self_term + neighbor_term)
22
23
24def normalize_adjacency(A: torch.Tensor) -> torch.Tensor:
25    """計算 A_tilde = D^(-1/2) (A + I) D^(-1/2)，加自環讓節點也聚合自己的特徵"""
26    A_hat = A + torch.eye(A.size(0))
27    D = A_hat.sum(dim=1)
28    D_inv_sqrt = torch.diag(D.pow(-0.5))
29    return D_inv_sqrt @ A_hat @ D_inv_sqrt
30
31
32class TwoLayerGCN(nn.Module):
33    """對應筆記中 K=2 層的堆疊，最後接一個分類頭做節點分類"""
34    def __init__(self, in_dim: int, hidden_dim: int, num_classes: int):
35        super().__init__()
36        self.layer1 = GCNLayer(in_dim, hidden_dim)
37        self.layer2 = GCNLayer(hidden_dim, num_classes)
38
39    def forward(self, X: torch.Tensor, A_tilde: torch.Tensor) -> torch.Tensor:
40        H1 = self.layer1(X, A_tilde)
41        H2 = self.layer2(H1, A_tilde)
42        return H2  # 回傳未經 softmax 的 logits，訓練時搭配 CrossEntropyLoss
43
44
45if __name__ == "__main__":
46    torch.manual_seed(224)
47    num_nodes, in_dim, hidden_dim, num_classes = 6, 4, 8, 2
48
49    # 建構一個玩具圖的鄰接矩陣（無向，6 個節點）
50    A = torch.tensor([
51        [0, 1, 1, 0, 0, 0],
52        [1, 0, 1, 0, 0, 0],
53        [1, 1, 0, 1, 0, 0],
54        [0, 0, 1, 0, 1, 1],
55        [0, 0, 0, 1, 0, 1],
56        [0, 0, 0, 1, 1, 0],
57    ], dtype=torch.float32)
58
59    X = torch.randn(num_nodes, in_dim)          # 隨機節點特徵
60    y = torch.tensor([0, 0, 0, 1, 1, 1])         # 假設的節點標籤（兩個社群）
61
62    A_tilde = normalize_adjacency(A)
63    model = TwoLayerGCN(in_dim, hidden_dim, num_classes)
64    optimizer = torch.optim.Adam(model.parameters(), lr=0.05)
65
66    for epoch in range(50):
67        optimizer.zero_grad()
68        logits = model(X, A_tilde)
69        loss = F.cross_entropy(logits, y)
70        loss.backward()
71        optimizer.step()
72        if epoch % 10 == 0:
73            pred = logits.argmax(dim=1)
74            acc = (pred == y).float().mean().item()
75            print(f"Epoch {epoch:2d} | Loss {loss.item():.4f} | Acc {acc:.2f}")

這個範例的教學價值：它刻意不使用 torch_geometric.nn.GCNConv 這種黑盒封裝，而是逐行對照筆記的矩陣公式手刻，讓讀者看清楚 $$W_0$$（自身特徵權重）與 $$W_1$$（鄰居聚合權重）分別對應程式碼中的哪一行、正規化鄰接矩陣 $$\tilde{A}$$ 是怎麼算出來的。等到真的理解這個底層邏輯後，再去用 PyG 的封裝函式會更知道自己在用什麼。

5.4 範例四：頻譜分群（Spectral Clustering）—— 對應 network-methods/spectral-clustering.md

 1"""
 2頻譜分群三步驟（對應筆記中的推導）：
 31. 建構圖拉普拉斯矩陣 L = D - A
 42. 取 L 的前 k 小特徵值對應的特徵向量，組成 n x k 的嵌入矩陣
 53. 對這個嵌入矩陣的每一列（每個節點的 k 維座標）跑 k-means
 6"""
 7import numpy as np
 8from numpy.linalg import eigh
 9
10
11def spectral_clustering(A: np.ndarray, k: int, num_iter: int = 100) -> np.ndarray:
12    n = A.shape[0]
13    D = np.diag(A.sum(axis=1))
14    L = D - A  # 圖拉普拉斯矩陣 (unnormalized Laplacian)
15
16    eigenvalues, eigenvectors = eigh(L)  # eigh 保證回傳依特徵值遞增排序（L 是對稱半正定）
17    # 捨棄第 0 個特徵值（恆為 0，對應「整張圖是一個連通分量」的平凡解）
18    embedding = eigenvectors[:, 1:k + 1]   # n x k
19
20    # 簡易版 k-means（教學用途，不使用 sklearn 以維持零依賴）
21    rng = np.random.default_rng(224)
22    centers = embedding[rng.choice(n, k, replace=False)]
23    labels = np.zeros(n, dtype=int)
24
25    for _ in range(num_iter):
26        distances = np.linalg.norm(embedding[:, None, :] - centers[None, :, :], axis=2)
27        new_labels = distances.argmin(axis=1)
28        if np.array_equal(new_labels, labels):
29            break
30        labels = new_labels
31        for c in range(k):
32            if (labels == c).any():
33                centers[c] = embedding[labels == c].mean(axis=0)
34
35    return labels
36
37
38if __name__ == "__main__":
39    # 兩個明顯社群，中間僅一條橋接邊（對應筆記中「圖分割」的直覺範例）
40    A = np.array([
41        [0, 1, 1, 0, 0, 0],
42        [1, 0, 1, 0, 0, 0],
43        [1, 1, 0, 1, 0, 0],  # 節點 2 是橋接兩個社群的關鍵節點
44        [0, 0, 1, 0, 1, 1],
45        [0, 0, 0, 1, 0, 1],
46        [0, 0, 0, 1, 1, 0],
47    ])
48    labels = spectral_clustering(A, k=2)
49    print("節點分群結果:", labels)
50    # 預期：{0,1,2} 一群，{3,4,5} 一群，因為只有節點 2-3 之間的邊跨越兩個社群

與講義概念的對應：第二小的特徵值（Fiedler value）與其對應的特徵向量（Fiedler vector）決定了圖最自然的二分割方式，這正是講義中「Graph Cut」與「圖拉普拉斯矩陣特徵分解」之間關聯的具體實作。

5.5 三個範例的共同教學設計原則

上述四個範例（PageRank、node2vec、GCN、頻譜分群）刻意遵循相同的撰寫原則，方便讀者建立跨演算法的比較直覺：

1. 零外部框架依賴（除 GCN 範例的 PyTorch 外）：不用 PyG、不用 igraph，讓讀者能一步步對照講義公式逐行理解程式碼，而不是被框架 API 擋住理解
2. 同一組小圖反覆出現：範例三、四刻意使用同一種「兩個社群 + 一條橋接邊」的拓撲結構，讓讀者能直接比較 GCN 的分類結果與頻譜分群的分群結果是否一致——這其實也是講義中「圖上的監督式 vs. 非監督式方法殊途同歸」的一個隱含主題
3. 每段程式碼都標註對應的講義章節與公式：這是刻意的教學設計，讓這份文件本身也能作為「講義 ↔ 程式碼」的雙向索引

6. 進階應用場景 (Advanced Use Cases)

6.1 真實世界應用案例

• 藥物發現 / 分子性質預測：把分子視為圖（原子=節點、化學鍵=邊），GCN/GAT 類架構被廣泛用於預測毒性、溶解度、與蛋白質結合能力（例如筆記中提及的框架後來演化出的 MoleculeNet、AlphaFold 的部分子模組）
• 推薦系統：使用者-商品二部圖上的訊息傳遞（如 PinSAGE，直接源自筆記中 GraphSAGE 的工業界擴展版本，由 Pinterest 與 Stanford SNAP 團隊合作發表）
• 金融詐欺偵測：交易網路中用結構角色分析（筆記中 RolX 演算法）找出異常節點
• 知識圖譜補全：筆記索引中列出的 TransE 方法被廣泛用於補全知識圖譜中缺失的三元組關係

6.2 與其他 snap-stanford 工具的整合

flowchart TD
    NOTES["cs224w-notes
理論講義"] -->|"提供演算法定義與公式"| IMPL["實作階段"]
    IMPL --> SNAP["snap-stanford/snap
C++/Python 高效圖運算"]
    IMPL --> PYG["PyTorch Geometric
GNN 模型框架"]
    IMPL --> OGB["snap-stanford/ogb
標準化評測資料集"]

    SNAP -->|"大規模圖統計/子圖枚舉"| RESULT["研究成果"]
    PYG -->|"訓練 GCN/GAT/GraphSAGE"| RESULT
    OGB -->|"公平比較 benchmark"| RESULT

實務上的典型工作流是：先讀 cs224w-notes 弄懂演算法「為什麼這樣設計」，再用 snap 函式庫做大規模圖的前處理與統計量計算（例如算 clustering coefficient、找 connected components），最後用 PyTorch Geometric 實作與訓練模型，並在 OGB 資料集上做標準化評測。

6.3 效能調校與最佳實踐

雖然這個 repo 本身沒有程式碼，但筆記中隱含的效能考量在實作時要注意：

1. Over-smoothing 問題：筆記提到 GNN 層數增加會讓感受野擴大，但講義沒有深入的一點是——層數太深時所有節點的嵌入會趨於一致（over-smoothing），實務上 GCN/GAT 通常只疊 2-4 層，不像 CNN 可以疊到上百層
2. 鄰接矩陣正規化的數值穩定性：$$D^{-1/2}$$ 在孤立節點（degree=0）時會除以零，需要像範例程式碼中一樣先加自環（self-loop）再算度數
3. 大圖的 mini-batch 訓練：完整鄰接矩陣運算（如範例三）只適合小圖教學展示，真實世界百萬節點的圖需要用 GraphSAGE 式的鄰居抽樣（neighbor sampling）或 Cluster-GCN 式的子圖切割，這是筆記中 GraphSAGE 章節提到的 inductive 能力在工程上的真正用武之地
4. 頻譜方法的可擴展性瓶頸：範例四的完整特徵分解是 $$O(n^3)$$ 複雜度，對於節點數超過幾萬的圖幾乎不可行；實務上會改用 Lanczos 迭代法等只求前 k 小特徵值/向量的近似演算法（如 scipy.sparse.linalg.eigsh），這也是「古典網路方法」與「深度學習方法」在工程可擴展性上的關鍵分野——這正是筆記把兩者分成 network-methods 與 machine-learning-with-networks 兩個獨立主題的深層原因之一：前者數學漂亮但難以擴展到超大圖，後者靠隨機抽樣、mini-batch 訓練換取可擴展性
5. PageRank 的稀疏矩陣優化：範例二示範用稠密矩陣運算，但真實網路（如整個 Web 圖）的鄰接矩陣極度稀疏，正式實作必須用 scipy.sparse 的 CSR 格式做矩陣向量乘法，否則記憶體會直接爆炸
6. node2vec 隨機遊走的平行化：範例三的遊走取樣是序列執行，真實場景（如 SNAP 函式庫的 C++ 實作）會針對數百萬個起始節點平行做隨機遊走，取樣完再統一餵進 Skip-gram 訓練，這是「理論演算法」到「工業級工具」之間最常見的工程落差

6.4 從筆記到研究論文的橋接路徑

對於想要進一步做研究（而非只是應用）的讀者，這份講義提供了一個清楚的「地圖」，指出接下來該往哪個方向深挖：

flowchart LR
    A["讀完 cs224w-notes
建立地基"] --> B{"研究方向？"}
    B -->|"模型架構創新"| C["讀 GAT/GraphSAGE 原始論文
+ 近年 Graph Transformer 論文"]
    B -->|"可擴展性"| D["讀 Cluster-GCN、GraphSAINT
大圖訓練技術"]
    B -->|"生成式模型"| E["讀 GraphRNN 後續
GraphVAE、擴散模型於圖生成"]
    B -->|"應用導向"| F["讀特定領域論文
(分子/推薦系統/知識圖譜)"]
    C --> G["用 PyTorch Geometric
實作並在 OGB 上評測"]
    D --> G
    E --> G
    F --> G

這張圖也說明了為什麼 cs224w-notes 在 AIKT 知識圖譜中適合當作「概念錨點」——它不是研究的終點，而是所有後續深入研究的共同起點，之後不論往哪個子領域鑽研，都能透過這份講義建立的詞彙與公式基礎快速銜接。

7. 與 AIKT 的關聯分析 (AIKT Integration Analysis)

7.1 定位釐清：知識來源，而非工具

cs224w-notes 與 AIKT 系統中大部分已收錄的 GitHub repo 不同——它不是一個可執行的工具或函式庫，而是一份結構化知識資產。因此它與 AIKT 的關聯，主要不是「AIKT 呼叫它的功能」，而是「AIKT 把它當作高品質知識來源去擷取、索引、再加工」。這正好是 AIKT L1-L15 這條知識管線設計初衷所要處理的典型素材。

7.2 可對應的 Layer

flowchart TD
    SRC["cs224w-notes
GitHub Repo"] -->|"L2 gh-save
純 GitHub URL 觸發"| INBOX["inbox/
結構化 md 摘要"]

    INBOX -->|"L4 graphify"| GRAPH["知識圖譜索引
PageRank/GCN/node2vec 概念節點化"]
    INBOX -->|"L5 ai-notebooklm"| RAG["NotebookLM RAG
可問答式檢索"]

    SRC -->|"L12 gh-tutorial-qd
GitHub URL + 教學意圖"| TUTORIAL["教學 HTML 全套交付
(本文件即此流程產出)"]

    SRC -->|"L15 paper-tutorial
搭配 GCN/GAT/node2vec 原始論文"| DEEP["論文+講義比對式精讀教學"]

    GRAPH --> QUERY["之後的研究任務可查詢：
『GCN 與 GraphSAGE 的差異』
『over-smoothing 問題』"]
    RAG --> QUERY

具體對應：

7.3 潛在整合場景與價值

1. 研究入門包（Onboarding Kit）：當團隊有新成員要跨入圖神經網路領域的研究（例如 Apotek 未來若涉及分子圖/蛋白質交互作用網路分析），可以用「L2 收錄 cs224w-notes → L4 建圖譜 → L5 建 RAG → L15 生成對照論文教學」這條管線，兩三個 Layer 呼叫內就產出一套完整可問答、可視覺化的入門教材，遠比人工整理快
2. 概念索引的「地基層」：AIKT 的知識圖譜若未來要收錄更多 GNN 相關論文或工具（PyG、OGB、DGL），cs224w-notes 產生的圖譜節點可以作為這些後續知識的「共同祖先」概念錨點，減少每次都要重新解釋 GCN/GAT 基礎定義的重複工作
3. 教學生成的品質基準：由於這是史丹佛官方助教撰寫、久經驗證的教材，AIKT 未來做 L12/L15 教學生成時，可以把這份講義的敘事節奏（先講限制、再講解法、再講數學、最後給參考文獻）當作品質校準的參考範本

7.4 邊界提醒

8. 優缺點與生態系定位 (Strengths, Limitations & Ecosystem Position)

8.1 核心優勢與創新點

• 敘事完整性：把投影片的條列重點展開成有邏輯脈絡的段落，特別適合自學者，不需要現場聽課也能理解「為什麼」而不只是「是什麼」
• 數學嚴謹但不失直覺：公式推導完整（如 GCN 矩陣形式推導、PageRank 收斂性），但每個公式後面都配有白話解釋
• 持續維護：由歷屆助教接力更新，內容會隨課程演進（新增知識圖譜、時序網路等主題），不是一次性寫完就放著不管的靜態文件
• 零框架依賴：純 Markdown + Jekyll，貢獻門檻極低，任何人都能直接編輯 .md 檔案提交 PR
• 免費、開源、MIT 授權：沒有付費牆，商業使用也完全合法
• 視覺化輔助：assets/img/ 內大量投影片截圖與示意圖，補足純文字推導難以傳達的空間直覺

8.2 目前限制與改進空間

1. 內容有「未完工」的部分：index.md 中部分章節連結是空的（例如「Network Robustness」「Network Evolution」「Knowledge Graphs and Metapaths」目前沒有對應連結），說明筆記仍在補完中，不是每一講都有文字版
2. 沒有配套程式碼：這是它與 PyTorch Geometric 官方教學最大的差異——後者是「讀了就能跑」，cs224w-notes 需要讀者自己動手實作才能驗證理解（本文件第 5 章即是彌補這個落差的嘗試）
3. 版本與課程進度綁定，更新頻率不均：內容更新取決於當學期助教的心力，不像商業教材有固定發布週期
4. 缺乏互動式練習：沒有隨堂測驗、沒有自動評分的程式作業，純粹是閱讀材料
5. 進階主題（如時序圖、異質圖神經網路、大規模分散式訓練）覆蓋不足：課程近年隨著領域發展持續擴充，但講義的更新速度落後於投影片本身

8.3 與同領域工具/教材的比較

8.4 適用場景建議

• 適合：初次接觸圖機器學習領域、想要有邏輯脈絡地建立完整知識框架的學習者；教學者想要一份可直接引用或改編的教材骨架；研究者需要快速回顧某個古典演算法（PageRank、Spectral Clustering）的公式推導
• 不太適合：想要「複製貼上就能跑」程式碼的實務工程師（應直接去看 PyTorch Geometric 或 DGL 官方教學）；需要涵蓋 2020 年後最新 GNN 研究（如 Transformer-based Graph Learning、大規模預訓練圖模型）的讀者，這部分講義覆蓋較薄弱

8.5 建議的閱讀順序（給第一次接觸的讀者）

若你是完全沒有網路科學或圖神經網路背景的讀者，建議依照以下順序閱讀，而不是照 repo 的檔案排序死板地從頭讀到尾：

1. 先讀 preliminaries/introduction-graph-structure.md：建立圖的基本語言（有向/無向、加權/不加權、bipartite 等）
2. 接著讀 network-methods/pagerank.md：這是最直覺、最少數學包袱的演算法，適合建立信心
3. 再讀 machine-learning-with-networks/node-representation-learning.md：理解「把節點變成向量」這個核心想法，是後面 GNN 的鋪墊
4. 然後讀 machine-learning-with-networks/graph-neural-networks.md：這是整份講義的核心，也是現代研究最活躍的部分
5. 最後依興趣挑讀 network-methods/ 其餘章節（影響力最大化、疫情偵測、頻譜分群）與 graph-generative-models.md

跳過第一遍不熟悉的數學推導、先抓住直覺，讀完一輪後再回頭啃公式，會比逐字精讀更有效率——這也是這份講義本身的敘事節奏設計（先給限制、再給動機、才給公式）鼓勵的閱讀方式。

8.6 總結

cs224w-notes 在整個圖機器學習教育生態系中扮演「黃金起點」的角色——它不追求成為最完整或最新的資源，而是穩定地提供一套邏輯清晰、公式完整、免費開源的入門路徑。對 AIKT 這樣的知識管理系統而言，它是絕佳的「知識種子」：結構清楚、內容穩定、邊界明確（無機密疑慮），非常適合被完整收錄、索引、再加工成可問答、可視覺化的知識資產，供未來任何 GNN / 網路科學相關研究任務快速調用。

附錄：關鍵詞速查表