Out-of-distribution (OOD) generalization is a challenging machine learning problem yet highly desirable in many high-stake applications. Distributionally robust optimization (DRO) is a promising learning paradigm to tackle this challenge but suffers from several limitations. To address this challenge, we propose graph-relational distributionally robust optimization that trains OOD-resilient machine learning models by exploiting the topological structure of data distributions. Our approach can uniformly handle both fully-known and partially-known topological structures. Empirical results on both synthetic and real-world datasets demonstrate the effectiveness and flexibility of our method.