基于GNN雙源學(xué)習(xí)的訪問控制關(guān)系預(yù)測方法

單棣斌，杜學(xué)繪，王文娟，劉敖迪，王娜

基于GNN雙源學(xué)習(xí)的訪問控制關(guān)系預(yù)測方法

單棣斌，杜學(xué)繪，王文娟，劉敖迪，王娜

（信息工程大學(xué)，河南 鄭州 450001）

隨著大數(shù)據(jù)技術(shù)的迅速發(fā)展和廣泛應(yīng)用，用戶越權(quán)訪問成為制約大數(shù)據(jù)資源安全共享、受控訪問的主要問題之一。基于關(guān)系的訪問控制（ReBAC，relation-based access control）模型利用實(shí)體之間關(guān)系制定訪問控制規(guī)則，增強(qiáng)了策略的邏輯表達(dá)能力，實(shí)現(xiàn)了動態(tài)訪問控制，但仍然面臨著實(shí)體關(guān)系數(shù)據(jù)缺失、規(guī)則的關(guān)系路徑復(fù)雜等問題。為克服這些問題，提出了一種基于GNN雙源學(xué)習(xí)的邊預(yù)測模型——LPMDLG，將大數(shù)據(jù)實(shí)體關(guān)系預(yù)測問題轉(zhuǎn)化為有向多重圖的邊預(yù)測問題。提出了基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)方法和有向雙半徑節(jié)點(diǎn)標(biāo)記算法，通過有向包圍子圖提取、子圖節(jié)點(diǎn)標(biāo)記計(jì)算和拓?fù)浣Y(jié)構(gòu)特征學(xué)習(xí)3個環(huán)節(jié)，從實(shí)體關(guān)系圖中學(xué)習(xí)節(jié)點(diǎn)與子圖的拓?fù)浣Y(jié)構(gòu)特征；提出了基于有向鄰居子圖的節(jié)點(diǎn)嵌入特征學(xué)習(xí)方法，融入了注意力系數(shù)、關(guān)系類型等要素，通過有向鄰居子圖提取、節(jié)點(diǎn)嵌入特征學(xué)習(xí)等環(huán)節(jié)，學(xué)習(xí)其節(jié)點(diǎn)嵌入特征；設(shè)計(jì)了雙源融合的評分網(wǎng)絡(luò)，將拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)嵌入聯(lián)合計(jì)算邊的得分，從而獲得實(shí)體關(guān)系圖的邊預(yù)測結(jié)果。邊預(yù)測實(shí)驗(yàn)結(jié)果表明，相較于R-GCN、SEAL、GraIL、TACT等基線模型，所提模型在AUC-PR、MRR和Hits@等評價(jià)指標(biāo)下均獲得更優(yōu)的預(yù)測結(jié)果；消融實(shí)驗(yàn)結(jié)果說明所提模型的雙源學(xué)習(xí)模式優(yōu)于單一模式的邊預(yù)測效果；規(guī)則匹配實(shí)驗(yàn)結(jié)果驗(yàn)證了所提模型實(shí)現(xiàn)了對部分實(shí)體的自動授權(quán)和對規(guī)則的關(guān)系路徑的壓縮。所提模型有效提升了邊預(yù)測的效果，能夠滿足大數(shù)據(jù)訪問控制關(guān)系預(yù)測需求。

大數(shù)據(jù)；基于關(guān)系的訪問控制；邊預(yù)測；圖神經(jīng)網(wǎng)絡(luò)

0 引言

大數(shù)據(jù)的廣泛應(yīng)用，有力推動了社會進(jìn)步與經(jīng)濟(jì)發(fā)展。但是大數(shù)據(jù)在迅速發(fā)展的同時，面臨諸多安全威脅，其中用戶越權(quán)訪問資源是制約大數(shù)據(jù)資源安全共享、受控訪問的主要問題。

訪問控制是實(shí)現(xiàn)大數(shù)據(jù)安全可控的重要技術(shù)手段之一。由于大數(shù)據(jù)具有資源數(shù)量巨大、資源動態(tài)生成、主體客體關(guān)系復(fù)雜等特點(diǎn)，傳統(tǒng)的訪問控制模型，如自主訪問控制（DAC，discretionary access control）、強(qiáng)制訪問控制（MAC，mandatory access control）、基于角色的訪問控制（RBAC，role-based access control）等，處理大數(shù)據(jù)訪問控制時，會面臨訪問控制策略配置負(fù)擔(dān)重、靜態(tài)策略不能預(yù)判動態(tài)資源生成、難以滿足復(fù)雜數(shù)據(jù)用戶關(guān)系與類型的安全約束等問題[1]。

基于關(guān)系的訪問控制（ReBAC，relationship- based access control）[2-4]將實(shí)體之間（如主體與主體、主體與客體等）的關(guān)系路徑RP（relationship path）[5-6]作為已知的基礎(chǔ)數(shù)據(jù)，并利用這些數(shù)據(jù)制定基于關(guān)系的訪問控制規(guī)則。ReBAC實(shí)現(xiàn)了對基于屬性的訪問控制[7]策略的擴(kuò)展[3,6]，增強(qiáng)了訪問控制策略的邏輯表達(dá)能力，使訪問控制變得更加動態(tài)和靈活。文獻(xiàn)[8-12]研究了ReBAC策略挖掘和學(xué)習(xí)算法，實(shí)現(xiàn)了將傳統(tǒng)訪問控制規(guī)則轉(zhuǎn)化為ReBAC規(guī)則，便于ReBAC策略的應(yīng)用與發(fā)展。但是在社交網(wǎng)絡(luò)、購物平臺、電子醫(yī)療等大數(shù)據(jù)平臺中，人工、半人工建立的關(guān)系數(shù)據(jù)通常是有限的、不完整的，而關(guān)系數(shù)據(jù)的缺失不可避免地會影響基于關(guān)系訪問控制規(guī)則的完備性，并且會增加訪問控制規(guī)則中關(guān)系路徑的復(fù)雜度。

針對實(shí)體關(guān)系數(shù)據(jù)缺失問題，可以通過預(yù)測和補(bǔ)全隱含存在的實(shí)體之間的關(guān)系及類型來解決。由于大數(shù)據(jù)系統(tǒng)中的實(shí)體關(guān)系數(shù)據(jù)集可構(gòu)成以實(shí)體為節(jié)點(diǎn)、實(shí)體關(guān)系為邊的大規(guī)模、復(fù)雜的有向多重圖，因此關(guān)系預(yù)測和補(bǔ)全本質(zhì)上是關(guān)系圖中節(jié)點(diǎn)之間的邊預(yù)測問題。

傳統(tǒng)的邊預(yù)測方法[13]，主要通過計(jì)算目標(biāo)節(jié)點(diǎn)相似性得分、分解網(wǎng)絡(luò)的矩陣表示等實(shí)現(xiàn)邊預(yù)測。隨著圖神經(jīng)網(wǎng)絡(luò)（GNN，graph neural network）技術(shù)的發(fā)展與應(yīng)用，基于圖神經(jīng)網(wǎng)絡(luò)的邊預(yù)測方法，如R-GCN（relational graph convolutional network）[14]、SEAL（learning from subgraphs，embeddings and attributes for link prediction）[15]、GraIL（graph inductive learning）[16]、TACT（topology-aware correlations）[17]等模型，通過圖形拓?fù)洹⒐?jié)點(diǎn)與邊特征的學(xué)習(xí)實(shí)現(xiàn)對目標(biāo)節(jié)點(diǎn)進(jìn)行邊預(yù)測，實(shí)驗(yàn)結(jié)果顯示其預(yù)測結(jié)果優(yōu)于傳統(tǒng)方法[18-21]。

但是基于圖神經(jīng)網(wǎng)絡(luò)的邊預(yù)測方法在處理復(fù)雜關(guān)系圖時，存在以下問題。一是R-GCN、SEAL、GraIL、TACT等邊預(yù)測模型的學(xué)習(xí)信息不夠全面，沒有同時兼顧拓?fù)浣Y(jié)構(gòu)特征、節(jié)點(diǎn)自身特征、節(jié)點(diǎn)類型等要素信息，降低了圖表示能力。二是SEAL、TACT等模型在拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)過程沒有考慮邊方向、邊類型、多重邊等特征，會將非同類別的邊或節(jié)點(diǎn)歸為一類，不同類型的邊預(yù)測時可能造成混淆。三是R-GCN、SEAL等模型沒有區(qū)分和學(xué)習(xí)不同鄰居節(jié)點(diǎn)的不同權(quán)重，可能造成節(jié)點(diǎn)嵌入特征受到非關(guān)鍵鄰居節(jié)點(diǎn)的干擾。以上3個方面降低了邊預(yù)測結(jié)果的準(zhǔn)確性。

為克服現(xiàn)有邊預(yù)測技術(shù)在解決復(fù)雜關(guān)系圖網(wǎng)絡(luò)邊預(yù)測問題時的不足，本文提出了一種基于圖神經(jīng)網(wǎng)絡(luò)雙源學(xué)習(xí)的邊預(yù)測模型。該模型依據(jù)關(guān)系數(shù)據(jù)集建立實(shí)體關(guān)系圖，將大數(shù)據(jù)訪問控制實(shí)體關(guān)系預(yù)測問題轉(zhuǎn)化為有向多重圖的邊預(yù)測問題；提出了基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)方法，通過有向包圍子圖提取、子圖節(jié)點(diǎn)標(biāo)記計(jì)算和拓?fù)浣Y(jié)構(gòu)特征學(xué)習(xí)3個環(huán)節(jié)，從實(shí)體關(guān)系圖中學(xué)習(xí)其節(jié)點(diǎn)與子圖的拓?fù)浣Y(jié)構(gòu)特征；提出了基于有向鄰居子圖的節(jié)點(diǎn)嵌入學(xué)習(xí)方法，通過有向鄰居子圖提取、節(jié)點(diǎn)嵌入特征學(xué)習(xí)等環(huán)節(jié)，學(xué)習(xí)其節(jié)點(diǎn)嵌入特征；設(shè)計(jì)了雙源融合的評分網(wǎng)絡(luò)，將拓?fù)浣Y(jié)構(gòu)特征與節(jié)點(diǎn)嵌入特征聯(lián)合計(jì)算目標(biāo)節(jié)點(diǎn)間邊的得分，從而得到邊預(yù)測結(jié)果。

1 相關(guān)研究

1.1 邊預(yù)測優(yōu)化ReBAC的可行性分析

邊預(yù)測，也被稱為鏈接預(yù)測，是預(yù)測網(wǎng)絡(luò)中兩個節(jié)點(diǎn)之間是否存在邊（鏈接）的問題[22]。由于圖網(wǎng)絡(luò)的普遍存在，邊預(yù)測在許多領(lǐng)域得到了應(yīng)用[13]，如社交網(wǎng)絡(luò)中的朋友推薦[23]、論文引用網(wǎng)絡(luò)中的合著作者預(yù)測[24]、藥物反應(yīng)預(yù)測[25]、知識圖的補(bǔ)全[26]等。邊預(yù)測研究[13]主要包括傳統(tǒng)邊預(yù)測方法和基于GNN的邊預(yù)測方法。

ReBAC規(guī)則是基于實(shí)體關(guān)系路徑[27-29]制定的，與訪問控制相關(guān)的實(shí)體（作為節(jié)點(diǎn)）和它們之間的關(guān)系（作為邊）構(gòu)成了實(shí)體關(guān)系圖。通過對實(shí)體關(guān)系圖進(jìn)行邊預(yù)測，可以學(xué)習(xí)到潛在的實(shí)體關(guān)系，解決其面臨的關(guān)系缺失問題，從而增強(qiáng)ReBAC自動化動態(tài)授權(quán)的能力，簡化基于原有關(guān)系建立的訪問控制規(guī)則。

以某醫(yī)療信息系統(tǒng)的ReBAC策略為例，系統(tǒng)中包括基于關(guān)系的訪問控制規(guī)則[8]（為明確問題，本文對該規(guī)則進(jìn)行了適度簡化）如下。規(guī)則1：醫(yī)生可以查閱他/她所屬的醫(yī)療團(tuán)隊(duì)治療的患者的電子健康記錄（HRs，health records），表示為 team patientresource，{read}>。規(guī)則2：管理電子健康記錄的醫(yī)生可以查閱這些電子健康記錄，表示為resource, {read}>。

原始的實(shí)體關(guān)系圖（如圖1(a)所示）中，節(jié)點(diǎn)、、表示醫(yī)生doctor，節(jié)點(diǎn)表示醫(yī)療團(tuán)隊(duì)team，節(jié)點(diǎn)表示患者patient，節(jié)點(diǎn)表示電子健康記錄HR。其中，醫(yī)生屬于團(tuán)隊(duì)，醫(yī)生是的團(tuán)隊(duì)同事，醫(yī)生負(fù)責(zé)管理電子健康記錄。關(guān)系1表示團(tuán)隊(duì)同事teammate_of，2表示屬于成員part_of，3表示治療關(guān)系treat，4表示擁有have，5表示管理manage。健康記錄的擁有者是患者，由團(tuán)隊(duì)進(jìn)行治療，即節(jié)點(diǎn)與節(jié)點(diǎn)之間組成一條關(guān)系路徑1：<2><3><4>，滿足規(guī)則1，所以可以查閱。醫(yī)生管理電子健康記錄HRs，即節(jié)點(diǎn)與節(jié)點(diǎn)之間組成一條關(guān)系路徑2：<5>，滿足規(guī)則2，所以可以查閱。

通過邊預(yù)測，可以對實(shí)體實(shí)現(xiàn)自動化的動態(tài)授權(quán)。例如，圖1(b)中，節(jié)點(diǎn)與節(jié)點(diǎn)滿足關(guān)系：<1>，即醫(yī)生是的團(tuán)隊(duì)同事。節(jié)點(diǎn)滿足<2>，如果可以預(yù)測<2>，則與也滿足關(guān)系路徑1，即滿足規(guī)則1，醫(yī)生也可以查閱健康記錄，那么自動為醫(yī)生進(jìn)行授權(quán)。

通過邊預(yù)測，可以簡化匹配ReBAC規(guī)則中的關(guān)系路徑。例如，圖1(b)中，節(jié)點(diǎn)與節(jié)點(diǎn)滿足關(guān)系：<1>，即醫(yī)生是的團(tuán)隊(duì)同事。節(jié)點(diǎn)滿足<5>，如果可以預(yù)測<5>，則滿足規(guī)則2，醫(yī)生可以查閱，那么將原來匹配的關(guān)系路徑<2><3><4>簡化為關(guān)系路徑<5>。

圖1 邊預(yù)測優(yōu)化ReBAC可行性分析

Figure 1 Feasibility analysis of link prediction for ReBAC optimization

1.2 傳統(tǒng)邊預(yù)測方法

傳統(tǒng)邊預(yù)測方法主要包括啟發(fā)式方法、潛在特征方法兩類。

啟發(fā)式方法使用簡單而有效的節(jié)點(diǎn)相似性分?jǐn)?shù)作為鏈接的可能性的度量標(biāo)準(zhǔn)，如公共鄰居（CN，common neighbor）、RPR（rooted page rank）[30]等方法，其主要思路是首先假定滿足預(yù)定義特征的兩個節(jié)點(diǎn)存在邊，再通過CN節(jié)點(diǎn)數(shù)量、Jaccard分?jǐn)?shù)、Katz指數(shù)等方法計(jì)算特征值從而進(jìn)行邊預(yù)測。但是這些預(yù)先定義的特征表達(dá)能力有限，只能描述部分的、局部的圖結(jié)構(gòu)模式。因此，啟發(fā)式方法一般用于同構(gòu)圖的邊預(yù)測，很難應(yīng)用于具有復(fù)雜形成機(jī)制的網(wǎng)絡(luò)。

潛在特征方法通常以節(jié)點(diǎn)的潛在屬性或表示為基礎(chǔ)，通過矩陣分解[31]、網(wǎng)絡(luò)嵌入[32]等方法實(shí)現(xiàn)邊的預(yù)測。這些方法本質(zhì)上是從圖結(jié)構(gòu)中提取低維節(jié)點(diǎn)嵌入信息，但不能捕捉節(jié)點(diǎn)之間的結(jié)構(gòu)相似性[33]，即共享相同鄰域結(jié)構(gòu)的兩個節(jié)點(diǎn)沒有映射到相似的嵌入；潛在特征方法屬于直推式學(xué)習(xí)方法，學(xué)習(xí)的節(jié)點(diǎn)嵌入不能推廣到新節(jié)點(diǎn)或新網(wǎng)絡(luò)。

1.3 基于GNN的邊預(yù)測方法

隨著圖神經(jīng)網(wǎng)絡(luò)的發(fā)展，基于GNN的圖表示學(xué)習(xí)應(yīng)用于邊預(yù)測中，取得了較好的效果。基于GNN的邊預(yù)測方法分為基于節(jié)點(diǎn)的GNN方法和基于子圖的GNN方法。

（1）基于節(jié)點(diǎn)的GNN方法

基于節(jié)點(diǎn)的GNN方法從圖的局部鄰域中學(xué)習(xí)節(jié)點(diǎn)嵌入，將GNN學(xué)習(xí)的成對的節(jié)點(diǎn)嵌入聚合為邊的表示，如圖自動編碼器（GAE，graph auto encoder）、可變圖自動編碼器（VGAE，variational graph auto encoder）[18]、R-GCN[14]等模型。

此類方法分別獨(dú)立計(jì)算兩個目標(biāo)節(jié)點(diǎn)的表示，沒有考慮兩個節(jié)點(diǎn)之間的相對位置、關(guān)聯(lián)信息和公共鄰居，從而造成聚合后的邊表示結(jié)果出現(xiàn)偏差。此類方法的多數(shù)模型沒有區(qū)分不同類別鄰居節(jié)點(diǎn)的不同權(quán)重，不支持鄰居節(jié)點(diǎn)重要程度的自動學(xué)習(xí)，從而影響邊預(yù)測結(jié)果。

（2）基于子圖的GNN方法

基于子圖的GNN方法首先提取每個目標(biāo)邊周圍的局部子圖，然后對子圖中節(jié)點(diǎn)計(jì)算標(biāo)記，最后通過GNN學(xué)習(xí)子圖表示邊預(yù)測，如SEAL[15]、IGMC[34]、GraIL[16]等模型。Zhang等[15]通過衰變啟發(fā)式理論驗(yàn)證了包圍子圖進(jìn)行邊預(yù)測的可行性，目標(biāo)節(jié)點(diǎn)周圍的局部子圖充分考慮了節(jié)點(diǎn)、邊以及它們周圍鄰居的拓?fù)浣Y(jié)構(gòu)特征。標(biāo)記方法[15-16]可對目標(biāo)節(jié)點(diǎn)及共同鄰居節(jié)點(diǎn)之間的關(guān)聯(lián)進(jìn)行建模，從而比基于節(jié)點(diǎn)的GNN方法具有更好的邊預(yù)測效果[35]。

但是，此類方法的很多模型提取的局部包圍子圖忽視了邊的方向、類別（對應(yīng)不同的關(guān)系類型）對圖結(jié)構(gòu)特征的影響，并且標(biāo)記方法不支持對不同方向邊所連接節(jié)點(diǎn)進(jìn)行區(qū)分。SEAL模型只能處理無向簡單圖，未考慮邊方向、多重邊、關(guān)系類別等要素。多數(shù)模型只關(guān)注了圖結(jié)構(gòu)特征，沒有考慮節(jié)點(diǎn)的屬性特征信息，不能區(qū)分拓?fù)浣Y(jié)構(gòu)相同或相近、而節(jié)點(diǎn)特征不同的邊。GraIL只通過學(xué)習(xí)拓?fù)浣Y(jié)構(gòu)信息進(jìn)行邊預(yù)測，忽視了不同類型、不同特征的節(jié)點(diǎn)對邊預(yù)測結(jié)果的影響；TACT模型雖然綜合考慮了圖的拓?fù)浣Y(jié)構(gòu)和關(guān)系的相關(guān)性，但缺少對節(jié)點(diǎn)特征信息嵌入的學(xué)習(xí)，造成邊預(yù)測結(jié)果準(zhǔn)確性降低。

基于節(jié)點(diǎn)的GNN方法的輸入數(shù)據(jù)是圖節(jié)點(diǎn)特征信息（目標(biāo)節(jié)點(diǎn)特征及其鄰居節(jié)點(diǎn)特征信息），可以支持同質(zhì)圖節(jié)點(diǎn)、異質(zhì)圖節(jié)點(diǎn)特征信息，但不包括圖結(jié)構(gòu)信息。因此，在邊預(yù)測時會損失節(jié)點(diǎn)之間的相對位置信息和結(jié)構(gòu)關(guān)聯(lián)信息。基于子圖的GNN方法的輸入數(shù)據(jù)是圖結(jié)構(gòu)特征信息（包圍子圖的結(jié)構(gòu)、鄰居節(jié)點(diǎn)結(jié)構(gòu)信息），需要目標(biāo)節(jié)點(diǎn)屬于同一連通圖。由于不包括圖節(jié)點(diǎn)特征、邊方向等信息，所以多數(shù)基于子圖GNN方法的模型進(jìn)行邊預(yù)測時，只能支持同類型節(jié)點(diǎn)的無向圖。

在基于子圖GNN方法的基礎(chǔ)上，需要增加邊方向、邊類型以及相關(guān)節(jié)點(diǎn)的特征信息等要素，用于提高基于圖神經(jīng)網(wǎng)絡(luò)對實(shí)體關(guān)系圖進(jìn)行邊預(yù)測的準(zhǔn)確性，從而實(shí)現(xiàn)對訪問控制規(guī)則所需實(shí)體關(guān)系的預(yù)測和補(bǔ)充。

2 基于GNN雙源學(xué)習(xí)的邊預(yù)測模型

2.1 問題定義

由于在大數(shù)據(jù)系統(tǒng)的訪問控制場景中，實(shí)體與實(shí)體之間存在多種關(guān)系類型，本文將實(shí)體以及它們之間的關(guān)系定義為有向多重圖(,,)，表示節(jié)點(diǎn)集合，表示有向邊集合，表示關(guān)系集合。在中，節(jié)點(diǎn)∈，帶有標(biāo)簽的有向邊e=(,,) ∈，表示節(jié)點(diǎn)與之間存在標(biāo)簽為關(guān)系的邊e，是e的頭節(jié)點(diǎn)，是e的尾節(jié)點(diǎn)，∈表示一種關(guān)系類型。依據(jù)實(shí)體關(guān)系圖與有向多重圖之間的對應(yīng)關(guān)系，可以將實(shí)體之間的關(guān)系預(yù)測問題轉(zhuǎn)化為有向多重圖的邊預(yù)測問題，即預(yù)測有向多重圖中的兩個目標(biāo)節(jié)點(diǎn)之間是否存在某種類型有向邊的問題。

定義1 有向多重圖的邊預(yù)測：假設(shè)有向多重圖(,,)中，目標(biāo)節(jié)點(diǎn)、∈，判斷節(jié)點(diǎn)、之間是否存在關(guān)系為的邊e=(,,)的過程，被稱為有向多重圖的邊預(yù)測。

2.2 模型框架

本文在基于子圖的GNN方法的基礎(chǔ)上，融入了邊方向、邊類型、節(jié)點(diǎn)特征等要素，融合了多關(guān)系特殊化處理方法，設(shè)計(jì)了基于圖神經(jīng)網(wǎng)絡(luò)雙源學(xué)習(xí)的邊預(yù)測模型（LPMDLG，link prediction model based on dual-source learning of graph neural network）。LPMDLG框架如圖2所示。

圖2 LPMDLG框架

Figure 2 Framework of LPMDLG

第1步，由原始實(shí)體關(guān)系數(shù)據(jù)集生成原始實(shí)體關(guān)系圖，如圖3(a)所示。原始的實(shí)體關(guān)系數(shù)據(jù)集中的每個元素是一個由兩個實(shí)體和對應(yīng)關(guān)系組成的三元組，如<,,>表示實(shí)體與實(shí)體之間的關(guān)系為。將實(shí)體作為圖節(jié)點(diǎn)，關(guān)系作為圖節(jié)點(diǎn)之間的邊，遍歷集合中的每個三元組，可構(gòu)建數(shù)據(jù)集對應(yīng)的實(shí)體關(guān)系圖。

第2步，確定實(shí)體關(guān)系圖中目標(biāo)節(jié)點(diǎn)和的階鄰居集。

第3步，基于GNN進(jìn)行圖表示學(xué)習(xí)，包括基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)與基于有向鄰居子圖的節(jié)點(diǎn)嵌入學(xué)習(xí)兩個方法。基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)方法通過階鄰居集提取有向包圍子圖，計(jì)算子圖中節(jié)點(diǎn)的標(biāo)記值，基于節(jié)點(diǎn)標(biāo)記值進(jìn)行圖卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)，生成節(jié)點(diǎn)與包圍子圖的拓?fù)浣Y(jié)構(gòu)特征。同步地，基于有向鄰居子圖的節(jié)點(diǎn)嵌入學(xué)習(xí)方法通過階鄰居集提取有向鄰居子圖，通過圖卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)獲得節(jié)點(diǎn)與鄰居子圖的嵌入特征。

圖3 原始實(shí)體關(guān)系圖與包圍子圖示例

Figure 3 Example of original entityrelationship graph and enclosing subgraph

第4步，將兩個方法學(xué)習(xí)的輸出結(jié)果相結(jié)合，由評分網(wǎng)絡(luò)進(jìn)行綜合打分，得到目標(biāo)節(jié)點(diǎn)之間存在邊（實(shí)體關(guān)系）的預(yù)測結(jié)果。

2.3 K階鄰居集的確定

確定目標(biāo)節(jié)點(diǎn)的鄰居集，是進(jìn)行拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)和節(jié)點(diǎn)嵌入學(xué)習(xí)的基礎(chǔ)。本文提出了計(jì)算目標(biāo)節(jié)點(diǎn)的階鄰居集的方法，過程如下。

1) 將原始實(shí)體關(guān)系圖（有向多重圖）轉(zhuǎn)換為無向圖，即為的底圖[36]。

2) 基于廣度優(yōu)先算法，在底圖中查找目標(biāo)節(jié)點(diǎn)的跳鄰居節(jié)點(diǎn)，構(gòu)成節(jié)點(diǎn)的階鄰居集合N()，即底圖中鄰居節(jié)點(diǎn)到的距離不大于。通過同樣方法得到節(jié)點(diǎn)的階鄰居集合N()。

2.4 基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)方法

基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)方法通過圖神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)目標(biāo)節(jié)點(diǎn)及其有向包圍子圖的拓?fù)浣Y(jié)構(gòu)特征信息。該方法包括目標(biāo)節(jié)點(diǎn)的有向包圍子圖提取、子圖節(jié)點(diǎn)標(biāo)記計(jì)算和拓?fù)浣Y(jié)構(gòu)特征學(xué)習(xí)3個環(huán)節(jié)。

2.4.1 有向包圍子圖提取

SEAL、GraIL等模型采用局部包圍子圖的方法對目標(biāo)節(jié)點(diǎn)之間邊的可能性進(jìn)行分析和判斷。其提取過程是：首先，計(jì)算兩個節(jié)點(diǎn)和的鄰居集合N()和N()，其中表示鄰居的最大距離（無方向的）；其次，取N()和N()的交集，得到N()∩N()；最后，通過修剪孤立的或距離大于的節(jié)點(diǎn)來計(jì)算包圍子圖(,)（如圖3(b)藍(lán)色虛線所示）。

這種提取包圍子圖方法的不足包括兩方面。一是提取目標(biāo)節(jié)點(diǎn)的包圍子圖時沒有考慮邊的方向。所得到子圖中的節(jié)點(diǎn)及其周圍拓?fù)浣Y(jié)構(gòu)與有向圖中的拓?fù)浣Y(jié)構(gòu)不完全相同，如圖3(b)中，由于邊是無向的，節(jié)點(diǎn)到節(jié)點(diǎn)、、可達(dá)，但實(shí)際的原始實(shí)體關(guān)系圖（圖3(a)）中，節(jié)點(diǎn)到節(jié)點(diǎn)單步可達(dá)，而節(jié)點(diǎn)到節(jié)點(diǎn)、不是單步可達(dá)的。基于該包圍子圖進(jìn)行后續(xù)的節(jié)點(diǎn)標(biāo)記與結(jié)構(gòu)特征學(xué)習(xí)時，會出現(xiàn)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)不同而標(biāo)記相同的現(xiàn)象，無法區(qū)分不同方向的邊所連接的節(jié)點(diǎn)，如圖3(b)中不能區(qū)分節(jié)點(diǎn)、拓?fù)浣Y(jié)構(gòu)的不同。二是原始的包圍子圖沒有區(qū)分邊的不同類型（即不同的關(guān)系）。例如，圖3(a)中，邊e、e都是的接鄰邊，但兩條邊的類型不同，即所代表的實(shí)體關(guān)系屬于不同類別，分別是關(guān)系1、2。原始的包圍子圖將上述兩條邊當(dāng)作同一類別，如圖3(b)中，邊e、e的類型是相同的，那么在后續(xù)進(jìn)行拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)時，不能區(qū)分不同關(guān)系1、2對其產(chǎn)生的影響。

為克服上述不足，本文提出了有向包圍子圖提取方法。為了準(zhǔn)確描述提取方法，本文對關(guān)鍵術(shù)語進(jìn)行了如下定義。

定義2 路徑：有向圖中的一個路徑path是一個由頂點(diǎn)x和邊a交錯排列的序列=11223…x?1a?1x，=1,2,…,?1,中邊a的尾是頂點(diǎn)x，頭是頂點(diǎn)x+1，并且任意兩條邊是不相同的，頂點(diǎn)互不相同，也稱是一條從節(jié)點(diǎn)x到節(jié)點(diǎn)x的（1,x）路徑。

定義3 可達(dá)、逆向可達(dá)：如果有向圖中存在一條(,)路徑，則稱從節(jié)點(diǎn)到節(jié)點(diǎn)是可達(dá)的，節(jié)點(diǎn)到節(jié)點(diǎn)是逆向可達(dá)的。

定義4 距離：對于有向圖的節(jié)點(diǎn)和，如果節(jié)點(diǎn)到節(jié)點(diǎn)是可達(dá)的，那么從節(jié)點(diǎn)到節(jié)點(diǎn)的距離(,)是路徑(,)的最小長度，從節(jié)點(diǎn)到節(jié)點(diǎn)是逆向可達(dá)的，距離(,)=?(,)，否則記(,) = ∞。

定義5 底圖距離：稱有向圖的底圖中兩個頂點(diǎn)x，x之間的距離d(,)為底圖距離，定義為中最短路徑的長度。如果此路徑不存在，令d(,)=∞。

定義7 有向包圍子圖：對于一個有向多重圖=(,,)，給定目標(biāo)節(jié)點(diǎn)=｛,｝?，的階有向包圍子圖是由中與節(jié)點(diǎn)和的底圖距離不超過的節(jié)點(diǎn)集合組成的子圖，記為D(,) =(V,E,R)。其中V={|d(,) ≤∩d(,) ≤}, 表示有向包圍子圖的節(jié)點(diǎn)集，E={(,)|,∈V}，表示其有向邊集合，R?，表示其關(guān)系集合。

目標(biāo)節(jié)點(diǎn)｛,｝的有向包圍子圖提取過程如下。

1) 在的底圖中，求節(jié)點(diǎn)和的階鄰居集合的交集：N(,)=N() ∩N()。

2) 在中查找N(,)的節(jié)點(diǎn)關(guān)聯(lián)的邊及邊類型（關(guān)系類別），獲得其階有向包圍子圖D(,) = (V,E,R)。如圖4所示，紅色虛線表示目標(biāo)節(jié)點(diǎn)、的有向包圍子圖D(,)，它與包圍子圖的區(qū)別是邊增加了邊方向、邊類型。

圖4 有向包圍子圖DEK(u,v)

Figure 4 Directed enclosing subgraphD(,)

2.4.2 子圖節(jié)點(diǎn)標(biāo)記計(jì)算

SEAL、GraIL等模型采用了雙半徑節(jié)點(diǎn)標(biāo)記（DRNL，double radius node labeling）方法對包圍子圖節(jié)點(diǎn)進(jìn)行標(biāo)記計(jì)算，作為拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)的初始特征信息。Zhang等[35]證明了在邊預(yù)測應(yīng)用中，節(jié)點(diǎn)標(biāo)記方法優(yōu)于單純的one-hot編碼方法，前者更能準(zhǔn)確地表示節(jié)點(diǎn)的圖結(jié)構(gòu)特征。DRNL不支持區(qū)分邊的方向。假設(shè)有向圖的兩個節(jié)點(diǎn)在其底圖（無向圖）中是同構(gòu)節(jié)點(diǎn)，由于關(guān)聯(lián)的邊的方向、關(guān)系類別的不同，原有向圖的兩個節(jié)點(diǎn)可能是非同構(gòu)的。例如，圖5(a)中根據(jù)DRNL方法，3個節(jié)點(diǎn)、是同構(gòu)節(jié)點(diǎn)，標(biāo)記均為（1,1），但實(shí)際上因?yàn)檫叺姆较颉㈩悇e不同，三者是不同構(gòu)的，標(biāo)記也不應(yīng)該相同。

本文在DRNL方法的基礎(chǔ)上，結(jié)合邊的方向，提出了有向雙半徑節(jié)點(diǎn)標(biāo)記（DDRNL，directed double radius node labeling）方法。如圖5(b)所示，節(jié)點(diǎn)和有向包圍子圖中的每個節(jié)點(diǎn)用元組((,),(,))標(biāo)記，記為()。其中(,)表示有向圖的節(jié)點(diǎn)不經(jīng)過到達(dá)的最短路徑長度，(,)表示節(jié)點(diǎn)不經(jīng)過到達(dá)的最短路徑長度。該元組表示了每個節(jié)點(diǎn)相對于目標(biāo)節(jié)點(diǎn)在有向包圍子圖中的結(jié)構(gòu)位置。當(dāng)?shù)讲豢蛇_(dá)時，(,)= ∞。同樣，當(dāng)?shù)讲豢蛇_(dá)時，(,)= ∞。目標(biāo)節(jié)點(diǎn)和分別表示為（0,1）和（1,0）。

圖5 DRNL、DDRNL對比示例

Figure 5 Comparison of DRNL, DDRNL examples

DDRNL方法的實(shí)現(xiàn)如算法1所示。

算法1 DDRNL

輸入D(,)

輸出(),∈D(,)，()=((,),(,))

1)()=((,),(,))=(0,1),()=((,),(,))=(1,0),()=(,),(∈D(,)，,)//節(jié)點(diǎn)標(biāo)記初始化

2)(out,)=(in,)={}; //節(jié)點(diǎn)的可達(dá)隊(duì)列和逆向可達(dá)隊(duì)列

3)(out,)=(in,)={}; //節(jié)點(diǎn)的可達(dá)隊(duì)列和逆向可達(dá)隊(duì)列

4) {(,),∈(out,)}Label((out,),D(,))

5) {(,),∈(in,)}Label((in,),D(,))

6){(,),∈(out,)}Label((out,),D(,))

7) {(,),∈(in,)}Label((in,),D(,))

1) 節(jié)點(diǎn)標(biāo)記初始化：目標(biāo)節(jié)點(diǎn)和的標(biāo)記分別表示為（0,1）、（1,0），D(,)中的其他節(jié)點(diǎn)標(biāo)記為（∞,∞）。

2) 節(jié)點(diǎn)隊(duì)列初始化：分別建立節(jié)點(diǎn)和的可達(dá)節(jié)點(diǎn)隊(duì)列和逆向可達(dá)節(jié)點(diǎn)隊(duì)列。out()表示節(jié)點(diǎn)的可達(dá)節(jié)點(diǎn)集合組成的隊(duì)列，in()表示節(jié)點(diǎn)的逆向可達(dá)節(jié)點(diǎn)集合組成的隊(duì)列。初始時，out()=in()=｛｝，其中=或。當(dāng)=時，表示目標(biāo)頭節(jié)點(diǎn)的相關(guān)隊(duì)列，當(dāng)=時，表示目標(biāo)尾節(jié)點(diǎn)的相關(guān)隊(duì)列。

3) 計(jì)算節(jié)點(diǎn)可達(dá)節(jié)點(diǎn)的標(biāo)記的第一元素：計(jì)算與其可達(dá)節(jié)點(diǎn)的距離(,)。

4) 計(jì)算節(jié)點(diǎn)逆向可達(dá)節(jié)點(diǎn)的標(biāo)記的第一元素：計(jì)算與其逆向可達(dá)節(jié)點(diǎn)的距離(,)。

5) 計(jì)算節(jié)點(diǎn)可達(dá)節(jié)點(diǎn)的標(biāo)記的第二元素：計(jì)算的可達(dá)節(jié)點(diǎn)到的距離(,)。

6) 計(jì)算節(jié)點(diǎn)逆向可達(dá)節(jié)點(diǎn)標(biāo)記的第二元素：計(jì)算的逆向可達(dá)節(jié)點(diǎn)到的距離(,)。

第3)～6)步，調(diào)用了節(jié)點(diǎn)標(biāo)記元素計(jì)算方法，如算法2所示。

算法2 節(jié)點(diǎn)標(biāo)記元素計(jì)算

輸入(dir,), D(,),dir={in,out},={,}

輸出(),∈(,)()=((,),(,))

1) while(Empty((dir,))True)

2)= front((dir,))

3) for(in(dir,))

4) if(==,dir==out,and(,)==)

5)(,)=(,),pred()=, push ((dir,),)

6) if (==,dir==in, and(,)==)

7)(,)=(,)1,succ()=, push ((dir,),)

8) if(==,dir==out, and(,)==)

9)(,)=(,)1,pred()=, push ((dir,),)

10) if (==,dir==in, and(,)==)

11)(,)=(,)1,succ()=,push ((dir,),)

12) return

算法2的輸入為目標(biāo)節(jié)點(diǎn)的可達(dá)或逆向可達(dá)節(jié)點(diǎn)隊(duì)列、有向封閉子圖D(,)，輸出為節(jié)點(diǎn)標(biāo)記元素值((,),(,))，∈(,)。

1) 當(dāng)(dir,)不為空時，執(zhí)行第一層循環(huán)。

2) 從(dir,)取出隊(duì)列首部的節(jié)點(diǎn)，根據(jù)dir取值獲得可達(dá)（dir=out）或逆向可達(dá)（dir=in）的直接鄰居節(jié)點(diǎn)集合(dir,)。

3) 通過第二層循環(huán)，從(dir,)中依次取出的直接鄰居節(jié)點(diǎn)，分情況計(jì)算節(jié)點(diǎn)的標(biāo)記元素值。

①如果是目標(biāo)頭節(jié)點(diǎn)的可達(dá)節(jié)點(diǎn)隊(duì)列（=,dir=out），且到的距離為，則令(,)=(,)1，節(jié)點(diǎn)的前綴節(jié)點(diǎn)為節(jié)點(diǎn)，即pred()=，并把節(jié)點(diǎn)加入(dir,)的隊(duì)尾。

②如果是目標(biāo)頭節(jié)點(diǎn)的逆向可達(dá)節(jié)點(diǎn)隊(duì)列（=, dir=in），且到的距離為，則令(,)=(,)?1，節(jié)點(diǎn)的后繼節(jié)點(diǎn)為節(jié)點(diǎn)，即succ()=，并把節(jié)點(diǎn)加入(dir,)的隊(duì)尾。

③如果是目標(biāo)頭節(jié)點(diǎn)的可達(dá)節(jié)點(diǎn)隊(duì)列（=,dir=out），且到的距離為，則令(,)=(,)?1，節(jié)點(diǎn)的前綴節(jié)點(diǎn)為節(jié)點(diǎn)，即pred()=，并把節(jié)點(diǎn)加入到(dir,)的隊(duì)尾。

④如果是目標(biāo)頭節(jié)點(diǎn)的逆向可達(dá)節(jié)點(diǎn)隊(duì)列（=, dir=in），且到的距離為，則令(,)=(,)+1，節(jié)點(diǎn)的后繼節(jié)點(diǎn)為節(jié)點(diǎn)，即succ()=，并把節(jié)點(diǎn)加入(dir,)的隊(duì)尾。

節(jié)點(diǎn)，(,)=0，dir=out，從(out,)取出隊(duì)列首部的節(jié)點(diǎn)（此時=），直接鄰居節(jié)點(diǎn)集合(out,)={,,}，令=，(,)=(,)+1=1，pred()=，加入(out,)；令=，(,)=(,)+1=1，pred()=，加入(out,)；令=，(,)=(,)+1=1，pred()=，加入(out,)；此時(out,)={,,}。取出(out,)的隊(duì)首節(jié)點(diǎn)(out,)=Null，取出隊(duì)首節(jié)點(diǎn)，(out,)={}，令=，(,)=(,)+1=2，pred()=，加入(out,)。同理計(jì)算可得：(,)=1，(,)=(,)=(,)=?1，(,)=(,)=1，(,)=(,)=(,)=1，(,)=(,)=2，(,)=(,)=(,)=(,)=。

2.4.3 拓?fù)浣Y(jié)構(gòu)特征學(xué)習(xí)

本文在R-GCN、SEAL、GraIL模型的基礎(chǔ)上，設(shè)計(jì)了基于邊方向與邊類別的圖神經(jīng)網(wǎng)絡(luò)的消息傳遞網(wǎng)絡(luò)。先按照邊的類別（關(guān)系）對鄰居節(jié)點(diǎn)分別進(jìn)行聚合；再將節(jié)點(diǎn)當(dāng)前的拓?fù)浣Y(jié)構(gòu)信息與聚合結(jié)果相結(jié)合來迭代更新節(jié)點(diǎn)信息；最后綜合有向封閉子圖內(nèi)各個節(jié)點(diǎn)的輸出結(jié)果，分別得到目標(biāo)節(jié)點(diǎn)和有向包圍子圖的拓?fù)浣Y(jié)構(gòu)特征信息。拓?fù)浣Y(jié)構(gòu)特征學(xué)習(xí)的圖神經(jīng)網(wǎng)絡(luò)示意如圖6所示。

圖6 拓?fù)浣Y(jié)構(gòu)特征學(xué)習(xí)的圖神經(jīng)網(wǎng)絡(luò)示意

Figure 6 Graph neural network for topology feature learning

假設(shè)兩個節(jié)點(diǎn)之間存在0～個邊類型（關(guān)系類別）。按照不同的邊類型分別進(jìn)行聚合，每個節(jié)點(diǎn)的層的圖結(jié)構(gòu)特征輸出為：

2.5 基于有向鄰居子圖的節(jié)點(diǎn)嵌入學(xué)習(xí)方法

基于有向鄰居子圖的節(jié)點(diǎn)嵌入學(xué)習(xí)方法通過圖神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)信息的逐層傳遞，將節(jié)點(diǎn)各類型鄰居節(jié)點(diǎn)嵌入特征的聚合結(jié)果與其當(dāng)前層的嵌入特征相結(jié)合，迭代更新下一層的節(jié)點(diǎn)嵌入特征，并將注意力系數(shù)、邊的多種關(guān)系與聚合運(yùn)算相結(jié)合，自動學(xué)習(xí)各類關(guān)系對應(yīng)鄰居節(jié)點(diǎn)對于目標(biāo)節(jié)點(diǎn)的重要性的權(quán)重。該方法包括有向鄰居子圖提取和節(jié)點(diǎn)嵌入特征學(xué)習(xí)兩個環(huán)節(jié)。

2.5.1 有向鄰居子圖提取

為解決節(jié)點(diǎn)嵌入特征學(xué)習(xí)的過平滑問題，本文提取目標(biāo)節(jié)點(diǎn)的階鄰居節(jié)點(diǎn)，合并組成有向鄰居子圖，以限定節(jié)點(diǎn)特征學(xué)習(xí)的鄰居節(jié)點(diǎn)范圍。

定義8 有向鄰居子圖：對于一個有向多重圖=(,,)，給定目標(biāo)節(jié)點(diǎn)=｛,｝?，的階有向鄰居子圖是由中與節(jié)點(diǎn)或的底圖距離不超過的節(jié)點(diǎn)集合組成的子圖，記為D(,) =(V,E,R)。其中，V={|d(,)≤∪d(,) ≤}，表示有向鄰居子圖的節(jié)點(diǎn)集，E={(,)|,∈V}，表示其有向邊集合，R?，表示其關(guān)系集合。

有向鄰居子圖提取方法過程如下。

1) 在有向圖的底圖中，獲取節(jié)點(diǎn)和的階鄰居集合N()N()，計(jì)算它們的并集N'(,)=N()∪N()。

2) 在有向圖中查找N'(,)的節(jié)點(diǎn)關(guān)聯(lián)的邊及其關(guān)系類別，獲得其有向鄰居子圖D(,)=(V,E,R)，V=N'(,)。有向鄰居子圖提取如圖7(a)所示，虛線表示目標(biāo)節(jié)點(diǎn)、的有向鄰居子圖。

2.5.2 節(jié)點(diǎn)嵌入特征學(xué)習(xí)

節(jié)點(diǎn)嵌入特征學(xué)習(xí)環(huán)節(jié)在R-GCN模型的基礎(chǔ)上，針對不同種類的關(guān)系進(jìn)行了特化處理，即按照不同的關(guān)系采用，并通過注意力系數(shù)[37]對同類型關(guān)系下不同鄰居的重要程度進(jìn)行自動學(xué)習(xí)。每個節(jié)點(diǎn)的輸出特征為

圖7 有向鄰居子圖提取與節(jié)點(diǎn)嵌入特征學(xué)習(xí)示例

Figure 7 Example of directed neighbor subgraph extraction and node embedding feature learning

注意力系數(shù)為

歸一化注意力系數(shù)為

目標(biāo)節(jié)點(diǎn)和及其有向鄰居子圖的嵌入特征信息輸出為

2.6 雙源融合的評分網(wǎng)絡(luò)與訓(xùn)練

在學(xué)習(xí)過程中，本文采用噪聲對比鉸鏈損失函數(shù)訓(xùn)練模型，使正三元組的得分高于負(fù)三元組。對于訓(xùn)練圖中出現(xiàn)的每個三元組，通過用均勻采樣的隨機(jī)實(shí)體替換三元組的頭部節(jié)點(diǎn)或尾部節(jié)點(diǎn)來采樣得到負(fù)三元組。然后使用損失函數(shù)通過隨機(jī)梯度下降來訓(xùn)練模型。損失函數(shù)為

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)集

為驗(yàn)證LPMDLG模型進(jìn)行邊預(yù)測的效果，綜合R-GCN、SEAL、GraIL、TACT模型實(shí)驗(yàn)結(jié)果，本文選用標(biāo)準(zhǔn)的WN18RR[38]、FB15k-237[39]和NELL-995[40]3個數(shù)據(jù)集各自的兩個版本（v2、v3）作為基準(zhǔn)測試，采用文獻(xiàn)中的比例將數(shù)據(jù)集劃分為訓(xùn)練集、測試集。描述數(shù)據(jù)集的參數(shù)為實(shí)體數(shù)量#E、關(guān)系數(shù)量#R、三元組數(shù)量#TR[17]。

為驗(yàn)證邊預(yù)測結(jié)果對自動化動態(tài)授權(quán)、簡化匹配ReBAC規(guī)則的效果，本文選用ReBAC模型基準(zhǔn)測試數(shù)據(jù)集[9]（EMR_15、healthcare_5、Project-mgmt_5、University_5、e-document_175和eWorkforce_30共6個數(shù)據(jù)集）作為ReBAC規(guī)則匹配的基準(zhǔn)測試數(shù)據(jù)。

3.2 基線模型與實(shí)驗(yàn)參數(shù)

根據(jù)現(xiàn)有工作的研究與對比，本文選擇4個模型作為邊預(yù)測的基線模型，包括基于節(jié)點(diǎn)的模型R-GCN，基于子圖的模型SEAL、GraIL、TACT。評估指標(biāo)為AUC-PR、MRR（mean reciprocal ranking）、Hits@。

邊預(yù)測基線模型保持超參數(shù)與原始文獻(xiàn)相同，本文采用Adam optimizer優(yōu)化器，拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)中隨機(jī)采樣兩階鄰居建立有向包圍子圖，節(jié)點(diǎn)嵌入學(xué)習(xí)選擇兩層鄰居建立有向鄰居子圖。對于WN18RR、FB15k-237、NELL-995，損失函數(shù)中的margins分別設(shè)置為8、16、10。訓(xùn)練周期epochs的最大數(shù)量被設(shè)置為10。

ReBAC規(guī)則匹配基線模型采用DTRM（decision tree ReBAC miner）模型[9]，分別在邊預(yù)測前、預(yù)測后兩個階段對數(shù)據(jù)集進(jìn)行ReBAC規(guī)則提取與匹配。通過比較兩個階段的匹配結(jié)果驗(yàn)證本文LPMDLG對實(shí)體的自動化動態(tài)授權(quán)、簡化匹配ReBAC規(guī)則的效果。

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 AUC-PR

為提高對比的公平性，本文參照GraIL、TACT模型的實(shí)驗(yàn)采樣方法，使用AUC-PR作為分類度量。AUC-PR表示精確召回曲線（P-R，precision recall curve）的下方面積，可看作為每個Recall閾值計(jì)算的Precision的平均值。首先，為獲得相應(yīng)的負(fù)樣本，本文用隨機(jī)采樣實(shí)體替換測試數(shù)據(jù)子集中三元組的頭節(jié)點(diǎn)或者尾節(jié)點(diǎn)；然后，對具有相同數(shù)量的負(fù)三元組的正三元組進(jìn)行評分；最后計(jì)算AUC-PR。本文用不同的隨機(jī)種子將每個實(shí)驗(yàn)運(yùn)行3次，并計(jì)算平均結(jié)果。

表1顯示了各個模型進(jìn)行邊預(yù)測的AUC-PR結(jié)果。*表示數(shù)據(jù)通過圖神經(jīng)網(wǎng)絡(luò)框架（DGL）中的模型源碼執(zhí)行所得，**表示數(shù)據(jù)來自TACT。本文提出的模型——LPMDLG在大多數(shù)數(shù)據(jù)集上優(yōu)于其他模型，特別是對于關(guān)系數(shù)量#R較多的數(shù)據(jù)集，如FB15k-237數(shù)據(jù)集、NELL-995數(shù)據(jù)集的v2、v3版本等，AUC-PR值平均提高約0.65%。

表1 AUC-PR結(jié)果

LPMDLG的AUC-PR值優(yōu)于其他模型，主要是由于它采用了基于拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)嵌入相結(jié)合的雙源信息學(xué)習(xí)模式進(jìn)行邊的預(yù)測。與R-GCN相比，LPMDLG對不同關(guān)系、類型的鄰居節(jié)點(diǎn)，采用注意力機(jī)制學(xué)習(xí)其重要程度，賦予其不同的權(quán)重。與SEAL相比，LPMDLG針對拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)、節(jié)點(diǎn)嵌入學(xué)習(xí)兩種模式選用了不同的鄰居集，并且在該模型的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)中采用了新標(biāo)記方法，該方法考慮邊的不同方向?qū)ζ錁?biāo)記結(jié)果的影響。與GraIL、TACT模型相比，LPMDLG增加了對節(jié)點(diǎn)特征的學(xué)習(xí)，采用了新標(biāo)記方法，考慮邊的方向?qū)ζ溆绊懀ψ⒁饬W(xué)習(xí)機(jī)制進(jìn)行了簡化。實(shí)驗(yàn)結(jié)果說明了本文提出的通過拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)嵌入相結(jié)合進(jìn)行邊預(yù)測方法的有效性。

3.3.2 MRR和Hits@

本文進(jìn)一步通過排名度量評估邊預(yù)測模型LPMDLG，選擇MRR和Hits@作為評價(jià)指標(biāo)，驗(yàn)證模型進(jìn)行多關(guān)系數(shù)據(jù)集邊預(yù)測的有效性。二者的計(jì)算過程如下。

首先，將測試集的每個三元組(,r,)中的r依次替換為數(shù)據(jù)集的每種關(guān)系；其次，通過評分函數(shù)分別計(jì)算替換后對應(yīng)的分?jǐn)?shù)值；然后，將得到一系列的分?jǐn)?shù)進(jìn)行排序，得到該三元組的邊預(yù)測排序；對各個三元組的邊預(yù)測正確結(jié)果的排名，求其倒數(shù)的平均值得到MRR值；判斷每個三元組正確結(jié)果的排名是否不超過，最后排在前的個數(shù)與總數(shù)的比值就是Hits@。

表2、表3分別顯示了各個模型的MRR和Hist@1（取=1）結(jié)果。其中，*表示數(shù)據(jù)通過圖神經(jīng)網(wǎng)絡(luò)框架中的模型源碼執(zhí)行所得，**表示數(shù)據(jù)來自TACT。

表2 MRR結(jié)果

表3 Hits@1結(jié)果

實(shí)驗(yàn)結(jié)果表明，LPMDLG的MRR和H@1指標(biāo)優(yōu)于基線參考模型，其中對于包含更多關(guān)系類型數(shù)據(jù)集FB15k-237和NELL995，MRR和H@1指標(biāo)提高更加明顯。這是由于LPMDLG從3個方面提高了邊預(yù)測的能力：一是基于拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)嵌入特征雙源信息學(xué)習(xí)，比單一模式學(xué)習(xí)的結(jié)果更能全面地反映目標(biāo)節(jié)點(diǎn)與邊的特征信息；二是模型在學(xué)習(xí)拓?fù)浣Y(jié)構(gòu)時增加了邊方向、邊類型等要素，可實(shí)現(xiàn)對不同關(guān)系類別的區(qū)分；三是模型在學(xué)習(xí)節(jié)點(diǎn)嵌入特征時綜合了邊的方向（關(guān)系指向）、邊的類別（關(guān)系類別）、鄰居權(quán)重等因素進(jìn)行學(xué)習(xí)，輸出結(jié)果更能反映出不同關(guān)系之間的區(qū)別。另外，數(shù)據(jù)集FB15k-237和NELL-995比WN18RR包含更多的關(guān)系，實(shí)驗(yàn)結(jié)果說明LPMDLG對于關(guān)系數(shù)量較多的數(shù)據(jù)集進(jìn)行邊預(yù)測更有優(yōu)勢，其更適用于多關(guān)系類型情況下的實(shí)體關(guān)系預(yù)測。

3.3.3 消融實(shí)驗(yàn)

3.3.4 ReBAC規(guī)則匹配結(jié)果

為驗(yàn)證邊預(yù)測結(jié)果對實(shí)體自動化動態(tài)授權(quán)、簡化匹配ReBAC規(guī)則的關(guān)系路徑的效果，本文通過ReBAC規(guī)則匹配[9,11]實(shí)驗(yàn)進(jìn)行分析。

當(dāng)SRA匹配規(guī)則時，主體可以依據(jù)規(guī)則對客體進(jìn)行訪問行為，則三元組取值為真，記為SRA=T。因此，滿足ReBAC規(guī)則的三元組數(shù)量可表示為SRA=T的元組數(shù)量。

本文對EMR、healthcare等6個數(shù)據(jù)集[9]進(jìn)行關(guān)系預(yù)測學(xué)習(xí)，分別統(tǒng)計(jì)關(guān)系預(yù)測前、預(yù)測后各個數(shù)據(jù)集規(guī)則匹配開銷、滿足ReBAC規(guī)則SRA數(shù)量的變化。

表4 LPMDLG模型消融實(shí)驗(yàn)結(jié)果對比

表5 關(guān)系預(yù)測前后SRA=T的數(shù)量、規(guī)則匹配開銷變化

從表5可以看出，通過邊預(yù)測，各個數(shù)據(jù)集的實(shí)體關(guān)系數(shù)量都有所增加，SRA=T的元組數(shù)量隨之增加，表明滿足規(guī)則的元組增加，在關(guān)系預(yù)測之前沒有權(quán)限、權(quán)限不確定的主體獲得了對目標(biāo)資源的訪問權(quán)限，從而驗(yàn)證了通過邊預(yù)測實(shí)現(xiàn)了對某些SRA元組的自動授權(quán)。規(guī)則匹配長度之和隨著實(shí)體關(guān)系數(shù)量的增加而減少，表明匹配ReBAC規(guī)則的路徑得到了簡化。這是由于采用LPMDLG模型后，發(fā)現(xiàn)并預(yù)測了原有數(shù)據(jù)集潛在的實(shí)體間的關(guān)系，對缺失的實(shí)體關(guān)系進(jìn)行了有效的補(bǔ)充，原先沒有訪問權(quán)限的主體與目標(biāo)客體之間建立了訪問權(quán)限關(guān)系，并且對原先較為復(fù)雜的關(guān)系路徑進(jìn)行了簡化，縮短了匹配ReBAC規(guī)則的關(guān)系路徑。

4 結(jié)束語

本文將大數(shù)據(jù)訪問控制中面臨的實(shí)體關(guān)系預(yù)測問題轉(zhuǎn)化為有向多重圖的邊預(yù)測問題，提出了基于圖神經(jīng)網(wǎng)絡(luò)雙源學(xué)習(xí)的邊預(yù)測模型—— LPMDLG。與現(xiàn)有邊預(yù)測模型（如R-GCN、SEAL、GraIL等）相比，所提模型采用了基于有向包圍子圖的拓?fù)浣Y(jié)構(gòu)學(xué)習(xí)方法，加入了邊方向、邊類型等要素，提高了節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)特征的準(zhǔn)確性；該模型采用了基于鄰居子圖的節(jié)點(diǎn)嵌入學(xué)習(xí)方法，融入注意力系數(shù)與關(guān)系類型學(xué)習(xí)多關(guān)系節(jié)點(diǎn)特征，提高了節(jié)點(diǎn)嵌入特征的表示能力；該模型采用了基于拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)嵌入相融合的雙源學(xué)習(xí)模式，優(yōu)于單一模式的邊預(yù)測效果。實(shí)驗(yàn)結(jié)果表明本文提出的模型在多關(guān)系的有向多重圖的邊預(yù)測中提高了預(yù)測結(jié)果，驗(yàn)證了該模型適用于解決大數(shù)據(jù)訪問控制系統(tǒng)中實(shí)體關(guān)系預(yù)測問題。后續(xù)將進(jìn)一步研究該模型中拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)嵌入的并行學(xué)習(xí)方法，以降低模型訓(xùn)練時間，并且研究基于關(guān)系預(yù)測結(jié)果的ReBAC規(guī)則推理問題，從而實(shí)現(xiàn)基于實(shí)體關(guān)系的大數(shù)據(jù)動態(tài)、自動化訪問控制。

[1] 李昊, 張敏, 馮登國, 等. 大數(shù)據(jù)訪問控制研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2017, 40(1): 72-91.

LI H, ZHANG M, FENG D G, et al. Research on access control of big data[J]. Chinese Journal of Computers, 2017, 40(1): 72-91.

[2] FONG P W L. Relationship-based access control: protection model and policy language[C]//Proceedings of the First ACM Conference on Data and Application Security and Privacy. 2011: 191-202.

[3] AHMED T, SANDHU R, PARK J. Classifying and comparing attribute-based and relationship-based access control[C]//Proceed- ings of the Seventh ACM on Conference on Data and Application Security and Privacy. 2017: 59-70.

[4] BOGAERTS J, DECAT M, LAGAISSE B, et al. Entity-based access control: supporting more expressive access control policies[C]//Proceedings of the 31st Annual Computer Security Applications Conference. 2015: 291-300.

[5] CHAKRABORTY S, SANDHU R. On Feasibility of attribute- aware relationship-based access control policy mining[C]//IFIP International Federation for Information Processing 2021. 2021: 393-405.

[6] CHAKRABORTY S, SANDHU R. Formal analysis of ReBAC policy mining feasibility[C]//Proceedings of the Eleventh ACM Conference on Data and Application Security and Privacy(CODASPY '21). 2021: 197-207.

[7] HU V C, FERRAIOLO D, KUHN R, et al. Guide to Attribute based access control (ABAC) definition and considerations: NIST Special Publication 800-162[S]. 2019: 1-37.

[8] BUI T, STOLLER S D, LI J J. Greedy and evolutionary algorithms for mining relationship-based access control policies[J]. Computers & Security, 2019, 80: 317-333.

[9] BUI T, STOLLER S D. A decision tree learning approach for mining relationship-based access control policies[C]//Proceedings of the 25th ACM Symposium on Access Control Models and Technologies. 2020: 167-178.

[10] BUI T, STOLLER S D, LI J. Mining relationship-based access control policies from incomplete and noisy data[M]//Foundations and Practice of Security. Switzerland. 2019: 267-284.

[11] BUI T, STOLLER S D. Learning attribute-based and relationship-based access control policies with unknown values[C]//Information Systems Security - 16th International Conference(ICISS). 2020: 23-44.

[12] IYER P, MASOUMZADEH A. Active learning of relationship-based access control policies[C]//Proceedings of the 25th ACM Symposium on Access Control Models and Technologies. 2020: 155-166.

[13] ZHANG M. Graph neural networks: link prediction[M]//Graph Neural Networks: Foundations, Frontiers, and Applications. Singapore, Springer. 2021: 195-224.

[14] SCHLICHTKRULL M, KIPF T N, BLOEM P, et al. Modeling relational data with graph convolutional networks[C]//The Semantic Web. 2018: 593-607.

[15] ZHANG M, CHEN Y. Link prediction based on graph neural networks[C]//Proceedings of 32nd Conference on Neural Information Processing Systems (NIPS 2018). 2018: 1-11.

[16] TERU K K, DENIS E, HAMILTON W L. Inductive relation prediction by subgraph reasoning[C]//Proceedings of the 37th International Conference on Machine Learning(ICML). 2020: 1-10.

[17] CHEN J, HE H, WU F, et al. Topology-aware correlations between relations for inductive link prediction in knowledge graphs[C]//Pro- ceedings of 35th AAAI Conference on Artificial Intelligence. ELECTR NETWORK. 2021: 6271-6278.

[18] KIPF T N, WELLING M. Variational graph auto-encoders[C]//Bay- esian Deep Learning Workshop (NIPS 2016). 2016: 1-3.

[19] YOU J, YING R, LESKOVEC J. Position-aware graph neural networks[C]//Proceedings of 36th International Conference on Machine Learning (ICML). 2019: 7134-7143.

[20] CHAMI I, YING R, Ré C, et al. Hyperbolic graph convolutional neural networks[J]. Advances in Neural Information Processing Systems, 2019, 32: 4869-4880.

[21] LI P, WANG Y B, WANG H W, et al. Distance encoding: design provably more powerful neural networks for graph representation learning[J]. arXiv: 2009.00142, 2020.

[22] LIBEN-NOWELL D, KLEINBERG J. The link prediction problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031.

[23] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230.

[24] SHIBATA N, KAJIKAWA Y, SAKATA I. Link prediction in citation networks[J]. Journal of the American Society for Information Science and Technology, 2012, 63(1): 78-85.

[25] STANFIELD Z, CO?KUN M, KOYUTüRK M. Drug response prediction as a link prediction problem[J]. Scientific Reports, 2017, 7: 40321.

[26] NICKEL M, MURPHY K, TRESP V, et al. A review of relational machine learning for knowledge graphs[J]. Proceedings of the IEEE, 2016, 104(1): 11-33.

[27] CRAMPTON J, SELLWOOD J. Path conditions and principal matching: A new approach to access control[C]//Proceedings of the 19th ACM Symposium on Access Control Models and Technologies (SACMAT’14). 2014: 187-198.

[28] PACI F, SQUICCIARINI A, ZANNONE N. Survey on access control for community-centered collaborative systems[J]. ACM Computing Surveys, 2019, 51(1): 1-38.

[29] ASIM Y, MALIK A K. A survey on access control techniques for social networks[M]//Information Diffusion Management and Knowledge Sharing. IGI Global, 2020: 319-342.

[30] BRIN S, PAGE L. Reprint of: the anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks, 2012, 56(18): 3825-3833.

[31] OU M D, CUI P, PEI J, et al. Asymmetric transitivity preserving graph embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD ’16). 2016: 1105-1114.

[32] PEROZZI B, AL-RFOU R, SKIENA S. Deepwalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data mining(KDD'14). 2014: 701-710.

[33] RIBEIRO L, SAVERESE P, FIGUEIREDO D R. Struc2vec: learning node representations from structural identity[C]//The ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 385-394.

[34] ZHANG M H, CHEN Y X. Inductive matrix completion based on graph neural networks[J]. arXiv: 1904.12058, 2019.

[35] ZHANG M, LI P, XIA Y, et al. Labeling trick: a theory of using graph neural networks for multi-node representation learning[C]//35th Conference on Neural Information Processing Systems (NeurIPS 2021). 2022: 9061-9073.

[36] BANG-JENSEN J, GUTIN G. Digraphs theory, algorithms and applications (second edition) [M]. London: Springer-Verlag, 2007.

[37] VELI?KOVI? P, CUCURULL G, CASANOVA A, et al. Graph attention networks[J]. arXiv: 1710.10903, 2017.

[38] TOUTANOVA K, CHEN D J. Observed versus latent features for knowledge base and text inference[C]//Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality(CVSC). 2015: 57.

[39] DETTMERS T, MINERVINI P, STENETORP P, et al. Convolutional 2D knowledge graph embeddings[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2018: 1811-1818.

[40] XIONG W, HOANG T, WANG W Y. DeepPath: a reinforcement learning method for knowledge graph reasoning[C]//Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing(EMNLP). 2017: 564-573.

Access control relationship prediction method based on GNN dual source learning

SHAN Dibin, DU Xuehui, WANG Wenjuan, LIU Aodi, WANG Na

Information Engineering University, Zhengzhou 450001, China

With the rapid development and wide application of big data technology, users’ unauthorized access to resources becomes one of the main problems that restrict the secure sharing and controlled access to big data resources. The ReBAC (Relationship-Based Access Control) model uses the relationship between entities to formulate access control rules, which enhances the logical expression of policies and realizes dynamic access control. However, It still faces the problems of missing entity relationship data and complex relationship paths of rules. To overcome these problems, a link prediction model LPMDLG based on GNN dual-source learning was proposed to transform the big data entity-relationship prediction problem into a link prediction problem with directed multiple graphs. A topology learning method based on directed enclosing subgraphs was designed in this modeled. And a directed dual-radius node labeling algorithm was proposed to learn the topological structure features of nodes and subgraphs from entity relationship graphs through three segments, including directed enclosing subgraph extraction, subgraph node labeling calculation and topological structure feature learning. A node embedding feature learning method based on directed neighbor subgraph was proposed, which incorporated elements such as attention coefficients and relationship types, and learned its node embedding features through the sessions of directed neighbor subgraph extraction and node embedding feature learning. A two-source fusion scoring network was designed to jointly calculate the edge scores by topology and node embedding to obtain the link prediction results of entity-relationship graphs. The experiment results of link prediction show that the proposed model obtains better prediction results under the evaluation metrics of AUC-PR, MRR and Hits@compared with the baseline models such as R-GCN, SEAL, GraIL and TACT. The ablation experiment results illustrate that the model’s dual-source learning scheme outperforms the link prediction effect of a single scheme. The rule matching experiment results verify that the model achieves automatic authorization of some entities and compression of the relational path of rules. The model effectively improves the effect of link prediction and it can meet the demand of big data access control relationship prediction.

big data, relationship-based access control, link predication, graph neural network

TP309

A

10.11959/j.issn.2096?109x.2022062

2022?06?01；

2022?08?15

杜學(xué)繪，office_paper@163.com

國家重點(diǎn)研發(fā)計(jì)劃（2018YFB0803603，2016YFB0501904）；國家自然科學(xué)基金（62102449）；河南省重點(diǎn)研發(fā)與推廣專項(xiàng)（222102210069）

The National Key R&D Program of China(2018YFB0803603, 2016YFB0501904), The National Natural Science Foundation of China (62102449), The Key Research and Development and Promotion Program of Henan Province(222102210069)

單棣斌, 杜學(xué)繪, 王文娟, 等. 基于GNN雙源學(xué)習(xí)的訪問控制關(guān)系預(yù)測方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報(bào), 2022, 8(5): 40-55.

Format: SHAN D B, DU X H, WANG W J, et al. Access control relationship prediction method based on GNN dual source learning[J]. Chinese Journal of Network and Information Security, 2022, 8(5): 40-55.

單棣斌（1982?），男，河北邯鄲人，信息工程大學(xué)講師，主要研究方向?yàn)榇髷?shù)據(jù)安全、信任安全、圖神經(jīng)網(wǎng)絡(luò)。

杜學(xué)繪（1968?），女，河南新鄉(xiāng)人，博士，信息工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔⑾到y(tǒng)安全、大數(shù)據(jù)和區(qū)塊鏈安全。

王文娟（1981?），女，河南鶴壁人，博士，信息工程大學(xué)教授，主要研究方向?yàn)樵朴?jì)算安全、入侵防御。

劉敖迪（1992?），男，黑龍江伊春人，博士，信息工程大學(xué)講師，主要研究方向?yàn)榇髷?shù)據(jù)安全。

王娜（1980?），女，山西臨汾人，博士，信息工程大學(xué)副教授，主要研究方向?yàn)樾畔⑾到y(tǒng)安全、大數(shù)據(jù)和區(qū)塊鏈安全。