Functional connectivity network (FCN) analysis is an effective technique for modeling human brain patterns and diagnosing neurological disorders such as Alzheimer’s disease (AD) and its early stage, Mild Cognitive Impairment. However, accurately estimating biologically meaningful and discriminative FCNs remains challenging due to the poor quality of functional magnetic resonance imaging (fMRI) data and our limited understanding of the human brain. Inspired by the inter-similarity nature of FCNs, similar regions of interest tend to share similar connection patterns. Here, we propose a functional brain network modeling scheme by encoding Inter-similarity prior into a graph-regularization term, which can be easily solved with an efficient optimization algorithm. To illustrate its effectiveness, we conducted experiments to distinguish Mild Cognitive Impairment from normal controls based on their respective FCNs. Our method outperformed the baseline and state-of-the-art methods by achieving an 88.19% classification accuracy. Furthermore, post hoc inspection of the informative features showed that our method yielded more biologically meaningful functional brain connectivity.