{"id":22477,"date":"2020-12-01T11:19:28","date_gmt":"2020-12-01T11:19:28","guid":{"rendered":"https:\/\/www.experfy.com\/blog\/weisfeiler-lehman-substructures-expressive-gnn\/"},"modified":"2021-05-21T03:31:58","modified_gmt":"2021-05-21T03:31:58","slug":"weisfeiler-lehman-substructures-expressive-gnn","status":"publish","type":"post","link":"https:\/\/www.experfy.com\/blog\/ai-ml\/weisfeiler-lehman-substructures-expressive-gnn\/","title":{"rendered":"Beyond Weisfeiler-Lehman: Using Substructures For Provably Expressive Graph Neural Networks"},"content":{"rendered":"\n

In this post, I discuss how to design local and computationally efficient provably powerful graph neural networks that are not based on the Weisfeiler-Lehman tests<\/em><\/em> hierarchy.<\/em><\/p>\n\n\n\n

This is the second in the series of posts on the expressivity of graph neural networks. See\u00a0Part 1<\/a>\u00a0describing the relation between graph neural networks and the Weisfeiler-Lehman graph isomorphism test.<\/em><\/p>\n\n\n\n

Recent groundbreaking papers [1\u20132] established the connection between graph neural networks and the graph isomorphism tests, observing the analogy between the message passing mechanism and the Weisfeiler-Lehman (WL) test [3]. WL test is a general name for a hierarchy of graph-theoretical polynomial-time iterative algorithms for determining graph isomorphism. The k<\/em>-WL test recolours k<\/em>-tuples of vertices of a graph at each step according to some neighbourhood aggregation rules and stops upon reaching a stable colouring. If the histograms of colours of the two graphs are not the same, the graphs are deemed not isomorphic; otherwise, the graphs are possibly (but not necessarily) isomorphic.<\/p>\n\n\n\n

Message passing neural networks are at most as powerful as the 1-WL test (also known as node colour refinement), and thus unable to distinguish between even very simple instances of non-isomorphic graphs. For example, message passing neural networks cannot count triangles [4], a motif known to play an important role in social networks where it is associated with the clustering coefficient indicative of how \u201ctightly knit\u201d the users are [5]. It is possible to design more expressive graph neural networks that replicate the increasingly more powerful k<\/em>-WL tests [2,6]. However, such architectures result in high complexity and large number of parameters, but most importantly, typically require non-local operations that make them impractical.<\/p>\n\n\n\n

\"Beyond
Examples of non-isomorphic graphs that cannot be distinguished by 1-WL but can be distinguished by 3-WL due to its capability of counting triangles.<\/figcaption><\/figure>\n\n\n\n

Thus, provably powerful graph neural networks based on the Weisfeiler-Lehman hierarchy are either not very powerful but practical, or powerful but impractical [7]. I argue that there is a different simple way to design efficient and provably powerful graph neural networks, which we proposed in a new paper with Giorgos Bouritsas and Fabrizio Frasca [8].<\/p>\n\n\n\n

Graph Substructure Networks.\u00a0<\/strong>The idea is actually very simple and conceptually similar to\u00a0positional encoding<\/a>\u00a0or graphlet descriptors [9]:\u00a0we make the message passing mechanism aware of the local graph structure, allowing for computing messages differently depending on the topological relationship between the endpoint nodes.<\/mark>\u00a0This is done by passing to message passing functions additional structural descriptors associated with each node [10], which are constructed by subgraph isomorphism counting. In this way, we can partition the nodes of the graph into different equivalence classes reflecting topological characteristics that are shared both between nodes in each graph individually and across different graphs.<\/p>\n\n\n\n

We call this architecture Graph Substructure Network (GSN). It has the same algorithmic design and memory and computational complexity as standard message passing neural networks, with an additional pre-computation step in which the structural descriptors are constructed. The choice of the substructures to count is crucial both to the expressive power of GSNs and the computational complexity of the pre-computation step.<\/p>\n\n\n\n

The worst-case complexity of counting substructures of size k<\/em> in a graph with n<\/em> nodes is (n\u1d4f<\/em>). Thus, it is similar to high-order graph neural network models or Morris [2] and Maron [6]. However, GSN has several advantages over these methods. First, for some types of substructures such as paths and cycles the counting can be done with significantly lower complexity. Secondly, the computationally expensive step is done only once as preprocessing and thus does not affect network training and inference that remain linear, the same way as in message-passing neural networks. The memory complexity in training and inference is linear as well. Thirdly and most importantly, the expressive power of GSN is different from k<\/em>-WL tests and in some cases is stronger.<\/p>\n\n\n\n

How powerful are GSNs?<\/strong> The substructure counting endows GSN with more expressive power than the standard message-passing neural networks. First, it is important to clarify that the expressive power of GSN depends on the graph substructures used. Same way as we have a hierarchy of k<\/em>-WL tests, we might have different variants of GSNs based on counting one or more structures. Using structures more complex than star graphs, GSNs can be made strictly more powerful than 1-WL (or the equivalent 2-WL) and thus also more powerful than standard message passing architectures. With 4-cliques, GSN is at least no less powerful than 3-WL, as shown by the following example of strongly regular graphs on which GSN succeeds while 3-WL fails:<\/p>\n\n\n\n

\"Beyond
Example of non-isomorphic\u00a0strongly regular graphs<\/a>\u00a0with 16 vertices and node degree 6, where every two adjacent vertices have 2 mutual neighbours, and every two non-adjacent vertices also have 2 mutual neighbours. The 3-WL test fails on this example, while GSN with 4-clique structure can distinguish between them. In the graph on the left (known as the Rook\u2019s graph) each node participates in exactly one 4-clique. The graph on the right (Shrikhande graph<\/a>) has maximum cliques of size 3 (triangles). Figure from [8].<\/figcaption><\/figure>\n\n\n\n

More generally speaking, for various substructures of (1) size, as long as they cannot be counted by 3-WL, there exist graphs where GSN succeeds and 3-WL fails [11]. While we could not find examples to the contrary, they might in principle exist \u2014 that is why our statement about the power of GSN is of a weak form, \u201cat least not less powerful\u201d.<\/p>\n\n\n\n

This holds for larger k<\/em> as well; a generalisation of strongly regular graphs in the above figure, called k<\/em>–isoregular<\/em>, are instances on which the (k<\/em>+1)-WL test fails [12]. These examples can also be distinguished by GSN with appropriate structures. The expressive power of GSNs can thus be captured by the following figure:<\/p>\n\n\n\n

\"Beyond
GSN is outside the Weisfeiler-Lehman hierarchy. With the appropriate structure (e.g. cliques or cycles of certain size), it is likely to be made at least not less powerful than k-WL.<\/figcaption><\/figure>\n\n\n\n

How powerful can GSN be in principle? This is still an open question. The\u00a0Graph Reconstruction Conjecture<\/a>\u00a0[13] postulates the possibility of recovering a graph from all its node-deleted substructures. Thus, if the Reconstruction Conjecture is correct, a GSN with substructures of size\u00a0n<\/em>\u22121 would be able to correctly test isomorphism of any graphs. However, the Reconstruction Conjecture is currently proven only for graphs of size\u00a0n\u2264<\/em>11 [14], and second, such large structures would be impractical.<\/p>\n\n\n\n

The more interesting question is whether a similar result exists for \u201csmall\u201d structures (of (1) size independent of the number of nodes\u00a0n<\/em>). Our empirical results show that GSN with small substructures such as\u00a0cycles<\/a>,\u00a0paths<\/a>, and\u00a0cliques<\/a>\u00a0work for strongly regular graphs, which are known to be a tough nut for the Weisfeiler-Lehman tests.<\/p>\n\n\n\n

Most importantly, GSN builds on top of standard message-passing architectures and thus inherits its locality and linear complexity. The hyperparameters of the method include the structures counted for the construction of the structural descriptors. It is likely that practical applications will be guided by the tradeoff between the required expressive power, the size of the structures that can guarantee it, and the complexity of computing them.<\/p>\n\n\n\n

\"Beyond
Using GSN with cycles of length k\u22656 significantly improves the prediction of chemical properties of molecular graphs in the ZINC database that is used by pharmaceutical companies for virtual screening of drug candidates. Such cyclic structures are abundant in organic molecules. Figure from [8].<\/figcaption><\/figure>\n\n\n\n

In our experiments, we observed that different problems and datasets benefit from different substructures, so it is likely that this choice is problem-specific. Fortunately, we often know what substructures matter in some applications. For example, in social networks, triangles and higher-order cliques are common and have a clear \u201csociological\u201d interpretation. In chemistry, cycles are a\u00a0very frequent pattern<\/a>, such as 5- and 6-membered\u00a0aromatic ring<\/a>\u00a0that appear in a plethora of organic molecules. The figure below shows an example most of us are familiar with, the molecule of\u00a0caffeine<\/a>, whose level in my bloodstream is alarmingly low. This sounds like the right moment to finish this post and make myself a cup of coffee.<\/p>\n\n\n\n

\"Trimethylxanthine\"\/
1,3,7-Trimethylxanthine<\/a>, better known as caffeine, is an example of a chemical cyclic compound containing 5- and 6-rings (denoted by red and yellow).<\/figcaption><\/figure>\n\n\n\n

[1] K. Xu et al.\u00a0How powerful are graph neural networks?<\/a>\u00a0(2019). Proc. ICLR.<\/p>\n\n\n\n

[2] C. Morris et al.\u00a0Weisfeiler and Leman go neural: Higher-order graph neural networks<\/a>\u00a0(2019). Proc. AAAI.<\/p>\n\n\n\n

[3] B. Weisfeiler, A. Lehman,\u00a0The reduction of a graph to canonical form and the algebra which appears therein<\/a>, 1968 (English translation)<\/p>\n\n\n\n

[4] Consequently, two graphs with a different number of triangles would be considered possibly isomorphic by the 1-WL test, or equivalently, will have an identical embedding constructed by a message passing neural network. There have been substantial new results extending our understanding of what structures are invariant under WL tests, see e.g. V. Arvind et al.\u00a0On Weisfeiler-Leman invariance: subgraph counts and related graph properties<\/a>\u00a0(2018) arXiv:1811.04801 and Z. Chen et al.\u00a0Can graph neural networks count substructures?<\/a>\u00a0(2020) arXiv:2002.04025.<\/p>\n\n\n\n

[5] Graph substructures have been used in complex networks for decades now. In bioinformatics, the seminal papers of R. Milo et al. Network motifs: simple building blocks of complex networks (2002). Science 298 (5594):824\u2013827. and N. Pr\u017eulj et al.\u00a0Modeling Interactome: Scale-free or geometric?<\/a>\u00a0(2004) Bioinformatics 20(18):3508\u20133515 introduced graph motifs and graphlets for the analysis of biological interaction networks. In social networks, the study of triangular motifs dates back to at least P. W. Holland and S. Leinhardt, Local structure in social networks (1976). Sociol. Methodol. 1\u201345.<\/p>\n\n\n\n

[6] H. Maron et al.\u00a0Provably powerful graph neural networks<\/a>\u00a0(2019). Proc. NeurIPS.<\/p>\n\n\n\n

[7] The 3-WL-equivalent graph neural network architecture of Morris has (n<\/em>\u00b3) space- and (n<\/em>\u2074) time complexity. The architecture of Maron has a slightly better (n<\/em>\u00b2) space- and (n<\/em>\u00b3) time complexity. For a modestly-sized graph with 1M nodes this still translates into enormous 1TB of memory and an exaflop of computation.<\/p>\n\n\n\n

[8] G. Bouritsas et al.\u00a0Improving graph neural network expressivity via subgraph isomorphism counting<\/a>\u00a0(2020). arXiv:2006.09252.<\/p>\n\n\n\n

[9] Graph analysis approaches based on substructure counting obviously predate the recent works on graph deep learning. Notable examples include the graphlet signatures proposed in bioinformatics in T. Milenkovi\u00e6 and N. Pr\u017eulj,\u00a0Uncovering biological network function via graphlet degree signatures<\/a>\u00a0(2008). Cancer Inform. 6:257\u2013273, or graphlet kernels N. Shervashidze et al.\u00a0Efficient graphlet kernels for large graph comparison<\/a>\u00a0(2009). Proc. AISTATS.<\/p>\n\n\n\n

[10] We show the same mechanism for edges as well, which I omit here for brevity.<\/p>\n\n\n\n

[11] 3-WL appears to be rather weak in terms of substructure counting. For example, it can count motif cycles of up to 7 nodes, but fails to count induced 4-cycles or paths of length 4. It is currently not clear what substructure counting capabilities are obtained by going up in the WL-hierarchy.<\/p>\n\n\n\n

[12] B. L. Douglas,\u00a0The Weisfeiler-Lehman method and graph isomorphism testing\u00a0<\/a>(2011). arXiv:1101.5211. Note that there is some level of confusion between what different references call \u201ck<\/em>-WL\u201d. Douglas uses the term\u00a0k<\/em>-WL for what others call (k<\/em>\u22121)-FWL (\u201cfolklore\u201d WL). In our terminology,\u00a0k<\/em>-WL fails on (k<\/em>\u22121)-isoregular graphs. Strongly regular graphs are 2-isoregular.<\/p>\n\n\n\n

[13] P.J. Kelly,\u00a0A congruence theorem for trees<\/a>\u00a0(1957). Pacific J. Math. 7:961\u2013968.<\/p>\n\n\n\n

[14] B. D. McKay, Small graphs are reconstructible (1997). Australasian J. Combinatorics 15:123\u2013126.<\/p>\n\n\n\n

I am grateful to Luca Belli, Giorgos Bouritsas, and Fabrizio Frasca for their help with proof-reading this post. A\u00a0<\/em>Chinese translation<\/em><\/a>\u00a0of this post is available by courtesy of\u00a0<\/em>Zhiyong Liu<\/em><\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

This post discusses how to design local and computationally efficient provably powerful graph neural networks that are not based on the Weisfeiler-Lehman tests hierarchy.<\/p>\n","protected":false},"author":874,"featured_media":18079,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"content-type":"","footnotes":""},"categories":[183],"tags":[97,206,561,578,1071],"ppma_author":[3686],"class_list":["post-22477","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ai-ml","tag-artificial-intelligence","tag-deep-learning","tag-graph-neural-networks","tag-graph-theory","tag-weisfeiler-lehman-test"],"authors":[{"term_id":3686,"user_id":874,"is_guest":0,"slug":"michael-bronstein","display_name":"Michael Bronstein","avatar_url":"https:\/\/www.experfy.com\/blog\/wp-content\/uploads\/2020\/08\/Michael-Bronstein-150x150.jpg","user_url":"https:\/\/www.imperial.ac.uk\/people\/m.bronstein","last_name":"Bronstein","first_name":"Michael","job_title":"","description":"Michael Bronstein is Professor, Chair in Machine Learning and Pattern Recognition at Imperial College, London, besides Head of Graph ML at Twitter \/ ML Lead at ProjectCETI\/ ex Founder & Chief Scientist at Fabula_ai\/ ex at Intel #AI #ML #graphs. His main expertise is in theoretical and computational geometric methods for data analysis, and his research encompasses a broad spectrum of applications ranging from machine learning, computer vision, and pattern recognition to geometry processing, computer graphics, and imaging. He has authored over 150 papers, the book Numerical geometry of non-rigid shapes (Springer 2008), and holds over 30 granted patents."}],"_links":{"self":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/22477","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/users\/874"}],"replies":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/comments?post=22477"}],"version-history":[{"count":1,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/22477\/revisions"}],"predecessor-version":[{"id":23179,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/posts\/22477\/revisions\/23179"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media\/18079"}],"wp:attachment":[{"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/media?parent=22477"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/categories?post=22477"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/tags?post=22477"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.experfy.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=22477"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}