淺析基于圖數(shù)據(jù)庫(kù)NebulaGraph的ID Resolution方法與代碼示例
本文是一個(gè)基于 NebulaGraph 上的圖算法、圖數(shù)據(jù)庫(kù)、圖神經(jīng)網(wǎng)絡(luò)的 ID-Mapping 方法綜述，除了基本方法思想的介紹之外，我還給大家提供了可以跑的 Playground。
1 基于圖數(shù)據(jù)庫(kù)的用戶 ID 識(shí)別方法用戶
ID 識(shí)別，是一個(gè)很常見的圖技術(shù)應(yīng)用場(chǎng)景，在不同的語(yǔ)境下它可能還被叫做 Entity Correlation（實(shí)體關(guān)聯(lián)）、Entity Linking（實(shí)體鏈接）、ID Mapping（身份映射）等等。ID 識(shí)別解決的問題是找出相同的用戶在同一個(gè)系統(tǒng)或者不同系統(tǒng)中的不同賬號(hào)。
由于 ID 識(shí)別天然地是一個(gè)關(guān)聯(lián)關(guān)系問題，也是一個(gè)典型的圖、圖數(shù)據(jù)庫(kù)應(yīng)用場(chǎng)景。
1.1 建立圖譜
1.1.1 圖建模
我們從一個(gè)最簡(jiǎn)單、直接的圖譜開始，如下邊的圖結(jié)構(gòu)示意顯示，我們定義了點(diǎn)：
Prop: [name, email, birthday, address, phone_num]
user
phone
device
ip
address
在他們之間有很自然的邊：
Prop: time
Prop: time
used_device
logged_in_from
has_phone
has_address
has_email
建立圖譜
1.1.2 數(shù)據(jù)
這份數(shù)據(jù)是開源的，地址在https://github.com/wey-gu/identity-correlation-datagen
1.1.3 寫入NebulaGraph
利用 Nebula Up，一行部署 NebulaGraph地址：https://github.com/wey-gu/nebula-up/
curl-fsSLnebula-up.siwei.io/install.sh|bash
圖建模的 Schema 對(duì)應(yīng)的 NebulaGraph DDL 是：
#創(chuàng)建一個(gè)叫做entity_resolution的圖空間 CREATESPACEentity_resolution(vid_type=FIXED_STRING(30)); USEentity_resolution; #創(chuàng)建點(diǎn)的類型TAG CREATETAG`user`(`name`stringNOTNULL,`email`stringNOTNULL,`phone_num`stringNOTNULL,`birthday`dateNOTNULL,`address`stringNOTNULL); CREATETAG`address`(`address`stringNOTNULL); CREATETAG`device`(`uuid`stringNOTNULL); CREATETAG`email`(); CREATETAG`ip`(); CREATETAG`phone`(); #創(chuàng)建邊的類型EdgeType CREATEEDGE`used_device`(`time`timestampNOTNULL); CREATEEDGE`logged_in_from`(`time`timestampNOTNULL); CREATEEDGE`has_phone`(); CREATEEDGE`has_address`(); CREATEEDGE`has_email`();
對(duì)于寫入數(shù)據(jù)的 DML，這里只給出user，email類型點(diǎn)、has_email類型邊的例子
INSERTVERTEX`user`(`email`,`name`,`birthday`,`address`,`phone_num`)VALUES "user_1":("heathermoore@johnson.com","MirandaMiller",date("1957-08-27"),"BrittanyForgeApt.718EastEricWV97881","+1-652-450-5443x00562"), "user_2":("holly@welch.org","HollyPollard",date("1990-10-19"),"1AmandaFreewayLisalandNJ94933","600-192-2985x041"), "user_3":("julia.h.24@gmail.com","JuliaHall",date("1927-08-24"),"RodriguezTrackEastConnorfortNC63144","1248361783"), "user_4":("franklin.b@gibson.biz","FranklinBarnett",date("2020-03-01"),"RichardCurveKingstadAZ05660","(224)497-9312"), "user_5":("4kelly@yahoo.com","AprilKelly",date("1967-12-01"),"SchmidtKeyLakeCharlesAL36174","410.138.1816x98702"), "user_6":("steven.web@johnson.com","StevenWebb",date("1955-04-24"),"5JoannaKeySuite704FrankshireOK03035","3666519376"), "user_7":("Jessica_Torres@morris.com","JessicaTorres",date("1958-09-03"),"1PayneCircleMitchellfortLA73053","535-357-3112x4903"), "user_8":("brettglenn@gmail.com","BrettGlenn",date("1992-09-03"),"WeberUnionsEddielandMT64619","660.391.3730"), "user_9":("veronica.j@yahoo.com","VeronicaJordan",date("1947-06-08"),"2KleinMissionNewAnnettetonHI05775","810-252-6218"), "user_10":("steven@phelps-craig.info","StevenBrooks",date("1954-06-14"),"1VanessaStravenueSuite184BaileyvilleNY46381","+1-665-328-8103x3448"), "user_11":("ReginaldTheMan@hotmail.com","ReginaldMccullough",date("1915-04-12"),"JohnGardenPortJohnLA54602","030.088.4523x94511"), "user_12":("Jennifer.f@carroll-acosta.com","JenniferFoster",date("1988-04-30"),"11WebbGrovesTiffanysideMN14566","(489)306-8558x98227"), "user_13":("Philip66@yahoo.com","PhilipGarcia",date("1955-12-01"),"70RobinsonLocksSuite113EastVeronicaND87845","490-088-7610x9437"), "user_14":("Ann@hernandez.com","AnnWilliams",date("1947-05-28"),"24McknightPortApt.028SarahboroughMD38195","868.057.4056x4814"), "user_15":("Jessica@turner.com","JessicaStewart",date("1951-11-28"),"0337MasonCornerApt.900ToddmouthFL61464","(335)408-3835x883"), "user_16":("Sandra311@hotmail.com","SandraDougherty",date("1908-06-03"),"7DavisStationApt.691PittmanfortHI29746","+1-189-827-0744x27614"), "user_17":("Sharon91@gmail.com","SharonMccoy",date("1958-09-01"),"1SouthportStreetApt.098WestportKY85907","(814)898-9079x898"), "user_18":("Sharon91+001@gmail.com","KathrynMiller",date("1958-09-01"),"1SouthportStreetApt.098WestportKY85907","(814)898-9079x898"), "user_19":("brettglenn@googlemail.com","BrettyGlenn",date("1991-09-03"),"WeberUnionsEddielandMT64619","660-391-3730"), "user_20":("julia.h.24@yahoo.com","JuliaH.",date("1927-08-24"),"RodriguezTrackEastConnorfortNC63144","1248361783"), "user_21":("holly@welch.org","Holly",date("0000-10-19"),"1AmandaFreewayLisalandNJ94933","(600)-192-2985"), "user_22":("veronica.j@yahoo.com","VeronicaJordan",date("0000-06-08"),"2KleinHI05775","(810)-252-6218"), "user_23":("4kelly@hotmail.com","KellyApril",date("2010-01-01"),"SchmidtKeyLakeCharlesAL13617","410-138-1816"); INSERTVERTEX`email`()VALUES "heathermoore@johnson.com":(), "holly@welch.org":(), "julia.h.24@gmail.com":(), "franklin.b@gibson.biz":(), "4kelly@yahoo.com":(), "steven.web@johnson.com":(), "Jessica_Torres@morris.com":(), "brettglenn@gmail.com":(), "veronica.j@yahoo.com":(), "steven@phelps-craig.info":(), "ReginaldTheMan@hotmail.com":(), "Jennifer.f@carroll-acosta.com":(), "Philip66@yahoo.com":(), "Ann@hernandez.com":(), "Jessica@turner.com":(), "Sandra311@hotmail.com":(), "Sharon91@gmail.com":(), "Sharon91+001@gmail.com":(), "brettglenn@googlemail.com":(), "julia.h.24@yahoo.com":(), "holly@welch.org":(), "veronica.j@yahoo.com":(), "4kelly@hotmail.com":(); INSERTVERTEX`ip`()VALUES "202.123.513.12":(), "202.41.23.11":(), "143.1.23.4":(), "143.1.23.12":(), "153.42.2.8":(), "9.1.4.1":(); INSERTVERTEX`device`(`uuid`)VALUES "device_0":("2a8e791d-0183-4df2-aa36-5ac82151be93"), "device_1":("f9be6a11-f74b-45f5-a9ea-bb3af5a868a2"), "device_2":("ae083379-91f5-4cd3-b2b3-273960979dab"), "device_3":("c0981d43-1e59-4cd5-a1e1-e88cd9e792a5"), "device_4":("e730dd8a-fcd3-47b4-be4a-0190610e6f02"); INSERTEDGE`has_email`()VALUES "user_1"->"heathermoore@johnson.com":(), "user_2"->"holly@welch.org":(), "user_3"->"julia.h.24@gmail.com":(), "user_4"->"franklin.b@gibson.biz":(), "user_5"->"4kelly@yahoo.com":(), "user_6"->"steven.web@johnson.com":(), "user_7"->"Jessica_Torres@morris.com":(), "user_8"->"brettglenn@gmail.com":(), "user_9"->"veronica.j@yahoo.com":(), "user_10"->"steven@phelps-craig.info":(), "user_11"->"ReginaldTheMan@hotmail.com":(), "user_12"->"Jennifer.f@carroll-acosta.com":(), "user_13"->"Philip66@yahoo.com":(), "user_14"->"Ann@hernandez.com":(), "user_15"->"Jessica@turner.com":(), "user_16"->"Sandra311@hotmail.com":(), "user_17"->"Sharon91@gmail.com":(), "user_18"->"Sharon91+001@gmail.com":(), "user_19"->"brettglenn@googlemail.com":(), "user_20"->"julia.h.24@yahoo.com":(), "user_21"->"holly@welch.org":(), "user_22"->"veronica.j@yahoo.com":(), "user_23"->"4kelly@hotmail.com":(); INSERTEDGE`used_device`(`time`)VALUES "user_2"->"device_0":(timestamp("2021-03-01T0800")), "user_21"->"device_0":(timestamp("2021-03-01T0800")), "user_18"->"device_1":(timestamp("2021-03-01T0800")), "user_17"->"device_1":(timestamp("2021-03-01T0800")), "user_22"->"device_2":(timestamp("2021-03-01T0800")), "user_9"->"device_3":(timestamp("2021-03-01T0800")), "user_9"->"device_2":(timestamp("2021-03-01T0800")), "user_23"->"device_4":(timestamp("2021-03-01T0800")); INSERTEDGE`logged_in_from`(`time`)VALUES "user_2"->"202.123.513.12":(timestamp("2021-03-01T0800")), "user_21"->"202.41.23.11":(timestamp("2021-03-01T0800")), "user_18"->"143.1.23.4":(timestamp("2021-03-01T0800")), "user_17"->"143.1.23.12":(timestamp("2021-03-01T0800")), "user_22"->"153.42.2.8":(timestamp("2021-03-01T0800")), "user_9"->"153.42.2.8":(timestamp("2021-03-01T0800")), "user_9"->"153.42.2.8":(timestamp("2021-03-01T0800")), "user_23"->"9.1.4.1":(timestamp("2021-03-01T0800"));1.2 根據(jù)確定規(guī)則獲取 ID 映射關(guān)系
最簡(jiǎn)單、直接的方法，在特定的場(chǎng)景下也可能是有用的，試想像 email、IP 地址、上網(wǎng)設(shè)備這些有嚴(yán)格結(jié)構(gòu)的數(shù)據(jù)，在它們成為圖譜中的點(diǎn)的時(shí)候，簡(jiǎn)單的相等關(guān)系就足以找出這樣對(duì)應(yīng)關(guān)系，比如：
擁有相同的 email
使用過相同的 IP 地址
使用過相同的設(shè)備
在前邊的圖譜、圖數(shù)據(jù)庫(kù)中，擁有相同的 email 可以直接表達(dá)為如下的圖模式（Graph Pattern）。
(:user)-[:has_email]->(:email)<-[:has_email]-[:user]
下圖為頂點(diǎn)：user 與邊：has_email 的一個(gè)圖的可視化結(jié)果，可以看到這其中有兩個(gè)三個(gè)點(diǎn)相連的串正是符合擁有相同 email 的模式的點(diǎn)。
注：
這個(gè)結(jié)果的數(shù)據(jù)源在https://github.com/wey-gu/identity-correlation-datagen/tree/main/sample/hand_crafted
如果通過線上訪問本文，你可以鼠標(biāo)懸停（獲取點(diǎn)上的屬性）和框選放大每一個(gè)點(diǎn)和子圖哦。
根據(jù)確定規(guī)則獲取 ID 映射關(guān)系
顯然，在構(gòu)建 ID Mapping 系統(tǒng)的過程中，我們就是通過在圖數(shù)據(jù)庫(kù)中直接查詢，可視化渲染結(jié)果來看到等效的洞察，這個(gè)查詢可以寫成：
MATCHp=(:user)-[:has_email]->(:email)<-[:has_email]-(:user) RETURN?p?limit?10
NebulaGraph 中的查詢結(jié)果
同樣，在上邊交互圖中可以放大看到這兩對(duì)擁有相同 email 關(guān)聯(lián)起來的賬號(hào)：
然而，在更多真實(shí)世界中，這樣的模式匹配往往不能解決更多稍微復(fù)雜一點(diǎn)的情形：
比如從上邊的圖中我們可以看到這兩個(gè)匹配了的映射中，holly@welch.org關(guān)聯(lián)下的兩個(gè)用戶的姓名是不同的，而veronica.j@yahoo.com關(guān)聯(lián)下的兩個(gè)用戶姓名是完全相同的。
user_2,holly@welch.org,HollyPollard,1990-10-19,1AmandaFreewayLisalandNJ94933,600-192-2985x041 user_21,holly@welch.org,Holly,0000-10-19,1AmandaFreewayLisalandNJ94933,(600)-192-2985
再比如Sharon91@gmail.com和Sharon91+001@gmail.com，這兩個(gè)人的姓名不同，但是手機(jī)和地址卻是相同的。
user_17,Sharon91@gmail.com,SharonMccoy,1958-09-01,1SouthportStreetApt.098WestportKY85907,(814)898-9079x898 user_18,Sharon91+001@gmail.com,KathrynMiller,1958-09-01,1SouthportStreetApt.098WestportKY85907,(814)898-9079x898
比較慶幸的是我們只需要增加類似于"擁有相同郵箱"、“擁有相同地址”、“擁有相同電話"等其他條件就可以把這種情況考慮進(jìn)來了，而隨之而來的問題是：
不是所有的數(shù)據(jù)都至少存在某一個(gè)確定條件的相等（二元的是與否），所以不存在一條確定的邊去連接它們，比如這兩個(gè)賬戶中：
user_5,4kelly@yahoo.com,AprilKelly,1967-12-01,SchmidtKeyLakeCharlesAL36174,410.138.1816x98702 user_23,4kelly@hotmail.com,KellyApril,2010-01-01,SchmidtKeyLakeCharlesAL13617,410-138-1816
如何表現(xiàn) 4kelly@yahoo.com 與 4kelly@hotmail.com 的相似性？
如何將多種匹配規(guī)則的信息都納入關(guān)聯(lián)系統(tǒng)？
1.3 非確定規(guī)則基于復(fù)合條件量化方法
前邊提到了幾種確定規(guī)則無法處理的情況，它們可以歸結(jié)為這兩點(diǎn)：
需要多因素（規(guī)則）進(jìn)行綜合考慮與判定
需要對(duì)非確定條件（屬性）進(jìn)行處理，挖掘隱含相等、相似的關(guān)聯(lián)關(guān)系（邊）
對(duì)于 1. ，很自然可以想到對(duì)多種關(guān)聯(lián)條件進(jìn)行量化評(píng)分（score），按照多種條件的重要程度進(jìn)行加權(quán)，給出認(rèn)定為關(guān)聯(lián)的總分的閾值。
有了多因素評(píng)分的機(jī)制，我們只需要考慮如何在確定的多因素基礎(chǔ)之上，增加對(duì)不確定因素的處理，從而解決 2. 的情況。這里，非確定的條件可能是：
a. 表現(xiàn)結(jié)構(gòu)化數(shù)據(jù)的相似性：Sharon91@gmail.com與Sharon91+001@gmail.com
b. 表現(xiàn)非結(jié)構(gòu)化數(shù)據(jù)的相似性：
直接判定子字符串
運(yùn)算 Jaccard index 等類似的相似度
Schmidt Key Lake Charles AL 36174與Schmidt Key Lake Charles AL 13617
600-192-2985x041與 (600)-192-2985對(duì)于 a. 的結(jié)構(gòu)化數(shù)據(jù)中的相似性，有兩個(gè)思路是可以考慮的：
直接進(jìn)行兩個(gè)值的相似度
拆分為更細(xì)粒的多個(gè)屬性
然后就可以設(shè)計(jì)詳細(xì)的確定性規(guī)則：email.handle 相等、甚至再在此基礎(chǔ)上應(yīng)用其他非確定規(guī)則
有時(shí)候，比如對(duì)于 email_domain 字段，我們還知道 gmail.com 和 googlemail.com 是等價(jià)的，這里的處理也是可以考慮的（像是user_19,brettglenn@googlemail.com與user_8,brettglenn@gmail.com，但從郵箱判斷背后就是同一個(gè)持有者)
將 emailfoo+num@bar.com拆分成三個(gè)子屬性 email_handle:foo, email_alias:num, email_domain:bar.com
而對(duì)于 b. 的非結(jié)構(gòu)屬性相似性距離，處理方式可以根據(jù)具體的 domain knowledge 千差萬別：
像Schmidt Key Lake Charles AL 36174與Schmidt Key Lake Charles AL 13617的地址信息，除了可以用值的相似度之外，還可以把它轉(zhuǎn)換成地理類型的屬性，比如一個(gè)經(jīng)緯度組成的點(diǎn)，從而計(jì)算兩個(gè)點(diǎn)之間的地理距離，根據(jù)給定的距離值來打分。
注，你知道嗎？NebulaGraph 圖數(shù)據(jù)庫(kù)中原生支持地理類型的屬性與索引，可以直接創(chuàng)建 Point 類型的地理屬性，并計(jì)算兩個(gè) Point 之間的距離。
對(duì)于600-192-2985x041與 (600)-192-2985這種字符串形式的電話號(hào)碼，則可以統(tǒng)一轉(zhuǎn)化為<國(guó)家碼>+<區(qū)域碼>+<本地號(hào)碼>+<分機(jī)號(hào)>這樣的結(jié)構(gòu)化數(shù)據(jù)，進(jìn)一步按照結(jié)構(gòu)化數(shù)據(jù)的方式處理。
如果賬號(hào)存在圖片對(duì)象 URL，可以對(duì)比其文件相似度。
另外，對(duì)于非結(jié)構(gòu)屬性的相似性計(jì)算我們要盡量避免兩兩窮舉運(yùn)算的方式（笛卡爾積），因?yàn)檫@是一個(gè)指數(shù)增長(zhǎng)的量級(jí)，一個(gè)可行的方法是只比較建立了確定性關(guān)系（比如相同郵件前綴：email_handle，地址在相同街區(qū)，IP 在同一個(gè)網(wǎng)段等）的實(shí)體。
小結(jié)
總結(jié)來看，為了解決真實(shí)世界數(shù)據(jù)的復(fù)雜情形，基于復(fù)合條件的量化方法有：
通過細(xì)化結(jié)構(gòu)數(shù)據(jù)（比如郵箱字段拆分為子屬性或者點(diǎn)）、或者轉(zhuǎn)變?yōu)榻Y(jié)構(gòu)化數(shù)據(jù)（處理字符串形式的電話號(hào)碼）建立相似結(jié)構(gòu)化數(shù)據(jù)之間的確定關(guān)聯(lián)；
在有限存在確定性關(guān)聯(lián)的點(diǎn)之間（避免兩兩窮舉），運(yùn)算其他量化、非確定相似性（字符距離、地理距離等、圖片文件相似度）；
為不同關(guān)系賦予加權(quán)，計(jì)算相似度總分；
1.3.1 基于復(fù)合條件量化方法實(shí)操
下邊，我們來給出這系列方法的實(shí)操案例。
細(xì)化結(jié)構(gòu)數(shù)據(jù)
通過細(xì)化結(jié)構(gòu)數(shù)據(jù)（比如郵箱字段拆分為子屬性或者點(diǎn)）、或者轉(zhuǎn)變?yōu)榻Y(jié)構(gòu)化數(shù)據(jù)（處理字符串形式的電話號(hào)碼）建立相似結(jié)構(gòu)化數(shù)據(jù)之間的確定關(guān)聯(lián)；
首先，我們把 email 的點(diǎn)拆成前綴 email_handle 與后綴 email_domain，自然地，會(huì)產(chǎn)生這樣的邊：
has_email_with_handle (user -> email_handle)
has_email_with_domain (user -> email_domain)
with_handle (email -> email_handle)
with_domain (email -> email_domain)
然而，可以想見 email_domain 是一個(gè)潛在的超級(jí)節(jié)點(diǎn)，并且，它的區(qū)分度在很多情況下是很小的，比如 gmail.com 這個(gè)公共郵箱后綴沒有很大的關(guān)聯(lián)性意義。我們可以只留下 email.handle 作為點(diǎn)，而對(duì)于 email_domain，把它留在邊中作為屬性：
email_domain
Prop:
email_domain
Prop:
has_email_with_handle (user -> email_handle)
with_handle (email -> email_handle)
對(duì)應(yīng)的新的點(diǎn)類型、邊類型的 NebulaGraph DDL 語(yǔ)句：
#新的點(diǎn)類型 CREATETAG`email_handle`(); #新的邊類型 CREATEEDGE`has_email_with_handle`(`email_domain`stringNOTNULL); CREATEEDGE`with_handle`(`email_domain`stringNOTNULL);
對(duì)應(yīng)新的點(diǎn)、邊的 DML 語(yǔ)句：
INSERTVERTEX`email_handle`()VALUES
"4kelly":(),
"Ann":(),
"brettglenn":(),
"franklin.b":(),
"heathermoore":(),
"holly":(),
"Jennifer.f":(),
"Jessica":(),
"Jessica_Torres":(),
"julia.h.24":(),
"Philip66":(),
"ReginaldTheMan":(),
"Sandra311":(),
"Sharon91":(),
"steven":(),
"steven.web":(),
"veronica.j":();
INSERTEDGE`has_email_with_handle`(`email_domain`)VALUES
"user_1"->"heathermoore":("johnson.com"),
"user_2"->"holly":("welch.org"),
"user_3"->"julia.h.24":("gmail.com"),
"user_4"->"franklin.b":("gibson.biz"),
"user_5"->"4kelly":("yahoo.com"),
"user_6"->"steven.web":("johnson.com"),
"user_7"->"Jessica_Torres":("morris.com"),
"user_8"->"brettglenn":("gmail.com"),
"user_9"->"veronica.j":("yahoo.com"),
"user_10"->"steven":("phelps-craig.info"),
"user_11"->"ReginaldTheMan":("hotmail.com"),
"user_12"->"Jennifer.f":("carroll-acosta.com"),
"user_13"->"Philip66":("yahoo.com"),
"user_14"->"Ann":("hernandez.com"),
"user_15"->"Jessica":("turner.com"),
"user_16"->"Sandra311":("hotmail.com"),
"user_17"->"Sharon91":("gmail.com"),
"user_18"->"Sharon91":("gmail.com"),
"user_19"->"brettglenn":("googlemail.com"),
"user_20"->"julia.h.24":("yahoo.com"),
"user_21"->"holly":("welch.org"),
"user_22"->"veronica.j":("yahoo.com"),
"user_23"->"4kelly":("hotmail.com");
INSERTEDGE`with_handle`(`email_domain`)VALUES
"heathermoore@johnson.com"->"heathermoore":("johnson.com"),
"holly@welch.org"->"holly":("welch.org"),
"julia.h.24@gmail.com"->"julia.h.24":("gmail.com"),
"franklin.b@gibson.biz"->"franklin.b":("gibson.biz"),
"4kelly@yahoo.com"->"4kelly":("yahoo.com"),
"steven.web@johnson.com"->"steven.web":("johnson.com"),
"Jessica_Torres@morris.com"->"Jessica_Torres":("morris.com"),
"brettglenn@gmail.com"->"brettglenn":("gmail.com"),
"veronica.j@yahoo.com"->"veronica.j":("yahoo.com"),
"steven@phelps-craig.info"->"steven":("phelps-craig.info"),
"ReginaldTheMan@hotmail.com"->"ReginaldTheMan":("hotmail.com"),
"Jennifer.f@carroll-acosta.com"->"Jennifer.f":("carroll-acosta.com"),
"Philip66@yahoo.com"->"Philip66":("yahoo.com"),
"Ann@hernandez.com"->"Ann":("hernandez.com"),
"Jessica@turner.com"->"Jessica":("turner.com"),
"Sandra311@hotmail.com"->"Sandra311":("hotmail.com"),
"Sharon91@gmail.com"->"Sharon91":("gmail.com"),
"Sharon91+001@gmail.com"->"Sharon91":("gmail.com"),
"brettglenn@googlemail.com"->"brettglenn":("googlemail.com"),
"julia.h.24@yahoo.com"->"julia.h.24":("yahoo.com"),
"holly@welch.org"->"holly":("welch.org"),
"veronica.j@yahoo.com"->"veronica.j":("yahoo.com"),
"4kelly@hotmail.com"->"4kelly":("hotmail.com");
可以看到，經(jīng)過這個(gè)處理，我們已經(jīng)得到更多關(guān)聯(lián)的用戶了，它可以用這個(gè)圖查詢表達(dá)：
MATCHp=(:user)-[:has_email_with_handle]->(:email_handle)<-[:has_email_with_handle]-(:user) RETURN?p?limit?10
基于復(fù)合條件量化方法實(shí)操
非確定性相似性
在有限存在確定性關(guān)聯(lián)的點(diǎn)之間（避免兩兩窮舉），運(yùn)算其他量化、非確定相似性（字符距離、地理距離等、圖片文件相似度）；
這里用地址的地理距離來做為例子，我們預(yù)先處理每一個(gè)地址，將它們的經(jīng)緯度導(dǎo)入圖譜。
這樣，我們更改地址這個(gè)點(diǎn)的類型 address 的 schema：
Prop: geo_point（geography(point) 經(jīng)緯度類型）
對(duì)應(yīng)過來，它的 DDL 變化是：
address
-CREATETAG`address`() +CREATETAG`address`(`geo_point`geography(point));
在已經(jīng)建立了初始的addressTAG 之上，可以用ALTER TAG的 DDL 去修改address的定義：
ALTERTAG`address`ADD(`geo_point`geography(point));
可以用SHOW CREATE TAG查看修改之后的 Schema
(root@nebula)[entity_resolution]>SHOWCREATETAG`address` +-----------+------------------------------------+ |Tag|CreateTag| +-----------+------------------------------------+ |"address"|"CREATETAG`address`(| ||`address`stringNOTNULL,| ||`geo_point`geography(point)NULL| ||)ttl_duration=0,ttl_col="""| +-----------+------------------------------------+
對(duì)應(yīng)的點(diǎn)、邊的 DML：
#插入邊
INSERTEDGE`has_address`()VALUES
"user_1"->"addr_0":(),
"user_2"->"addr_15":(),
"user_3"->"addr_18":(),
"user_4"->"addr_1":(),
"user_5"->"addr_2":(),
"user_6"->"addr_3":(),
"user_7"->"addr_4":(),
"user_8"->"addr_14":(),
"user_9"->"addr_5":(),
"user_10"->"addr_6":(),
"user_11"->"addr_7":(),
"user_12"->"addr_8":(),
"user_13"->"addr_9":(),
"user_14"->"addr_10":(),
"user_15"->"addr_11":(),
"user_16"->"addr_12":(),
"user_17"->"addr_13":(),
"user_18"->"addr_13":(),
"user_19"->"addr_14":(),
"user_20"->"addr_18":(),
"user_21"->"addr_15":(),
"user_22"->"addr_16":(),
"user_23"->"addr_17":();
#插入點(diǎn)，geo_point是地址的經(jīng)緯度
INSERTVERTEX`address`(`address`,`geo_point`)VALUES
"addr_0":("BrittanyForgeApt.718EastEricWV97881",ST_Point(1,2)),
"addr_1":("RichardCurveKingstadAZ05660",ST_Point(3,4)),
"addr_2":("SchmidtKeyLakeCharlesAL36174",ST_Point(13.13,-87.65)),
"addr_3":("5JoannaKeySuite704FrankshireOK03035",ST_Point(5,6)),
"addr_4":("1PayneCircleMitchellfortLA73053",ST_Point(7,8)),
"addr_5":("2KleinMissionNewAnnettetonHI05775",ST_Point(9,10)),
"addr_6":("1VanessaStravenueSuite184BaileyvilleNY46381",ST_Point(11,12)),
"addr_7":("JohnGardenPortJohnLA54602",ST_Point(13,14)),
"addr_8":("11WebbGrovesTiffanysideMN14566",ST_Point(15,16)),
"addr_9":("70RobinsonLocksSuite113EastVeronicaND87845",ST_Point(17,18)),
"addr_10":("24McknightPortApt.028SarahboroughMD38195",ST_Point(19,20)),
"addr_11":("0337MasonCornerApt.900ToddmouthFL61464",ST_Point(21,22)),
"addr_12":("7DavisStationApt.691PittmanfortHI29746",ST_Point(23,24)),
"addr_13":("1SouthportStreetApt.098WestportKY85907",ST_Point(120.12,30.16)),
"addr_14":("WeberUnionsEddielandMT64619",ST_Point(25,26)),
"addr_15":("1AmandaFreewayLisalandNJ94933",ST_Point(27,28)),
"addr_16":("2KleinHI05775",ST_Point(9,10)),
"addr_17":("SchmidtKeyLakeCharlesAL13617",ST_Point(13.12,-87.60)),
"addr_18":("RodriguezTrackEastConnorfortNC63144",ST_Point(29,30));
有了經(jīng)緯度信息，結(jié)合 NebulaGraph 原生對(duì)于 Geo Spatial 空間地理屬性的處理能力，我們可以輕松獲得兩個(gè)點(diǎn)之間的距離（單位：米）
如下，ST_Distance(ST_Point(13.13, -87.65),ST_Point(13.12, -87.60) 表示兩個(gè)地球上的點(diǎn) ST_Point(13.13, -87.65)和ST_Point(13.12, -87.60)之間的距離是5559.9459840993895米。
RETURNST_Distance(ST_Point(13.13,-87.65),ST_Point(13.12,-87.60))ASdistance; +--------------------+ |distance| +--------------------+ |5559.9459840993895| +--------------------+
那么，我們可以用查詢語(yǔ)句來表達(dá)”所有擁有相同郵箱前綴用戶之間的距離“：
MATCH(v_start:user)-[:has_email_with_handle]->(:email_handle)<-[:has_email_with_handle]-(v_end:user) MATCH?(v_start:user)-[:has_address]->(a_start:address) MATCH(v_end:user)-[:has_address]->(a_end:address) RETURNv_start,v_end,ST_Distance(a_start.address.geo_point,a_end.address.geo_point)ASdistance,a_start,a_end;
這里，為了展現(xiàn)出針對(duì) ”非確定性“ 條件之間的 ”相似性”，我們可以把地址中字符串完全相同的結(jié)果過濾掉，WHERE a_start.address.address != a_end.address.address，如此：
MATCH(v_start:user)-[:has_email_with_handle]->(:email_handle)<-[:has_email_with_handle]-(v_end:user) MATCH?(v_start:user)-[:has_address]->(a_start:address) MATCH(v_end:user)-[:has_address]->(a_end:address) WHEREa_start.address.address!=a_end.address.address RETURNv_start.`user`.name,v_end.`user`.name,ST_Distance(a_start.address.geo_point,a_end.address.geo_point)ASdistance,a_start.address.address,a_end.address.address
它的結(jié)果是：
+-------------------+-------------------+--------------------+--------------------------------------------+--------------------------------------------+ |v_start.user.name|v_end.user.name|distance|a_start.address.address|a_end.address.address| +-------------------+-------------------+--------------------+--------------------------------------------+--------------------------------------------+ |"AprilKelly"|"KellyApril"|5559.9459840993895|"SchmidtKeyLakeCharlesAL36174"|"SchmidtKeyLakeCharlesAL13617"| |"VeronicaJordan"|"VeronicaJordan"|0.0|"2KleinMissionNewAnnettetonHI05775"|"2KleinHI05775"| |"KellyApril"|"AprilKelly"|5559.9459840993895|"SchmidtKeyLakeCharlesAL13617"|"SchmidtKeyLakeCharlesAL36174"| |"VeronicaJordan"|"VeronicaJordan"|0.0|"2KleinHI05775"|"2KleinMissionNewAnnettetonHI05775"| +-------------------+-------------------+--------------------+--------------------------------------------+--------------------------------------------+
可以看出：
user_5與user_23之間的地址距離只相差 5559 米，因?yàn)樗麄兊牡刂肪驮谝粋€(gè)街區(qū)
而user_9與user_13之間距離相差 0 米，因?yàn)樗鼈儯ā? Klein Mission New Annetteton HI 05775” 與 “2 Klein HI 05775”）實(shí)際上是完全相同的地址。
這就是利用屬性的具體含義（domain knowledge）計(jì)算的實(shí)質(zhì)距離的一個(gè)最好的詮釋，大家可以借助于圖數(shù)據(jù)庫(kù)中查詢語(yǔ)句描述能力或者利用其他系統(tǒng)去運(yùn)算用戶間非確定性特征的量化距離/相似度。
加權(quán)評(píng)分
為不同關(guān)系賦予加權(quán)，計(jì)算相似度總分；
下邊是一個(gè)在實(shí)際應(yīng)用中，可以綜合考量的多種關(guān)聯(lián)關(guān)系，包括但不限于：
確定性關(guān)系
同名（精確匹配）
相同電話（格式化處理）
使用過相同設(shè)備（精確匹配）
同郵件前綴（精細(xì)化處理）
非確定性
地址距離（處理成經(jīng)緯度，計(jì)算地球球面距離）
頭像圖片背景相似度（訓(xùn)練模型計(jì)算圖像距離）
一個(gè)很直覺的方法就是將多種條件按照不同的權(quán)重加權(quán)，獲得兩點(diǎn)間的總“疑似相同賬號(hào)”的評(píng)分。
本例中，為求簡(jiǎn)潔，我們只給出考慮“同郵件前綴”、“同名”與“地理距離小于 10KM”的綜合加權(quán)，并且認(rèn)為兩個(gè)因素的權(quán)重都是 1。
注，為了防止兩兩全匹配，我們從相同郵件前綴條件作為初始匹配條件。
MATCH(v_start:user)-[:has_email_with_handle]->(:email_handle)<-[:has_email_with_handle]-(v_end:user) MATCH?(v_start:user)-[:has_address]->(a_start:address) MATCH(v_end:user)-[:has_address]->(a_end:address) WITHid(v_start)ASs,id(v_end)ASe,v_start.`user`.nameASs_name,v_end.`user`.nameASe_name,ST_Distance(a_start.address.geo_point,a_end.address.geo_point)ASdistance RETURNs,e,1ASshared_email_handle,s_name==e_nameASshared_name,distance
結(jié)果是
+-----------+-----------+---------------------+-------------+-----------------+ |s|e|shared_email_handle|shared_name|shared_location| +-----------+-----------+---------------------+-------------+-----------------+ |"user_5"|"user_23"|1|false|true| |"user_9"|"user_22"|1|true|true| |"user_21"|"user_2"|1|false|true| |"user_2"|"user_21"|1|false|true| |"user_22"|"user_9"|1|true|true| |"user_20"|"user_3"|1|false|true| |"user_3"|"user_20"|1|false|true| |"user_18"|"user_17"|1|false|true| |"user_17"|"user_18"|1|false|true| |"user_19"|"user_8"|1|false|true| |"user_8"|"user_19"|1|false|true| |"user_23"|"user_5"|1|false|true| +-----------+-----------+---------------------+-------------+-----------------+
然后，我們計(jì)算加權(quán)分?jǐn)?shù)：
MATCH(v_start:user)-[:has_email_with_handle]->(:email_handle)<-[:has_email_with_handle]-(v_end:user) MATCH?(v_start:user)-[:has_address]->(a_start:address) MATCH(v_end:user)-[:has_address]->(a_end:address) WITHid(v_start)ASs,id(v_end)ASe,v_start.`user`.nameASs_name,v_end.`user`.nameASe_name,ST_Distance(a_start.address.geo_point,a_end.address.geo_point)ASdistance WITHs,e,1ASshared_email_handle,CASEWHENs_name==e_nameTHEN1ELSE0ENDASshared_name,CASEWHENdistance
結(jié)果是
+-----------+-----------+-------+ |s|e|score| +-----------+-----------+-------+ |"user_9"|"user_22"|3| |"user_22"|"user_9"|3| |"user_5"|"user_23"|2| |"user_21"|"user_2"|2| |"user_2"|"user_21"|2| |"user_20"|"user_3"|2| |"user_3"|"user_20"|2| |"user_18"|"user_17"|2| |"user_17"|"user_18"|2| |"user_19"|"user_8"|2| |"user_8"|"user_19"|2| |"user_23"|"user_5"|2| +-----------+-----------+-------+
1.3.2 利用 Active Learning 的方法交互式學(xué)習(xí)評(píng)分權(quán)重
實(shí)際應(yīng)用中，不同因素的加權(quán)關(guān)系也不是那么容易輕易給出的，我們可以利用有限的人力判斷進(jìn)行 Active Learning 的交互訓(xùn)練來習(xí)得權(quán)重。
注：篇幅所限，本文中略掉具體的方法實(shí)操。
1.4 利用新的邊連接不同方法
進(jìn)一步，對(duì)于這些確定（是否二元的）或非確定（量化的）關(guān)系，利用圖庫(kù)與外部系統(tǒng)獲得了關(guān)聯(lián)關(guān)系之后，常常可以直接把它們定義為圖譜中直連的邊，寫回圖庫(kù)，提供給其他算法、系統(tǒng)作為輸入，做進(jìn)一步迭代、計(jì)算。
1.4.1 創(chuàng)建單獨(dú)的直連邊
假設(shè)之前對(duì)郵件、地址、姓名的處理之后，把結(jié)果作為用戶實(shí)體之前的直連邊插入圖譜，這些種邊叫做：
shared_similar_email
shared_similar_location
shared_name
#DDL CREATEEDGE`shared_similar_email`(); CREATEEDGE`shared_similar_location`(); CREATEEDGE`shared_name`(); #DML INSERTEDGE`shared_similar_email`()VALUES "user_5"->"user_23":(), "user_9"->"user_22":(), "user_21"->"user_2":(), "user_2"->"user_21":(), "user_22"->"user_9":(), "user_20"->"user_3":(), "user_3"->"user_20":(), "user_18"->"user_17":(), "user_17"->"user_18":(), "user_19"->"user_8":(), "user_8"->"user_19":(), "user_23"->"user_5":(); INSERTEDGE`shared_name`()VALUES "user_9"->"user_22":(), "user_22"->"user_9":(); INSERTEDGE`shared_similar_location`()VALUES "user_5"->"user_23":(), "user_9"->"user_22":(), "user_21"->"user_2":(), "user_2"->"user_21":(), "user_22"->"user_9":(), "user_20"->"user_3":(), "user_3"->"user_20":(), "user_18"->"user_17":(), "user_17"->"user_18":(), "user_19"->"user_8":(), "user_8"->"user_19":(), "user_23"->"user_5":();
1.4.2 創(chuàng)建復(fù)合評(píng)分之后的邊
比如，我們查詢綜合分?jǐn)?shù)大于 2 的點(diǎn)：
MATCH(v_start:user)-[:has_email_with_handle]->(:email_handle)<-[:has_email_with_handle]-(v_end:user) MATCH?(v_start:user)-[:has_address]->(a_start:address) MATCH(v_end:user)-[:has_address]->(a_end:address) WITHid(v_start)ASs,id(v_end)ASe,v_start.`user`.nameASs_name,v_end.`user`.nameASe_name,ST_Distance(a_start.address.geo_point,a_end.address.geo_point)ASdistance WITHs,e,1ASshared_email_handle,CASEWHENs_name==e_nameTHEN1ELSE0ENDASshared_name,CASEWHENdistance2 RETURNs,e,score ORDERBYscoreDESC
然后根據(jù)返回結(jié)果建立新的邊：
#DDL CREATEEDGE`is_similar_to`(scoreintNOTNULL); #DML INSERTEDGE`is_similar_to`(`score`)VALUES "user_22"->"user_9":(3), "user_9"->"user_22":(3);1.5 基于圖算法的方法
前邊的方法中我們直接利用了用戶的各項(xiàng)屬性、行為事件中產(chǎn)生的關(guān)系，并利用各種屬性、值相似度的方法建立了基于概率或者帶有評(píng)分的關(guān)聯(lián)關(guān)系。而在通過其他方法增加了新的邊之后的圖上，我們也可以利用圖算法的方法來映射潛在的相同用戶 ID。
1.5.1 圖相似性算法
利用節(jié)點(diǎn)相似性圖算法，比如 Jaccard Index、余弦相似度等，我們可以或者 a. 利用圖庫(kù)之上的圖計(jì)算平臺(tái)全量計(jì)算相似度，或者 b. 用圖查詢語(yǔ)句實(shí)現(xiàn)全圖/給定的點(diǎn)之間的相似度，最后給相似度一定的閾值來幫助建立新的（考慮了涉及邊的）映射關(guān)系。
注，這里的 Jaccard index 和我們前邊提到的比較兩個(gè)字符串的方法本質(zhì)是一樣的，不過我們現(xiàn)在提及的是應(yīng)用在圖上的點(diǎn)之間存在相連點(diǎn)作為算法中的“交集”的實(shí)現(xiàn)。
1.5.2 社區(qū)發(fā)現(xiàn)算法
自然地，還可以用社區(qū)發(fā)現(xiàn)的算法全圖找出給定的基于邊之下的社區(qū)劃分，調(diào)試算法，使得目標(biāo)劃分社區(qū)內(nèi)部點(diǎn)為估計(jì)的相同用戶。
1.5.3 基于圖算法的方法
1.5.3.1 基于圖查詢的 Jaccard 實(shí)現(xiàn)
Jaccard Index 是一個(gè)描述兩個(gè)集合距離的定義公式，非常簡(jiǎn)單、符合直覺，它的定義為：
這里，我們把交集理解為 A 與 B 共同連接的點(diǎn)（設(shè)備、IP、郵箱前綴、地址），而并集理解為這幾種關(guān)系下與 A 或者 B 直連的所有點(diǎn)，于是，我們用這樣的 NebulaGraph OpenCypher 查詢就可以算出至少包含一跳關(guān)系的點(diǎn)和它相關(guān)的點(diǎn)、以及 Jaccard Index 值，越大代表關(guān)聯(lián)度越大。
MATCH(v_start:user)-[:used_device|logged_in_from|has_email_with_handle|has_address]->(shared_components)<-[:used_device|logged_in_from|has_email_with_handle|has_address]-(v_end:user) WITH?v_start,?v_end,?count(shared_components)?AS?intersection_size MATCH?(v_start:user)-[:used_device|logged_in_from|has_email_with_handle|has_address]->(shared_components) WITHid(v_start)ASv_start,v_end,intersection_size,COLLECT(id(shared_components))ASset_a MATCH(v_end:user)-[:used_device|logged_in_from|has_email_with_handle|has_address]->(shared_components) WITHv_start,id(v_end)ASv_end,intersection_size,set_a,COLLECT(id(shared_components))ASset_b WITHv_start,v_end,toFloat(intersection_size)ASintersection_size,toSet(set_a+set_b)ASA_U_B RETURNv_start,v_end,intersection_size/size(A_U_B)ASjaccard_index ORDERBYjaccard_indexDESC
我們可以看到結(jié)果里：
+-----------+-----------+---------------------+ |v_start|v_end|jaccard_index| +-----------+-----------+---------------------+ |"user_8"|"user_19"|1.0| |"user_19"|"user_8"|1.0| |"user_20"|"user_3"|0.6666666666666666| |"user_3"|"user_20"|0.6666666666666666| |"user_21"|"user_2"|0.6| |"user_18"|"user_17"|0.6| |"user_17"|"user_18"|0.6| |"user_2"|"user_21"|0.6| |"user_22"|"user_9"|0.5| |"user_9"|"user_22"|0.5| |"user_23"|"user_5"|0.2| |"user_5"|"user_23"|0.2| |"user_21"|"user_20"|0.16666666666666666| |"user_20"|"user_21"|0.16666666666666666| +-----------+-----------+---------------------+
user_8 與 user_19 的系數(shù)是最大的的，讓我們看看他們之間的連接？
FINDALLPATHFROM"user_8"TO"user_19"OVER*BIDIRECTYIELDpathASp;
果然，他們之間的相似度很大：
基于圖算法的方法1.5.3.2 基于 NebulaGraph Algorithm 圖計(jì)算平臺(tái)的 Jaccard 方法
1.5.3.2.1 前面方法的局限
利用圖數(shù)據(jù)庫(kù)查詢計(jì)算 Jaccard 系數(shù)的方法有兩方面局限。
首先，為了防止兩兩運(yùn)算，我們假設(shè)了所有值得被運(yùn)算的點(diǎn)之間已經(jīng)存在某種確定鏈接（對(duì)應(yīng) MATCH 第一行），雖然這樣的假設(shè)在大部分情況下是可以粗略被接受的，但是它是一種壓縮和妥協(xié)。
其次，在數(shù)據(jù)量很大的情形里，這樣的查詢將不具有可操作性。
1.5.3.2.2 更 Scale 的方法
為了能處理更大規(guī)模，我們可以利用 Spark 等并行計(jì)算平臺(tái)進(jìn)行算法執(zhí)行；
在全圖運(yùn)算時(shí)，我們可以利用局部敏感哈希 MinHash 來對(duì)兩兩比對(duì)降維，慶幸的是，Spark 中提供了 MinHash 的實(shí)現(xiàn)供我們使用！
MinHash 的思想：這個(gè)方法是用概率去有損估計(jì) Jaccard 系數(shù)，這里的降維體現(xiàn)在它用 bit map 去數(shù)字化每一個(gè)集合，隨機(jī)定義不同的集合上的 shuffle（亂序）變換，取變換之后 hash 的最小值。
這里，兩個(gè)集合的隨機(jī)變換后最小值 相等的概率是等于 Jaccard 系數(shù)的。所以，這樣偷梁換柱，就把需要兩兩集合運(yùn)算比較的算法變成只需要對(duì)每一個(gè)集合做常數(shù)次隨機(jī)變換取最小的降維近似運(yùn)算了。在圖上，對(duì)于每一個(gè)點(diǎn)，我們認(rèn)為它的鄰居就是這個(gè)點(diǎn)的集合，那么在 Spark 中運(yùn)算 Jaccard 系數(shù)的過程就是：
獲取每一個(gè)點(diǎn)的鄰居集合
對(duì)點(diǎn)的鄰居進(jìn)行 MinHash 運(yùn)算，獲得 Jaccard 系數(shù)
慶幸的是，開源的 NebulaGraph Algorithm 已經(jīng)提供了這個(gè)算法的實(shí)現(xiàn)，而我們只需要調(diào)用 NebulaGraph Algorithm 就可以了，使用方法參考 NebulaGraph Algorithm 文檔。
注，配置中 jaccard.tol 的意涵是 approxSimilarityJoin 中的 threshold ：
defapproxSimilarityJoin( datasetA:Dataset[_], datasetB:Dataset[_], threshold:Double, distCol:String):Dataset[_]={ ... //Filterthejoineddatasetswherethedistancearesmallerthanthethreshold. joinedDatasetWithDist.filter(col(distCol)
讀者到這里應(yīng)該會(huì)注意到，這個(gè)方法顯然是假設(shè)所有的點(diǎn)都是用戶實(shí)體，邊是他們之間的直連關(guān)系的。所以再應(yīng)用這個(gè)方法之前，我們需要?jiǎng)?chuàng)建經(jīng)過預(yù)處理的直連邊，這個(gè)步驟正是前邊章節(jié)“利用新的邊連接不同方法”中的內(nèi)容。
1.5.3.3 基于 NebulaGraph Algorithm 圖計(jì)算平臺(tái)社區(qū)發(fā)現(xiàn)算法
提到基于全圖的算法，我們自然可以想到可以利用社區(qū)發(fā)現(xiàn)的手段去幫助識(shí)別相同用戶的不同賬號(hào)，弱聯(lián)通分量（WCC）、Louvain 算法都是常見的手段。
同樣，NebulaGraph Algorithm 開箱即用地提供了這兩種算法，我們可以很容易在 NebulaGraph 得出社區(qū)劃分，并在此基礎(chǔ)上做復(fù)合方法的識(shí)別。
1.5.3.4 上手基于 NebulaGraph Algorithm 圖計(jì)算方法
因?yàn)槠P(guān)系，這里不展示 NebulaGraph Algorithm 方法的上手環(huán)節(jié)，類似于在之前 Fraud Detection 方法文章中的對(duì)應(yīng)章節(jié)，你可以利用 Nebula-Up 的 all-in-one 模式，一行命令搭建這樣的環(huán)境并親自體驗(yàn)。
Nebula-Up 部署命令：
curl-fsSLnebula-up.siwei.io/all-in-one.sh|bash-s--v3spark1.6 基于圖神經(jīng)網(wǎng)絡(luò)的方法
我們注意到，在講以上不同的方法相結(jié)合的時(shí)候，會(huì)把前導(dǎo)方法的結(jié)果作為圖上的邊，進(jìn)而作為后邊的方法的輸入，而相同用戶 ID 的識(shí)別本質(zhì)上就是在圖上去預(yù)測(cè)用戶之間鏈接、邊。
在 GNN 的方法中，除了我們?cè)谄墼p檢測(cè)中利用到的節(jié)點(diǎn)分類（屬性預(yù)測(cè)）之外，鏈接預(yù)測(cè)（Link Prediction）也是另一個(gè)常見的算法目標(biāo)和應(yīng)用場(chǎng)景。自然地，可以想到用 GNN 的方法結(jié)合 1. 非 GNN 方法獲得的、 2. 已經(jīng)有的人為標(biāo)注的鏈接，來學(xué)習(xí)、預(yù)測(cè)圖上的 ID 映射。
值得注意的是，GNN 的方法只能利用數(shù)字型的 feature、屬性，我們沒辦法把非數(shù)字型的屬性像在分類情況里那樣枚舉為數(shù)值，相反，我們?cè)谡嬲?GNN 之前，可以用其他的圖方法去建立基于打分、或者相似度的邊建立。這時(shí)候，這些前邊的方法成為了 GNN 鏈路預(yù)測(cè)的特征工程。
1.6.1 基于 GNN 的實(shí)操
和在 “基于 NebulaGraph 圖數(shù)據(jù)庫(kù)的欺詐檢測(cè)方法與代碼示例” 的欺詐檢測(cè)類似，我將給出的例子也是 GNN 結(jié)合圖數(shù)據(jù)庫(kù)做實(shí)時(shí)預(yù)測(cè)的例子。
1.6.1.1 HDE[ICDM2021]
我們利用 Heterogeneous Graph Neural Network with Distance Encoding 給出的方法來做 Inductive Learning 的異構(gòu) GNN 上的鏈路預(yù)測(cè)，同時(shí)，我們將用一個(gè)更方便的 GNN 工具，OpenHGNN，有了它，本例中的代碼量也會(huì)大大下降。
注：OpenHGNN 是由北郵 GAMMA Lab 開發(fā)的基于 PyTorch 和 DGL 的開源異質(zhì)圖神經(jīng)網(wǎng)絡(luò)工具包。
1.6.1.2 數(shù)據(jù)集
本利的數(shù)據(jù)集是前邊方法中建立在 NebulaGraph 中的圖譜，借助于 Nebula-DGL，我們可以一行代碼把 NebulaGraph 中的圖加載到 DGL 之中。
注：
這里，我們使用的的工具為 Deep Graph library（DGL），NebulaGraph 圖數(shù)據(jù)庫(kù)和他們之間的橋梁，Nebula-DGL。
你可以直接 load 這個(gè) .ngql 文件到 NebulaGraph。
1.6.1.3 數(shù)據(jù)處理
為了將 NebulaGraph 圖譜進(jìn)行工程處理，序列化成為 DGL 的圖對(duì)象，我們要通過 Nebula-DGL 的 YAML 配置文件 API 描述所需的點(diǎn)、邊類型以及關(guān)心的屬性（特征）。
我們看下現(xiàn)在的圖中有哪些點(diǎn)、邊類型：
(root@nebula)[entity_resolution]>SHOWTAGS +----------------+ |Name| +----------------+ |"address"| |"device"| |"email"| |"email_handle"| |"ip"| |"phone"| |"user"| +----------------+ Got7rows(timespent1335/7357us) (root@nebula)[entity_resolution]>SHOWEDGES +---------------------------+ |Name| +---------------------------+ |"has_address"| |"has_email"| |"has_email_with_handle"| |"has_phone"| |"is_similar_to"| |"logged_in_from"| |"shared_name"| |"shared_similar_email"| |"shared_similar_location"| |"used_device"| |"with_handle"| +---------------------------+ Got11rows(timespent1439/30418us)
在本例中，我們不考慮屬性(特征)。
nebulagraph_entity_resolution_dgl_mapper.yaml--- #Ifvertexidisstring-typed,remap_vertex_idmustbetrue. remap_vertex_id:True space:entity_resolution #strorint vertex_id_type:int vertex_tags: -name:user -name:address -name:device -name:email_handle -name:ip edge_types: -name:has_email_with_handle start_vertex_tag:user end_vertex_tag:email_handle -name:is_similar_to start_vertex_tag:user end_vertex_tag:user -name:shared_similar_location start_vertex_tag:user end_vertex_tag:user -name:has_address start_vertex_tag:user end_vertex_tag:address -name:logged_in_from start_vertex_tag:user end_vertex_tag:ip -name:used_device start_vertex_tag:user end_vertex_tag:device
然后，我們?cè)诎惭b好 Nebula-DGL 之后只需要這幾行代碼就可以將 NebulaGraph 中的這張圖構(gòu)造為 DGL 的 DGLHeteroGraph 圖對(duì)象：
fromnebula_dglimportNebulaLoader nebula_config={ "graph_hosts":[ ('graphd',9669), ('graphd1',9669), ('graphd2',9669) ], "nebula_user":"root", "nebula_password":"nebula", } #loadfeature_mapperfromyamlfile withopen('nebulagraph_entity_resolution_dgl_mapper.yaml','r')asf: feature_mapper=yaml.safe_load(f) nebula_loader=NebulaLoader(nebula_config,feature_mapper) g=nebula_loader.load() g=g.to('cpu') device=torch.device('cpu')
模型訓(xùn)練
參考custom_link_prediction_dataset.py
HDE_link_predict.pyimporttorchasth fromopenhgnnimportExperiment fromopenhgnn.datasetimportAsLinkPredictionDataset,generate_random_hg fromdglimporttransformsasT fromdglimportDGLHeteroGraph fromdgl.dataimportDGLDataset fromdgl.dataloading.negative_samplerimportGlobalUniform meta_paths_dict={'APA':[('user','has_email_with_handle','email_handle'),('user','is_similar_to','user'),('user','shared_similar_location','user'),('user','has_address','address'),('user','logged_in_from','ip'),('user','used_device','device')]} target_link=[('user','is_similar_to','user')] target_link_r=[('user','is_similar_to','user')] classMyLPDataset(DGLDataset): def__init__(self,g): super().__init__(name='entity_resolution',force_reload=True) self.g=g defprocess(self): #Generatearandomheterogeneousgraphwithlabelsontargetnodetype. self._g=transform_hg(self.g) #Somemodelsrequiremetapaths,youcansetmetapathdictforthisdataset. @property defmeta_paths_dict(self): returnmeta_paths_dict def__getitem__(self,idx): returnself._g def__len__(self): return1 deftransform_hg(g:DGLHeteroGraph)->DGLHeteroGraph: transform=T.Compose([T.ToSimple(),T.AddReverse()]) hg=transform(g) returnhg deftrain_with_custom_lp_dataset(dataset): experiment=Experiment(model='HDE',dataset=dataset,task='link_prediction',gpu=-1) experiment.run() myLPDataset=AsLinkPredictionDataset( MyLPDataset(g), target_link=target_link, target_link_r=target_link_r, split_ratio=[0.8,0.1,0.1], force_reload=True) train_with_custom_lp_dataset(myLPDataset)
注，這里尚需把 g 處理成為 MyLPDataset() 可以接受的數(shù)據(jù)，篇幅所限、略。
審核編輯：劉清
-
神經(jīng)網(wǎng)絡(luò)
+關(guān)注
關(guān)注
42文章
4762瀏覽量
100541 -
URL
+關(guān)注
關(guān)注
0文章
139瀏覽量
15312 -
DDL
+關(guān)注
關(guān)注
0文章
12瀏覽量
6320 -
DML模型
+關(guān)注
關(guān)注
0文章
4瀏覽量
6011
原文標(biāo)題：基于圖數(shù)據(jù)庫(kù)NebulaGraph的ID Resolution方法與代碼示例
文章出處：【微信號(hào)：OSC開源社區(qū)，微信公眾號(hào)：OSC開源社區(qū)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
SQL存儲(chǔ)過程在.NET數(shù)據(jù)庫(kù)中的應(yīng)用
簡(jiǎn)單的Access數(shù)據(jù)庫(kù)查詢示例
labview連接MS SQL數(shù)據(jù)庫(kù)示例
淺析對(duì)象數(shù)據(jù)庫(kù)和NoSQL
基于Data Ability的關(guān)系型數(shù)據(jù)庫(kù)和數(shù)據(jù)管理能力，實(shí)現(xiàn)數(shù)據(jù)庫(kù)相關(guān)應(yīng)用服務(wù)的快速開發(fā)
HarmonyOS關(guān)系型數(shù)據(jù)庫(kù)和對(duì)象關(guān)系數(shù)據(jù)庫(kù)的使用方法
數(shù)據(jù)庫(kù)設(shè)計(jì)方法、規(guī)范、技巧
各種數(shù)據(jù)庫(kù)的連接方法詳細(xì)資料說明
MACSV數(shù)據(jù)庫(kù)導(dǎo)出、導(dǎo)入的方法
Spring嵌入式數(shù)據(jù)庫(kù)示例
用于完整的數(shù)據(jù)庫(kù)加密使用教程
圖數(shù)據(jù)庫(kù)的特性及其優(yōu)勢(shì)
工商網(wǎng)監(jiān)
評(píng)論