https://www.sciencedirect.com/science/article/pii/S2667305324000292
Conjunctive block coding for hyperdimensional graph representation
用于超維圖表示的合取塊編碼
摘要
知識圖譜（KGs）已經(jīng)成為機器學(xué)習(xí)中一個關(guān)鍵的知識表示工具，不僅提供了獲取現(xiàn)有知識的方式，還通過高級應(yīng)用使得新知識的發(fā)現(xiàn)成為可能。在這些應(yīng)用中使用的可擴展推理方法中，分布式圖嵌入方法，特別是圖神經(jīng)網(wǎng)絡(luò)（GNNs），已經(jīng)因為大規(guī)模圖相關(guān)任務(wù)而變得流行。然而，這些方法中的許多在可解釋性方面存在局限性，并且未能在其表示中考慮結(jié)構(gòu)相似性。超維計算（HDC），也被稱為向量符號架構(gòu)（VSA），通過在符號概念的分布式表示上使用定義良好的認知操作來解決這一問題。本文提出了一種新的向量符號圖表示方法CLOG，它保留了超出邊對應(yīng)關(guān)系的近似結(jié)構(gòu)相似性，并與以前的方法有根本的不同。通過理論分析、圖重建實驗和鏈接預(yù)測任務(wù)評估了該模型在圖表示中的有效性，突出了其效率和準確性。這種方法通過增強HDC在圖表示中的能力，顯著推進了該領(lǐng)域的發(fā)展，代表了對現(xiàn)有方法的顯著改進。
關(guān)鍵詞：超維計算 向量符號架構(gòu) 圖表示 認知計算
1. 引言
知識圖譜（KG）作為一種知識表示類型，在機器學(xué)習(xí)社區(qū)中引起了特別的興趣。知識圖譜是由實體作為節(jié)點、關(guān)系作為邊構(gòu)成的多關(guān)系有向圖。它收集并組織關(guān)于實體的關(guān)系和屬性，在許多應(yīng)用中扮演著越來越重要的角色，包括問答和信息檢索。除了從知識圖譜中檢索現(xiàn)有信息外，像鏈接預(yù)測和知識圖譜補全這樣的高級應(yīng)用還能夠在圖譜內(nèi)發(fā)現(xiàn)新的和隱藏的知識（Chen等，2020）。
像Freebase（Bollacker等，2008）、WordNet（Fellbaum，2010）和GeneOntology（Ashburner等，2000）這樣的大規(guī)模知識圖譜對于包括網(wǎng)絡(luò)/移動搜索和問答在內(nèi)的AI應(yīng)用至關(guān)重要。傳統(tǒng)的形式邏輯推理在這些廣泛的圖譜中進行長距離推理時存在困難（Zamini等，2022）?，F(xiàn)在更傾向于使用分布式圖嵌入等可擴展方法來處理大規(guī)模任務(wù)，為高效的圖算法執(zhí)行提供低維空間表示。圖神經(jīng)網(wǎng)絡(luò)（GNNs）因其在圖相關(guān)問題中的有效性而越來越受歡迎（Arora，2020；Cheng等，2022；Park等，2019）。然而，GNNs通常需要大量的標記數(shù)據(jù)才能達到最佳性能，知識圖譜的長尾特性，即許多關(guān)系只在少數(shù)三元組中出現(xiàn)（Zhang等，2022），給純粹的數(shù)據(jù)驅(qū)動方法帶來了挑戰(zhàn)。
知識圖譜嵌入方法面臨兩個主要限制。首先，它們將符號化的邏輯知識圖譜轉(zhuǎn)換為連續(xù)表示，而不保留實體和關(guān)系完整性，限制了基于梯度的方法只能進行事后解釋（Hersche等，2023）。其次，正如Zamini等（2022）所強調(diào)的，許多方法在捕捉多步關(guān)系和利用結(jié)構(gòu)相似性進行鏈接預(yù)測和圖譜補全方面存在困難。雖然圖神經(jīng)網(wǎng)絡(luò)（GNNs）使用網(wǎng)絡(luò)架構(gòu)來隱式地解決這些問題，但組成（實體、關(guān)系）相似性和結(jié)構(gòu)相似性之間的重疊常常使得預(yù)測的驅(qū)動因素變得不明確。組成相似性主要源于元素的內(nèi)在屬性，而結(jié)構(gòu)相似性則是從它與其他元素的關(guān)系中派生出來的。
為了激發(fā)結(jié)構(gòu)相似性和組成相似性的解耦，我們轉(zhuǎn)向類比推理的研究，這是一種在人類認知中普遍存在的形式，旨在識別兩種情況之間的共同關(guān)系系統(tǒng)，并從它們的共同點中推斷（Gentner & Smith，2013）。作為一種在兩組實體及其關(guān)系之間的結(jié)構(gòu)相似性上嚴重依賴的方法，它既提供了洞察力，也引入了潛在的謬誤。除了引用諺語來突出常見情況中的模式外，人們還利用類比推理在已知系統(tǒng)和未知系統(tǒng)之間建立聯(lián)系，以促進理解和假設(shè)生成（Gentner & Smith，2013），而有時由于實體和關(guān)系的表面匹配，類比可能會產(chǎn)生事實上不正確的推斷。通過區(qū)分這兩種相似性，我們可能在模型使用它們時提供更好的控制。
超維計算（HDC），也稱為向量符號架構(gòu)（VSA），通過在符號概念的分布式表示上執(zhí)行定義明確的認知操作來解決可解釋性和類比相似性的問題。HDC的設(shè)計確保了超維向量（超向量）內(nèi)符號概念的完整性，從而實現(xiàn)了可解釋性。這些表示允許在圖的大小在超向量的記憶容量內(nèi)時恢復(fù)圖的節(jié)點和邊。此外，由于圖由單個超向量表示，圖超向量的點積反映了它們之間的某些全局相似性。雖然存在各種圖表示算法（Gayler & Levy，2009；Nunes等，2022；Poduval等，2022），但它們都會產(chǎn)生基于邊匹配來確定結(jié)構(gòu)相似性的圖超向量，由于超向量的記憶容量而面臨可擴展性限制。
本工作旨在提出并評估一種新的向量符號圖表示方法，該方法保留了超出邊對應(yīng)關(guān)系的近似結(jié)構(gòu)相似性。我們介紹了CLOG：用于超維圖表示的聯(lián)合塊編碼，這是一種與以前方法根本不同的方法。我們的貢獻包括：
? 一種新的超維圖表示方法，利用HDC的變量綁定操作符來保留每個節(jié)點到鄰居的聯(lián)合連接。直接的結(jié)果是增加了超向量對稀疏圖的記憶容量。
? 一種塊編碼和掩蔽方案，用于將原子概念（在這種情況下是圖節(jié)點）投影到超維空間，從而實現(xiàn)鄰居的松散聯(lián)合，使得表示的解碼更加高效。
? 由于CLOG與GNN采取的方法正交，我們提出了CLOG與GNN的集成。為了展示CLOG在知識圖譜結(jié)構(gòu)表示方面的能力，我們還在基準鏈接預(yù)測數(shù)據(jù)集上測試了我們的模型，并將其與現(xiàn)有方法進行了比較。
接下來的部分涵蓋了該領(lǐng)域的相關(guān)文獻。第3節(jié)討論了超維計算的基本原理和現(xiàn)有的HDC圖表示。第4節(jié)介紹了所提出方法及其組成部分的細節(jié)。第5節(jié)提供了CLOG的實驗和評估及其在各種任務(wù)中的性能。
2. 相關(guān)工作
2.1 圖表示
圖表示方法是計算機科學(xué)中一個關(guān)鍵的研究領(lǐng)域，特別是在數(shù)據(jù)科學(xué)、機器學(xué)習(xí)和網(wǎng)絡(luò)分析領(lǐng)域。這些方法旨在有效且高效地表示圖結(jié)構(gòu)數(shù)據(jù)，由于其非歐幾里得特性，這種數(shù)據(jù)本質(zhì)上是復(fù)雜的。
Perozzi等人（2014）的開創(chuàng)性工作標志著一個基礎(chǔ)性的轉(zhuǎn)變，通過將自然語言處理技術(shù)應(yīng)用于圖數(shù)據(jù)，使用截斷的隨機游走來學(xué)習(xí)社交表示。Grover和Leskovec（2016）進一步改進了這一概念，增強了模型捕捉局部和全局網(wǎng)絡(luò)結(jié)構(gòu)的靈活性?；谶@些嵌入，圖神經(jīng)網(wǎng)絡(luò)（GNNs）領(lǐng)域出現(xiàn)了，關(guān)鍵貢獻如Kipf和Welling（2016），將深度學(xué)習(xí)擴展到圖結(jié)構(gòu)數(shù)據(jù)。Velickovic等人（2017）引入的圖注意力網(wǎng)絡(luò)（GATs）增加了基于注意力的機制，允許對節(jié)點重要性進行更細致的評估。Dwivedi和Bresson（2020）進一步復(fù)雜化了這一領(lǐng)域，將最初為自然語言處理中的序列數(shù)據(jù)設(shè)計的變換器架構(gòu)擴展到處理圖結(jié)構(gòu)數(shù)據(jù)。當前研究正專注于增強這些方法的可擴展性（Huang, Li, Cao等人，2022；Li等人，2023；Rampá?ek等人，2022；Thakoor等人，2021）、可解釋性（Chen, Jiao, Liu等人，2022；Feng等人，2022；Huang, Yamada, Tian等人，2022；Wu等人，2023）和泛化能力，解決圖結(jié)構(gòu)數(shù)據(jù)在現(xiàn)實世界中的復(fù)雜性（Gao等人，2023；Li, Zheng, Feng等人，2023；Li, Zhang, Cui等人，2023；Liu等人，2023；Wang等人，2022）。
2.2 超維計算
超維計算的基本概念已經(jīng)建立相當長一段時間，但直到最近幾年，它們在理論和實踐中才開始獲得顯著的關(guān)注。關(guān)鍵的理論發(fā)展（Clarkson等人，2023；Frady等人，2018）吸引了更廣泛的機器學(xué)習(xí)社區(qū)的注意，導(dǎo)致了廣泛的實際部署，包括健康監(jiān)測（Ge & Parhi，2022；Moin等人，2021；Ni, Lesica, Zeng等人，2022）、強化學(xué)習(xí)（Chen, Issa, Ni等人，2022；Ni等人，2022）和輕量級識別算法（Imani等人，2022；Lee等人，2023）。這種日益增長的興趣可以歸因于HDC能力解決當代人工神經(jīng)網(wǎng)絡(luò)中發(fā)現(xiàn)的一些缺點的方式，包括更高的學(xué)習(xí)效率（Hersche等人，2022；Ni等人，2024）、更好的可解釋性（Poduval等人，2022）以及在硬件平臺上的自然并行性（Chen等人，2024）。因此，出現(xiàn)了一種將神經(jīng)符號方法合并的混合模型的新興趨勢（Hersche等人，2023；Lee等人，2023；Zou等人，2022）。
特別地，HDC在圖表示學(xué)習(xí)領(lǐng)域顯示出與圖卷積神經(jīng)網(wǎng)絡(luò)（GCN）競爭的巨大潛力（Poduval等人，2022）。雖然HDC圖表示與GNNs在處理圖數(shù)據(jù)時的聚合階段有一些相似之處，但其方法和目標有顯著不同。GNNs在學(xué)習(xí)任務(wù)中表現(xiàn)出色，但在高級推理和知識提取方面缺乏能力，因為神經(jīng)網(wǎng)絡(luò)通常專注于學(xué)習(xí)而非記憶。相比之下，超維學(xué)習(xí)使用符號超向量，模仿強大的類腦推理，并消除了在多個層中進行迭代節(jié)點聚合的需要（Chen等人，2023；Kang等人，2022；Nunes等人，2022；Poduval等人，2022）。
3 預(yù)備知識
3.1. 超維計算
超維計算（HDC），也稱為向量符號架構(gòu)（VSA）（Gayler，1998；Kanerva，1996；Plate等人，1991），具有將數(shù)據(jù)結(jié)構(gòu)操作成分布式表示的能力。HDC在超維向量空間中全息地編碼數(shù)據(jù)結(jié)構(gòu)，其中隨機超向量，即超維向量，被用作表示的基礎(chǔ)，并且采用三種主要操作在超維空間上形成代數(shù)。
在這項研究中，使用獨立的隨機雙極向量作為原子原語，其維度為。向量之間的相似性通過它們的點積來衡量，，從1到的求和，這表明原子對象是否相同以及復(fù)雜對象之間的結(jié)構(gòu)相似性。為了構(gòu)建結(jié)構(gòu)化對象，定義了以下三種HDC操作：
捆綁（+）操作是通過超向量的逐元素相加完成的，表示為 = 1 +2。這個操作疊加元素，充當記憶功能，將輸入數(shù)據(jù)的信息保留結(jié)果在向量中。捆綁的超向量與其原子超向量保持相似性，即?,? ? 0；因此，它非常適合表示集合。這種相似性意味著即使來自多個向量的信息被組合，各個向量的本質(zhì)也不會丟失，這有助于在HDC框架內(nèi)進行聯(lián)想記憶檢索。
綁定（⊙）1和2是通過兩個超向量之間的Hadamard積，即逐元素相乘來，完成的，表示為 = 1 ⊙ 2。結(jié)果的合取超向量與其組成的向量不同，?,1? ≈ 0。這個操作是可逆的，即1 = ⊙ 。由于綁定在某種意義上保持了其成分的信息而不增加大小，它可以作為變量關(guān)聯(lián)。這種可逆性允許檢索原始信息，使綁定成為HDC中編碼復(fù)雜關(guān)系的強大工具。
排列（）操作， = ()，對的組件應(yīng)用循環(huán)移位。排列在捆綁上分配，( + 2) = (1) + (2)，以及綁定，(1 ⊙ 2) = (1) ⊙ (2)。像綁定一樣，排列使超向量分離，當 ≠ 0時，?(),? ≈ 0。由于排列是可逆的，并且通過對超向量的重復(fù)排列引入自然順序，它被用來表示序列和為不同層級的層次結(jié)構(gòu)編碼順序。
3.2. HDC中的圖表示
盡管算法和節(jié)點排序存在一些差異，現(xiàn)有的HDC圖表示主要利用邊對應(yīng)作為結(jié)構(gòu)相似性的度量（Gayler & Levy，2009；Nunes等人，2022；Poduval等人，2022）。對于一個無向圖 = (, )，該框架首先為圖中的每個節(jié)點 ∈ 分配一個大小為的隨機雙極超向量，并生成大小為 × 的碼本矩陣 = [1, 2, ..., ]，作為圖節(jié)點的超維表示。由于是隨機生成的，節(jié)點超向量幾乎正交，每對超向量之間的相似性大約為零：?, ? ≈ 0, ≠ 。
對于每個節(jié)點，基于HDC的模型通過其鄰居集合創(chuàng)建一個節(jié)點記憶超向量： = ∑( ∈ ?()) 。捆綁操作的性質(zhì)意味著節(jié)點記憶與每個捆綁超向量之間的相似性遠大于零：? ∈ ?(), ?, ? ? 0。這個性質(zhì)允許在重建過程中通過相似性檢查檢索每個鄰居。
然后，模型分兩步為整個圖構(gòu)建一個單一的超向量。首先，它將每個節(jié)點超向量與其對應(yīng)的節(jié)點記憶關(guān)聯(lián)（綁定）， ⊙ 。這增加了節(jié)點記憶之間的區(qū)別，并允許模型在圖重建期間識別每個節(jié)點的正確記憶。然后，所有關(guān)聯(lián)的對被捆綁在一起形成圖超向量：
最后的等式利用了綁定操作在捆綁操作上的分配性。結(jié)果是一個透明的模型，它壓縮了圖中所有的邊，每條邊都由端點超向量的綁定來表示。它可以用來重建原始圖或在其上執(zhí)行推理任務(wù)。
要從圖超向量中檢索圖信息，基于HDC的表示框架首先恢復(fù)每個節(jié)點的記憶，這可以通過將圖超向量與相應(yīng)的節(jié)點超向量綁定來大致完成：
獲得的節(jié)點記憶記為，與原始節(jié)點記憶超向量不同，因為它包含了額外的成分。在解碼過程的后續(xù)和最后階段，由于超向量的正交性，這些多余的成分被消除了。
在估計了節(jié)點記憶之后，我們可以通過測量一個節(jié)點的超向量與另一個節(jié)點記憶超向量之間的相似性，，來檢查節(jié)點和之間的連接。如果和之間存在邊，那么否則，
4. 主要貢獻
本節(jié)介紹了我們提出的方法，用于在超維空間中表示圖的結(jié)構(gòu)。如第3節(jié)所述，采用超維數(shù)學(xué)將圖信息分布到一個完全整體的超維表示中。我們引入了CLOG，它采用了獨特的兩階段塊編碼和一種創(chuàng)新的解碼算法。本節(jié)將深入討論這個設(shè)計的細節(jié)。
4.1. 共振網(wǎng)絡(luò)
如第3.2節(jié)所討論的，以前基于HDC的圖表示工作主要利用捆綁操作及其特性將節(jié)點連接聚合到記憶超向量中。使用捆綁來記憶超向量限制了模型的可擴展性，因為結(jié)果記憶超向量的大小將遠大于其原子成分，這導(dǎo)致記憶最終飽和。這種飽和可以在解碼過程變得更加困難時觀察到，并且在嘗試確定記憶與其成分之間的相似性時，噪聲項的數(shù)量增加。
為了克服這一點，可以通過綁定超向量來執(zhí)行記憶，消除上述缺點。然而，當從合取超向量中解碼信息時，這種方法可能具有挑戰(zhàn)性。
雖然綁定操作在已知除一個以外的所有成分時是可逆的，但從給定的綁定超向量中找到所有成分向量并不簡單。一般來說，這個因式分解問題可能涉及兩個或更多的因子，導(dǎo)致潛在解空間的指數(shù)增長。假設(shè)我們給定一個復(fù)合向量，它是個向量的乘積：
由Frady等人（2020）提出的共振網(wǎng)絡(luò)，Kent等人在2020年進一步利用，并在多種應(yīng)用中使用（Frady等人，2022；Renner等人，2022），試圖在不通過窮舉搜索因子的所有可能組合的情況下解決這個問題，如圖1所示。該算法通過在每個相應(yīng)碼本中的所有向量上使用疊加來初始化每個因子的猜測，然后迭代地改進這些猜測，并從上一次迭代中推斷出新的估計值。
通過反復(fù)執(zhí)行指定的操作，共振網(wǎng)絡(luò)可以生成改進的估計，同時降低猜測中的噪聲水平，直到模型達到收斂并發(fā)現(xiàn)解決方案。
4.2. 塊編碼和掩蔽
盡管共振網(wǎng)絡(luò)是一種分解復(fù)合超向量的出色且有效的方法，但它存在可擴展性問題。圖2展示了隨著搜索空間大?。纯赡芤蜃咏M合的數(shù)量）的變化，該方法的準確性和迭代次數(shù)的變化。很明顯，網(wǎng)絡(luò)的準確性只能在搜索空間大小的非常小的范圍內(nèi)保持，這限制了我們案例中輸入圖的大小和密度，因為我們在設(shè)計中稍后使用該方法。同樣明顯的是，對更大圖的嘗試導(dǎo)致算法無法達到收斂，導(dǎo)致準確性下降。進一步增加搜索空間也會導(dǎo)致虛假點和最終準確性降低。
為了解決可擴展性問題，我們提出了一種基礎(chǔ)編碼方法的配置，它允許共振網(wǎng)絡(luò)在更平滑的搜索空間中工作，從而實現(xiàn)更高效的解碼。我們還相應(yīng)地改變了共振網(wǎng)絡(luò)的更新規(guī)則，這顯著減少了網(wǎng)絡(luò)收斂所需的迭代次數(shù)。
我們不是為每個節(jié)點生成一個隨機超向量，而是將每個節(jié)點超向量分成多個塊，只隨機生成其中的一部分，留下其他塊作為所有分量都設(shè)為1的向量。我們定義密度為隨機塊數(shù)與總塊數(shù)的比例：
圖3(a)中可以看到這樣的掩蔽示例。
現(xiàn)在假設(shè)我們正在處理一個因子分解問題，其中的超向量具有掩蔽塊。共振網(wǎng)絡(luò)能夠在其搜索空間中更平滑地更新其猜測，因為之前正交的超向量現(xiàn)在它們之間有了相關(guān)性。
此外，可以觀察到，通過在隨機生成的塊之間添加單位塊，最終復(fù)合超向量中的每個塊在創(chuàng)建時涉及的因子數(shù)量會減少，圖3(b)提供了一個示例。我們可以利用合取向量這一新特性，通過改變共振網(wǎng)絡(luò)的更新規(guī)則并包括新的終止規(guī)則，從而提高其收斂速度。
我們?yōu)楣舱窬W(wǎng)絡(luò)提出了以下新的更新規(guī)則：
當所有因子都達到收斂時，即進一步迭代不會對猜測產(chǎn)生任何變化時，共振網(wǎng)絡(luò)終止其迭代。相同的標準也適用于我們提出的設(shè)計，但使用掩碼和塊超向量可以在這里帶來顯著的優(yōu)勢。通過將超向量分割成塊，并相應(yīng)地更新共振網(wǎng)絡(luò)，可以添加新標準以確保各個塊的收斂。
假設(shè)共振網(wǎng)絡(luò)正在進行第次迭代，目前持有構(gòu)建復(fù)合超向量的因子的猜測?。我們可以將與從綁定所有當前猜測得到的超向量?進行比較。如果兩個提到的向量之間的相似性很高，即?, ?? ? 0，我們可以得出結(jié)論，猜測已經(jīng)收斂到它們各自的碼本條目。假設(shè)超向量像之前描述的那樣被分割成塊，可以獨立于其他塊檢查每個塊的上述標準。同時考慮到掩碼，可以看出，一些塊可能包含作為它們因子的掩碼塊。如果對這種情況使用1掩碼，它們可以作為因子被忽略，因為它們在綁定中充當單位元素，這意味著各個塊可能使用比完整超向量更少的因子構(gòu)建。這可以顯著加快檢測收斂的過程；如果單個超向量塊滿足收斂標準，它們可以被檢查并暗示完整超向量的因子。
4.3. 基于HDC的圖表示CLOG
我們現(xiàn)在提出我們的新穎圖記憶和學(xué)習(xí)方案，CLOG。我們將設(shè)計分為兩部分，首先詳細解釋編碼過程，然后繼續(xù)解碼過程。圖4展示了設(shè)計的高級視圖。
4.3.1. 編碼
在新方法CLOG中，我們使用兩步編碼，減少了捆綁在一起的項的數(shù)量，使模型能夠更好地適應(yīng)圖的大小和密度。這增加了超向量的記憶容量，解決了以前方法中存在的可擴展性問題。首先，我們?yōu)槊總€節(jié)點生成一個維度為的隨機超向量。使用固定數(shù)量的塊，我們還對每個節(jié)點超向量應(yīng)用密度為的隨機掩碼，得到。
生成了表示每個節(jié)點所需的向量后，圖編碼現(xiàn)在可以分為兩個級別的記憶。對于第一級別，CLOG在本地捕獲節(jié)點信息，將每個節(jié)點的所有鄰居關(guān)聯(lián)在一起，形成一個單一的節(jié)點記憶超向量：
其中是完整節(jié)點超向量的掩蔽版本，即 = []，是基礎(chǔ)節(jié)點記憶，它也是一個掩蔽超向量。（注意，如果節(jié)點沒有任何鄰居，則 = 。）為了避免為每個節(jié)點生成更多的超向量，我們可以將掩蔽節(jié)點超向量分配為其相應(yīng)的基礎(chǔ)節(jié)點記憶， = ，假設(shè)圖中不包含任何自環(huán)。
在第一步中利用HDC的變量綁定操作符允許CLOG為每個節(jié)點保留與鄰居的合取連接，這與之前主要關(guān)注邊對應(yīng)的方法相比，表現(xiàn)出根本性的轉(zhuǎn)變。
對于第二級編碼，所有在節(jié)點記憶中收集的信息都被捆綁在一起，形成最終的圖超向量：
其中是完整的節(jié)點超向量，并且對節(jié)點記憶也應(yīng)用了排列，以完全分離兩個編碼級別。值得一提的是，排列的數(shù)量等于超向量塊的長度，這確保了不同塊的內(nèi)容不會混合在一起。
4.3.2. 解碼
重建過程可以分為兩個步驟。首先，從圖超向量中檢索每個節(jié)點的節(jié)點記憶的估計值：
請注意，我們在這里也使用超向量塊的長度作為排列的大小，本質(zhì)上是將塊向后移動一個位置。計算結(jié)果記為?，這與原始節(jié)點記憶不同，可能包含噪聲項。在下一步中，CLOG需要從其節(jié)點記憶超向量中識別每個節(jié)點的鄰居。由于模型通過綁定創(chuàng)建節(jié)點記憶，因此可以使用共振網(wǎng)絡(luò)將生成的綁定超向量分解為其成分，共振網(wǎng)絡(luò)提供了一種高效的超向量分解機制，如第4.1節(jié)所討論的。我們還對共振網(wǎng)絡(luò)應(yīng)用了第4.2節(jié)中討論的修改，遵循編碼步驟中使用的塊編碼和掩蔽，以增加方法的效率和可擴展性。這里我們將使用以下等式：
該公式將所有先前的因子猜測與基礎(chǔ)向量和復(fù)合向量（即檢索到的節(jié)點記憶）相關(guān)聯(lián)，然后計算碼本條目的加權(quán)線性組合，作為當前因子的新猜測。同時請注意，構(gòu)建每個節(jié)點記憶所使用的因子數(shù)量假定為，即最大節(jié)點度。
共振網(wǎng)絡(luò)將更新其對因子的猜測，從第一個因子迭代到最后一個，然后再回到第一個進行新的猜測。迭代將在所有因子達到穩(wěn)定點時結(jié)束，即每個因子的新猜測與前一次迭代保持不變。為了使CLOG獲取所有節(jié)點的鄰居，從而重建完整圖，這個過程需要對每個節(jié)點執(zhí)行。
通過使用塊編碼和掩蔽，我們能夠修改算法，使其在完整超向量收斂之前就找到因子，同時處理的因子數(shù)量也少于。由于塊本質(zhì)上是相互獨立的，我們每隔幾次迭代就執(zhí)行一次塊相似性檢查。如果有塊的猜測綁定與合取向量匹配，這意味著這些塊已經(jīng)收斂。從單個因子開始，即 = 1，算法增加因子數(shù)量，同時識別可以用較少因子構(gòu)建的塊，從而實現(xiàn)更快的收斂。這是掩蔽方法的直接結(jié)果；一些塊可能包含多個掩蔽因子，這有助于共振網(wǎng)絡(luò)用更少的因子和搜索空間大小識別和分解它們。
與以前的模型相比，CLOG在超維計算的圖表示方面引入了重大進步。與主要關(guān)注邊對應(yīng)的早期模型不同，該框架使用綁定操作作為連接相鄰節(jié)點的手段，并結(jié)合了獨特的塊編碼和掩蔽方案，確保了鄰居之間的松散結(jié)合，這通過我們修改的共振網(wǎng)絡(luò)增強了解碼。這種方法不僅保留了超出簡單邊連接的結(jié)構(gòu)相似性，而且與以前的框架相比，在圖表示中提高了記憶容量和效率。
5. 實驗
在本節(jié)中，我們將展示對CLOG進行的實驗并討論其意義。我們對模型進行了三種類型的實驗。首先，我們從理論上分析CLOG的數(shù)學(xué)屬性，并通過詳細闡述設(shè)計特征來展示其能力。其次，我們展示了CLOG在從編碼圖超向量重建圖方面的有效性。我們通過在各種輸入和模型超參數(shù)設(shè)置下進行重建任務(wù)時測量幾個性能指標來實證評估我們的模型。最后，我們檢驗了模型在知識圖譜鏈接預(yù)測任務(wù)上的能力。我們使用基準數(shù)據(jù)集評估我們的結(jié)果，并將其與幾項關(guān)于該任務(wù)的最新研究進行比較。
5.1. 理論評估
在解釋了CLOG的基本原理之后，我們現(xiàn)在將其與先前基于HDC的圖表示研究進行比較，并通過理論檢驗指出主要區(qū)別。我們使用先前工作中的GrapHD（Poduval等人，2022），并在比較中包括一個中間模型，該模型使用與我們設(shè)計相同的方法，但不使用掩蔽和塊編碼程序。先前的圖表示、沒有塊編碼的CLOG和帶有塊編碼的CLOG分別被索引為1、2、3。圖5展示了模型兩個主要方面的比較，計算復(fù)雜性和內(nèi)存敏感性。
比較每個模型執(zhí)行重建所需的計算量是至關(guān)重要的。所有模型都使用相同的計算順序來編碼圖表示，但三個模型的解碼過程在復(fù)雜性上有所不同，可以量化如下：
假設(shè)模型的超參數(shù)是固定的，圖5(a)展示了使用方程(13)計算的計算復(fù)雜性測量結(jié)果。對于CLOG，其值隨著用于重建的圖的大小在設(shè)定的圖密度值下呈近二次方增加。中間模型也遵循類似的趨勢，直到達到一個點，在增加圖大小時復(fù)雜性無限增長，模型完全無法執(zhí)行任務(wù)。該模型能夠執(zhí)行重建，但對于更大的圖，它產(chǎn)生了虛假的結(jié)果。最后，在類似條件下，GrapHD的復(fù)雜性呈二次方增加，其值比CLOG小一個維度因子。
表示方法的另一個主要屬性是它產(chǎn)生的結(jié)果的質(zhì)量。在基于HDC的模型中，我們可以評估用于表示的超向量的精確度。我們可以通過信號相對于噪聲的敏感度來量化存儲在記憶超向量中的向量的質(zhì)量，正式定義如下：
當通過捆綁進行存儲時，隨著更多超向量被添加，檢測記憶超向量中每個成分的敏感度會降低。關(guān)于上述定義的更詳細解釋可以在Frady等人（2018）中找到。為了量化每種方法的圖表示能力，我們可以計算重建記憶中的敏感度值，這有助于我們展示這些方法在記憶能力和容量方面的差異。
圖5(b)展示了每種方法對于不同圖大小的敏感度值的圖表?？梢钥闯?，GrapHD的敏感度評估最低，CLOG位居第二，而不使用掩蔽的CLOG具有最高的敏感度，僅略高于CLOG。請注意，圖密度在測量過程中被設(shè)定為一個固定值，導(dǎo)致圖中節(jié)點和邊的數(shù)量之間有以下關(guān)系：。
結(jié)合圖5中顯示的兩個評估，可以推斷出在這三個算法中，CLOG是領(lǐng)先的，因為它在敏感度上比先前的工作有明顯的優(yōu)勢，代價是復(fù)雜度略有增加。CLOG還超越了沒有掩蔽的中間設(shè)計，同時保持了高水平的記憶質(zhì)量。不使用掩蔽和塊編碼會導(dǎo)致更大圖的復(fù)雜度無限增長，最終無法為該方法產(chǎn)生可接受的結(jié)果。
考慮到框架的兩個主要屬性，記憶敏感度和計算復(fù)雜度，理論評估展示了CLOG帶來的改進。記憶敏感度是表示方法的一個關(guān)鍵屬性，評估用于表示的超向量的精確度。這通過信號相對于噪聲的敏感度來量化。CLOG顯示出高敏感度，并且在敏感度上比先前的工作有明顯的優(yōu)勢，表明具有優(yōu)越的記憶能力和容量。計算復(fù)雜度對于確定每個模型執(zhí)行其重建所需的計算量至關(guān)重要，CLOG有效地管理了復(fù)雜度和質(zhì)量之間的權(quán)衡，與以前的框架相比，保持了合理的計算量。
對CLOG的理論評估通過關(guān)注兩個關(guān)鍵方面：記憶敏感度和計算復(fù)雜度，展示了該框架相對于先前工作的改進。記憶敏感度衡量超向量在表示中的準確性，CLOG顯示出增強的敏感度和與先前方法相比更優(yōu)越的記憶能力。同時，計算復(fù)雜度，即衡量模型重建所需的計算工作量，CLOG有效地進行了平衡。它避免了過度計算需求的陷阱，確保其與早期框架相比保持相似的計算量級。
此外，掩蔽和塊編碼的調(diào)整被證明是非常有益的，這在與沒有掩蔽的中間方法的比較中得到了證明。缺少這些修改會導(dǎo)致更大圖的復(fù)雜度無限增長，而CLOG有效地處理了這一點，同時沒有犧牲記憶質(zhì)量。
5.2. 圖重建實驗
除了前文提到的理論評估之外，我們還進行了許多實驗來評估我們的模型。在處理圖重建任務(wù)時，可以將CLOG視為一個分類器。每個圖包含若干條邊，這些邊可以被標記為“1”或“存在的邊”，而與相同大小的完整圖相比缺失的邊可以被標記為“0”或“不存在的邊”。因此，圖重建任務(wù)的目標可以表述為對圖中的邊進行分類。這使我們能夠使用分類性能測量來評估CLOG。
我們首先展示并討論我們設(shè)計的接收者操作特征（ROC）曲線，該曲線顯示了分類器的診斷能力，隨著決策閾值的變化而變化。圖6展示了從模型在不同類型的圖上的性能生成的一系列ROC曲線。我們可以觀察到，這些曲線并不像通常的ROC曲線那樣從(0, 0)開始，到(1, 1)結(jié)束，因為CLOG中使用的決策閾值與大多數(shù)分類器不同；它影響分類過程的多個階段（例如，在分解節(jié)點記憶時檢查超向量相似性），而不僅僅是最后階段。盡管存在這種差異，這些曲線還是展示了我們的模型對不同組圖的能力，在ROC空間中接近左上角，即完美分類。如圖6(a)所示，隨著最大度數(shù)的增加，我們模型的性能略有下降，但它仍然保持了令人滿意的邊分類準確性水平。圖6(b)還展示了圖的大小對我們模型分類性能的影響，其中度數(shù)參數(shù)是固定的。盡管隨著圖的大小增加曲線有所下降，但模型的表現(xiàn)仍然相當令人滿意。
圖7展示了CLOG在進行重建任務(wù)時，在不同維度和圖大小下的分類性能指標。請注意，我們使用平衡準確率而不是準確率作為模型的整體性能指標，因為對于不平衡的數(shù)據(jù)集，如稀疏圖，準確率可能是一個具有誤導(dǎo)性的指標。
實驗是在具有固定平均度和最大度值的圖上進行的，并且編碼超參數(shù)也保持不變。結(jié)果表明了我們模型的有效性。分析模型在超參數(shù)變化下的行為同樣非常重要。CLOG在處理超維向量時使用三個主要參數(shù)：維度、塊的數(shù)量和密度。圖8描繪了我們設(shè)計關(guān)于其超參數(shù)的評估。在每個圖中，一個超參數(shù)保持不變，而其他兩個則在幾個值中變化。結(jié)果表明，當超向量密度和塊的數(shù)量在其各自范圍內(nèi)設(shè)置得相對較高或較低時，準確率值會下降。此外，增加維度可以改善重建結(jié)果。然而，這并不總是有益的，因為當處理更大的超向量時，它要求模型執(zhí)行更復(fù)雜的計算。
5.3. 鏈接預(yù)測任務(wù)
類似于GNN，CLOG也可以用于表示知識圖譜的結(jié)構(gòu)信息以進行鏈接預(yù)測。我們用于此任務(wù)的總體架構(gòu)如圖9所示，并由Schlichtkrull等人（2018）使用，將CLOG作為前端編碼器來獲取圖結(jié)構(gòu)信息，并使用評分函數(shù)（DistMult (Yang等人，2014)）作為解碼器來預(yù)測缺失的實體。鑒于HDC的固有符號屬性，我們僅更新實體和關(guān)系嵌入向量，并在訓(xùn)練過程中保持編碼基礎(chǔ)超向量不變。
如表1所示，我們使用FB15k-237（Toutanova & Chen，2015）和WN18RR（Dettmers等人，2018）作為基準數(shù)據(jù)集來評估鏈接預(yù)測性能。原始嵌入向量和編碼超向量的維度分別設(shè)置為400字節(jié)和2000字節(jié)。表2表明，與以前的知識圖譜表示模型相比，CLOG實現(xiàn)了出色的鏈接預(yù)測準確性。對于FB15K-237，CLOG實現(xiàn)了平均倒數(shù)排名（MRR）0.356，Hits@10 0.526，Hits@3 0.393和Hits@1 0.269。在WN18RR數(shù)據(jù)集上，CLOG記錄了MRR 0.465，Hits@10 0.521，Hits@3 0.487和Hits@1 0.444。更具體地說，與以前的基于GNN的模型R-GCN（Schlichtkrull等人，2018）相比，CLOG在平均倒數(shù)排名（MRR）上平均提高了約26.7%。值得注意的是，它取得了與先進的基于GNN的模型CompGCN（Schlichtkrull等人，2018）和幾個領(lǐng)先的基于嵌入的模型（如InteractE（Vashishth等人，2020）和RotatE（Sun等人，2019））相當?shù)母偁幜Y(jié)果，并在多個指標上超越了它們。與其他模型相比，CLOG在FB15k-237上表現(xiàn)出優(yōu)越的性能，而在WN18RR上，CLOG與其他模型具有競爭力，Hits@1上超越了它們。這種差異可以歸因于數(shù)據(jù)集屬性，其中FB15k-237具有比WN18RR多20倍以上的關(guān)系和每個關(guān)系大約7倍少的樣本。這些進展表明，CLOG在捕獲圖內(nèi)結(jié)構(gòu)關(guān)系方面的新方法及其高效的編碼和解碼過程有助于提高其在預(yù)測知識圖譜內(nèi)鏈接方面的性能。
6 結(jié)論
在這項研究中，我們介紹了CLOG，這是一種創(chuàng)新的基于超維計算（HDC）的圖表示方法。CLOG利用HDC的變量綁定操作符來捕捉圖節(jié)點之間的結(jié)構(gòu)關(guān)系。我們的方法結(jié)合了塊編碼和掩蔽技術(shù)，能夠更有效地將原子概念（例如圖節(jié)點）投影到高超維空間。這導(dǎo)致了鄰居之間更松散的結(jié)合，從而促進了改進的解碼。CLOG的有效性已通過理論和實證實驗得到驗證，并通過與其他方法在基準鏈接預(yù)測數(shù)據(jù)集上的比較得到進一步證明。
展望未來，有幾個有前景的研究方向可以進一步研究。未來的工作可以探索CLOG編碼的改進，更具體地說是解碼過程的改進，將模型應(yīng)用于更多樣化和復(fù)雜的圖類型，以及將CLOG與其他機器學(xué)習(xí)框架集成以增強其適用性和性能。該框架在基于圖的知識表示和推理領(lǐng)域做出重大貢獻的潛力很大，預(yù)計在這一領(lǐng)域的持續(xù)探索將產(chǎn)生寶貴的見解和進步。
原文鏈接：https://www.sciencedirect.com/science/article/pii/S2667305324000292
熱門跟貼