基于最小描述長度原則的屬性圖概要方法

張 陶，于 炯，廖 彬，畢雪華

1.新疆大學 信息科學與工程學院，烏魯木齊 830046

2.新疆醫科大學 醫學工程技術學院，烏魯木齊 830011

3.新疆財經大學 統計與信息學院，烏魯木齊 830012

圖是一種能夠表現實體及其之間復雜關系的模型。許多領域如Web網絡、通信網絡、社交網絡、生物網絡、交通網絡、傳球網絡[1]等，都可以用圖數據結構進行描述，采用基于圖數據的方法進行處理。然而，隨著時間的推移，圖變得越來越大，例如截止2017 年10 月，Facebook 的常規移動用戶達到20 億[2]。如何從這些具有上億節點和千億條邊的大規模圖數據中找到和分析用戶所需要的信息，是一個極具挑戰性的難題。因為將如此大規模的圖直接加載內存，不僅耗費大量資源，而且導致可視化視圖非常混亂。圖概要（圖聚集）技術是大圖內存處理的一種有效的方法。它將一個大規模圖概要成一個簡潔且能夠反映原始圖結構和屬性信息的小規模圖（被稱為“概要圖”或“摘要圖”）。概要圖代替原始大圖進行數據分析，幫助用戶理解和分析原始圖中的有用信息。如圖1所示，圖1（右）是圖1（左）的一個摘要結果。顯然圖1（右）較圖1（左）更容易分析和理解。超點V4、V5，因為里面的節點屬性不相似，被劃分到不同超點中。若為了結構更緊湊，可繼續合并超點V4、V5為超點V6。

圖1 由原始圖產生的摘要圖Fig.1 Summary graphs generated from original graphs

實際應用中圖數據往往擁有大量信息，除了用節點來表示實體、邊表示實體之間的關系之外，還有大量的屬性信息伴隨著節點和邊出現。這種圖稱為屬性圖。節點的屬性信息是非常重要的，例如在社交網絡、合作網絡等圖應用領域中頂點所代表的實體都帶有某些語義的屬性，而語義的含義是不可忽視的。此種情形下，同時利用結構信息和屬性信息意味著會得到更加準確和有意義的分析結果，使聚集圖具有更全面的原始圖信息。但這也為屬性圖概要研究帶來了許多挑戰，如結構信息和屬性信息在語義上是相互獨立的實體，如何能夠同時考慮到節點屬性和結構信息[2]，實際應用中，當圖中節點附加有多個屬性，且屬性維度具有多種表現形式，如離散值、連續變量、字符串等時，那么屬性值距離的度量方式也會不一樣。如何確立統一的屬性相似性度量公式是需解決的問題之一。本文通過對屬性圖概要問題進行分析和建模，結合最小描述長度原則（Minimum Description Length，MDL），提出了兩種多屬性圖概要方法（Greedy algorithm-based Multi-Attributed Graph Summarization，Greedy-MAGS）和（Random algorithmbased Multi-Attributed Graph Summarization，Random-MAGS）。

本文所做工作如下：

（1）基于MDL 原則，對屬性圖概要問題進行分析建模。

（2）借鑒Levenshtein Distance 思想，本文提出了一種計算節點屬性相似性的方法。該屬性度量方法對節點屬性的限制較小，不要求節點屬性的距離或表現形式是一致的，節點的屬性可以是不同形式，不同的類型。并且將節點間的相似性統一為存儲代價，實現了節點結構相似和屬性相似的協同考慮。

（3）提出了兩種屬性圖概要算法：貪心算法Greedy-MAGS，追求全局最優，每次選擇圖中最佳的節點對進行合并，最后輸出一個高度壓縮的概要圖；隨機算法Random-MAGS，不追求全局最優，而是隨機選擇一個節點，將其與其附近的最佳節點合并。此算法提高了生成概要圖的速度，可以更好地適應更大原始圖的圖概要需求。

（5）通過在真實數據集和合成數據集上實驗，表明了本文所提算法的有效性。

1 相關工作

圖概要研究的目的是減少大型圖的結構復雜度和描述長度，通過壓縮、總結原始圖，來創建一個有意義的摘要圖，它近似地保留了底層圖的結構特性。目前的研究可以根據原始圖類型的不同分為僅結構圖[3-9]、屬性圖[10-17]或動態圖[18-19]的總結。綜述可在[20-23]中找到，以便全面了解。圖概要的算法采用的主要核心技術分類如表1所示。

表1 圖概要算法的核心技術分類Table 1 Technical classification of graph summarization algorithm

文獻[3-5]基于鄰接節點一致性，使得同一分組內部各節點具有相同的鄰接節點。Tian 等人[13]基于每個聚類中的節點屬性一致原則，根據節點的屬性對屬性圖進行聚類（k-SNAP）。該算法將屬性完全相同的點聚到一組，通過允許用戶下鉆和上取，實現了OLAP 形式的多粒度的圖聚。但這些算法都僅僅是考慮節點結構或屬性單方面的信息，這樣往往會造成某些分組中的屬性或者節點結構聯系非常松散。

而絕大部分方法考慮屬性相似性的方法一般先考慮屬性相似，然后根據結構相似性進行聚合摘要，不能實現結構和屬性的協同考慮，如文獻[10，12-14]；或者要求同一維度屬性的距離或表現形式是一樣的，工整的。

尹丹等人[10]研究了屬性圖的聚集方法，該算法將整個聚集過程分為了兩個階段，首先根據節點屬性的Jaccard相似性將節點劃分為M≤k個分組，然后根據邊的分布，選取節點，不斷迭代劃分至k個分組。此算法需預先設定超點的數量k，當用戶對數據沒有充分了解時，無法生成高質量的概要圖。

Navlakha 等人[4]提出了一種利用MDL 原則進行圖概要的方法，該算法既壓縮了原始圖，又產生了高層次抽象的概要圖，此方法奠定了基礎。但他們僅考慮了節點的結構相似性，未考慮屬性相似性。當輸入圖中的節點附加屬性時，它極可能合并具有高鄰域相似性但屬性不相似的節點。

Khan 等人[15-16]將MDL 與局部敏感哈希（Locality Sensitive Hashing，LSH）相結合，提出了一種基于集合的相似散列的總結方法。

本文借鑒了文獻[4]將MDL 原則應用于圖概要，可以實現圖壓縮和圖概要雙重目標的思路，改進了其衡量節點相似度的代價計算模型，同時考慮節點的結構相似性和屬性相似性這兩個信息來生成候選的相似節點，以解決屬性圖概要的問題。

2 問題描述

在本章中，定義了本文中的各種關鍵概念以及陳述問題。

2.1 基本概念及定義

定義1原始圖G。

設摘要前的屬性圖G=(V,E,A)為原始圖，其中V={v1,v2,…,vn} 表示節點集合；E={(vi,vj)|vi,vj∈V且i≠j}表示邊的集合；A={a1,a2,…,ak} 表示節點的k維屬性的集合，每個節點vi∈V的屬性可以表示為屬性向量attri(vi)=[a1(vi),a2(vi),…,ak(vi)]。

定義2概要圖GS。

G中的每個節點都分到唯一超級節點，形成一個節點分組，原始圖G關于此節點分組的概要圖為GS=(VS,ES,AS)。注意VS中的節點形成了不相交的節點子集，這些節點的聯合覆蓋了點集合V。

定義3圖的最小描述代價表示GMDL。

最小描述長度MDL原則[24]是由Rissanen于1978年提出的一種信息論原理。MDL原理指出當描述數據的總描述長度（代價）最小時的模型就是最佳的模型。數據的總描述代價由兩部分組成：模型的大小和模型編碼的大小。在圖概要中，數據是原始圖G，模型是概要圖GS，而模型編碼就是邊和屬性修正列表C（修正列表C是在摘要過程中添加或刪除的邊，以及節點的屬性修正值，主要用于重構原始圖）。當圖表示(GS,C)是原始圖的最小描述代價表示時，那么MDL 原則認為GS就是“最佳”的圖摘要結果。也就是說，GS既是原始圖G的最壓縮表示，同時也是其最好的摘要圖。最小代價圖表示(GS,C)被稱為圖G的最小描述代價表示GMDL。

GMDL由兩部分組成：GMDL=(GS,C)。第一部分是概要圖GS(VS,ES,AS)（比原始圖G小得多），它捕捉了原始圖中的重要集群和關系；第二部分是一組修正C，C可細分為兩部分：邊修正CE——原始圖G的一組邊，它們被標注為正(+) 或負(-) ；和屬性修正CA——一組G中節點的屬性值，它們被標注為插入(+)、刪除(-)或替換(→)。如果有必要，C可以幫助重新創建原始圖，重構G中每個節點只需要展開一個超級節點并讀取C中的相應條目。

2.2 問題定義

將MDL原則用于圖概要的目的就是找到具有最小修正C且高度緊湊的概要圖GS。

本文研究的圖概要問題的形式化定義如下：

即給出一個靜態無向屬性圖G，圖中每個節點都有多個屬性，目標是通過對具有公共鄰居且屬性相同或相似的節點進行合并壓縮，求解出圖G的最小代價MDL表示GMDL=(GS,C)。圖2顯示屬性圖概要的結果示例。

圖2 屬性圖概要示例Fig.2 Example of attributed graph summarization

輸入：G(V,E,A)

輸出：GMDL=(GS(VS,ES,AS),C=CE+CA)

如果給出一組超級節點VS，通過查看每個超級節點，根據創建超邊及修正的規則進行簡單選擇就可以計算出最小的表示代價cost(GMDL)，然而，如何為GMDL找到最佳的超級節點集才是主要的挑戰，它是將在第3章中要解決的一個困難問題。在第3 章中描述了關于代價模型和求解最小代價表示的算法的詳細說明。

3 多屬性圖概要方法

在本章中，首先介紹了多屬性圖MDL 表示代價模型，然后給出了尋找原始圖G的MDL 表示GMDL=(GS,C)的兩種算法。

GMDL=(GS,C)的描述代價取決于GS和C的代價之和，即cost(GMDL)=|GS|+|C|。|GS|與模型的大小對應，|C|對應模型編碼的大小。與超邊集ES、屬性集AS和C的存儲代價相比，將節點分組Av映射為超級節點v∈Vs的存儲代價通常要小得多，因此忽略了它。最小描述代價表示GMDL的代價計算公式為cost(GMDL)=|ES|+|AS|+|CE|+|CA|。

3.1 代價模型

鄰接和屬性列表在語義上是兩個獨立的實體。為了能同時考慮節點結構相似性和屬性相似性，將其統一為存儲代價來衡量。提出的代價模型分為結構存儲代價和屬性存儲代價兩部分。節點的相似性越高，合并后的存儲代價越小。

定義4結構代價CostE。

在圖中，鄰域相似性是一種廣泛使用的方法。通常，合并共享公共鄰居的任何兩個節點都可以降低成本，而更多的公共鄰居通常意味著更高的成本降低。

公式（1）[2]計算了總結的結構代價，它是創建超級節點時的邊數和邊修正數之和。其中，Nu是超級節點u∈VS的鄰居集合。

當原始圖中的節點帶有屬性時，如果僅考慮結構相似性，減少了聚集圖的信息量，則很有可能將具有高鄰域相似性但具有不同屬性相似性的節點合并起來，使聚集圖的質量下降。為了克服這個缺陷，最好同時考慮候選相似節點對的結構信息及屬性信息。

定義5屬性代價CostA。

圖中的每個節點都有多個屬性，這些屬性都是該節點的某些方面的特征信息，屬性取值可能是離散型的（如布爾值），可能是連續型的，也可能是文本型的。如社交網絡中的用戶，不僅具有性別、年齡屬性，還具有興趣愛好等復雜屬性。屬性維度間不一樣的表現形式會導致一樣的相似性度量方式。有的文獻是將屬性轉化為屬性值矩陣，用0/1表示屬性是否存在；有的方法是將屬性值轉化為集合的形式，然后使用距離度量函數（比如Jaccard相似度）衡量其相似性；也有方法將屬性值映射到具體數值上，例如局部敏感哈希（Local Sensitive Hash）方法、SimHash 算法。但上述方法都需要節點屬性的距離或表現形式是一樣的，工整的。在實際的應用中圖中節點的屬性具有多樣性，不同屬性維度的距離往往是不一樣的。針對這個弊端，本文提出了一種統一的屬性相似性方法。本文借鑒了字符串相似性算法Levenshtein Distance的思想，來衡量節點屬性的相似，該方法對節點屬性的限制較小，節點的屬性可以是不同形式、不同的類型，并將其轉為屬性存儲代價，與結構代價相統一。

編輯距離（Edit Distance），是由1956年俄國科學家Vladimir Levenshtein給字符串相似度提出的定義，又稱Levenshtein距離。是指兩個字符串之間，由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。例如從aware 到award 需要一步（一次替換），從has 到have 則需要兩步（替換s 為v 和再加上e）。字符越相似，編輯操作則越少。若兩個字符串等長時，編輯距離即為漢明距離。

本文受上述思想的啟發，提出了用屬性編輯距離（Attributed Edit Distance，AED）來計算節點屬性相似度。此方法將每個節點的屬性分布看作是字符串，其中的每個屬性維度值則類似于一個字符。

公式（2）是節點間的屬性編輯距離，距離值越小，屬性分布越相似，編輯操作則越少。產生的編輯操作列表作為屬性修正，加入CE。

公式（3）計算了總結的屬性代價，它是創建超級節點時的屬性維度個數和屬性修正數之和。au(i)表示節點u第i維屬性值，k是節點的屬性維度個數。

如圖3所示，以某社交網絡精簡的屬性分布為例說明本文屬性相似度計算方法。每行代表一個用戶節點v1～v5，列表示其屬性（4 個屬性維度A、B、C、D）。A的屬性域為一個0～1分布；B的屬性域是數值類型的連續變量；C的屬性域包含三種取值：a、b、c；D的屬性域是一個集合，代表用戶的興趣愛好，比如音樂music或者閱讀reading等。編輯操作列表是每個節點屬性變為某一屬性分布所需的最少編輯操作。假設節點v1與節點v2～v5具有完全相同的鄰居節點，此時僅考慮它們的屬性相似性。其中，節點v2具有與v1完全相同的屬性分布，因此不產生編輯操作，是v1最佳的合并節點。而節點v5與v1屬性完全不同，因此將產生4 個編輯操作。節點的屬性越相似，則產生的編輯操作越少，屬性代價越小。

圖3 節點屬性相似度計算示例Fig.3 Example of computing attribute similarity of node

對于節點集v1～v5，A屬性維度是（0，0，1，0，1），A維度下重復出現次數最多的屬性值（即最大頻率屬性值）是0。當將每個節點的A 維屬性都變為最大頻率屬性值0，將產生最少的編輯操作次數（2 個）。按照屬性值的出現頻率節點集v1～v54 個屬性維度下的最大頻率屬性分布為(0,10,a,Music)，可得節點v1～v5變為此屬性分布所產生的編輯操作之和是最小的，因此得到的屬性修正是最小。因此，在圖概要過程中，為了產生最少的編輯操作，生成最小的屬性修正列表CE，將合并后超級節點的屬性設置為最大頻率屬性分布的值。

定義6總代價Cost(u,v)。

公式（4）計算了總結的總代價，通過參數β∈[0,1]調整兩種代價的權重。β越大表示結構代價的權重越大，合并更側重于結構的相似性。

定義7代價降低比率s(u,v)。

在一個大圖中，通過合并許多節點對可以降低圖的存儲代價。通常，任何兩個具有相似結構和屬性的節點合并就可以降低存儲代價，比如兩個節點擁有共同的鄰居節點且屬性值也相同，就可以將它們折疊成一個超級節點，用單個超邊替換到每個公共鄰居的兩條邊。顯然，這將大大減少需要存儲的總邊數，同時節點屬性的存儲空間也會降低50%，從而大大降低了內存需求。而擁有更多共同鄰居和相似屬性的節點通常意味著更高的成本降低。在此基礎上，定義了合并節點對(u,v)后的代價降低比率s(u,v)，如公式（5）。s(u,v)被定義為合并節點u和v（形成一個新的超節點w）帶來的存儲代價降低值和合并節點u和v前存儲總代價的比值。只要有利于存儲代價降低的點合并都會進行，只是會根據s(u,v)值的大小調整其被合并的順序。在貪心算法中，迭代地將圖中具有對s(u,v)的最大值的節點對合并。算法的核心思想是選擇具有最大共同鄰居數及屬性相似的節點對進行合并，以創建將s(u,v)降低到最大值的超級節點。隨著算法的發展，維護了一組超級節點VS，它們構成了圖概要中的超級節點。

當兩個節點具有完全相同的鄰接列表和屬性列表時，則被認為是完全等價的節點，合并它們，s(u,v)可以取到最大值0.5。當節點u,v的屬性完全不同時，屬性編碼代價的降低為0。

下面詳細描述用于尋找原始圖G的MDL 表示GMDL=(GS,C)的兩種算法。

3.2 貪心算法

貪心算法Greedy-MAGS算法迭代地將最大代價降低（全局最優）的節點對合并成超級節點。為了有效地選擇s(·)值最大的節點對，使用標準的max-heap結構H來存儲s(u,v)大于0的圖中的所有節點對。

算法1Greedy-MAGS算法

此算法分為三個階段進行：第一階段初始化（第1～7行）：此階段任務是采用時間復雜度最優的堆排序將所有候選合并節點對按照其s(?)值排序。步驟如下：首先遍歷超點集VS中所有2 跳節點對，并計算它們的s(?)值。之所以只考慮相隔2跳的節點對，是因為觀察到兩個沒有共同鄰居的節點合并不可能降低結構存儲代價，只有合并擁有公共鄰居節點的節點對才能降低結構存儲代價。而相隔2 跳的節點對之間必然有至少一個共同鄰居節點。然后將(s(?)>0)的節點對放入一個最大堆H中進行排序。

第二階段迭代合并：依次選擇最大s(?)值的節點對進行合并，并更新超點集VS和最大堆H。對于每個超級節點，為了產生更少的屬性修正，通過從{ }u,v中選擇到最大頻率屬性分布的編輯距離AEDMAX更小的節點的屬性值來設置其屬性（第13～17行）。第23～28行重新計算了包含節點x∈Nw的所有對的s(?)值，并在堆H中更新它們（因為超點w的鄰居節點x，它以前是節點u或v的鄰居節點，合并u和v可能會改變邊(u,x)（和/或(v,x)）的s(?)值）。

結果輸出階段：第31～41行生成超邊及修正列表C，包含邊修正Ce和屬性修正Ca兩部分。當|Auv|>(|Πuv|+1)/2時，新增邊(u,v)至ES。最后輸出摘要圖GS以及邊和屬性的修正列表集C。

創建超邊及修正時尋求最小的內存需求，只對高度緊湊的總結和最少的修正感興趣。具體規則如下：將Πuv定義為Au,Av∈VS之間所有可能邊的集合，Auv作為Au和Av之間的實際存在的邊集合。當符合|Auv|>(|Πuv|+1)/2 時，超點間創建超邊(u,v)，并對Πuv-Auv里的邊創建負修正，內存代價是(1+|Πuv-Auv|)；否則，不創建超邊，僅對Auv里的邊創建正修正，內存代價為|Auv|。也就是說為了讓圖表示更緊湊、體積更小，只有當Au與Av間的節點密集連接時，才在超級節點u和v之間存儲一條超邊，并且選擇內存代價更小的邊修正方式。

為了產生最少的編輯操作，生成最小的屬性修正列表CE，對于每個超級節點u，通過選擇Au中具最大頻率屬性分布的值來設置其屬性。其余屬性值作為屬性修正創建。

算法1 時間復雜度分析：算法第1 行初始化復雜度為O(n) ；第2～7 行代碼為堆排序操作，時間復雜度為O(n×lbn)，其中n為超點集VS中所有具有正代價降低率的二跳節點對個數；8～26 行代碼是while 循環嵌套if判斷以及for循環，其中，第9～15每行復雜度都為O(1)，對于第一個for循環，時間復雜度由每個節點的度m決定；同樣，23～26 行代碼復雜度為O(m)；疊加外層while循環，所以8～26 行代碼復雜度為O(n×2m)；第30 行的時間復雜度為O(n)，31～41 行為for 循環嵌套兩個if 判斷，當超點集VS里節點對個數為n時，每個if判斷中的代碼最多會被操作n次；所以，算法1 的時間復雜度為O(n+n×lbn+n×2m+n)≈O(n(lbn+m)) 。

3.3 隨機算法

為了更大輸入圖的圖概要需求，提高生成概要圖的速度，本文又提出了一種生成概要圖更快的策略方法——隨機算法Random-MAGS算法。Random-MAGS算法不需要堆結構，它不追求全局最優，不是合并全局最優節點對，而是隨機選取一個節點，將其與其附近的最佳節點合并。因此節點合并過程比貪婪算法Greedy-MAGS算法快很多。

算法2Random-MAGS算法

算法2中，算法第1～3行的初始化操作，每行時間復雜度為O(n)，第4～18 行是while 循環嵌套if 判斷，代碼復雜度為O(n)；所以，結果輸出階段，與算法1 一樣，代碼復雜度為O(n)，所以，算法2 的時間復雜度為O(2n+1+n+n)≈O(n)。

4 實驗結果與分析

本章從聚集效果和算法性能兩方面評估兩種屬性圖聚集算法Greedy-MAGS 和Random-MAGS。實驗數據選取了4個真實的無向圖數據集D1～D4 和一個合成數據集D5（在數據集D4 基礎上，又創建了一維屬性并隨機生成其屬性值（10個候選值））。表2給出了每個數據集的具體信息。選取BB-ULSH算法[15]進行對比，BBULSH 算法屬性相似性設置為50%。實驗環境是Core i7-8750H 2.20 GHz CPU和16 GB的RAM，所有算法用Java語言實現。

表2 數據集信息Table 2 Dataset information

4.1 聚集效果

使用邊壓縮率和屬性修正代價來評價屬性圖概要的質量。在理想的情況下，摘要圖的屬性修正應該和超級節點一樣都是最小的。

使用公式（6）計算邊壓縮率，其中PreviousCost表示原始圖中實際存在的邊；CurrentCost表示摘要圖中超邊和邊修正之和。超邊和邊修正越少，此結果值就越大，代表了摘要結果越好。

如圖4，兩種算法都獲得了較高的壓縮率。這是因為兩種算法都采用了成對創建超節點的策略，嚴格探索查詢每個節點的2跳鄰居節點，保證了合并的每一對節點都是最高壓縮比，因此，都實現了較好的壓縮。

圖4 不同數據集下的邊壓縮率對比（越高越好）Fig.4 Compression rate comparison of different data sets（the higer the better）

4.2 算法性能

圖5 顯示了所有算法的運行時間對比，BB-ULSH算法的運行時間最短，是因為它是采用基于集合創建超點的技術，一次迭代可以遍歷和壓縮多個節點；而兩種算法則都是以其迭代的成對超節點創建技術，遍歷查詢每個節點的2跳鄰居列表以確定最佳可壓縮節點，且每個迭代只壓縮一對節點，因此花費了更多的時間，但隨著圖的稀疏性的降低，這兩種算法的執行時間都不斷下降。

圖5 不同數據集下的運行時間對比（越小越好）Fig.5 Runtime comparison of different data sets（the smaller the better）

在D1 數據集上幾種算法的運行時間差異不大。而數據集D5 上差異較大。這是因為采用成對創建超節點技術的兩種算法運行時間與每個節點2跳鄰居列表的大小成正比，而D5 中每個節點都有大量的2 跳節點。因此需要的運行時間更多，其中，與本文的預測一致，Greedy-MAGS 算法追求全局結構最緊密屬性最相似，Random-MAGS 算法要明顯快于Greedy-MAGS算法。

4.3 算法參數分析

本實驗考察了本文兩種算法在不同數據規模數據集上在摘要表示代價和運行時間方面的差異。

圖6結果所示，采用兩種算法都得到了遠小于原始圖存儲代價的摘要圖。Greedy-MAGS算法追求全局最優時間代價方面明顯大于Random-MAGS算法，但同時也獲得了存儲代價更小的摘要圖。

圖6 兩種算法表示成本和運行時間對比Fig.6 Comparison of representation costs and running times

接下來，觀察了圖中MDL表示的各部分存儲代價。如圖7，MDL表示的存儲代價共有4部分組成：超點（節點分組）、摘要圖、邊修正和屬性修正。其中邊修正和屬性修正是主要的表示成本，占到80%左右。同時也觀察到，當原始圖屬性維度增加時(D4 →D5)，屬性修正代價呈直線上升。除了因為屬性維度個數增加外，新增屬性值是隨機產生的也是原因之一。

圖7 MDL表示成本（Greedy-MAGS算法）Fig.7 Breakup of cost of representation computed by Greedy-MAGS

整體來看，相較D5 數據集，所有算法在D4 數據集都產生了更少的屬性修正。這是因為真實的數據集節點屬性通常與節點鄰居節點相關，稱之為節點自然屬性同質性的優勢，比如社交網絡上通常是相同層次的人員之間進行互動交流，他們具有共同的朋友和興趣品味（屬性）。因此產生較少的屬性修正。D4 數據集具有節點自然屬性同質性的優勢。而D5 數據集因為每個節點有一維屬性值是隨機生成的，因此屬性值與鄰域之間不協調，則產生了更多的屬性修正。

5 結語

首先，本文對多屬性圖概要問題進行了分析，提出了多屬性圖概要問題的MDL 模型。其次，提出了計算節點屬性相似性方法，將節點間的相似性統一為存儲代價，解決了不能同時考慮節點屬性相似性和領域相似性這兩個語義完全不同的實體的問題。然后，提出了兩種多屬性圖概要算法貪心算法Greedy-MAGS和隨機算法Random-MAGS適應不同的圖概要需求。最后，通過在真實和合成的數據集上實驗分析，證明本文所提能屬性圖概要方法的有效性。下一步工作主要集中在以下幾個方面：基于MDL 的圖概要方法對應的修正列表占據的空間消耗較大，幾乎占所有消耗的80%，并且發現修正列表中存在一些重復率較高的編輯操作，可針對這個進行再次壓縮，比如可以使用Huffma 編碼或者串表壓縮（LZW 算法）等算法提取修正列表中的不同編輯操作，基于這些編輯操作創建一個編譯表，然后用編譯表中的字符的索引來替代原始修正列表中的相應編輯操作，減少進一步原始數據大小。另外現有算法僅考慮了邊的結構信息，下一步工作多加考慮邊的類型以及權重等信息。