基于節(jié)點(diǎn)相似性分組與圖壓縮的圖摘要算法

宏宇，陳鴻昶，張建朋*，黃瑞陽(yáng)

基于節(jié)點(diǎn)相似性分組與圖壓縮的圖摘要算法

宏宇1，陳鴻昶2，張建朋2*，黃瑞陽(yáng)2

（1.鄭州大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，鄭州 450002； 2.信息工程大學(xué) 信息技術(shù)研究所，鄭州 450002）（ ? 通信作者電子郵箱j_zhang_edu@sina.com）

針對(duì)當(dāng)前圖摘要方法壓縮率較高，圖壓縮算法無(wú)法直接被用于下游任務(wù)分析的問(wèn)題，提出一種圖摘要與圖壓縮的融合算法，即基于節(jié)點(diǎn)相似性分組與圖壓縮的圖摘要算法（GSNSC）。首先，初始化節(jié)點(diǎn)為超節(jié)點(diǎn)，并根據(jù)相似度對(duì)超節(jié)點(diǎn)分組；其次，將每個(gè)組的超節(jié)點(diǎn)合并，直到達(dá)到指定次數(shù)或指定節(jié)點(diǎn)數(shù)；再次，在超節(jié)點(diǎn)之間添加超邊和校正邊以恢復(fù)原始圖；最后，對(duì)于圖壓縮部分，判斷對(duì)每個(gè)超節(jié)點(diǎn)的鄰接邊壓縮和摘要的代價(jià)，并選擇二者中代價(jià)較小的執(zhí)行。在Web-NotreDame、Web-Google和Web-Berkstan等6個(gè)數(shù)據(jù)集上進(jìn)行了圖壓縮率和圖查詢實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，在6個(gè)數(shù)據(jù)集上，與SLUGGER（Scalable Lossless sUmmarization of Graphs with HiERarchy）算法相比，所提算法的壓縮率至少降低了23個(gè)百分點(diǎn)；與SWeG（Summarization of Web-scale Graphs）算法相比，所提算法的壓縮率至少降低了13個(gè)百分點(diǎn)；在Web-NotreDame數(shù)據(jù)集上，所提算法的度誤差比SWeG降低了41.6%。以上驗(yàn)證了所提算法具有更好的圖壓縮率和圖查詢準(zhǔn)確度。

圖摘要；圖壓縮；圖查詢；超邊；最小描述長(zhǎng)度

0 引言

圖數(shù)據(jù)可以用于建模實(shí)體和實(shí)體之間的復(fù)雜關(guān)系，在現(xiàn)實(shí)世界中應(yīng)用廣泛，如社交網(wǎng)絡(luò)、蛋白質(zhì)分子網(wǎng)絡(luò)、合作關(guān)系網(wǎng)絡(luò)和通信網(wǎng)絡(luò)等。許多計(jì)算問(wèn)題都可以轉(zhuǎn)換成圖上的計(jì)算問(wèn)題，從而利用圖上的相關(guān)技術(shù)解決問(wèn)題。圖有很多下游任務(wù)，如模式挖掘、社區(qū)發(fā)現(xiàn)、圖查詢和可視化等，服務(wù)于解決現(xiàn)實(shí)問(wèn)題；然而，隨著數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，用于分析的圖數(shù)據(jù)也越來(lái)越復(fù)雜多樣，難以存儲(chǔ)和分析，解決這些問(wèn)題已經(jīng)成為當(dāng)前研究的熱點(diǎn)和難點(diǎn)。

目前用于解決圖數(shù)據(jù)量大問(wèn)題的技術(shù)包括圖壓縮和圖摘要（Graph summarization）技術(shù)。圖摘要技術(shù)［1-11］將具有較高相似度的節(jié)點(diǎn)合并成超節(jié)點(diǎn)，減少節(jié)點(diǎn)和邊的數(shù)量以降低圖的復(fù)雜度，主要方法有基于節(jié)點(diǎn)分組的方法［5-7］、基于邊分組的方法［2］和基于稀疏化的方法［1］等。圖壓縮技術(shù)［4，12-16］將圖數(shù)據(jù)以存儲(chǔ)占用更低的壓縮方式存儲(chǔ)，主要方法有基于頂點(diǎn)重排序的方法［12-13］和基于鄰接矩陣的方法［14］等。這兩類技術(shù)的側(cè)重點(diǎn)不同，圖摘要技術(shù)側(cè)重于保存圖的結(jié)構(gòu)信息，它的輸出是一個(gè)更為抽象緊湊的圖，因此可以直接用于下游任務(wù)分析；圖壓縮技術(shù)則是以各種方式最大限度地降低圖數(shù)據(jù)在磁盤空間或內(nèi)存空間的存儲(chǔ)占用，由于圖壓縮技術(shù)并不關(guān)注圖的結(jié)構(gòu)信息，因此在降低存儲(chǔ)空間方面，圖壓縮效果更好，但是圖壓縮產(chǎn)生的圖并不能直接使用，需要先對(duì)壓縮后的圖進(jìn)行解碼操作。

通過(guò)對(duì)比兩種技術(shù)的特點(diǎn)可以發(fā)現(xiàn)，圖摘要雖然能夠降低圖的復(fù)雜度，但為了能夠恢復(fù)原始圖和保存結(jié)構(gòu)特征，它的效果比圖壓縮的效果差；而圖壓縮雖然能夠更好地降低圖的消耗，但是不能直接用于分析。

針對(duì)以上問(wèn)題，本文提出一種基于節(jié)點(diǎn)相似性分組與圖壓縮的圖摘要算法（Graph Summarization algorithm based on Node Similarity grouping and graph Compression， GSNSC），結(jié)合了圖摘要與圖壓縮的優(yōu)勢(shì)。

本文的主要工作如下：

1）提出了一種基于節(jié)點(diǎn)相似性分組與圖壓縮的圖摘要算法（GSNSC）。首先通過(guò)將節(jié)點(diǎn)分組聚合成超節(jié)點(diǎn)的方式產(chǎn)生較小的輸出摘要圖，其次壓縮摘要圖中的超邊和校正邊，降低圖的壓縮率，減少運(yùn)行時(shí)間。所提算法不僅能夠降低圖的存儲(chǔ)空間占用，而且還能直接用于挖掘和分析。

2）在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，所提算法比現(xiàn)有的圖摘要算法具有更好的壓縮率和更低的運(yùn)行時(shí)間。針對(duì)圖查詢?cè)O(shè)計(jì)了相關(guān)實(shí)驗(yàn)，驗(yàn)證了所提算法具有較好的查詢準(zhǔn)確度。

1 相關(guān)工作

1.1　圖摘要

圖摘要又叫作圖概要，是一種降低大規(guī)模圖的復(fù)雜度和描述長(zhǎng)度的技術(shù)。它通過(guò)一些策略（如合并多個(gè)節(jié)點(diǎn)成一個(gè)超節(jié)點(diǎn)、去掉不重要的邊等）創(chuàng)建一個(gè)摘要圖，在降低圖的成本的同時(shí)也保存了圖的結(jié)構(gòu)特征，使得到的摘要圖能夠更容易地支持圖模式挖掘、可視化和鄰域查詢等下游任務(wù)。

圖1　例子示意圖

1.2　圖壓縮

圖壓縮也是降低圖規(guī)模的一種方法，和圖摘要的區(qū)別是它不關(guān)注圖的結(jié)構(gòu)信息和語(yǔ)義信息，它的目標(biāo)是盡可能地降低圖的存儲(chǔ)空間占用，使得大圖數(shù)據(jù)可以存儲(chǔ)在較小的磁盤空間上，以解決圖數(shù)據(jù)量較大的問(wèn)題。目前圖壓縮的研究還處于起步階段［4］，這些方法大多壓縮節(jié)點(diǎn)的邊，其中較為常用的是基于節(jié)點(diǎn)重排的方法。由于真實(shí)的圖通常都是非常稀疏的，如在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)代表用戶，邊代表用戶之間的好友關(guān)系，圖中的節(jié)點(diǎn)數(shù)可能達(dá)到上千萬(wàn)甚至上億，而每個(gè)節(jié)點(diǎn)的好友關(guān)系可能僅有幾十或者幾百條。圖壓縮可以在不改變圖結(jié)構(gòu)的情況下壓縮節(jié)點(diǎn)的稀疏鄰邊，因此當(dāng)使用鄰接表壓縮邊時(shí)，節(jié)點(diǎn)的排序非常重要。通過(guò)節(jié)點(diǎn)重排算法可以更好地降低圖的壓縮率，每個(gè)節(jié)點(diǎn)的鄰邊以鄰接表保存，其次利用編碼技術(shù)壓縮節(jié)點(diǎn)的鄰邊?？梢钥闯?，圖壓縮技術(shù)的目的是降低圖數(shù)據(jù)的存儲(chǔ)空間占用，并不保留圖的結(jié)構(gòu)特征，因此單純的圖壓縮技術(shù)產(chǎn)生的壓縮圖不是圖的結(jié)構(gòu)，不能直接用于分析，必須進(jìn)行解碼操作。本文的目標(biāo)不僅是降低圖的存儲(chǔ)空間占用，而且還能直接用于挖掘和分析，因此需要結(jié)合圖摘要技術(shù)改進(jìn)算法。

文獻(xiàn)［14］中利用鄰接矩陣的特征提出了2-tree，2-tree能很好地壓縮鄰接矩陣，實(shí)現(xiàn)較好的時(shí)間/空間均衡，但2-tree還面臨以下問(wèn)題：2-tree中還存在大量的同構(gòu)子樹(shù)；2-tree只能壓縮稀疏圖；2-tree只能表示靜態(tài)圖，不能向其中增加或者刪除邊。針對(duì)上述問(wèn)題，文獻(xiàn)［21］中把多值決策圖（Multiple-valued Decision Diagram， MDD）和2-tree結(jié)合，提出了2-MDD，利用MDD的刪除規(guī)則和化簡(jiǎn)規(guī)則合并相同子圖。

2 問(wèn)題定義

在本文研究中，創(chuàng)建摘要圖采用最小描述長(zhǎng)度（Minimum Description Length， MDL）原則［22］，MDL原則的目的是尋找最好的損失模型，使得模型和編碼數(shù)據(jù)的損失最小。本文通過(guò)最小描述長(zhǎng)度創(chuàng)建摘要圖和壓縮圖，問(wèn)題定義如下：

表1　符號(hào)及含義

3 算法基本原理

本文算法使用的代價(jià)模型分兩部分組成，分別是對(duì)邊進(jìn)行圖摘要方式存儲(chǔ)的代價(jià)模型和對(duì)邊進(jìn)行圖壓縮方式存儲(chǔ)的代價(jià)模型。對(duì)節(jié)點(diǎn)進(jìn)行圖摘要的損失如下：

壓縮超節(jié)點(diǎn)相連的超邊時(shí)的損失如下：

通過(guò)式（1）可以得出合并一對(duì)節(jié)點(diǎn)的收益為：

其中為合并和之后的節(jié)點(diǎn)。合并超節(jié)點(diǎn)對(duì)的收益表示相較于合并之前，合并之后圖的總消耗的降低量，該值越大說(shuō)明收益越高。

3.1　算法描述

2）合并階段。合并第1）步產(chǎn)生的每個(gè)組。計(jì)算超節(jié)點(diǎn)的合并收益時(shí)需要查找所有其他超節(jié)點(diǎn)，選出最佳的那個(gè)超節(jié)點(diǎn)與之合并，但是這樣會(huì)非常浪費(fèi)時(shí)間，因此采取分組合并的方式降低時(shí)間復(fù)雜度。

首先根據(jù)超節(jié)點(diǎn)的shingle值（見(jiàn)3.2節(jié)）將超節(jié)點(diǎn)劃分成多個(gè)組，每個(gè)組內(nèi)的超節(jié)點(diǎn)都比較相似，即有很多個(gè)公共鄰居，將這些節(jié)點(diǎn)合并會(huì)使得合并前后的總體邊數(shù)量大幅降低。分組后只需要對(duì)每個(gè)組內(nèi)的超節(jié)點(diǎn)計(jì)算合并收益，不必搜索整個(gè)超節(jié)點(diǎn)集，大幅縮小了查找范圍。合并完成后，執(zhí)行以下操作：

編碼 將滿足條件的超節(jié)點(diǎn)之間連接超邊并更新校正邊集，對(duì)于每個(gè)超節(jié)點(diǎn)的所有鄰接超邊，比較壓縮存儲(chǔ)或者摘要存儲(chǔ)的消耗，選擇存儲(chǔ)消耗更小的方式存儲(chǔ)。

GSNSC的偽代碼如算法1所示。

算法1 GSNSC。

while（<） do

合并每個(gè)組

3.2　分組階段

分組階段的偽代碼如算法2所示。

算法2 分組階段。

3.3　合并階段

合并階段的偽代碼如算法3所示。

算法3 合并階段。

while（||>1 &&<） do

隨機(jī)采樣中任意節(jié)點(diǎn)對(duì)

3.4　編碼階段

當(dāng)處理所有超節(jié)點(diǎn)后，再壓縮校正邊集。具體步驟為：首先遍歷原始圖中的每一個(gè)節(jié)點(diǎn)，獲取每一個(gè)節(jié)點(diǎn)的所有校正邊，其次計(jì)算該節(jié)點(diǎn)的鄰邊壓縮存儲(chǔ)消耗和摘要存儲(chǔ)消耗，如果壓縮需要的存儲(chǔ)代價(jià)更小，則選擇壓縮，以段的方式存儲(chǔ)；否則以節(jié)點(diǎn)對(duì)的方式存儲(chǔ)。至此算法結(jié)束，返回摘要壓縮圖和校正邊集合。

編碼階段的偽代碼如算法4所示。

算法4 編碼階段。

6） else

11） else

15） 壓縮

17） else

3.5　算法時(shí)間復(fù)雜度分析

3.6　算法空間復(fù)雜度分析

4 實(shí)驗(yàn)與結(jié)果分析

4.1　實(shí)驗(yàn)設(shè)置

1）數(shù)據(jù)集。

實(shí)驗(yàn)使用的數(shù)據(jù)集如表2所示。Web-Berkstan數(shù)據(jù)集（http：//snap.stanford.edu/data/）中節(jié)點(diǎn)代表來(lái)自berkely.edu 和stanford.edu的頁(yè)面，邊代表它們之間的連接。類似地，Web-Google和Web-NotreDame數(shù)據(jù)集中的節(jié)點(diǎn)分別代表谷歌和諾特丹大學(xué)網(wǎng)站的頁(yè)面。DBLP數(shù)據(jù)集中，節(jié)點(diǎn)代表論文作者，邊代表兩個(gè)作者之間有合作關(guān)系。Skitter數(shù)據(jù)集為Internet拓?fù)鋱D，追蹤路線從幾個(gè)分散的來(lái)源到數(shù)百萬(wàn)個(gè)目的地。Youtube數(shù)據(jù)集為在線社交網(wǎng)絡(luò)數(shù)據(jù)集。

表2　數(shù)據(jù)集描述

2）環(huán)境設(shè)置。

GSNSC代碼運(yùn)行在一個(gè)Intel Xeon CPU E5-2650 v4 @ 2.20 GHz的linux服務(wù)器上，其中包含4個(gè)CPU，每個(gè)CPU12核，語(yǔ)言為C++。

3）評(píng)價(jià)指標(biāo)。

4.2　對(duì)比算法

針對(duì)壓縮率對(duì)比實(shí)驗(yàn)，對(duì)比算法如下。

1）DPGS［6］。原算法的損失函數(shù)是編碼長(zhǎng)度而不是邊和節(jié)點(diǎn)的數(shù)量，實(shí)驗(yàn)中采用本文中的損失函數(shù)。

2）SWeG［5］。該算法采用和本文算法相同的分組方式，但是在合并步驟上有所不同。

3）GREEDY［3］。該算法是圖摘要的經(jīng)典貪心算法。

4）GreedyCS［4］。和本文算法類似，該算法也是采用圖摘要和圖壓縮結(jié)合的方法降低圖的規(guī)模。

5）SLUGGER［18］。該算法貪婪地將節(jié)點(diǎn)合并為超節(jié)點(diǎn)，同時(shí)維護(hù)和利用它們的層次結(jié)構(gòu)。

4.3　壓縮率和運(yùn)行時(shí)間實(shí)驗(yàn)

不同算法的壓縮率和運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果對(duì)比如表3所示，其中：OOT代表運(yùn)行時(shí)間太久或內(nèi)存超過(guò)限制，屬于無(wú)效數(shù)據(jù)；壓縮率為輸出圖與輸入圖大小的比值，值越小，效果越好。設(shè)置閾值分別為0.1、0.2和0.3（SLUGGER無(wú)閾值區(qū)分），對(duì)比每種算法的實(shí)驗(yàn)結(jié)果。對(duì)于同一數(shù)據(jù)集的同一個(gè)方法，當(dāng)越大時(shí)，效果越差，這是因?yàn)樵酱?，合并?jié)點(diǎn)的門檻就越高，節(jié)點(diǎn)越不容易被合并，因此輸出圖中的節(jié)點(diǎn)數(shù)和邊數(shù)就越多，導(dǎo)致壓縮率更高。與SLUGGER相比，GSNSC的壓縮率至少降低了23個(gè)百分點(diǎn)；與SweG相比，壓縮率至少降低了13個(gè)百分點(diǎn)。通過(guò)每個(gè)數(shù)據(jù)集上的結(jié)果可以看出，GSNSC的壓縮率效果明顯優(yōu)于其他對(duì)比算法，原因是該算法相較于其他對(duì)比算法，不僅壓縮摘要圖中的超邊，還壓縮了用于恢復(fù)原圖的校正邊集，后者對(duì)壓縮率降低做出最大貢獻(xiàn)，這是因?yàn)樾Ｕ吋ǔ？偸沁h(yuǎn)大于超邊集，兩個(gè)超節(jié)點(diǎn)之間最多有一條超邊，但是可以有多條校正邊。對(duì)于不同的數(shù)據(jù)集，同種方法壓縮率相差較大；從結(jié)果可以看出，圖的密度越低，壓縮率就越好。

表3　不同算法在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對(duì)比

4.4　θ和壓縮率的關(guān)系

圖2展示了在Web-NotreDame數(shù)據(jù)集下測(cè)試的和壓縮率之間的關(guān)系?？梢钥闯觯?dāng)值為0.05時(shí)壓縮率最低，當(dāng)值逐漸變大，壓縮率也在不斷升高；這是由于越大，節(jié)點(diǎn)合并的閾值就越高，因此效果越差。

圖2　Web-NotreDame數(shù)據(jù)集上和壓縮率的關(guān)系

4.5　T和壓縮率的關(guān)系

圖3展示了在Web-NotreDame數(shù)據(jù)集上，當(dāng)=0.2時(shí)迭代次數(shù)和壓縮率之間關(guān)系的實(shí)驗(yàn)結(jié)果?？梢钥闯?，在的取值為1到5時(shí)，壓縮率下降較快；這是由于此時(shí)太小，每次循環(huán)合并的節(jié)點(diǎn)數(shù)是有限的，因此每增加1，壓縮率就大幅下降。當(dāng)>5時(shí)，越往后壓縮率不斷上下浮動(dòng)并趨于穩(wěn)定，這很大程度上是由于算法運(yùn)行具有隨機(jī)性。

圖3　Web-NotreDame數(shù)據(jù)集上T和壓縮率的關(guān)系（θ=0.2）

4.6　圖查詢

通過(guò)期望鄰接矩陣對(duì)圖進(jìn)行查詢將會(huì)比在原始圖上更快，這是因?yàn)檎獔D中的節(jié)點(diǎn)數(shù)很少，因此鄰接矩陣相較于原始圖更小，因此查詢效率更高，本文從圖查詢的準(zhǔn)確度方面評(píng)估摘要圖的好壞。

對(duì)比GSNSC、DPGS和SweG這3種算法在Web-NotreDame數(shù)據(jù)集上的度誤差，在Web-NotreDame和Web-Google數(shù)據(jù)集上的鄰接誤差，實(shí)驗(yàn)結(jié)果如表4所示?？梢钥闯?，GSNSC的度誤差和鄰接誤差更低，與SweG相比，度誤差降低了41.6%，說(shuō)明GSNSC在針對(duì)圖查詢的準(zhǔn)確率上優(yōu)于其他對(duì)比算法。

表4　不同數(shù)據(jù)集上3種算法的度誤差和鄰接誤差對(duì)比

5 結(jié)語(yǔ)

本文結(jié)合圖摘要和圖壓縮的優(yōu)勢(shì)，提出一種圖摘要和圖壓縮的融合算法（GSNSC），用于壓縮大規(guī)模圖數(shù)據(jù)。經(jīng)過(guò)理論分析和實(shí)驗(yàn)驗(yàn)證，結(jié)果表明所提算法具有較好的效果，所提融合算法具有一定的可行性。然而，本文算法目前只適用于簡(jiǎn)單靜態(tài)同質(zhì)圖，還無(wú)法適用于異質(zhì)圖、屬性圖和動(dòng)態(tài)圖等。未來(lái)可以通過(guò)設(shè)置損失函數(shù)等方法，將本文算法擴(kuò)充至屬性圖，根據(jù)不同節(jié)點(diǎn)的類型擴(kuò)充至異質(zhì)圖，加入時(shí)間屬性擴(kuò)充至動(dòng)態(tài)圖。

[1] LEE K， JO H， KO J， et al. SSumM： sparse summarization of massive graphs［C］// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2020： 144-154.

[2] MACCIONI A， ABADI D J. Scalable pattern matching over compressed graphs via dedensification［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 1755-1764.

[3] NAVLAKHA S， RASTOGI R， SHRIVASTAVA N. Graph summarization with bounded error［C］// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 419-432.

[4] SEO H， PARK K， HAN Y， et al. An effective graph summarization and compression technique for a large-scaled graph［J］. The Journal of Supercomputing， 2020， 76（10）： 7906-7920.

[5] SHIN K， GHOTING A， KIM M， et al. SWeG： lossless and lossy summarization of web-scale graphs［C］// Proceedings of the 2019 World Wide Web Conference. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2019： 1679-1690.

[6] ZHOU H， LIU S， LEE K， et al. DPGS： degree-preserving graph summarization［C］// Proceedings of the 2021 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2021：280-288.

[7] ZHU L， GHASEMI-GOL M， SZEKELY P， et al. Unsupervised entity resolution on multi-type graphs［C］// Proceedings of the 2016 International Semantic Web Conference， LNCS 9981. Cham： Springer， 2016： 649-667.

[8] TIAN Y， HANKINS R A， PATEL J M. Efficient aggregation for graph summarization［C］// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 567-580.

[9] YONG Q， HAJIABADI M， SRINIVASAN V， et al. Efficient graph summarization using weighted LSH at billion-scale［C］// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2021： 2357-2365.

[10] UR R S， NAWAZ A， ALI T， et al. g-Sum： a graph summarization approach for a single large social network［J］. EAI Endorsed Transactions on Scalable Information Systems， 2021， 8（32）： No.e2.

[11] SACENTI J A P， FILETO R， WILLRICH R. Knowledge graph summarization impacts on movie recommendations［J］. Journal of Intelligent Information Systems， 2022， 58（1）： 43-66.

[12] BOLDI P， SANTINI M， VIGNA S. Permuting web graphs［C］// Proceedings of the 2009 International Workshop on Algorithms and Models for the Web-Graph， LNCS 5427. Berlin： Springer， 2009： 116-126.

[13] HERNáNDEZ C， NAVARRO G. Compressed representations for Web and social graphs［J］. Knowledge and Information Systems， 2014， 40（2）： 279-313.

[14] BRISABOA N R， LADRA S， NAVARRO G.2-trees for compact Web graph representation［C］// Proceedings of the 2009 International Symposium on String Processing and Information Retrieval， LNCS 5721. Berlin： Springer， 2009： 18-30.

[15] FRANCISCO A P， GAGIE T， K?PPL D， et al. Graph compression for adjacency-matrix multiplication［J］. SN Computer Science， 2022， 3（3）： No.193.

[16] EMAMZADEH ESMAEILI NEJAD A， JAHROMI M Z， TAHERI M. Graph compression based on transitivity for neighborhood query［J］. Information Sciences， 2021， 576： 312-328.

[17] YANG S， YANG Z， CHEN X， et al. Distributed aggregation-based attributed graph summarization for summary-based approximate attributed graph queries［J］. Expert Systems with Applications， 2021， 176： No.114921.

[18] LEE K， KO J， SHIN K. SLUGGER： lossless hierarchical summarization of massive graphs［C］// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 472-484.

[19] KE X， KHAN A， BONCHI F. Multi-relation graph summarization［J］. ACM Transactions on Knowledge Discovery from Data， 2022， 16（5）： No.82.

[20] KANG S， LEE K， SHIN K. Personalized graph summarization： formulation， scalable algorithms， and applications［C］// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 2319-2332.

[21] 董榮勝，張新凱，劉華東，等. 大規(guī)模圖數(shù)據(jù)的2-MDD表示方法與操作研究［J］. 計(jì)算機(jī)研究與發(fā)展， 2016， 53（12）：2783-2792.（DONG R S， ZHANG X K， LIU H D， et al. Representation and operations research of2-MDD in large-scale graph data［J］. Jouanal of Computer Research and Development， 2016， 52（12）：2783-2792.）

[22] RISSANEN J. Modeling by shortest data description［J］. Automatica， 1978， 14（5）： 465-471.

[23] BRODER A Z， CHARIKAR M， FRIEZE A M， et al. Min-wise independent permutations［J］. Journal of Computer and System Sciences， 2000， 60（3）： 630-659.

[24] LeFEVRE K ， TERZI E. GraSS： graph structure summarization［C］// Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2010： 454-465.

Graph summarization algorithm based on node similarity grouping and graph compression

HONG Yu1， CHEN Hongchang2， ZHANG Jianpeng2*， HUANG Ruiyang2

（1，，450002，；2，，450002，）

To solve the problem that the current graph summarization methods have high compression ratios and the graph compression algorithms cannot be directly used in downstream tasks， a fusion algorithm of graph summarization and graph compression was proposed， which called Graph Summarization algorithm based on Node Similarity grouping and graph Compression （GSNSC）. Firstly， the nodes were initialized as super nodes， and the super nodes were grouped according to the similarity. Secondly， the super nodes of each group were merged until the specified number of times or nodes were reached. Thirdly， super edges and corrected edges were added between the super nodes for reconstructing the original graph. Finally， for the graph compression part， the cost of compressing and summarizing the adjacent edges of each super node were judged， and the less expensive one in these two was selected to execute. Experiments of graph compression ratio and graph query were conducted on six datasets such as Web-NotreDame， Web-Google and Web-Berkstan. Experimental results on six datasets show that， the proposed algorithm has the compression ratio reduced by at least 23 percentage points compared with SLUGGER （Scalable Lossless sUmmarization of Graphs with HiERarchy） algorithm， and the compression ratio decreased by at least 13 percentage points compared with SWeG （Summarization of Web-scale Graphs） algorithm. Experimental results on Web-NotreDame dataset show that the degree error of the proposed algorithm is reduced by 41.6% compared with that of SWeG algorithm. The above verifies that the proposed algorithm has better graph compression ratio and graph query accuracy.

graph summarization; graph compression; graph query; super edge; Minimum Description Length (MDL)

1001-9081（2023）10-3047-07

10.11772/j.issn.1001-9081.2022101535

2022?10?17；

2023?01?31；

國(guó)家自然科學(xué)基金資助項(xiàng)目（62002384）；中國(guó)博士后科學(xué)基金資助項(xiàng)目（2020M683760）。

宏宇（1998—），男，河北廊坊人，碩士研究生，主要研究方向：圖數(shù)據(jù)挖掘； 陳鴻昶（1964—），男，河南新密人，教授，博士生導(dǎo)師，博士，主要研究方向：大數(shù)據(jù)分析、通信與信息系統(tǒng)； 張建朋（1988—），男，河北廊坊人，助理研究員，博士，主要研究方向：大數(shù)據(jù)分析； 黃瑞陽(yáng)（1986—），男，福建漳州人，副研究員，博士，主要研究方向：知識(shí)圖譜、文本挖掘。

TP391

A

2023?01?31。

This work is partially supported by National Natural Science Foundation of China （62002384）， China Postdoctoral Science Foundation （2020M683760）.

HONG Yu， born in 1998， M. S. candidate. His research interests include graph data mining.

CHEN Hongchang， born in 1964， Ph. D.， professor. His research interests include big data analysis， communication and information systems.

ZHANG Jianpeng， born in 1988， Ph. D.， research assistant. His research interests include big data analysis.

HUANG Ruiyang， born in 1986， Ph. D.， associate research fellow. His research interests include knowledge graph， text mining.