Knowledge graphs (KGs) have gradually become valuable assets for many AI applications. In a KG, a node denotes an entity, and an edge(or link) denotes a relationship between the entities represented by the nodes. Knowledge graph completion infers and predicts missing edges in a KG automatically. Knowledge graph embeddings have shed light on addressing this task. Recent research embeds KGsin hyperbolic (negatively curved) space instead of conventionalEuclidean (zero curved) space and has been effective in capturing hierarchical structures. However, as a multi-relational graph, KGs are not structured uniformly and display intrinsic heterogeneous structures. They usually contain rich types of structures, such as hierarchical or cyclical structure. Embedding KGs in single-curvature space, such as hyperbolic or Euclidean space, overlooks the intrinsic heterogeneous structures of KGs, and therefore cannot accurately capture their structure. To address this issue, we propose a Mixed-Curvature Multi-Relational Graph Neural Net-work (M2GNN), a generic approach that embeds multi-relationalKGs in mixed-curvature space. Specifically, we define and construct a mixed-curvature space through a product manifold combining multiple single-curvature spaces (e.g., spherical, hyperbolic, or Euclidean) with the purpose of modeling a variety of structures. However, constructing a mixed-curvature space typically requires manually defining the fixed curvatures, which requires domain knowledge and additional data analysis. Improperly defined curvature spaces also cannot capture the structure of KGs accurately. To overcome this problem, we adopt trainable curvatures to better capture the underlying structure of the KGs. Furthermore, we propose a Graph Neural Updater by leveraging the heterogeneous relational context in mixed-curvature space to improve the quality of the embedding. Experiments on three KG datasets demonstrate that the proposed M2GNN can outperform its single geometry counterpart as well as state-of-the-art embedding methods on the KGcompletion task.