Recent knowledge graph (KG) embeddings have been advanced by the hyperbolic geometry due to its superior capability for representing hierarchies. The real-world KGs, however, are usually organized not uniformly, rather in a heterogeneous way, i.e., a KG is a mixture of multiple distinct hierarchies and non-hierarchical structures (e.g., cycles). A single homogeneous (either Euclidean or hyperbolic) geometry is not sufficient for representing such heterogeneous structures of KGs. To capture the heterogeneous structures of KGs, we present an Ultrahyperbolic KG Embedding (UltraE) in a pseudo-Riemannian manifold that seamlessly interleaves hyperbolic and spherical submanifolds that can naturally capture different graph structures. In particular, we consider the pseudo-hyperboloid of signature (p,q) and model relations as pseudo-orthogonal transformations that are isometries preserving the pseudo-Riemannian bilinear form. We derive a linearly complex relational parameterization by decomposing the quadratic pseudo-orthogonal transformation into various geometric operators (i.e., rotation, reflection, and translation), allowing for simultaneously modeling heterogeneous geometry as well as complex logical patterns including symmetry, anti-symmetry, inversion, and composition relations. We theoretically show the expressiveness of UltraE and discuss its connection to some existing Euclidean and hyperbolic methods. Experimental results on standard KG benchmarks show that UltraE outperforms previous Euclidean- and hyperbolic-based approaches.