Developing new diagnostic models based on the underlying biological mechanisms rather than subjective symptoms for psychiatric disorders is an emerging consensus. Recently, machine learning (ML)-based classifiers using functional connectivity (FC) for psychiatric disorders and healthy controls (HCs) are developed to identify brain markers. However, existing ML-based diagnostic models are prone to overfitting (due to insufficient training samples) and perform poorly in new test environments. Furthermore, it is difficult to obtain explainable and reliable brain biomarkers elucidating the underlying diagnostic decisions. These issues hinder their possible clinical applications. In this work, we propose BrainIB, a new graph neural network (GNN) framework to analyze functional magnetic resonance images (fMRI), by leveraging the famed information bottleneck (IB) principle. BrainIB is able to identify the most informative edges in the brain (i.e., subgraph) and generalizes well to unseen data. We evaluate the performance of BrainIB against three baselines and seven state-of-the-art (SOTA) brain network classification methods on three psychiatric datasets and observe that our BrainIB always achieves the highest diagnosis accuracy. It also discovers the subgraph biomarkers that are consistent with clinical and neuroimaging findings. The source code and implementation details of BrainIB are freely available at the GitHub repository (https://github.com/SJYuCNEL/brain-and-Information-Bottleneck).