在安全領(lǐng)域，“圖分析”廣泛應(yīng)用在賬戶交易異常、不同事件關(guān)聯(lián)等各種場(chǎng)景下。與其他機(jī)器學(xué)習(xí)算法類比較， 其特有的優(yōu)點(diǎn)在于分析方法符合人的思維方式，分析過(guò)程能直觀地可視化。

舉例來(lái)說(shuō)，下圖是把瀚思某客戶企業(yè)中幾類安全事件 ： 登陸、使用USB盤、檢測(cè)到病毒、機(jī)器IP、 用戶使用機(jī)器 - 綜合到一起做關(guān)聯(lián)分析。

圖中“邊”代表發(fā)生過(guò)事件;點(diǎn)(機(jī)器、用戶、IP、病毒、USB盤五類之一) 的大小代表事件多少。一張圖上我們可以快速定位爆發(fā)次數(shù)最多的病毒、哪些用戶違規(guī)使用同臺(tái)機(jī)器、哪些機(jī)器使用過(guò)同一個(gè)USB盤。

下圖是另一類例子，瀚思幫銀行客戶做的交易異常分析：點(diǎn)大小與出度成正比， 顏色隨著入度大小按藍(lán)色⇒白色⇒紅色方向變化。用金融術(shù)語(yǔ)來(lái)說(shuō)：出度過(guò)大的叫火山，入度過(guò)大的叫黑洞。這類情況往往和詐騙洗錢相關(guān)。

但是，圖一旦變大，分析過(guò)程會(huì)變慢，需要分析的邊數(shù)量，即使最壞不會(huì)到全連通有向圖中等于節(jié)點(diǎn)數(shù)N的N*(N-1)/2， 也往往遠(yuǎn)大于N。而且可視化因?yàn)槠聊淮笮『鸵鬃x性的限制，不宜再把成千上萬(wàn)個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的邊放到一張圖上。

這種情況下，我們采用分而治之策略：利用實(shí)際經(jīng)驗(yàn)中圖的社區(qū)性特征，把圖分割成若干個(gè)強(qiáng)聯(lián)通的區(qū)域， 對(duì)每一個(gè)區(qū)域做分析和可視化。

好的圖劃分算法在實(shí)際應(yīng)用中要額外有三個(gè)特征：

1、高速度，最好能并行化或者能用GPU加速。

2、能處理小世界網(wǎng)絡(luò)特征(也就是節(jié)點(diǎn)度數(shù)呈肥尾分布)。

3、對(duì)參數(shù)不敏感。

很多算法無(wú)法滿足2和3，教科書中算法大多是把圖均分，而且假設(shè)知道圖要分為多少類。

根據(jù)前文所述，瀚思利用“圖計(jì)算”在實(shí)際應(yīng)用中，幫助客戶解決了有關(guān)異常行為檢測(cè)的工作。而本文將重點(diǎn)針對(duì)三類應(yīng)用廣泛、效率較高并可以應(yīng)用于異常檢測(cè)的圖劃分算法進(jìn)行詳述。

譜劃分

譜劃分算法：它是最早用于解決圖劃分的一類算法，其思想來(lái)源于譜圖劃分理論。 矩陣的譜就是它的特征值和特征向量。 求圖劃分準(zhǔn)則的最優(yōu)解是一個(gè)NP難問(wèn)題。 一個(gè)很好的求解方法是考慮問(wèn)題的連續(xù)松弛形式，將原問(wèn)題轉(zhuǎn)換成求解Laplacian 矩陣的譜分解， 因此將這類方法統(tǒng)稱為譜劃分。

假定將每個(gè)數(shù)據(jù)樣本看作圖中的頂點(diǎn)V，根據(jù)樣本間的相似度將 頂點(diǎn)間的邊 E 賦權(quán)重值，便可得到一個(gè)基于相似度的無(wú)向加權(quán)圖 G=(V,E). 相似矩陣通常用 W 或 A 表示，有時(shí)也稱為親和矩陣(Affinity Matrix)， 往往是通過(guò)計(jì)算高斯核得到。

將相似度矩陣的每行元素相加，即得到對(duì)應(yīng)點(diǎn)的度，以所有度值為對(duì)角元素構(gòu)成的對(duì)角矩陣稱為度矩陣，通常記為 D。定義好相似矩陣W及度矩陣D，便可得如下的 Laplacian 矩陣：L=D – W

根據(jù)不同的準(zhǔn)則函數(shù)及譜映射方法，譜劃分算法發(fā)展了很多不同的具體實(shí)現(xiàn)方法，但都可以歸納為下面的三個(gè)主要步驟：

對(duì)于給定的圖G=(V,E)，計(jì)算圖的 Laplacian 矩陣L;

對(duì)L矩陣進(jìn)行特征值分解，取其前 k 個(gè)特征值對(duì)應(yīng)的特征向量，構(gòu)建特征向量矩陣Q;

利用K-means算法或其他經(jīng)典聚類算法對(duì)矩陣Q進(jìn)行劃分，每一行代表一個(gè)樣本點(diǎn), 即原圖的頂點(diǎn)所屬的類別.

上述步驟只是譜劃分的一個(gè)框架，在具體實(shí)現(xiàn)中，還存在著不同的劃分準(zhǔn)則，常見的有 Minimum Cut，Ratio Cut，Normalized Cut等。

譜劃分算法，首先通過(guò)引入 Laplacian 矩陣，運(yùn)用 Laplacian Eigenmap 進(jìn)行降維，再對(duì)這些 低維數(shù)據(jù)利用聚類算法進(jìn)行劃分，使得運(yùn)算量大大較少.下圖是用譜劃分算法實(shí)現(xiàn)的效果圖：

　　但譜劃分算法也有一些不足之處：

1)構(gòu)建特征向量矩陣Q無(wú)疑是該算法中最耗時(shí)間的， 在高維情況下, 不說(shuō)求解特征向量就是求解特征值都非常困難;

2)需要借助先驗(yàn)知識(shí)定義遞歸終止條件，即不具備智能識(shí)別圖類別總數(shù)的能力;

3)現(xiàn)實(shí)世界中的復(fù)雜網(wǎng)絡(luò)圖往往包含多個(gè)類，而遞歸的二分策略不能保證得到的劃分是最優(yōu)的劃分。

多層劃分算法

第二類圖劃分算法，稱為*多層劃分(Multilevel Partitioning，1995，Karypis)*。

以高效及運(yùn)算時(shí)間快著稱，比譜劃分算法快10%-50%， 計(jì)算千萬(wàn)數(shù)級(jí)的圖，時(shí)間基本是以秒計(jì)算。其主要實(shí)現(xiàn)步驟通常分為圖的 粗化階段(Coarsening phase), 初始劃分階段(Initial partitioning phase)和細(xì)化階段 (Uncoarsening phase)三個(gè)階段。

簡(jiǎn)言之，如下圖所示，該算法就是將原始圖經(jīng)粗化階段一層一層壓縮變“小”，得到頂點(diǎn)數(shù)目足夠小的圖， 再將這個(gè)數(shù)目足夠小的圖經(jīng)過(guò)初始劃分階段和細(xì)化階段一層一層還原變“大”，直到還原成原始圖，完成劃分。

粗化階段主要是為了減少原始圖的復(fù)雜性，構(gòu)建圖的多級(jí)層次. 它對(duì)原始圖的點(diǎn)和邊進(jìn)行壓縮合并， 構(gòu)造了一個(gè)層次化的較小的圖序列, 最終將原始圖壓縮成一個(gè)頂點(diǎn)數(shù)目足夠小的圖。 這種壓縮的思想(詳見下圖)可以形式化地定義為匹配 (Matching)，圖的匹配是指 邊的集合，其中任意兩條邊都沒(méi)有公共頂點(diǎn)。 在一個(gè)圖的所有匹配中，所含匹配邊數(shù)最多的匹配，稱為這個(gè)圖的最大匹配.

在整個(gè)粗化階段，原始圖的所有點(diǎn)以及權(quán)重都會(huì)累計(jì)，最終反應(yīng)在最小規(guī)模圖。 將最小規(guī)模圖進(jìn)行簡(jiǎn)單的劃分，稱為初始劃分階段，該階段由于結(jié)點(diǎn)數(shù)目較少，運(yùn)算非?？?，基本不耗時(shí)。 也不是多層算法的核心部分，其算法與接下來(lái)的細(xì)化階段算法聯(lián)系比較相似，這里不再贅述.

細(xì)化階段，也可稱為圖的還原優(yōu)化階段，該階段按照粗化層次一層一層將圖還原成原始圖，并在還原過(guò)程中 利用某些精細(xì)的算法逐層優(yōu)化，直到得到對(duì)原始圖的劃分.

這其中的常見的劃分算法有譜二分法算法有Spectral Bisection(SB)，Graph Growing Algorithm(GGP), Greedy Refinement(GR)， Kernighan-Lin Refinement(KLR)等， 其中比較著名的是Kernighan-Lin劃分算法。

*Kernighan-Lin劃分算法*，簡(jiǎn)稱KL算法，由Kernighan和Lin在1970年提出，是一個(gè)局部搜索優(yōu)化算法, 優(yōu)化的目標(biāo)函數(shù)是連接不同類的邊權(quán)之和最小。

舉個(gè)簡(jiǎn)單的例子，如下圖，紫色的點(diǎn)屬于一類，黑色的點(diǎn)屬于一類，KL算法是實(shí)現(xiàn)將下圖(a)轉(zhuǎn)換成下圖(b)的過(guò)程。

如何實(shí)現(xiàn)將紫色類別中的點(diǎn)和黑色類別中的點(diǎn)進(jìn)行交換，則是通過(guò)計(jì)算不同類別損失權(quán)重的差值來(lái)判斷的， 即交換前的內(nèi)外權(quán)重差(如下圖(a)的數(shù)字所示)減去交換后的內(nèi)外權(quán)重的值。當(dāng)且僅當(dāng)該值為正進(jìn)行交換，否則拒絕交換。 重復(fù)以上步驟，直至該值為負(fù)。

KL算法，較易理解，但得到的解往往是局部最優(yōu)。下圖，是利用多層劃分算法進(jìn)行圖劃分的例子：

多層劃分算法最大的局限在于它最大的局限性在于需要先驗(yàn)知識(shí)來(lái)產(chǎn)生一個(gè)較好的初始類。

MCL

最后談?wù)?，Markov Cluster Algorithm(2000, Stijn van Dongen), 簡(jiǎn)稱MCL算法，是一種快速可擴(kuò)展的 無(wú)監(jiān)督圖形聚類算法，有時(shí)也可以用于圖的劃分，其思想非常簡(jiǎn)單，主要是基于 隨機(jī)游走(Random walk) 和馬爾科夫鏈 (Markov chain)。 先簡(jiǎn)單說(shuō)一下這兩個(gè)概念.

隨機(jī)游走說(shuō)的是，如果我們從圖中的某一個(gè)點(diǎn)開始“瞎轉(zhuǎn)”，那么很可能就會(huì)在某一個(gè)子圖里面轉(zhuǎn)悠，而不是在子圖間來(lái)回游蕩. 而隨機(jī)游走的計(jì)算是通過(guò) Markov鏈來(lái)實(shí)現(xiàn)的. Markov鏈指的是一個(gè)隨機(jī)序列，該序列滿足“無(wú)后效性”，即 將來(lái)的狀態(tài)只依賴當(dāng)前狀態(tài)，而與過(guò)去的狀態(tài)無(wú)關(guān)。

MCL算法的關(guān)鍵思想就是：”隨機(jī)漫游者抵達(dá)稠密的類后，不會(huì)輕易的離開該類”. 前者是隨機(jī)游走的過(guò)程，后者依據(jù)是 Markov鏈的“無(wú)后效性”。 MCL算法中隨機(jī)漫游的過(guò)程，其實(shí)是一個(gè)不斷修改轉(zhuǎn)移概率矩陣的過(guò)程，該過(guò)程 重復(fù)執(zhí)行擴(kuò)展(Expansion)和膨脹(Inflation)兩個(gè)操作。

擴(kuò)展就是前面提到的馬爾科夫鏈的轉(zhuǎn)移矩陣的極限分布， 這個(gè)步驟不斷地對(duì)轉(zhuǎn)移概率矩陣進(jìn)行自乘直到它不再改變?yōu)橹埂?目的是連接圖的不同區(qū)域。膨脹是對(duì)每一個(gè)元素進(jìn)行冪操作，再將每一列歸一化，目的是為了強(qiáng)鄰居的連接更強(qiáng)， 弱鄰居的連接更弱，也就是讓轉(zhuǎn)移矩陣中概率大的概率更大，而小的更小。 這兩個(gè)操作重復(fù)執(zhí)行一直到概率轉(zhuǎn)移矩陣收斂為止，得到最終的矩陣，根據(jù)最終的矩陣便可得結(jié)果。

MCL算法對(duì)無(wú)權(quán)圖及有權(quán)圖均試用，劃分的子圖個(gè)數(shù)無(wú)需事先設(shè)定，這是該算法的 最大優(yōu)勢(shì); 劃分的子圖是非均勻的，試用于長(zhǎng)尾分布的數(shù)據(jù)。 下圖就是利用 MCL 進(jìn)行圖劃分的結(jié)果：

但是MCL算法對(duì)圖的直徑較大的情況不適用。(直徑是指兩個(gè)點(diǎn)之間的距離最大值，距離是兩個(gè)點(diǎn)之間的所有路的長(zhǎng)度的最小值)