Recently, there has been a surge of interest in enabling graph neural networks to generalize to data from unseen environments. However, a significant challenge for these algorithms is the presuming assumptions on the correlation strengths between spurious features and class label, which can lead to potential failures when these assumptions do not hold in real-world scenarios. To bridge this gap, we introduce a novel learning paradigm for graph invariance learning, which induces a robust inductive bias without the reliance on presuming correlation strengths between spurious features and class labels. We further propose a flexible learning framework EQuAD to realize this learning paradigm and introduce a new learning objective tailored for EQuAD that provably elicits invariant representations. Notably, our approach shows stable and enhanced performance across different degrees of bias in synthetic datasets and outperforms state-of-the-art baseline methods by an average of 31.76%. Additionally, EQuAD establishes new state-of-the-art benchmarks on multiple real-world datasets, demonstrating the effectiveness and robustness of our proposed framework.