We present an algorithm for inferring an unknown graph from time-indexed signals corresponding to the graph nodes. The signals are assumed to consist of a few dominant, yet unknown, frequencies within the graph spectrum, consistent across all time points, as well as sparse, potentially temporally incoherent corruptions. These corruptions may serve as relevant features for classification in neurological applications. We apply our algorithm to neuropsychiatric datasets, including ADHD, OPEN-NEURO, and COBRE, in order to learn graphs for patients and controls. The learned graphs, used as features for classification, result in higher classification accuracy compared to existing graph learning methods. Furthermore, our proposed model generates more connected or “small-world” networks, consistent with previous findings on brain networks. We also demonstrate that the proposed model achieves a better separation between patient and control classes. © 2023 Elsevier B.V.