https://www.sciencedirect.com/science/article/pii/S2667305324000292

Conjunctive block coding for hyperdimensional graph representation

用于超維圖表示的合取塊編碼

摘要

知識圖譜（KGs）已經成為機器學習中一個關鍵的知識表示工具，不僅提供了獲取現有知識的方式，還通過高級應用使得新知識的發現成為可能。在這些應用中使用的可擴展推理方法中，分布式圖嵌入方法，特別是圖神經網絡（GNNs），已經因為大規模圖相關任務而變得流行。然而，這些方法中的許多在可解釋性方面存在局限性，并且未能在其表示中考慮結構相似性。超維計算（HDC），也被稱為向量符號架構（VSA），通過在符號概念的分布式表示上使用定義良好的認知操作來解決這一問題。本文提出了一種新的向量符號圖表示方法CLOG，它保留了超出邊對應關系的近似結構相似性，并與以前的方法有根本的不同。通過理論分析、圖重建實驗和鏈接預測任務評估了該模型在圖表示中的有效性，突出了其效率和準確性。這種方法通過增強HDC在圖表示中的能力，顯著推進了該領域的發展，代表了對現有方法的顯著改進。

關鍵詞：超維計算 向量符號架構 圖表示 認知計算

1. 引言

知識圖譜（KG）作為一種知識表示類型，在機器學習社區中引起了特別的興趣。知識圖譜是由實體作為節點、關系作為邊構成的多關系有向圖。它收集并組織關于實體的關系和屬性，在許多應用中扮演著越來越重要的角色，包括問答和信息檢索。除了從知識圖譜中檢索現有信息外，像鏈接預測和知識圖譜補全這樣的高級應用還能夠在圖譜內發現新的和隱藏的知識（Chen等，2020）。

像Freebase（Bollacker等，2008）、WordNet（Fellbaum，2010）和GeneOntology（Ashburner等，2000）這樣的大規模知識圖譜對于包括網絡/移動搜索和問答在內的AI應用至關重要。傳統的形式邏輯推理在這些廣泛的圖譜中進行長距離推理時存在困難（Zamini等，2022）。現在更傾向于使用分布式圖嵌入等可擴展方法來處理大規模任務，為高效的圖算法執行提供低維空間表示。圖神經網絡（GNNs）因其在圖相關問題中的有效性而越來越受歡迎（Arora，2020；Cheng等，2022；Park等，2019）。然而，GNNs通常需要大量的標記數據才能達到最佳性能，知識圖譜的長尾特性，即許多關系只在少數三元組中出現（Zhang等，2022），給純粹的數據驅動方法帶來了挑戰。

知識圖譜嵌入方法面臨兩個主要限制。首先，它們將符號化的邏輯知識圖譜轉換為連續表示，而不保留實體和關系完整性，限制了基于梯度的方法只能進行事后解釋（Hersche等，2023）。其次，正如Zamini等（2022）所強調的，許多方法在捕捉多步關系和利用結構相似性進行鏈接預測和圖譜補全方面存在困難。雖然圖神經網絡（GNNs）使用網絡架構來隱式地解決這些問題，但組成（實體、關系）相似性和結構相似性之間的重疊常常使得預測的驅動因素變得不明確。組成相似性主要源于元素的內在屬性，而結構相似性則是從它與其他元素的關系中派生出來的。

為了激發結構相似性和組成相似性的解耦，我們轉向類比推理的研究，這是一種在人類認知中普遍存在的形式，旨在識別兩種情況之間的共同關系系統，并從它們的共同點中推斷（Gentner & Smith，2013）。作為一種在兩組實體及其關系之間的結構相似性上嚴重依賴的方法，它既提供了洞察力，也引入了潛在的謬誤。除了引用諺語來突出常見情況中的模式外，人們還利用類比推理在已知系統和未知系統之間建立聯系，以促進理解和假設生成（Gentner & Smith，2013），而有時由于實體和關系的表面匹配，類比可能會產生事實上不正確的推斷。通過區分這兩種相似性，我們可能在模型使用它們時提供更好的控制。

超維計算（HDC），也稱為向量符號架構（VSA），通過在符號概念的分布式表示上執行定義明確的認知操作來解決可解釋性和類比相似性的問題。HDC的設計確保了超維向量（超向量）內符號概念的完整性，從而實現了可解釋性。這些表示允許在圖的大小在超向量的記憶容量內時恢復圖的節點和邊。此外，由于圖由單個超向量表示，圖超向量的點積反映了它們之間的某些全局相似性。雖然存在各種圖表示算法（Gayler & Levy，2009；Nunes等，2022；Poduval等，2022），但它們都會產生基于邊匹配來確定結構相似性的圖超向量，由于超向量的記憶容量而面臨可擴展性限制。

本工作旨在提出并評估一種新的向量符號圖表示方法，該方法保留了超出邊對應關系的近似結構相似性。我們介紹了CLOG：用于超維圖表示的聯合塊編碼，這是一種與以前方法根本不同的方法。我們的貢獻包括：

? 一種新的超維圖表示方法，利用HDC的變量綁定操作符來保留每個節點到鄰居的聯合連接。直接的結果是增加了超向量對稀疏圖的記憶容量。

? 一種塊編碼和掩蔽方案，用于將原子概念（在這種情況下是圖節點）投影到超維空間，從而實現鄰居的松散聯合，使得表示的解碼更加高效。

? 由于CLOG與GNN采取的方法正交，我們提出了CLOG與GNN的集成。為了展示CLOG在知識圖譜結構表示方面的能力，我們還在基準鏈接預測數據集上測試了我們的模型，并將其與現有方法進行了比較。

接下來的部分涵蓋了該領域的相關文獻。第3節討論了超維計算的基本原理和現有的HDC圖表示。第4節介紹了所提出方法及其組成部分的細節。第5節提供了CLOG的實驗和評估及其在各種任務中的性能。

2. 相關工作

2.1 圖表示

圖表示方法是計算機科學中一個關鍵的研究領域，特別是在數據科學、機器學習和網絡分析領域。這些方法旨在有效且高效地表示圖結構數據，由于其非歐幾里得特性，這種數據本質上是復雜的。

Perozzi等人（2014）的開創性工作標志著一個基礎性的轉變，通過將自然語言處理技術應用于圖數據，使用截斷的隨機游走來學習社交表示。Grover和Leskovec（2016）進一步改進了這一概念，增強了模型捕捉局部和全局網絡結構的靈活性。基于這些嵌入，圖神經網絡（GNNs）領域出現了，關鍵貢獻如Kipf和Welling（2016），將深度學習擴展到圖結構數據。Velickovic等人（2017）引入的圖注意力網絡（GATs）增加了基于注意力的機制，允許對節點重要性進行更細致的評估。Dwivedi和Bresson（2020）進一步復雜化了這一領域，將最初為自然語言處理中的序列數據設計的變換器架構擴展到處理圖結構數據。當前研究正專注于增強這些方法的可擴展性（Huang, Li, Cao等人，2022；Li等人，2023；Rampá?ek等人，2022；Thakoor等人，2021）、可解釋性（Chen, Jiao, Liu等人，2022；Feng等人，2022；Huang, Yamada, Tian等人，2022；Wu等人，2023）和泛化能力，解決圖結構數據在現實世界中的復雜性（Gao等人，2023；Li, Zheng, Feng等人，2023；Li, Zhang, Cui等人，2023；Liu等人，2023；Wang等人，2022）。

2.2 超維計算

超維計算的基本概念已經建立相當長一段時間，但直到最近幾年，它們在理論和實踐中才開始獲得顯著的關注。關鍵的理論發展（Clarkson等人，2023；Frady等人，2018）吸引了更廣泛的機器學習社區的注意，導致了廣泛的實際部署，包括健康監測（Ge & Parhi，2022；Moin等人，2021；Ni, Lesica, Zeng等人，2022）、強化學習（Chen, Issa, Ni等人，2022；Ni等人，2022）和輕量級識別算法（Imani等人，2022；Lee等人，2023）。這種日益增長的興趣可以歸因于HDC能力解決當代人工神經網絡中發現的一些缺點的方式，包括更高的學習效率（Hersche等人，2022；Ni等人，2024）、更好的可解釋性（Poduval等人，2022）以及在硬件平臺上的自然并行性（Chen等人，2024）。因此，出現了一種將神經符號方法合并的混合模型的新興趨勢（Hersche等人，2023；Lee等人，2023；Zou等人，2022）。

特別地，HDC在圖表示學習領域顯示出與圖卷積神經網絡（GCN）競爭的巨大潛力（Poduval等人，2022）。雖然HDC圖表示與GNNs在處理圖數據時的聚合階段有一些相似之處，但其方法和目標有顯著不同。GNNs在學習任務中表現出色，但在高級推理和知識提取方面缺乏能力，因為神經網絡通常專注于學習而非記憶。相比之下，超維學習使用符號超向量，模仿強大的類腦推理，并消除了在多個層中進行迭代節點聚合的需要（Chen等人，2023；Kang等人，2022；Nunes等人，2022；Poduval等人，2022）。

3 預備知識

3.1. 超維計算

超維計算（HDC），也稱為向量符號架構（VSA）（Gayler，1998；Kanerva，1996；Plate等人，1991），具有將數據結構操作成分布式表示的能力。HDC在超維向量空間中全息地編碼數據結構，其中隨機超向量，即超維向量，被用作表示的基礎，并且采用三種主要操作在超維空間上形成代數。

在這項研究中，使用獨立的隨機雙極向量作為原子原語，其維度為。向量之間的相似性通過它們的點積來衡量，，從1到的求和，這表明原子對象是否相同以及復雜對象之間的結構相似性。為了構建結構化對象，定義了以下三種HDC操作：

捆綁（+）操作是通過超向量的逐元素相加完成的，表示為 = 1 +2。這個操作疊加元素，充當記憶功能，將輸入數據的信息保留結果在向量中。捆綁的超向量與其原子超向量保持相似性，即?,? ? 0；因此，它非常適合表示集合。這種相似性意味著即使來自多個向量的信息被組合，各個向量的本質也不會丟失，這有助于在HDC框架內進行聯想記憶檢索。

綁定（⊙）1和2是通過兩個超向量之間的Hadamard積，即逐元素相乘來，完成的，表示為 = 1 ⊙ 2。結果的合取超向量與其組成的向量不同，?,1? ≈ 0。這個操作是可逆的，即1 = ⊙ 。由于綁定在某種意義上保持了其成分的信息而不增加大小，它可以作為變量關聯。這種可逆性允許檢索原始信息，使綁定成為HDC中編碼復雜關系的強大工具。

排列（）操作， = ()，對的組件應用循環移位。排列在捆綁上分配，( + 2) = (1) + (2)，以及綁定，(1 ⊙ 2) = (1) ⊙ (2)。像綁定一樣，排列使超向量分離，當 ≠ 0時，?(),? ≈ 0。由于排列是可逆的，并且通過對超向量的重復排列引入自然順序，它被用來表示序列和為不同層級的層次結構編碼順序。

3.2. HDC中的圖表示

盡管算法和節點排序存在一些差異，現有的HDC圖表示主要利用邊對應作為結構相似性的度量（Gayler & Levy，2009；Nunes等人，2022；Poduval等人，2022）。對于一個無向圖 = (, )，該框架首先為圖中的每個節點 ∈ 分配一個大小為的隨機雙極超向量，并生成大小為 × 的碼本矩陣 = [1, 2, ..., ]，作為圖節點的超維表示。由于是隨機生成的，節點超向量幾乎正交，每對超向量之間的相似性大約為零：?, ? ≈ 0, ≠ 。

對于每個節點，基于HDC的模型通過其鄰居集合創建一個節點記憶超向量： = ∑( ∈ ?()) 。捆綁操作的性質意味著節點記憶與每個捆綁超向量之間的相似性遠大于零：? ∈ ?(), ?, ? ? 0。這個性質允許在重建過程中通過相似性檢查檢索每個鄰居。

然后，模型分兩步為整個圖構建一個單一的超向量。首先，它將每個節點超向量與其對應的節點記憶關聯（綁定）， ⊙ 。這增加了節點記憶之間的區別，并允許模型在圖重建期間識別每個節點的正確記憶。然后，所有關聯的對被捆綁在一起形成圖超向量：

最后的等式利用了綁定操作在捆綁操作上的分配性。結果是一個透明的模型，它壓縮了圖中所有的邊，每條邊都由端點超向量的綁定來表示。它可以用來重建原始圖或在其上執行推理任務。

要從圖超向量中檢索圖信息，基于HDC的表示框架首先恢復每個節點的記憶，這可以通過將圖超向量與相應的節點超向量綁定來大致完成：

獲得的節點記憶記為，與原始節點記憶超向量不同，因為它包含了額外的成分。在解碼過程的后續和最后階段，由于超向量的正交性，這些多余的成分被消除了。

在估計了節點記憶之后，我們可以通過測量一個節點的超向量與另一個節點記憶超向量之間的相似性，，來檢查節點和之間的連接。如果和之間存在邊，那么否則，

4. 主要貢獻

本節介紹了我們提出的方法，用于在超維空間中表示圖的結構。如第3節所述，采用超維數學將圖信息分布到一個完全整體的超維表示中。我們引入了CLOG，它采用了獨特的兩階段塊編碼和一種創新的解碼算法。本節將深入討論這個設計的細節。

4.1. 共振網絡

如第3.2節所討論的，以前基于HDC的圖表示工作主要利用捆綁操作及其特性將節點連接聚合到記憶超向量中。使用捆綁來記憶超向量限制了模型的可擴展性，因為結果記憶超向量的大小將遠大于其原子成分，這導致記憶最終飽和。這種飽和可以在解碼過程變得更加困難時觀察到，并且在嘗試確定記憶與其成分之間的相似性時，噪聲項的數量增加。

為了克服這一點，可以通過綁定超向量來執行記憶，消除上述缺點。然而，當從合取超向量中解碼信息時，這種方法可能具有挑戰性。

雖然綁定操作在已知除一個以外的所有成分時是可逆的，但從給定的綁定超向量中找到所有成分向量并不簡單。一般來說，這個因式分解問題可能涉及兩個或更多的因子，導致潛在解空間的指數增長。假設我們給定一個復合向量，它是個向量的乘積：

由Frady等人（2020）提出的共振網絡，Kent等人在2020年進一步利用，并在多種應用中使用（Frady等人，2022；Renner等人，2022），試圖在不通過窮舉搜索因子的所有可能組合的情況下解決這個問題，如圖1所示。該算法通過在每個相應碼本中的所有向量上使用疊加來初始化每個因子的猜測，然后迭代地改進這些猜測，并從上一次迭代中推斷出新的估計值。

通過反復執行指定的操作，共振網絡可以生成改進的估計，同時降低猜測中的噪聲水平，直到模型達到收斂并發現解決方案。

4.2. 塊編碼和掩蔽

盡管共振網絡是一種分解復合超向量的出色且有效的方法，但它存在可擴展性問題。圖2展示了隨著搜索空間大小（即可能因子組合的數量）的變化，該方法的準確性和迭代次數的變化。很明顯，網絡的準確性只能在搜索空間大小的非常小的范圍內保持，這限制了我們案例中輸入圖的大小和密度，因為我們在設計中稍后使用該方法。同樣明顯的是，對更大圖的嘗試導致算法無法達到收斂，導致準確性下降。進一步增加搜索空間也會導致虛假點和最終準確性降低。

為了解決可擴展性問題，我們提出了一種基礎編碼方法的配置，它允許共振網絡在更平滑的搜索空間中工作，從而實現更高效的解碼。我們還相應地改變了共振網絡的更新規則，這顯著減少了網絡收斂所需的迭代次數。

我們不是為每個節點生成一個隨機超向量，而是將每個節點超向量分成多個塊，只隨機生成其中的一部分，留下其他塊作為所有分量都設為1的向量。我們定義密度為隨機塊數與總塊數的比例：

圖3(a)中可以看到這樣的掩蔽示例。

現在假設我們正在處理一個因子分解問題，其中的超向量具有掩蔽塊。共振網絡能夠在其搜索空間中更平滑地更新其猜測，因為之前正交的超向量現在它們之間有了相關性。

此外，可以觀察到，通過在隨機生成的塊之間添加單位塊，最終復合超向量中的每個塊在創建時涉及的因子數量會減少，圖3(b)提供了一個示例。我們可以利用合取向量這一新特性，通過改變共振網絡的更新規則并包括新的終止規則，從而提高其收斂速度。

我們為共振網絡提出了以下新的更新規則：

當所有因子都達到收斂時，即進一步迭代不會對猜測產生任何變化時，共振網絡終止其迭代。相同的標準也適用于我們提出的設計，但使用掩碼和塊超向量可以在這里帶來顯著的優勢。通過將超向量分割成塊，并相應地更新共振網絡，可以添加新標準以確保各個塊的收斂。

假設共振網絡正在進行第次迭代，目前持有構建復合超向量的因子的猜測?。我們可以將與從綁定所有當前猜測得到的超向量?進行比較。如果兩個提到的向量之間的相似性很高，即?, ?? ? 0，我們可以得出結論，猜測已經收斂到它們各自的碼本條目。假設超向量像之前描述的那樣被分割成塊，可以獨立于其他塊檢查每個塊的上述標準。同時考慮到掩碼，可以看出，一些塊可能包含作為它們因子的掩碼塊。如果對這種情況使用1掩碼，它們可以作為因子被忽略，因為它們在綁定中充當單位元素，這意味著各個塊可能使用比完整超向量更少的因子構建。這可以顯著加快檢測收斂的過程；如果單個超向量塊滿足收斂標準，它們可以被檢查并暗示完整超向量的因子。

4.3. 基于HDC的圖表示CLOG

我們現在提出我們的新穎圖記憶和學習方案，CLOG。我們將設計分為兩部分，首先詳細解釋編碼過程，然后繼續解碼過程。圖4展示了設計的高級視圖。

4.3.1. 編碼

在新方法CLOG中，我們使用兩步編碼，減少了捆綁在一起的項的數量，使模型能夠更好地適應圖的大小和密度。這增加了超向量的記憶容量，解決了以前方法中存在的可擴展性問題。首先，我們為每個節點生成一個維度為的隨機超向量。使用固定數量的塊，我們還對每個節點超向量應用密度為的隨機掩碼，得到。

生成了表示每個節點所需的向量后，圖編碼現在可以分為兩個級別的記憶。對于第一級別，CLOG在本地捕獲節點信息，將每個節點的所有鄰居關聯在一起，形成一個單一的節點記憶超向量：

其中是完整節點超向量的掩蔽版本，即 = []，是基礎節點記憶，它也是一個掩蔽超向量。（注意，如果節點沒有任何鄰居，則 = 。）為了避免為每個節點生成更多的超向量，我們可以將掩蔽節點超向量分配為其相應的基礎節點記憶， = ，假設圖中不包含任何自環。

在第一步中利用HDC的變量綁定操作符允許CLOG為每個節點保留與鄰居的合取連接，這與之前主要關注邊對應的方法相比，表現出根本性的轉變。

對于第二級編碼，所有在節點記憶中收集的信息都被捆綁在一起，形成最終的圖超向量：

其中是完整的節點超向量，并且對節點記憶也應用了排列，以完全分離兩個編碼級別。值得一提的是，排列的數量等于超向量塊的長度，這確保了不同塊的內容不會混合在一起。

4.3.2. 解碼

重建過程可以分為兩個步驟。首先，從圖超向量中檢索每個節點的節點記憶的估計值：

請注意，我們在這里也使用超向量塊的長度作為排列的大小，本質上是將塊向后移動一個位置。計算結果記為?，這與原始節點記憶不同，可能包含噪聲項。在下一步中，CLOG需要從其節點記憶超向量中識別每個節點的鄰居。由于模型通過綁定創建節點記憶，因此可以使用共振網絡將生成的綁定超向量分解為其成分，共振網絡提供了一種高效的超向量分解機制，如第4.1節所討論的。我們還對共振網絡應用了第4.2節中討論的修改，遵循編碼步驟中使用的塊編碼和掩蔽，以增加方法的效率和可擴展性。這里我們將使用以下等式：

該公式將所有先前的因子猜測與基礎向量和復合向量（即檢索到的節點記憶）相關聯，然后計算碼本條目的加權線性組合，作為當前因子的新猜測。同時請注意，構建每個節點記憶所使用的因子數量假定為，即最大節點度。

共振網絡將更新其對因子的猜測，從第一個因子迭代到最后一個，然后再回到第一個進行新的猜測。迭代將在所有因子達到穩定點時結束，即每個因子的新猜測與前一次迭代保持不變。為了使CLOG獲取所有節點的鄰居，從而重建完整圖，這個過程需要對每個節點執行。

通過使用塊編碼和掩蔽，我們能夠修改算法，使其在完整超向量收斂之前就找到因子，同時處理的因子數量也少于。由于塊本質上是相互獨立的，我們每隔幾次迭代就執行一次塊相似性檢查。如果有塊的猜測綁定與合取向量匹配，這意味著這些塊已經收斂。從單個因子開始，即 = 1，算法增加因子數量，同時識別可以用較少因子構建的塊，從而實現更快的收斂。這是掩蔽方法的直接結果；一些塊可能包含多個掩蔽因子，這有助于共振網絡用更少的因子和搜索空間大小識別和分解它們。

與以前的模型相比，CLOG在超維計算的圖表示方面引入了重大進步。與主要關注邊對應的早期模型不同，該框架使用綁定操作作為連接相鄰節點的手段，并結合了獨特的塊編碼和掩蔽方案，確保了鄰居之間的松散結合，這通過我們修改的共振網絡增強了解碼。這種方法不僅保留了超出簡單邊連接的結構相似性，而且與以前的框架相比，在圖表示中提高了記憶容量和效率。

5. 實驗

在本節中，我們將展示對CLOG進行的實驗并討論其意義。我們對模型進行了三種類型的實驗。首先，我們從理論上分析CLOG的數學屬性，并通過詳細闡述設計特征來展示其能力。其次，我們展示了CLOG在從編碼圖超向量重建圖方面的有效性。我們通過在各種輸入和模型超參數設置下進行重建任務時測量幾個性能指標來實證評估我們的模型。最后，我們檢驗了模型在知識圖譜鏈接預測任務上的能力。我們使用基準數據集評估我們的結果，并將其與幾項關于該任務的最新研究進行比較。

5.1. 理論評估

在解釋了CLOG的基本原理之后，我們現在將其與先前基于HDC的圖表示研究進行比較，并通過理論檢驗指出主要區別。我們使用先前工作中的GrapHD（Poduval等人，2022），并在比較中包括一個中間模型，該模型使用與我們設計相同的方法，但不使用掩蔽和塊編碼程序。先前的圖表示、沒有塊編碼的CLOG和帶有塊編碼的CLOG分別被索引為1、2、3。圖5展示了模型兩個主要方面的比較，計算復雜性和內存敏感性。

比較每個模型執行重建所需的計算量是至關重要的。所有模型都使用相同的計算順序來編碼圖表示，但三個模型的解碼過程在復雜性上有所不同，可以量化如下：

假設模型的超參數是固定的，圖5(a)展示了使用方程(13)計算的計算復雜性測量結果。對于CLOG，其值隨著用于重建的圖的大小在設定的圖密度值下呈近二次方增加。中間模型也遵循類似的趨勢，直到達到一個點，在增加圖大小時復雜性無限增長，模型完全無法執行任務。該模型能夠執行重建，但對于更大的圖，它產生了虛假的結果。最后，在類似條件下，GrapHD的復雜性呈二次方增加，其值比CLOG小一個維度因子。

表示方法的另一個主要屬性是它產生的結果的質量。在基于HDC的模型中，我們可以評估用于表示的超向量的精確度。我們可以通過信號相對于噪聲的敏感度來量化存儲在記憶超向量中的向量的質量，正式定義如下：

當通過捆綁進行存儲時，隨著更多超向量被添加，檢測記憶超向量中每個成分的敏感度會降低。關于上述定義的更詳細解釋可以在Frady等人（2018）中找到。為了量化每種方法的圖表示能力，我們可以計算重建記憶中的敏感度值，這有助于我們展示這些方法在記憶能力和容量方面的差異。

圖5(b)展示了每種方法對于不同圖大小的敏感度值的圖表。可以看出，GrapHD的敏感度評估最低，CLOG位居第二，而不使用掩蔽的CLOG具有最高的敏感度，僅略高于CLOG。請注意，圖密度在測量過程中被設定為一個固定值，導致圖中節點和邊的數量之間有以下關系：。

結合圖5中顯示的兩個評估，可以推斷出在這三個算法中，CLOG是領先的，因為它在敏感度上比先前的工作有明顯的優勢，代價是復雜度略有增加。CLOG還超越了沒有掩蔽的中間設計，同時保持了高水平的記憶質量。不使用掩蔽和塊編碼會導致更大圖的復雜度無限增長，最終無法為該方法產生可接受的結果。

考慮到框架的兩個主要屬性，記憶敏感度和計算復雜度，理論評估展示了CLOG帶來的改進。記憶敏感度是表示方法的一個關鍵屬性，評估用于表示的超向量的精確度。這通過信號相對于噪聲的敏感度來量化。CLOG顯示出高敏感度，并且在敏感度上比先前的工作有明顯的優勢，表明具有優越的記憶能力和容量。計算復雜度對于確定每個模型執行其重建所需的計算量至關重要，CLOG有效地管理了復雜度和質量之間的權衡，與以前的框架相比，保持了合理的計算量。

對CLOG的理論評估通過關注兩個關鍵方面：記憶敏感度和計算復雜度，展示了該框架相對于先前工作的改進。記憶敏感度衡量超向量在表示中的準確性，CLOG顯示出增強的敏感度和與先前方法相比更優越的記憶能力。同時，計算復雜度，即衡量模型重建所需的計算工作量，CLOG有效地進行了平衡。它避免了過度計算需求的陷阱，確保其與早期框架相比保持相似的計算量級。

此外，掩蔽和塊編碼的調整被證明是非常有益的，這在與沒有掩蔽的中間方法的比較中得到了證明。缺少這些修改會導致更大圖的復雜度無限增長，而CLOG有效地處理了這一點，同時沒有犧牲記憶質量。

5.2. 圖重建實驗

除了前文提到的理論評估之外，我們還進行了許多實驗來評估我們的模型。在處理圖重建任務時，可以將CLOG視為一個分類器。每個圖包含若干條邊，這些邊可以被標記為“1”或“存在的邊”，而與相同大小的完整圖相比缺失的邊可以被標記為“0”或“不存在的邊”。因此，圖重建任務的目標可以表述為對圖中的邊進行分類。這使我們能夠使用分類性能測量來評估CLOG。

我們首先展示并討論我們設計的接收者操作特征（ROC）曲線，該曲線顯示了分類器的診斷能力，隨著決策閾值的變化而變化。圖6展示了從模型在不同類型的圖上的性能生成的一系列ROC曲線。我們可以觀察到，這些曲線并不像通常的ROC曲線那樣從(0, 0)開始，到(1, 1)結束，因為CLOG中使用的決策閾值與大多數分類器不同；它影響分類過程的多個階段（例如，在分解節點記憶時檢查超向量相似性），而不僅僅是最后階段。盡管存在這種差異，這些曲線還是展示了我們的模型對不同組圖的能力，在ROC空間中接近左上角，即完美分類。如圖6(a)所示，隨著最大度數的增加，我們模型的性能略有下降，但它仍然保持了令人滿意的邊分類準確性水平。圖6(b)還展示了圖的大小對我們模型分類性能的影響，其中度數參數是固定的。盡管隨著圖的大小增加曲線有所下降，但模型的表現仍然相當令人滿意。

圖7展示了CLOG在進行重建任務時，在不同維度和圖大小下的分類性能指標。請注意，我們使用平衡準確率而不是準確率作為模型的整體性能指標，因為對于不平衡的數據集，如稀疏圖，準確率可能是一個具有誤導性的指標。

實驗是在具有固定平均度和最大度值的圖上進行的，并且編碼超參數也保持不變。結果表明了我們模型的有效性。分析模型在超參數變化下的行為同樣非常重要。CLOG在處理超維向量時使用三個主要參數：維度、塊的數量和密度。圖8描繪了我們設計關于其超參數的評估。在每個圖中，一個超參數保持不變，而其他兩個則在幾個值中變化。結果表明，當超向量密度和塊的數量在其各自范圍內設置得相對較高或較低時，準確率值會下降。此外，增加維度可以改善重建結果。然而，這并不總是有益的，因為當處理更大的超向量時，它要求模型執行更復雜的計算。

5.3. 鏈接預測任務

類似于GNN，CLOG也可以用于表示知識圖譜的結構信息以進行鏈接預測。我們用于此任務的總體架構如圖9所示，并由Schlichtkrull等人（2018）使用，將CLOG作為前端編碼器來獲取圖結構信息，并使用評分函數（DistMult (Yang等人，2014)）作為解碼器來預測缺失的實體。鑒于HDC的固有符號屬性，我們僅更新實體和關系嵌入向量，并在訓練過程中保持編碼基礎超向量不變。

如表1所示，我們使用FB15k-237（Toutanova & Chen，2015）和WN18RR（Dettmers等人，2018）作為基準數據集來評估鏈接預測性能。原始嵌入向量和編碼超向量的維度分別設置為400字節和2000字節。表2表明，與以前的知識圖譜表示模型相比，CLOG實現了出色的鏈接預測準確性。對于FB15K-237，CLOG實現了平均倒數排名（MRR）0.356，Hits@10 0.526，Hits@3 0.393和Hits@1 0.269。在WN18RR數據集上，CLOG記錄了MRR 0.465，Hits@10 0.521，Hits@3 0.487和Hits@1 0.444。更具體地說，與以前的基于GNN的模型R-GCN（Schlichtkrull等人，2018）相比，CLOG在平均倒數排名（MRR）上平均提高了約26.7%。值得注意的是，它取得了與先進的基于GNN的模型CompGCN（Schlichtkrull等人，2018）和幾個領先的基于嵌入的模型（如InteractE（Vashishth等人，2020）和RotatE（Sun等人，2019））相當的競爭力結果，并在多個指標上超越了它們。與其他模型相比，CLOG在FB15k-237上表現出優越的性能，而在WN18RR上，CLOG與其他模型具有競爭力，Hits@1上超越了它們。這種差異可以歸因于數據集屬性，其中FB15k-237具有比WN18RR多20倍以上的關系和每個關系大約7倍少的樣本。這些進展表明，CLOG在捕獲圖內結構關系方面的新方法及其高效的編碼和解碼過程有助于提高其在預測知識圖譜內鏈接方面的性能。

6 結論

在這項研究中，我們介紹了CLOG，這是一種創新的基于超維計算（HDC）的圖表示方法。CLOG利用HDC的變量綁定操作符來捕捉圖節點之間的結構關系。我們的方法結合了塊編碼和掩蔽技術，能夠更有效地將原子概念（例如圖節點）投影到高超維空間。這導致了鄰居之間更松散的結合，從而促進了改進的解碼。CLOG的有效性已通過理論和實證實驗得到驗證，并通過與其他方法在基準鏈接預測數據集上的比較得到進一步證明。

展望未來，有幾個有前景的研究方向可以進一步研究。未來的工作可以探索CLOG編碼的改進，更具體地說是解碼過程的改進，將模型應用于更多樣化和復雜的圖類型，以及將CLOG與其他機器學習框架集成以增強其適用性和性能。該框架在基于圖的知識表示和推理領域做出重大貢獻的潛力很大，預計在這一領域的持續探索將產生寶貴的見解和進步。

原文鏈接：https://www.sciencedirect.com/science/article/pii/S2667305324000292