原創(chuàng) | 圖注意力神經(jīng)網(wǎng)絡(luò)(Graph Attention Networks)綜述（2）

3GAT在組合優(yōu)化問題中的應(yīng)用

3.1組合優(yōu)化問題

組合優(yōu)化問題是運(yùn)籌學(xué)中的核心問題，也是學(xué)者開始學(xué)習(xí)運(yùn)籌學(xué)的必經(jīng)之路。組合優(yōu)化問題是計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)中的核心領(lǐng)域，涉及到許多實(shí)際應(yīng)用，如物流、調(diào)度和網(wǎng)絡(luò)設(shè)計(jì)等。組合優(yōu)化問題 在許多實(shí)際應(yīng)用中都起著至關(guān)重要的作用。例如，在物流領(lǐng)域，組合優(yōu)化問題可以幫助人們?cè)诩姺卞e(cuò) 雜的運(yùn)輸條件中，找到最優(yōu)的貨物配送路線，從而節(jié)省運(yùn)輸成本和提高貨運(yùn)效率。在調(diào)度問題中，組合優(yōu)化可以幫助人們有效地分配資源，以滿足各種約束條件，同時(shí)最大化或最小化某個(gè)所需的某個(gè)目標(biāo)值（通常稱為目標(biāo)函數(shù)）。

然而，傳統(tǒng)的組合優(yōu)化算法通常需要針對(duì)每個(gè)新問題從頭開始設(shè)計(jì)，并且需要專家對(duì)問題結(jié)構(gòu)進(jìn)行仔細(xì)的考慮。解決組合優(yōu)化問題通常需要大量的計(jì)算資源，特別是對(duì)于來(lái)源于現(xiàn)實(shí)的問題，通常情況下問題本身規(guī)模十分龐大，傳統(tǒng)的優(yōu)化算法可能無(wú)法在合理的時(shí)間內(nèi)找到解決方案，甚至無(wú)法在可達(dá)的時(shí)間內(nèi)求解。因此，如何有效地解決組合優(yōu)化問題，一直是研究者們關(guān)注的焦點(diǎn)。近年來(lái)，使用馬爾科夫鏈構(gòu)造動(dòng)態(tài)規(guī)劃的方式，可以解決被表述為由狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)定義的單人游戲的組合優(yōu)化問題，包括最小生成樹、最短路徑、旅行商問題（TSP）和車輛路徑問題（VRP），而無(wú)需專家知識(shí)。這種方法使用強(qiáng)化學(xué)習(xí)訓(xùn)練圖注意力神經(jīng)網(wǎng)絡(luò)（GNN），在未標(biāo)記的圖訓(xùn)練集上進(jìn)行訓(xùn)練。訓(xùn)練后的網(wǎng)絡(luò)可以在線性運(yùn)行時(shí)間內(nèi)輸出新圖實(shí)例的近似解。在TSP問題中，GAT可以有效地處理城市之間的距離關(guān)系，從而找到最短的旅行路徑。在VRP問題中，GAT可以有效地處理車輛、客戶 和倉(cāng)庫(kù)之間的關(guān)系，從而找到最優(yōu)的配送路線。這些研究結(jié)果表明，GAT在解決組合優(yōu)化問題方面，具 有巨大的潛力。

3.2GAT解決路徑規(guī)劃論文案例

(Kool et al.,2018)中提出了一種類似GAT的基于注意力機(jī)制的模型來(lái)解決不同的路徑規(guī)劃問題,包括TSP, VRP, OP等問題。本文主要是通過(guò)將路徑規(guī)劃問題(例如TSP)構(gòu)造為基于圖的問題，在TSP中 的每個(gè)顧客點(diǎn)位的位置以及其它信息作節(jié)點(diǎn)的特征。經(jīng)由基于注意力機(jī)制的編碼-****，得出路徑結(jié)果即一個(gè)隨機(jī)策略π(π|s), 使用此策略在給定的測(cè)試數(shù)據(jù)點(diǎn)中找到最有路徑方法π,此方法被θ參數(shù)化并且分解為：

       (10)

解碼過(guò)程是順序進(jìn)行的。在每個(gè)時(shí)間步，****根據(jù)編碼器的嵌入和在時(shí)間生成的輸出來(lái)輸出節(jié)點(diǎn)πt。在解碼過(guò)程中，增加一個(gè)特殊的上下文節(jié)點(diǎn)來(lái)表示解碼上下文。****在編碼器的頂部計(jì)算一個(gè)注意力(子)層，但是只向上下文節(jié)點(diǎn)發(fā)送消息以提高效率。最后的概率是使用單頭注意力機(jī)制計(jì)算的。在 時(shí)間t，****的上下文來(lái)自編碼器和在時(shí)間t之前的輸出。對(duì)于TSP來(lái)說(shuō)包括圖的嵌入，前一個(gè)(最 后一個(gè))節(jié)點(diǎn)πt-1和第一個(gè)節(jié)點(diǎn)π1。同時(shí)為了計(jì)算輸出概率，添加一個(gè)具有單個(gè)注意力頭的最終****層。文章通過(guò)梯度下降優(yōu)化損失L，使用REINFORCE梯度估計(jì)器和基線。文章使用Rollout基線，基線策略的更新是周期性的，也是較好的模型定義策略，用來(lái)確定性貪婪Rollout的解決方案。

文章還詳細(xì)討論了對(duì)于不同問題的處理策略，例如對(duì)于獎(jiǎng)勵(lì)收集旅行商問題(PCTSP)，作者在編碼器中使用了單獨(dú)的參數(shù)來(lái)處理倉(cāng)庫(kù)節(jié)點(diǎn)，并且提供了節(jié)點(diǎn)獎(jiǎng)勵(lì)和懲罰作為輸入特征。在****的上下文中，作者使用了當(dāng)前/最后的位置和剩余的獎(jiǎng)勵(lì)來(lái)收集。在PCTSP中，如果剩余的獎(jiǎng)勵(lì)大于0且所有節(jié)點(diǎn)都沒有被訪問過(guò)，那么倉(cāng)庫(kù)節(jié)點(diǎn)不能被訪問。只有當(dāng)節(jié)點(diǎn)已經(jīng)被訪問過(guò)時(shí)，才會(huì)被屏蔽(即不 能被訪問)。

由于篇幅限制，本文只著重介紹Kool et al. (2018)是如何基于圖注意力機(jī)制來(lái)構(gòu)造在TSP中節(jié)點(diǎn) 間相互傳遞加權(quán)信息的算法。在文中構(gòu)造的圖中，節(jié)點(diǎn)接收到的帶有權(quán)重的信息，來(lái)自于自己和周圍的鄰點(diǎn)們。而這些節(jié)點(diǎn)位的信息值是取決于其查詢與鄰居的鍵的兼容性，如Figure6所示。作者定義了dk, dv并設(shè)計(jì)計(jì)算了相應(yīng)的ki∈ ?dk, vi∈ ?dv, qi∈ ?dk。對(duì)于所有點(diǎn)位的對(duì)應(yīng)qi ,ki,v i，通過(guò)以下方法 投影嵌入到hi來(lái)計(jì)算：

其中的WQ,WK是兩組維數(shù)是dk ×dh的參數(shù)矩陣，WV的大小是(dv × dh). (推薦想深入了解Transformer中q, k, v設(shè)置與計(jì)算方法的讀者，移步至WMathor (2020))

兩點(diǎn)之間的兼容性，就是通過(guò)計(jì)算節(jié)點(diǎn)i的qi同j點(diǎn)的kj之間的值uij來(lái)實(shí)現(xiàn)的 (Velickovic et al.,2017)：

(11)

設(shè)置-∞避免了不相接的點(diǎn)互相傳遞信息，通過(guò)構(gòu)建的兼容性，類似于Velickovic et al.(2017)中的eij, Khalil et al.(2017) 是這樣計(jì)算注意力權(quán)重aij的：

       (12)

最終，節(jié)點(diǎn)i將接收到一個(gè)向量h’i，其中包含了向量vj的凸組合：

       (13)

4結(jié)語(yǔ)

4.1GAT的未來(lái)發(fā)展和應(yīng)用前景

圖注意力網(wǎng)絡(luò)(GAT)在解決組合優(yōu)化問題，特別是旅行商問題(TSP)和車輛路徑問題(VRP)等問題上的能力已經(jīng)得到了廣泛的證明。然而也需要注意到，雖然GAT在這些問題上表現(xiàn)出了優(yōu)越性，但是它并不是萬(wàn)能的。對(duì)于一些特定的問題，可能需要設(shè)計(jì)特定的模型或者算法來(lái)解決。因此，在研究問題時(shí)，需要根據(jù)問題的具體情況，結(jié)合GAT解決問題的特性，選擇合適的工具來(lái)解決不同的組合 優(yōu)化問題。

在其它領(lǐng)域GAT也發(fā)揮著不同的作用，例如，Zhang et al. (2022)中提出了一種新的GAT架構(gòu)，該架構(gòu)可以捕獲不同規(guī)模圖知識(shí)之間的潛在關(guān)聯(lián)。這種新的GAT架構(gòu)在預(yù)測(cè)準(zhǔn)確性和訓(xùn)練速度上都優(yōu)于 傳統(tǒng)的GAT模型。

此外，Shao et al.(2022)提出了一種新的動(dòng)態(tài)多圖注意力模型，該模型可以處理長(zhǎng)期的時(shí)空預(yù)測(cè)問題。這種模型通過(guò)構(gòu)建新的圖模型來(lái)表示每個(gè)節(jié)點(diǎn)的上下文信息，并利用長(zhǎng)期的時(shí)空數(shù)據(jù)依賴結(jié)構(gòu)。這種方法在兩個(gè)大規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)表明，它可以顯著提高現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)模型在長(zhǎng)期時(shí)空預(yù)測(cè)任務(wù)上的性能。

在股票市場(chǎng)預(yù)測(cè)方面，GAT也有著廣泛的應(yīng)用。Zhao et al. (2022)提出了一種基于雙注意力網(wǎng)絡(luò)的股票移動(dòng)預(yù)測(cè)方法。首先構(gòu)建了一個(gè)包含兩種類型的實(shí)體(包括上市公司和相關(guān)的高管)和混合關(guān)系(包括顯式關(guān)系和隱式關(guān)系)的市場(chǎng)知識(shí)圖。然后，提出了一種雙注意力網(wǎng)絡(luò)，通過(guò)這個(gè)網(wǎng)絡(luò)可以 學(xué)習(xí)到市場(chǎng)知識(shí)圖中的動(dòng)量溢出信號(hào)，從而進(jìn)行股票預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明，該方法在股票預(yù)測(cè)方面的性能優(yōu)于九種最先進(jìn)的基線方法。

總的來(lái)說(shuō)，圖形的視角為研究提供了一種全新的方式來(lái)理解和解決問題。將已有的問題以圖形的形式思考和轉(zhuǎn)換，不僅可以揭示問題的新的方面和特性，而且還可能引發(fā)新的創(chuàng)新點(diǎn)。同樣，將新的問題用圖形方法思考，也可能帶來(lái)意想不到的收獲。這種方法的優(yōu)點(diǎn)在于，它可以幫助學(xué)者更好地理解問題的結(jié)構(gòu)和復(fù)雜性，從而找到更有效的解決方案。希望大家從本篇對(duì)于GAT的介紹開始，可以更多了解圖神經(jīng)網(wǎng)絡(luò)的原理，更多地應(yīng)用到自己的學(xué) 習(xí)和研究當(dāng)中，通過(guò)使用GAT可以為解決問題提供強(qiáng)有力的支持。

作者簡(jiǎn)介

作者鄧楊，西安交通大學(xué)管理學(xué)院-香港城市大學(xué)系統(tǒng)工程學(xué)院聯(lián)合培養(yǎng)博三學(xué)生，研究方向?yàn)閺?qiáng)化學(xué)習(xí)在城市物流中的應(yīng)用。碩士畢業(yè)于南加州大學(xué)交通工程專業(yè)，榮譽(yù)畢業(yè)生。曾就職于工程咨詢 企業(yè)HATCH洛杉磯辦公室，加州注冊(cè)EIT。曾獲AACYF 2017年‘三十位三十歲以下優(yōu)秀創(chuàng)業(yè)青年’、2019年‘全美十大華裔杰出青年’等稱號(hào)。現(xiàn)為包頭市海聯(lián)會(huì)副會(huì)長(zhǎng)、僑聯(lián)、歐美同學(xué)會(huì)會(huì)員。

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