# 社群網路作業一
[論文連結](https://arxiv.org/pdf/1905.10418.pdf)
姓名：張議隆
學號：F74082125
這一小段是我寫到最後才回來寫的，在此跟教授和助教說聲抱歉。這篇報告前段內容是論文相關，我整理得還算勉強可以接受；後半段大多為實驗的紀錄以及我當下遇到的挫折與疑問，因此非常瑣碎。筆記內提到的日期皆為我當下紀錄的時間點，可以從時間點感受到我做這份作業的發展。
另外有關於所有被 `spoiler` 遮住的部分在麻煩批改時到[這個網頁](https://hackmd.io/@bebo1010/Social_Network_HW1)來展開，我將它們全部遮起來是考量到作業要求中提到不可包含程式碼，但是站在我的筆記來看我還是得附上一些程式碼才更好紀錄，不好意思麻煩助教了！
:::spoiler TOC
[TOC]
:::
## Section 1: Introduction
> 3/9
注重於Between Centrality高的node
BC前幾%的node有時是解決問題的關鍵
當node數量達到百萬，計算每個node的BC變得不實際
DrBC(Deep Ranker for BC)
Section 2: related work
Section 3: DrBC architecture
Section 4: model evaluation
Section 5: observations; insights
Section 6: conclusion
## Section 3: DrBC architecture
### 3.1 Preliminaries -- The Brandes Algorithm
[參考論文網址](http://snap.stanford.edu/class/cs224w-readings/brandes01centrality.pdf)，以下內容摘錄自此論文的 `Section 4. Accumulation of Pair-Dependencies`
* $\delta_{st}(v)$ 代表從點 $s$ 到點 $t$ 且經過點 $v$ 的最短路徑除以從點 $s$ 到點 $t$ 的最短路徑個數，也就是 $\delta_{st}(v) = \dfrac{\sigma_{st}(v)}{\sigma_{st}}$
* $\sigma_{st}$ 代表從點 $s$ 到點 $t$ 的最短路徑個數，$\sigma_{st}(v)$ 代表從點 $s$ 到點 $t$ 且經過點 $v$ 的最短路徑個數(Section 2有描述)
* 假設從點 $s$ 到 graph 中每個 $t$ 皆只有一條最短路徑，底下這個式子成立
* $\delta_{s \cdot }(v) = \displaystyle \sum_{w : v \in P_s(w)} (1 + \delta_{s \cdot }(w))$
* 從 $s$ 到整個 graph 的任何一點 $v$ ，其中 $v$ 是點 $w$ 的 predecessor($P_s(w)$)。
:::info
這篇論文有不少符號混用的問題，以及這個 $t$ 也沒有解釋得很完整，描述只有寫到 `for some $t$`。有可能只是為了不失一般性的敘述。
我能理解 $\delta_{s \cdot }(w)$ 的部分，但是我還是不理解為何會額外 +1。
:::
* 從點 $s$ 到 graph 中任一點 $v$，遵守下列式子
* $\delta_{s \cdot }(v) = \displaystyle \sum_{w : v \in P_s(w)} \dfrac{\sigma_{sv}}{\sigma_{sw}}(1 + \delta_{s \cdot }(w))$
* 從點 $s$ 到點 $t$ 且經過點 $v$ 的任一最短路徑中，從點 $v$ 到點 $w$ 的邊僅有一條。
:::info
看到這裡我還是不理解發生什麼事情，但我還是先繼續看下去
:::
* 作者將原本的 $\delta_{st}(v)$ 修改為 $\delta_{st}(v, e) = \dfrac{\sigma_{st}(v, e)}{\sigma_{st}}$，也就是特別指定從點 $s$ 到點 $t$ 的最短路徑有包含邊 $e$。
* $\delta_{s \cdot }(v) = \displaystyle \sum_{t \in V}\delta_{st}(v) = \sum_{t \in V}\sum_{w : v \in P_s(w)} \delta_{st}(v, \{v, w\}) = \sum_{w : v \in P_s(w)} \sum_{t \in V} \delta_{st}(v, \{v, w\})$
:::info
到這裡為止我看起來只是做了一些代換，沒有太多有趣的內容。
:::
* 從點 $s$ 到點 $w$ 的最短路徑中，必然會跟著從點 $s$ 到點 $v$ 的最短路徑再經過 $\{v, w\}$ 的邊。
* 因此從點 $s$ 到點 $t \neq w$ 的最短路徑必然會含有點 $v$ 和邊 $\{v, w\}$，可以改寫 $\delta_{st}(v, \{v, w\})$ 為以下內容：
* $\delta_{st}(v, \{v, w\}) =\dfrac{\sigma_{sv}}{\sigma_{sw}}, \text{if } t = w$
* $\delta_{st}(v, \{v, w\}) =\dfrac{\sigma_{sv}}{\sigma_{sw}} \cdot \dfrac{\sigma_{st}(w)}{\sigma_{st}}, \text{if } t \neq w$
* 把 $\delta_{st}(v, \{v, w\})$ 放回去上面改寫的內容得到：
* $\displaystyle \sum_{w : v \in P_s(w)} \sum_{t \in V} \delta_{st}(v, \{v, w\}) = \sum_{w : v \in P_s(w)}(\dfrac{\sigma_{sv}}{\sigma_{sw}} + \sum_{t \in V \backslash \{w\}} \dfrac{\sigma_{sv}}{\sigma_{sw}} \cdot \dfrac{\sigma_{st}(w)}{\sigma_{st}}) \\ = \displaystyle \sum_{w : v \in P_s(w)} \dfrac{\sigma_{sv}}{\sigma_{sw}}(1 + \delta_{s \cdot }(w))$
:::info
我完全不理解發生了什麼怪事，這篇論文內也沒有解釋為何可以這樣處理。
除了這個演算法已知較快以外，我不知道為何 DrBC 要使用這個演算法的內容。
`3.1 Preliminaries` 這章節內有太多沒解釋清楚的東西，回去找 `Brandes Algorithm` 的原始論文也沒辦法直接存取，我找到的這個連結是某堂課的教材開放出來才能取得。
:::
> 3/10
`Brandes Algorithm` 有兩個階段
1. 計算從每個點 $v$ 到其他點 $u$ 的最短路徑，並取得每個點的 Predecessor
2. 將每個點底下的點想像成一個 Tree，從這個 Tree 的 leave 往 root 計算 $\delta_{u \cdot}(w)$
### 3.2 Notations
* $G = (V, E)$ 為具有每個 node 上特徵 $X_v \in R^c$ 的 graph(network)，其中 $c$ 代表輸入的特徵向量數量。
* $|V|$ 代表 graph $G$ 的 node 個數，$|E|$ 代表 graph $G$ 的 edge 個數
* $h_v^{(l)} \in R^p, l = 1, \cdots, L$ 代表第 $l$ 層運算(embedding) 的點 $v$ 向量。
* $p$ 是每層運算完後的向量維度，假設每層運算完後的維度皆相同
* 起始的特徵向量 $h_v^{(0)} = X_v$ 設為 $[d_v , 1, 1]$， $d_v$ 代表點 $v$ 的 degree(鄰居數量)，但它沒解釋兩個 $1$ 分別是什麼
* $N(v)$ 為點 $v$ 的所有鄰居(neighbor)
* $h_{N(v)}^{(l)}$ 表示在第 $l$ 層運算完後的鄰居表示狀態
### 3.3.1 DrBC encoder
* 內容是計算出 embedding
* 使用 Graph Neural Network(GNN)
* 訓練時使用較小的 graph，測試時使用很大的 graph
* encoder 內有四個不同部件：
1. Neighborhood Definition
從前面 `Branders Algorithm` 可以得知，計算 BC 時需要考慮一個點的所有鄰居，因此在運算時應該要考量到所有鄰居
訓練時僅使用較小的 graph，因此不會造成太大的運算負擔
2. Neighborhood Aggregation
每個鄰居都有 $\dfrac{\sigma_{sv}}{\sigma_{sw}}$ 的權重影響，但是在太大的 graph 內計算 shortest path 的數量會太消耗時間，改為使用 degree 作為權重可以省下時間
$h_{N(v)}^{(l)} = \displaystyle \sum_{j \in N(v)} \dfrac{1}{\sqrt{d_v + 1} \cdot \sqrt{d_j + 1}} h_{j}^{(l-1)}$
3. COMBINE Function
將目前這個 layer 運算完的點的鄰居的 embedding ($h_{N(v)}^{(l)}$)與前一個 layer 的點的 embedding ($h_{v}^{(l-1)}$)結合起來
使用 `GRU` 進行運算，運算完後的 $h_{v}^{(l)} = \text{GRUCell}(h_{v}^{(l-1)}, h_{N(v)}^{(l)})$
* $u_l$ 表示之前 layer 的多少資訊要傳送到之後的 layer
* $r_l$ 表示之前 layer 的多少資訊應該要拋棄
* $u_l = \text{sigmoid}(W_1 h_{N(v)}^{(l)} + U_1 h_{v}^{(l-1)})$
* $r_l = \text{sigmoid}(W_2 h_{N(v)}^{(l)} + U_2 h_{v}^{(l-1)})$
* $f_l = \text{tanh}(W_3 h_{N(v)}^{(l)} + U_3 (r_l \odot h_{v}^{(l-1)}))$
* $h_{v}^{(l)} = u_l \odot f_l + (1 - u_l) \odot h_{v}^{(l-1)}$
* 其中 $\odot$ 表示 `element-wise matrix multiplication`
:::info
這個部分沒有解釋 $f_l$ 為何，我暫時先把它當成一個計算中的 immediate value
:::
4. Layer Aggregation
對於高 BC 和低 BC 的點，使用相同的 iteration 去計算不太合理
這篇論文使用了 `max-pooling aggregator`，也就是做一次 element-wise $max(h_{v}^{(1)}, \cdots, h_{v}^{(l)})$ 以選出對於每種不同特徵最具有資訊的 layer 輸出
經過實驗後發現選擇 5 個 layer 的結果是最佳的
:::info
這段的敘述很長，我認為我應該沒有曲解作者本身的含意
但我已經盡力了
:::
### Encoder Algorithm
### 3.3.2 DrBC decoder
將 encoder 的輸出 $z_v$ 進行下列運算
$y_v = W_5 \text{RELU}(W_4 z_v)$
#### DrBC framework
### 3.4 Training Algorithm
假設 node pair(i, j) 的真實 BC 值為 $b_i, b_j$，定義 $b_{ij} \equiv b_i - b_j$；模型預測的 BC 值為 $y_i, y_j$，定義 $y_{ij} \equiv y_i - y_j$，使用 `binary cross-entropy cost function`
定義 Loss function = $\displaystyle \sum_{i, j \in V} C_{i, j} = \sum_{i, j \in V} -\text{sigmoid}(b_{ij}) * log(\sigma y_{ik}) - (1 - \text{sigmoid}(b_{ij})) * log(1 - \sigma y_{ik})$
:::info
原文是使用 $g(x) = \dfrac{1}{1 + e^{-x}}$ 表示我文中的 `sigmoid`，實際上兩者是相等的。
另外我稍微調整了括號的位置，原文的標示沒有很清楚
:::
## DrBC 模型訓練程式碼拆解
> 3/14
我將拆解完的成果放在 `drbc-code-dissection.ipynb` 這個檔案內。
從程式碼內看不太出上述的計算細節，計算細節都藏在 `./src/lib` 的 C++ 程式碼內。
我沒打算重新撰寫一次這些細節相關的程式碼，畢竟這次作業的重點是學會如何使用跟 graph/network 相關的 package。
這部分我會直接使用 DrBC 已經包裝完成的程式碼。
### 程式碼疑問
`self.ngraph_train` 和 `self.ngraph_test` 的用途是什麼? 每次針對 training data 或是 testing data 做 gen_graph 時就加一，但是實際效果不明。
> 3/15
`self.ngraph_train` 的用途是 Index，用來存取已經生成好的 Graph
### 重新撰寫遇到的困難(tensorflow)
`BuildNet()` 的細節我暫時沒時間進行修改，但是我發現裡面的程式碼使用的是 `tensorflow v1`。
下表紀錄了有哪些 `tensorflow v1` 的 function 以及我修改後的 `tensorflow v2` function。
Line number 是 `drbc-code-dissection.ipynb` 內第一次看到的程式碼位置。
| tensorflow v1 | tensorflow v2 | Line number |
| -------- | -------- | -- |
| tf.truncated_normal() | tf.random.truncated_normal() | line 9 |
| tf.sparse.sparse_tensor_dense_matmul() | tf.sparse.sparse_dense_matmul() | line 67 |
| tf.train.AdamOptimizer() | tf.optimizers.Adam() | line 167 |
| tf.trainable_variables() | model.trainable_variables | line 169 |
:::warning
經過以上修改後，程式仍然無法正常執行。
我意識到了一個蠻重要的問題：
`tensorflow v1` 的程式碼撰寫是從模型的頭寫到模型的尾。
而 `tensorflow v2` 的程式碼是從模型的大綱開始再撰寫到模型的細節。
:::
我在底下放了由 `ChatGPT` 產生的 `tensorflow v1` 的程式碼和 `tensorflow v2` 的程式碼。內容大致相同，已經足夠比較得出我前面所提的差異。
:::spoiler `tensorflow v1` Code
```python
# tensorflow v1
import tensorflow as tf
# Define the model
input = tf.placeholder(tf.float32, shape=[None, 784])
hidden = tf.layers.dense(input, 10, activation=tf.nn.relu)
output = tf.layers.dense(hidden, 1, activation=None)
# Define the loss
target = tf.placeholder(tf.float32, shape=[None, 1])
loss = tf.reduce_mean(tf.square(target - output))
# Define the optimizer
optimizer = tf.train.AdamOptimizer(learning_rate=0.001)
# Get the trainable variables
trainable_vars = tf.trainable_variables()
# Define the training operation
train_op = optimizer.minimize(loss, var_list=trainable_vars)
```
:::
:::spoiler `tensorflow v2` Code
```python
import tensorflow as tf
# Define the model
model = tf.keras.Sequential([
tf.keras.layers.Dense(10, activation='relu', input_shape=(784,)),
tf.keras.layers.Dense(1, activation=None)
])
# Define the loss function
loss_fn = tf.keras.losses.MeanSquaredError()
# Define the optimizer
optimizer = tf.optimizers.Adam(learning_rate=0.001)
# Get the trainable variables
trainable_vars = model.trainable_variables
# Define the training step
@tf.function
def train_step(x, y):
with tf.GradientTape() as tape:
# Forward pass
y_pred = model(x, training=True)
# Compute the loss
loss = loss_fn(y, y_pred)
# Compute the gradients
gradients = tape.gradient(loss, trainable_vars)
# Update the weights
optimizer.apply_gradients(zip(gradients, trainable_vars))
return loss
# Train the model
for epoch in range(10):
for x_batch, y_batch in train_dataset:
loss = train_step(x_batch, y_batch)
print('Epoch {}, loss: {}'.format(epoch, loss))
```
:::
考量到上述問題，我會嘗試全部重新撰寫成 `tensorflow v2` 的版本。
但是如果重新撰寫失敗，我會選擇將電腦的 `tensorflow` 版本降至 `v1` 執行。
---
為了可以參照 `tensorflow v2` 的寫法，我再次請教 `ChatGPT` 有關於如何在 `model` 內新增變數。
也參照了 [tensorflow documentation](https://www.tensorflow.org/api_docs/python/tf/keras/layers/Layer) 的內容。
:::spoiler model 內新增變數的寫法
```python
import tensorflow as tf
class MyLayer(tf.keras.layers.Layer):
def __init__(self, output_dim, **kwargs):
self.output_dim = output_dim
super(MyLayer, self).__init__(**kwargs)
def build(self, input_shape):
# Declare the trainable variable within the build() method
self.my_var = self.add_weight(name='my_var',
shape=(input_shape[-1], self.output_dim),
initializer='random_normal',
trainable=True)
def call(self, inputs):
# Compute the output using the declared variable
return tf.matmul(inputs, self.my_var)
...
model = tf.keras.Sequential([
tf.keras.layers.Dense(10, activation='relu', input_shape=(784,)),
MyLayer(20),
tf.keras.layers.Dense(1, activation='sigmoid')
])
```
:::
為了替代掉 `tensorflow v1` 內的 `tf.placeholder()` 寫法，必須轉成 `tf.keras.Input()`。
---
在 `Encoder` 和 `Decoder` 撰寫好後，想連接起來時發生錯誤。如果將 `encoder` 的輸出當成 `decoder` 的輸入直接接起來會發生以下錯誤：
目前還沒有方法可以解決這種問題。
```bash!
ValueError: Graph disconnected: cannot obtain value for tensor KerasTensor(type_spec=TensorSpec(shape=(None, None, 3), dtype=tf.float32, name='node_feat'), name='node_feat', description="created by layer 'node_feat'") at layer "concatenate_53". The following previous layers were accessed without issue: []
```
> 3/18
經過多次的重新撰寫和修改程式碼後，我正式放棄以 `tensorflow v2` 重新撰寫論文的程式碼。
一開始遇到的問題是 `encoder` 的輸出沒辦法直接給 `decoder` 作為輸入，原因是 `layer` 的輸入必須先額外定義出 `InputLayer` 才能作為 `layer` 的輸入，前一個 `layer` 的輸出自然不能當成下一個 `layer` 的輸入。
後來我的想法是和 `DrBC` 的作法類似，將 `encoder` 跟 `decoder` 併成一個 `layer` 去實作。但是實作過程中使用到了 `tensorflow` 的 `function`(如 `tf.matmul()`)，`tensorflow v2` 中大多數使用的是 `tensorflow.keras`，這東西與原本 `tensorflow` 中的 `function` 相性極差，基本上沒有辦法正常使用。
有關於所有我嘗試過的內容我都放在 `./tensorflow/my_implementation_tensorflow.ipynb` 內，我只有實驗到 `BuildNet()` 這個 `function`，之後的內容都不保證正確。
### 重新撰寫遇到的困難(pytorch geometric)
> 3/21
[main reference(pytorch geometric documentation)](https://pytorch-geometric.readthedocs.io/en/latest/tutorial/create_gnn.html)
本次重新撰寫我打算以更有結構的形式撰寫程式碼，上次重新撰寫時是直接從 `DrBC` 的核心開始著手，我發現我的能力完全不足以理解各個變數之間的關係。如果從外圍慢慢進入到核心我應該可以更加了解各個變數之間的關聯性。目前粗估撰寫程式碼的順序如下：
#### 程式碼撰寫 Flowchart
:::spoiler Flowchart
```flow
st=>start: import packages:>https://github.com/FFrankyy/DrBC[blank]
op1=>operation: 1.create dataset
op2=>operation: 2.create model
op3=>operation: 3.know how to call DrBC library
op4=>operation: 4.write training and validation code
op5=>operation: 5. test the model
cond1=>condition: Is model good enough?
e=>end: end
st->op1->op2->op3->op4->op5->cond1
cond1(yes)->e
cond1(no)->op2
```
:::
---
開始拆解生成資料集的過程發現原始程式碼具有無用變數，`self.TrainBetwRankList` 這個變數僅有宣告但完全沒有被使用到。
本次寫 `model` 時參照的是論文內的演算法，而不是像上次一樣參考原始碼撰寫。`decoder` 的部分由於沒有 `algorithm` 的圖形，直接參照 `framework` 的圖形內標示內容。
[link to encoder algorithm](#Encoder-Algorithm)
[link to full framework](#DrBC-framework)
今天做到的內容為 `flowchart` 中的 1 到 2 點，第 3 點我還在逐步嘗試並了解。 `DrBC` 自己撰寫的 `library` 其實內容還挺好懂得，可以從 `*.pyx` 得知有哪些 `method` 可以使用，並且可以從 `src/lib/*.cpp` 中了解原作者是如何實作內容的。
> 3/22
從 [`torch.nn.Module.Modules()`](https://pytorch.org/docs/stable/generated/torch.nn.Module.html#torch.nn.Module.modules) 得知了一個可以把目前模型結構列出來的方法，以下是我目前的模型內容：
:::spoiler 模型結構
```bash
0 -> DrBC(
(encoder): Encoder()
(decoder): Decoder(
(hidden): Linear(in_features=128, out_features=5, bias=True)
(relu): ReLU(inplace=True)
(output): Linear(in_features=5, out_features=1, bias=True)
)
)
1 -> Encoder()
2 -> MaxAggregation()
3 -> Linear(in_features=256, out_features=128, bias=True)
4 -> ReLU(inplace=True)
5 -> GRUCell(128, 128)
6 -> Decoder(
(hidden): Linear(in_features=128, out_features=5, bias=True)
(relu): ReLU(inplace=True)
(output): Linear(in_features=5, out_features=1, bias=True)
)
7 -> Linear(in_features=128, out_features=5, bias=True)
8 -> ReLU(inplace=True)
9 -> Linear(in_features=5, out_features=1, bias=True)
```
:::
製作好了模型後發生了一個問題，我不知道這個模型的輸入到底是什麼。我認為應該是 `node_feat` 這個變數，還需要再進行實驗。
:::info
如果以 `node_feat` 作為輸入變數，`encoder` 的 `input dimension` 會變成 $\text{node count} * \text{batch size}$。
我後來決定將 `embedding size` 設為 $\text{node count} * \text{batch size} / 16$
:::
---
有關於 [`torch.nn.CrossEntropyLoss()`](https://pytorch.org/docs/master/generated/torch.nn.CrossEntropyLoss.html?highlight=crossentropyloss#torch.nn.CrossEntropyLoss)，我還不理解為何計算完之後要加一個 `output.backward()`，透過這個能夠更新那些東西？
我從網路上大概得知可以用來得到微分，但我有了這個微分數值後可以做什麼？
> 3/24
目前進行到 [`flowchart`](#程式碼撰寫-Flowchart) 的第四步，我在嘗試撰寫 `training` 相關的程式碼，從 `pytorch` 的範例程式碼中看到了一些我不理解的事情，主要有三個問題需要解決：
1. `optimizer.zero_grad()`
2. `loss.backward()`
3. `optimizer.step()`
:::spoiler pytorch 範例程式碼
```python
...
learning_rate = 1e-3
optimizer = torch.optim.RMSprop(model.parameters(), lr=learning_rate)
for t in range(2000):
# Forward pass: compute predicted y by passing x to the model.
y_pred = model(xx)
# Compute and print loss.
loss = loss_fn(y_pred, y)
if t % 100 == 99:
print(t, loss.item())
# Before the backward pass, use the optimizer object to zero all of the
# gradients for the variables it will update (which are the learnable
# weights of the model). This is because by default, gradients are
# accumulated in buffers( i.e, not overwritten) whenever .backward()
# is called. Checkout docs of torch.autograd.backward for more details.
optimizer.zero_grad()
# Backward pass: compute gradient of the loss with respect to model
# parameters
loss.backward()
# Calling the step function on an Optimizer makes an update to its
# parameters
optimizer.step()
...
```
:::
這三個 `method` 都屬於我沒辦法直接看出到底做了哪些事情，在詢問同學以及重新閱讀程式碼後，我對於這三個 `method` 有了一點想法，以下是我的解讀：
* `optimizer.zero_grad()`
* 將 `optimizer` 的 `gradient` 先設為 $0$，目的是為了避免前一次的 `gradient` 影響到下一次的運算。
* `loss.backward()`
* 直接計算各個參數的微分並且更新參數
* `optimizer.step()`
* 更新 `optimizer` 內的參數
以上解讀可能還是有錯誤，但我已經嘗試去理解了。
---
我發現我沒有把 `DrBC library` 的 `pair_ids_src` 跟 `pair_ids_tgt` 拿來使用，我認為這兩個數值應該是用來計算 `Betweeness Centrality` 的關鍵。
另外我現在才注意到 `loss function` 和 `prediction` 時使用的內容似乎不太一樣，`loss function` 做的是比較 `Betweeness Centrality` 的差距值，`prediction` 做的是比較 `pair_ids_src` 以及 `pair_ids_tgt` 的差距，我還得花更多時間才能釐清兩者之間的關係。
---
有關於之前提到設定 `model` 的參數大小，如果我將 `training set` 中的 `graph` 的 `node count` 設為 $256$，`batch size` 設為 $32$，一個 `GRUCell` 需要 $192.0\ \text{GiB}$，我沒有那麼強力的東西可以跑得動這東西，要先逐步降低才能正常執行。
* **更新**：我不小心誤把 `embedding size` 設為這兩個數字相乘後再乘以 $16$ ，應該是這個原因導致數值爆炸。
另外有關於輸出檔案的部分，我竟然會卡在怎麼創立一個空的檔案...參考了 [`stackoverflow`](https://stackoverflow.com/questions/1158076/implement-touch-using-python) 的網站實作方式。
:::warning
更新：結果不是需要創立空檔案，只是因為 `./models` 這個目錄不存在而報錯
:::
---
我發現我的模型缺乏了 `edge_index` 這個輸入參數，進一步追蹤後發現這個參數應該是對應到 `DrBC` 的 `n2nsum_param` 的參數，在 `DrBC` 的實作內將這個參數以 `sparse matrix` 的形式儲存著，我得再研究才能曉得如何使用。
當我要使用 `crow_indices()` 取回 `edge_index` 中的 `row_index` 時發生了 `NotImplementedError`(詳細內容如下
)，我得再尋找如何替換掉 `backend` 才能取得。
:::spoiler
```bash!
NotImplementedError: Could not run 'aten::crow_indices' with arguments from the 'SparseCUDA' backend. This could be because the operator doesn't exist for this backend, or was omitted during the selective/custom build process (if using custom build). If you are a Facebook employee using PyTorch on mobile, please visit https://fburl.com/ptmfixes for possible resolutions. 'aten::crow_indices' is only available for these backends: [SparseCsrCPU, SparseCsrCUDA, BackendSelect, Python, Named, Conjugate, Negative, ZeroTensor, ADInplaceOrView, AutogradOther, AutogradCPU, AutogradCUDA, AutogradXLA, AutogradLazy, AutogradXPU, AutogradMLC, AutogradHPU, AutogradNestedTensor, AutogradPrivateUse1, AutogradPrivateUse2, AutogradPrivateUse3, Tracer, AutocastCPU, Autocast, Batched, VmapMode, Functionalize].
```
:::
> 3/25
我回去了解了 `DrBC` 對於 `n2num_param` 的實作發現他們會將這個參數包裝成 `COO sparse matrix` 的形式輸出，因此我也跟著他的做法並將原本的 `tensorflow v1` 程式碼改寫成 `torch` 的程式碼。接著我發現可以直接透過呼叫 `.indices()` 取得 `row index` 和 `column index`
目前發生的狀況是傳入 `MessagePassing.propagate()` 發生了一些怪事，這個 `method` 會自動呼叫 `MessagePassing.message()`，而傳入這個 `method` 有 `x_j` 和 `norm`，但這個 `method` 很像有些地方不太正常。以下是我的實作：
:::spoiler MessagePassing.message()
```python=62
def message(self, x_j, norm):
# x_j has shape [E, out_channels]
# Step 4: Normalize node features.
print("x_j: type {}, shape: {}".format(type(x_j), x_j.size()))
print("norm: type {}, shape: {}".format(type(norm), norm.size()))
if norm is None:
return x_j
else:
return norm.view(-1, 1) * x_j
```
:::
以上內容可以執行後會有以下輸出：
:::spoiler 輸出內容
```bash
x_j: type <class 'torch.Tensor'>, shape: torch.Size([8952, 64])
norm: type <class 'torch.Tensor'>, shape: torch.Size([8952])
...
Input In [7], in Encoder.message(self, x_j, norm)
62 def message(self, x_j, norm):
63 # x_j has shape [E, out_channels]
64
65 # Step 4: Normalize node features.
---> 66 print("x_j: type {}, shape: {}".format(type(x_j), x_j.size()))
67 print("norm: type {}, shape: {}".format(type(norm), norm.size()))
68 if norm is None:
AttributeError: 'NoneType' object has no attribute 'size'
```
:::
看到這邊我真的是不理解發生了什麼事情，`x_j` 可以印出 `type` 和 `shape`，但是他又跟我說這是 `NoneType`？我唯一能解釋的方式是第二次呼叫此 `method` 時 `x_j` 不知道掉去哪裡，但是又沒有一個正確解答。
我目前猜測是不同 `layer` 之間的 `x_j` 會被丟到不見，第一次列印成功是第一個 `layer` 的結果，第二個 `layer` 的 `x_j` 在運算時不知道發生什麼怪事就被丟掉。
---
我找到這篇論文計算 `betweeness centrality` 的位置在哪了，他的呼叫是使用 `utils.py_Utils().Betweenness()` 來直接取得 `BC`，但是我目前需要的 `bc_log` 是空的，看起來我只能根據這個 `BC` 以及 `DrBC` 的 `library` 內容重新手刻計算過程。
---
經過大量的 debug 時間後，整個程式可以跑了，但是看起來還是有許多錯誤需要解決。
從以下的輸出可以得知我的模型應該是有重大錯誤，才會得到 `loss` 等於 $0$
我將這個可以跑出結果的程式碼放於 `./first_runnable` 作為備份以及紀念，撰寫了兩個多禮拜的程式碼終於可以正常執行了。
```bash
iter 0, Top0.01: 1.000000, kendal: 0.000000
testing 100 graphs time: 2.21s
500 iterations total time: 52.61s
Training loss is 0.0000
5%|███▌ | 500/10000 [00:22<07:48, 20.28it/s]
```
我使用 `pandas.DataFrame` 回頭去找在 `fit` 時 `prediction` 和 `label` 的狀況，發現了一個異常：
:::spoiler 輸出結果
```bash
# prediction
0
0 -0.085814
1 -0.087843
2 -0.088259
3 -0.087843
4 -0.088259
... ...
4091 -0.085896
4092 -0.085896
4093 -0.085896
4094 -0.085896
4095 -0.085896
# label
0
0 7.563165
1 5.219191
2 5.079460
3 5.170758
4 5.074898
... ...
4091 6.964626
4092 7.429688
4093 7.040573
4094 6.899422
4095 7.060764
```
:::
從這個輸出結果，我猜測可能是模型輸出時有異常，或是我必須做完標準化後才能計算 `loss value`。
另外，不只是數值上的異常，`prediction` 最後五筆的資料也很奇怪，每個資料的數值都是相同的。
> 3/26
我晚上睡覺時突然注意到了這兩筆資料的關聯性，有可能在於 $-log_{10}()$ 的這個操作上。我的 `training data` 的 `label` 有做這個處理，而 `testing data` 的 `label` 沒有做這個處理。因此我先嘗試計算 `label` 第一個數值經過轉換後的狀況，得到 $-log_{10}(7.563165) \simeq -0.8787$，對照我的 `prediction` 的結果 $-0.085814$ 就發現像多了，只是 `prediction` 的結果跟 `label` 差了一個位數。我應該先嘗試去除 $-log_{10}()$ 這個算式，再看看我可以做什麼修改。
做了以上修改後，重新列印出 `prediction` 和 `label` 的內容：
:::spoiler 輸出結果
```bash
# prediction
0
0 0.094251
1 0.094251
2 0.094251
3 0.094251
4 0.094251
... ...
4091 0.094251
4092 0.094251
4093 0.094251
4094 0.094251
4095 0.094251
# label
0
0 0.023779
1 0.025899
2 0.119236
3 0.050261
4 0.130700
... ...
4091 0.000827
4092 0.001653
4093 0.000896
4094 0.000421
4095 0.001010
```
:::
我同時也將做 `Predict` 時的模型 `prediction` 結果和 `label` 也用同樣方法列印出來，得到的結果如下：
:::spoiler 輸出結果
```bash
# prediction
0
0 0
1 0
2 0
3 0
4 0
... ...
123 0
124 0
125 0
126 0
127 0
# label
0
0 0.028179
1 0.084506
2 0.150675
3 0.014735
4 0.169698
... ...
123 0.001397
124 0.003497
125 0.001370
126 0.000995
127 0.001492
```
:::
綜合上面結果，我只覺得狀況比修改前更糟，原本的數值還會有一些變化，目前則是所有數值都相同。不過目前應該可以確定一點：我的模型製作上應該有誤。而至於錯在哪裡... 我不知道。
---
經過了數百個 `iteration` 的持續數值追蹤，我發現 `prediction` 的數值還是有變化，但是變化的位置大約在小數點後第五位至第六位。換言之我的 `learning rate` 可能過小，才導致這種問題。另外我現在才想起來標準化這件事情的存在，我應該先花點時間處理好標準化再進行測試。
對於 `fit` 的 `prediction` 和 `label` 進行標準化後得到以下結果：
:::spoiler 輸出結果
```bash
# prediction
0
0 1.0
1 1.0
2 1.0
3 1.0
4 1.0
... ...
4091 1.0
4092 1.0
4093 1.0
4094 1.0
4095 1.0
# label
0
0 0.014427
1 0.045485
2 0.067565
3 0.075842
4 0.094192
... ...
4091 0.001652
4092 0.001744
4093 0.001804
4094 0.001519
4095 0.001051
```
:::
因為前面提過 `prediction` 的輸出數值皆相同，標準化後自然都變為 $1$ 了，另外我也對於 `label` 做了標準化，但我總覺得這個 `label` 數值也有點不正常了。
---
附帶一提，把 `gen_train_graph()` 放在 `training` 的迴圈中會有這種我難以解釋的輸出，如果獨立執行時則不會有以下輸出，以下輸出結果來自於 `trange()` 的呼叫。
:::spoiler `trange()` 在 `gen_train_graph()` 的奇怪輸出
```bash
0%| | 0/10000 [00:00<?, ?it/s]
0%| | 0/1000 [00:00<?, ?it/s]
3%|██▎ | 32/1000 [00:00<00:03, 310.05it/s]
6%|████▋ | 64/1000 [00:00<00:03, 310.38it/s]
10%|███████ | 96/1000 [00:00<00:02, 310.96it/s]
13%|█████████▏ | 128/1000 [00:00<00:02, 305.70it/s]
16%|███████████▍ | 159/1000 [00:00<00:02, 301.34it/s]
19%|█████████████▋ | 190/1000 [00:00<00:02, 298.78it/s]
22%|███████████████▉ | 221/1000 [00:00<00:02, 300.23it/s]
25%|██████████████████▏ | 252/1000 [00:00<00:02, 292.20it/s]
28%|████████████████████▎ | 282/1000 [00:00<00:02, 293.09it/s]
31%|██████████████████████▌ | 313/1000 [00:01<00:02, 295.97it/s]
34%|████████████████████████▋ | 343/1000 [00:01<00:02, 294.83it/s]
37%|██████████████████████████▉ | 374/1000 [00:01<00:02, 297.71it/s]
40%|█████████████████████████████▏ | 405/1000 [00:01<00:01, 298.71it/s]
44%|███████████████████████████████▍ | 436/1000 [00:01<00:01, 299.40it/s]
47%|█████████████████████████████████▌ | 467/1000 [00:01<00:01, 300.98it/s]
50%|███████████████████████████████████▊ | 498/1000 [00:01<00:01, 299.56it/s]
53%|██████████████████████████████████████ | 529/1000 [00:01<00:01, 301.54it/s]
56%|████████████████████████████████████████▎ | 560/1000 [00:01<00:01, 302.50it/s]
59%|██████████████████████████████████████████▌ | 591/1000 [00:01<00:01, 301.41it/s]
62%|████████████████████████████████████████████▊ | 622/1000 [00:02<00:01, 232.93it/s]
65%|███████████████████████████████████████████████ | 653/1000 [00:02<00:01, 250.83it/s]
68%|█████████████████████████████████████████████████▏ | 684/1000 [00:02<00:01, 265.37it/s]
72%|███████████████████████████████████████████████████▍ | 715/1000 [00:02<00:01, 275.55it/s]
75%|█████████████████████████████████████████████████████▋ | 746/1000 [00:02<00:00, 282.83it/s]
78%|███████████████████████████████████████████████████████▉ | 777/1000 [00:02<00:00, 288.76it/s]
81%|██████████████████████████████████████████████████████████▏ | 808/1000 [00:02<00:00, 292.76it/s]
84%|████████████████████████████████████████████████████████████▍ | 839/1000 [00:02<00:00, 296.54it/s]
87%|██████████████████████████████████████████████████████████████▋ | 870/1000 [00:02<00:00, 299.51it/s]
90%|████████████████████████████████████████████████████████████████▊ | 901/1000 [00:03<00:00, 300.95it/s]
93%|███████████████████████████████████████████████████████████████████ | 932/1000 [00:03<00:00, 302.52it/s]
96%|█████████████████████████████████████████████████████████████████████▎ | 963/1000 [00:03<00:00, 303.53it/s]
100%|███████████████████████████████████████████████████████████████████████| 1000/1000 [00:03<00:00, 292.83it/s]
```
:::
---
我突然想到一個問題，會不會是我的 `loss function` 選錯了？從上面的實驗結果中得知，`prediction` 和 `label` 都是有對應數值的。但是不論如何，`mean_loss` 的結果都是 $0$，我目前先試驗看看不同 `loss function` 會帶來哪些影響。
我將 `loss function` 改為 [`torch.nn.functional.binary_cross_entropy_with_logits`](https://pytorch.org/docs/stable/generated/torch.nn.functional.binary_cross_entropy_with_logits.html?highlight=binary_cross_entropy_with_logits#torch.nn.functional.binary_cross_entropy_with_logits)，修改後的 `training loss` 可以得出一個數值了，但我也不確定這樣是否正確。
另外對於 `Learning Rate`，我將初始數值從 $10^{-4}$ 改為 $10^{-3}$，而且額外加上 [`exponential decay`](https://pytorch.org/docs/stable/generated/torch.optim.lr_scheduler.ExponentialLR.html?highlight=exponentiallr#torch.optim.lr_scheduler.ExponentialLR)，每 $500$ 次 `iteration` 會將 `learning rate` 乘上之前的數值的 $0.9$ 倍。
---
另外我開始注意到輸出的 `Top0.01: 1.000000, kendal: 0.000000`，經過仔細的追蹤 `DrBC library` ([`./src/lib/metrics.cpp`](https://github.com/FFrankyy/DrBC/blob/master/src/lib/metrics.cpp#L46))後我有了以下理解：
* `Top0.01` 的意思是在所有 `node` 的前 `1%` 的數值在 `prediction` 和 `label` 中都不為 $0$ 的比例。我覺得很詭異，兩個數值皆不為 $0$ 的狀況應該是非常常見的，除非 `DrBC` 中有針對數值極低的做過處理，不然 `Top0.01` 這個數值本身不具有任何意義。
* **更正**：剛剛讀程式碼時出了一點錯誤，實際狀況是分別取 `label` 和 `prediction` 的前 `1%` 數值，並將這前 `1%` 的數值分別回去和原始資料找對應關係。如果有找到一次就 $+1$，直到分別將這兩個陣列全部查找完為止。因此我還是不理解 `Top0.01` 的數值意義是什麼，查找的對應關係也不是從 `prediction` 到 `label` 而是 `prediction` 到 `prediction`。
* `kendal` 的部分我嘗試讀了，但是程式碼內容太過難以理解發生什麼狀況，半小時後都找不到一個切入的線索。
---
目前要做[`flowchart`](#程式碼撰寫-Flowchart) 的第五步`(test the model)`，我突然意識到一個問題：我目前的模型是假設輸入的 `size` 為 $(\text{node count}, 3)$。根據之前的內容，我的模型只能接受 $(4096, 3)$ 的輸入，理論上不能直接輸入測試資料的 $(5000, 3)$。我目前想到一個方法是把原本模型的第一個 `Linear layer` 去除掉，說不定就可以接受各種輸入的 `size`。
在上述的問題發生以前，我就已經先發生一個問題了。我的 `embedding size` 當初是設成 $\text{node count} * \text{batch size} / 16$，這樣的設計會因為 `node count` 不同自然就不可能正常執行，我得先將 `embedding size` 設為固定值($256$)才能正常執行。
---
我發現我在處理測試資料時不小心把 $30$ 個 `graph` 全部混成同份資料了，實際執行時應該是要取得這 $30$ 個資料的分別準確率並且計算平均值與標準差。以下內容是我原本的程式碼，以作為備份使用。
:::spoiler 處理測試資料相關程式碼
```python
# Prepare testing data
score_path_list = []
data_path_list = []
for file in os.listdir(DATA_PATH):
if "score" in file:
score_path_list.append(os.path.join(DATA_PATH, file))
else:
data_path_list.append(os.path.join(DATA_PATH, file))
# create label and edge_index
test_label_list = []
test_row_index_list = []
test_col_index_list = []
degree_list = np.zeros((feature_count, 1))
for score_path, data_path in zip(score_path_list, data_path_list):
score_file_descriptor = open(score_path, "r")
data_file_descriptor = open(data_path, "r")
score_lines = score_file_descriptor.readlines()
data_lines = data_file_descriptor.readlines()
for line in score_lines:
test_label_list.append(float(line.split("\t")[1].strip("\n")))
for line in data_lines:
edge_from, edge_to = int(line.split("\t")[0]), int(line.split("\t")[1].strip("\n"))
degree_list[edge_from] = degree_list[edge_from] + 1
test_row_index_list.append(edge_from)
test_col_index_list.append(edge_to)
score_file_descriptor.close()
data_file_descriptor.close()
test_edge_index_list = np.stack((test_row_index_list, test_col_index_list))
# create node feature data from degree ([dc, 1, 1])
ones_list = np.ones((feature_count, 1))
test_node_feature_list = np.hstack((degree_list, ones_list, ones_list))
# print(test_node_feature_list.shape)
# print(test_node_feature_list[0])
# print input features
dataframe = pd.DataFrame(test_node_feature_list)
with pd.option_context('display.max_rows', None,
'display.max_columns', None,
'display.precision', 3,
):
print(dataframe)
# conver to tensor
test_label = torch.tensor(test_label_list).to(device)
test_edge_index = torch.tensor(test_edge_index_list).to(device)
test_node_feature = torch.tensor(test_node_feature_list).to(device)
```
:::
成功載入所有資料後還是有個問題，我之前都是使用 `DrBC library` 製作資料，如何從載入的資料變成可以與 `DrBC library` 共通的狀態都是一個問題。目前主要的狀況是 `edge_index` 必須轉為前面提到的 `COO sparse matrix`，要能做到這件事情基本上要直接依賴 `DrBC library` 的實作方式，我不太想手刻出整個實作內容。
我在 `networkx` 上找到直接使用 `edge_index` 直接做出 `graph` 的方法了，使用 [`nx.from_edgelist`](https://networkx.org/documentation/stable/reference/generated/networkx.convert.from_edgelist.html) 或是 `nx.Graph()` 就可以直接建出來，有個差別是 `edge_index` 的生成是使用到 `np.stack()`，而要生成 `graph` 的話必須改成使用 `list(zip())` 來達成。這是因為這個 `method` 的輸入必須改為 `list of tuples` 才可以正常運作。
另外即使拿到了 `graph`，也必須再呼叫一次 `DrBC library` 才可以將數值輸入進模型內，處理方法和訓練資料完全相同。
## 最終結果
筆記本位於 `./pytorch/my_implementation_pytorch.ipynb`在我的環境(參見下方表格)下執行時間約為 25 分鐘
| | |
| -------- | -------- |
| CPU | AMD Ryzen 9 3900X 12-Core Processor |
| GPU | NVIDIA GeForce RTX 3070 (VRAM 8GiB) |
| RAM | 12 GB |
每次 `iteration` 都會從 `training data` 中取出 `batch size(32)` 個 `graph` 進行訓練。
參數細節：
| | |
| -------- | -------- |
| number of nodes in training data | $128$ |
| number of graphs in training data | $1000$ |
| batch size | $32$ |
| number of graphs in validation data | $100$ |
| max iteration | $10000$ |
| initial learning rate | $10^{-3}$ |
| embedding size | $256$ |
模型細節：
```bash
0 -> DrBC(
(encoder): Encoder()
(decoder): Decoder(
(hidden): Linear(in_features=256, out_features=5, bias=True)
(relu): ReLU(inplace=True)
(output): Linear(in_features=5, out_features=1, bias=True)
)
)
1 -> Encoder()
2 -> MaxAggregation()
3 -> Linear(in_features=3, out_features=256, bias=True)
4 -> ReLU(inplace=True)
5 -> GRUCell(256, 256)
6 -> Decoder(
(hidden): Linear(in_features=256, out_features=5, bias=True)
(relu): ReLU(inplace=True)
(output): Linear(in_features=5, out_features=1, bias=True)
)
7 -> Linear(in_features=256, out_features=5, bias=True)
8 -> ReLU(inplace=True)
9 -> Linear(in_features=5, out_features=1, bias=True)
```
執行結果：
```bash
top 1% with accuracy mean 0.00000 and standard deviation 0.00000
top 5% with accuracy mean 0.00000 and standard deviation 0.00000
top 10% with accuracy mean 0.00000 and standard deviation 0.00000
kendal with accuracy mean 0.41287 and standard deviation 0.04434
time with accuracy mean 0.00082 and standard deviation 0.00006
```
我認為我已經盡力達成了，盡我的能力去理解 `DrBC`、`tensorflow`、`pytorch`、`pytorch geometric`，但我不知道是哪個細節做錯才導致這種狀況的發生。可能是模型建置出錯，也可能是我在某個區塊的計算出錯，也有可能是我使用 `DrBC library` 時用錯了。
感謝教授多給一周時間讓我繼續做這份作業，在一周前這份作業都還卡在 `tensorflow` 裡面，在這多出來的一周裡我大致了解了 `pytorch` 怎麼使用。
最後在看到那份[`flowchart`](#程式碼撰寫-Flowchart)，"Is model good enough?"，絕對還是不夠。連撰寫這份程式碼的我都還不能解釋為何 `accuracy` 是 $0\%$，還是只能繼續回去調整模型狀況。
###### tags: `1112_courses` `social network`
Sign in with Wallet
Connect another wallet