[發明專利]一種基于鄰接矩陣的連接信息規整系統、圖特征提取系統、圖分類系統和方法

在審

• 申請號: 201810286686.3
• 申請日: 2018-03-31
• 公開（公告）號: CN108520275A
• 公開（公告）日: 2018-09-11
• 發明（設計）人: 羅智凌;尹建偉;吳朝暉;鄧水光;李瑩;吳健
• 申請（專利權）人: 浙江大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/04
• 代理公司: 浙江杭州金通專利事務所有限公司 33100
• 代理人: 劉曉春

本發明提供了一種基于鄰接矩陣的連接信息規整系統、圖特征提取系統、圖分類系統和方法，通過將圖對應的鄰接矩陣中的連接信息元素集中到鄰接矩陣的特定的對角線區域中，將非連接信息元素提前進行削減，這樣在使用大小固定的窗口沿對角線區域遍歷就可以捕獲圖中所有對應大小的子圖結構時，時間復雜度大大降低了；進一步使用過濾矩陣沿對角線方向提取圖的子圖結構，然后采用層疊的卷積神經網絡提取更大的子圖結構，一方面大大減少了計算復雜度和計算量，解決了計算復雜度的限制和窗口大小的限制，并且能夠通過較小的窗口捕獲大型多頂點的子圖結構，以及來自頂點和邊的隱式相關結構的深層特征，提高了圖分類的準確性和速度。

技術領域

本發明屬于人工智能領域，具體涉及一種基于鄰接矩陣的連接信息規整系統、圖特征提取系統、圖分類系統和方法。

背景技術

圖論中的圖(graph)是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有某種關系。圖論中的圖(Graph)G是一個有序二元組(V，E)，其中V稱為頂點集(vertex set)，即圖中所有頂點組成的集合，E稱為邊集(edge set)，即所有頂點之間的邊組成的集合。簡單的說，頂點表示事物，邊表示事物之間的關系。圖(graph)是一種非網格數據(non-grid data)，這類數據的特點是，在具體的場景中維度(dimension)是不確定的，并且維度高且無上限，所述的圖的維度(dimension)是指圖的頂點的數量。例如化學結構式可以對應一個圖(graph)，其中原子即為圖(graph)中的頂點，原子間的化學鍵即為圖(graph)中的邊。一個分子的維度為該分子中包含的原子數量，例如一個分子包含100個原子組成，則該分子的維度為100。在一個分子的集合中，每個分子由數量不定的原子構成，故其維度是不確定的。現實中蛋白質等復雜結構往往由幾十甚至上百個原子構成，其維度就高達幾十甚至上百。又例如社交網絡也可以對應一個圖(graph)，其中，人即圖(graph)中的頂點，人與人之間的關系即圖(graph)中的邊，社交網絡的維度會更高且更加復雜，一般較大的社交網絡能有幾千個頂點，幾萬條邊，維度就高達幾千，可見圖論中的圖對應的維度是非常高的，且無上限。

另一方面，圖片、文本、音視頻等數據均屬于網格數據(grid data)，該類數據特點是，維度低(不超過3維)，并且維度是確定的。例如圖片(image)，對于一個圖片的集合，圖片的維度不受圖片的數量的影響，對于一張圖片，它的維度可以表示為2維或3維，更多張的圖片(例如數百張)，其維度是不變的，仍然為2維或3維。可見，網格數據和非網格數據是兩種完全不同的數據，非網格數據相比于網格數據有著更高且不確定的維度和更復雜的結構，對兩種數據的分類方法和特征提取方法也是完全不同的。

商業、科學和工程學中的許多復雜問題可以被抽象為圖(graph)的問題，然后可以通過使用圖分析算法來解決。圖分類(graph classification)問題將圖(graph)視為復雜對象，根據圖中隱藏的常見子圖結構模式構建深度學習模型來學習圖的分類(graphclassification)。例如，MUTAG數據集由許多硝基化合物組成，其中類別標簽可以指示化合物對細菌是否具有誘變作用。另一個例子是將不可見化合物映射到其對癌細胞的活性水平上。

圖分類問題(graph classification)將圖視為復雜對象，根據圖中隱藏的常見子圖(subgraph)結構模式構建深度學習模型來學習圖的分類。所述子圖(subgraph)是指圖中部分頂點以及將這些頂點連接起來的邊表現出的圖論中的圖。復雜對象分類的方法通常通過設計適合的相似度函數來測量兩個復雜對象之間的相似距離，然后再使用一些分類算法來對復雜對象進行分類。現有的基于圖相似度計算模型的圖分類大致分為兩類：