[發明專利]基于節點級嵌入特征三維關系重建的圖數據相似度方法

在審

• 申請號: 202210059012.6
• 申請日: 2022-01-18
• 公開（公告）號: CN114511708A
• 公開（公告）日: 2022-05-17
• 發明（設計）人: 劉博;武嘉慧;王志晗;張冀東
• 申請（專利權）人: 北京工業大學
• 主分類號: G06V10/44
• 分類號: G06V10/44;G06V10/764;G06V10/82;G06V10/74;G06K9/62;G06N3/04;G06N3/08
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 沈波

本發明公開了基于節點級嵌入特征三維關系重建的圖數據相似度方法，屬于深度學習領域，首先通過孿生圖卷積層和相似節點交互模塊生成節點級嵌入特征三維關系，然后將節點級嵌入特征三維關系經過三維卷積提取特征，將三維特征經過Flatten層展開為一維，獲得最終節點級關系向量。這一關系向量輸入到由全連接層構成的結果輸出模塊得到預測輸出。這一預測輸出與實際的標簽值進行比較，通過損失函數和反向傳播算法對整體模型參數進行更新以達到學習的目的。完成訓練的DeepSIM?3D模型能高效可靠地計算輸入的兩個圖結構數據的相似度。

技術領域

本發明屬于深度學習領域，主要用于圖結構數據相似度計算。設計了一種成對節點比較方法，主要用于基于節點級嵌入特征三維關系重建的圖結構數據相似度計算。

背景技術

圖廣泛存在于真實世界的多種場景中，即節點和邊的集合。比如社交網絡中人與人之間的聯系，生物中蛋白質相互作用以及通信網絡中的IP地址之間的通信等等。除此之外，我們最常見的一張圖片、一個句子也可以抽象地看做是一個圖模型的結構，圖結構可以說是無處不在。

圖相似性搜索是最重要的基于圖的應用程序之一，例如查找與化合物最相似的化合物，但比較兩個圖的相似度是一個非常復雜的問題。將神經網絡應用到圖結構數據上，是一類計算圖之間相似度的辦法，減少計算復雜度，同時保持良好的性能。圖結構數據是非歐幾里得數據，難以通過傳統的距離度量直接表示，在圖上直接進行機器學習具有一定的局限性，通常使用圖嵌入來進行圖的表示。圖嵌入是一種將圖數據(通常為高維稠密的矩陣)映射為低微稠密向量的過程。圖嵌入技術大致可以分為兩種：節點嵌入和圖嵌入。當需要對節點進行分類，節點相似度預測，節點分布可視化時一般采用節點的嵌入；當需要在圖級別上進行預測，需要將整個圖表示為一個向量進行嵌入表示。將圖表示為向量后，可以方便的用傳統距離度量方式計算相似度，如馬氏距離。

節點嵌入的目標是優化嵌入空間和節點到該空間的映射邏輯，使網絡中“相似”的節點在嵌入空間中彼此“接近”。早期的節點嵌入算法利用基于隨機行走方法來得到節點在多維空間上的向量表示并以此定義節點之間的“相似性”。隨著深度學習的出現，基于神經網絡的算法，包括圖卷積網絡(Graph Convolution Network)，也被應用到節點嵌入的計算中。

本發明最重要的創新點是提出了一種新的基于節點級嵌入特征的圖結構數據相似度模型。本模型使用圖卷積網絡(GCN)結合孿生結構(Siamese Architecture)進行特征提取，即：生成成對的圖結構數據嵌入。孿生圖卷積神經網絡通過在雙分支結構的兩個圖卷積神經網絡模塊之間共享權值的方式，實現孿生結構。基于深度學習的圖相似度計算本質上是衡量兩個圖在特征空間上的差異，孿生圖卷積神經網絡可以將成對的圖嵌入到向量空間中，更有利于利用常見的度量方式(如：歐氏距離、余弦相似度和馬氏距離等)進行比對。

將經過圖卷積層得到的節點級嵌入輸入到全連接層中，得到固定維度的節點級向量，并對每層向量進行組內相加，得到節點級特征交互向量，并通過向量整合獲得三維特征，再經過卷積層、Flatten層獲得一維節點級關系向量，最終輸入到全連接層中以實現相似度計算并輸出預測得分。

本發明綜合以上思想，對圖結構數據相似度進行計算，調研中發現，基于節點級嵌入特征三維關系重建的圖結構數據相似度計算方法的本發明所提模型具有創新性和原創性。

發明內容

受前人工作啟發，本發明所提出的模型設計兩個輸入用以接收成對的圖數據，輸入模塊之后連接三個共享權值的圖卷積層實現孿生圖卷積特征提取模塊。將孿生圖卷積模塊的輸出結果輸入到全連接層得到固定維度的節點級向量。每對孿生圖卷積層的兩個輸出向量對應相加得到三個節點級交互向量，之后將三個向量相乘得到三維特征。經過三維卷積層提取特征，并用Flatten層將三維的輸入壓平，得到一維的節點級關系向量。關系向量表征節點對之間的差異，將其輸入全連接層輸出預測值，與實際值進行比較并通過反向傳播算法對模型整體參數進行訓練，訓練完成后的模型可以對圖結構數據進行可靠、快速的計算。