Connectivity Matrix Seriation via Relaxation

Volume electron microscopy together with computer-based image analysis are yielding neural circuit diagrams of ever larger regions of the brain. These datasets are usually represented in a cell-to-cell connectivity matrix and contain important information about prevalent circuit motifs allowing to directly test various theories on the computation in that brain structure. Of particular interest are the detection of cell assemblies and the quantification of feedback, which can profoundly change circuit properties. While the ordering of cells along the rows and columns doesn’t change the connectivity, it can make special connectivity patterns recognizable. For example, ordering the cells along the flow of information, feedback and feedforward connections are segregated above and below the main matrix diagonal, respectively. Different algorithms are used to renumber matrices such as to minimize a given cost function, but either their performance becomes unsatisfying at a given size of the circuit or the CPU time needed to compute them scales in an unfavorable way with increasing number of neurons. Based on previous ideas, I describe an algorithm which is effective in matrix reordering with respect to both its performance as well as to its scaling in computing time. Rather than trying to reorder the matrix in discrete steps, the algorithm transiently relaxes the integer program by assigning a real-valued parameter to each cell describing its location on a continuous axis (‘smooth-index’) and finds the parameter set that minimizes the cost. I find that the smooth-index algorithm outperforms all algorithms I compared it to, including those based on topological sorting.Author summary: Connectomic data provide researchers with neural circuit diagrams of ever larger regions of the brain. These datasets are usually represented in a cell-to-cell connectivity matrix and contain important information about prevalent circuit motifs. Such motifs, however, only become visible if the connectivity matrix is reordered appropriately. For example, ordering the cells along the flow of information, feedback and feedforward connections are segregated above and below the main matrix diagonal, respectively. While most previous approaches rely on topological sorting, my method relaxes the discrete vertex indices to real numbers (‘smooth-index’) along independent parameter axes and defines a differentiable cost function, thus, allowing gradient-based algorithms to find a minimum. The parameter set at this minimum is then re-discretized to reorder the connectivity matrix accordingly. I find my method to scale favorably with the circuit size and to outperform all algorithms I compared it to.