【技術分享】唯品會圖卷積算法簡介和應用

百家 作者:唯品會安全 2019-08-28 08:36:19 閱讀:74


鳴 謝

VSRC感謝業界小伙伴——sneutrino 分享原創類文章。VSRC歡迎精品原創類文章投稿,優秀文章一旦采納發布,將有好禮相送,我們已為您準備好了豐富的獎品!

(活動最終解釋權歸VSRC所有)




1、基本介紹

近幾年來,深度學習取得了突破式的進展,特別是在圖像處理和機器翻譯領域。在這里面扮演關鍵角色的是卷積神經網絡。

卷積神經網絡可以非常有效地處理網格狀結構類數據,即數據有規律的分布在一定區域。比如對于彩色照片,由R,G,B三基色矩陣構成,每個矩陣的尺寸為照片尺寸,矩陣元描述該像素點紅(綠、藍)的程度,矩陣元的取值范圍為0-255的整數;對于機器翻譯,輸入的數據結構為詞向量組成的序列。

圖1:CNN卷積過程


對于這類網格狀的數據,通過訓練尺寸統一的局部過濾器(filter),將過濾器作用在輸入數據的各個區域,從而為后續的計算提取出需要的特征。如圖1所示。




1.1

圖類型數據和神經網絡

然而在工程生產的過程中,存在大量的無法表示為網格拓撲結構的數據,比如,社會網絡,生物網絡,蛋白質結構等,這類數據的特點在于:數據結構上沒有固定的拓撲結構,不像照片那樣為固定的網狀結構,即每個頂點周圍的頂點不具有明確的順序性,比如對于照片中的每個像素點,其周圍的像素點可按照一定的空間位置順序排序(從左到右,從上到下);而圖類數據不具有這類特點,比如在社會關系網絡中,每個頂點(node)的鄰接頂點無法通過空間位置信息進行排序。同時,每個頂點周圍的鄰接點的數目也不固定,這導致無法像處理照片那樣建立卷積神經網絡--通過訓練通用的同一尺寸的過濾器來自動提取特征。

圖卷積神經網絡便被用來處理這類數據,這類問題中,有一類為半監督學習,對圖上的每個頂點進行分類:圖上的頂點只有少部分具有標簽(label),其余的無標簽數據都是待分類數據;頂點之間由無向邊(edge)互相連接,表明頂點和頂點之間具有某種聯系。圖2即為圖(graph)的直觀表示。

傳統的神經網絡(NN)分類往往將每個數據樣本本身的高維特征輸入到多層神經網絡內,通過逐層向前傳播不斷提取信息,最后進行分類,然而其不足在于無法利用關聯數據。對于圖卷積神經網絡(GNN),在每一次向前傳播的過程中,隱藏層的特征還與其臨界點有關。

圖2




2、常用的算法

如今已有大量算法處理圖類數據。本文將介紹兩篇近期比較流行的文章:Tomas N.Kipf的 Semi-supervised Classification with Graph Convolutional Network和 Peter Velickovic的Graph Attention Network。

我們首先簡單介紹GCN和GAT算法,了解二者之間的關系。隨后,我們介紹一下在唯品會安全場景下我們對GCN算法的應用,以及程序和訓練參數設置。最后是我們的總結和展望。



2.1

圖的數學表示

為了簡單考慮,只考慮無向圖。對于無向圖,其為頂點和邊的集合,每個圖有N個頂點,以及一系列的邊通過圖上的關聯關系,可以得到N*N的鄰接矩陣A,同時通過鄰接矩陣還可以得到對角矩陣度矩陣對于鄰接矩陣當頂點和頂點相連時,,否則,所以鄰接矩陣描述了圖中頂點之間的連接情況。度矩陣則描述了對于每個頂點有多少個頂點在它周圍。這些是非常直觀的數學解釋。

通常情況下會對鄰接矩陣考慮自連接,所以使用,其中為N*N的單位矩陣,表示每個點都和自己連接;同時度矩陣可以重新定義為



2.2

圖卷積

圖卷積可以表示為:

參考Kipf的文章,文章中計算得出了如下近似:

其中為歸一化的鄰接矩陣。可以發現,數據的特征矩陣(N個頂點,每個頂點有C維特征),卷積后得到了如下新的特征矩陣:

這里Z為N*F的矩陣,卷積核W為C*F的矩陣。上式等號右邊可以看作三個矩陣的相乘,項和前饋神經網絡的特征提取一樣;不同之處在于,展開后表示為:

由于只在頂點的鄰接點和自身處取值為1,其余為0,所以求和只對鄰接點以及自身進行,最后的特征為鄰接點(包括自身)臨時特征的算術平均。



2.3

半監督頂點分類學習

頂點的分類問題是半監督學習任務:只知道圖中部分頂點的標簽,需要將無標簽的頂點進行分類。

圖卷積神經網絡的每一層卷積結束后使用ReLU激活函數:

最后一層使用softmax函數進行分類:

?其中為倒數第二層的輸出結果。

進行模型訓練,損失函數(loss function)為交叉熵函數,由于在圖中只有部頂點帶有標簽,所以最后的求和只對有標簽的數據進行求和:



2.4

自注意力機制改進:GAT

通過上面的介紹可以看出,以上的方法有改進的空間。GCN算法在計算隱藏層特征時,鄰接頂點對該頂點有等權重的影響,但實際情況中并非如此,可以利用兩兩頂點的特征計算關聯的重要性。

在Velickovic的文章中,作者引入了自注意力機制(self-attention),用于優化隱藏層的特征的計算,該算法為GAT算法。任意頂點的不同鄰接點,其對隱藏層的特征計算的權重是不一樣的。比如,單個頂點的輸入特征向量為時,進行一次卷積計算后,可以初步得到特征:,隨后進行卷積計算。在上面的GCN算法中最后確定的特征為:

這里n表示該頂點的鄰接點個數,求和的對象包括該頂點本身。而在GAT算法中,隱藏層特征表示為:

不同鄰接點對該頂點的影響是不一樣的,我們可以構建通用的神經網絡,用于計算自注意力系數接下來我們計算自注意力系數,該系數的求取使用的是單層的向前傳播神經網絡,激活函數為LeakyReLU,其輸入為頂點和鄰接點的特征:

該公式計算了頂點j對頂點i的重要程度。對所有鄰接點(包括自身)計算完該系數后,我們可以利用softmax函數對所有的注意力系數進行歸一化:

在得到歸一化的注意力系數之后,我們便可以簡單得到維數為k’的隱藏層的新特征。

為了能夠讓學習的過程具有較好的穩定性,文章中使用了多頭注意力機制:即使用K個注意力機制的神經網絡,它們得到的結果合并起來形成隱藏層的特征向量,從而進一步修正上面的公式,我們可以得到:

這樣,我們新得到的隱藏層的特征維數為KF’。這里,(公式)為連接算符,將兩個高維向量連接為一個更高維的向量。這個多頭計算過程有點類似于CNN中,每層卷積都使用了多個卷積核,多個卷積核的作用就是為了提升模型的穩定性以及提取盡可能多的特征。

而對于輸出層,如果我們采用和隱藏層一樣的多頭注意力機制,則不能簡單的將每個頭的輸出進行拼接,文章中采用了輸出特征平均的方法,隨后使用softmax函數來作為激活函數,用于分類。

圖3:注意力機制下的注意力系數計算和隱藏層特征計算



2.5

算法總結

常規的神經網絡算法中,我們通過輸入樣本實例的特征,逐層向前傳播提取有用信息,最后給出分類結果,這類方法已經取得了很大的成功。但是許多數據,實例和實例之間還有各種關聯,常規的神經網絡無法利用這部分信息。

GCN算法改進了常規的神經網絡算法,將實例之間的關系利用起來,每個樣本在隱藏層的特征不僅僅和自己的特征有關,還和其關聯樣本的特征有關,每個樣本點在隱藏層的特征是其自身新特征和鄰接點新特征的算術平均。但由于關聯信息在算法中的利用只是關聯點特征的算術平均,這點值得優化。

在GAT算法中,使用了自注意力機制,樣本點的隱藏層特征是自身新特征和鄰接點新特征的加權平均,其權值由每層通用的神經網絡決定,該神經網絡的輸入為相關聯的兩個頂點的特征,為單層神經網絡,這樣可以很好的反映不同鄰接點對頂點的影響程度,同時,每層使用了多頭的自注意力神經網絡,這種多頭設計非常類似于CNN中,每層卷積使用多個卷積核,這樣可以進一步增強模型的穩定性。

可見GCN和GAT都極大的利用了數據樣本之間的關聯信息,相比常規的NN算法而言,更有效的挖掘了數據所的信息。同時GAT相比于GCN,使用了多頭的自注意力機制,進一步優化了隱藏層的特征更新。




3、我們的應用

3.1

應用場景

在唯品會購物平臺上,大多數用戶都是正常用戶,少部分為非正常用戶,有的往往注冊多個小號,成為馬甲用戶;有的代客下單;有的直接使用機器行為搶購商品。這些非正常用戶影響了我們公司的運營,更重要的是影響了其他正常用戶的購物體驗,許多優惠商品和高價值的商品都被這些非正常用戶一掃而空。

對于所有的注冊用戶,我們根據他們的不同種類的行為進行不同評分,一般有幾類,比如注冊評分,登陸評分等等,評分過高的用戶普遍為可疑用戶。同時,用戶之間可以通過各種方式關聯起來,比如使用的設備,電話號碼,收貨地址等。

在這個由用戶組成的關系圖中,一些較新的用戶暫時沒有太多評分,一些很老的用戶得分也不是很全,還有一些用戶有評分但是介于正常和非正常得分之間。為了挖掘這部分用戶的性質,我們可以使用他們的關聯數據進一步得判斷。



3.2

模型構建

為了進一步挖掘惡意用戶,我們嘗試利用這些關聯數據。作為簡單嘗試,我們使用GCN算法,其包含:四個輸入單元,為四類評分方式的得分;包含了三個隱藏層,每層隱藏層包含32,8,4個激活單元,使用ReLU激活函數;由于是二分類問題,輸出層包含兩個輸出單元,最后的分類使用softmax進行分類。學習效率,為了防止過擬合,我們使用dropoup = 0.15。同時我們設置epoch = 2000。

我們首先挑選近期活躍用戶,以及和他們有一度關聯的用戶,將他們四類用戶評分作為輸入,對于評分只要存在非常高得分的(大于等于90分以上)的用戶作為馬甲用戶,評分都低于30分的用戶作為正常用戶,介于這二者之間的、以及沒有得分的為待評估用戶。



3.3

程序

使用的程序為kipf在github上的代碼,下載地址為https://github.com/tkipf/gcn,該代碼需要tensorflow和networkx兩個庫。

我們的模型輸入包含三個pickle文件:1)表明用戶之間關系的文件,為字典格式,字典的鍵為用戶UID,字典的值為與其相關聯用戶組成的集合;2)用戶得分文件,為numpy array格式,記錄了每個用戶的三種評分;3)用戶標簽文件,為numpy array格式,記錄每個用戶的標簽,為one-hot表示,負樣本為[1, 0],正樣本為[0, 1],對于那些缺乏標簽的用戶設定為[0, 0]。

首先導入數據,我們首先利用networkx處理第一個pickle文件,得到鄰接矩陣。由于可使用數據充足,我們將全量數據分成三等分:training,validation,testing。原程序中使用的數據為sparse matrix,我們的輸入數據和處理后得到的數據均為sparse matrix類型。

在特征預處理過程中,由于各種得分的跨度較大,為了均衡處理每種得分在損失函數中的權重,我們使用了sk-learn中的StandardScaler類,利用該類的transform方法讓每個特征分布在0到1這樣一個區間里面:

對于模型部分,Layer的定義至關重要,可參考原程序GraphConvolution 類的定義:

圖卷積類中最重要的是私有方法_call(最后被特殊方法__call__調用,這樣該類可以像函數那樣調用),首先實現的是dropout;隨后根據GCN中卷積計算公式,分別進行sparse矩陣相乘:權重和輸入相乘得到初步隱藏層特征,隨后支持度矩陣和初步隱藏層特征相乘,得到輸出;最后,如果需要加入偏執,則最后在output中加入偏執。

由于原代碼中只實現了兩層圖卷積,我們重新實現了多層圖卷積神經網絡,從而方便實現任意層數的卷積神經網絡:

進行訓練,最重要的是定義損失函數:

損失函數分成兩部分,第一部分使用weight decay,確保權重都是較小的值,第二部分則是模型預測結果的交叉熵,由于我們只關心打了標簽的數據,所以最后的交叉熵關注的是有標簽實例。

在預處理完成數據之后,我們的便可以開始常規的tensorflow模型訓練過程。



3.4

訓練結果

訓練后我們發現,該模型的正確率為0.959,準確率為0.979,召回率為0.940。同時我們輸出那些被“誤判”的正常用戶,發現,他們普遍存在問題,比如和上百個用戶關聯,或者其關聯的十多個用戶中一半以上是非正常用戶等等。




4、展望和總結

本文介紹了最近比較流行的GCN和GAT算法,相比于傳統的DNN算法,GCN和GAT考慮了樣本點之間的關系,提取出了更多的信息。而GAT相比于GCN,使用了注意力機制,從而可以量化樣本點之間的關聯強弱,優化了隱藏層的特征提取,可以有效的提升模型的健壯性。

在這兩類模型中,都只是考慮了頂點的特征,在GAT中,注意力權重也只是和兩兩頂點的特征相關,而沒有考慮邊(關聯方式)的特征。而在關聯方式中,依舊存在大量的信息值得我們去挖掘和提取。

本文暫時只是使用了GCN 算法,在后期,我們也將嘗試GAT算法,以及嘗試其他圖卷積算法,比如考慮邊的性質。




精彩原創文章投稿有驚喜!

歡迎投稿!

VSRC歡迎精品原創類文章投稿,優秀文章一旦采納發布,將為您準備的豐富獎金稅后1000元現金或等值禮品,上不封頂!如若是安全文章連載,獎金更加豐厚,稅后10000元或等值禮品,上不封頂!可點擊“閱讀原文”了解規則。(最終獎勵以文章質量為準。活動最終解釋權歸VSRC所有)



我們聆聽您寶貴建議


不知道,大家都喜歡閱讀哪些類型的信息安全文章?

不知道,大家都希望我們更新關于哪些主題的干貨?

現在起,只要您有任何想法或建議,歡迎直接回復本公眾號留言!

精彩留言互動的熱心用戶,將有機會獲得VSRC贈送的精美獎品一份!

同時,我們也會根據大家反饋的建議,選取熱門話題,進行原創發布!



點擊閱讀原文進入 ? 為了掙到10000塊,他在VSRC投了一篇稿!



關注公眾號:拾黑(shiheibook)了解更多

[廣告]贊助鏈接:

選擇AiDeep,讓人工智能為你工作:http://www.aideep.com/
四季很好,只要有你,文娛排行榜:http://www.yaopaiming.com/
讓資訊觸達的更精準有趣:https://www.0xu.cn/

關注網絡尖刀微信公眾號
隨時掌握互聯網精彩
百度熱搜榜
排名 熱點 搜索指數
急冻钻石闯关
中国体育彩票大乐透 下载陕西星悦麻将 河南快三计划软件手机版式 苹果如何下载熊猫棋牌app 快乐十分走势全 35选7走势图综合版辽宁 河南豫四方麻将下载 十大股票交易平台 国际象棋兵 山东体彩11选5一 河北十一选五遗漏t 安徽11选5前三遗漏数据 永利棋牌游戏下载 双彩p3开机号 山西11选5任选五推荐号 北京赛车pk10直播开奖