Ang Bagong Paraan ng Pagsasanay ng AI sa Graph Data Nang Walang Superbisyon

Mga May-akda: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang BUOD Ang kayamanan sa nilalaman ng iba't ibang network ng impormasyon tulad ng mga social network at communication network ay nagbibigay ng walang katulad na potensyal para sa pag-aaral ng mataas na kalidad na mga representasyon na nagpapahayag nang walang panlabas na superbisyon. Sinusuri ng papel na ito kung paano panatilihin at kunin ang masaganang impormasyon mula sa graph-structured data patungo sa embedding space sa isang unsupervised na paraan. Para sa layuning ito, nagmumungkahi kami ng isang bagong konsepto, Graphical Mutual Information (GMI), upang masukat ang ugnayan sa pagitan ng mga input graph at high-level hidden representations. Ang GMI ay nagpapalawak sa ideya ng mga kumbensyonal na pagkalkula ng mutual information mula sa vector space patungo sa graph domain kung saan ang pagsukat ng mutual information mula sa dalawang aspeto ng node features at topological structure ay napakahalaga. Nagpapakita ang GMI ng ilang mga benepisyo: Una, ito ay hindi nagbabago sa isomorphic transformation ng mga input graph—isang hindi maiiwasang kondisyon sa maraming umiiral na graph representation learning algorithm; Bukod pa rito, maaari itong mahusay na tantyahin at i-maximize ng mga kasalukuyang paraan ng pagtatantya ng mutual information tulad ng MINE; Panghuli, kinukumpirma ng aming teoretikal na pagsusuri ang kawastuhan at pangangatwiran nito. Sa tulong ng GMI, bumubuo kami ng isang unsupervised learning model na sinanay sa pamamagitan ng pag-maximize ng GMI sa pagitan ng input at output ng isang graph neural encoder. Ang malaking eksperimento sa transductive pati na rin sa inductive node classification at link prediction ay nagpapakita na ang aming paraan ay mas mahusay kaysa sa state-of-the-art unsupervised counterparts, at kung minsan ay lumalampas pa sa pagganap ng mga supervised. 1 PANIMULA Upang makamit ang maaasahang quantitative analysis para sa iba't ibang information network, ang mataas na kalidad na representation learning para sa graph-structured data ay naging isa sa mga kasalukuyang nakakaintrigang paksa. Ang mga kamakailang pamamaraan patungo sa layuning ito, na karaniwang ikinakategorya bilang Graph Neural Networks (GNNs), ay gumawa ng mga kapansin-pansin na pagsulong sa maraming learning task, tulad ng node classification [ , , ], link prediction [ , , ], graph alignment [ , , ], molecular generation [ , , ], upang magbanggit ng ilan. Bagama't masagana sa pag-unlad, ang pagtuturo sa mga GNN sa mga umiiral na pamamaraan ay karaniwang nangangailangan ng isang tiyak na anyo ng superbisyon. Walang alinlangan, ang labeling information ay mahal makuha—manual annotation o pagbabayad para sa pahintulot, at kahit na imposible makuha dahil sa privacy policy. Hindi pa banggitin na ang pagiging maaasahan ng mga ibinigay na label ay kung minsan ay kaduda-dudang. Samakatuwid, kung paano makamit ang mataas na kalidad na graph representation nang walang superbisyon ay naging kinakailangan para sa maraming praktikal na kaso, na nagtutulak sa pag-aaral ng papel na ito. 35 42 50 26 27 49 12 19 43 4 5 46 Sa pamamagitan ng maingat na pagsusuri sa aming nakolektang graph-structured data, natuklasan namin na karaniwang nagmumula ang mga ito sa iba't ibang mapagkukunan tulad ng mga social network, citation network, at communication network kung saan mayroong napakaraming impormasyon sa nilalaman at pagkakaugnay. Halimbawa, ang data sa maraming social platform tulad ng Twitter, Flickr, at Facebook ay naglalaman ng mga tampok ng mga user, *hal.*, pangunahing personal na detalye, teksto, mga larawan, IP, at ang kanilang mga relasyon, *hal.*, pagbili ng parehong item, pagiging magkaibigan. Ang mga mayamang data na ito ay sapat upang suportahan ang mga susunod na mining task nang walang karagdagang patnubay: kung ang dalawang entity ay nagpapakita ng matinding pagkakatulad sa mga tampok, may mataas na posibilidad ng isang link sa pagitan nila (link prediction), at malamang na kabilang sila sa parehong kategorya (classification); kung ang dalawang entity ay parehong nagli-link sa parehong entity, malamang na mayroon silang magkatulad na katangian (recommendation). Sa ganitong diwa, ang pagpapanatili at pagkuha ng mas maraming impormasyon hangga't maaari mula sa mga information network patungo sa embedding space ay nagpapadali sa pag-aaral ng mataas na kalidad na mga representasyon na nagpapahayag na nagpapakita ng kanais-nais na pagganap sa mga mining task nang walang anumang anyo ng superbisyon. Ang unsupervised graph representation learning ay isang mas paborableng pagpipilian sa maraming kaso dahil sa kalayaan mula sa mga label, lalo na kapag nilalayon nating makinabang mula sa malalaking unlabeled data sa wild. Upang ganap na maipasa ang mayamang impormasyon sa mga graph, sa papel na ito, isinasagawa namin ang graph embedding batay sa Mutual Information (MI) maximization, na hango sa empirikal na tagumpay ng Deep Info-Max method [ ] na gumagana sa mga imahe. Upang matuklasan ang mga kapaki-pakinabang na representasyon, sinasanay ng Deep InfoMax ang encoder upang i-maximize ang MI sa pagitan ng mga input nito ( *i.e.*, ang mga imahe) at mga output ( *i.e.*, ang mga hidden vector). Kapag isinasaalang-alang ang Deep InfoMax sa graph domain, ang unang bato na kailangan nating lampasan ay kung paano tukuyin ang MI sa pagitan ng mga graph at hidden vector, habang ang topology ng mga graph ay mas kumplikado kaysa sa mga imahe (tingnan ang Figure Isa sa mga hamon ay ang tiyakin na ang MI function sa pagitan ng hidden representation ng bawat node at ng mga input feature nito sa paligid ay sumusunod sa symmetric property, o katumbas nito, ay hindi nagbabago sa mga permutation ng mga kapitbahay. Bilang isang kamakailang pag-aaral na isinasaalang-alang ang MI, ang Deep Graph Infomax (DGI) [ ] ay unang nag-e-embed ng isang input graph at isang kaukulang corrupted graph, pagkatapos ay ibinubuod ang input graph bilang isang vector sa pamamagitan ng isang readout function, sa wakas ay nag-maximize ng MI sa pagitan ng summary vector na ito at mga hidden representation sa pamamagitan ng pagkilala sa input graph (positive sample) mula sa corrupted graph (negative sample). Ang Figure ay nagbibigay ng madaling maunawaan na pangkalahatang-ideya ng DGI. Ang pag-maximize ng ganitong uri ng MI ay napatunayang katumbas ng pag-maximize ng isa sa pagitan ng mga input node feature at hidden vector, ngunit ang pagkakapantay-pantay na ito ay humahawak sa ilalim ng ilang paunang kondisyon, *hal.*, ang readout function ay dapat na injective, na tila labis na limitado sa mga totoong kaso. Kahit na magagarantiya natin ang pagkakaroon ng injective readout function sa pamamagitan ng ilang disenyo, *hal.*, ang ginamit sa DeepSets [ ], ang kakayahan ng injective na readout function ay apektado rin ng kung paano sinanay ang mga parameter nito. Ibig sabihin, ang isang orihinal na injective function ay may panganib pa ring maging non-injective kung ito ay sinanay nang walang anumang external na superbisyon. At kung ang readout function ay hindi injective, ang impormasyon ng input graph na nakapaloob sa isang summary vector ay bababa habang lumalaki ang laki ng graph. Higit pa rito, ang DGI ay nananatili sa isang magaspang na graph/patch-level na MI maximization. Kaya sa DGI, walang garantiya na ang encoder ay maaaring mag-distill ng sapat na impormasyon mula sa input data dahil hindi nito pinag-uugnay nang malinaw ang mga hidden representation sa kanilang orihinal na mga input. 20 1). 41 1 47 Sa papel na ito, nagmumungkahi kami ng isang mas tuwid na paraan upang isaalang-alang ang MI patungkol sa mga istruktura ng graph nang hindi gumagamit ng anumit na readout function at corruption function. Direktang nagmumula kami ng MI sa pamamagitan ng paghahambing ng input ( *i.e.*, ang sub-graph na binubuo ng input neighborhood) at ang output ( *i.e.*, ang hidden representation ng bawat node) ng encoder. At kamangha-mangha, ang aming mga teoretikal na paglalarawan ay nagpapakita na ang direktang pormulang MI ay maaaring mabuwag sa isang weighted sum ng mga lokal na MI sa pagitan ng bawat feature ng kapitbahayan at ang hidden vector. Sa ganitong paraan, nabuwag namin ang mga input feature at ginawang tractable ang MI computation. Higit pa rito, ang anyo ng MI na ito ay madaling makakatugon sa symmetric property kung aayusin natin ang mga halaga ng mga timbang. Inilalaan namin ang higit pang mga detalye sa § Dahil ang MI na nabanggit sa itaas ay pangunahing sinusukat sa antas ng mga node feature, tinawag namin itong Feature Mutual Information (FMI). 3.1. Dalawang natitirang isyu tungkol sa FMI: ang mga pinagsamang timbang ay hindi pa rin kilala at hindi nito isinasaalang-alang ang topology ( *i.e.*, ang mga edge feature). Upang higit pang matugunan ang dalawang isyung ito, tinutukoy namin ang aming Graphical Mutual Information (GMI) measurement batay sa FMI. Sa partikular, ang GMI ay naglalapat ng isang intuitive na pagtatalaga ng halaga sa pamamagitan ng pagtatakda ng mga timbang sa FMI na katumbas ng proximity sa pagitan ng bawat kapitbahay at ang target node sa representation space. Tungkol sa pagpapanatili ng topology information, higit pang inuugnay ng GMI ang mga timbang na ito sa mga input edge feature sa pamamagitan ng karagdagang mutual information term. Ang nagresultang GMI ay topologically invariant at maaari ding kalkulahin gamit ang Mutual Information Neural Estimation (MINE) [ ]. Ang mga pangunahing kontribusyon ng aming trabaho ay ang mga sumusunod: 1. 2. 2 • : Pinapalawak namin ang kumbensyonal na MI estimation sa graph domain at nagmumungkahi ng isang bagong konsepto ng Graphical Mutual Information (GMI) nang naaayon. Ang GMI ay walang potensyal na panganib na dulot ng readout function dahil isinasaalang-alang nito ang MI sa pagitan ng mga input graph at high-level embeddings sa isang tuwid na pattern. Mga Konsepto • : Sa pamamagitan ng aming teoretikal na pagsusuri, nagbibigay kami ng isang tractable at calculable na anyo ng GMI na nagbubuwag sa buong GMI sa isang weighted sum ng mga lokal na MI. Sa tulong ng MINE method, ang GMI maximization ay madaling makakamit sa isang node-level. Mga Algorithm • : Pinapatunayan namin ang pagiging epektibo ng GMI sa ilang sikat na node classification at link prediction tasks kabilang ang transductive at inductive. Ang mga eksperimento ay nagpapakita na ang aming pamamaraan ay naghahatid ng magagandang performance sa iba't ibang benchmarks at minsan ay lumalampas pa sa mga supervised counterparts. Mga Natuklasan sa Eksperimento 2 KAUGNAY NA TRABAHO Alinsunod sa pokus ng aming trabaho, maikli naming sinusuri ang mga nakaraang trabaho sa dalawang sumusunod na lugar: mutual information estimation, at neural network para sa pag-aaral ng representation sa mga graph. 1. 2. . Dahil isinusulong ng InfoMax principle [ ] ang pag-maximize ng MI sa pagitan ng mga input at output ng neural network, maraming pamamaraan tulad ng ICA algorithms [ , ] ang sumusubok na gamitin ang ideya ng MI sa unsupervised feature learning. Gayunpaman, ang mga pamamaraang ito ay hindi madaling magagamit sa deep neural network dahil sa kahirapan sa pagkalkula ng MI sa pagitan ng high dimensional continuous variables. Sa kabutihang palad, ang Mutual Information Neural Estimation (MINE) [ ] ay ginagawang posible ang pagtatantya ng MI sa deep neural network sa pamamagitan ng pagtuturo sa isang statistics network bilang isang classifier upang makilala ang mga sample na nagmumula sa joint distribution at ang produkto ng mga marginal ng dalawang random variable. Sa partikular, ginagamit ng MINE ang eksaktong KL-based na pormulasyon ng MI, habang ang isang non-KL na alternatibo, ang Jensen-Shannon divergence (JSD) [ ], ay maaaring gamitin nang walang pag-aalala tungkol sa eksaktong halaga ng MI. Mutual information estimation 3 1 21 2 30 . Sa mabilis na pag-unlad ng graph neural network (GNNs), maraming graph representation learning algorithm na nakabatay sa GNNs ang ipinakilala sa mga nakaraang taon, na nagpapakita ng mas malakas na performance kaysa sa tradisyonal na random walk-based at factorization-based embedding approaches [ , , , , ]. Karaniwan, ang mga pamamaraang ito ay maaaring hatiin sa supervised at unsupervised categories. Kabilang sa mga ito, mayroong mayaman na literatura sa supervised representation learning sa mga graph [ , , , , ]. Sa kabila ng kanilang pagkakaiba-iba sa network architecture, nakakamit nila ang empirikal na tagumpay sa tulong ng mga label na kadalasang hindi naa-access sa mga totoong sitwasyon. Sa kasong ito, ang unsupervised graph learning methods [ , , ] ay may mas malawak na application potential. Ang kilalang pamamaraan ay GraphSAGE [ ], isang inductive framework upang turuan ang mga GNN sa pamamagitan ng isang random-walk based na layunin sa unsupervised setting nito. At kamakailan lamang, ang DGI [ ] ay naglalapat ng ideya ng MI maximization sa graph domain at nakakakuha ng malakas na performance sa isang unsupervised pattern. Gayunpaman, ipinatutupad ng DGI ang isang magaspang na maximization ( *i.e.*, pag-maximize ng MI sa graph/patch-level) na nagpapahirap na mapanatili ang maselan na impormasyon sa input graph. Bukod pa rito, ang kondisyon na ipinataw sa readout function na ginamit sa DGI ay tila labis na limitado sa mga totoong kaso. Sa kabaligtaran, nakatuon kami sa pagtanggal ng limitasyon ng readout function at pagdating sa graphical mutual information maximization sa isang node-level sa pamamagitan ng direktang pag-maximize ng MI sa pagitan ng mga input at output ng encoder. Ang mga representasyong hinango ng aming pamamaraan ay mas sopistikado sa pagpapanatili ng impormasyon ng input graph, na nagsisiguro ng potensyal nito para sa mga downstream graph mining task, *hal.*, node classification, link prediction, at recommendation. Neural networks para sa graph representation learning 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAPHICAL MUTUAL INFORMATION: DEFINITION AT MAXIMIZATION Bago magpatuloy, nagbibigay muna kami ng mga paunang konsepto na ginamit sa papel na ito. Hayaan ang G = (V, E) ay kumatawan sa isang graph na may *N* na mga node na *vi* ∈ V at mga edge na *eij* = (*vi* , *vj* ) ∈ E. Ang mga node feature, na may ipinapalagay na empirical probability distribution P, ay ibinigay ng *X* ∈ R ×*D* = {*x* 1, · · · , *x* N } kung saan ang *xi* ∈ R*D* ay kumakatawan sa feature para sa node *vi* . Ang adjacency matrix na *A* ∈ R ×*N* ay kumakatawan sa mga koneksyon ng edge, kung saan ang *Aij* na nauugnay sa edge *eij* ay maaaring isang tunay na numero o multi-dimensional na vector1. N N Ang layunin ng graph representation learning ay matuto ng isang encoder na *f* : R ×*D* × R ×*N* → R ×*D* ′ , upang ang mga hidden vector na *H* = {*h*1, · · · , *hN* } = *f* (*X* , *A*) ay nagpapahiwatig ng mga high-level representation para sa lahat ng node. Ang proseso ng encoding ay maaaring isulat muli sa isang node-wise na anyo. N N N Upang ipakita ito, tinutukoy namin ang *Xi* at *Ai* para sa node *i* bilang ang mga feature ng mga kapitbahay nito at ang kaukulang adjacency matrix kung kondisyon sa mga kapitbahay. Sa partikular, ang *Xi* ay binubuo ng lahat ng k-hop na kapitbahay ng *vi* na may *k* ≤ *l* kung ang encoder na *f* ay isang *l* -layer GNN, at naglalaman ito ng node *i* mismo kung idadagdag pa natin ang mga self-loop sa adjacency matrix. Dito, tinatawag namin ang sub-graph na pinalawak ng *Xi* at *Ai* bilang isang para sa node *i*, na tinutukoy bilang G*i* . Sa kahulugan ng support graph, ang encoding para sa bawat node ay nagiging *hi* = *f* (G*i* ) = *f* (*Xi* , *Ai* ). support graph Sa Deep InfoMax [ ], ang training objective ng encoder ay ang pag-maximize ng MI sa pagitan ng mga input at output nito. Ang MI ay tinatantya sa pamamagitan ng paggamit ng isang statistics network bilang discriminator upang makilala ang mga sample na nagmumula sa joint distribution at ang mga nakuha mula sa produkto ng mga marginal. Natural, kapag inaangkop ang ideya ng Deep InfoMax sa mga graph, dapat nating i-maximize ang MI sa pagitan ng representation na *hi* at ang support graph na G*i* para sa bawat node. Tinutukoy namin ang ganitong graphical MI bilang *I* (*hi* ; G*i* ). Gayunpaman, hindi ito direkta na tukuyin ang I (*hi* ; Gi ). Ang mga hirap ay: Mga Hirap sa Pag-define ng Graphical Mutual Information. 20 • Ang graphical MI ay dapat na hindi nagbabago hinggil sa node index. Sa madaling salita, dapat mayroon tayong *I* (*hi* ; G*i* ) = *I* (*hi* ; G′*i* ), kung ang G*i* at G′*i* ay isomorphic sa isa't isa. • Kung gagamitin natin ang MINE method para sa MI calculation, ang discriminator sa MINE ay tumatanggap lamang ng mga input na may fixed size. Ito ay hindi magagawa para sa G*i* dahil ang iba't ibang G*i* ay karaniwang naglalaman ng iba't ibang bilang ng mga node at samakatuwid ay may iba't ibang laki. Upang malampasan ang isyu ng pagtukoy ng graphical mutual information, ang seksyong ito ay nagsisimula sa pagpapakilala ng konsepto ng Feature Mutual Information (FMI) na nakasalalay lamang sa mga node feature. Batay sa inspirasyon mula sa decomposition ng FMI, pagkatapos ay tinutukoy namin ang Graphical Mutual Information (GMI), na isinasaalang-alang ang parehong mga node feature at 3.1 Feature Mutual Information Tinutukoy namin ang empirical probability distribution ng node features na *Xi* bilang *p*(*Xi* ), ang probability ng *hi* bilang *p*(*hi* ), at ang joint distribution bilang *p*(*hi* , *Xi* ). Ayon sa information theory, ang MI sa pagitan ng *hi* at *Xi* ay tinukoy bilang Kahanga-hanga, mayroon kaming sumusunod na mutual information decomposition theorem para sa pagkalkula ng *I* (*hi* ; *Xi* ). Theorem 1 (Mutual Information Decomposition). (*hi* |*Xi* ) (*hi* ; *Xi* ) Kung ang conditional probability p ay multiplicative (tingnan ang kahulugan ng multiplicative sa [ ]), ang global mutual information I 36 na tinukoy sa Eq. (1) ay maaaring mabuwag bilang isang weighted sum ng mga lokal na MI, namely, ≤ ≤ 1 kung saan, xj ay ang j-th neighbor ng node i, in ay ang bilang ng lahat ng elemento sa Xi , at ang weight wij ay sumusunod sa 1 wij para sa bawat j. Upang patunayan ang nasa itaas na theorem, ipinakikilala muna namin ang dalawang lemma at isang kahulugan. Lemma 1. Para sa anumang random variables X, Y , at Z, mayroon tayong Gamit ang decomposition sa Theorem maaari naming kalkulahin ang kanang bahagi ng Eq. sa pamamagitan ng MINE dahil ang mga input ng discriminator ay nagiging mga pares ng (*hi* , *xj* ) na ang laki ay palaging pareho ( *i.e.*, *D* ′-by-*D* ). Bukod dito, maaari naming ayusin ang mga timbang upang ipakita ang isomorphic transformation ng mga input graph. Halimbawa, kung ang *Xi* ay naglalaman lamang ng one-hop na kapitbahay ng node *i*, ang pagtatakda ng lahat ng timbang na magkatulad ay magreresulta sa parehong MI para sa mga input node sa iba't ibang pagkakasunud-sunod. 1, (2) Sa kabila ng ilang mga benepisyo ng decomposition, mahirap ilarawan ang eksaktong mga halaga ng mga timbang dahil nauugnay ang mga ito sa mga halaga ng *I* (*hi* ; *xj* ) at ang kanilang mga pinagbabatayang probability distribution. Isang trivial na paraan ay ang pagtatakda ng lahat ng timbang sa , pagkatapos ay ang pag-maximize ng kanang bahagi ng Eq. ay katumbas ng pag-maximize ng lower bound ng *I* (*hi* ; *Xi* ), kung saan ang tunay na FMI ay na-maximize din sa ilang lawak. Bukod sa pamamaraang ito, nagbibigay kami ng karagdagang pinahusay na solusyon sa pamamagitan ng pagsasaalang-alang sa mga timbang bilang trainable attention, na siyang paksa sa susunod na subsection. 1 (2) Hango sa decomposition sa Theorem sinubukan naming bumuo ng mga trainable na timbang mula sa iba pang aspeto ng mga graph ( *i.e.*, 3.2 Topology-Aware Mutual Information 1, topological view) upang ang mga halaga ng *wij* ay maaaring maging mas flexible at makuha ang likas na katangian ng mga graph. Sa huli, inilalarawan namin ang kahulugan ng Graphical Mutual Information (GMI). Kahulugan 2 (Graphical Mutual Information). G = (*X* , *A* ) Ang MI sa pagitan ng hidden vector h at ang support graph nito ay tinukoy bilang kung saan ang mga kahulugan ng parehong xj at in ay kapareho ng Theorem 1, aij ay ang edge weight/feature sa adjacency matrix A, at σ (·) ay isang sigmoid function. Sa intuitive na paraan, ang weight wij sa unang termino ng Eq. (10) ay sumusukat sa coped with in experiments ay unweighted. Sa pormal na paraan, kinakalkula namin ang I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). &