|
事實上，在2019年的各大頂級學術會議上，與圖神經(jīng)網(wǎng)絡有關的論文也占據(jù)了相當可觀的份額。相信在未來幾年，這種流行的趨勢會只增不減。 本文就從“圖”說起，帶你了解圖神經(jīng)網(wǎng)絡的概念及應用。 作者：劉忠雨、李彥霖、周洋 來源：大數(shù)據(jù)DT（ID：hzdashuju） 01 圖的基本定義 圖（Graph）是一個具有廣泛含義的對象。在數(shù)學中，圖是圖論的主要研究對象；在計算機工程領域，圖是一種常見的數(shù)據(jù)結(jié)構(gòu)；在數(shù)據(jù)科學中，圖被用來廣泛描述各類關系型數(shù)據(jù)。許多圖學習的理論都專注于圖數(shù)據(jù)相關的任務上。 通常，圖被用來表示物體與物體之間的關系。這在生活中有著非常多的現(xiàn)實系統(tǒng)與之對應，比如化學分子、通信網(wǎng)絡、社交網(wǎng)絡等。事實上，任何一個包含二元關系的系統(tǒng)都可以用圖來描述。因此，研究并應用圖相關的理論，具有重大的現(xiàn)實意義。 本文，我們主要對圖相關的概念做一些基礎介紹，包括圖的基本定義、圖在計算機中的存儲表示方法與遍歷方法、圖數(shù)據(jù)及其常見的應用場景、圖數(shù)據(jù)深度學習的淺述。 在數(shù)學中，圖由頂點（Vertex）以及連接頂點的邊（Edge）構(gòu)成。頂點表示研究的對象，邊表示兩個對象之間特定的關系。 圖可以表示為頂點和邊的集合，記為G = (V, E)，其中V是頂點集合，E是邊集合。同時，我們設圖G的頂點數(shù)為N，邊數(shù)為M（如無特殊說明，本文中的圖均如此表示）。一條連接頂點vi, vj∈V的邊記為（vi, vj）或者eij。如圖1-1所示，V = {v1, v2, v3, v4, v5}，E = {(v1, v2), (v1, v3), (v2, v4), (v2, v3), (v3, v4), (v4, v5)}。 ▲圖1-1 圖G的定義 02 圖的基本類型 1. 有向圖和無向圖 如果圖中的邊存在方向性，則稱這樣的邊為有向邊eij = <vi, vj>，其中vi是這條有向邊的起點，vj是這條有向邊的終點，包含有向邊的圖稱為有向圖，如圖1-2所示。與有向圖相對應的是無向圖，無向圖中的邊都是無向邊，我們可以認為無向邊是對稱的，同時包含兩個方向：eij = <vi, vj> = <vj, vi> = eji。 ▲圖1-2 有向圖 2. 非加權圖與加權圖 如果圖里的每條邊都有一個實數(shù)與之對應，我們稱這樣的圖為加權圖，如圖1-3所示，該實數(shù)稱為對應邊上的權重。在實際場景中，權重可以代表兩地之間的路程或運輸成本。一般情況下，我們習慣把權重抽象成兩個頂點之間的連接強度。與之相反的是非加權圖，我們可以認為非加權圖各邊上的權重是一樣的。 ▲圖1-3 加權圖 3. 連通圖與非連通圖 如果圖中存在孤立的頂點，沒有任何邊與之相連，這樣的圖被稱為非連通圖，如圖1-4所示。相反，不存在孤立頂點的圖稱為連通圖。 ▲圖1-4 非連通圖 4. 二部圖 二部圖是一類特殊的圖。我們將G中的頂點集合V拆分成兩個子集A和B，如果對于圖中的任意一條邊eij均有vi∈A，vj∈B或者vi∈B，vj∈A，則稱圖G為二部圖，如圖1-5所示。二部圖是一種十分常見的圖數(shù)據(jù)對象，描述了兩類對象之間的交互關系，比如：用戶與商品、作者與論文。 ▲圖1-5 二部圖 03 圖數(shù)據(jù)的應用場景 我們提到圖，更多的是帶有一種數(shù)學上的理論色彩，在實際的數(shù)據(jù)場景中，我們通常將圖稱為網(wǎng)絡（Network），與之對應的，圖的兩個要素（頂點和邊）也被稱為節(jié)點（Node）和關系（Link），比如我們熟知的社交網(wǎng)絡、物流網(wǎng)絡等概念名詞。 為了達成統(tǒng)一并與神經(jīng)網(wǎng)絡（Neural Networks）中的“網(wǎng)絡”概念區(qū)分開來（盡管神經(jīng)網(wǎng)絡也是一種網(wǎng)絡）。 圖數(shù)據(jù)是一類比較復雜的數(shù)據(jù)類型，存在非常多的類別。這里我們介紹其中最重要的4類：同構(gòu)圖（Homogeneous Graph）、異構(gòu)圖（Heterogeneous Graph）、屬性圖（Property Graph）和非顯式圖（Graph Constructed from Non-relational Data）。
▲圖1-9 屬性圖 在我們研究多元化對象系統(tǒng)的時候，圖是一種非常重要的視角。在現(xiàn)實世界中，圖數(shù)據(jù)有著十分廣泛的應用場景。下面我們舉幾個例子進行說明，如圖1-10所示。 ▲圖1-10 圖數(shù)據(jù)應用示例[1, 19]
社交網(wǎng)絡是十分常見的一類圖數(shù)據(jù)，代表著各種個人或組織之間的社會關系。如圖1-10的a圖展示了在線社交網(wǎng)絡中的用戶關注網(wǎng)絡：以用戶為節(jié)點，用戶之間的關注關系作為邊。這是一個典型的同構(gòu)圖，一般用來研究用戶的重要性排名以及相關的用戶推薦等問題。 隨著移動互聯(lián)網(wǎng)技術的不斷深入，更多元化的媒體對象被補充進社交網(wǎng)絡中，比如短文本、視頻等，如此構(gòu)成的異構(gòu)圖可以完成更加多樣化的任務。
電子購物是互聯(lián)網(wǎng)中的一類核心業(yè)務，在這類場景中，業(yè)務數(shù)據(jù)通?？梢杂靡粋€用戶–商品的二部圖來描述，在如圖1-10的b圖所展示的例子中，節(jié)點分為兩類：用戶和商品，存在的關系有瀏覽、收藏、購買等。 用戶與商品之間可以存在多重關系，如既存在收藏關系也存在購買關系。這類復雜的數(shù)據(jù)場景可以用屬性圖輕松描述。電子購物催生了一項大家熟知的技術應用—推薦系統(tǒng)。用戶與商品之間的交互關系，反映了用戶的購物偏好。例如，經(jīng)典的啤酒與尿布的故事：愛買啤酒的人通常也更愛買尿布。
以原子為節(jié)點，原子之間的化學鍵作為邊，我們可以將分子視為一種圖數(shù)據(jù)進行研究，分子的基本構(gòu)成以及內(nèi)在聯(lián)系決定了分子的各項理化性質(zhì)，通常我們用其指導新材料、新藥物的研究任務，如圖1-10的c圖所示。
交通網(wǎng)絡具有多種形式，比如地鐵網(wǎng)絡中將各個站點作為節(jié)點，站點之間的連通性作為邊構(gòu)成一張圖，如圖1-10的d圖所示。通常在交通網(wǎng)絡中我們比較關注的是路徑規(guī)劃相關的問題：比如最短路徑問題，再如我們將車流量作為網(wǎng)絡中節(jié)點的屬性，去預測未來交通流量的變化情況。
場景圖是圖像語義的一種描述方式，它將圖像中的物體當作節(jié)點，物體之間的相互關系當作邊構(gòu)成一張圖。場景圖可以將關系復雜的圖像簡化成一個關系明確的語義圖。場景圖具有十分強大的應用場景，如圖像合成、圖像語義檢索、視覺推理等。 圖1-10的e圖所示為由場景圖合成相關語義圖像的示例，在該場景圖中，描述了5個對象：兩個男人、一個小孩、飛盤、庭院以及他們之間的關系，可以看到場景圖具有很強的語義表示能力。
我們可以將電子器件如諧振器作為節(jié)點，器件之間的布線作為邊將電路設計抽象成一種圖數(shù)據(jù)。在參考文獻[1]中，對電路設計進行了這樣的抽象，如圖1-10的f圖所示，然后基于圖神經(jīng)網(wǎng)絡技術對電路的電磁特性進行仿真擬合，相較于嚴格的電磁學公式仿真，可以在可接受的誤差范圍內(nèi)極大地加速高頻電路的設計工作。 圖數(shù)據(jù)的應用場景遠不止這些，還有諸如描述神經(jīng)網(wǎng)絡計算過程的計算圖、傳感器陣列網(wǎng)絡、由各類智能傳感器構(gòu)成的物聯(lián)網(wǎng)。事實上，如果要找一種最具代表性的數(shù)據(jù)描述語言與現(xiàn)實數(shù)據(jù)對應，那么圖應該是最具競爭力的候選者。總的來說，圖數(shù)據(jù)的應用跨度大、應用場景多，研究圖數(shù)據(jù)具有廣泛且重要的現(xiàn)實意義。 04 圖數(shù)據(jù)深度學習 作為一種重要的數(shù)據(jù)類型，圖數(shù)據(jù)的分析與學習的需求日益凸顯，許多圖學習（Graph Learning）的理論均專注于圖數(shù)據(jù)相關的任務學習。 譜圖理論（Spectral Graph Theory）[2]是將圖論與線性代數(shù)相結(jié)合的理論，基于此理論發(fā)展而來的譜聚類相關算法[3]，可以用來解決圖的分割或者節(jié)點的聚類問題。 統(tǒng)計關系學習（Statistical Relational Learning）[4]是將關系表示與似然表示相結(jié)合的機器學習理論，區(qū)別于傳統(tǒng)的機器學習算法對數(shù)據(jù)獨立同分布（independent and Identically Distributed，數(shù)據(jù)對象是同類且獨立不相關的）的假設，統(tǒng)計關系學習打破了對數(shù)據(jù)的上述兩種假設，對圖數(shù)據(jù)的學習具有更好的契合度。 為了更加貼合實際場景中的異構(gòu)圖數(shù)據(jù)，異構(gòu)信息網(wǎng)絡（Heterogeneous Information Network）[5]分析被提出，用以挖掘異構(gòu)圖中更加全面的結(jié)構(gòu)信息和豐富的語義信息。 由于這些年深度學習在實際應用領域取得的巨大成就，表示學習和端對端學習的概念日益得到重視，為了從復雜的圖數(shù)據(jù)中學習到包含充分信息的向量化表示，出現(xiàn)了大量網(wǎng)絡表示學習（Network Embedding）[6]的方法。然而網(wǎng)絡表示學習很難提供表示學習加任務學習的端對端系統(tǒng)，基于此，圖數(shù)據(jù)的端對端學習系統(tǒng)仍然是一個重要的研究課題。 由于圖數(shù)據(jù)本身結(jié)構(gòu)的復雜性，直接定義出一套支持可導的計算框架并不直觀。與圖數(shù)據(jù)相對應的數(shù)據(jù)有圖像、語音與文本，這些數(shù)據(jù)是定義在歐式空間中的規(guī)則化結(jié)構(gòu)數(shù)據(jù)，基于這些數(shù)據(jù)的張量計算體系是比較自然且高效的。 圖1-11給出了圖數(shù)據(jù)與其他幾類常見類型數(shù)據(jù)的對比。圖像數(shù)據(jù)呈現(xiàn)出規(guī)則的2D柵格結(jié)構(gòu)，這種柵格結(jié)構(gòu)與卷積神經(jīng)網(wǎng)絡的作用機制具有良好的對應。文本數(shù)據(jù)是一種規(guī)則的序列數(shù)據(jù)，這種序列結(jié)構(gòu)與循環(huán)神經(jīng)網(wǎng)絡的作用機制相對應。 ▲圖1-11 圖像和語音文本數(shù)據(jù)類型 受圖信號處理（Graph Signal Processing）[7]中對圖信號卷積濾波的定義的啟發(fā)，近幾年發(fā)展出了一套基于圖卷積操作并不斷衍生的神經(jīng)網(wǎng)絡理論。本文將這類方法統(tǒng)稱為圖神經(jīng)網(wǎng)絡（Graph Neural Network，GNN[8-10]）。下面我們簡述其發(fā)展歷程。 2005年，Marco Gori等人發(fā)表論文[11]，首次提出了圖神經(jīng)網(wǎng)絡的概念。在此之前，處理圖數(shù)據(jù)的方法是在數(shù)據(jù)的預處理階段將圖轉(zhuǎn)換為用一組向量表示。這種處理方法最大的問題就是圖中的結(jié)構(gòu)信息可能會丟失，并且得到的結(jié)果會嚴重依賴于對圖的預處理。GNN的提出，便是為了能夠?qū)W習過程直接架構(gòu)于圖數(shù)據(jù)之上。 隨后，其在2009年的兩篇論文[12, 13]中又進一步闡述了圖神經(jīng)網(wǎng)絡，并提出了一種監(jiān)督學習的方法來訓練GNN。但是，早期的這些研究都是以迭代的方式，通過循環(huán)神經(jīng)網(wǎng)絡傳播鄰居信息，直到達到穩(wěn)定的固定狀態(tài)來學習節(jié)點的表示。這種計算方式消耗非常大，相關研究開始關注如何改進這種方法以減小計算量。 2012年前后，卷積神經(jīng)網(wǎng)絡開始在視覺領域取得令人矚目的成績，于是人們開始考慮如何將卷積應用到圖神經(jīng)網(wǎng)絡中。2013年Bruna等人首次將卷積引入圖神經(jīng)網(wǎng)絡中，在引文[14]中基于頻域卷積操作的概念開發(fā)了一種圖卷積網(wǎng)絡模型，首次將可學習的卷積操作用于圖數(shù)據(jù)之上。 自此以后，不斷有人提出改進、拓展這種基于頻域圖卷積的神經(jīng)網(wǎng)絡模型。但是基于頻域卷積的方法在計算時需要同時處理整個圖，并且需要承擔矩陣分解時的很高的時間復雜度，這很難使學習系統(tǒng)擴展到大規(guī)模圖數(shù)據(jù)的學習任務上去，所以基于空域的圖卷積被提出并逐漸流行。 2016年，Kipf等人[15]將頻域圖卷積的定義進行簡化，使得圖卷積的操作能夠在空域進行，這極大地提升了圖卷積模型的計算效率，同時，得益于卷積濾波的高效性，圖卷積模型在多項圖數(shù)據(jù)相關的任務上取得了令人矚目的成績。 近幾年，更多的基于空域圖卷積的神經(jīng)網(wǎng)絡模型的變體[16-18]被開發(fā)出來，我們將這類方法統(tǒng)稱為GNN。各種GNN模型的出現(xiàn)，大大加強了學習系統(tǒng)對各類圖數(shù)據(jù)的適應性，這也為各種圖數(shù)據(jù)的任務學習奠定了堅實的基礎。 自此，圖數(shù)據(jù)與深度學習有了第一次真正意義上的結(jié)合。GNN的出現(xiàn)，實現(xiàn)了圖數(shù)據(jù)的端對端學習方式，為圖數(shù)據(jù)的諸多應用場景下的任務，提供了一個極具競爭力的學習方案。 在本文的最后，我們給出圖數(shù)據(jù)相關任務的一種分類作為結(jié)尾。 1. 節(jié)點層面（Node Level）的任務 節(jié)點層面的任務主要包括分類任務和回歸任務。這類任務雖然是對節(jié)點層面的性質(zhì)進行預測，但是顯然不應該將模型建立在一個個單獨的節(jié)點上，節(jié)點的關系也需要考慮。節(jié)點層面的任務有很多，包括學術上使用較多的對論文引用網(wǎng)絡中的論文節(jié)點進行分類，工業(yè)界在線社交網(wǎng)絡中用戶標簽的分類、惡意賬戶檢測等。 2. 邊層面（Link Level）的任務 邊層面的任務主要包括邊的分類和預測任務。邊的分類是指對邊的某種性質(zhì)進行預測；邊預測是指給定的兩個節(jié)點之間是否會構(gòu)成邊。常見的應用場景比如在社交網(wǎng)絡中，將用戶作為節(jié)點，用戶之間的關注關系建模為邊，通過邊預測實現(xiàn)社交用戶的推薦。目前，邊層面的任務主要集中在推薦業(yè)務中。 3. 圖層面（Graph Level）的任務 圖層面的任務不依賴于某個節(jié)點或者某條邊的屬性，而是從圖的整體結(jié)構(gòu)出發(fā)，實現(xiàn)分類、表示和生成等任務。目前，圖層面的任務主要應用在自然科學研究領域，比如對藥物分子的分類、酶的分類等。 參考文獻 [1] Zhang G, He H, Katabi D. Circuit-GNN: Graph Neural Networks for Distributed Circuit Design[C]//International Conference on Machine Learning. 2019: 7364-7373. [2] F. R. Chung. Spectral Graph Theory. American Mathematical Society, 1997. [3] Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4): 395-416. [4] Koller D, Friedman N, D~eroski S, et al. Introduction to statistical relational learning[M]. MIT press, 2007. [5] Shi C, Li Y, Zhang J, et al. A survey of heterogeneous information network analysis[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 29(1): 17-37. [6] Cui P, Wang X, Pei J, et al. A survey on network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(5): 833-852. [7] Shuman D I, Narang S K, Frossard P, et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE signal processing magazine, 2013, 30(3): 83-98. [8] Zhou J, Cui G, Zhang Z, et al. Graph neural networks: A review of methods and applications[J]. arXiv preprint arXiv:1812.08434, 2018. [9] Zhang Z, Cui P, Zhu W. Deep learning on graphs: A survey[J]. arXiv preprint arXiv:1812.04202, 2018. [10] Wu Z, Pan S, Chen F, et al. A comprehensive survey on graph neural networks[J]. arXiv preprint arXiv:1901.00596, 2019. [11] Gori M, Monfardini G, Scarselli F. A new model for learning in graph domains[C]//Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005. IEEE, 2005, 2: 729-734. [12] Micheli A. Neural network for graphs: A contextual constructive approach[J]. IEEE Transactions on Neural Networks, 2009, 20(3): 498-511. [13] Scarselli F, Gori M, Tsoi A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80. [14] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013. [15] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016. [16] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs[C]//Advances in Neural Information Processing Systems. 2017: 1024-1034. [17] Velikovi P, Cucurull G, Casanova A, et al. Graph attention networks[J]. arXiv preprint arXiv:1710.10903, 2017. [18] Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry [C]//Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017: 1263-1272. [19] Johnson J, Gupta A, Fei-Fei L. Image generation from scene graphs[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018: 1219-1228. |
|
|
