  Knowledge graph embedding (KGE) models achieved state-of-the-art results on
many knowledge graph tasks including link prediction and information retrieval.
Despite the superior performance of KGE models in practice, we discover a
deficiency in the expressiveness of some popular existing KGE models called
\emph{Z-paradox}. Motivated by the existence of Z-paradox, we propose a new KGE
model called \emph{MQuinE} that does not suffer from Z-paradox while preserves
strong expressiveness to model various relation patterns including
symmetric/asymmetric, inverse, 1-N/N-1/N-N, and composition relations with
theoretical justification. Experiments on real-world knowledge bases indicate
that Z-paradox indeed degrades the performance of existing KGE models, and can
cause more than 20\% accuracy drop on some challenging test samples. Our
experiments further demonstrate that MQuinE can mitigate the negative impact of
Z-paradox and outperform existing KGE models by a visible margin on link
prediction tasks.
