A joint graph inference case study: the C. elegans chemical and electrical connectomes

ABSTRACT

We investigate joint graph inference for the chemical and electrical connectomes of the Caenorhabditis elegans roundworm. The C. elegans connectomes consist of ${\displaystyle 253}$ non-isolated neurons with known functional attributes, and there are two types of synaptic connectomes, resulting in a pair of graphs. We formulate our joint graph inference from the perspectives of seeded graph matching and joint vertex classification. Our results suggest that connectomic inference should proceed in the joint space of the two connectomes, which has significant neuroscientific implications.

KEYWORDS:

• fusion inference
• joint graph inference
• joint vertex classification
• neural connectome
• omnibus embedding
• seeded graph matching

Introduction

The Caenorhabditis elegans (C. elegans) is a non-parasitic, transparent roundworm approximately one millimeter in length. The majority of C. elegans are hermaphrodites.¹ first described the worm in 1900 and named it Rhabditis elegans. It was later categorized under the subgenus Caenorhabditis by Osche,² and then, in 1955, raised to the generic status by Ellsworth Dougherty, to whom much of the recognition for choosing C. elegans as a model system in genetics is attributed.³ The long name of this nematode mixes Greek and Latin, where Caeno means recent, rhabditis means rod-like, and elegans means elegant.

Research on C. elegans rose to prominence after the nematode was adopted as a model organism: an easy-to-maintain non-human species widely studied, so that discoveries on this model organism might offer insights for the functionality of other organisms. The discoveries of caspases,⁴ RNA interference,⁵ and microRNAs⁶ are among some of the notable research using C. elegans.

Connectomes, the mapping of neural connections within the nervous system of an organism, provide a comprehensive structural characterization of the neural network architecture, and represent an essential foundation for basic neurobiological research. Applications based on the discovery of the connectome patterns and the identification of neurons based on their connectivity structure give rise to significant challenges and promise important impact on neurobiology. Recently there has been an increasing interest in the network properties of C. elegans connectomes. The hermaphrodite C. elegans is the only organism with a fully constructed connectome,⁷ and has one of the most highly studied nervous systems.

Studies on the C. elegans connectomes traditionally focus on utilizing one single connectome alone,^8-11 although there are many connectomes available. Notably, Varshney et al.⁸ discovered structural properties of the C. elegans connectomes via analyzing the connectomes' graph statistics. Pavlovic et al.⁹ estimated the community structure of the connectomes, and their findings are compatible with known biological information on the C. elegans nervous system.

Our new statistical approach of joint graph inference looks instead at jointly utilizing the paired chemical and electrical connectomes of the hermaphrodite C. elegans. We formulate our inference framework from the perspectives of seeded graph matching and joint vertex classification, which we will explain in Section 2. This framework gives a way to examine the structural similarity preserved across multiple connectomes within species, and make quantitative comparisons between joint connectome analysis and single connectome analysis. We found that the optimal inference for the information-processing properties of the connectome should proceed in the joint space of the C. elegans connectomes, and using the joint connectomes predicts neuron attributes more accurately than using either connectome alone.

The hermaphrodite C. elegans connectomes consist of ${\displaystyle 302}$ labeled neurons for each organism. The C. elegans somatic nervous system has 279 neurons connecting to each other across synapses. There are many possible classifications of synaptic types. Here we consider two types of synaptic connections among these neurons: chemical synapses and electrical junction potentials. These two types of connectivity result in two synaptic connectomes consisting of the same set of neurons.

We represent the connectomes as graphs. A graph is a representation of a collection of interacting objects. The objects are referred to as nodes or vertices. The interactions are referred to edges or links. In a connectome, the vertices represent neurons, and the edges represent synapses. Mathematically, a graph ${\displaystyle G=(V, E)}$ consists of a set of vertices or nodes ${\displaystyle V=[n]:=\left\{1,2,\mathrm{\dots },n\right\}}$ and a set of edges ${\displaystyle E\subset }$. If the graph is undirected and non-loopy, then the edge set${\displaystyle E=\left(\begin{array}{l}V\\ 2\end{array}\right)=\left(\begin{array}{l}[n]\\ 2\end{array}\right)}$, where ${\displaystyle \left(\begin{array}{l}[n]\\ 2\end{array}\right)}$ denotes all (unordered) pairs ${\displaystyle \{v_i, v_j\}}$ for all ${\displaystyle v_i, v_j\in V}$ and ${\displaystyle v_i\ne v_j}$. If the graph is directed and non-loopy, there are ${\displaystyle n(n-1)}$ possible edges, and we can represent them as ordered pairs. In this work, we assume the graphs are undirected, weighted, and non-loopy. The adjacency matrix ${\displaystyle A}$ of ${\displaystyle G}$ is the ${\displaystyle n}$ -by- ${\displaystyle n}$ matrix in which each entry ${\displaystyle A_{ij}}$ denotes the edge existence between vertex ${\displaystyle i}$ and ${\displaystyle j:A_{ij}=1}$ if an edge is present, and ${\displaystyle A_{ij}=0}$ if an edge is absent. The adjacency matrix is symmetric, binary and hollow, i.e., the diagonals are all zeros.

For the hermaphrodite C. elegans worm, the chemical connectome ${\displaystyle G_c}$ is weighted and directed. The electrical gap junctional connectome ${\displaystyle G_g}$ is weighted and undirected. This is consistent with an important characteristic of electrical synapses – they are bidirectional.¹² The weighting for both ${\displaystyle G_c}$ and ${\displaystyle G_g}$ is the number of synaptic connections between a pair of non-identical neurons. The chemical connectome ${\displaystyle G_c}$ has ${\displaystyle 3}$ loops and no isolated vertices, while the electrical gap junctional connectome ${\displaystyle G_g}$ has no loops and 26 isolated vertices. Both connectomes are sparse. The chemical connectome ${\displaystyle G_c}$ has 2194 directed edges out of ${\displaystyle 279\cdot 278}$ possible ordered neuron pairs, resulting in a sparsity level of approximately ${\displaystyle 2.8\%}$. The electrical gap junctional connecome ${\displaystyle G_g}$ has 514 undirected edges out of ${\displaystyle (\begin{array}{l}279\\ 2\end{array})}$ possible unordered neuron pairs, resulting in a sparsity level of approximately ${\displaystyle 1.3\%}$.

In our analysis, we are interested in the ${\displaystyle 279-26=253}$ non-isolated neurons in the hermaphrodite C. elegans somatic nervous system. The non-isolated neurons have synaptic connections with at least one other neuron. Each of these ${\displaystyle 253}$ neurons can be classified in a number of ways, including into 3 non-overlapping connectivity based types: sensory neurons (${\displaystyle 27.96\%}$), interneurons (${\displaystyle 29.75\%}$) and motor neurons (${\displaystyle 42.29\%}$). Here we will work with binary, symmetric and hollow adjacency matrices of the neural connectomes throughout. We symmetrize ${\displaystyle A}$ by ${\displaystyle A\leftarrow A+A^T}$, then binarize ${\displaystyle A}$ by thresholding the positive entries of ${\displaystyle A}$ to be 1 and 0 otherwise, and finally set the diagonal entries of ${\displaystyle A}$ to be zero. Indeed, we focus on the existence of synaptic connectomes, and the occurrence of loops is low (3 loops in ${\displaystyle G_c}$ and none in ${\displaystyle G_g}$) so we can ignore it.

The pair of the neural connectomes are visualized in Figure 1. In the chemical connectome ${\displaystyle G_{\text{c}}}$, the interneurons are heavily connected to the sensory neurons. The sensory neurons are connected more frequently to the motor neurons and interneurons than among themselves. Moreover, the sensory neurons are much more frequently connected to the interneurons than to the motor neurons. This is consistent with the typical information flow from sensory neurons to interneurons and then to motor neurons. In the electrical gap junction potential connectome ${\displaystyle G_{\text{g}}}$, the motor neurons are heavily connected to the interneurons. The sensory neurons are connected more frequently to the motor neurons and interneurons than among themselves. The connectome dataset is accessible at http://openconnecto.me/herm-c-elegans. Figure 2 presents the adjacency matrices of the paired C. elegans connectomes.

Figure 1. The pair of C. elegans neural connectomes visualized as graphs. Red nodes correspond to motor neurons, green nodes correspond to interneurons, and blue nodes correspond to sensory neurons. (Left) The chemical connectome ${\displaystyle G_{\text{c}}}$. (Right) The electrical gap junctional connectome ${\displaystyle G_{\text{g}}}$. Both synaptic connectomes are sparse, while ${\displaystyle G_{\text{g}}}$ is much sparser than ${\displaystyle G_{\text{c}}}$. A similar connectivity pattern is seen across both connectomes.

Figure 2. (Left): The adjacency matrix ${\displaystyle A_{\text{c}}}$ of ${\displaystyle G_{\text{c}}}$ sorted according to the neuron types. (Right): The adjacency matrix ${\displaystyle A_{\text{g}}}$ of ${\displaystyle G_{\text{g}}}$ sorted according to the neuron types. The red block corresponds to the connectivity among the motor neurons, the green block corresponds to the connectivity among the interneurons, and the blue block corresponds to the connectivity among the sensory neurons.

Results and discussion

Finding the correspondence between the chemical and the electrical connectomes

We apply seeded graph matching on the paired C. elegans neural connectomes, and discover the underlying structure preserved across the chemical and the electrical connectomes.¹³ Figure 3 presents the errorbar plot of the seeded graph matching accuracy ${\displaystyle \delta (m)}$, plotted in black, against the number of seeds ${\displaystyle m\in \{0, 20, 40,\dots , 180\}}$. For each selected number of seeds ${\displaystyle m}$, we randomly and independently select 100 seeding sets ${\displaystyle S_1}$. For each seeding set ${\displaystyle S_1}$ at a given number of seeds ${\displaystyle m}$, we apply the state-of-the-art seeded graph matching algorithm.¹³ The mean accuracy ${\displaystyle \delta (m)}$ is obtained by averaging the accuracies over the ${\displaystyle 100}$ Monte Carlo replicates at each ${\displaystyle m}$. As ${\displaystyle m}$ increases, the matching accuracy improves. This is expected, because more seeds give more information, making the SGM problem less difficult. The chance accuracy, plotted in brown dashed line, at each ${\displaystyle m}$ is ${\displaystyle \frac{1}{n-m}}$, which does not increase significantly as ${\displaystyle m}$ increases.

Figure 3. Seeded graph matching on the C. elegans neural connectomes. For each selected number of seeds ${\displaystyle m\in \{0, 20, 40,\dots , 180\}}$, we randomly select ${\displaystyle 100}$ independent seeding sets ${\displaystyle S_1}$ and apply SGM for each Monte Carlo replicate. The SGM mean accuracy ${\displaystyle \delta (m)}$, plotted in black, is obtained by averaging the accuracies over the ${\displaystyle 100}$ Monte Carlo replicates. As the number of seeds ${\displaystyle m}$ increases, the accuracy increases. The chance accuracy, plotted in brown dashed line, is much lower than the SGM accuracy. This suggests that a significant similarity exists between the two types of synapse connections. The SGM performance on the C. elegans neural connectome is much more significant than chance but less than a perfect matching, indicating the optimal inference must proceed in the joint space of both neural connectomes.

We note two significant neurological implications based on our graph matching result. First, SGM on the pair of connectomes indicate that the chemical and the electrical connectomes have statistically significant similar connectivity structure. The second significant implication is: If the performance of SGM on the chemical and the electrical connections were perfect, then one could consider just one (either one) of the paired neural connectomes without losing much information. If performance of SGM on the chemical and the electrical connections were no better than random vertex alignment, then it suggests that there is no structure similarity across the two connectomes, and this further suggests that analysis on the connectomes should proceed separately and individually. In fact, the seeded graph matching result on the C. elegans neural connectome is much more significant than chance but less than a perfect matching. This demonstrates that the optimal inference should be performed in the joint space of the chemical and the electrical connectomes. This discovery is noted in Lyzinski et al.¹⁴

Predicting neuron types from the joint space of the chemical and the electrical connectomes

The result of SGM on the C. elegans neural connectomes demonstrates the advantage of inference in the joint space of the neural connectomes, and provides a statistical motivation to apply our proposed joint vertex classification approach. Furthermore, the neuroscientific motivation of applying joint vertex classification stems from illustrating a methodological framework to understand the coexistence and significance of chemical and electrical synaptic connectomes.

We apply joint vertex classification and single vertex classification on the paired C. elegans neural connectomes, and compare the classification performance. The validation is done via leave-one-out cross validation. Here we do not investigate which embedding dimension ${\displaystyle d}$ or classifier are optimal for our classification task, and we choose support vector machine classifier with radial basis¹⁵ for the classification step. The paired plots in Figure 4 present the misclassification errors against the embedding dimensions ${\displaystyle d\in \{2, 5, 8,\dots , 116, 119\}}$. For the chemical connectome, the joint vertex classification (plotted in magenta) outperforms the single vertex classification (plotted in black) at all the considered embedding dimensions. For the electrical connectome, the joint vertex classification (plotted in magenta) outperforms the single vertex classification (plotted in black) at most of the considered embedding dimensions, especially larger valued embedding dimensions.

Figure 4. Classification performance of joint and single vertex classification. (Left) Classification on the chemical connectome ${\displaystyle A_c}$. For all embedding dimensions ${\displaystyle d\in \{2, 5, 8,\dots , 116, 119\}}$, the error rate of joint vertex classification, plotted in magenta, is lower than the single vertex classification, plotted in black. (Right) Classification on the electrical gap junctional connectome ${\displaystyle A_g}$. For most of the embedding dimensions especially with larger values, the error rate of joint vertex classification, plotted in magenta, is lower than the single vertex classification, plotted in black. Our classification result indicates that using information from the joint space of the neural connectomes improves classification performance.

The superior performance of the joint vertex classification over the single vertex classification has an important neuroscientific implication. In many animals, the chemical synapses co-exist with the electrical synapses. Modern understanding of coexistence of chemical and electrical synaptic connectomes suggest such a coexistence has physiological significance. We discover that using both chemical and electrical connectomes jointly generates better classification performance than using one connectome alone. This may serve as a first step toward providing a methodological and quantitative approach toward understanding the coexistent significance.

Summary and discussion

The paired Caenorhabditis elegans connectomes have become a fascinating data set for motivating a better understanding of the nervous connectivity systems. We have presented the unique statistical approach of joint graph inference – inference in the joint graph space – to study the worm's connectomes. Utilizing jointly the chemical and the electrical connectomes, we discover statistically significant similarity preserved across the two synaptic connectome structures. Our result of seeded graph matching indicates that the optimal inference on the information-processing properties of the connectomes must proceed in the joint space of the paired graphs.

The development of seeded graph matching provides a strong statistical motivation for joint vertex classification, where we predict neuron types in the joint space of the paired connectomes. Joint vertex classification outperforms the single vertex classification against all embedding dimensions for our different choices of dissimilarity measures. Fusion inference using both the chemical and the electrical connectomes produces more accurate results than using one (either one) connectome alone, and enhances our understanding of the C. elegans connectomes. The chemical and the electrical synapses are known to coexist in most organisms. Our proposed joint vertex classification provides a methodological and quantitative framework for understanding the significance of the coexistence of the chemical and the electrical synapses. Further development of joint graph inference is a topic of ongoing investigation in both neuroscience and statistics.

Methods

We consider an inference framework in the joint space of the C. elegans neural connectomes, which we refer to as joint graph inference. We focus on two aspects of joint graph inference: seeded graph matching and joint vertex classification.

Seeded graph matching

The problem of seeded graph matching (SGM) is a subproblem of the graph matching (GM) problem, which has wide applications in object recognition,^16,17 image analysis,¹⁸ computer vision,^19,20 and neuroscience.^21,22,23]. Given two graphs, ${\displaystyle G_1=(V_1, E_1)}$ and ${\displaystyle G_2=(V_2, E_2)}$ with respective adjacency matrices ${\displaystyle A_1}$ and ${\displaystyle A_2}$, and ${\displaystyle \left|V_1\right|=\left|V_2\right|=n}$, the GM problem seeks a bijection ${\displaystyle \phi }$ between the vertex sets that minimizes edge disagreements.^13,24 The graph matching problem is NP-hard.²⁵ It is not known whether any graph matching algorithm is efficient, and it is suspected that none exist. For a comprehensive survey on the graph matching problem, see Conte et al.²⁶ and Vogelstein et al.²² The intuitive idea of graph matching is seen in Figure 5.

Figure 5. (A)depiction of graph matching. Given two graphs ${\displaystyle G_1}$ and ${\displaystyle G_2}$, graph matching seeks an alignment (represented in the green lines) between the vertices across 2 graphs.

The seeded graph matching (SGM) problem employs additional constraint, where a partial correspondence between the vertices is known a priori. Those vertices are called “seeds.” Addition of seeds slightly changes the graph matching algorithm, and improves the graph matching performance.¹³ Let ${\displaystyle S_1\subset V_1}$ and ${\displaystyle S_2\subset V_2}$ be two subsets of the vertex sets, and suppose ${\displaystyle S_1=S_2=\{1, 2,\dots , m\}}$. The elements of ${\displaystyle S_1}$ and ${\displaystyle S_2}$ are called seeds, and the remaining ${\displaystyle n-m}$ vertices are non-seeds. In the SGM problem, one seeks a a bijection, with constraint on ${\displaystyle \phi }$ such that ${\displaystyle {\phi }_{S_1}={\phi }_{S_2}}$, to minimize the number of induced edge disagreements.

The SGM problem, as a subproblem of GM, is NP-hard. We seek an approximated SGM solution that is computationally efficient. The performance of SGM solutions is measured by the matching accuracy ${\displaystyle \delta (m)}$, defined as the number of correctly matched non-seeded vertices divided by the total number of non-seeds ${\displaystyle n-m}$. When the number of seeds ${\displaystyle m}$ is given, the remaining ${\displaystyle n-m}$ vertices need to be matched. Hence, the chance matching accuracy is ${\displaystyle \frac{1}{n-m}}$, and this accuracy increases as ${\displaystyle m}$ increases. For larger values of ${\displaystyle m}$, more information on the partial correspondence between the vertices is available, and thus the SGM matching accuracy becomes higher. In this work, we apply the state-of-the-art SGM algorithm developed by Fishkind et al.^[13], seek the correspondence between the two types of neuron connectomes, and study the joint structure of the worm neural connectomes.

Joint vertex classification

When we observe the adjacency matrix ${\displaystyle A\in {\left\{0, 1\right\}}^{n\times n}}$ on ${\displaystyle n}$ vertices and the class labels ${\displaystyle {\left\{Y_i\right\}}_{i=1}^{n-1}}$ associated with the first ${\displaystyle (n-1)}$ training vertices, the task of vertex classification is to predict the label ${\displaystyle Y}$ of the test vertex ${\displaystyle v}$. In this case study, the class labels are the neuron types: motor neurons, interneurons and sensory neurons. In this work, we assume the correspondence between the vertex sets across the two graphs is known. Given two graphs ${\displaystyle G_1=(V, E_1)}$ and ${\displaystyle G_2=(V, E_2)}$ where ${\displaystyle V=\{v_1,\dots , v_{n-1}, v\}}$, and given the class labels ${\displaystyle {\left\{Y_i\right\}}_{i=1}^{n-1}}$ associated with the first ${\displaystyle (n-1)}$ training vertices, the task of joint vertex classification predicts the label of a test vertex ${\displaystyle v}$ using information jointly from ${\displaystyle G_1}$ and ${\displaystyle G_2}$.

Fusion inference merges information on multiple disparate data sources in order to obtain more accurate inference than using only single source. Our joint vertex classification consists of two main steps: first, a fusion information technique, namely the omnibus embedding methodology by Priebe et al.²⁷; and secondly, the inferential task of vertex classification.

The step of omnibus embedding proceeds as follows. Given $G_1$ and ${\displaystyle G_2}$, we construct an omnibus matrix $M=(\begin{array}{ll}{A}_1\hfill & \Lambda \hfill \\ \Lambda \hfill & A_2\hfill \end{array})\in {ℝ}^{2n\times 2n}$, where ${\displaystyle A_1}$ and ${\displaystyle A_2}$ are the adjacency matrices of ${\displaystyle G_1}$ and ${\displaystyle G_2}$ respectively, and the off-diagonal block is ${\displaystyle \Lambda =\frac{1}{2}(A_1+A_2)}$. We consider adjacency spectral embedding²⁸ of ${\displaystyle M}$ as ${\displaystyle 2n}$ points into ${\displaystyle {ℝ}^d}$. Let ${\displaystyle U=\left[\begin{array}{l}{U}_1\hfill \\ U_2\hfill \end{array}\right]\in {ℝ}^{2n\times d}}$ denote the resulted joint embedding, where ${\displaystyle U_1\in {ℝ}^{n\times d}}$ is the joint embedding corresponding to ${\displaystyle G_1}$, and ${\displaystyle U_2\in {ℝ}^{n\times d}}$ to ${\displaystyle G_2}$. Our inference task is vertex classification. Let ${\displaystyle T_{n-1}:=U_1([n-1],:)\in {ℝ}^{(n-1)\times d}}$ denote the training set containing the first ${\displaystyle n-1}$ vertices. We train a classifier on ${\displaystyle T_{n-1}}$, and classify the test vertex ${\displaystyle v}$. A depiction of the joint vertex classification procedure is seen in Figure 6.

Figure 6. (A)depiction of joint vertex classification. An illustration of joint vertex classification, which embeds the joint adjacency matrix – the omnibus matrix, and classifies on the embedded space.

We demonstrate that fusing both pairs of the neural connectomes generates more accurate inference results than using a single source of connectome alone. We consider single vertex classification for comparison, which embeds the adjacency matrix ${\displaystyle A_1}$ to ${\displaystyle {ℝ}^d}$ via adjacency spectral embedding, and classifies on the embedded space. A depiction of the single vertex classification procedure is seen in Figure 7.

Figure 7. (A)depiction of single vertex classification. An illustration of single vertex classification, which embeds one single adjacency matrix, and classifies on the embedded space.

Disclosure of potential conflicts of interest

No potential conflicts of interest were disclosed.

Funding

This work is partially supported by a National Security Science and Engineering Faculty Fellowship (NSSEFF), Johns Hopkins University Human Language Technology Center of Excellence (JHU HLT COE), the XDATA program of the Defense Advanced Research Projects Agency (DARPA) administered through Air Force Research Laboratory contract FA8750-12-2-0303, the NSF BRAIN Early Concept Grants for Exploratory Research (EAGER) award DBI-1451081, and Acheson J. Duncan Fund for the Advancement of Research in Statistics.