Chapter 1 Introduction

1.1 What is a graph?

Graph：邊和點的集合。 graph

\mathcal{G} = \left( \mathcal{V}, \varepsilon \right)

，其中

\mathcal{V}

表示節點集，

\varepsilon

表示邊集。

Graph可以透過鄰接矩陣

A \in \mathbb{R}^{\left| \mathcal{V} \right| \times \left| \mathcal{V} \right|}

表示。

Simple graph

每兩個節點間至多有一條邊，節點沒有自環，所有的邊都是無向的，即

\left( u, v \right) \in \varepsilon \leftrightarrow \left( v, u \right) \in \varepsilon

。

Multi-relational Graphs

除了區分無向圖、有向圖以及加權圖之外，我們還考慮有不同types的邊的圖。例如用圖表示藥品之間的反應時，我們用不同的邊代表發生的不同的副作用。在這種情況下，給邊加一個relation屬性

\tau

， 即

(u, \tau, v) \in \varepsilon

。

我們為每種邊的型別都定義一種鄰接矩陣

A_{\tau}

，我們稱這種圖為“Multi-relational Graphs”。Adjacency tensor

\mathcal{A} \in \mathbb{R}^{\left| \mathcal{V} \right|\times\left| \mathcal{R} \right| \times \left| \mathcal{V} \right|}

，

\mathcal{R}

是relation集合。

Heterogeneous graphs

異構圖中節點也有多種types。例如一種節點型別代表蛋白質，另一種節點型別代表藥品，另一種節點型別代表疾病。代表“treatment”的邊只會出現在藥物節點和疾病節點之間。 同樣，代表“polypharmacy side-effects”的邊只會出現在兩個藥物節點之間。

Multiplex graphs

Multiplex graphs中，圖被分解為k個layers的集合。每個節點存在於每個layer中，每個layer對應一個唯一的關係，表示該層中edge的型別。我們同時假設每層之間的edge型別存在，它將不同層中的同一節點連線起來。

我們透過例子來理解multiplex graphs：在一個存在多種交通方式的交通網路中，每個節點代表一個城市，而每一層代表一種不同的交通方式（例如，飛機或火車）。層內的edge代表城市之間的交通方式，而每一層之間的edge則代表在特定城市內切換交通方式的可能性。

1.2 Machine learning on graphs

Node classification

假設有一個數百萬使用者的大型社交網路資料集，但是我們知道這些使用者中的絕大部分實際上是機器人。識別這些機器人很重要，因為我們不希望向機器人推送廣告。

與標準的有監督問題不同，圖中的節點不是

獨立同分布

的（independent and identically distributed （i。i。d。），獨立同分布是指一組隨機變數中每個變數的機率分佈都相同，且這些隨機變數互相獨立）。一般的有監督機器學習都假設各個datapoints之間都是獨立的，否則我們可能需要對所有輸入點之間的依賴關係進行建模。

所以，在圖節點分類任務中，與建模一系列獨立同分布的datapoints不同，我們改為

建模一組互連的節點，利用節點之間的聯絡進行節點分類

。

最流行的方法是利用節點間的

同質性（homophily）

，即圖中的節點會與它的鄰居節點具有相似的屬性，例如，人們傾向於與擁有相同興趣的其他人建立友誼。基於同質性的想法，我們可以建立機器學習模型，嘗試為圖中的相鄰節點分配相似的標籤。

除了homophily，還有

structural equivalence

的概念，即具有相似local neighborhood structures 的節點具有相似的labels。此外還有異質性（heterophily），假設節點將優先連線到具有不同標籤的節點。

當我們建立節點分類模型時，我們想利用這些概念並對節點之間的關係進行建模，而不是簡單地將節點視為獨立的資料點。

另外，由於圖節點分類任務的性質，我們拿到的資料常常是整個graph，其中包括沒有label的測試節點，而且我們可以利用這些測試節點的資訊幫助我們提高分類任務的準確度。這一點與標準的監督學習任務不同，所以該任務也可以視為半監督學習。不過，必須注意的是，半監督學習仍然需要datapoints滿足i。i。d。

Relation prediction

給出node集合，以及一個不完整的具有資訊的edge 集合

\varepsilon_{train} \in \varepsilon

，使用具有資訊的edge對missing edge進行推測。例如，預測藥物之間的反應。

Clustering and community detection

Node classification和Relation prediction都是推測圖資料的missing information，都屬於監督學習任務。而Community detection則屬於圖領域的無監督學習。

如果我們希望這個網路像許多現實世界的網路一樣表現出社群結構，其中節點更有可能與同屬一個社群的節點相連。社群檢測的挑戰在於，僅在輸入圖

\mathcal{G} = \left( \mathcal{V}, \varepsilon \right)

的情況下，推斷潛在的社群結構。社群檢測在現實世界中的許多應用包括髮現遺傳互動網路中的功能模組和發現金融交易網路中的欺詐性使用者組。

Graph classification, regression, and clustering

在Graph classification， regression， and clustering問題上，我們需要在整個graph資料上進行學習，而不是對單個圖的各個組成部分進行預測。我們獲得了包含多個不同圖的資料集，我們的目標是針對每個圖進行獨立的預測。在圖聚類的相關任務中，目標是無監督的學習圖與圖之間的相似性。

graph classification， graph regression任務中，每個graph都是帶label的獨立同分布的datapoint，我們的目標是使用訓練集學習從datapoints（即graph）到labels的對映。同樣，graph clustering也是對圖資料的無監督聚類的直接擴充套件。

在graph-level的任務上，挑戰在於如何定義有用的特徵，這些特徵考慮每個資料點內的關係結構

Chapter 2 Background and Traditional Approaches

本章回顧一些在機器學習與深度學習出現之前graph上使用的傳統方法。

2.1 Graph Statistics and Kernel Methods

2.1.1 Node-level statistics and features

Node degree

d_{u} = \sum_{v \in V}{A[u, v]} \tag{2.1} \\

Node centrality

節點的度僅說明了該節點的鄰居數量，對於衡量一個節點的重要度遙遠不夠。節點的centrality可以作為衡量節點重要性的指標，衡量節點centrality的一個重要方式是

eigenvector centrality

。

節點的度僅說明了該節點的鄰居數量，eigenvector centrality還考慮了節點鄰居的重要性。我們透過遞迴關係定義節點的eigenvector centrality

e_{u}

，其中節點的centrality與其鄰居的平均centrality成正比：

e_{u} = \frac{1}{\lambda} \sum_{v \in V}{ A[u, v] e_{v}} \quad \forall u \in \mathcal{V} \tag{2.2} \\

\lambda

是一個常數。我們可以用向量形式表述這個等式，

e

是node centralities的向量符號，我們可以看到這個遞迴式定義了鄰接矩陣的標準特徵向量方程：

\lambda e = Ae \tag{2.3} \\

換句話說，滿足方程式2。2中的遞迴式的centrality度量對應於鄰接矩陣的特徵向量。假設我們需要正中心值，我們可以應用Perron-Frobenius定理進一步確定centrality值

e

的向量是由對應於

A

的最大特徵值的特徵向量給出的。

Eigenvector centrality的一種觀點是，它在graph中無限長的random walk上對訪問節點的可能性進行排名。這種觀點可以透過使用冪迭代獲得eigenvector centrality來說明。也就是說，由於

\lambda

是

A

的前導特徵向量（the leading eigenvector），我們可以使用冪迭代（power iteration）來計算

e

：

e^{(t+1)} = A e^{(t)} \tag{2.4} \\

以Florentine marriage network為例，計算圖上的eigenvector centrality， Medici family 影響力最大， normalized value 是0。43，相比之下第二大的值是0。36。

Graph Representation Learning:簡介及傳統方法

當然，我們還可以使用其他centrality度量來表徵該圖中的節點，其中一些相對於Medici 家族的影響力更為明顯。比如用betweeness centrality（它衡量一個節點位於兩個其他節點之間的最短路徑上的頻率）以及closeness centrality（它衡量一個節點與所有其他節點之間的平均最短路徑長度）。

The clustering coefficient

圖2。1中的Peruzzi和Guadagni節點具有非常相似的度數（3 vs。 4）和相似的eigenvector centralities （0。28 vs。 0。29）。但是，從圖中的圖表來看，這兩個家族之間顯然存在差異。Peruzzi家族處於相對緊密的家族叢集之中，而Guadagni家族則更像一個星型網路。

我們可以使用clustering coefficient 的變體來衡量這種structural distinction，該聚類係數可以測量結點local neighborhood中閉合三角形的比例。The popular local variant of the clustering coefficient is computed as follows：

c_{u} = \frac{ \left| \left( v_{1}, v_{2} \right) \in \varepsilon : v_{1}, v_{2} \in \mathcal{N \left( u \right)} \right| }{d_{u} 2} \tag{2.5} \\

式2。5中的分子計算節點

u

的鄰居之間的邊的數量，我們使用

\mathcal{N} \left( u \right) = \left\{ v \in \mathcal{V} : \left( u,v \right) \in \varepsilon \right\}

表示節點

u

的鄰居節點的集合。分母計算出節點u的鄰域中有多少對節點。

Clustering coefficient之所以得名，是因為它可以衡量節點鄰域的cluster緊密程度。Clustering coefficient為1表示

u

的所有鄰居也是彼此的鄰居。在佛羅倫薩婚姻圖中，我們可以看到一些節點是高度聚集的。例如，Peruzzi節點的聚集係數為0。66 ，而其他節點（例如Guadagni節點）的聚集係數為0。（用閉合三角形的比例算clustering coefficient最簡單）

Graph的clustering coefficient是其每個節點的clustering coefficient的平均數。節點的clustering coefficient表現了這個節點的臨近節點的集中情況，圖的clustering coefficient表明圖的集中水平。

Closed triangles, ego graphs, and motifs

除了作為local clustering的度量，看待clustering coefficient的另一種觀點是，它計算每個節點的local neighborhood內的閉合三角形（closed triangles）的數量。用更精確的術語來說，clustering coefficient與節點的ego graph（即包含該節點及其鄰居，以及節點和鄰居節點之間的所有邊的子圖）中的實際三角形數量與所有可能的三角形數量之間的比率相關。

這個想法可以推廣到對一個節點的ego graph中的任意的motifs 或 graphlets進行計數的概念。也就是說，我們不僅可以考慮三角形，還可以考慮更復雜的結構，例如特定長度的環，並且可以透過計數這些不同motifs在其ego graph中出現的頻率來表徵節點。實際上，透過這種方式檢查節點的ego graph，我們可以將計算node-level上的統計資訊和特徵的任務轉變為graph-level上的任務。

2.1.2 Graph-level features and graph kernels

Bag of nodes

最簡單的graph-level特徵就是單純將node-level的statistics聚合。但是，完全基於local node-level資訊會丟失許多graph的global特徵。

The Weisfeiler-Lehman kernel

Bag of nodes的一種改進是iterative neighborhood aggregation，意思是抽取包括更多資訊而不只是local ego graph的node-level的特徵，然後將這些更加豐富的特徵聚合到graph-level的表示裡面。

這種策略的典型演算法就是Weisfeiler-Lehman （WL） algorithm and kernel，WL演算法基本思想如下：

Graph Representation Learning:簡介及傳統方法

WL kernel具有重要的理論特性。例如，一種常用的近似圖同構的方法是檢查經過WL演算法的K個輪次後，兩個圖是否具有相同的標籤集，並且該方法可以解決broad set of graphs的同構問題。

Graphlets and path-based methods

Graphlets：記錄所有子圖結構在整個圖中出現了多少次。graphlet kernel列舉特定大小的所有可能的圖形結構，並計算它們在整個圖形中出現的次數。Figure 2。2 illustrates the various graphlets of size 3。

Graph Representation Learning:簡介及傳統方法

這種方法所面臨的挑戰是，儘管已經提出了許多近似方法，但對這些graphlets進行計數是一個combinatorially difficult的問題

與找出所有可能的子圖結構不同，另一個簡單的方式是找出graph中出現的各種型別的path（1。random walk，記下不同degree sequences的出現；或2。使用兩個節點間的最短路徑）。用這種方式可避免很多combinatorial pitfalls。

2.2 Neighborhood Overlap Detection

上文提到的提取單個節點或整個圖的特徵及統計資料的方法是有侷限性的，這種侷限性體現在它們無法量化節點之間的關係。例如，上一節討論的統計資料對於relation prediction任務不是很有用，因為我們的目標是預測兩個節點之間是否存在邊（如圖2。3）。

我們要考慮節點對之間的鄰域重疊情況，用來量化一對節點的相關程度。例如，最簡單的鄰域重疊度量僅計算兩個節點共享的鄰居數：

S\left[ u, v \right] = \left| \mathcal{N(u)} \cap \mathcal{N(v)} \right| \tag{2.7} \\

S\left[ u, v \right]

表示量化節點

u

和

v

之間關係的值，

S \in \mathbb{R}^{\left| \mathcal{V} \right| \times \left| \mathcal{V} \right|}

表示summarizing所有成對節點統計資訊的similarity matrix。

給定鄰域重疊統計量

S\left[ u, v \right]

，一種常用的策略是假設

edge\left( u, v \right)

的可能性

僅與

S\left[ u, v \right]

成正比：

P\left( A\left[ u, v \right] = 1 \right) \propto S\left[ u, v \right] \tag{2.8} \\

Graph Representation Learning:簡介及傳統方法

2.2.1 Local overlap measures

Local overlap statistics表示兩個node共同的鄰居數量，即

\left| \mathcal{N(u)} \cap \mathcal{N(v)} \right|

。常用的方法有：

S_{Sorenson}\left[ u, v \right] = \frac{ 2 \left| \mathcal{N(u)} \cap \mathcal{N(v)} \right| }{d_{u} + d_{v}} \tag{2.9} \\

S_{Salton}\left[ u, v \right] = \frac{ 2 \left| \mathcal{N(u)} \cap \mathcal{N(v)} \right| }{\sqrt{ d_{u} + d_{v} }} \tag{2.10} \\

S_{Jaccard}\left[ u, v \right] = \frac{ \left| \mathcal{N(u)} \cap \mathcal{N(v)} \right| }{ \left| \mathcal{N(u)} \cup \mathcal{N(v)} \right| } \tag{2.11} \\

通常，這些措施試圖量化節點鄰域之間的重疊，同時最小化由於節點度引起的bias。

除了簡單地計算共同鄰居的數量外，還有一些措施試圖以某種方式考慮共同鄰居的importance。The Resource Allocation（RA）index計算公共鄰居的inverse degrees：

S_{RA}\left[ v_1, v_2 \right] = \sum_{ u \in \mathcal{N(u)} \cap \mathcal{N(v)} }{\frac{1}{d_u}} \tag{2.12} \\

The Adamic-Adar （AA） index performs a similar computation using the inverse logarithm of the degrees：

S_{AA}\left[ v_1, v_2 \right] = \sum_{ u \in \mathcal{N(u)} \cap \mathcal{N(v)} }{\frac{1}{\log{(d_u)}}} \tag{2.13} \\

這兩種措施都賦予low-degree的common neighbors更大的權重，直覺是shared low-degree neighbor比共享的shared high-degree鄰居提供更多資訊。

2.2.2 Global overlap measures

The local approaches are limited in that they only consider local node neighborhoods。 例如，兩個節點在其鄰域中可能沒有local overlap，但仍是graph中同一community的成員。Global overlap statistics試圖將這種關係考慮進去。

Katz index

S_{Katz}\left[ u, v \right] = \sum_{i=1}^{\infty} \beta^i A^i\left[ u, v \right] \tag{2.14} \\

\beta

是一個使用者定義的正實數，控制短路徑和長路徑的權重，

\beta＜1

會降低長路徑的重要性。

Katz index是一系列幾何矩陣的一個例子，其變體經常出現在圖分析和圖表示學習中。定理1給出了矩陣的基本幾何級數的解。

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

（矩陣的0次冪是單位矩陣

I

）

Graph Representation Learning:簡介及傳統方法

Leicht, Holme, and Newman (LHN) similarity

Katz index is strongly biased by node degree。與low degree節點相比，等式（2。14）通常會在考慮high degree節點時給出更高的整體相似性評分（overall similarity scores），因為high degree節點通常會涉及更多路徑。為了解決這個問題，Leicht等人透過考慮實際觀察到的路徑數與兩個節點之間的預期路徑數之比，提出一種改進的度量標準：

\frac{A^i}{\mathbb{E}[A^i]} \tag{2.16} \\

也就是說，根據我們對隨機模型下期望的路徑數的期望，對兩個節點之間的路徑數進行歸一化。

為了計算期望

\mathbb{E}[A^i]

，我們依賴於所謂的configuration model，

該模型假設我們繪製了一個隨機圖，其度數與給定圖的度數相同。在此假設下，我們可以分析計算

\mathbb{E}[A^2[v_1, v_2]] = \frac{d_{u} d_{v}} {2m} \tag{2.17} \\

我們使用

m = \left| \varepsilon \right|

來表示圖中的邊總數。等式（2。17）指出，在random conguration model下，一條edge的likelihood僅與兩個節點度的乘積成正比。可以看到，有

d_u

條邊離開

u

，並且這些邊中的每一條都有

d_v / 2m

的機會以

v

結尾。對於

\mathbb{E}[A^2[v_1, v_2]]

我們可以類似地計算

\mathbb{E}[A^2[v_1, v_2]] = \frac{d_{v1}d_{v2}}{(2m)^2} \sum_{u \in \mathcal{V}}{(d_u -1) d_u} \tag{2.18} \\

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Random walk methods

考慮隨機路徑而不是graph上path的精確計數。

隨機遊走是一種從圖中提取序列的技術，對圖中的每個節點，隨機轉到任何連線的節點。我們可以使用這些序列來訓練一個skip-gram模型來學習節點嵌入。隨機遊走會在圖中生成一條特定長度的隨機遊走路徑。

2.3 Graph Laplacians and Spectral Methods

2.3.1 Graph Laplacians

鄰接矩陣雖然可以儲存graph的全部資訊，但graph還可以用一種包含許多有用的數學性質的矩陣表示，這就是Laplacians，它由鄰接矩陣變形而來。

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

2.3.2 Graph Cuts and Clustering

定理2指出，拉普拉斯矩陣L的0特徵值的幾何重數（geometric multiplicity，代數重數與幾何重數是相對於矩陣的某一個特徵值而言的， 特徵值作為特徵多項式的根的重數稱為它的代數重數， 特徵值對應的特徵空間的維數稱為其幾何重數。 一個特徵值的代數重數與幾何重數不一定相等。 當矩陣可對角化時一定相等）對應graph中聯通部分（connected components）的數目。我們看到與Laplacian的0特徵值相對應的特徵向量可用於根據節點所屬的連線成分將節點分配給cluster。但是，這種方法僅允許我們對已經處於disconnected components中的節點進行cluster，這是無意義的。

我們將介紹Laplacian可用於在完全連通圖內給出節點的最佳clustering。

我們需要先了解

graph cuts

以及

optimal cluster

的概念。

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Approximating the RatioCut with the Laplacian spectrum

下面介紹如何使用Laplacian最小化RatioCut。

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

Graph Representation Learning:簡介及傳統方法

譜聚類參考文章

2.3.3 Generalized spectral clustering

我們已經知道the second-smallest eigenvector可以被用來將node劃分到不同的cluster裡面去。透過檢查拉普拉斯運算元的K個最小特徵向量，可以將這個general idea擴充套件到任意數量的K個cluster。此一般方法的步驟如下：

Graph Representation Learning:簡介及傳統方法

與上一節中對K = 2情況的討論一樣，可以將該方法改為使用歸一化的Laplacian，並且對於K = 2的近似結果也可以推廣到K> 2的情況

Spectral clustering的general principle是十分powerful的。我們可以使用圖拉普拉斯運算元的頻譜來表示圖中的節點，並且可以將這種表示（representation）作為對最佳圖聚類的原則上的近似。頻譜聚類和圖上的隨機遊走以及圖訊號處理的領域之間還有緊密的理論聯絡。

2.4 Towards Learned Representations

上面介紹的方法都是人工設計要提取的特徵或要採取的measures，這並不靈活，無法適配整個學習過程，而且手工設計特徵是一個費時費力的事情。

Graph representation learning，除了提取手工設計的特徵外，我們還將嘗試學習編碼表示圖形結構資訊的表示形式。