[發明專利]一種基于全局采樣子圖的圖寬度學習分類方法及系統

在審

• 申請號: 202110270414.6
• 申請日: 2021-03-12
• 公開（公告）號: CN113111914A
• 公開（公告）日: 2021-07-13
• 發明（設計）人: 宣琦;陳鵬濤;王金煥
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06K9/46
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵

一種基于全局采樣子圖的圖寬度學習分類方法，包括：1)全局采樣，使用連邊采樣法對原始網絡進行全局采樣，得到子圖；2)子圖映射，通過連邊到節點的映射機制分別將上述子圖映射一次或兩次得到一階與二階網絡；3)圖特征提取與融合，通過Graph2vec模型提取原始網絡以及所有映射后網絡的特征，再將提取得到的原始網絡特征以及各次采樣映射后的一、二階網絡特征拼接，作為原始圖的特征表示；4)寬度網絡分類。本發明還公開了一種基于上述方法的高效準確圖分類系統。結合上述融合的圖特征與已知的圖標簽有監督的訓練寬度網絡分類器中的權重矩陣。最后根據寬度網絡中的權重矩陣與輸入圖特征來實現對圖的有效分類。

技術領域

本發明涉及網絡科學、數據挖掘以及數據分析技術，特別是一種全局采樣子圖的圖寬度學習分類方法及系統。

背景技術

近年來，圖數據越來越受到廣泛的關注。在現實生活中的社交關系網絡、生物蛋白質網絡以及文獻的引用網絡本質上都可以用圖來刻畫。而圖分類問題則是圖數據挖掘中一個常見的任務，如在蛋白質毒理性推斷以及化學分子性質預測等方面都有廣泛的應用。因此研究圖分類問題具有非常重要的現實意義。

子圖是網絡中的一個基本組件，它能夠用于描述網絡中更加深層次的信息。由不同子圖構成的網絡通常存在著截然不同的拓撲屬性，因此將子圖集成到許多圖算法當中往往能實現更高的算法性能。目前大多數子圖的獲取都是通過采樣的方法，最常用的是基于隨機游走和有偏游走的局部采樣。而本發明則提供了一種基于全局的連邊采樣方式。

深度學習近些年是人工智能領域研究的熱點和主流，因為其性能的優勢在各大領域被廣泛的提及和使用。然而，深度學習的模型具有參數量大的問題，進而帶來算力損耗和時間損耗大的欠缺。本發明則使用了寬度網絡分類器大大降低了參數更新量，實現時間上的優化。

申請號為2019110684734的專利所公開的技術方案，一種基于采樣子圖網絡的節點分類方法，該方法使用隨機游走策略對網絡進行局部采樣，通過圖映射機制將采樣圖映射成多個子圖然后進行特征矩陣融合，使用極限隨機樹對網絡節點進行分類。該方法使用了隨機游走的策略得到局部的網絡結構，而缺失了全局的內在信息導致分類精度欠缺，而使用極限隨機樹作為分類器在分類訓練速度上還有待增強。

發明內容

本發明要克服現有技術的上述缺陷，提供一種基于全局采樣子圖的圖寬度學習分類方法和系統。

本發明利用全局采樣的策略、圖映射方法以及寬度網絡分類器構建了一個圖分類的模型，該模型通過全局采樣和圖映射充分提取了圖的內部結構與全局信息，將圖中提取的特征信息有監督的訓練寬度網絡分類器，從而提升了圖分類的精度和效率。

本發明實現上述發明目的所采用的技術方案如下：

一種基于全局采樣子圖的圖寬度學習分類方法，包括以下步驟：

S1：全局采樣，對原始圖按照連邊進行N次全局采樣得到N個子網絡；

S2：子圖映射，按照SGN規則分別對N個子網絡進行一階和二階的映射，得到2N個映射網絡；

S3：特征提取與特征融合，對原始網絡與2N個映射網絡分別基于Graph2vec進行特征提取，分別得到2N+1個網絡的K維網絡表征向量，通過表征向量橫向拼接獲取(2N+1)×K維的特征向量作為原始網絡的最終表示；

S4：寬度網絡分類器訓練，通過原始網絡的最終表示和網絡標簽有監督的訓練寬度網絡，最終通過十折交叉驗證獲得圖分類的精度。

進一步的，所述步驟S1具體包括：