圖概要技術(shù)研究進(jìn)展

王 雄 董一鴻 施煒杰 潘劍飛,2

1(寧波大學(xué)信息科學(xué)與工程學(xué)院 浙江寧波 315211)2(百度在線網(wǎng)絡(luò)技術(shù)有限公司 北京 100085)

隨著數(shù)據(jù)量的爆發(fā)式增長(zhǎng)[1]，人們對(duì)數(shù)據(jù)的處理識(shí)別能力并沒(méi)有因?yàn)橛?jì)算資源和存儲(chǔ)能力的提高而提升.圖結(jié)構(gòu)數(shù)據(jù)[2]能夠在許多應(yīng)用中表現(xiàn)實(shí)體對(duì)象之間復(fù)雜的關(guān)系，如用戶交互形成的社交網(wǎng)絡(luò)[3]、電話信息組成的通信網(wǎng)絡(luò)[4]、學(xué)者合作形成的研究網(wǎng)絡(luò)[5]、網(wǎng)頁(yè)瀏覽形成的Web網(wǎng)絡(luò)[6]、用戶產(chǎn)品和服務(wù)購(gòu)買(mǎi)的交易網(wǎng)絡(luò)[7]、行程和道路組成的交通網(wǎng)絡(luò)[8]、垃圾噪音數(shù)據(jù)組成的過(guò)濾網(wǎng)路[9]，以及化學(xué)化合物互相作用的生物網(wǎng)絡(luò)[10]等.圖數(shù)據(jù)隨處可見(jiàn)，在大數(shù)據(jù)背景下圖數(shù)據(jù)的規(guī)模日益增大，截至2017年6月Facebook的月活躍用戶數(shù)已達(dá)20億，Twitter的月活躍用戶數(shù)保持在3.2億，騰訊的QQ保持8.61億月活躍用戶，微信則超過(guò)9.6億[11-12]，社交網(wǎng)絡(luò)已成為連接網(wǎng)絡(luò)信息空間和人類(lèi)現(xiàn)實(shí)世界不可或缺的橋梁.

然而，這種連接關(guān)系所構(gòu)成的大規(guī)模圖結(jié)構(gòu)數(shù)據(jù)具有上億頂點(diǎn)和千億條邊，對(duì)于這樣的社交網(wǎng)絡(luò)圖是無(wú)法直接加載內(nèi)存進(jìn)行處理；現(xiàn)有的大多數(shù)算法對(duì)于這類(lèi)大圖不能有效處理，尤其是涉及到圖流實(shí)時(shí)分析決策時(shí)，無(wú)法及時(shí)反饋給用戶需要的信息；現(xiàn)實(shí)生活中的數(shù)據(jù)往往含有很多隱藏的錯(cuò)誤信息標(biāo)簽，例如WEB網(wǎng)絡(luò)圖中錯(cuò)誤的鏈接以及一些垃圾郵件的傳播[13]、病毒的擴(kuò)散[14]等，這種噪音阻礙了用戶對(duì)原始圖真實(shí)結(jié)構(gòu)特征的挖掘，增加了計(jì)算資源的消耗.大圖數(shù)據(jù)的這些缺陷使得用戶難以直接管理，給社會(huì)網(wǎng)絡(luò)分析和數(shù)據(jù)挖掘帶來(lái)了挑戰(zhàn).

針對(duì)大規(guī)模圖數(shù)據(jù)的概要化是潛在的解決方案，圖的概要化(graph summarization)[15]，簡(jiǎn)稱圖概要，運(yùn)用各種圖形操作技術(shù)，尋找一組簡(jiǎn)潔的超圖或稀疏圖，闡明原始圖的主要結(jié)構(gòu)信息或變化趨勢(shì)，代替原始大圖進(jìn)行數(shù)據(jù)分析.它一般針對(duì)大規(guī)模的圖數(shù)據(jù)，在一定的應(yīng)用背景下，考慮時(shí)間、空間和信息之間的權(quán)衡，量化頂點(diǎn)或邊緣的屬性相似性和鄰域相似性，縮小原始圖的規(guī)模，保留一些應(yīng)用價(jià)值屬性，支持用戶的互動(dòng)分析，或者濾除噪聲數(shù)據(jù).一個(gè)優(yōu)秀的概要圖涵蓋了原始圖中主要的結(jié)構(gòu)特征,其頂點(diǎn)稱為超級(jí)頂點(diǎn)(簡(jiǎn)稱超點(diǎn)),它代表原始圖中一組相近頂點(diǎn)的集合;其邊稱為超級(jí)邊(簡(jiǎn)稱超邊),它代表2個(gè)頂點(diǎn)集合之間的聯(lián)系.圖概要既可以揭露實(shí)體之間隱藏的復(fù)雜關(guān)系，又可以保持原圖的性質(zhì)，有效減少圖的存儲(chǔ)空間，提高圖計(jì)算的效率.

通常，圖概要概念的不同表述還有圖概括(graph synposis)[16]、圖聚集(graph aggregation)[17]、圖規(guī)約(graph simplification)[18-19]等，而圖采樣(graph sampling)[20-21]、圖聚類(lèi)(graph clustering)[22-23]、圖壓縮(graph compression)[24-25]與圖概要有緊密的聯(lián)系，但最終的目標(biāo)又不盡相同.

圖采樣與圖概要的目標(biāo)都是創(chuàng)建一個(gè)原始圖的簡(jiǎn)短表示[26]，進(jìn)行有效的算法分析.不同點(diǎn)在于圖采樣是通過(guò)局部子圖特征來(lái)估計(jì)原始圖的屬性，例如頂點(diǎn)采樣和邊采樣，進(jìn)行圖的稀疏化以縮小圖的規(guī)模，如何進(jìn)行有代表性、有普遍性的采樣是其研究的核心，但會(huì)導(dǎo)致圖結(jié)構(gòu)特征大量丟失；而圖概要?jiǎng)t從全局出發(fā)，合并高度相似的頂點(diǎn)減小圖的規(guī)模，能維持圖結(jié)構(gòu)特征.

圖聚類(lèi)和圖概要都通過(guò)頂點(diǎn)的分組合并得到子圖.不同點(diǎn)在于圖聚類(lèi)是組合密集連接的頂點(diǎn)，側(cè)重尋找局部稠密的結(jié)構(gòu)，圖聚類(lèi)沒(méi)有特定的目標(biāo)和任務(wù)；而圖概要立足于整體結(jié)構(gòu)，側(cè)重尋找屬性和結(jié)構(gòu)相似的集合,它不僅概括稠密的結(jié)構(gòu),還概括稀疏的結(jié)構(gòu)，相較于圖聚類(lèi)，圖概要一般都具有特定的任務(wù)，與實(shí)際應(yīng)用聯(lián)系更為緊密.

圖概要和圖壓縮主要目的都是節(jié)省大量的空間開(kāi)銷(xiāo).但是圖壓縮旨在尋找輸入圖的最小空間存儲(chǔ)，忽視了圖結(jié)構(gòu)和屬性隱藏的語(yǔ)義特征，可解釋性差；圖概要旨在尋找高質(zhì)量的超圖代替原始圖進(jìn)行分析.當(dāng)然，圖概要中部分方法基于圖壓縮的理念尋找輸入圖的較小表示，兼顧了其結(jié)構(gòu)特征的相似性.

總之，圖采樣通過(guò)局部結(jié)構(gòu)評(píng)估整體特征，圖聚類(lèi)合并局部稠密的頂點(diǎn)，圖壓縮尋找原始圖的最小表示模型，它們更注重處理大型數(shù)據(jù)時(shí)計(jì)算效率的提升和內(nèi)存資源的利用，但往往忽略了圖數(shù)據(jù)的真實(shí)結(jié)構(gòu)信息.而圖概要技術(shù)的根本目的在于通過(guò)小規(guī)模的超圖或稀疏圖替代原始圖進(jìn)行特征分析，更注重挖掘用戶未知的結(jié)構(gòu)模式和隱藏的信息特征，一個(gè)優(yōu)秀的圖概要技術(shù)往往需要結(jié)合特定的應(yīng)用背景和需求.因此當(dāng)我們面對(duì)一個(gè)真實(shí)世界的大型網(wǎng)絡(luò)數(shù)據(jù)時(shí)，如何去發(fā)現(xiàn)一些有趣的結(jié)論或者未知的結(jié)構(gòu)，圖概要技術(shù)是最佳的選擇.例如關(guān)于維基百科的編輯網(wǎng)絡(luò)概要圖，圖采樣只能評(píng)估其編輯網(wǎng)絡(luò)中各個(gè)話題的熱度級(jí)別；圖聚類(lèi)將相近的話題進(jìn)行分組；圖壓縮則將其轉(zhuǎn)化為無(wú)法解釋的最小存儲(chǔ)模型；而圖概要能描述了一些群體在對(duì)某些敏感問(wèn)題上多次互相編輯，形成“沖突-戰(zhàn)爭(zhēng)”導(dǎo)致兩極分化的特殊結(jié)構(gòu)，有助于人們尋找文化差異較大甚至對(duì)立的特殊社會(huì)群體.

Fig. 1 Cosum entity relationship summary[32]圖1 Cosum實(shí)體關(guān)系概要圖[32]

1 圖概要技術(shù)

本文從圖概要的解決方案及應(yīng)用需求，將現(xiàn)有的概要技術(shù)分為：基于空間壓縮的圖概要、基于查詢優(yōu)化的圖概要、基于模式可視化的圖概要和基于影響分析的圖概要.圖結(jié)構(gòu)數(shù)據(jù)主要有靜態(tài)圖和動(dòng)態(tài)圖，靜態(tài)圖的邊和頂點(diǎn)保持一致，動(dòng)態(tài)圖由于其自身的邊或頂點(diǎn)不斷變化，具有時(shí)間維度屬性.

1.1 基于空間壓縮的圖概要

基于空間壓縮的圖概要方案，旨在減少輸入圖的規(guī)模，降低網(wǎng)絡(luò)的異構(gòu)性[27]，濾除噪音數(shù)據(jù)，保留原始圖的主要結(jié)構(gòu)信息，用較小的、有代表性的超圖代替原始圖進(jìn)行數(shù)據(jù)分析.主要采用圖壓縮和圖聚類(lèi)2種方法.

1) 基于圖聚類(lèi)的方法

圖聚類(lèi)將每個(gè)密集連接的集群映射到超級(jí)頂點(diǎn)，確保不同集群的頂點(diǎn)性質(zhì)不相同，生成的概要圖僅凸顯集群內(nèi)部邊緣信息的頂點(diǎn)集合，以近似鄰接矩陣表示.聚類(lèi)技術(shù)最初不能保證概要圖的質(zhì)量，啟發(fā)式算法的出現(xiàn)，通過(guò)給定輸入圖和期望超點(diǎn)的數(shù)量k，重建誤差最小化，使得概要圖的質(zhì)量得以提高.

文獻(xiàn)[28]提出的關(guān)于加權(quán)圖的概要化WGC(compression of weighted graphs)，從“簡(jiǎn)單”和“廣義”進(jìn)行擴(kuò)展，主要尋找實(shí)體關(guān)系結(jié)構(gòu)相似的頂點(diǎn)合并，在保持最小化誤差的條件下追求壓縮最大化，關(guān)鍵在于合并一定跳數(shù)頂點(diǎn)的過(guò)程中保持邊權(quán)重或連接強(qiáng)度，以獲得壓縮圖.在簡(jiǎn)單加權(quán)圖概要任務(wù)中，通過(guò)為每個(gè)邊分配其代表所有邊的平均權(quán)重，逼近原始圖使誤差最小化.在廣義加權(quán)圖壓縮任務(wù)中生成保持連通性的子圖，即任何2個(gè)頂點(diǎn)的最佳路徑在概要圖中與原始圖相等，但路徑不一定一樣.

文獻(xiàn)[29]提出的概要技術(shù)GRAC(graph clust-ering)采用多層次的聚類(lèi)算法，主要分為粗化階段、初始聚類(lèi)階段以及細(xì)化階段.當(dāng)頂點(diǎn)合并成超點(diǎn)時(shí)，超邊的權(quán)重為包含的所有邊的權(quán)重之和.粗化階段首先隨機(jī)遍歷所有未標(biāo)記的頂點(diǎn)，如果頂點(diǎn)v的所有鄰居頂點(diǎn)已標(biāo)記，則標(biāo)記此頂點(diǎn)；若該頂點(diǎn)存在未標(biāo)記的鄰居頂點(diǎn)，則合并頂點(diǎn)v與某一鄰居頂點(diǎn)使其最大化：

(1)

其中，e(u,v)對(duì)應(yīng)邊的權(quán)值，w(v)對(duì)應(yīng)頂點(diǎn)的權(quán)值，直到所有頂點(diǎn)粗化完成.聚類(lèi)階段則采用光譜算法[30]參數(shù)進(jìn)行劃分.細(xì)化階段受核k-means[31]和譜聚類(lèi)的啟發(fā)，采用增量式加權(quán)核k-means保證算法優(yōu)化相應(yīng)的圖聚類(lèi)目標(biāo)，采用本地搜索來(lái)提升批量細(xì)化的質(zhì)量.

Cosum[32]將RDF(resource description frame-work)圖轉(zhuǎn)化為多類(lèi)型圖，并將實(shí)體解析問(wèn)題轉(zhuǎn)化為多類(lèi)型圖概要問(wèn)題.其關(guān)鍵方法是輸入k-型圖轉(zhuǎn)換為由超頂點(diǎn)組成的另一個(gè)k-型概要圖，使用不同類(lèi)型的頂點(diǎn)集鏈接來(lái)提高頂點(diǎn)分辨率的準(zhǔn)確性.Cosum將頂點(diǎn)聯(lián)合成超頂點(diǎn)，使得每個(gè)超級(jí)頂點(diǎn)是相干的(即頂點(diǎn)具有相同類(lèi)型并且具有高相似性)，并且根據(jù)其組成頂點(diǎn)之間的原始邊緣創(chuàng)建超級(jí)邊緣.已經(jīng)表明：Cosum優(yōu)于最先進(jìn)的通用實(shí)體解決方法，特別是在具有缺失值和一對(duì)多或多對(duì)多關(guān)系的數(shù)據(jù)集中.如圖1所示，RDF圖被建模為多類(lèi)型圖，輸入圖頂點(diǎn)表示不同對(duì)象，實(shí)線表示關(guān)系，虛線上方的權(quán)重w表示實(shí)體之間的相似度，相似度可通過(guò)鄰居頂點(diǎn)相似或者內(nèi)容相似度(字符串)計(jì)算.概要圖顯示對(duì)于產(chǎn)品1，2而言，合并超頂點(diǎn)時(shí)制造商是更重要的特征，而對(duì)于產(chǎn)品3，4而言價(jià)格特征則更重要.

2) 基于圖壓縮的方法

壓縮是數(shù)據(jù)概要中的常用技術(shù)，其目標(biāo)是通過(guò)壓縮技術(shù)最小化描述輸入圖，通?；谧钚∶枋鲩L(zhǎng)度[33](minimum description length, MDL)原則，構(gòu)造輸入圖的模型及模型規(guī)則下存儲(chǔ)的數(shù)據(jù)，辨別各種結(jié)構(gòu)模式.問(wèn)題在于如何利用MDL去選擇最合適的模型，一般應(yīng)用相關(guān)的優(yōu)化函數(shù)將頂點(diǎn)或邊緣遞歸合并到超級(jí)頂點(diǎn)中.關(guān)鍵策略是合并過(guò)程中保持邊緣權(quán)重或連接的強(qiáng)度，最小化誤差并最大化壓縮獲得壓縮圖.在屬性圖概要化中，壓縮技術(shù)也利用了頂點(diǎn)結(jié)構(gòu)和屬性.初始的策略是優(yōu)先選取一個(gè)維度(屬性信息)進(jìn)行概要化壓縮，然后再根據(jù)拓?fù)浣Y(jié)構(gòu)進(jìn)行修正，后期從信息論的角度統(tǒng)一度量結(jié)構(gòu)和屬性的差異化.

文獻(xiàn)[34]是第1個(gè)基于MDL原則提出了全新的圖概要模型，該模型在可控有界誤差內(nèi)生成概要圖，其概要圖由2部分組成：通過(guò)聚合頂點(diǎn)生成S和校正C.校正指精確重建G的邊緣校正列表.成本R是S和C的存儲(chǔ)成本總和：Cost(R)=E(S)+C.該模型在計(jì)算最大壓縮圖的同時(shí)生成了最佳概要圖，核心策略有2種:1)基于貪心策略遍歷所有頂點(diǎn)，尋找全局最佳頂點(diǎn)對(duì)，迭代合并成超點(diǎn)，最大限度地降低頂點(diǎn)的成本；2)隨機(jī)策略則是一種輕量級(jí)的隨機(jī)化方案，選擇頂點(diǎn)與附近的最佳頂點(diǎn)對(duì)合并.此模型針對(duì)概要圖的誤差進(jìn)一步擴(kuò)展研究，定義了誤差參數(shù)度量：

(2)

Fig. 2 MDL compression of origin graph[34]圖2 原始圖的MDL壓縮[34]

文獻(xiàn)[36]提出了概要化模型——SlashBurn.現(xiàn)實(shí)世界的圖很容易被高度頂點(diǎn)(集線器)斷開(kāi)，可以通過(guò)尋找高度頂點(diǎn)和鄰居(輻條)，對(duì)其頂點(diǎn)進(jìn)行排序，遞歸地將一個(gè)圖分割成僅由集線器連接的超級(jí)集線器和超級(jí)輻條，快速地壓縮原始圖，以MDL的原則生成概要模型，該方法支持任何冪律圖上工作，而不需要任何領(lǐng)域特定的知識(shí)或者在圖上定義良好的自然排序以實(shí)現(xiàn)更好的排列.圖3是SlashBurn概要化1次之后的圖形，通過(guò)刪除集線器頂點(diǎn)創(chuàng)建許多較小的“輻條”和GCC(giant connected com-ponent)，集線器頂點(diǎn)獲得最低的ID，輻條中的頂點(diǎn)按照它們所屬的連接組件大小遞減順序獲得最高的ID即(9，16)，并且GCC獲得剩余的ID(2，8)，下一次迭代從GCC開(kāi)始.

Fig. 3 Graph summary with hub model 圖3 集線器模型

與SlashBurn類(lèi)似的有文獻(xiàn)[37],提出一種基于無(wú)損壓縮高度頂點(diǎn)的G-Dedensified方法，認(rèn)為高度頂點(diǎn)附近存在大量的冗余信息，引入公共的壓縮頂點(diǎn)去除多余的邊緣，加速查詢處理，問(wèn)題的關(guān)鍵在于如何尋找公共連接的高度頂點(diǎn).通常情況下將所有高度頂點(diǎn)鄰居劃分為2個(gè)集合，遵循MDL的原則使高度頂點(diǎn)和輸入頂點(diǎn)分開(kāi)，且確保輸入頂點(diǎn)包含所有高度頂點(diǎn)的輸出邊，稱之為“解密”操作.

SAGS(set-based approximate graph summariza-tion)[38]使用統(tǒng)一的局部敏感散列(unified locality sensitive Hash, ULSH)[39]和MDL來(lái)壓縮大型網(wǎng)絡(luò)，以進(jìn)行內(nèi)存處理，生成概要圖.在這項(xiàng)工作中，ULSH通過(guò)在頂點(diǎn)鄰域上執(zhí)行一組minhash函數(shù)來(lái)處理圖形，計(jì)算散列碼，然后聚合基于多個(gè)散列函數(shù)輸出相同的頂點(diǎn)，添加新的虛擬頂點(diǎn).

AGSUM(attribute graph summarization)[40]基于MDL最小化模型和模型數(shù)據(jù)，模型成本代價(jià)主要由3部分組成：頂點(diǎn)、屬性和頂點(diǎn)之間的鏈接.核心策略是通過(guò)貪心算法結(jié)合拓?fù)浣Y(jié)構(gòu)和屬性信息度量頂點(diǎn)相似性，結(jié)構(gòu)信息相似度則根據(jù)2跳頂點(diǎn)對(duì)進(jìn)行衡量，屬性相似度基于Jaccard相似度構(gòu)建，初始化時(shí)通過(guò)屬性傳播算法對(duì)原始圖初始化,基于貪心策略反復(fù)迭代合并使成本最小化，如圖4所示.圖4(a)為原始圖，圖4(b)為概要圖，其中不同標(biāo)簽的頂點(diǎn)分別被合并為超點(diǎn)，最后將原始圖劃分為3個(gè)子圖G1，G2，G3;圖4(c)為還原后的原始圖，由于概要化中可能導(dǎo)致結(jié)構(gòu)信息的丟失，重構(gòu)的原始圖具有一定的誤差率.

Fig. 4 AGSUM graph summary[40]圖4 AGSUM概要示意圖[40]

Fig. 5 Structural entropy and attribute entropy[41]圖5 結(jié)構(gòu)熵與屬性熵[41]

文獻(xiàn)[41]由信息論啟發(fā)，提出了統(tǒng)一熵模型S-Entropy和分區(qū)同質(zhì)性度量，核心思想是把屬性轉(zhuǎn)化為頂點(diǎn)，通過(guò)概率分布對(duì)其進(jìn)行編碼計(jì)算分區(qū)之間的熵差，再基于標(biāo)準(zhǔn)放松，根據(jù)用戶自身偏好，轉(zhuǎn)化為加權(quán)熵，最終產(chǎn)生精確同質(zhì)分區(qū)和近似同質(zhì)分區(qū).加權(quán)熵主要是由邊熵和頂點(diǎn)屬性熵組成,熵的計(jì)算方式為

(3)

圖5(a)表格表示了屬性熵的計(jì)算，超點(diǎn)S1內(nèi)含頂點(diǎn)v1,v2,v3,頂點(diǎn)具有屬性a1,a2,a3,a4,則超點(diǎn)S1屬性熵為1.85,超點(diǎn)S2的屬性熵為3.7，即表明S1內(nèi)部屬性相似度大于S2;右側(cè)則根據(jù)鄰居邊的頻數(shù)分布轉(zhuǎn)化為二進(jìn)制表示，S2超點(diǎn)到S1超點(diǎn)的平均邊數(shù)為10，其中2個(gè)頂點(diǎn)9條邊、2個(gè)頂點(diǎn)10條邊、1個(gè)頂點(diǎn)12條邊，轉(zhuǎn)化為直方圖，基于直方圖的視覺(jué)將9,10,11轉(zhuǎn)化為全1的二進(jìn)制向量，去除一樣的列，只關(guān)心其中的差異，計(jì)算結(jié)構(gòu)熵.

文獻(xiàn)[42]在文獻(xiàn)[34]的基礎(chǔ)上提出了最新的成本定義，添加了新的壓縮成本，創(chuàng)建一個(gè)原始圖的概要圖，通過(guò)成本模型重復(fù)選擇最優(yōu)頂點(diǎn)對(duì)合并.成本模型由概要成本和壓縮成本組成，基于貪心算法重復(fù)選擇最低總成本.成本模型為

(4)

其中,Costs(u)屬于概要成本，Costc(u)屬于壓縮成本，Costsc(u)選擇其中的最小值.如圖6所示，超點(diǎn)ID從90起標(biāo)記，觀察到頂點(diǎn)對(duì)(27,2)具有最大的壓縮率，彼此共享所有的鄰居頂點(diǎn)，當(dāng)超點(diǎn)90合并后，繼續(xù)根據(jù)成本模型選擇最優(yōu)壓縮頂點(diǎn)對(duì)(51,60),此次壓縮新增了多余的邊(60,24)，需要在較正列表中刪去此邊.

Fig. 6 Iterative steps of cost model[42]圖6 成本模型迭代步驟[42]

1.2 基于查詢優(yōu)化的圖概要

基于查詢優(yōu)化的圖概要以維持原始圖的特定結(jié)構(gòu)信息為主要目的，解決超大規(guī)模圖下針對(duì)某些查詢?nèi)蝿?wù)的快速響應(yīng)，支持現(xiàn)有或特定的圖形算法加速查詢，盡可能地減少磁盤(pán)的訪問(wèn)，得到精確的結(jié)果，降低平均誤差.

文獻(xiàn)[43]提出的層次聚類(lèi)GRASS(graph structure summarization)針對(duì)查詢效率，通過(guò)貪心法分組頂點(diǎn)，歸一化差異性，支持頂點(diǎn)的鄰接關(guān)系和特征向量中心查詢，并在誤差允許內(nèi)重構(gòu)原始圖:

(5)

其中,A(i，j)表示原始圖頂點(diǎn)(i，j)存在的邊.

文獻(xiàn)[44]提出一種基于質(zhì)量保證的超點(diǎn)合并策略S2A，給定期望的超點(diǎn)數(shù)量，使重建誤差最小化.這種針對(duì)如三角形或者子圖查詢計(jì)數(shù)進(jìn)行優(yōu)化的啟發(fā)式策略，可用于如Grass等概要化方法的改進(jìn).

SNAP和K-SNAP[45]是用于概要圖形的2種經(jīng)典模型，其核心思想首先基于頂點(diǎn)屬性對(duì)所有頂點(diǎn)進(jìn)行迭代分組，直到分組中的頂點(diǎn)屬性一樣，最終產(chǎn)生最大關(guān)系屬性圖,啟發(fā)式算法K-SNAP允許用戶控制概要化的精確度，通過(guò)不同層次的概要圖進(jìn)行查詢優(yōu)化，這2種圖形聚合與數(shù)據(jù)庫(kù)操作風(fēng)格類(lèi)似，引入了頂點(diǎn)分組的概念，并提供了2個(gè)啟發(fā)式算法(自上而下和自下而上)來(lái)評(píng)估SNAP.如圖7左側(cè)圖所示，每個(gè)頂點(diǎn)代表學(xué)生，學(xué)生具有性別、班級(jí)等屬性，學(xué)生之間包含朋友、同學(xué)的關(guān)系，SNAP操作生成右邊的概要圖，這個(gè)概要圖表明了4組學(xué)生及其關(guān)系，每個(gè)小組學(xué)生屬于同一性別且同一班級(jí)，直觀上說(shuō)，SNAP根據(jù)用戶選擇的屬性和頂點(diǎn)生成一個(gè)滿足以下條件的概要圖：該概要圖的頂點(diǎn)對(duì)應(yīng)于最大的兼容分組，該概要圖的邊緣關(guān)系滿足從原始圖R中推導(dǎo)出的群組關(guān)系.圖7右側(cè)圖顯示了根據(jù)屬性分組構(gòu)建的概要圖，但該方法在結(jié)構(gòu)一致性上缺乏更好的表現(xiàn).

Fig. 7 SNAP-graph summary[45]圖7 SNAP-概要化[45]

CANAL[46]在K-SNAP的基礎(chǔ)上，針對(duì)頂點(diǎn)屬性為連續(xù)值時(shí)，利用鏈接結(jié)構(gòu)和隱藏的信息實(shí)現(xiàn)自動(dòng)化分類(lèi)，評(píng)估概要圖的興趣度，幫助用戶自動(dòng)找出有意義的概要圖，而這一行為在K-SNAP中可能需要用戶對(duì)多個(gè)分辨率的概要圖進(jìn)行匯總.

存在一些特殊應(yīng)用背景的概要技術(shù)，查詢優(yōu)化只是其次要任務(wù)，例如關(guān)于隱私保護(hù)的概要化，一個(gè)零知識(shí)隱私框架(zero knowledge private， ZKP).文獻(xiàn)[47]在圖概要中使用ZKP保護(hù)用戶的個(gè)人隱私，引入了合成屬性，將拉普拉斯噪聲[48]標(biāo)度λ設(shè)置為與靈敏度和采樣誤差之和成正比，并且與ZKP隱私級(jí)別成反比，簡(jiǎn)化圖概要中ZKP機(jī)制的構(gòu)建和分析，生成概率圖.概率圖[49]將具有相同屬性值的頂點(diǎn)分組一起，提出一個(gè)概率圖概要化框架，當(dāng)中涉及復(fù)雜的概率推理，通過(guò)計(jì)算每個(gè)分組之間的期望值(所有鏈接邊的概率值之和)生成一個(gè)概要圖.其核心操作可使用R-DBMS中的關(guān)系運(yùn)算符來(lái)實(shí)現(xiàn).因?yàn)殛P(guān)系數(shù)據(jù)庫(kù)是一個(gè)已經(jīng)被證明可以擴(kuò)展到非常大的數(shù)據(jù)的完善和成熟的技術(shù)，這是其自身優(yōu)勢(shì)之一.概率圖定義了一組可能的實(shí)例PI.將概率圖G的所有可能實(shí)例的集合表示為E(PI).每個(gè)PI是從概率圖導(dǎo)出的正則圖，其中每個(gè)邊或者存在或者不存在.每個(gè)PI的存在概率計(jì)算為

Fig. 9 Topological model of incremental sketch[55]圖9 增量概要圖的拓?fù)淠Ｐ蚚55]

(6)

其中對(duì)于給定邊存在所有實(shí)例集合的概率和為1.

查詢隨時(shí)間動(dòng)態(tài)變化的大型復(fù)雜圖形數(shù)據(jù)面臨更多的挑戰(zhàn)，例如通過(guò)電話或社交網(wǎng)絡(luò)與其他人的通信模式、網(wǎng)絡(luò)服務(wù)器之間的連接、信息流動(dòng)、新聞傳播、信息在智能家居環(huán)境中的設(shè)備之間傳輸.目前，動(dòng)態(tài)圖的概要技術(shù)研究剛剛起步，采用的方案往往是將數(shù)據(jù)線性投影到保持?jǐn)?shù)據(jù)顯著特征低維空間.

頻率動(dòng)態(tài)圖概要具有3個(gè)特征：更小的次線性空間、線性構(gòu)建時(shí)間以及邊緣更新時(shí)恒定的維護(hù)成本，以便提升查詢效率性能.廣泛的做法是基于散列[50]或基于樣本的方法獨(dú)立處理每個(gè)流元素，而不用維護(hù)元素之間的連接.現(xiàn)有的算法假設(shè)查詢存在，建立索引加速，但只能解決臨時(shí)問(wèn)題，而不支持對(duì)圖流進(jìn)行多樣化和復(fù)雜的分析，例如CountMin[51]和Bottom-k[52]等工作受限于查詢數(shù)據(jù)假設(shè)存在，G-sketch[53]通過(guò)假設(shè)存在更好的劃分輸入圖流數(shù)據(jù)進(jìn)一步改善了CountMin.

由Tang等人[54]提出的TCM模型則適用于眾多圖流數(shù)據(jù)，其采用多個(gè)獨(dú)立的散列函數(shù)對(duì)流圖生成多個(gè)草圖，并滿足4個(gè)條件：1)概要圖S的尺寸遠(yuǎn)小于G；2)在線性時(shí)間內(nèi)構(gòu)造S；3)S的更新成本是恒定的；4)S滿足原始圖的結(jié)構(gòu)特征.如圖8所示，S1和S2是由2個(gè)獨(dú)立的散列函數(shù)生成的概要圖，當(dāng)執(zhí)行查詢頂點(diǎn)g到頂點(diǎn)b的權(quán)重時(shí)，2個(gè)概要圖均顯示為1，根據(jù)選取的聚合函數(shù)選擇最小權(quán)值為1，實(shí)踐證明使用多個(gè)獨(dú)立散列函數(shù)能提高查詢的準(zhǔn)確性.

TCM模型在查詢優(yōu)化方面比基于頻率計(jì)數(shù)或者單一樣本的概要圖更優(yōu)越，同時(shí)在針對(duì)各種類(lèi)型的流數(shù)據(jù)處理時(shí)，其自身具備更好的適用性和普遍性.

Bandyopadhyay等人[55]提出的一種基于局部鄰域最小散列的可擴(kuò)展概要圖，使用k個(gè)散列函數(shù)維護(hù)一個(gè)最小鄰居頂點(diǎn)的采樣子圖，對(duì)于每一個(gè)散列函數(shù)選取具有最小散列值的數(shù)據(jù)作為局部樣本,濾除單個(gè)數(shù)據(jù)流中的頻繁更新對(duì)采樣偏斜的影響.然后,對(duì)于相同散列函數(shù)產(chǎn)生的樣本,選取具有最小散列值的樣本作為全局樣本,完成局部樣本集在中心頂點(diǎn)的合并,濾除在分布頂點(diǎn)上的重復(fù)更新對(duì)樣本偏斜的影響，同時(shí)可以導(dǎo)出圖結(jié)構(gòu)的無(wú)偏估計(jì)量，例如三角形.如圖9所示，散列函數(shù)的結(jié)果H1:1，5，2，4，3；H2:4，1，5，2，3；此時(shí)更新矩陣Mk和計(jì)數(shù)表C，當(dāng)新來(lái)一條邊(i，j)時(shí)，判斷H1(j)

1.3 基于模式可視化的圖概要

基于可視化的概要方法通過(guò)刪除或合并不重要的頂點(diǎn)或邊緣對(duì)原始圖進(jìn)行高度的抽象描述，產(chǎn)生一個(gè)可直觀理解的概要圖，幫助用戶在特定應(yīng)用場(chǎng)景下理解分析原始圖的實(shí)際意義.這里的概要圖由原始頂點(diǎn)和邊緣的子集組成.通常，基于可視化[56]生成概要圖主要有基于頂點(diǎn)邊緣的可視化和基于模式結(jié)構(gòu)可視化2種策略.

基于頂點(diǎn)邊緣的可視化是通過(guò)特定頂點(diǎn)的語(yǔ)義對(duì)網(wǎng)絡(luò)進(jìn)行剪枝、結(jié)構(gòu)抽象或性質(zhì)過(guò)濾，比較典型的有OntoVis[57]，一種依靠頂點(diǎn)過(guò)濾的視覺(jué)分析工具，用于分析不同的大型異構(gòu)社交網(wǎng)絡(luò)，使用與社交網(wǎng)絡(luò)相關(guān)聯(lián)的本體中的信息從語(yǔ)義上修剪大的異構(gòu)網(wǎng)絡(luò)[58]，獲得語(yǔ)義抽象.除語(yǔ)義抽象外，OntoVis允許用戶進(jìn)行結(jié)構(gòu)抽象和重要性過(guò)濾，使用統(tǒng)計(jì)度量來(lái)評(píng)估頂點(diǎn)類(lèi)型之間的連通性和相關(guān)性，以使大型網(wǎng)絡(luò)易于管理分析.

文獻(xiàn)[59]提出了一種無(wú)監(jiān)督的機(jī)制，可用于自我中心信息抽象，根據(jù)網(wǎng)絡(luò)子結(jié)構(gòu)自動(dòng)篩選，即k-hop鄰域漸進(jìn)地構(gòu)建了一個(gè)自我中心抽象圖，允許用戶可視化結(jié)果.針對(duì)與OntoVis相同類(lèi)型的圖形，采用邊緣而不是頂點(diǎn)過(guò)濾，提出了一種無(wú)監(jiān)督機(jī)制建立中心抽象圖.

虛擬頂點(diǎn)挖掘(virtual node miner, VNM)[60]是Web圖形的有損壓縮方案，VNM使用頻繁挖掘方法通過(guò)將每個(gè)頂點(diǎn)的出入邊作為事務(wù)項(xiàng)集來(lái)提取有意義的連接.對(duì)于每個(gè)循環(huán)模式，它從其頂點(diǎn)中刪除鏈接，并在S中生成一個(gè)新的頂點(diǎn)(虛擬頂點(diǎn))，添加一個(gè)出邊，從而允許增量圖表更新.相關(guān)地，引入了主題簡(jiǎn)化的思想來(lái)增強(qiáng)網(wǎng)絡(luò)可視化，其中頂點(diǎn)和鏈接的常見(jiàn)模式被緊湊的字形替換以幫助可視化和了解實(shí)體及其屬性之間復(fù)雜的關(guān)系，如圖10所示，原始圖共30條邊，添加VN后只需要11條邊，并完整地保留原始圖信息.

基于模式結(jié)構(gòu)的可視化是面向圖形挖掘應(yīng)用領(lǐng)域和用戶興趣形成的一些特殊的圖形概要方法，為了滿足特定的需求，以一個(gè)或多個(gè)固定的結(jié)構(gòu)作為核心特征合并成超頂點(diǎn)，尋找“異?！蹦Ｊ剑ㄟ^(guò)可視化揭露實(shí)體屬性的特征關(guān)系.

Motif[61]是一種依靠圖簡(jiǎn)化技術(shù)，利用網(wǎng)絡(luò)中的重復(fù)圖案來(lái)減少可視化的復(fù)雜性，提高可閱讀性.該技術(shù)采取易于理解的結(jié)構(gòu)來(lái)替換網(wǎng)絡(luò)中的圖案，結(jié)構(gòu)必須具有3個(gè)特征：1)需要較少的屏幕空間，確?？梢暬拈喿x性;2)易于理解的結(jié)構(gòu)性;3)可展示隱藏的關(guān)系.文獻(xiàn)[61]中提出2個(gè)結(jié)構(gòu)：扇形圖案和并行圖案，并設(shè)計(jì)有效的算法進(jìn)行可視化，如圖11所示：

Fig. 11 Motif: graph summary of sector structure[61]圖11 Motif：扇形結(jié)構(gòu)的概要化[61]

文獻(xiàn)[62]基于MDL原理，將原始圖拆分為多個(gè)可能重復(fù)的子圖，再與6種基本結(jié)構(gòu)詞匯表匹配壓縮，分別是星、鏈、完全團(tuán)、近似團(tuán)、二分核、近似二分核.每一步壓縮的過(guò)程中追求代價(jià)最小化，最后選擇多個(gè)算法結(jié)合提出的質(zhì)量度量依次選擇候選結(jié)構(gòu)，生成最適合的概要模型,圖12顯示了維基百科的編輯網(wǎng)絡(luò)圖的可視化結(jié)果，旨在發(fā)現(xiàn)用戶爭(zhēng)議分歧最大的相關(guān)主題.

Fig. 12 Wikipedia editor conflict war visualization[62]圖12 維基百科編輯-沖突戰(zhàn)爭(zhēng)可視化[62]

針對(duì)動(dòng)態(tài)圖，基于模式挖掘的概要方法從時(shí)間數(shù)據(jù)中提取有意義的模式.TIME-C[63]描述了具有1組重要時(shí)間結(jié)構(gòu)的大型動(dòng)態(tài)圖.文獻(xiàn)[63]的作者將時(shí)間圖概要問(wèn)題正式轉(zhuǎn)化為信息理論優(yōu)化問(wèn)題，其目標(biāo)是確定時(shí)間行為的局部靜態(tài)結(jié)構(gòu)，最小化動(dòng)態(tài)圖的全局描述長(zhǎng)度.它引入了很多基于時(shí)間行為的詞典(閃爍、周期、單詞)，主要分為4步：1)識(shí)別每個(gè)時(shí)間戳中的靜態(tài)結(jié)構(gòu);2)使用靜態(tài)詞典標(biāo)記它們;3)鏈接在一起查找時(shí)間結(jié)構(gòu);4)時(shí)間詞典標(biāo)記它們;5)選擇最小化描述時(shí)間成本的時(shí)間結(jié)構(gòu).縫合靜態(tài)結(jié)構(gòu)對(duì)應(yīng)于進(jìn)化跟蹤，其通過(guò)迭代奇異值分解(SVD)處理以找到潛在的時(shí)間相干結(jié)構(gòu)，然后利用余弦相似性度量所發(fā)現(xiàn)的結(jié)構(gòu)的時(shí)間相干性.

1.4 基于影響擴(kuò)散的圖概要

Fig. 13 Cluster graph of COARSENET[67]圖13 COARSENET的聚類(lèi)圖[67]

影響和擴(kuò)散趨勢(shì)分析是圖挖掘長(zhǎng)期研究的重點(diǎn)，其本質(zhì)是隨著時(shí)間演變，如何在動(dòng)態(tài)網(wǎng)絡(luò)中總結(jié)影響擴(kuò)散的主要過(guò)程.基于影響擴(kuò)散的圖概要旨在尋找原始大圖中影響力的動(dòng)態(tài)描述，方便理解影響傳播的模式，主要通過(guò)概要化過(guò)程中維持優(yōu)化與應(yīng)用相關(guān)的信息實(shí)現(xiàn).

影響和擴(kuò)散過(guò)程本質(zhì)上是時(shí)間的演變對(duì)社會(huì)網(wǎng)絡(luò)的影響.OSNet[64]總結(jié)了動(dòng)態(tài)圖中有趣的擴(kuò)散過(guò)程.輸入時(shí)間有序的交互流，表示為標(biāo)記頂點(diǎn)間的無(wú)向邊.OSNet的目標(biāo)是在有向圖中捕獲級(jí)聯(lián)(即擴(kuò)散過(guò)程，如新聞傳播)，從而顯示動(dòng)態(tài)的流動(dòng).輸出概要圖由原始輸入圖中“有趣”頂點(diǎn)的子圖組成，其中將興趣定義為頂點(diǎn)擴(kuò)散程度的線性組合(即擴(kuò)散過(guò)程中感染的頂點(diǎn)數(shù)量)，以及最大“傳播半徑”(即從擴(kuò)散過(guò)程根到頂點(diǎn)的路徑長(zhǎng)度).OSNet的關(guān)鍵思想是:1)構(gòu)建傳播樹(shù);2)通過(guò)其熵和閾值來(lái)計(jì)算摘要的特征表現(xiàn).文獻(xiàn)[65]側(cè)重于了解社會(huì)團(tuán)體隨著時(shí)間推移的集體活動(dòng).該文作者提出了通過(guò)多圖(用戶照片、用戶評(píng)論、照片標(biāo)簽和評(píng)論標(biāo)簽圖)非負(fù)矩陣分解[66]來(lái)提取活動(dòng)主題，以獲得用戶和概念的潛在空間.潛在空間中的頂級(jí)用戶和術(shù)語(yǔ)定義了與活動(dòng)主題相對(duì)應(yīng)的“重要”動(dòng)作，應(yīng)用余弦相似性來(lái)隨著時(shí)間的演變跟蹤主題.

一種近線性時(shí)間算法COARSENET[67]使用評(píng)分技術(shù)反復(fù)合并2個(gè)相鄰頂點(diǎn)對(duì)獲得加權(quán)圖，尋找對(duì)網(wǎng)絡(luò)擴(kuò)散性能影響不大的邊緣，使得概要圖保留其主要性質(zhì)，實(shí)驗(yàn)表明其空間縮小至原始圖的10%而不會(huì)丟失主要信息.為了表示網(wǎng)絡(luò)的擴(kuò)散特性，最近的研究表明當(dāng)鄰接矩陣的第一特征值為與原始圖的第一特征值相似時(shí)表明它們是自然相近的，當(dāng)合并頂點(diǎn)對(duì)時(shí)需要重新對(duì)邊進(jìn)行權(quán)值計(jì)算，權(quán)值的更新取其刪減邊緣和鄰接邊的平均值，選擇使特征值變化最小的頂點(diǎn)(閾值限制)對(duì)進(jìn)行合并.如圖13所示，計(jì)算當(dāng)前原始圖每一條邊的評(píng)分，當(dāng)特征值變化低于閾值時(shí)用實(shí)線框標(biāo)注，視為一次成功的合并，高于閾值時(shí)則用虛線框標(biāo)注，視為一次失敗的合并，其中頂點(diǎn)4,5,8,9,12,15合并為超點(diǎn)，6,11合并為超點(diǎn)，右側(cè)則顯示了一次迭代后的概要圖.

文獻(xiàn)[68]基于圖譜理論提出了一個(gè)圖概要框架，對(duì)于大型圖而言，具有相近光譜特性的網(wǎng)絡(luò)圖具有相似的結(jié)構(gòu)模式，并提出光譜距離來(lái)度量概要圖與原始圖的結(jié)構(gòu)相似性.其中光譜距離定義為

(7)

其中,λ為歸一化拉普拉斯矩陣的特征值，光譜距離將粗化圖的特征值與原始網(wǎng)絡(luò)的頭尾進(jìn)行比較，參數(shù)l則控制匹配的位置.

Fig. 14 Difference between VEGAS and traditional clustering圖14 VEGAS聚類(lèi)和傳統(tǒng)的圖聚類(lèi)的區(qū)別

VEGAS[69]是一個(gè)典型的針對(duì)引文網(wǎng)絡(luò)圖的最大化影響分析的概要方法，其核心算法是基于k-means，通過(guò)矩陣分解生成概要圖，并支持基于流的影響模式，支持豐富的屬性信息擴(kuò)展.為了流影響的最大化，生成的頂點(diǎn)簇內(nèi)的一致性不再取決于密集的內(nèi)部連接，而是由同一簇中的高度頂點(diǎn)拓?fù)湎嗨菩詠?lái)定義.在這個(gè)目標(biāo)中，跨越群集的邊緣會(huì)比傳統(tǒng)方法更多，從而突出描繪影響模式的流程.如圖14所示，假設(shè)原始圖存在統(tǒng)一的權(quán)值，原始圖中虛線框內(nèi)頂點(diǎn)聚類(lèi)為概要圖中的正方形超點(diǎn)，超點(diǎn)上方標(biāo)記了影響流的大小，左側(cè)是傳統(tǒng)的圖聚類(lèi)，導(dǎo)致了更大的影響內(nèi)流，其值是0.8，而右側(cè)的VEGAS聚類(lèi)，則更好地表示了群內(nèi)和群間的影響流.

1.5 圖概要算法小結(jié)

為了綜合比較主流的圖概要方法，本節(jié)對(duì)1.1～1.4節(jié)提到的各類(lèi)算法從輸入圖的類(lèi)型、結(jié)構(gòu)、參數(shù)、輸出圖等進(jìn)行綜合比較，比較結(jié)果如表1所示：

Table 1 Comparison of Graph Summarization Methods表1 圖概要方法對(duì)比

Notes:“√” stands for support; “×” stands for non-support.

表1主要從輸入圖的類(lèi)型區(qū)分加權(quán)圖、無(wú)權(quán)圖、有向圖、無(wú)向圖、同質(zhì)圖、異構(gòu)圖以及是否需要給定參數(shù)和時(shí)間復(fù)雜度來(lái)區(qū)分各個(gè)圖概要技術(shù)，其中√代表支持，×代表不支持.

1) 大部分主流概要技術(shù)應(yīng)用于無(wú)向無(wú)權(quán)的簡(jiǎn)單圖數(shù)據(jù)，針對(duì)加權(quán)和異構(gòu)圖的概要技術(shù)較少.

2) 在基于空間壓縮的圖概要技術(shù)中，支持加權(quán)圖的概要技術(shù)一般采用圖聚類(lèi)的思想，但能勝任異構(gòu)網(wǎng)絡(luò)概要化的研究方法比較匱乏.

3) 在查詢優(yōu)化的圖概要技術(shù)中尚未考慮到加權(quán)圖的查詢，大部分方法的算法復(fù)雜度是非線性的，只解決了某些特定查詢的優(yōu)化，在動(dòng)態(tài)圖流上圖概要查詢優(yōu)化技術(shù)取得不小的進(jìn)展，領(lǐng)先于其他應(yīng)用領(lǐng)域的動(dòng)態(tài)概要技術(shù).

4) 影響分析的圖概要技術(shù)除了OSNet外，都是針對(duì)有向圖，無(wú)需輸入?yún)?shù)，能客觀地分析網(wǎng)絡(luò)結(jié)構(gòu)中頂點(diǎn)間的影響關(guān)系,實(shí)際應(yīng)用中影響分析擴(kuò)散傳播往往需要考慮時(shí)間粒度.

5) 模式可視化的概要技術(shù)不支持加權(quán)的圖數(shù)據(jù)，除了VNM算法外，都是針對(duì)無(wú)向圖，算法TIME-C和Moitif能同時(shí)處理同構(gòu)圖和異構(gòu)圖.

2 分布式環(huán)境下的圖概要化

隨著圖數(shù)據(jù)規(guī)模的擴(kuò)大、屬性的多樣化和結(jié)構(gòu)的復(fù)雜化，有學(xué)者開(kāi)始致力于分布式圖概要的研究.當(dāng)前關(guān)于分布式下圖形概要化的工作剛剛起步，相關(guān)文獻(xiàn)較少.分布式圖概要主要面臨3個(gè)問(wèn)題：

1) 由于頂點(diǎn)和邊緣分布在不同的設(shè)備內(nèi)存中，集中式圖形摘要算法中看似簡(jiǎn)單的操作需要在分布式環(huán)境中跨多個(gè)頂點(diǎn)的消息傳遞和仔細(xì)協(xié)調(diào).

2) 集中式算法不需要擔(dān)心計(jì)算如何分布，但是一個(gè)好的分布式圖表匯總方法應(yīng)該在不同的機(jī)器上完全分配計(jì)算，以實(shí)現(xiàn)高效的并行化.

3) 計(jì)算量和通信成本成為分布式圖概要的主要因素.

文獻(xiàn)[75]首次提出了分布式下的圖概要，在Apache Graph上實(shí)現(xiàn)了3種分布式算法：1)第1種對(duì)應(yīng)于文獻(xiàn)[34]的集中式貪心策略，尋找超級(jí)頂點(diǎn)對(duì)，但造成了大量的通信和計(jì)算成本.2)第2種采用隨機(jī)策略尋找頂點(diǎn)對(duì)，但隨機(jī)性負(fù)面地影響了概要的準(zhǔn)確性.3)第3種為Dist-LSH，采用Striped-minhash的技術(shù)，新增了權(quán)值歸一化處理，快速比較2個(gè)集合的相似度，直接找出合適的候選人進(jìn)行檢查，從而完全消除了與不必要檢查相關(guān)的計(jì)算和網(wǎng)絡(luò)成本.如圖15所示，將權(quán)重向量{ai:wi}作為輸入除以權(quán)值范圍[0,1]進(jìn)行歸一化處理，以頂點(diǎn)個(gè)數(shù)作為桶數(shù)進(jìn)行區(qū)域劃分，如圖15中w1=0.53，給定集合A和B，在每個(gè)縱軸上應(yīng)用不同的散列函數(shù)，如果散列到同一桶中則視為命中1次，總的命中次數(shù)越高則代表集合的相似性越高，即采用這種方案尋找最相似的加權(quán)候選集.

Fig. 15 Normalization of Striped-minhash weights圖15 R=5時(shí)Striped-minhash權(quán)值歸一化

文獻(xiàn)[76]提出了一種新的度量主干的概念來(lái)提高大型圖形數(shù)據(jù)的分析效率，度量主干即為保留權(quán)值的最短路徑的最小子圖，用于替代原始圖精確或近似進(jìn)行各個(gè)指標(biāo)的度量.計(jì)算度量主干需要解決所有頂點(diǎn)對(duì)的最短路徑問(wèn)題 (all-pairs-shortest-paths， APSP)問(wèn)題，該文獻(xiàn)通過(guò)算法避免APSP并證明了半度量子圖依然能提升計(jì)算性能.同時(shí)，可作為一種有損壓縮機(jī)制，半度量邊數(shù)量作為存儲(chǔ)的邊.最后給出了算法在Apache Graph上的分布式實(shí)現(xiàn):1)檢測(cè)第1階半度量邊;2)迭代標(biāo)記局部度量邊;3)標(biāo)記所有剩余的度量邊.

3 部分圖概要算法實(shí)驗(yàn)

圖的概要化是一個(gè)相對(duì)廣泛的概念，其核心技術(shù)本身與用戶的興趣和應(yīng)用目的緊密聯(lián)系，導(dǎo)致不同應(yīng)用領(lǐng)域的概要技術(shù)無(wú)法客觀地對(duì)比，原因在于解決主要問(wèn)題的技術(shù)方案不同，不同維度的評(píng)價(jià)指標(biāo)無(wú)法展示各個(gè)圖概要技術(shù)的優(yōu)越性.

相對(duì)而言，基于空間壓縮的概要圖技術(shù)，核心任務(wù)基本一致，對(duì)比的指標(biāo)相同.本文在無(wú)屬性的圖上選取了經(jīng)典的基于MDL壓縮的MDL-R[34],REF[72],GBASE[73],GRAC[29]四種算法進(jìn)行了實(shí)驗(yàn)性能的比較.

1) MDL-R.第1個(gè)基于MDL的壓縮概要技術(shù)，雖然在大型圖數(shù)據(jù)下效率偏低，但提供了高質(zhì)量的概要圖.

2) REF.一個(gè)流行的Web壓縮技術(shù)，該方法由2個(gè)邏輯部分組成:第1部分減少每個(gè)頂點(diǎn)鄰居列表的大??；第2部分使用復(fù)雜的比特級(jí)編碼進(jìn)行壓縮.為了實(shí)驗(yàn)對(duì)比的公平性，去除比特級(jí)編碼運(yùn)行該算法.

3) GBASE.一個(gè)針對(duì)大型圖存儲(chǔ)壓縮的查詢優(yōu)化系統(tǒng)方案，本研究只采用其壓縮技術(shù)——塊存儲(chǔ)編碼，將鄰接矩陣轉(zhuǎn)換為二進(jìn)制字符串.

4) GRAC.加權(quán)圖的圖聚類(lèi)算法，將給定的加權(quán)圖進(jìn)行劃分使得權(quán)重最小.

實(shí)驗(yàn)的數(shù)據(jù)集為CNR，RouteView，Wordnet，F(xiàn)acebook四種數(shù)據(jù)集.

1) CNR.該網(wǎng)絡(luò)是從CNR域網(wǎng)爬蟲(chóng)提取的，由有向邊轉(zhuǎn)化為無(wú)向邊，最大的CNR數(shù)據(jù)集具有10萬(wàn)頂點(diǎn)和40萬(wàn)余條邊.

2) RouteView.這是一個(gè)表示Internet拓?fù)湎到y(tǒng)的模型，這個(gè)數(shù)據(jù)集是由俄勒崗大學(xué)路線視圖項(xiàng)目組收集，大約具有1萬(wàn)個(gè)頂點(diǎn)和3萬(wàn)條邊.

3) Wordnet.自然語(yǔ)言處理應(yīng)用程序中常用的英語(yǔ)單詞的大型詞匯數(shù)據(jù)庫(kù)，將每個(gè)單詞對(duì)應(yīng)于1個(gè)頂點(diǎn)，如果每個(gè)單詞具有相近或包含或前置的關(guān)系，則頂點(diǎn)之間存在邊，該圖大約有7萬(wàn)個(gè)頂點(diǎn)和12萬(wàn)條邊.

4) Facebook.該數(shù)據(jù)集是2005年康奈爾大學(xué)從自身大學(xué)社區(qū)提取的Facebook網(wǎng)絡(luò)圖，有1.5萬(wàn)頂點(diǎn)和14萬(wàn)條邊，每個(gè)頂點(diǎn)存在邊即表示學(xué)生之間為朋友關(guān)系.

Fig. 16 Experiment on information retention rate and compression ratio of non-attribute graph圖16 無(wú)屬性圖信息保持率和壓縮率的對(duì)比實(shí)驗(yàn)

圖16顯示了無(wú)屬性圖上4種算法的信息保持率和壓縮率的實(shí)驗(yàn)結(jié)果.信息保持率上，GRAC的性能相對(duì)優(yōu)越，值得關(guān)注的是REF在Facebook數(shù)據(jù)集上幾乎沒(méi)有丟失信息，但結(jié)合壓縮率指標(biāo)可知，該現(xiàn)象是由壓縮效果不理想引起.對(duì)于另外2種算法，概要化過(guò)程中為了追求一定的壓縮率都采取了誤差閾值進(jìn)行擴(kuò)展：MDL-R在各類(lèi)數(shù)據(jù)集上均可以取得最大化壓縮的結(jié)果，主要原因在于根據(jù)MDL信息理論，其在迭代壓縮過(guò)程中始終基于貪心策略尋找最大化壓縮頂點(diǎn)，而GRAC的壓縮效果相對(duì)最差， Facebook數(shù)據(jù)集由于其頂點(diǎn)和邊緣的高度比，壓縮性明顯最差.值得關(guān)注的是GRAC在該數(shù)據(jù)集上效果最好，其核心是基于聚類(lèi)的分區(qū)思想，在這種高度密集的圖數(shù)據(jù)上更有優(yōu)勢(shì).

圖17是針對(duì)無(wú)屬性圖的運(yùn)行時(shí)間比較.MDL-R時(shí)間開(kāi)銷(xiāo)最大，因?yàn)椴捎秘澬牟呗?，重心永遠(yuǎn)關(guān)注在如何全局最大化降低成本上，MDL-R可以擴(kuò)展基于局部最優(yōu)的隨機(jī)策略進(jìn)行概要化，減少時(shí)間開(kāi)銷(xiāo)的增大，其生成的概要模型忽略了頂點(diǎn)存儲(chǔ)的自身信息.在時(shí)間代價(jià)上GRAC表現(xiàn)最為優(yōu)異，主要通過(guò)權(quán)值相同聚類(lèi)降低有限的成本，但缺陷在于需要重復(fù)給定分類(lèi)參數(shù)，尋找合適的壓縮率.

Fig. 17 Experiments on time cost of non-attributed graphs圖17 無(wú)屬性圖時(shí)間代價(jià)的對(duì)比實(shí)驗(yàn)

在屬性圖上進(jìn)行了實(shí)驗(yàn)，選取壓縮率、屬性熵[77]以及時(shí)間代價(jià)進(jìn)行對(duì)比.算法選擇SAC[74]，K-SNAP[45]，AGSUM[40]，S-Entropy[41]這4種算法.

1) SAC.一種針對(duì)屬性圖的聚類(lèi)算法，通過(guò)隨機(jī)游走距離度量屬性相似性和結(jié)構(gòu)相似性.

2) K-SNAP.第1個(gè)基于用戶屬性分組進(jìn)行概要技術(shù)的經(jīng)典方案.

3) AGSUM.在K-SNAP基礎(chǔ)上進(jìn)一步優(yōu)化了結(jié)構(gòu)一致性的壓縮.

4) S-Entropy.是一種基于屬性熵和結(jié)構(gòu)熵的統(tǒng)一模型,產(chǎn)生近似同質(zhì)分區(qū).

數(shù)據(jù)集采用Political Books(PB)和DBLP[78]數(shù)據(jù)集.

1) Political Books(PB).政治家的博客數(shù)據(jù)集，具有1 500頂點(diǎn)、2萬(wàn)條邊和3個(gè)屬性，其中平均度8.

2) DBLP.是計(jì)算機(jī)領(lǐng)域內(nèi)以作者為核心的一個(gè)計(jì)算機(jī)類(lèi)英文文獻(xiàn)的數(shù)據(jù)庫(kù)系統(tǒng)，按年代列出了作者科研成果、國(guó)際期刊和會(huì)議等發(fā)表的論文.實(shí)驗(yàn)選擇的數(shù)據(jù)集包括3個(gè)DBLP數(shù)據(jù)集，DBLP1只包含選定的數(shù)據(jù)庫(kù)出版物，具有7 000頂點(diǎn)和2萬(wàn)條邊，DBLP2新增了AL出版物，具有1.5萬(wàn)個(gè)頂點(diǎn)和3.8萬(wàn)條邊，DBLP3包含了所有會(huì)議和期刊的出版物，具有10萬(wàn)頂點(diǎn)和24萬(wàn)條邊.

圖18顯示了4種圖概要技術(shù)在屬性圖上壓縮率和信息熵的實(shí)驗(yàn).在圖18(b)熵的指標(biāo)上K-SNAP性能最好，主要原因在于K-SNAP單純通過(guò)頂點(diǎn)的屬性進(jìn)行概要匯總，未考慮網(wǎng)絡(luò)的結(jié)構(gòu)，因此結(jié)構(gòu)性能上表現(xiàn)最差，壓縮率最高；而AGSUM充分考慮了屬性和結(jié)構(gòu)的一致性，生成了緊湊的概要圖，壓縮率降低，熵比較大是因?yàn)闋奚藢傩缘囊恢滦?；SAC是基于距離的一般聚類(lèi)方法，將屬性頂點(diǎn)轉(zhuǎn)化為增廣頂點(diǎn)，導(dǎo)致不同屬性的頂點(diǎn)放在一起從而產(chǎn)生較高的熵；S-Entropy基于熵的維度平衡結(jié)構(gòu)和屬性一致性，概要圖的結(jié)構(gòu)性能降低.

Fig. 18 Experiments on entropy and compression ratio of attribute graph圖18 屬性圖信息熵和壓縮率的對(duì)比實(shí)驗(yàn)

由圖19可知，K-SNAP時(shí)間開(kāi)銷(xiāo)最低，主要原因是只考慮一個(gè)維度的概要化，計(jì)算量明顯低于其他方法；S-Entropy比其他性能更為優(yōu)異.隨著數(shù)據(jù)集的增大，S-Entropy的時(shí)間性能更接近線性增長(zhǎng)，表明了該技術(shù)在大型數(shù)據(jù)集上良好的擴(kuò)展性，相比較AGSUM，S-Entropy更重視屬性的一致性，對(duì)于結(jié)構(gòu)熵的度量缺乏更多有力的說(shuō)明，這也是概要技術(shù)評(píng)價(jià)需要考慮的標(biāo)準(zhǔn)之一.

Fig. 19 Experiments on time cost of attribute graph圖19 屬性圖時(shí)間代價(jià)的對(duì)比實(shí)驗(yàn)

4 圖概要應(yīng)用

隨著互聯(lián)網(wǎng)的迅速發(fā)展，實(shí)際生活中圖數(shù)據(jù)量不斷增加，研究者識(shí)別大規(guī)模圖數(shù)據(jù)的模式和隱藏意義的困難持續(xù)增加，從而影響決策過(guò)程.圖概要技術(shù)為理解和識(shí)別圖數(shù)據(jù)中的結(jié)構(gòu)和意義提供了可能.圖概要的應(yīng)用與現(xiàn)實(shí)生活緊密聯(lián)系、息息相關(guān)，主要有5個(gè)方面的應(yīng)用領(lǐng)域:

1) 減少數(shù)據(jù)量和存儲(chǔ)空間.現(xiàn)實(shí)世界圖形數(shù)據(jù)集往往極為龐大，例如Facebook的社交網(wǎng)絡(luò)超過(guò)30億的用戶，每天郵件的發(fā)送投遞超過(guò)1 000億，這些應(yīng)用所產(chǎn)生的圖數(shù)據(jù)已經(jīng)超出內(nèi)存的限制，大多數(shù)圖算法無(wú)法直接作用于原始圖去提煉潛在的結(jié)構(gòu)特征.圖概要技術(shù)下的社交網(wǎng)絡(luò)圖具有更小的空間，且讓研究者在更高層次對(duì)原始圖進(jìn)行分析研究，準(zhǔn)確揭露隱藏結(jié)構(gòu).

2) 圖數(shù)據(jù)的查詢優(yōu)化.大量通用的圖數(shù)據(jù)查詢算法在解決龐大的復(fù)雜數(shù)據(jù)圖時(shí)面臨著效率低下、準(zhǔn)確性降低的弊端，特定的概要技術(shù)可以極大提高查詢的效率和準(zhǔn)確性，例如社交網(wǎng)絡(luò)圖上最經(jīng)典的查詢可能詢問(wèn)2個(gè)頂點(diǎn)是否存在邊或者路徑.這樣的查詢通過(guò)鄰接矩陣概要化技術(shù)可以比最先進(jìn)的圖查詢算法提速50倍，減少平均錯(cuò)誤率.其他類(lèi)似的提高查詢效率的有三角形查詢、權(quán)重估計(jì)等.然而，針對(duì)常見(jiàn)的查詢尚缺乏能取得優(yōu)化效果的通用型圖概要技術(shù).

3) 可視化分析.在交互式圖形界面領(lǐng)域，圖概要技術(shù)作為可視化的重要手段，解決原始圖過(guò)大而無(wú)法加載到屏幕的弊端，幫助用戶直觀地理解原始圖的結(jié)構(gòu)特征，加速分析.比較經(jīng)典的可視化技術(shù)，通過(guò)結(jié)合用戶自身的興趣結(jié)構(gòu)，給定一些特殊的結(jié)構(gòu)去壓縮原始圖，例如文獻(xiàn)[61]通過(guò)一些特定詞匯結(jié)構(gòu)針對(duì)維基百科編輯圖進(jìn)行可視化，旨在尋找用戶分歧較大的主題，這往往能發(fā)現(xiàn)許多額外的有趣現(xiàn)象.

4) 影響分析和擴(kuò)散.部分文獻(xiàn)通過(guò)圖概要技術(shù)，試圖尋找大型圖中影響力的動(dòng)態(tài)擴(kuò)散模式，以便理解影響傳播的模式和重要條件，一般結(jié)合實(shí)際背景維持一些與影響有關(guān)的全局因子并捕捉變化模式，經(jīng)典應(yīng)用有網(wǎng)絡(luò)作品的影響力分析[68]、社交圖譜的概要化[79]、圖表抽象從模擬異構(gòu)犯罪數(shù)據(jù)集中提取影響流、高效識(shí)別犯罪團(tuán)伙.

5) 噪聲過(guò)濾和隱私保護(hù).真實(shí)的圖數(shù)據(jù)通常是大規(guī)模、具有很多噪聲的數(shù)據(jù)，例如錯(cuò)誤的連接或者標(biāo)簽屬性，這種數(shù)據(jù)阻礙了分析，隱藏了重要信息，增加了數(shù)據(jù)工作的處理量.概要化技術(shù)有利于濾除噪聲，揭示隱藏模式.同樣，針對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)圖的真實(shí)信息，概要技術(shù)可以濾出與應(yīng)用需求無(wú)關(guān)的部分用戶敏感信息，加強(qiáng)對(duì)用戶的隱私保護(hù)[49].

5 存在的問(wèn)題及挑戰(zhàn)

近年來(lái)，盡管涌現(xiàn)了許多圖數(shù)據(jù)概要方面的研究工作，但該領(lǐng)域仍然是新興的，需要更多的深入研究，目前尚面臨許多問(wèn)題和挑戰(zhàn)：

1) 圖概要化評(píng)價(jià)標(biāo)準(zhǔn)的確立[80-81].圖數(shù)據(jù)的概要化是一個(gè)相對(duì)廣泛的概念，尚沒(méi)有明確的定義，其本身是依賴于用戶的興趣和應(yīng)用需求，不同應(yīng)用領(lǐng)域的概要技術(shù)無(wú)法直觀地對(duì)比，因此缺乏統(tǒng)一標(biāo)準(zhǔn)的概要評(píng)估技術(shù).如果概要化的目的是為了解決存儲(chǔ)空間的限制，可以采用壓縮率、信息保持率等評(píng)價(jià)標(biāo)準(zhǔn)；當(dāng)概要化是為了加速圖形算法的查詢效率，則評(píng)估的標(biāo)準(zhǔn)應(yīng)是查詢時(shí)間、準(zhǔn)確度等；當(dāng)概要化是為了圖的可視化，則評(píng)價(jià)指標(biāo)更加難以度量.本文調(diào)查表明，應(yīng)用背景和目的需求相近時(shí)的圖概要技術(shù)，才能依照統(tǒng)一的評(píng)價(jià)指標(biāo)衡量算法的優(yōu)劣，例如本文的實(shí)驗(yàn)針對(duì)空間壓縮的應(yīng)用需求，壓縮率、信息保持率以及時(shí)間代價(jià)可以作為衡量指標(biāo).當(dāng)前還沒(méi)有統(tǒng)一的評(píng)價(jià)指標(biāo)對(duì)各種圖概要技術(shù)進(jìn)行評(píng)價(jià)，考慮到概要技術(shù)的應(yīng)用性，可以針對(duì)其概要技術(shù)提出一個(gè)多領(lǐng)域評(píng)估框架，囊括主流的概要技術(shù)，根據(jù)應(yīng)用需求選擇適應(yīng)的評(píng)估方案，這也是圖概要領(lǐng)域的研究者當(dāng)前亟需確立的任務(wù).

2) 基于動(dòng)態(tài)圖流的概要化[82].現(xiàn)實(shí)世界中的社交網(wǎng)絡(luò)是基于時(shí)間維度的，對(duì)于這類(lèi)圖概要需要捕獲隨時(shí)間變化的結(jié)構(gòu)和屬性的模式[83].然而，針對(duì)動(dòng)態(tài)圖流的概要技術(shù)尚未得到充分的探索，當(dāng)前部分模型通過(guò)嵌入技術(shù)將頂點(diǎn)投影到低維向量空間，并保持其頂點(diǎn)的結(jié)構(gòu)相似性.現(xiàn)實(shí)生活中，F(xiàn)acebook用于發(fā)送消息所形成的社交網(wǎng)絡(luò)、網(wǎng)絡(luò)服務(wù)器之間的鏈接和消息流動(dòng)、智能家居設(shè)備之間的信號(hào)傳遞都可以被視為動(dòng)態(tài)圖流.圖流中每個(gè)頂點(diǎn)具有自己的鄰接矩陣，通過(guò)矩陣的更新提取頂點(diǎn)隨著時(shí)間變化的動(dòng)態(tài)特征并進(jìn)行個(gè)性化分析是圖流概要化的核心技術(shù).然而，增加時(shí)間維度將面臨更多的挑戰(zhàn):如何描述隨著時(shí)間推移而形成的動(dòng)態(tài)圖形的結(jié)構(gòu)特征?如何濾除冗余的變化？如何根據(jù)實(shí)際應(yīng)用需求捕捉合適的時(shí)間窗口，確定圖流對(duì)時(shí)間的敏感度，這都是導(dǎo)致動(dòng)態(tài)圖概要研究進(jìn)展緩慢的原因.動(dòng)態(tài)圖流的概要化無(wú)法用單一的概要圖描述其空間特征和時(shí)間特征，而是需要一系列概要圖序列描述其變化趨勢(shì).未來(lái)工作可以借助機(jī)器學(xué)習(xí)領(lǐng)域的Boosting思想，構(gòu)建概要圖序列，初始概要圖代表初始時(shí)間窗口的特征(樹(shù))，下一時(shí)刻概要圖描述矯正信息(圖流更新信息)，通過(guò)一系列概要圖序列擬合動(dòng)態(tài)圖流的變化趨勢(shì)，描述并預(yù)測(cè)動(dòng)態(tài)圖流的結(jié)構(gòu)特征.時(shí)間窗口的選取可通過(guò)偏方差和懲罰項(xiàng)制定損失函數(shù)，自適應(yīng)地調(diào)整，避免過(guò)擬合，提升概要圖序列對(duì)圖流特征描述的泛化能力.

3) 異構(gòu)信息網(wǎng)絡(luò)的圖概要[84].當(dāng)前大多數(shù)關(guān)于網(wǎng)絡(luò)科學(xué)、社交和信息網(wǎng)絡(luò)的研究，普通是同構(gòu)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中的頂點(diǎn)都是相同實(shí)體類(lèi)型的對(duì)象，并且鏈接都是相同類(lèi)型的關(guān)系.這些研究獲得了許多有趣的結(jié)果以及眾多有重要影響的應(yīng)用.然而，實(shí)際中大多數(shù)網(wǎng)絡(luò)是異構(gòu)的(heterogeneous)[85]，即網(wǎng)絡(luò)中的頂點(diǎn)和關(guān)系并不是相同類(lèi)型的.例如，在一個(gè)醫(yī)療保健預(yù)測(cè)網(wǎng)絡(luò)中，頂點(diǎn)可以是病人、醫(yī)生、檢查、疾病、藥物、醫(yī)院、治療措施等，構(gòu)建出頂點(diǎn)類(lèi)型不同的異構(gòu)網(wǎng)絡(luò).而現(xiàn)有的圖概要技術(shù)多是基于相同頂點(diǎn)類(lèi)型的同構(gòu)網(wǎng)絡(luò)，由于頂點(diǎn)實(shí)體類(lèi)型的多樣化和結(jié)構(gòu)的復(fù)雜化，無(wú)法移植到異構(gòu)網(wǎng)絡(luò)中，但針對(duì)異構(gòu)網(wǎng)絡(luò)建?？梢圆东@真實(shí)世界中最根本的語(yǔ)義信息.有2種策略可以幫助建立異構(gòu)網(wǎng)絡(luò)的圖概要，一是借鑒現(xiàn)有的屬性與結(jié)構(gòu)的相似性轉(zhuǎn)化操作，將異構(gòu)網(wǎng)絡(luò)中不同的實(shí)體類(lèi)型以增加屬性域的方法轉(zhuǎn)化為同一實(shí)體的不同屬性，從而將異構(gòu)網(wǎng)絡(luò)轉(zhuǎn)化為同構(gòu)網(wǎng)絡(luò)來(lái)處理；二是將異構(gòu)網(wǎng)絡(luò)拆分為多個(gè)同構(gòu)網(wǎng)絡(luò)分別進(jìn)行概要化操作，提取隱藏的模式結(jié)構(gòu)，揭示不同頂點(diǎn)之間的隱藏關(guān)系，不失為一種有效策略.目前針對(duì)異構(gòu)網(wǎng)絡(luò)的概要化技術(shù)尚未得到足夠的關(guān)注.

4) 分布式圖概要技術(shù)的擴(kuò)展[86].當(dāng)前的圖概要技術(shù)，大多采取單個(gè)進(jìn)程內(nèi)存處理所有的任務(wù).隨著圖數(shù)據(jù)規(guī)模的指數(shù)級(jí)增長(zhǎng)和信息結(jié)構(gòu)的復(fù)雜化，尤其在處理千億個(gè)頂點(diǎn)和邊時(shí)，單機(jī)的概要化技術(shù)往往陷入數(shù)據(jù)災(zāi)難.分布式環(huán)境能提供更多的存儲(chǔ)內(nèi)存，并行計(jì)算能極大地提高概要化效率.目前，分布式下的概要技術(shù)尚未得到重視，這主要取決于計(jì)算和通信成本的嚴(yán)峻挑戰(zhàn).首先頂點(diǎn)和邊緣分布在不同的內(nèi)存中，因此集中式圖概要技術(shù)看似簡(jiǎn)單的操作，需要在分布式環(huán)境中跨越多個(gè)頂點(diǎn)進(jìn)行消息傳遞和仔細(xì)協(xié)調(diào).其次，單機(jī)的概要算法不需要考慮計(jì)算資源的分配，而一個(gè)優(yōu)秀的分布式下圖概要技術(shù)應(yīng)該充分利用每一個(gè)機(jī)器，以實(shí)現(xiàn)高效的并行化計(jì)算，克服這些挑戰(zhàn).通過(guò)設(shè)計(jì)輕量級(jí)的過(guò)濾交互算法，在每一次迭代前對(duì)圖數(shù)據(jù)進(jìn)行預(yù)處理，可避免不必要的計(jì)算和通信開(kāi)銷(xiāo)，分布式下的概要技術(shù)更能勝任大圖流下的計(jì)算分析，圖概要領(lǐng)域的研究者更應(yīng)重視這一方向的工作.

5) 圖概要的低維嵌入表示[87].近年來(lái)以深度學(xué)習(xí)(deep learning)[88]為代表的表征學(xué)習(xí)方法在語(yǔ)音識(shí)別、圖像理解以及機(jī)器翻譯等任務(wù)上取得了巨大的成功.這些方法通過(guò)設(shè)計(jì)多層的非線性神經(jīng)網(wǎng)絡(luò)從原始數(shù)據(jù)提取有效特征，整個(gè)模型從數(shù)據(jù)的原始輸入到目標(biāo)任務(wù)的最終輸出，實(shí)現(xiàn)了端到端的學(xué)習(xí).由于深度學(xué)習(xí)等表征學(xué)習(xí)方法在多個(gè)領(lǐng)域的有效性，近年來(lái)涌現(xiàn)了大量的致力于面向網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)的表征學(xué)習(xí)的工作.深度學(xué)習(xí)網(wǎng)絡(luò)表征學(xué)習(xí)算法的目標(biāo)是獲得網(wǎng)絡(luò)的低維稠密表示，對(duì)于大規(guī)模網(wǎng)絡(luò)(如社會(huì)網(wǎng)絡(luò))，網(wǎng)絡(luò)表征學(xué)習(xí)的目標(biāo)是把網(wǎng)絡(luò)中的每個(gè)頂點(diǎn)表示成為一個(gè)低維稠密的向量并且保證在這個(gè)低維空間上能夠很好地保留網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).頂點(diǎn)表示能夠當(dāng)作頂點(diǎn)的特征用于頂點(diǎn)分類(lèi)、頂點(diǎn)聚類(lèi)、網(wǎng)絡(luò)可視化、鏈接預(yù)測(cè)等不同的任務(wù)，本質(zhì)上是通過(guò)保留網(wǎng)絡(luò)的局部結(jié)構(gòu)性來(lái)估計(jì)頂點(diǎn)的表示.概要技術(shù)可以引入其思想，將圖數(shù)據(jù)的特征映射到低維向量空間中進(jìn)行概要化，這種充滿潛力的方案似乎更能解決大型復(fù)雜網(wǎng)絡(luò)的概要化難點(diǎn).