作者：鄧楊
本文約6300字，建議閱讀10分鐘本文根據提出GAT文章Velickovic et al.(2017)中論述的順序，簡單介紹一下GAT的工作原理。 數無形時少直覺，形少數時難入微–華羅庚
1 圖注意力神經網絡的介紹
1.1GAT的原理與特性
圖形，由點、線、面和體構成，代表了一種了解抽象概念和表達抽象思想的有效工具。圖形語言的優勢在于其跨越語言障礙的能力，這種能力和技術大多是人類為了了解世界而發展出來的。計算機科學和人工智能的快速進步，使得了解和學習事物之間的更深層次客觀關系變得可能。圖神經網絡(GNN)的誕生，更加幫助人類通過圖形來了解和解決問題。圖注意力神經網絡(GAT)是一種專為處理圖結構資料而設計的特殊神經網絡。不同于傳統神經網絡，GAT在處理輸入資料時，會充分考慮資料間的關系，使其在處理圖結構資料時能更準确地捕捉到資料間的關聯性。GAT的主要優勢在于其自動學習節點間關系的能力，無需人工預設。
GAT的核心工作原理是通過注意力機制來計算節點間的關系。在傳統神經網絡中，每個節點的狀态更新是獨立進行的。而在GAT中，每個節點的狀态更新會考慮到其鄰居節點的狀态，GAT會計算一個節點與其鄰居節點之間的注意力權重，然後根據這個權重來更新節點的狀态。通過計算權重而更新 資訊的方式使得GAT能更好地捕捉到圖中的結構資訊。在計算權重分值和捕捉資訊的方面，GAT采用了類似于Transformer的掩蔽自注意力機制，由堆疊在一起的圖注意力層構成，每個圖注意力層擷取節點嵌入作為輸入，輸出轉換後的嵌入，節點嵌入會關注到它所連接配接的其他節點的嵌入(Velickovic et al.,2017)。在GAT的實際運算中，注意力分數的計算是通過一個名為“注意力頭”的結構完成的。每個注意力頭都會計算一組注意力分數，并且在最後的結果中，所有的注意力頭的結果會被平均或者拼接起來，以得到最終的節點嵌入。這樣做的好處是，每個注意力頭可以關注到不同的特征或者模式，進而使得GAT能夠捕捉到更多的資訊。具體的數學内容将在下面的文章中解釋。
此外，GAT引入了圖池化的概念，這是一種選擇最具資訊的節點子集的方法，可以生成更具區分性的圖。在圖池化過程中，GAT使用一個可學習的投影向量來計算每個節點的投影分數，然後根據投 影分數來選擇保留的節點。這種方式可以進一步提高GAT的性能。GAT還有一個重要特性是模型級别的融合。在處理複雜的問題時，GAT可以通過模型級别的融合來利用不同的資訊源。這種能力已經使 得GAT在許多領域顯示出其優越性，包括圖像識别、自然語言處理和推薦系統等。在圖像識别中，GAT 可以有效地處理圖像中的像素之間的關系，進而提高圖像識别的準确性。在自然語言進行中，GAT可以有效地處理文本中的詞語之間的關系，進而提高文本了解的準确性。在推薦系統中，GAT可以有效地處理使用者和商品之間的關系，進而提高推薦的準确性。
1.2GAT在生活中的例子
為了更加直覺地了解圖注意力神經網絡(GAT)，可以通過一個生活中的例子來揭示其工作原理和應用。
在中國的傳統婚禮中，座位安排是一項重要的任務。主辦方需要考慮所有賓客間的關系，以確定每個人在婚禮上都能享受到愉快的體驗。這個過程可以被視為一個圖，其中每個賓客代表一個節點，賓客間的關系代表邊。主辦方的目标是找到一個最優的座位安排，使得每個桌子的賓客都能和諧相處。
在GAT的架構下，這個過程被模組化為一個注意力機制。每個節點(賓客)都用一個向量表示，稱其為嵌入，可以被視為節點的特征或屬性。在這個例子中，賓客的嵌入可能包括他們的年齡、性别、興趣等資訊。注意力機制的工作原理是通過計算每個節點(賓客)與其他節點(其他賓客)之間的相似度，來決定每個節點的重要性。這個相似度被稱為注意力分數，它是通過一個叫做“點積注意力”的函數計算得出的。注意力分數越高，表示這個節點與其他節點的關系越好，他們被安排在同一個位置的可能性就越大。在這個例子中，如果兩個賓客的注意力分數很高，那麼他們可能會被安排在同一個桌子上。在這個過程中，GAT還會考慮到每個桌子的負責人。這個負責人需要有較高的注意力分數，因 為他需要照顧到桌子上的每一個賓客，確定他們都能享受到婚禮。這就像是在圖中找出最重要的節點。
然而，就像在實際的婚禮座位安排中一樣，GAT也有一些局限性。例如，如果賓客數量非常多，計算每個賓客的注意力分數可能會非常複雜。此外，GAT可能會忽略一些重要的資訊，例如，一些賓客可能雖然與其他人的關系不是很好，但是他們可能是婚禮的重要人物。這就需要在計算注意力分數時，引入更多的資訊，例如賓客的地位、他們對婚禮的貢獻等。
總的來說，GAT是一種強大的工具，它可以幫助解決一些複雜的問題。然而，也需要了解它的局限性，并且在使用它的時候，需要考慮到問題的具體情況。通過将GAT與日常生活中的經驗相聯系，可以更好地了解和應用這個強大的工具。接下來本文将着重介紹GAT的工作原理以及部分算法的設計原理和數學知識。
2 GAT的工作原理
本文根據提出GAT文章Velickovic et al.(2017)中論述的順序，簡單介紹一下GAT的工作原理。如果初次接觸圖神經網絡相關知識，推薦先移步至DGL Team (2023) and LabML Team (2023)了解基礎相關工作。
GAT通常由多個單層圖注意力層組成，以下為一個單層圖注意力層的解釋。N個點與F個特征的輸入可以記為：
(1)
這裡的
作為輸入的特征。這樣的輸入層會對于點生成新的特征，是以輸出結果可以表示為：
(2)
這裡的
.為了将輸入的特征轉換為高維的特征，這裡至少需要一個科學系的線性轉換。在 (Velickovic et al.,2017)中，作者對于每一個點使用了一個共享的線性轉換方式，同時介紹了一個權重矩陣
來參數化線性轉換。
2.1自注意力機制(Self-Attention Mechanism)
差別于注意力機制，自注意力關注每一個點和自己的關系，而與每個點間重要關系不同，按照相應關系得出權重，将權重按照重要關系賦予點與點之間的連接配接上。結合上文提到的W, (Velickovic et al.,2017) 提出了自注意力機制
。是以，對于節點i來說，節點j的特征重要性可以用以下式子衡量：
(3)
這樣的機制可以讓每個節點彼此之間産生聯系，并且摒棄了所有的結構化新消息。
2.2多頭注意力機制(Multi-head Attention)
相較于上述的單一注意力機制中對于h1的處理方法，多頭注意力機制在每一個注意力頭中擷取一個h1k。多頭注意力機制中每個頭的特征值串聯，串聯後的特征以下方式表示：
(4)
在多頭注意力機制下，最終的輸出值将不再是F’個特征，而是KF’ 個特征。對于重複計算得出的結果可以通過取平均值
或者向量的連接配接(Concatenation)
對于更細緻的解釋和數學推導，有興趣的讀者可以移步繼續學習研究：(Graph Attention NetworksExperiment 2022;Graph Attention Networks 2022)。
2.3分步圖示
本文參照(LaBonne,2022)的例子，更好地解釋在節點中如何使用上文中提到的計算方法。對于節點1的embedding自注意力計算方法：
圖1:例子圖示
(5)
其中αij仍為節點之間特征關系的重要性，hi為每個點的屬性向量。基于上面的計算方法，圖注意力機制将計算出節點1的嵌入值。至于處理式子中的圖注意力相關系數，要通過‘四步走’(LaBonne,2022)：線性轉換，激活函數，softmax歸一化，以及多頭的注意力機制來使用神經網絡學習和節點1相關的注意力分數。
第一步，對于每個點與點之間連線的重要性計算，可以通過對于兩點間的向量連接配接 (concatenate) 創造隐藏向量配對。為此，應用linear transformation與一個權重矩陣Watt來實作：
(6)
第二步，添加一個激活函數LeakyReLU：
(7)
第三步，将神經網絡的輸出結果歸一化，友善進行比較：
歸一化後的注意力分值可以計算和比較，但同時産生了新的問題，即自注意力是非常不穩定的。Velickovic et al.,2017)對此提出了給予transformer結構的多頭注意力機制。
(8)(9)
第四步，按照上文提到的多頭注意力機制，這裡用作處理和計算注意力繁分數：
3GAT在組合優化問題中的應用
3.1組合優化問題
組合優化問題是運籌學中的核心問題，也是學者開始學習運籌學的必經之路。組合優化問題是計算機科學和運籌學中的核心領域，涉及到許多實際應用，如物流、排程和網絡設計等。組合優化問題 在許多實際應用中都起着至關重要的作用。例如，在物流領域，組合優化問題可以幫助人們在紛繁錯 雜的運輸條件中，找到最優的貨物配送路線，進而節省運輸成本和提高貨運效率。在排程問題中，組合優化可以幫助人們有效地配置設定資源，以滿足各種限制條件，同時最大化或最小化某個所需的某個目标值（通常稱為目标函數）。
然而，傳統的組合優化算法通常需要針對每個新問題從頭開始設計，并且需要專家對問題結構進行仔細的考慮。解決組合優化問題通常需要大量的計算資源，特别是對于來源于現實的問題，通常情況下問題本身規模十分龐大，傳統的優化算法可能無法在合理的時間内找到解決方案，甚至無法在可達的時間内求解。是以，如何有效地解決組合優化問題，一直是研究者們關注的焦點。近年來，使用馬爾科夫鍊構造動态規劃的方式，可以解決被表述為由狀态、動作和獎勵定義的單人遊戲的組合優化問題，包括最小生成樹、最短路徑、旅行商問題（TSP）和車輛路徑問題（VRP），而無需專家知識。這種方法使用強化學習訓練圖注意力神經網絡（GNN），在未标記的圖訓練集上進行訓練。訓練後的網絡可以線上性運作時間内輸出新圖執行個體的近似解。在TSP問題中，GAT可以有效地處理城市之間的距離關系，進而找到最短的旅行路徑。在VRP問題中，GAT可以有效地處理車輛、客戶 和倉庫之間的關系，進而找到最優的配送路線。這些研究結果表明，GAT在解決組合優化問題方面，具 有巨大的潛力。
3.2GAT解決路徑規劃論文案例
(Kool et al.,2018)中提出了一種類似GAT的基于注意力機制的模型來解決不同的路徑規劃問題,包括TSP, VRP, OP等問題。本文主要是通過将路徑規劃問題(例如TSP)構造為基于圖的問題，在TSP中 的每個顧客點位的位置以及其它資訊作節點的特征。經由基于注意力機制的編碼-解碼器，得出路徑結果即一個随機政策π(π|s), 使用此政策在給定的測試資料點中找到最有路徑方法π,此方法被θ參數化并且分解為：
(10)
解碼過程是順序進行的。在每個時間步，解碼器根據編碼器的嵌入和在時間生成的輸出來輸出節點πt。在解碼過程中，增加一個特殊的上下文節點來表示解碼上下文。解碼器在編碼器的頂部計算一個注意力(子)層，但是隻向上下文節點發送消息以提高效率。最後的機率是使用單頭注意力機制計算的。在 時間t，解碼器的上下文來自編碼器和在時間t之前的輸出。對于TSP來說包括圖的嵌入，前一個(最 後一個)節點πt-1和第一個節點π1。同時為了計算輸出機率，添加一個具有單個注意力頭的最終解碼器層。文章通過梯度下降優化損失L，使用REINFORCE梯度估計器和基線。文章使用Rollout基線，基線政策的更新是周期性的，也是較好的模型定義政策，用來确定性貪婪Rollout的解決方案。
文章還詳細讨論了對于不同問題的處理政策，例如對于獎勵收集旅行商問題(PCTSP)，作者在編碼器中使用了單獨的參數來處理倉庫節點，并且提供了節點獎勵和懲罰作為輸入特征。在解碼器的上下文中，作者使用了目前/最後的位置和剩餘的獎勵來收集。在PCTSP中，如果剩餘的獎勵大于0且所有節點都沒有被通路過，那麼倉庫節點不能被通路。隻有當節點已經被通路過時，才會被屏蔽(即不 能被通路)。
由于篇幅限制，本文隻着重介紹Kool et al. (2018)是如何基于圖注意力機制來構造在TSP中節點 間互相傳遞權重資訊的算法。在文中構造的圖中，節點接收到的帶有權重的資訊，來自于自己和周圍的鄰點們。而這些節點位的資訊值是取決于其查詢與鄰居的鍵的相容性，如Figure6所示。作者定義了dk, dv并設計計算了相應的ki∈ ℝdk, vi∈ ℝdv, qi∈ ℝdk。對于所有點位的對應qi ,ki,v i，通過以下方法 投影嵌入到hi來計算：
其中的WQ,WK是兩組維數是dk ×dh的參數矩陣，WV的大小是(dv × dh). (推薦想深入了解Transformer中q, k, v設定與計算方法的讀者，移步至WMathor (2020))
兩點之間的相容性，就是通過計算節點i的qi同j點的kj之間的值uij來實作的 (Velickovic et al.,2017)：
(11)
設定-∞避免了不相接的點互相傳遞資訊，通過建構的相容性，類似于Velickovic et al.(2017)中的eij, Khalil et al.(2017) 是這樣計算注意力權重aij的：
(12)
最終，節點i将接收到一個向量h’i，其中包含了向量vj的凸組合：
(13)
4結語
4.1GAT的未來發展和應用前景
圖注意力網絡(GAT)在解決組合優化問題，特别是旅行商問題(TSP)和車輛路徑問題(VRP)等問題上的能力已經得到了廣泛的證明。然而也需要注意到，雖然GAT在這些問題上表現出了優越性，但是它并不是萬能的。對于一些特定的問題，可能需要設計特定的模型或者算法來解決。是以，在研究問題時，需要根據問題的具體情況，結合GAT解決問題的特性，選擇合适的工具來解決不同的組合 優化問題。
在其它領域GAT也發揮着不同的作用，例如，Zhang et al. (2022)中提出了一種新的GAT架構，該架構可以捕獲不同規模圖知識之間的潛在關聯。這種新的GAT架構在預測準确性和訓練速度上都優于 傳統的GAT模型。
此外，Shao et al.(2022)提出了一種新的動态多圖注意力模型，該模型可以處理長期的時空預測問題。這種模型通過建構新的圖模型來表示每個節點的上下文資訊，并利用長期的時空資料依賴結構。這種方法在兩個大規模資料集上的實驗表明，它可以顯著提高現有圖神經網絡模型在長期時空預測任務上的性能。
在股票市場預測方面，GAT也有着廣泛的應用。Zhao et al. (2022)提出了一種基于雙注意力網絡的股票移動預測方法。首先建構了一個包含兩種類型的實體(包括上市公司和相關的高管)和混合關系(包括顯式關系和隐式關系)的市場知識圖。然後，提出了一種雙注意力網絡，通過這個網絡可以 學習到市場知識圖中的動量溢出信号，進而進行股票預測。實驗結果表明，該方法在股票預測方面的性能優于九種最先進的基線方法。
總的來說，圖形的視角為研究提供了一種全新的方式來了解和解決問題。将已有的問題以圖形的形式思考和轉換，不僅可以揭示問題的新的方面和特性，而且還可能引發新的創新點。同樣，将新的問題用圖形方法思考，也可能帶來意想不到的收獲。這種方法的優點在于，它可以幫助學者更好地了解問題的結構和複雜性，進而找到更有效的解決方案。希望大家從本篇對于GAT的介紹開始，可以更多了解圖神經網絡的原理，更多地應用到自己的學 習和研究當中，通過使用GAT可以為解決問題提供強有力的支援。
作者簡介
作者鄧楊，西安交通大學管理學院-香港城市大學系統工程學院聯合培養博三學生，研究方向為強化學習在城市物流中的應用。碩士畢業于南加州大學交通工程專業，榮譽畢業生。曾就職于工程咨詢 企業HATCH洛杉矶辦公室，加州注冊EIT。曾獲AACYF 2017年‘三十位三十歲以下優秀創業青年’、2019年‘全美十大華裔傑出青年’等稱号。現為標頭市海聯會副會長、僑聯、歐美同學會會員。
References
1.DGL Team. 9 Graph Attention Network (GAT) Deep Graph Library (DGL). https: //docs .dgl.ai/ en/0.8.x/tutorials/models/1_gnn/9_gat.html (2023).
2.Graph Attention Networks LabML. https://nn.labml.ai/graphs/gat/index.html (2023).
3.Graph Attention Networks Experiment LabML. https://nn.labml.ai/graphs/gat/experiment. html (2023).
4.Khalil, E., Dai, H., Zhang, Y., Dilkina, B. & Song, L. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems 30 (2017).
5.Kool, W., Van Hoof, H. & Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 (2018).
6.LabML Team. Graph Neural Networks LabML. https://nn.labml.ai/graphs/index.html (2023).
7.LaBonne, M. Graph Attention Networks: Theoretical and Practical Insights https : / / mlabonne . github.io/blog/posts/2022-03-09-graph_attention_network.html (2023).
8.Shao, W., Jin, Z., Wang, S., Kang, Y., Xiao, X., Menouar, H., Zhang, Z., Zhang, J. & Salim, F. Long-term Spatio-Temporal Forecasting via Dynamic Multiple-Graph Attention. arXiv preprint arXiv:2204.11008 (2022).
9.Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y., et al. Graph attention networks. stat 1050, 10–48550 (2017).
10.WMathor. Graph Attention Networks https://wmathor.com/index.php/archives/1438/ (2023).
11.Zhang, W., Yin, Z., Sheng, Z., Li, Y., Ouyang, W., Li, X., Tao, Y., Yang, Z. & Cui, B. Graph attention multilayer perceptron in Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (2022), 4560–4570.
12.Zhao, Y., Du, H., Liu, Y., Wei, S., Chen, X., Zhuang, F., Li, Q. & Kou, G. Stock Movement Prediction Based on Bi-Typed Hybrid-Relational Market Knowledge Graph Via Dual Attention Networks. IEEE Transactions on Knowledge and Data Engineering (2022).REFERENCES