Saturday Morning NeuroSim Discussion Thread: Physical Computing

 

From the “Macy Conference Redux” feature form our July 1 meeting

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.

One recent lecture/discussion thread is on Physical Computation. Our approach to the topic begins with the debate around the role of computation in Cognitive Science and the Neurosciences. And so we begin in Week 1 with a discussion of the connections between computation, information processing, and the brain, largely focusing on the work of Gualtiero Piccinini and Corey Maley. A starting point for this session is their Stanford Encyclopedia of Philosophy article on “Computation in Physical Systems”. Many current assumptions about computation in the brain stem from the Church-Turing thesis, which often leads to a poor fit between model and experiment. Piccinini and Maley propose that the Church-Turing-Deutsch thesis is preferable when talking about systems that perform non-digital computations. Amanda Nelson pointed out the it makes sese to think of evolved biological systems (brains) as instances of analogue computers. Another interesting point from the session is the distinction between the digital (Von Neumann) computers and alternatives such as “physical” or “analog” computation, which would be picked up on in the next session.

Physical Computation Session I from June 24 (roughly one hour in length).

The second session focused on physical computation, and led us to discuss the idea of pancomputationalism. While pancomputationalism is the fundamental assumption behind the phrase “the brain is a computer” [1], we we also introduced to pancomputationalism in ferrofluidic systems and mycelial networks. We discussed the works of Richard Feynman (Feynman Lectures on Computation) and Edward Fredkin (Digital Physics), which helped us form an epistemic framework for computation in nature [2]. We also discussed Andy Adamatsky’s work on unconventional computation, particularly his work on Reaction-Diffusion (R-D) Automata, that while discrete in nature has connections to excitable (e.g neural) systems via the Fitzhugh-Nagumo model.

Physical Computation Session II from July 1 (roughly one hour in length)

After taking a break from the topic, our July 15 meeting featured an alternative viewpoint on pancomputationalism. This was made manifest in a shorter discussion on physical computation, with views from Tomasso Toffoli and Stephen Wolfram. We covered Toffoli’s paper “Action, or the funcgability of computation”, which connects physical entropy, information, action, and the amount of computation performed by a system. This paper is of great interest to the group in light of our work and discussions on 4E (embodied, embedded, enactive, and extended) cognition [3]. Toffoli makes some provocative arguments herein, including the notion of computation as “units of action”. A concrete example of this is a 10-speed bicycle, which is not only not a conventional computer, but also has linkages to perception and action. Amanda Nelson found the notion of transformation from one unit into another particularly salient to the distinction between analogue and digital computation. The physical basis of all forms of computation can also be better defined by revisiting “A New Kind of Science” [4], in which Wolfram sketches out the essential components and analogies of a computational system with a physical substrate. We can then compare some of the more abstract aspects of a physical computer with neural systems. This is particularly relevant to engineered systems that include select components of biological networks.

Physical Computation Session III from July 15 (about 15 minutes in length)

The next session followed up on computation in natural systems as well as Wolfram’s notion of universality, particularly in terms of computational models. In particular, Wolfram argues that cellular automata models can characterize universality, which is related to pancomputationalism. Universality suggests that any one computational model can capture system behavior that can be applied across a wide variety of domains. In this sense, context is not important. Rule 30 produces an output that resembles pattern formation in biological phenotypes (the shell of snail species Conus textile), but can also be used as a pseudo-random number generator [5]. In “A Framework for Universality in Physics, Computer Science, and Beyond”, this perspective is extended to understand the connections between computation defined by the Turing machine and a class of model called Spin Models. This provides a framework for universality that is useful form defining computation across the various levels of neural systems, but also gives rise to understanding what is uncomputable. This sessions natural system examples featured computation among bacterial colonies embedded in a colloidal substrate along with computation in granular matter itself. The latter is an example of non-silicon based polycomputation [6].

Physical Computation Session IV from July 22 (about 12 minutes in length).

After talking a more extended break from the topic, we returned to this discussion four weeks later (August 19). Our sixth (VI) session occurred in our August 19 meeting, and covered three topics: physical computation and topology, morphological computation, and RNA computing/Molecular Biology as universal computer.

We have discussed category theory before in our discussions on Symbolic Systems and Causality. In this section, we revisited the role of category theory, but this time with reference to Physical Computation. John Carlos Baez and Mike Stay give a tour of category theory’s role in computation via topology. The idea is that category theory forms analogies with computation, which can be expressed on a topological surface/space.

Computable Topology, Wikipedia.

Baez, J. and Stay, M. (2009). Physics, Topology, Logic and Computation: A Rosetta Stone. arXiv, 0903.0340.

Mapping category theory operators to a topological description.

We aslo covered the role of Morphological Computation by reviewing three papers on this form of physical computation that intersects with digital computational representations. Morphological Computation is the role of the body in the notion of “cognition is computation”. One idea that is critiqued with in these papers is offloading from the brain to the body. Offloading is moving computational capacity from the central nervous system to the periphery. If you grab a ball with your hand, you recognize and send commands to grasp the ball, but you must grasp and otherwise manipulate the object to fully compute the object. Thus, this capacity is said to be offloaded to the hand or peripheral nervous system.

Interestingly, offloading and embodiment are integral parts of 4E (Embodied, Embedded, Enactive, and Externalized) Cognition, which itself critiques the brain as computation idea. But as an analytical tool, morphological computation is much more utilitarian than Cognitive Science theory, and is concerned with how the robotic bodies and other mechanical systems interact with an intelligent controller. In non-embodied robotics, body dynamics is treated as noise. But in morphological computation, body dynamics play an integral role in the intelligent system and contribute to a dynamical system.

Muller, V.C. and Hoffmann, M. (2017). What Is Morphological Computation? On How the Body Contributes to Cognition and Control. Artificial Life, 23, 1–24.

Fuchslin, R.M., Dzyakanchuk, A., Flumini, D., Hauser, H., Hunt, K.J., Luchsinger, R.H., Reller, B., Scheidegger, S., and Walker, R. (2013). Morphological Computation and Morphological Control: Steps Toward a Formal Theory and Applications. Artificial Life, 19, 9–34.

Milkowski, M. (2018). Morphological Computation: Nothing but Physical Computation. Entropy, 20, 942.

The three insights from our morphological computational discussion.

While these papers do not get too deeply into the role of pancomputation in Morphological Computation, it is implicitly stated and plays a central role in our last topic: RNA computing and Molecular Biology. For more information, see this talk on YouTube and the paper below. Basically, while the pancomputationalism perspective is missing from biology, the structure and potential function of DNA and RNA provide a route to phycial computation.

Akhlaghpour, H. (2022). An RNA-based theory of natural universal computation. Journal of Theoretical Biology, 537, 110984.

Bringing pancomputationalism into biology? What is its value?

Thanks to Morgan Hough for joining us from Hawaii (4:00 am!) on August 19.

References

[1] Richards, B.A. and Lillicrap, T.P. (2022). The Brain-Computer Metaphor Debate Is Useless: A Matter of Semantics. Frontiers in Computational Science, 4, 810358.

Should we just simply “shut up and calculate”, or debate some more?

[2] Fredkin, E. (2003). An Introduction to Digital Philosophy. International Journal of Theoretical Physics, 42(2), 189.

This work is the Rosetta Stone for many comparisons between modern AI systems and human-like intelligence, at least in terms of computation.

[3] Newen, A., DeBruin, L., and Gallagher, S. (2018). The Oxford Handbook of 4E Cognition. Oxford University Press.

[4] Wolfram, S. (2002). A New Kind of Science. Wolfram Media.

This is a link to the 20th Anniversary edition, with a full set of Cellular Automata rules, defined by number.

[5] Zenil, H. (2016). How can I generate random numbers using the Rule 30 Cellular Automaton? Quora post.

[6] Bongard, J. and Levin, M. (2023). There’s Plenty of Room Right Here: Biological Systems as Evolved, Overloaded, Multi-Scale Machines. Biomimetics, 8(1), 110.

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.