[PDF] Topology Optimization based Graph Convolutional Network

View - Download Topology Optimization based Graph Convolutional Network

Previous PDF

Next PDF

TopologyOptimization basedGraph Conv olutionalNetw ork

Liang Yang

1 2

3,Zesheng Kang1,Xiaochun Cao2,Di Jin4,Bo Yang5;3andYuanfangGuo 6;

1School ofArticial Intelligence,Hebei Univ ersityof Technology,China

2State KeyLaboratoryofInformation Security, Instituteof InformationEngineering, CAS,China

3KeyLaboratoryof SymbolicComputation andKno wledgeEngineering ofMinistry ofEducation, China

4Collegeof Intelligenceand Computing,T ianjinUni versity ,China

5Collegeof ComputerScience andT echnology, JilinUni versity,China

6School ofComputer Scienceand Engineering,Beihang Univ ersity, Chinayangliang@vip.qq.com, andyguo@buaa.edu.cn

Abstract

In thepast few years,semi-supervisednodeclassi-

cation inattrib utednetworkhas beendeveloped rapidly.Inspired bythe success ofdeep learn- ing, researchersadopt thecon volutional neuralnet- (GCN), andthe yhave achievedsurprisingclassi- cation accuracybyconsidering thetopological in- formation andemplo yingthefully connectednet- work(FCN). Howe ver,thegivennetworktopol- ogy mayalso inducea performancede gradationif it isdirectly employed inclassication,becauseit may possesshigh sparsityand certainnoises. Be- sides, thelack oflearnable ltersin GCNalso lim- its theperformance. Inthis paper, wepropose a novelTopology OptimizationbasedGraph Convo- lutional Networks(TO-GCN) tofullyutilizethe potential informationby jointlyrening thenet- worktopology andlearning theparameters ofthe

FCN. Accordingto ourderi vations, TO-GCNis

more exiblethanGCN, inwhich thelters are xedand onlythe classiercan beupdated during the learningprocess. Extensiv eexperimentsonreal attributednetw orksdemonstratethe superiorityof the proposedTO-GCN againstthestate-of-the-art approaches.

1 Introduction

Objects inreal world, whichisusuallymodeled bynodes in typical graphs/networks,arelik elyto beconnectedinv arious approaches. Forexample, peopleareconnectedthrough so- cial networkandonline socialnetw orks.Computers arecon- nected viaintranets andInternet. Proteinsare connectedby the existenceofelectrostatic forces.T oe xplorethe character- istics andmechanisms ofthese networks, network analysisis introduced [Newman,2003 ]. Innetw orkanalysis,nodeclas- sication, whichis alsonamed asnetw orkpartition, commu- nity detectionand graphclustering, isone ofthe mostwidely studied topic [Fortunato,2010; Fortunato andHric,2016;

Taoet al., 2017].fl

Corresponding author.

Figure 1:The difference betweenGraphConv olutionalNetw orks (GCN) andour proposedT O-GCN.Learnable variablesaresho wn with abackground color. GCNtakesthe giv ennetworktopology Aand nodefeature Xas inputand onlylearns theparameters of FCNWwith labelZ. TO-GCNjointlylearns thenetw orktopology O(red lineand disk)and theparameters ofthe FCNWto fully explorethe labelsinformation Z. Classical nodeclassication isde veloped basedontheuti- lization ofthe network topology.Althoughthe ycontribute signicantly inunderstanding thecharacteri sticsand mecha- nisms ofthe networks, theirperformancesaretypically un- satisfactorydue tothe sparsityproperties oft henetw orksand the noisesin thenetw orks.T oimprove theperformances,nu- merous sideinformationis adopted.Among them,label and content informationare themost commonlyutilized [Tuet al. , 2016;Y anget al., 2013]. Byef fectivelyexploitingthe labels andnetw orktopology,label propagation [Zhuet al., 2003
]achievesagreat performanceboost. Man yalgorithms are laterproposed toutilize thepairwise constraintinforma- tion, whichis anotherkind ofsupervised informationin the form ofmust-link andcannot-link [Lu andPeng, 2013]. By exploringthe correlations betweennodefeatureand network topology structure,node classicationtask inattrib utednet-

workshas ach ievedgreatsuccessandperformanceimprove-Proceedingsofthe Tw enty-E ighthInternationalJointConferenceon ArtificialIntelligence(IJCAI-19)

4054
ment [Wanget al., 2016]. Recently,man yeffortsha vebeenmade toresolvethetask of semi-supervisednode classificationin attributed networks, which predictsthe labelsby exploiting thenetw orktopology, node featuresand labels.Moti vated bythesuccessofdeep learning [Goodfellowet al., 2016], especiallythe conv olu- tional neuralnetw orks(CNNs) [Krizhevskyet al., 2012], re- searchers extendCNNsto processthe irregular graphdata, e.g., graphsand manifolds.Among thesee xtensions,Graph ConvolutionalNetworks (GCN),whichsimplifiesChebNet [Defferrardet al., 2016], hasattracted alar geamount ofat- tentions duet oitssimplicityand highperformance [Kipf and

Welling,2017

]. Assho wninFigure1(A), GCNis equiv- alent tosmoothing thenode featuresin theneighbourhoods and processthem witha fullyconnected netw ork(FCN). The success ofGCN isyielded bythe network topology, whichis shownin [Liet al., 2018], andthe labelinformation, whichis only employedtotrain theparameters inFCN. Unfortunately,GCN hasnot fullye xploitedthe potential of thenetw orktopologyandthe flexibility ofthe FCNis also limited. Specifically,thegi ven networktopologyisnotop- timal dueto certainsparsity andnoises. Somenodes inone class maynot beclose, whileother nodesbelonging todif fer- ent classesmay bedirectly connected.These phenomenons havenotbeen taken intoconsiderations byGCN.Onthe other hand, thefle xibilityofGCNis limitedcompared toCNN. Typically,CNNconsists oftwolearnablecomponents,convo- lutional layers(including poolinglayers) andfully connected layers. Theformer onecan bere garded asthe featureextrac- tor withlearnable filters,while thelatter oneis equiv alentto a learnableclassifier .Onthecontrary ,the filtersAin GCN are fixedandonly theclassifier islearnable (Figure1(A)). Tobetter utilizethe network topologyvia refinementand improvethefle xibilityof thenetwork,we proposea nov el (TO-GCN).As shown inFigure1(B),the giv enlabels areuti- lized tosimultaneously andjointly learnthe network topol- ogy andthe parametersof theFCN, whichpro videsmore flexibilitycompared toGCN. Specifically,with thegi ven labelsbeingthepairwisecon- straints (must-linkand cannot-link),the network topologyis refined tosatisfy thepairwise constraintsand predictthe un- knownlabels accordingto thegi ven labels.T omeasurethe consistencies betweenthe learnednetw orktopology andpair- wise constraints,constraint propagation isformulatedasa minimization ofan objectiv efunctionwiththerefinedtopol- ogy beingthe parameters.This modelis optimizedwith re- spect tothe refinedtopology andthe parametersof FCN. Analysis ofthe jointoptimization algorithmindicates thatthe learned topologyis affected byboththegi ven constraintsand classification results.

Our maincontrib utionsaresummarizedas follows:

Weanal yzetheimpactof network topologyto theper -

formance ofsemi-supervised nodeclassification inat- tributednetw orksanddemonstratethat thelabel infor- mation hasnot beenfully explored inmost oftheexist- ing methods. Wepropose ano vel TopologyOptimizationbasedGraphConvolutionalNetworks (TO-GCN),whichjointly learns thenetw orktopologyandthe parametersof the

FCN withrespect tothe giv enlabels.

Wepro videananalysisof thejoint optimizationalgo- rithm todemonstrat eitssuperioritycompared tothe straightforwardseparate optimizationapproach.

2 BackgroundsandMoti vations

2.1 Notationsand Denitions

Define anattrib utednetworkas G= (V;E;X)with

nodes/verticesV=fv1;v2;:::;vNgand edgesE= f e

1;e2;:::;eMg. Theattrib utesofallthe vertices arerepre-

sented asan attribute matrixX2RNF, wherethe nthrow of which,xn2R1F, correspondsto theattrib utesof ver- texvnin theform ofa F-dimensional vector.Thenetwork topology isrepresented byan adjacency matrixA= [aij]2 R NN. Theelements inthe adjacency matrixpossess binary value,i.e., aij= 1, ifan edgee xistsbetween thevertices v iandvj, andvice versa. D= diag(d1;d2;:::;dN), where d n=P janjis thede greeofverte xvn, isthe degree matrix. In general,semi-supervised nodeclassification predictsthe labelsY2 f0;1gNCof thev erticesinV, giventhenetwork G= (V;E;X)and somelabelled nodesin setVlin theform ofZ= [Znc]2 f0;1gNC, whereCis thenumber ofclasses andZnc= 1if andonly ifthe verte xvnbelongs tocthclass.

2.2 LabelPr opagation

The semi-supervisednode classificationoriginates from graph-based semi-supervisedlearning, whichmak esfull use of thelimited numberof labelsby exploring thegraph struc- ture. Thephilosoph ybehindthemis theassumption that nearby verticesona graphtend toshare thesame lab el. Thus, theycan beformulated asminimizing theobjecti ve function L

Y) =12

X i;jwij(yiyj)2;(1) wherewijis thesimilarity betweenthe vertices viandvj. Unfortunately,most of thegraph-basedsemi-supervised learning algorithmsignore eithernetw orktopology ornode feature. Whenthe nodefeatures arene glected,some methods likeLP A [Raghavanet al., 2007]only exploitthelabel propa- gationon thenetw ork(topology information),i.e.,wij=aij, which isan elementin theadjacenc ymatrix. Othermethods propagatethe labelsin similaritygraph, whichis constructed from thenode featureswithout takingthe topologicalinfor - mation intoconsideration [Zhuet al., 2003]. Inthe similarity graph,wij= expjjxixjjj22=2is thesimil aritycalcu- lated betweenthe vertices viandvjwith referenceto their features. Theprocess ofthe labelpropag ationin graphcan be seenas refiningthe graphstructure withthe giv enlabels.

2.3 GraphCon volutionalNeuralNetworks

Recently,semi-supervised nodeclassificationalgorithmstend to improvetheperformanceby jointlyconsidering thenet- worktopology andnode attributes (graphdata) duetotheir necessity.Inspired bythe successfulapplications ofdeep learning tothe regular griddata(e.g.images andvideos),

researchers considerto adoptthe deeplearning techniquesProceedingsofthe Tw enty-E ighthInternationalJointConferenceon ArtificialIntelligence(IJCAI-19)

4055
to processthe irregular graphdata(e.g.graphs ormani- folds) [Defferrardet al., 2016;Duv enaudet al., 2015;Niepert et al. , 2016;Hamilton et al., 2017;Scarselli et al., 2009; Xuet al., 2019]. Toalleviate thisdifficulty, spectralap- proaches applythe conv olutionoperationdirectlytothespec- trumofthegraph(i.e.,thesingularvalues ofgraphLaplacian) by treatingthe nodeattrib utesas signalsingraphaccording to thespectral graphtheory . g x=Ug()UTx;(2) whereUandrepresent thesingular vectors andsingular valuesof thegraph LaplacianL=D1=2(DA)D1=2, i.e.,L=UUT, respectively. Unfortunately,the highcomputational complexity ofsin- gular valuedecomposition(SVD) prev entsthe spectralap- proaches frombeing appliedto large graphs.T oovercome this deficit,may simplifications havebeen proposed.Cheb- Net [Defferrardet al., 2016]approximates thespectral fil- ter withPthorder Chebyshevpolynomialsas gx=PP p =00pTp(L)x, whereTpandparetheChebyshevpolyno- mials andcoef ficients,respectively .GCN(KipfandWelling

2017) furthersimplifies ChebNetas

g x=(I+D1=2AD1=2)x;(3) by constrainingthe Chebyshev polynomialswith1storder and thelar gestsingularvalues with2, whereIdenotes the identity matrix.By denoting~A=A+Iand~Dnn=P j~Anj and generalizingone inputchannel xand onespectral filters toFinput channelsXandCspectral filters2RFfiC,

GCN becomes

H=(~D12

~A~D12

X);(4)

where(:)is thenonlinear activ ationfunction,suchassoft- max orReLU, assho wnin Figure1(A).Accordingto the experiments,stacking two GCNs,whichissho wnin Eq.(5), will providethebest performance.

Z=f(X;A) =softmax ^AReLU(^AX(0))(1)

;(5) where ^A=~D12 ~A~D12 . Theparameters (0)and(1)can be calculatedby minimizingthe cross-entropy errorsof the labeled nodes L=X n 2 V lX C c =1Ynclog(Znc);(6) whereVldenotes theset oflabelled nodes.Recent litera- ture [Liet al., 2018]indicates thatthe graphcon volution op- eration ~D12 ~A~D12

Xin GCNis equiv alenttoaLaplacian

smoothing operationapplied tothe localneighbourhood, i.e., the graphcon volutionoperationisessentiallya veraging the node attributesina localneighbourhood withweight 1pd idj, wherediis thede greeofnodevi.

Graph attentionnetw ork(GAT)

[Velickovi´cet al., 2018] extendsGCN byimposing theattention mechanism [Bah- danauet al., 2015]to theneighbouring weightassignment and formulatesthe weightbetween vertices vnandvkas O ij=expc(xTi;xTj)P k2N(j)expc(xTk;xTj);(7)Dataset FCNGCN GCN-GT

Citeseer 57.1%72.0% 100%

Cora 56.2%81.3% 100%

PubMed 70.7%79.2% 100%Table1: Classificationresults withdif ferenttopologies. wherec(x;y)is theself-attention witha sharedattentional mechanismc:RCRC!R. Ascan beobserv ed,GA T is equivalenttoestimatingthe edgeweights accordingto the attributesimilarities betweenthe connectednodes.

Mixture modelnetw orks(MoNet)

[Montiet al., 2017]uni- fies somecon volutionaloperationsonnon-Euclideanstruc- tured data(graph ormanifold) asmixture CNNs.

2.4 Motivation

After there viewoftheexisting schemes,the maindra wbacks of thesemethods, labelpropag ation(LP) andgraphconv olu- tional networks(GCN),are summarizedthat threekinds of information arenot fullyutilized bythe existing approaches. LP predictsthe labelsby combiningeither thenetw ork topology ornode featureswith thegi ven labellednodes. Ob- viously,LP approachesha ve notfullyexploredallthe av ail- able information,including thenetw orktopology ,nodefea- tures andgi venlabels. GCN inEq. (4),whi chis representedinFigure1(A), can be rewrittenas

H=((~D12

~A~D12 )|{z}

First Term(X)|{z}

Second Term);(8)

where thefirst termis thegi ven graphLaplacian withoutthe parameters, andthe secondterm isthe fullyconnected net- work(FCN) whichdirectly employs thenode featuresasin- puts. [Liet al., 2018]claims thatthe classificationperfor - mance issignificantly improv edcomparedtoGCNwithout the Laplaciansmoothing term(first term).Therefore, the givennetwork topology(forLaplaciansmoothing) playsa veryimportant rolesin theclassification task.

Based onthe abov eobservationin

[Liet al., 2018], we further obtainthat "A clearernetwork(community) struc- ture willimpro vetheperformanceofsemi-supervised node classification". Thepresenceofcommunity(modular/cluster) structures, inwhich thenodes aredensely connectedwithin the communitiesand seldomlyconnected acrossthe commu- nities, isa commonproperty ofnetw orks.F orbetter illus- tration, weconduct experiments onthreeattributed networks, Cora, Citeseerand PubMed,with thesame attribute matrix and labellednodes yetthree different network topologies. FCN onlyutilize thenode featureswithout thegraph convolutionoperation;

GCN takesthegi ven networktopologyAas input;

GCN-GT employstheground truthmembership matrixG= [gij]2 f0;1gNfiN, wheregij= 1if andonly if the verticesviandvjare inthe sameclass. It isob viousthatthecommunity structureof GCN-GTis clearer thanthat ofGCN, andthe communitystructure of

GCN isclearer thanthat ofFCN. Proceedingsofthe Tw enty-E ighthInternationalJointConferenceon ArtificialIntelligence(IJCAI-19)

4056

As canbe observed inTable1, theperformance isim-

provedwhenthe network structure becomesclear.This cer- tainly revealsthatarefined network topologywill benefit the classificationperformance. Howe ver,thenetworktopol- ogy isfix edinGCN,which limitsthe flexibility ofthe net- work.Some previous workhav eshownthat thenetwork structure canbe improv edwiththelabels [Zhuet al., 2003;

Lu andPeng, 2013

]. However,thegivenlabel information has notbeen properlyinte gratedwith thenetworktopology in GCN.Therefore, GCNhas notfully utilizedthe giv enla- bel information.

3 TopologyOptimizationbased Graph

ConvolutionalNetworks

The existingwork reviewedin Section2motivatesus tore- fine thenetw orktopology.Although thereexistspre vious methods, whichrefine thenetw orktopology withthegiv en labels, theselabel informationhas notbeen fullye xploited. Therefore, inthis paper, weconsidertoutilize thegi ven la- bels tosimultaneously andjointly refine thenetw orktopol- ogy andlearn theparameters ofthe FCN.The flow chartof our proposedmethod issho wnin Figure1(B).Inthis sec- tion, ournetw orktopologyrefinementmethod isfirstly in- troduced. Then,the proposedT opologyOptimization based Graph ConvolutionalNetworks(T O-GCN)ispresented,fol- lowedby theoptimization algorithm.Finally ,the analysisof TO-GCNis giv enfromthemodelandopti mizationperspec- tives.

3.1 NetworkTopology Refinement

Torefine thenetw orktopology withthegiv enlabels and maintain thetopology tobe non-neg ativ e,therefinementis modeled asa labelpropag ationprocess. Withtheassump- tion thatthe nearbyv erticesin agraphtendto sharethe same label, Eq.(1) canbe reformedto min Y12 X i;ja ijjjyiyjjj22= minY12

Tr(YTLY)

s:t: y n=zn8vn2Vl;(9) whereVlstands forthe setof labelledv ertices,zn2 f 0 ;1g1Kandyn2 f0;1g1Kare theground-truth andpre-quotesdbs_dbs30.pdfusesText_36

[PDF] document de référence 2014 - Le groupe Bouygues

[PDF] E Commerce Kenneth Laudon 9e Download - Go About

[PDF] Download PDF E-Commerce 2015, Global Edition Book

[PDF] advantages and disadvantages of the electronic commerce

[PDF] Global B2C E-commerce Report 2016 - EcommerceWiki

[PDF] E-commerce and the WTO - World Trade Organization

[PDF] E-commerce in Europe 2016 - PostNord

[PDF] E-commerce statistics Statistics Explained - European Commission

[PDF] e-commerce & commerce - Fédération Française du prêt à porter

[PDF] Le Royaume-Uni - Landmark Global

[PDF] QUARTERLY RETAIL E-COMMERCE SALES 3rd QUARTER 2017

[PDF] Images correspondant à e en 3d filetype:pdf

[PDF] Les acteurs de la GRH - e-Rhorg

[PDF] Avis de recrutement des Agents Opérations 2017

[PDF] Guides thématiques V2014 à destination des experts-visiteurs - HAS