lecture15_recent_graph_neural_netorkspdf
lecture15_recent_graph_neural_netorkspdf
Page 1 of 820
Xavier shared this file. Want to do more with it?
  1. 1CE7454 : Deep Learning for Data ScienceXavier Bresson1School of Computer Science and EngineeringData Science and AI Research Centre Nanyang Technological University (NTU), SingaporeLecture 15: Recent Developments in Graph Network ArchitecturesSemester 1 2020/21Xavier Bressonhttps://twitter.com/xbresson
  2. 2OutlineXavier Bresson2Weisfeiler-Lehman GNNsGraph Isomorphism NetworksPrincipal NeighbourhoodAggregationEquivariant GNNs3-WL/Ring GNNs Sparse WL-GNNsLow-Rank Attention GNNsGraph Substructure Networks Expressivity Power and Universal ApproximatorExpressivity with WLGraph Universal ApproximatorLimitations of ExpressivityGraph Positional EncodingsIndex Positional EncodingsStructural Message Passing NetworksLaplacian Positional EncodingsLink Prediction with Edge RepresentationGNNs for Sets
  3. 3OutlineXavier Bresson3Weisfeiler-Lehman GNNsGraph Isomorphism NetworksPrincipal NeighbourhoodAggregationEquivariant GNNs3-WL/Ring GNNs Sparse WL-GNNsLow-Rank Attention GNNsGraph Substructure Networks Expressivity Power and Universal ApproximatorExpressivity with WLGraph Universal ApproximatorLimitations of ExpressivityGraph Positional EncodingsIndex Positional EncodingsStructural Message Passing NetworksLaplacian Positional EncodingsLink Prediction with Edge RepresentationGNNs for Sets
  4. 4Graph IsomorphismXavier Bresson4Graph isomorphism : Two graphs are isomorphic if there exists an index permutation between the nodes that preserves node adjacencies. An exampleof two isomorphic molecular graphs. Node correspondence is given by the node color. Determining whether two graphs are isomorphic is NP-intermediate: It is not known if a polynomial time algorithm exists, or the problem is NP-hard.Weisfeiler-Lehman(WL) proposed an algorithm[1]to test if two graphs are not isomorphic. However, the WL test is not sufficientto guarantee that two graphs are isomorphic.FCCHHHHOGraph 1CFCHHHHOGraph 2Isomorphicgraphs,[1] B Weisfeiler, A Lehman, A reduction of a graph to a canonical form and an algebra arising during this reduction, 19681234567814253768
  5. 5WL Test[1]Xavier Bresson5Idea : Design an injective “coloring” function fWLthat takes a pair (node, its neighborhood) as input, and outputs a new node color :Properties of fWL:Unique color for the same pair of (node, its neighborhood).Different colors for distinct pairs of (node, its neighborhood). fWLc`i,{c`j}j2Ni=c`+1ifWL( )FCCOfWL( )CFCO=Same colorfWL( )CFOfWL( )CFCDifferent color6=iterationMultiset (set of unordered and repetitive elements)fWL(F,{C,C,O})=fWL(F,{O,C,C})=fWL(F,{C,O})=fWL(F,{C,C})=Simply said, fWLmust be injective(mapping different inputs to different outputs).Multiset functionInjectivity is a discriminative property.[1] B Weisfeiler, A Lehman, A reduction of a graph to a canonical form and an algebra arising during this reduction, 1968
  6. 6WL Test[1]Xavier Bresson6WL algorithm iterativelyapplies the coloring function fWLuntil no new colors are created. This produces a canonical representation of a graph as a histogram of colors.FCCHHHHOGraph 1Step 1+Step 2+Step 3+Step 4No new colors created, algorithm stops.Histogram of colors[1] B Weisfeiler, A Lehman, A reduction of a graph to a canonical form and an algebra arising during this reduction, 1968
  7. 7WL Test[1]Xavier Bresson7The WL test is a necessary but not sufficient condition for isomorphism : If the two graphs have differentcolor histograms then the two graphs are guaranteed to be non-isomorphic.If the two graphs produce the samehistogram of colors, the graphs are possibly isomorphic (although not guaranteed).No new colors created, algorithm stops.Histogram of colors(Possibly) Isomorphic graphs,[1] B Weisfeiler, A Lehman, A reduction of a graph to a canonical form and an algebra arising during this reduction, 1968FCCHHHHOGraph 1Histogram of colorsStep 1+Step 2+Step 3+Step 4CFCHHHHOGraph 2CFCHHHHOGraph 2
  8. 8WL-based Graph Neural NetworksXavier Bresson8Can we turn the WL test into a neural network to classify non-isomorphic graphs ?Yes, but is it necessary to have a learning process for the WL test ? No, but designinga constraint-free analytical injective function fWLis hard and easierto do in a learningsetting.Distinguishing non-isomorphic graphs is not necessarily useful in practice. What is usefulis the “coloring” process that can provide rich representation of data-structured graphs and can be used for downstream tasks like graph classification or regression.FCCHHHHO++Applications :Classify non-isomorphic graphsGraph classification/regressionWL-based GNNs
  9. 9Graph Isomorphism Networks (GINs)[1]Xavier Bresson9The WL test algorithm iterates the “coloring” formula :where function fWLprovides :A unique color for the same pair (ci,{cj}Ni). Different colors for distinct pairs (ci,{cj}Ni). This implies that fWLmust be injective:Which aggregator functions are injective? fWLc`i,{c`j}j2Ni=c`+1i[1] Xu, Hu, Leskovec, Jegelka, How powerful are graph neural networks?, 2019ci6=ci0or{c`j}j2Ni6={c`j}j2Ni0)fWLc`i,{c`j}j2Ni6=fWLc`i0,{c`j}j2Ni0
  10. 10Graph Isomorphism Networks (GINs)[1]Xavier Bresson10(Simple) aggregator functionsfWL:[1] Xu, Hu, Leskovec, Jegelka, How powerful are graph neural networks?, 2019hi= maxj2Nihjhi= meanj2Nihjhi= sumj2NihjNot injectiveNotinjectiveInjectivei, hij1, hj1= 2j2, hj2=3Max fails to discriminate the red nodeMean, Sum succeedMax, Mean fail to discriminate the red nodeSum succeedsInjectivityis a discriminative property at the node level and by extension at the graph level.
  11. 11h`+1i=fGINh`i,{h`j}j2Ni= MLP`⇣(1 +")h`i+Xj2Nih`j⌘Graph Isomorphism Networks (GINs)[1]Xavier Bresson11Can we design a NN that is maximally expressive in the sense that fNNis as powerful as the WL testto distinguish non-isomorphic graphs? Yes, and such NN has an aggregation function of the form :where we must haveFunction ginjective.Sum aggregator (mean/max are not injective). Constant εmust be irrational(a number that cannot be written as a ratio of two integers, π= 3.1415..)It is difficult to design an analytical injective function g (upper bound on the neighborhood size for countable colors, one-hot encoding does not provide meaningful distance between features).A MLP can approximate gas the universal approximation theorem guarantees the existence of such function (although SGD is not guaranteed to find it):fNNh`i,{h`j}j2Ni= (1 +")g(h`i) +Xj2Nig(h`j)Scalar εis learned (computer cannot represent irrational numbers)[1] Xu, Hu, Leskovec, Jegelka, How powerful are graph neural networks?, 2019
  12. 12Graph Isomorphism Networks (GINs)[1]Xavier Bresson12Graph readout aggregation function must also be injective:Summary :Injectivity: GIN can learn injective function from (graph, node features) to Euclidean space.Discriminative power : GIN can learn different graph representations in RKfor graphs that can be distinguished by the WL test.Pioneer work[1]with[2]on the theoretical question of representation/discriminative power of GNNs.Sum functionhG= MLP⇣Xi2VhLi⌘2RK[1] Xu, Hu, Leskovec, Jegelka, How powerful are graph neural networks?, 2019[2] Morris, Ritzert, Fey, Hamilton, Lenssen, Rattan, Grohe, Weisfeiler and leman go neural: Higher-order graph networks, 2019FCCHHHHOCCCCCCCCCCCFCHHHHORK
We use cookies to provide, improve, protect and promote our services. Visit our Privacy Policy and Privacy Policy FAQs to learn more. You can manage your personal preferences, including your ‘Do not sell or share my personal data to third parties’ setting using the “Customize cookies” button below.