Imagine a knowledge graph containing the relations IsFatherOf and IsWifeOf. If we compose these relations to traverse a multi-hop path, the order of operations matters immensely: the "father of the wife" is a completely different person from the "wife of the father."
In mathematics, when the order of operations changes the outcome, the system is non-commutative ($A \circ B \neq B \circ A$). However, early representation learning models frequently treated relational composition as a commutative operation. As noted by Wenpeng Yin et al. and Yao Zhu et al., collapsing these distinct logical sequences into commutative vector math creates severe semantic confusion, rendering models unable to accurately trace multi-hop paths or perform complex reasoning.
To build models that truly understand hierarchies, language, and sequential logic, researchers have shifted toward embedding frameworks governed by non-commutative algebra.
The Failure of Commutativity
To understand why non-commutativity is necessary, we must look at how standard embeddings fail. Consider a simple translational model like TransE, which represents a relation as a vector addition ($\mathbf{h} + \mathbf{r} = \mathbf{t}$). If we compose two relations, the path is modeled as $\mathbf{r}_1 + \mathbf{r}_2$. Because vector addition is commutative, $\mathbf{r}_1 + \mathbf{r}_2$ is mathematically identical to $\mathbf{r}_2 + \mathbf{r}_1$. The model is fundamentally blind to path order.
Even models that move beyond simple addition can fall into the commutativity trap. For instance, representing relations as rotations in a two-dimensional complex plane (like RotatE) seems highly expressive. However, as Hidetoshi Shimodaira et al. point out, 2D rotations are inherently commutative; rotating an entity by angle $\theta_1$ and then $\theta_2$ yields the exact same state as reversing the order. This geometric constraint prevents the capture of directional logic required for complex real-world hierarchies and role chains (Ling Cai et al.).
The issue is not confined to multi-step paths; it affects single relations as well. Danushka Bollegala et al. demonstrate that while commutative operators aggregate shared attributes, they fail to distinguish the distinct, asymmetric roles of participating entities—such as separating the subject from the object.
Designing Non-Commutative Operators
To preserve directionality, the mathematical operators used for embedding composition must be inherently order-dependent. Researchers have explored several algebraic mechanisms to achieve this.
Matrix-Vector Interactions
One of the earliest solutions was introduced by Alberto Paccanaro et al. through Linear Relational Embedding (LRE). LRE treats entities as vectors and relations as matrices. Because matrix multiplication is non-commutative ($M_1 M_2 \neq M_2 M_1$), the model naturally respects structural context and hierarchy.
In natural language processing, Edward Grefenstette et al. applied this concept to compositional distributional semantics. By mapping relational words (like verbs) to matrices acting on noun vectors, the authors created a system that respects syntax, successfully distinguishing sentences that contain identical words but different meanings due to word order.
Holographic Embeddings and Circular Correlation
While full matrices offer non-commutativity, they suffer from parameter explosion. To circumvent this, Maximilian Nickel et al. introduced holographic embeddings (HolE), which utilize circular correlation ($\star$) to model entity interactions.
$$\mathbf{a} \star \mathbf{b} \neq \mathbf{b} \star \mathbf{a}$$
Because circular correlation is non-commutative, it cleanly differentiates between subject and object roles while maintaining the computational efficiency of vector-space models. This mechanism was later adapted by Yi Tay et al. to capture the asymmetric, directional relationship between questions and answers in text retrieval tasks.
Block Circulant and Affine Transformations
To strike an optimal balance between expressiveness and parameter efficiency, Katsuhiko Hayashi 0001 et al. proposed representing relations using block circulant matrices. This structure enforces non-commutative composition for sequential path queries without the memory overhead of unconstrained matrices.
Taking a geometric approach, Xiou Ge et al. combined translation, rotation, and scaling into cascaded operations within the affine group. By compounding these geometric operations, the sequence of relational compositions remains mathematically distinct, preventing distinct logical paths from collapsing into the same representation.
Escaping Flat Space with Hypercomplex Rotations
If 2D rotations are commutative, how can we leverage the stability of rotational embeddings without losing the benefits of order? The answer lies in higher-dimensional spaces and non-Abelian groups.
Hidetoshi Shimodaira et al. demonstrated that moving to orthogonal transformations in dimensions greater than two breaks commutativity. A elegant way to implement this is through hypercomplex numbers, specifically quaternions. Quaternions extend complex numbers into a four-dimensional space where multiplication is non-commutative ($i \cdot j = k$, but $j \cdot i = -k$).
By leveraging quaternion math, models can represent relations as 3D rotations. As shown by Zongsheng Cao et al. (using dual quaternions) and Hidetoshi Shimodaira et al. (combining 3D rotations with hyperbolic translations), hypercomplex spaces naturally preserve directional logic.
Alternatively, Canran Xu et al. achieved non-commutative composition by incorporating reflections alongside rotations via the Dihedral group, mapping relation paths to a non-Abelian algebraic structure.
Commutative (2D Rotation)
Entity ───► Rotate θ1 ───► Rotate θ2 ───► Final State A
Entity ───► Rotate θ2 ───► Rotate θ1 ───► Final State A (Same)
Non-Commutative (3D Quaternion Rotation / Matrices)
Entity ───► Rotate R1 ───► Rotate R2 ───► Final State B
Entity ───► Rotate R2 ───► Rotate R1 ───► Final State C (Distinct)
Extending Order to Graphs and Sequential Reasoning
The necessity of non-commutative composition extends beyond simple knowledge graph triplets into graph neural networks (GNNs) and hypergraphs.
Traditional GNNs rely on permutation-invariant aggregators (like sum or mean), which treat a node's neighbors as an unordered set. However, Kaijia Xu et al. demonstrated that replacing these symmetric aggregators with recurrent neural networks (LSTMs) allows the model to respect the natural sequence of data, breaking performance ceilings on algorithmic tasks like selection and partitioning.
For multi-relational data, Landon Butler et al. showed that the sequence in which different types of interactions occur changes the resulting state, meaning multi-graph convolutions must be non-commutative to avoid losing structural context. When dealing with hypergraphs where relationships involve multiple entities, Naganand Yadati introduced frameworks that explicitly preserve the specific role or position an entity occupies within a hyperedge.
Finally, Huaiyu Wan et al. integrated gated sequential mechanisms to fuse relations step-by-step. This architectural choice ensures that paths like "father of wife" and "wife of father" map to entirely unique mathematical representations, aligning the model's internal logic with the directional reality of human knowledge.
Key Foundational Work
Learning Hierarchical Structures with Linear Relational Embedding (2001) — contributed 1 concept elements to this direction.
Experimental Support for a Categorical Compositional Distributional Model of Meaning (2011) — contributed 1 concept elements to this direction.