Quantifying significance of interactions of brain regions and inferring brain connectivity network is of paramount importance in neuroscience. Although there have recently emerged some tests for graph inference based on the neuroimaging data in the form of a spatial temporal matrix, there is no readily available solution to test the change of brain network before and after a stimulus activity. In this talk, we develop a paired test of matrix graphs to infer brain connectivity network when the groups of samples are correlated. The proposed test statistic is both bias corrected and variance corrected, which theoretically guarantees the subsequent multiple testing procedure built on this test statistic can asymptotically control the false discovery rate at the pre-specified level. Both the methodology and theory of the new method are considerably different from the two independent samples framework, due to the strong correlations of measurements on the same subjects before and after the stimulus. We illustrate the efficacy of our proposal through both simulations, and an analysis of an Alzheimer's Disease Neuroimaing Initiative dataset.