On the discovery of group-consistent graph substructure patterns from brain networks

Complex networks constitute a recurring issue in the analysis of neuroimaging data. Recently, network motifs have been identified as patterns of interconnections since they appear in a significantly higher number than in randomized networks, in a given ensemble of anatomical or functional connectivity graphs. The current approach for detecting and enumerating motifs in brain networks requires a predetermined motif repertoire and can operate only with motifs of small size (consisting of few nodes). There is a growing interest in methodologies for frequent graph-based pattern mining in large graph datasets that can facilitate adaptive design of motifs. The results presented in this paper are based on the graph-based Substructure pattern mining (gSpan) algorithm and introduce a manifold of ways to exploit it for data-driven motif extraction in connectomics research. Functional connectivity graphs from electroencephalographic (EEG) recordings during resting state and mental calculations are used to demonstrate our approach. Relying on either time-invariant or time-evolving graphs, characteristic motifs associated with various frequency bands were derived and compared. With a suitable manipulation, the gSpan discovers motifs which are specific to performing mental arithmetics. Finally, the subject-dependent temporal signatures of motifs' appearance revealed the transient nature of the evolving functional connectivity (math-related motifs "come and go").