[發明專利]一種同質關系大圖的摘要提取方法及系統

在審

• 申請號: 202110308958.7
• 申請日: 2021-03-23
• 公開（公告）號: CN113139098A
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 劉盛華;程學旗;周厚銓;劉財政;沈華偉
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06N3/04
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 祁建國

本發明提出一種同質關系大圖的摘要提取方法及系統，包括：獲取待摘要提取的關系圖數據作為當前圖數據，且該關系圖數據為同質關系大圖，并將該當前圖數據中每個節點均看作超點；根據該當前圖數據的鄰接矩陣，通過局部敏感哈希對該當前圖數據中節點進行分組；從組中隨機選擇多個超點對，分別計算該超點對若合并后和該關系圖數據之間的差距，選擇差距最小的超點對進行合并，得到重構圖數據；輸出該重構圖數據作為摘要提取結果。

技術領域

本發明涉及數據挖掘領域，特別涉及一種同質關系大圖的快速總結摘要及重構技術、裝置。

背景技術

目前社交媒體已超越搜索引擎，成為互聯網第一大流量來源，二者占比分別為46％和40％。關系圖數據成為一種常見數據應用到許多科學和工程中，圖可以表示成這樣一種結構，即圖G＝(V，E)是一對集合：一組節點V表示實體和一組邊E表示實體之間的關系或連接。在計算機科學中，網絡包含節點和邊緣；而在社會科學中，相應的術語則是行為者和關系，在本文中這兩個術語具有同等意義。截至2020年第一季度，微信及WeChat的合并月活躍帳戶數達12.025億，這意味著微信正式成為中國首個月活躍用戶超過10億的應用，從除夕到初五，微信消息發送量同比增長64.2％、8.23億人收發微信紅包。截止2020年3月31日的一季度財報。傳播最多的是“1萬億美元”，截止2020年3月31日止12個月，阿里平臺GMV達人民幣7.053萬億。過去12個月，有7.8億國人在阿里平臺購買產品或服務，阿里中國零售市場，移動月活躍用戶數8.46億，年度活躍買家7.26億。這些平臺的用戶之間的發信關系或者購物關系構成圖，如圖1和圖2所示，用戶構成圖中的節點，邊構成用戶之間的購物關系或者發信關系。在大多數情況下，圖數據是由一個或多個生成過程創建的，它們不僅能夠表示系統中的活動，還能夠收集實體的觀察結果。但是，由于這些大規模的圖數據數據量非常龐大，難以處理、分析和理解，這給圖數據挖掘應用程序帶來了巨大的挑戰。一個有效的技術來解決這些挑戰是圖摘要。給定一個圖G，它的目的是找到G的一個簡潔表示形式，即具有超節點和超邊的摘要圖(以圖3為例)。摘要模型通常需要從摘要圖中重構出圖，因此重構方案是大多數摘要模型的核心。針對摘要總結的思想，當前的方法主要包括以下幾類：

(1)鄰接矩陣的誤差：這類方法試圖最小化原始圖的鄰接矩陣和重構圖的鄰接矩陣之間的一些誤差度量，以達到最好的摘要總結效果。

(2)總邊數：在這種方法中，目標函數定義為摘要圖中的邊數加上邊校正信息，通過邊數和校正信息，提高摘要總結的性能。

(3)編碼長度：這類方法通常采用最小描述長度(MDL)原則，以編碼總長度為目標函數。通常會在不同的編碼方案下優化最小描述長度。

上面提到的方法主要集中在靜態簡單圖和應用在某一類圖數據上，無法具有普遍適用性。同時上述方法需要計算每一對節點之間的關系，以便于對圖數據進行摘要總結，盡管存在一些方法可以優化和加速上述計算過程，但是計算復雜度依然較高，尤其是在面對大圖數據時，這些方法普遍存在效率低、費時、需要占用較多內存等不足。

發明內容

本發明涉及數據挖掘領域，特別涉及一種同質關系大圖的快速總結摘要及重構技術、裝置，其核心思想是與常用的配置模型一樣，同質即圖中的節點類型相同，如社交網絡中的節點的類型都為用戶；而在電商購物網絡中，部分節點代表顧客，部分節點代表商品，節點類型不同，即為異質圖，本方法設置一些與節點的度成比例的超邊，基于配置的分配方案(CR方案)通常可以嵌入到現有摘要總結方法并能改進現有的相關摘要方法的性能和效果；基于信息論中的最小描述長度(MDL)作為原理，以最小化摘要圖和重建錯誤的成本。同時本方法設計了一種快速算法，稱為DPGS算法，其基于局部敏感哈希(Locality SensitiveHashing：LSH)方法對大圖的候選節點進行分組，并在組內進行貪婪合并以達到對圖進行摘要總結的目的。在理論上，本方法證明了通過最小化重建誤差來限制拉普拉斯特征值的擾動。

針對現有技術的不足，本發明提出一種同質關系大圖的摘要提取方法，其中包括：