[發明專利]一種基于圖卷積網絡的圖可視化方法

在審

• 申請號: 201811432008.X
• 申請日: 2018-11-28
• 公開（公告）號: CN109753589A
• 公開（公告）日: 2019-05-14
• 發明（設計）人: 朱梓豪;周川;曹亞男;張鵬;劉萍;郭莉
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/904
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 司立彬

本發明公開了一種基于圖卷積網絡的圖可視化方法，其步驟包括：1)對于目標領域的網絡G＝(V，E)，將網絡G中的節點嵌入到一個低維歐式空間中，得到網絡G的低維嵌入向量；所述低維嵌入向量包含網絡G中節點的特征信息和網絡G的拓撲結構信息；其中，V是節點集合，E是邊集合；2)將所述低維嵌入向量構造成一張K近鄰圖，即KNN圖；3)基于概率模型將所述KNN圖在二維空間中繪制出來。本發明學習到的嵌入向量同時保留了節點的結構信息和特征信息，可以對可視化結果進行粒度化調整。

技術領域

本發明屬于網絡嵌入-網絡可視化技術領域，涉及一種基于圖卷積網絡的圖可視化方法。

背景技術

隨著大數據時代的到來，全球信息數據量呈爆炸式增長。網絡成為表達數據之間復雜關系的重要形式，在信息世界中無處不在。Facebook、微信等社交媒體構成了社交網絡；生物中的蛋白質構成了高分子網絡；各類通訊媒介構成了通信網絡；智能硬件之間構成了物聯網等等。很多網絡的節點除了互相連接以外，還附加有豐富的文本、圖像、音視頻等多媒體信息，形成了典型的復雜信息網絡。通過對復雜網絡進行表示并進行可視化繪制，可以宏觀分析網絡的數據分布情況，包括聚類、分類等，為后續網絡分析任務提供技術支撐。

如果要可視化網絡首先需要對網絡進行表示，包括節點的拓撲結構信息和特征信息。傳統的網絡表示方案是通過建立鄰接矩陣表示網絡結構，假設網絡G＝(V,E)，其中V是節點集合，E是邊集合，網絡的鄰接矩陣定義為A∈|V|×|V|,其中A_ij＝1如果(v_i,v_j)∈E,否則A_ij＝0的。隨著網路規模不斷擴大，鄰接矩陣占用大量的存儲空間，而且其中的大部分元素都是0，面臨嚴重的稀疏性問題。

近些年來，隨著以深度學習為代表的特征學習技術在自然語言處理領域的廣泛應用，研究者開始探索面向網絡的特征表示方案，即類似于自然語言處理中的詞向量嵌入技術(word2vec,參考Mikolov T,Chen K,Corrado G,et al.Efficient estimation of wordrepresentations in vector space[J].arXiv preprint arXiv:1301.3781,2013.)，將網絡節點嵌入到低維歐式空間中，即用低維稠密向量表示。

Local Linear Embedding(參考Roweis S T,Saul L K.Nonlineardimensionality reduction by locally linear embedding[J].science,2000,290(5500):2323-2326.)、Laplacian Eigenmap(參考Belkin M,Niyogi P.Laplacianeigenmaps and spectral techniques for embedding and clustering[C]//Advancesin neural information processing systems.2002:585-591.)是基于矩陣分解的方法。LLE算法的輸入是一個鄰接矩陣，然后計算出每個節點的局部重建權值矩陣，最后推導出特征值分解問題，進而計算節點的低維表示。Laplacian Eigenmaps算法最終選取網絡的拉普拉斯矩陣的最小k個非零特征值對應的特征向量作為節點的低維表示。