Connectomics, a subfield of neuroscience, reconstructs structural and functional brain maps at synapse-level resolution. These complex spatial maps consist of tree-like neurons interconnected by synapses. Motif analysis is a widely used method for identifying recurring subgraph patterns in connectomes. These motifs, thus, potentially represent fundamental units of information processing. However, existing computational tools often oversimplify neurons as mere nodes in a graph, disregarding their intricate morphologies. In this paper, we introduce MoMo, a novel interactive visualization framework for analyzing neuron morphology-aware motifs in large connectome graphs. First, we propose an advanced graph data structure that integrates both neuronal morphology and synaptic connectivity. This enables highly efficient, parallel subgraph isomorphism searches, allowing for interactive morphological motif queries. Second, we develop a sketch-based interface that facilitates the intuitive exploration of morphology-based motifs within our new data structure. Users can conduct interactive motif searches on state-of-the-art connectomes and visualize results as interactive 3D renderings. We present a detailed goal and task analysis for motif exploration in connectomes, incorporating neuron morphology. Finally, we evaluate MoMo through case studies with four domain experts, who asses the tool's usefulness and effectiveness in motif exploration, and relevance to real-world neuroscience research. The source code for MoMo is available here.

Finding connected components in a graph is a fundamental problem in graph analysis. In this work, we present a novel minimum-mapping based Contour algorithm to efficiently solve the connectivity problem. We prove that the Contour algorithm with two or higher order operators can identify all connected components of an undirected graph within$\mathcal{O} (\log d_{max})$iterations, with each iteration involving$\mathcal{O}(m)$work, where$d_{max}$represents the largest diameter among all components in the given graph, and$m$is the total number of edges in the graph. Importantly, each iteration is highly parallelizable, making use of the efficient minimum-mapping operator applied to all edges. To further enhance its practical performance, we optimize the Contour algorithm through asynchronous updates, early convergence checking, eliminating atomic operations, and choosing more efficient mapping operators. Our implementation of the Contour algorithm has been integrated into the open-source framework Arachne. Arachne extends Arkouda for large-scale interactive graph analytics, providing a Python API powered by the high-productivity parallel language Chapel. Experimental results on both real-world and synthetic graphs demonstrate the superior performance of our proposed Contour algorithm compared to state-of-the-art large-scale parallel algorithm FastSV and the fastest shared memory algorithm ConnectIt. On average, Contour achieves a speedup of 7.3x and 1.4x compared to FastSV and ConnectIt, respectively. All code for the Contour algorithm and the Arachne framework is publicly available on GitHub11https://githuh.comJBears-R-Us/arkouda-njit, ensuring transparency and reproducibility of our work.

In graph analytics, a truss is a cohesive subgraph based on the number of triangles supporting each edge. It is widely used for community detection applications such as social networks and security analysis, and the performance of truss analytics highly depends on its triangle counting method. This paper proposes a novel triangle counting kernel named Minimum Search (MS). Minimum Search can select two smaller adjacency lists out of three and uses fine-grained parallelism to improve the performance of triangle counting. Then, two basic algorithms, MS-based triangle counting, and MS-based support updating are developed. Based on the novel triangle counting kernel and the two basic algorithms above, three fundamental parallel truss analytics algorithms are designed and implemented to enable different kinds of graph truss analysis. These truss algorithms include an optimized K-Truss algorithm, a Max-Truss algorithm, and a Truss Decomposition algorithm. Moreover, all proposed algorithms have been implemented in the parallel language Chapel and integrated into an open-source framework, Arkouda. Through Arkouda, data scientists can efficiently con-duct graph analysis through an easy-to-use Python interface and handle large-scale graph data in powerful back-end computing resources. Experimental results show that the proposed methods can significantly improve the performance of truss analysis on real-world graphs compared with the existing and widely adopted list intersection-based method. The implemented code is publicly available from GitHub (https://github.com/Bears-R-Us/arkouda-njit).