Saturday Morning NeuroSim Discussion Thread: Causality

Over the past three years, the Saturday Morning NeuroSim group has met weekly on Saturdays (mornings in North America). The Saturday Morning format continues in the tradition of Saturday Morning Physics and covers a wide variety of topics.

Our discussion thread on causality begins with Causality and Circles on May 13. From a Mastodon post by Yohan John, we considered how spatialized diagrams are confused with temporal sequences in a feedback loop. We also covered three papers in this session.

Vernon, D., Lowe, R., Thill, S., and Ziemke, T. (2015). Embodied cognition and circular causality: on the role of constitutive autonomy in the reciprocal coupling of perception and action. Frontiers in Psychology, 6, 1660.

Raginsky, M. (2023). Directed Information and Pearl’s Causal Calculus. arXiv, 1110.0718.

Laland, K.N., John Odling-Smee, J., Hoppitt, W., and Uller, T. (2013). More on how and why: cause and effect in biology revisited. Biological Philosophy, 28, 719–745.

Our conversation continued after the last week of Neuromatch Academy, when the NMA curriculum featured causal networks. Our July 29 meeting featured a collection of references on Bayesianism, Probabilistic Graphical Models, methods of integration, time-series applications, and more. Some core readings are given below.

Stanford Encyclopedia of Philosophy: causal models. This article takes an epistemological approach and provides us with a baseline for structural equation model, graphical probabilistic models, and other statistical formulations of causal relationships.

Daphne Koller’s Probabilistic Graphical Models course. Hosted on Stanford University’s Open Classroom platform, this course includes units on representation, inference, learning, and causation. The causation unit covers decision theory, utility functions, influence diagrams, and the notion of perfect information.

Pearl, J. (2000). Causality. Cambridge Press, Cambridge, UK. This classic book by Judea Pearl builds from a theory of inferred causation, starting at causal diagrams, and continuing through direct effects, indirect effects, confounds, counterfactuals, bounding effects, and probabilities. The book also covers structural models, decision analysis, and Simpson’s Paradox as the basis for methods for detecting causal relationships.

Scholkopf, B. (2019). Causality for Machine Learning. arXiv, 1911.10500.

Heckman, J.J. (2005). The Scientific Model of Causality. Sociological Methodology, 35, 1–97. Causality from an econometrics point-of-view. Counterfactuals are a set of possible outcomes generated by determinants. A causal effect is defined by the change in the manipulated factor where amongst a set of factors, in a situation where all but one is held constant.

Taskesen, E. (2021). A step-by-step guide in detecting causal relationships using Bayesian structure learning in Python. Towards Data Science, September 7.

Which variables have a direct causal effect on a target variable? Hint: association and correlation are not equivalent to causation.

Bayesian Models:

Neuberg, L.G. (2003). Causality: models, reasoning, and inference. Econometric Theory, 19, 675–685.

Pearl, J. (2001). Bayesianism and causality, or, why I am only a half-Bayesian. In “Foundations of Bayesianism”, pgs. 19–36. Kluwer Press.

Methods of Interaction: networks and non-directional graphs, as opposed to directed acyclic graphs (DAGs), require a different set of considerations. The methods below cover highly interacting systems like graphs and how change over time can be properly interpreted as causal.

Leng, S., Ma, H., Kurths, J., Lai, Y-C., Lin, W., Aihara, K., and Chen, L. (2020). Partial cross mapping eliminates indirect causal influences. Nature Communications, 11, 2632.

Park, S.H., Ha, S., and Kim, J.K. (2023). A general model-based causal inference method overcomes the curse of synchrony and indirect effects. Nature Communications, 14, 4287.

From the Granger Causality Wikipedia entry.

Time-series using Granger Causality: the first two references apply Granger Causality to time-series datasets. In such cases, the datapoints are dependent with respect to time. Given two time-series x and y, x is the cause of y if x predicts y (lagged with respect to x over a certain time interval) given x and prior values of y. This is in comparison with simply predicting the current value of y given previous values of y, which would be the counterfactual case.

The final paper in the group (Stokes and Purdon) critiques Granger Causality from a Neuroscience perspective.

Carlos‐Sandberg, L. and Clack, C.D. (2021). Incorporation of causality structures to complex network analysis of time‐varying behaviour of multivariate time series. Scientifc Reports, 11, 18880.

Runge, J., Nowack, P., Kretschmer, M., Flaxman, S., Sejdinovic, D. (2019). Detecting and quantifying causal associations in large nonlinear time series datasets. Science Advances, 5(11), aau4996.

Stokes, P.A. and Purdon, P.L. (2017). A study of problems encountered in Granger causality analysis from a neuroscience perspective. PNAS, 114(34), E7063-E7072.

The third session (August 5) was a focus on causality specifically as it is treated in Neuroscience. This session followed up on a Twitter debate by Kording Lab and Earl Miller about the role of causality in neuroscience. The consensus to the question “Why is Neuroscience so into causality?” was that it provides a means to identify mechanisms for function. Causality in neuroscience differs from philosophical discussions about causality in that Neuroscience must infer causality from data, while philosophers (and statisticians) do the work of proving causality.

One interesting point from Kording Lab is that there is a difference between proximate causes and ultimate causes. In some fields, causality is obvious and so causal methods are not always necessary. But Neuroscience is partially about the behavioral substrate, and so we can turn to Niko Tinbergen’s four questions. The four questions concern 1) how a trait arose in development (proximate, dynamic), 2) how a trait arose in evolution (ultimate, dynamic), 3) what is the mechanism or structure of a trait (proximate, static), and 4) what is the adaptive value or function of a trait (ultimate, static).

You can read more about Tinbergen’s four questions and their causal implications in the following papers.

Beer, C. (2020). Niko Tinbergen and questions of instinct. Animal Behaviour, 164, 261–265.

Nesse, R.M. (2019). Tinbergen’s four questions: two proximate, two evolutionary. Evolution, Medicine, and Public Health, 2, doi:10.1093/ emph/eoy035.

Mayr, E. (1961). Cause and effect in biology. Science, 134, 1501–1506.

The other papers from this session focused on mental representations and causal functional connectivity in the brain, respectively.

Sloman, S.A. and Lagnado, D. (2015). Causality in Thought. Annual Reviews in Psychology, 66, 223–247.

While Bayesian approaches are good for theory-building, they are an incomplete account of what goes on in the cognitive world.

Biswas, R. and Shlizerman, E. (2022). Statistical perspective on functional and causal neural connectomics: The Time-Aware PC algorithm. PLoS Computational Biology, 18(11), e1010653.

The fourth session (August 19) picks up on a point covered in the second session, namely how causality can be inferred from network data. This covers related ideas of transitivity, weak interactions, and anti-causal models. Papers for this session include networks in ecology, anticipative and non-anticipative control theory, and anti-causal systems.

Typology of causal models for past, present, and future events.

Naghshtabrizi, P. and Hespanha, J.P. (2006). Anticipative and non-anticipative controller design for network control systems. Lecture Notes in Control and Information Science, 331.

Sugihara, G., May, R., Ye, H., Hsieh, C-H., Deyle, E., Fogarty, M., Munch, S. (2012). Detecting Causality in Complex Ecosystems. Science, 338, 496–500.

Chattopadhyay, I. (2014). Causality Networks. arXiv, 1406.6651.

Anticausal System. Wikipedia.

McCurdy, T. (2007). Causal Systems: understanding the basics. Physics Forums. September 23.

From the Necessity and Sufficiency Wikipedia entry.

Finally, some fields (cell and molecular biology) have working models of causation that while useful, are not particularly illuminating. In the cell and molecular biology example, the traditional model of necessity and sufficiency (a mechanism being necessary but not sufficient) can be criticized for not being complete with respect to incorporating counterfactuals or multiple potential causes. See this paper for more information:

Bizzarri, M., Brash, D.E., Briscoe, J., Grieneisen, V.A., Stern, C.D., and Levin, M. (2019). A call for a better understanding of causation in cell biology. Nature Reviews Molecular Cell Biology, 20, 261–262.

Google Summer of Code 2023

Welcome to the new Google Summer of Code scholars for 2023! INCF is sponsoring four students for which I (Bradly Alicea) am acting as mentor: two students for the DevoWorm group (via the OpenWorm Foundation community) and two students for the Orthogonal Research and Education Laboratory. These four students are pursuing three projects.

D-GNNs and DevoLearn (sponsored by the DevoWorm group)

Congratulations to Himanshu Chougule and Sushmanth Reddy Mereddy for being accepted to work on the Developmental Graph Neural Networks (D-GNNs) project. Sushmanth has been contributing to the DevoLearn platform for quite some time and will spend this summer working on improving the image segmentation to GNN embedding pipeline. Himanshu was a part of last Summer's GSoC cohort in the Orthogonal Research and Education Laboratory, working on the Open-source Sustainability project. His work resulted in developing Agent-based Model-Reinforcement Learning hybrid models. This year, he will be working on building Topological Data Analytic capabilities into the D-GNN pipeline. 

Mayukh Deb and Jiahang Li are co-mentors for this project.

Virtual Reality for Research and Open-source Sustainability (sponsored by the Orthogonal Research and Education Lab)

Congratulations to Vrushali Nandurkar and R.V. Rajagopalan for being accepted to work on the projects Virtual Reality for Research and Open-source Sustainability, respectively. Vrushali is enthusiastic about working on creating open-source virtual world assets for scientific research and educational initiatives. R.V. will be working on a continuation of the Open-source Sustainability project, helping to augment the existing models and web interface.

Jesse Parent is a co-mentor for both projects, while Brian McCorkle is a co-mentor for the Open-source Sustainability project. 

Ancient Embryogenesis and Evolutionary Origins

"Darwin as an Embryo". In this case, Neoteny really does recapitulates Phylogeny! COURTESY: Stable Diffusion.

For this year's delayed Darwin Day post, I will present some of the latest work on ancient embryos which we have been discussing in the DevoWorm group meetings. While this is by no means a complete review, we will discuss the earliest fossil evidence for eggs, embryos, and nervous systems (in animals, not plants), in addition to the conditions that lead to their emergence. In short, how did we get to embryos from a universal common ancestor with bacteria and archebacteria, and why do only different types of Eukaryotes (plants, radial symmetrical Metazoans, and bilateral Metazoans) have embryos?

Tree of Life (genome tree) from Hug et.al [1] with three domains. Click to enlarge.

The ecological states of early Earth. COURTESY: J. Hirshfeld/Wikimedia. Click to enlarge.

We begin in the Cambrian, where the first bilaterian appeared around 600 million years ago, approximately 70-80 million years before the Cambrian explosion [2]. In between the emergence of bilaterians, several key innovations occurred that suggests the origins of embryos and egg-laying. The first are the presence of fossilized burrows [2] for egg-laying behaviors. By the end of the Cambrian explosion, early pancrustecean arthropod species were possibly subject to life-history tradeoffs related to clutch size [3]. Another key innovation is direct evidence in the form of well-preserved multicellular structures from the period leading up to the Cambrian explosion that show a transition in cell geometry from a 2-cell stage to a cleavage stage [4]. As representative of a variety of ancestral algae species from the Doushantuo formation, these remains have not been connected to any particular adult form. However, they do demonstrate oogenesis and cleavage [2]. Finally, the functional genomics of developmental pattern formation emerged during this time [5]. This includes a ProtoHox cluster in ancestral cnidarians [6], Hox gene duplication [7], and an increase in body size and shape diversity alongside the advent of bilaterian bauplans [8]. Multiple Hox gene families may have served the role of promoting directed locomotion that in turn promoted active exploration of the environment [7].

Images of a potential early embryo, including the 2-cell and cleavage stages [from 4]. Click to enlarge.

The Ediacaran (630-540 million years ago) has yielded a large number of potential embryonic forms. In the Ediacaran biota, we find a number of Metazoan remains with no clear phylogenetic position. However, Evans et.al [9] propose that early embryos evolved independently (with several origins) in the bilaterian clade. However, during this time, a number of general trends emerge that enabled modern bilaterian adult forms. As previously discussed, Multicellular structures with distinct cell types, axial polarity, and anatomical segmentation [10, 11] emerged during this time. Left-right symmetry was a related feature of these embryos [11]. So-called polarized elements [12] such as microtubules, flagella, and apical-to-basal orientation were all found soon after the last Eukaryotic common ancestor (LECA). The evolution and diversification of polarity proteins is consistent with this timeline [12]. Other organismal structures such as a gut, sub-specialization of the phenotype, and a nervous system with heads and appendages are also features of note. We will talk about the emergence of nervous systems later on.

Scenario for the origins of development in bilaterians from [9]. Click to enlarge.

Bicellum brasieri is a 10⁹ year old fossil holozoan that might provide the very earliest examples of modern embryos and embryogenesis [13]. Microfossils of Bicellum demonstrate morphogenesis in the form of cell-cell adhesion for different cell types, as well as differential layers of cells (driven by adhesion) which may be the precursors of tissue differentiation. This can be compared to the Doushantuo embryos from Precambrian China [14], and Caveasphera from 609 million years ago [15], which are perhaps the direct ancestors of Metazoan embryonic forms. These are the first examples of development proceeding within an enclosed space, enabled by cell adhesion similar to what is observed during gastrulation in modern embryos. Caveasphera in particular shows evidence of anatomical polarization (particularly polar aggregation), cell division events, and ingression [15]. This is informative but is not diagnostic of the Urmetazoan condition [16].

Graphical abstract and (top) palynological evidence of Bicellum brasieri (bottom) as shown in [13]. Epidermal layer (A and C), ellipsoid (D) and oblate (E) specimens Click to enlarge.

Since these pre-Cambrian explosion phenotypes are very simple, we can look to fossil evidence for much more complex embryo phenotypes in the late Cretaceous. Xing et.al [17] report on an in-ovo therapod dinosaur embryo, where the body is folded into an elongated egg. The authors are able to demonstrate how the fully formed head and legs are folded into different prehatching postures.

Graphical abstract showing developmental stages of Caveasphera [15]. Click to enlarge.

While the early phylogeny of nervous system origins is the very definition of a tangled tree [18], the first nervous systems coincide with the emergence of discrete body types in the Cambrian [19]. Brains emerged in part from the developmental toolkit responsible for patterning and segmentation [20]. This toolkit consists of genes and regulatory mechanisms that were co-opted for the development of excitable cells [21], synapses [22], and neuronal networks [2]. While the strongest evidence for early embryos only show evidence for bilaterian organization, radial symmetry is actually the basal condition for Metazoans [23]. Therefore, early embryos should yield at least two types of nervous system configurations that are observed in modern phenotypes: a centralized nervous system that converges in the head (the brains of bilaterians), and a distributed nervous system (the nerve nets of cnidarians). Centralized nervous systems originated from the mesoderm layer of triploblastic embryos, while distributed nervous systems are derived from the endoderm of diploblastic embryos. While there is a distinct literature on fossil radial embryos from China [24], there does not seem to be fossil evidence of germ layers formation and subsequent differentiation in any early embryos to date.

Image of Baby Yingliang (therapod dinosaur late-stage embryo) [17]. Click to enlarge.

But what happened before the earliest embryos (1000-650 million years ago)? What ecological conditions might have driven this innovation? One trigger may have been the great oxygenation event, which occurred in two stages: the first at 2.4 billion years ago, and the second at 950 million years ago. It was the second event that increased oxygen content to a level more resembling the present, and in turn drove diversification of distinct fungi, plants, and animals. It is of note that LECA (the last Eukaryotic common ancestor) lies well-beforehand [25]. The earliest embryos (or at least multicellular packings) might have resulted from selection pressure for retaining a low-oxygenation environment. But while these findings may lead to significant speculation, it seems that embryos are unique to Eukaryotic evolution, having no Bacterial or Archaebacterial counterpart despite evolving under the same conditions. It is most likely the interaction of genomic factors, developmental contingencies, and environmental conditions that ultimately lead to the emergence of embryos [26].

Phylogeny with evolution transitions from LUCA to embryos in plants and animals. Included are the two oxygenation events of Earth's history. Transitions derived from Refs [14, 27-31]. Click to enlarge.

References

[1] Hug, L.A. et.al (2016). A new view of the tree of life. Nature Microbiology, 1, 16048. 

[2] Valentine, J.W., Jablonski, D., and Erwin, D.H. (1999). Fossils, molecules and embryos: new perspectives on the Cambrian explosion. Development, 126, 851-859.

[3] Ou, Q., Vannier, J., Yang, X., Chen, A., Mai, H., Shu, D., Han, J., Fu, D., Wang, R., and Mayer, G. (2020). Evolutionary trade-off in reproduction of Cambrian arthropods. Science Advances, 6(18), doi:10.1126/sciadv.aaz3376.

[4] Xiao, S., Zhang, Y. and Knoll, A. H. (1998). Three-dimensional preservation of algae and animal embryos in a Neoproterozoic phosphorite. Nature, 391, 553-558.

[5] Erwin, D.H. (2020). Origin of animal bodyplans: a view from the regulatory genome. Development, 147, dev182899. 

[6] Chourrout, D. et al. (2006). Minimal ProtoHox cluster inferred from bilaterian and cnidarian Hox

complements. Nature, 442, 684–687. 

[7] Holland, P.W.H. (2015). Did homeobox gene duplications contribute to the Cambrian explosion? Zoological Letters, 1, 1. 

[8] Zhuravlev, A.Y. and Wood, R. (2020). Dynamic and synchronous changes in metazoan body size during the Cambrian Explosion. Scientific Reports, 10, 6784. 

[9] Evans, S.D., Droser, M.L., Erwin, D.H. (2021). Developmental processes in Ediacara macrofossils. Royal Society B, 288, 20203055.

[11] Finnerty, J.R., Pang, K., Burton, P., Paulson, D., and Martindale, M.Q. (2004). Origins of bilateral

symmetry: Hox and Dpp expression in a sea anemone. Science, 304, 1335–1337.

[12] Brunet, T. and Booth, D.S. (2023). Cell polarity in the protist-to-animal transition. Current Topics in Developmental Biology, doi:10.1016/bs.ctdb.2023.03.001.

[13] Strother, P.K., Brasier, M.D., Wacey, D., Timpe, L., Saunders, M., and Wellman, C.H. (2021). A possible billion-year-old holozoan with differentiated multicellularity. Current Biology, 31, 1–8.

[14] First Embryos: Chen, J-Y., Bottjer, D.J., Li, G., Hadfield, M.G., Gao, F., Cameron, A.R., Zhang, C-Y., Xian, D-C., Tafforeau, P., Liao, X., and Yin, Z-J. (2009). Complex embryos displaying bilaterian characters from Precambrian Doushantuo phosphate deposits, Weng’an, Guizhou, China. PNAS, 106(45), 19056-19060.

[15] Yin, Z., Vargas, K., Cunningham, K., Bengtson, S., Zhu, M., Marone, F., and Donoghue, P. (2019). The Early Ediacaran Caveasphaera Foreshadows the Evolutionary Origin of Animal-like Embryology. Current Biology, 29, 4307–4314.

[16] Sebe-Pedros, A., Degnan, B.M., and Ruiz-Trillo, I. (2017). The origin of Metazoa: a unicellular perspective. Nature Reviews Genetics, 18, 498–512.

[17] Xing, L., Niu, K., Ma, W., Zelenitsky, D.K., Yang, T-R., and Brusatte, S.L. (2021). An exquisitely preserved in-ovo theropod dinosaur embryo sheds light on avian-like prehatching postures. iScience, 103516.

[18] Miller, G. (2009). On the Origin of The Nervous System. Science, 325(5936), 24-26.

[19] Erwin, D.H. (2020). Origin of animal bodyplans: a view from the regulatory genome. Development, 147, dev182899. 

[20] Hartenstein, V. and Stollewerk, A. (2015). The evolution of early neurogenesis. Developmental Cell, 32, 390–407.

[21] Moroz, L.L. and Kohn, A.B. (2016). Independent origins of neurons and synapses: insights from ctenophores. Royal Society B, 371, 20150041.

[22] Moroz, L.L. (2021). Multiple Origins of Neurons From Secretory Cells. Frontiers in Cell and Developmental Biology, 9, 669087. 

[23] Ghysen, A. (2003). The origin and evolution of the nervous system. International Journal of Developmental Biology, 47(7-8), 555-562.

[24] Xian, X-F., Zhang, H-Q., Liu, Y-H., and Zhang, Y-N. (2019). Diverse radial symmetry among the Cambrian Fortunian fossil embryos from northern Sichuan and southern Shaanxi provinces, South China. Palaeoworld, 28(3), 225-233.  AND  Chang, S., Clausen, S., Zhang, L., Feng, Q., Steiner, M., Bottjer, D.J., Zhang, Y., Shi, M. (2018). New probable cnidarian fossils from the lower Cambrian of the Three Gorges area, South China, and their ecological implications. Palaeogeography, Palaeoclimatology, Palaeoecology, 505, 150-166.

[25] McGrath, C. (2022). Highlight: Unraveling the Origins of LUCA and LECA on the Tree of Life. Genome Biology and Evolution, 14(6), evac072.

[26] Erwin, D.H. (2021). Developmental capacity and the early evolution of animals. Journal of the Geological Society, 178(5), jgs2020-245.

[27] Archaea: Gribaldo, S. and Brochier-Armanet, C. (2006). The Origin and Evolution of Archaea: a state of the art. Royal Society B, 361, 1007-1022.

[28] Great Oxygenation Event: Knoll, A.H.and Nowak, M.A. (2017). The Timetable of Evolution. Science Advances, 3, e1603076.  AND   Erwin, D.H. (2015). Early metazoan life: divergence, environment and ecology. Royal Society B, 370, 20150036.

[29] Fungi-Animal Common Ancestor: Phelps, C., Gburcik, V., Suslova, E., Dudek, P., Forafonov, F., Bot, N., MacLean, M., Fagan, R.J., and Picard, D. (2006). Fungi and animals may share a common ancestor to nuclear receptors. PNAS, 103(18), 7077–7081.

[30] LUCA: Dodd, MS, Papineau, D, Grenne, T et al. (5 more authors) (2017). Evidence for early life in Earth’s oldest hydrothermal vent precipitates. Nature, 543 (7643). pp. 60-64.  AND  Hassenkam, T., Andersson, M., Dalby, K., MacKensie, D.M.A., and Rosing, M.T. (2017). Elements of Eoarchean life trapped in mineral inclusions. Nature, 548, 78–81.

[31] Tree of Life: Feng, D-F., Cho, G., and Doolittle, R.F. (1997). Determining divergence times with a protein clock: Update and reevaluation. PNAS, 94, 13028-13033.

The 500k Apex

I am pleased to report that as of the beginning of December 2022, Synthetic Daisies blog has reached 500,000 reads. The blog started over the 2008 Holiday season (14 years ago) and took about a year to garner significant readership. Over the years, Synthetic Daisies has participated in the Carnival of Evolution, several SciComm (Science Communication) initiatives, and charted the research progress of a number of initiatives (including the DevoWorm group).

Number of posts by year. Click to enlarge.

Although the number of time investment has declined in recent years, the posts have continued to accumulate reads. Synthetic Daisies has a Github repository and overlay site where some of the more popular posts are profiled. The Github repo also features associated code and other items from these posts. 

Number of readers over the course of 14 years. Click to enlarge.

More to report in another 200,000 to 300,000 reads!

Learning on Graphs (LoG) conference recap

 

The Learning on Graphs (LoG) conference took place from December 9-12 and featured a broad diversity of research on Graph Neural Networks (GNNs). GNNs [1] encompass a relatively new area of machine learning research which have a number of interesting connections to applied math and network science. The daily sessions (keynote talks and oral presentations), in addition to the seven workshop sessions, are available from the conference YouTube channel.

GNNs are a way to take data that yield graphical relationships in the real world and analyze then using the power of neural networks. While GNNs are specialized for problems that can be represented as a graph (discrete, interconnected systems), any problem with a set of complex geometric relationships is appropriate for GNNs. While the output of GNNs are typically embeddings (graph topologies embedded in the feature space), some problems require different approaches such as functions or more formal representations.

It is the analysis of these graphical relationships which make it a useful analytical approach. In all their forms, GNNs yield useful representations of graph data partly because they take into consideration the intrinsic symmetries of graphs, such as invariance and equivariance of graph topology with respect to a relabeling of the nodes [2]. Based on what was featured at LoG, GNNs had many potential applications in the biological arena, including precision medicine, drug discovery, and characterizing molecular systems (such as Stefan Gunnemann's (Technical University of Munich) talk in the Friday session).

GNNs can be evaluated using the isomorphism (or k-WL) test, which evaluates whether two graphs are isomorphic. Given that a graph can be drawn from the source data, the source data graph should be isomorphic with the output graph. The Weisfeiler-Lehman heuristic for graph isomorphism can be summarized in the 1-D case as the color refinement algorithm. A related issue in GNN research is algorithmic expressiveness. Expressivity is the breadth of ideas that can be represented and communicated using a particular type of representation. One current challenge of GNNs as they are applied to various problem domains is their ability to be functionally robust. One solution to this is by using GNNs as a generative model. Generating alternate graph representations allows us to use graphons [3], functions that capture different GNN topologies of the same type. The collection of graphs associated with a graphon can then be evaluated. Soledad Villar's (Johns Hopkins) presentation during the Sunday session featured an in-depth discussions of expressiveness and graphons as they relate to GNN performance.

GNNs can be combined with various analytical techniques traditionally used in complex network analysis. One of these involves the analysis of graphical models using tools from network science. These include the use of random graphs and stochastic block models to uncover the presence of topological structure and community formation, respectively. GNNs have ties to category theory as well. The cats.for.ai workshop (October 2022) featured applications of category theory to GNNs. In the Saturday session, Taco Cohen (Qualcomm AI) discussed how the techniques of category theory, monads in particular, can be applied to GNNs. GNNs can also form directed acyclic graphs (DAGs), which are amenable to causal models. 

GNNs are constructed using a series of inferential techniques. One technique discussed at LoG is message passing neural networks (MPNNs). Discrete forward passes from node to node (along edges) allow for approximation of the true, original network topology to be reconstructed. MPNN is a standard technique that lends itself to a wide variety of problem domains. The MPNN approach [4] can be extended to directed multigraphs and other types of graphs that capture complex systems, but can suffer shortcomings such as over-smoothing, over-squashing and under-reaching. While message passing has been the standard in the GNN field, continuous methods using approaches inspired by differential geometry and algebraic topology might serve as powerful alternatives [5]. Aside from approximations of real-world networks and graph-like structures, we can also think of GNN outputs in terms of time (capturing delays) and space (capturing translations). GNNs are also well-suited to mapping problems from algorithmic domains, in particular dynamic programming [6].

GNNs are particularly useful for task-specific architectures. The DevoWorm group’s D-GNN work (DevoGraph) is an example of this, being specialized for embryogenetic image processing or capturing biological growth and differentiation processes. But GNNs can also engage in transfer learning, which is the transfer of learned information from one context to another. Successful graph transfer learning is characterized by the reproduction of a graph of a similar but different size, or problems that require changes in network size over time.

From "Do we need deep graph neural networks?" by Michael Bronstein, Towards Data Science, July 20, 2020.

Workshops

Several of the workshops were particularly interesting with respect to some of the points mentioned above. There were also a number of outstanding oral presentations and posters not discussed here, but are worth checking out in the daily session recordings or on OpenReview.

Neural Algorithmic Reasoning (video). GNNs serve as excellent processors (neural networks in latent space) that can be aligned with more traditional algorithms [7]. This recasts many optimization problems as neural representation learning, particularly in cases where optimization algorithms do not represent the system being analyzed in a realistic manner.

Expressive GNNs (video). This tutorial covers a range of techniques that can be used to increase the expressivity of GNNs. Borrowing from areas such as topological data analysis and group theory, there is great potential for a variety of highly effective strategies for improving GNN architectures for a host of problems.

Graph Rewiring (video, web). Graph rewiring is presented as a way to overcome the limitations of the MPNN approach. Rewiring is based on the reconstruction of graph edges from iterative adaptive sampling of the input data. There are a number of different techniques that allow us to evaluate edge relevance using techniques such as diffusion and spectral approaches.

GNNs on TensorFlow (video). This tutorial introduces nascent modelers to implementing their own GNN models in the open-source TF-GNN framework. The tutorial uses heterogeneous input data to show how to implement the GNN and deal with missing label and edge information.

References

[1] Sanchez-Lengeling, B., Reif, E., Pearce, A., and Wiltschko, A.B. (2021). A Gentle Introduction to Graph Neural Networks. Distill, doi:10.23915/distill.00033.

[2] Chen, Z., Villar, S., Chen, L., and Bruna, J. (2019). On the equivalence between graph isomorphism testing and function approximation with GNNs. Proceedings of Neural Information Processing Systems, 32.

[3] Ruiz, L., Chamon, L.F.O., and Ribeiro, A. (2020). Graphon Neural Networks and the Transferability of Graph Neural Networks. arXiv, 2006.03548.

[4] Heydari, S. and Livi, L. (2022). Message Passing Neural Networks for Hypergraphs. arXiv, 2203. 16995.

[5] Bronstein, M. (2022). Beyond Message Passing: a Physics-Inspired Paradigm for Graph Neural Networks. The Gradient, May 7.

[6] Dudzik, A. and Velickovic, P. (2022). Graph Neural Networks are Dynamic Programmers. arXiv, 2203.15544.

[7] Velickovic, P. and Blundell, C. (2021). Neural Algorithmic Reasoning. arXiv, 2105.02761.