原文連結：Graph Structure of Neural Networks（ICML 2020）

神經網路經常表示為神經元之間的連線圖。然而，儘管它們被廣泛使用，透過之前的研究發現，神經網路的效能在很大程度上取決於它的結構，但對神經網路的準確性和其底層圖結構之間的關係幾乎沒有系統的理解。本文系統地研究了神經網路的圖結構如何影響其預測效能。

建立神經網路結構及其準確性之間的關係並不容易，因為不清楚如何將神經網路對映到圖（反之亦然）。自然的選擇是使用

計算圖(Computation Graph)

表示，即將神經元表示成節點，有向邊連線不同層中的神經元。這種圖表示展示了網路如何透過隱藏層將資訊從其輸入神經元傳遞和轉換到輸出神經元。但它有許多限制：

缺乏一般性：

計算圖受到允許的圖屬性的約束，例如，這些圖必須是有向和無環的（DAGs），在層級別是二分的，在網路級別是單入單出的；

與生物學/神經科學脫節：

大腦網路中有資訊交流，而不僅僅是單向流動。這種生物學或神經學模型不能簡單地用有向無環圖來表示。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖1 全連線層的計算圖表示

於是，文章提出了一種將神經網路表示為圖的新方法：

關係圖(Relational Graph)。

例。 對於一個固定寬度的全連線層（圖2（a）），將一個輸入通道和一個輸出通道一起表示為一個節點。一條邊表示兩個節點之間有訊息交換。一個神經網路層對應一個關係圖上的一輪訊息交換。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖2 （a）5層MLP其中一層對應的關係圖 （b）神經網路和關係圖對應的其他例子

關係圖中的訊息交換由訊息函式和聚合函式定義：

訊息函式(message function)：

輸入為節點的特徵，輸出為訊息，記為

f(\cdot)

；

聚合函式(aggregation function)：

輸入為一組訊息，輸出為更新的節點特徵，記為

AGG(\cdot)

。

在每一輪訊息交換中，每個節點向其鄰居傳送訊息，並聚集來自其鄰居的傳入訊息。 每個訊息在每個邊緣透過訊息函式

f(\cdot)

進行轉換，然後在每個節點透過聚合函式

AGG(\cdot)

進行聚合。 假設我們進行第

R

輪訊息交換，那麼節點

v

的第

r

輪訊息交換可以表示為：

\boldsymbol x_v^{(r+1)}=AGG(\{f(_v^{(r)}(\boldsymbol x_u^{(r)}),\forall u\in N(v)\})

其中

N(v)=\{u|v\vee(u,v)\in E\}

，

\boldsymbol x_v^{(r)}

是節點

v

的輸入特徵，

\boldsymbol x_v^{(r+1)}

是節點

v

的輸出特徵（這個訊息交換可以在任何圖

G

上定義，為簡單起見，本文只考慮無向圖）。

例。

例項化4層65維MLP。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖3 將4節點關係圖轉換為4層65維MLP的示例

這個公式給出了訊息交換的一般定義，我們可以將這個通用的訊息交換定義例項化為不同的神經網路架構。

固定寬度的多層感知機(Fixed-width MLPs)

多層感知器（MLP）由多層計算單元（神經元）組成，其中每個神經元對標量輸入執行加權求和，接著做一個非線性變換得到輸出。假設MLP的第

r

層以

\boldsymbol x^{(r)}

為輸入，

\boldsymbol x^{(r+1)}

為輸出，那麼神經元計算：

x_i^{(r+1)}=\sigma(\sum_jw_{ij}^{(r)}x_j^{(r)})

其中

w_{ij}^{(r)}

是可訓練的權重引數，

x_j^{(r)}

是輸入特徵

\boldsymbol x^{(r)}

的第

j

維，即

\boldsymbol x^{(r)}=(x_1^{(r)},...,x_n^{(r)})

，

x_i^{(r+1)}

是輸出特徵

\boldsymbol x^{(r+1)}

的第

i

維，

\sigma

為非線性變換。

固定寬度的多層感知機即考慮所有層都具有相同的輸入輸出維度，在這種情況下，完全連線的固定寬度MLP層可以用完全關係圖（complete relational graph）來表示，其中每個節點都與其他所有節點相連（包括自身），即對每個

v

，

N(v)=V

。它的訊息交換定義為：

f_i(x_j)=w_{ij}x_j

AGG(\{x_i\})=\sigma(\sum\{x_i\})

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖4 固定寬度MLP層可以用完全關係圖表示

基於訊息交換的一般定義式，固定寬度的多層感知機的訊息交換定義為：

x_i^{(r+1)}=\sigma(\sum_{j\in N(i)}w_{ij}^{(r)}x_j^{(r)})

可變寬度的多層感知機(Variable-width MLPs)

大多數情況下，神經網路層的寬度是變化的。為了表示一個可變寬度的多層感知機，我們將節點特徵從標量

x_i^{(r)}

推廣到向量

\boldsymbol x_i^{(r)}

，這個向量是由輸入

\boldsymbol x^{(r)}

中的某些維度組成的。假設輸入和輸出維度分別為

m1

和

m2

維，將輸入輸出統一為

n

維（

n\leq m1,n\leq m2

）則有：

\boldsymbol x^{(r)}=(x_1^{(r)},...x_{m1}^{(r)})=CONCAT(\boldsymbol x_1^{(r)},...,\boldsymbol x_n^{(r)})

\boldsymbol x^{(r+1)}=(x_1^{(r+1)},...x_{m2}^{(r+1)})=CONCAT(\boldsymbol x_1^{(r+1)},...,\boldsymbol x_n^{(r+1)})

這裡允許不同層中的相同節點

\boldsymbol x_i^{(r)}

和

\boldsymbol x_i^{(r+1)}

可以具有不同的維度，在同一層內，不同的節點

\boldsymbol x_i^{(r)}

和

\boldsymbol x_j^{(r)}

可以具有不同的維數。

同時，將訊息函式的標量乘法推廣到矩陣乘法，就能夠得到可變寬度的多層感知機訊息交換的定義為：

\boldsymbol x_i^{(r+1)}=\sigma(\sum_{j\in N(i)}\boldsymbol W_{ij}^{(r)}\boldsymbol x_j^{(r)})

這種廣義的定義使得神經網路能夠靈活的用圖表示，因為我們可以對任意寬度的不同層重用相同的關係圖。

卷積神經網路(CNNs)

為了使關係圖適用於輸入為張量

\boldsymbol X^{(r)}

的卷積神經網路，我們將節點特徵的定義從向量

\boldsymbol x_i^{(r)}

推廣到張量

\boldsymbol X_i^{(r)}

，每個張量由輸入的某些通道組成，即

\boldsymbol X^{(r)}=CONCAT(\boldsymbol X_1^{(r)},...,\boldsymbol X_n^{(r)})

。並將矩陣乘法推廣到卷積運算，得到卷積神經網路的訊息交換的定義為：

\boldsymbol X_i^{(r+1)}=\sigma(\sum_{j\in N(i)}\boldsymbol W_{ij}^{(r)}*\boldsymbol X_j^{(r)})

其中

*

為卷積運算。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖5 用關係圖表示不同的神經網路結構

為了設計和探索關係圖空間以研究神經網路圖結構與其預測效能之間的關係，給出了表示圖結構屬性的圖度量（graph measures）、可以生成不同圖的圖生成器（graph generators）以及一種控制計算預算（computational budget）的方法。

圖度量(graph measures)

由於圖結構的複雜性，圖度量經常被用來描述圖的特徵。

全域性圖度量：

平均路徑長度(average path length)

，即任意一對節點之間的最短路徑距離的平均值。

區域性圖度量：

聚類係數(clustering coefficient)

，即對於節點

v

，找出其直接鄰居節點集合

N(v)

，計算

N(v)

構成的網路中的邊數除以

N(v)

集合中可能邊數的比例，在所有節點上取均值。

圖生成器(graph generators)

給定選定的圖度量，我們的目標是使用圖生成器生成能夠覆蓋大範圍圖度量的不同圖。

WS-flex圖生成器：

WS-flex生成器由節點數

n

，平均度

k

和邊重連機率

p

引數化。容易知道邊數為

e=\lfloor n*k/2\rfloor

。

WS-flex生成器首先建立一個環形圖，其中每個節點連線到

\lfloor e/n\rfloor

個相鄰節點；然後，生成器隨機挑選

e

mod

n

個節點，並將每個節點分別連線到一個最近的相鄰節點；最後，所有的邊以機率

p

隨機重新連線。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖6 不同圖生成器生成的圖

從圖6中能夠看出，由那些經典圖生成器生成的圖在平均路徑長度（L）和聚類係數（C）的空間中具有有限的跨度。 本文提出的圖生成器WS-flex可以覆蓋更大的圖空間，而且WS-flex圖生成器生成的圖幾乎包含了經典隨機圖生成器生成的所有圖。

在WS-flex圖生成器生成的所有圖中取樣3942個關係圖用於後續的實驗，如圖7所示。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖7 根據圖度量來探索關係圖的設計空間

控制計算預算(computational budget)

為了比較由不同的關係圖轉化得到的神經網路的效能，要確保所有網路具有近似相同的複雜性，使得效能的差異只歸因於它們的關係圖結構的不同。使用FLOPS作為複雜性的度量。以完全關係圖（基線網路）的FLOPS作為參考複雜度。由於透過將維度或通道劃分為不相交的節點特徵集，關係圖結構可以被例項化為具有可變寬度的神經網路。因此，我們可以方便地調整神經網路的寬度，以匹配參考複雜度（基線FLOPS的0。5%以內），而不改變關係圖結構。

實驗部分

實驗設定

CIFAR-10：

50K張訓練影象，10K張驗證影象，10類

基線架構：具有512個隱藏單元的5層MLP

ImageNet：

1。28M張訓練影象，50K張驗證影象，1K類

基線架構：3種ResNet系列架構：ResNet-34，ResNet-34-sep，ResNet-50；EfficientNet-B0架構；CNN：8層3x3卷積，stride=2，三個階段的隱藏單元數量為［64， 128， 256］。

實驗結果

√ 存在可以優於完全關係圖（基線）的圖結構。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖8 最佳關係圖（紅色十字）在不同的設定下始終優於基線完整圖，“最佳點”（紅色矩形區域）中的關係圖在統計上並不比最佳關係圖（帶有紅色十字的箱子）差

存在可以優於完全關係圖效能的關係圖，而且表現最好的圖往往聚集在最佳點，可以按照以下步驟確定最佳點（sweet spot）：

（1）對WS-flex圖生成器生成的圖進行取樣，得到3942個圖（圖8左），將其聚合為52個箱子（bin）。每個箱子記錄落入這個箱子中的關係圖對應神經網路的平均效能（圖8右）；

（2） 確定具有最佳平均效能的箱子（圖8中帶有紅色十字的箱子）；

（3） 針對表現最佳的箱子對每一個箱子進行單尾t檢驗，記錄沒有明顯差於表現最佳的箱子的箱子（閾值p=0。05）。將覆蓋這些箱子的面積最小的矩形視為最佳點（圖8中紅色矩形區域）。

√ 神經網路的效能近似是其關係圖的聚類係數和平均路徑長度的光滑函式。

將其中一個圖度量固定在一個小範圍內（

C\in [0.4,0.6]

或

L\in [2,2.5]

），然後根據另一個圖度量視覺化神經網路效能。發現神經網路效能和圖度量之間存在平滑的U形相關性。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖9 神經網路效能和圖度量之間存在平滑的U形相關性

√

本文的發現在許多架構和任務中是一致的。

定性一致性（Qualitative consistency）： 不同架構之間的最佳點大致一致； 圖度量和相應的神經網路效能之間的U形趨勢在視覺上也是一致的。

定量一致性（Quantitative consistency）：每個箱值表示圖度量屬於箱子範圍的關係圖的平均效能，圖12繪製了不同任務不同架構之間52個箱值之間的相關性，發現具有特定圖度量的關係圖對應的神經網路的效能在不同的任務和體系結構中相互關聯。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖10 所有實驗的彙總

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖11 圖度量和相應的神經網路效能之間的U形趨勢在視覺上也是一致的

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖12 具有特定圖度量的關係圖對應的神經網路的效能在不同的任務和體系結構中相互關聯

√

只需要幾個關係圖樣本和幾個訓練階段就可以有效地識別最佳點。

訓練數以千計的關係圖，直到收斂，這在計算上可能是禁止的。 因此，我們定量地表明，可以用更少的計算成本來識別最佳點，例如，透過取樣使用更少的圖進行訓練或訓練更少的epochs。

僅使用52個圖計算的箱值與使用全部3942個圖計算的箱值具有0。90的高皮爾遜相關性。這一發現表明，在實踐中進行類似分析所需的圖要少得多。

訓練了3個epoch的模型與完整訓練100個epoch的模型效能已經具有高相關性（0。93），這意味著即使在訓練早期，好的關係圖也表現良好。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖13 快速確定最佳位置。左：使用較少的關係圖樣本和使用所有3942個圖來識別最佳點之間的相關性，右：訓練較少的epoch和完整訓練100個epoch確定的最佳點之間的相關性

√ 表現良好的神經網路具有與真實生物神經網路驚人相似的圖結構。

人工神經網路的圖度量（L和C）與生物神經網路高度相似；

利用關係圖表示，我們可以將生物神經網路轉化為5層MLP，並發現這些網路的效能也優於基線完全圖。

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

神經網路圖結構如何影響其預測效能？Graph Structure of Neural Networks(ICML 2020)

圖14 生物（左）和人工（右）神經網路圖形結構的視覺化。