論文資訊
論文标題：PairNorm: Tackling Oversmoothing in GNNs
論文作者：Lingxiao Zhao, Leman Akoglu
論文來源：2020,ICLR
論文位址：download
論文代碼：download
1 Introduction
GNNs 的表現随着層數的增加而有所下降，一定程度上歸結于 over-smoothing 問題，重複圖卷積操作會使得節點表示最終變得不可區分。為緩解過平滑問題提出了 PairNorm， 一種歸一化方法。
比較可惜的時，該論文在使用了 2022 年的 "Mask" 政策，可惜了實驗做的不咋好。為什麼失敗，見文末。太可惜了...
2 Understanding oversmoothing
Definition
$\tilde{\mathbf{A}}_{\mathrm{sym}}=\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}$
$\tilde{\mathbf{A}}_{\mathrm{rw}}=\tilde{\mathbf{D}}^{-1} \tilde{\mathbf{A}}$
2.1 The oversmoothing problem
2.1.1 Oversmoothing
GNN 性能下降的原因：
-
- 參數數量的增加；
- 梯度消失導緻訓練困難；
- 圖卷積而造成的過平滑；
過平滑的考慮方法如下：當多次使用拉普拉斯平滑導緻節點特征收斂到一個平穩點。假設 $\mathbf{x}_{\cdot j} \in \mathbb{R}^{n}$ 表示 $\mathbf{X}$ 的第 $j $ 列，對于任意 $\mathbf{x}_{\cdot j} \in \mathbb{R}^{n}$：
$\begin{array}{l}\underset{k \rightarrow \infty}{\text{lim}} \quad \tilde{\mathbf{A}}_{\mathrm{sym}}^{k} \mathbf{x}_{\cdot j} =\boldsymbol{\pi}_{j}\\ \text { and } \quad \frac{\boldsymbol{\pi}_{j}}{\left\|\boldsymbol{\pi}_{j}\right\|_{1}}=\boldsymbol{\pi}\end{array}$
其中，标準化解 $\pi \in \mathbb{R}^{n}$ 滿足 $\boldsymbol{\pi}_{i}=\frac{\sqrt{\operatorname{deg}_{i}}}{\sum_{i} \sqrt{\operatorname{deg}_{i}}} \text{ for all } i \in[n]$。
Note：$\boldsymbol{\pi}$ 不依賴于節點特征矩陣，而是一個單純依靠圖結構度的函數。
2.1.2 Its Measurement
本文提出兩種度量過平滑的方式：$\text{row-diff}$ 和 $\text{col-diff}$。
設 $\mathbf{H}^{(k)} \in \mathbb{R}^{n \times d}$ 為第 $k$ 個圖卷積後的節點表示矩陣，即 $\mathbf{H}^{(k)}=\tilde{\mathbf{A}}_{\mathrm{sym}}^{k} \mathbf{X}$。設 $\mathbf{h}_{i}^{(k)} \in \mathbb{R}^{d}$ 為 $\mathbf{H}^{(k)}$ 的第 $i$ 行，$\mathbf{h}_{. i}^{(k)} \in \mathbb{R}^{n}$ 為 $\mathbf{H}^{(k)}$ 的第 $i$ 列。
$\text{row-diff}( \left.\mathbf{H}^{(k)}\right)$ 和 $\text{col-diff}( \left.\mathbf{H}^{(k)}\right)$ 的定義如下：
${\large \operatorname{row}-\operatorname{diff}\left(\mathbf{H}^{(k)}\right) =\frac{1}{n^{2}} \sum\limits _{i, j \in[n]}\left\|\mathbf{h}_{i}^{(k)}-\mathbf{h}_{j}^{(k)}\right\|_{2}} \quad\quad\quad(2)$
${\large \operatorname{col-diff}\left(\mathbf{H}^{(k)}\right) =\frac{1}{d^{2}} \sum\limits _{i, j \in[d]}\| \frac{\mathbf{h}_{\cdot i}^{(k)}}{\|\mathbf{h}_{\cdot i}^{(k)}\|_{1}}-\frac{\mathbf{h}_{\cdot j}^{(k)}}{\|\mathbf{h}_{\cdot j}^{(k)}\|_{1}} \|_{2}} \quad\quad\quad(3) $
$\text{row-diff}$ 量化節點之間的成對距離，而 $\text{col-diff}$ 特征之間的成對距離。
2.2 Studying oversmoothing with SGC
GCN 過平滑可能由于層數增加導緻的性能下降，即添加更多的層導緻更多的參數（添加的線性層 存在 $\mathbf{W}^{(k)}$）容易導緻過拟合。同樣層數增加，容易存在反向傳播梯度的消失（應該指的是參數多）。
将層數增加影響過平滑和 使用參數導緻過拟合即反向傳播梯度消失 解耦。本文使用 SGC ，一種簡化的 GCN :去除圖卷積層的所有投影參數和所有層間的非線性激活。SGC可寫為：
$\widehat{\boldsymbol{Y}}=\operatorname{softmax}\left(\tilde{\mathbf{A}}_{\mathrm{sym}}^{K} \mathbf{X} \mathbf{W}\right) \quad\quad\quad(4) $
其中，$K$ 為圖卷積的個數，$\mathbf{W} \in \mathbb{R}^{d \times c}$ 表示可學習參數。
Note：SGC有一個固定數量的參數，不依賴于圖卷積的數量（即層），也是以防止了過拟合和消失梯度問題的影響。
那麼，這隻給我們留下了過平滑作為随着 $K$ 增加的性能下降的可能原因。需要注意的是 SGC 并不是一種犧牲，在某些分類任務似乎有更好或者相似的準确性。
Figure 1 中的虛線說明了當增加層數( $K$ )時，SGC 在 Cora 資料集上的性能。訓練（交叉熵）損失随着 $K$ 的增大而單調地增加，這可能是因為圖卷積将節點表示與它們的鄰居混合在一起，使它們變得不那麼容易區分（訓練變得更加困難）。另一方面，至多到 $K=4$，圖卷積（即平滑）提高了泛化能力，減少了訓練和驗證/測試損失之間的差距，之後，過平滑開始影響性能。$\text{row-diff}$ 和 $\text{col-diff}$ 都随 $K$ 繼續單調遞減，為過平滑提供了支援證據。
3 Tackling oversmoothing
3.1 Proposed pairnorm
考慮圖正則化最小二乘(GRLS)：設 $\overline{\mathbf{X}} \in \mathbb{R}^{n \times d}$ 是節點表示矩陣，其中 $\overline{\mathbf{x}}_{i} \in \mathbb{R}^{d}$ 表示 $\overline{\mathbf{X}}$ 的第 $i$ 行，GRLS 問題為：
$\underset{\overline{\mathbf{x}}}{\text{min}} \sum\limits _{i \in \mathcal{V}}\left\|\overline{\mathbf{x}}_{i}-\mathbf{x}_{i}\right\|_{\tilde{\mathbf{D}}}^{2}+\sum\limits_{(i, j) \in \mathcal{E}}\left\|\overline{\mathbf{x}}_{i}-\overline{\mathbf{x}}_{j}\right\|_{2}^{2}\quad\quad\quad(5)$
其中：
-
- $\left\|\mathbf{z}_{i}\right\|_{\tilde{\mathbf{D}}}^{2}=\mathbf{z}_{i}^{T} \tilde{\mathbf{D}} \mathbf{z}_{i}$；
第一項可以看作是度權重最小二乘，第二個是一個圖正則化項，度量新特征在圖結構上的變化。
優化問題的目标可認為是估計新的 “去噪” 特征 $\overline{\mathbf{x}}_{i}$ 離輸入特征 $\mathbf{x}_{i}$ 不遠，并且在圖結構上很平滑。
GRLS 問題有一個封閉形式的解 $\overline{\mathbf{X}}=\left(2 \mathbf{I}-\tilde{\mathbf{A}}_{\mathrm{rw}}\right)^{-1} \mathbf{X}$，其中 $\tilde{\mathbf{A}}_{\mathrm{rw}} \mathbf{X}$ 是一階泰勒近似，即 $\tilde{\mathbf{A}}_{\mathrm{rw}} \mathbf{X} \approx \overline{\mathbf{X}}$。通過替換 $\tilde{\mathbf{A}}_{\mathrm{rw}}$ 為 $\tilde{\mathbf{A}}_{\text {sym }}$，得到與圖卷積相同的形式，即 $\tilde{\mathbf{X}}=\tilde{\mathbf{A}}_{\text {sym }} \mathbf{X} \approx \overline{\mathbf{X}}$。是以，圖卷積可以看作是 $\text{Eq.5}$ 的近似解，它最小化了圖結構上的變化，同時保持新的表示接近原始表示。
理想情況下，希望獲得對同一叢集内的節點的平滑，但是避免平滑來自不同叢集的節點。$\text{Eq.5}$ 中的目标通過圖正則化項隻優化第一個目标。是以，當重複應用卷積時，它容易出現過平滑。為規避這個問題并同時實作這兩個目标，可以添加一個負項，如沒有邊連接配接對之間的距離之和如下：
$\underset{\overline{\mathbf{x}}}{\text{min}} \sum\limits _{i \in \mathcal{V}}\left\|\overline{\mathbf{x}}_{i}-\mathbf{x}_{i}\right\|_{\tilde{\mathbf{D}}}^{2}+\sum\limits_{(i, j) \in \mathcal{E}}\left\|\overline{\mathbf{x}}_{i}-\overline{\mathbf{x}}_{j}\right\|_{2}^{2}-\lambda \sum_{(i, j) \notin \mathcal{E}}\left\|\overline{\mathbf{x}}_{i}-\overline{\mathbf{x}}_{j}\right\|_{2}^{2}\quad\quad\quad(6)$
同樣，可通過推導 $\text{Eq.6}$ 的封閉型解并用一階泰勒展開進行逼近，得到一個具有超參數 $\lambda$ 的修正圖卷積算子。
在本文中，沒有提出了一個全新的圖卷積算子，而是提出了一個通用的、有效的 “更新檔”，稱為 PAIRNORM，它可以應用于具有過平滑潛力的任何形式的圖卷積。
設 $\tilde{\mathbf{X}}$（圖卷積的輸出）和 $\dot{\mathbf{X}}$ 分别為 PAIRNORM 的輸入和輸出。觀察到圖卷積 $\tilde{\mathbf{X}}=\tilde{\mathbf{A}}_{\text {sym }} \mathbf{X}$ 的輸出實作了第一個目标 度權重，PAIRNORM 作為一個标準化層，在 $\tilde{\mathbf{X}}$ 上工作，以實作第二個目标，即保持未連接配接的對表示更遠。具體來說，PAIRNORM 将 $\tilde{\mathbf{X}}$ 歸一化，使總成對平方距離 $\operatorname{TPSD}(\dot{\mathbf{X}}):=\sum\limits_{i, j \in[n]}\left\|\dot{\mathbf{x}}_{i}-\dot{\mathbf{x}}_{j}\right\|_{2}^{2} $ 和 $\operatorname{TPSD}(\mathbf{X} )$ 一樣：
$ \sum\limits_{(i, j) \in \mathcal{E}}\left\|\dot{\mathbf{x}}_{i}-\dot{\mathbf{x}}_{j}\right\|_{2}^{2}+\sum\limits_{(i, j) \notin \mathcal{E}}\left\|\dot{\mathbf{x}}_{i}-\dot{\mathbf{x}}_{j}\right\|_{2}^{2}=\sum\limits_{(i, j) \in \mathcal{E}}\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}^{2}+\sum\limits_{(i, j) \notin \mathcal{E}}\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}^{2} \quad\quad\quad(7)$
理想情況下，希望 $\sum\limits _{(i, j) \notin \mathcal{E}}\left\|\dot{\mathbf{x}}_{i}-\dot{\mathbf{x}}_{j}\right\|_{2}^{2}$ 和 $\sum\limits _{(i, j) \notin \mathcal{E}}\left\|\mathbf{x}_{i}-\mathbf{x}_{j}\right\|_{2}^{2}$ 一樣大，$\sum\limits _{(i, j) \in \mathcal{E}}\left\|\dot{\mathbf{x}}_{i}-\dot{\mathbf{x}}_{j}\right\|_{2}^{2} \approx \sum\limits _{(i, j) \in \mathcal{E}}\left\|\tilde{\mathbf{x}}_{i}-\tilde{\mathbf{x}}_{j}\right\|_{2}^{2}$ 是由于拉普拉斯平滑的原因。
實踐中，不需要時刻關注 $\operatorname{TPSD}(\mathbf{X} )$ 的值，隻需要在所有層使得 $\operatorname{TPSD}(\mathbf{X} )$ 保持一個恒定的常量 $C$。
為計算 $\operatorname{TPSD}(\mathbf{X} )$ 的常數值，可先計算 $\operatorname{TPSD}(\tilde{\mathbf{X}})$。當然直接計算 $\operatorname{TPSD}(\tilde{\mathbf{X}})$ 涉及到 $n^{2}$ 個成對的距離 $\mathcal{O}\left(n^{2} d\right)$，這對大資料集來說是十分耗時間的。
同樣地，規範化可以通過一個兩步的方法來完成，其中 $\operatorname{TPSD}$ 被重寫為
$\operatorname{TPSD}(\tilde{\mathbf{X}})=\sum\limits_{i, j \in[n]}\left\|\tilde{\mathbf{x}}_{i}-\tilde{\mathbf{x}}_{j}\right\|_{2}^{2}=2 n^{2}\left(\frac{1}{n} \sum\limits_{i=1}^{n}\left\|\tilde{\mathbf{x}}_{i}\right\|_{2}^{2}-\left\|\frac{1}{n} \sum\limits_{i=1}^{n} \tilde{\mathbf{x}}_{i}\right\|_{2}^{2}\right) \quad\quad\quad(8)$
$\text{Eq.8}$ 的第一項 表示節點表示的均方長度，第二項描述了節點表示的均值的平方長度。
為簡化 $\text{Eq.8}$ 的計算，令每個 $\tilde{\mathbf{x}}_{i}$ 減去行均值 $\tilde{\mathbf{x}}_{i}^{c}=\tilde{\mathbf{x}}_{i}-\frac{1}{n} \sum\limits _{i}^{n} \tilde{\mathbf{x}}_{i}$，其中 $\tilde{\mathbf{x}}_{i}^{c}$ 表示中心表示。這種移動不會影響 $\operatorname{TPSD}$，并且驅動了項 $\left\|\frac{1}{n} \sum\limits _{i=1}^{n} \tilde{\mathbf{x}}_{i}\right\|_{2}^{2} $ 趨近 $0$。那麼，計算 $\operatorname{TPSD}(\tilde{\mathbf{X}}) $ 可歸結為計算 $\tilde{\mathbf{X}}^{c}$ 的 $F$ 範數的平方，并有 $\mathcal{O}(n d)$：
$\operatorname{TPSD}(\tilde{\mathbf{X}})=\operatorname{TPSD}\left(\tilde{\mathbf{X}}^{c}\right)=2 n\left\|\tilde{\mathbf{X}}^{c}\right\|_{F}^{2} \quad\quad\quad(9)$
$\text{Eq.9}$ 可以寫成一個兩步的、中心和規模的歸一化過程：
$\tilde{\mathbf{x}}_{i}^{c}=\tilde{\mathbf{x}}_{i}-\frac{1}{n} \sum\limits _{i=1}^{n} \tilde{\mathbf{x}}_{i} \quad\quad\text{(Center)}\quad(10)$
$\dot{\mathbf{x}}_{i}=s \cdot \frac{\tilde{\mathbf{x}}_{i}^{c}}{\sqrt{\frac{1}{n} \sum\limits_{i=1}^{n}\left\|\tilde{\mathbf{x}}_{i}^{c}\right\|_{2}^{2}}}=s \sqrt{n} \cdot \frac{\tilde{\mathbf{x}}_{i}^{c}}{\sqrt{\left\|\tilde{\mathbf{X}}^{c}\right\|_{F}^{2}}} \quad\quad\text{(Scale)}\quad(11)$
縮放後，資料保持中心化 $\left\|\sum\limits _{i=1}^{n} \dot{\mathbf{x}}_{i}\right\|_{2}^{2}=0$ 。在 $\text{Eq.11}$ 中，$s$ 是一個超參數，它決定了 $C$。具體來說，
$\operatorname{TPSD}(\dot{\mathbf{X}})=2 n\|\dot{\mathbf{X}}\|_{F}^{2}=2 n \sum\limits_{i}\left\|s \cdot \frac{\tilde{\mathbf{x}}_{i}^{c}}{\sqrt{\frac{1}{n} \sum\limits_{i}\left\|\tilde{\mathbf{x}}_{i}^{c}\right\|_{2}^{2}}}\right\|_{2}^{2}=2 n \frac{s^{2}}{\frac{1}{n} \sum\limits_{i}\left\|\tilde{\mathbf{x}}_{i}^{c}\right\|_{2}^{2}} \sum\limits_{i}\left\|\tilde{\mathbf{x}}_{i}^{c}\right\|_{2}^{2}=2 n^{2} s^{2} \quad(12)$
然後，$\dot{\mathbf{X}}:=\operatorname{PAIRNORM}(\tilde{\mathbf{X}})$ 擁有行均值為 $0$ （Center），和恒定的總成對平方距離 $C=2 n^{2} s^{2}$。在 Figure 2 中給出了一對範數的說明。PAIRNORM 的輸出被輸入到下一個卷積層。
本文還推導出 PAIRNORM 的變體，即通過替換 $\text{Eq.11}$ 的 $\sum\limits _{i=1}^{n}\left\|\tilde{\mathbf{x}}_{i}^{c}\right\|_{2}^{2} $ 為 $n\left\|\tilde{\mathbf{x}}_{i}^{c}\right\|_{2}^{2}$ ，本文稱之為 PAIRNORM-SI ，此時所有的節點都有相同的 $L_{2}$ 範數 $s$ 。
在實踐中，發現 PAIRNORM 和 PAIRNORM-SI 對 SGC 都很有效，而 PAIRNORM-SI 對 GCN 和 GAT 提供了更好和更穩定的結果。GCN 和 GAT 需要更嚴格的歸一化的原因可能是因為它們有更多的參數，更容易發生過拟合。在所有實驗中，對SGC采用PAIRNORM，對 GCN 和 GAT 采用 PAIRNORM-SI。
Figure 1 中的實線顯示了 SGC 性能， 與 “vanilla” 版本相比，随着層數的增加，我們在每個圖卷積層之後使用 PAIRNORM。類似地，Figure 3 用于 GCN 和 GAT（在每個圖卷積激活後應用PAIRNORM-SI）。請注意，PAIRNORM 的性能衰減要慢得多。
雖然 PAIRNORM 使更深層次的模型對過度平滑更穩健，但總體測試精度沒有提高似乎很奇怪。事實上，文獻中經常使用的基準圖資料集需要不超過 $4$ 層，之後性能就會下降（即使是緩慢的）。
3.2 A case where deeper GNNs are beneficial
如果一個任務需要大量的層來實作其最佳性能，那麼它将更多的收益于使用 PAIRNORM，為此本文研究了 “missing feature setting”，即節點的一個子集存在特征缺失。
假設 $\mathcal{M} \subseteq \mathcal{V}_{u}$ 代表特征缺失子集，其中 $\forall m \in \mathcal{M}$，$\mathbf{x}_{m}=\emptyset $。本文設定 $p=|\mathcal{M}| /\left|\mathcal{V}_{u}\right|$ 代表缺失比例。将這種任務的變體稱為具有缺失向量的半監督節點分類(SSNC-MV)。直覺的說，需要更多的傳播步驟才能恢複這些節點有效的特征表示。
Figure 4 顯示了随着層數的增加，SGC、GCN 和 GAT 模型在 Cora 上的性能變化，其中我們從所有未标記的節點中删除特征向量，即 $p=1$。與沒有PAIRNORM 的模型相比，具有 PAIRNORM 的模型獲得了更高的測試精度，它們通常會達到更多的層數。
4 Experiments
在本節中，我們設計了廣泛的實驗來評估在SSNC-MV設定下的SGC、GCN和GAT模型的有效性。
4.1 Experiment setup
4.2 Experiment results
核心代碼：
if __name__ == "__main__":
mode = 'PN'
scale = 1
x =torch.randint(0,10,(3,2)).type(torch.float)
col_mean = x.mean(dim=0)
if mode == 'PN':
x = x - col_mean
print("x = ",x)
rownorm_mean = (1e-6 + x.pow(2).sum(dim=1).mean()).sqrt()
x = scale * x / rownorm_mean
if mode == 'PN-SI':
x = x - col_mean
rownorm_individual = (1e-6 + x.pow(2).sum(dim=1, keepdim=True)).sqrt()
x = scale * x / rownorm_individual
if mode == 'PN-SCS':
rownorm_individual = (1e-6 + x.pow(2).sum(dim=1, keepdim=True)).sqrt()
x = scale * x / rownorm_individual - col_mean 節點分類
代碼以 Deep_GCN 為例子：
class DeepGCN(nn.Module):
def __init__(self, nfeat, nhid, nclass, dropout, nlayer=2, residual=0,
norm_mode='None', norm_scale=1, **kwargs):
super(DeepGCN, self).__init__()
assert nlayer >= 1
self.hidden_layers = nn.ModuleList([
GraphConv(nfeat if i==0 else nhid, nhid) for i in range(nlayer-1)
])
self.out_layer = GraphConv(nfeat if nlayer==1 else nhid , nclass)
self.dropout = nn.Dropout(p=dropout)
self.dropout_rate = dropout
self.relu = nn.ReLU(True)
self.norm = PairNorm(norm_mode, norm_scale)
self.skip = residual
def forward(self, x, adj):
x_old = 0
for i, layer in enumerate(self.hidden_layers):
x = self.dropout(x)
x = layer(x, adj)
x = self.norm(x)
x = self.relu(x)
if self.skip>0 and i%self.skip==0:
x = x + x_old
x_old = x
x = self.dropout(x)
x = self.out_layer(x, adj)
return x 5 Conclusion
提出了一種有效防止過平滑問題的 成對範數 ，一種新的歸一化層，提高了深度 GNNs 對過平滑的魯棒性。
6 Reason of failure
即實驗對于 mask feature 隻處理了一次，并沒有在每個 epoch 中進行處理。
def load_data(data_name='Cora', normalize_feature=True, missing_rate=0, cuda=False):
# can use other dataset, some doesn't have mask
print(os.path.join(DATA_ROOT, data_name))
dataset = geo_data.Planetoid(DATA_ROOT, data_name)
print("dataset = ",dataset)
# print(dataset[0])
# print(dataset.data)
data = geo_data.Planetoid(DATA_ROOT, data_name).data
# original split
data.train_mask = data.train_mask.type(torch.bool)
data.val_mask = data.val_mask.type(torch.bool)
# data.test_mask = data.test_mask.type(torch.bool)
# expand test_mask to all rest nodes
data.test_mask = ~(data.train_mask + data.val_mask)
# get adjacency matrix
n = len(data.x)
adj = sp.csr_matrix((np.ones(data.edge_index.shape[1]), data.edge_index), shape=(n,n))
adj = adj + adj.T.multiply(adj.T > adj) - adj.multiply(adj.T > adj) + sp.eye(adj.shape[0])
adj = normalize_adj_row(adj) # symmetric normalization works bad, but why? Test more.
data.adj = to_torch_sparse(adj)
# normalize feature
if normalize_feature:
data.x = row_l1_normalize(data.x)
# generate missing feature setting
indices_dir = os.path.join(DATA_ROOT, data_name, 'indices')
if not os.path.isdir(indices_dir):
os.mkdir(indices_dir)
missing_indices_file = os.path.join(indices_dir, "indices_missing_rate={}.npy".format(missing_rate))
if not os.path.exists(missing_indices_file):
erasing_pool = torch.arange(n)[~data.train_mask] # keep training set always full feature
size = int(len(erasing_pool) * (missing_rate/100))
idx_erased = np.random.choice(erasing_pool, size=size, replace=False)
np.save(missing_indices_file, idx_erased)
else:
idx_erased = np.load(missing_indices_file)
# erasing feature for random missing
if missing_rate > 0:
data.x[idx_erased] = 0
if cuda:
data.x = data.x.cuda()
data.y = data.y.cuda()
data.adj = data.adj.cuda()
return data View Code
因上求緣，果上努力~~~~ 作者：關注我更新論文解讀，轉載請注明原文連結：https://www.cnblogs.com/BlairGrowing/p/16607263.html