Scaling High-Order Feature Interactions via Tensor Decomposition

87 concepts63 papers1 proposal

Standard deep learning architectures rely heavily on linear combinations ($\mathbf{W}\mathbf{x} + \mathbf{b}$) followed by element-wise non-linear activations. While highly successful, this approach forces networks to learn complex feature conjunctions implicitly through deep stacking. If we want to explicitly model multi-way interactions—such as feature combinations in multi-view data, cross-modal correlations in multimodal fusion, or high-degree polynomial expansions—we naturally run into high-order tensors.

However, explicitly modeling these interactions introduces a severe bottleneck: the curse of dimensionality. If an input vector has dimension $d$, modeling all $N$-way interactions requires a weight tensor with $d^N$ parameters. This exponential explosion makes high-order modeling computationally prohibitive and highly prone to overfitting, a challenge noted by Mo Yu et al. in their work on compressing discrete feature conjunctions via Embedding Lexical Features via Low-Rank Tensors.

The core insight of parameter-efficient tensor modeling is that these massive interaction tensors are highly redundant. By applying low-rank tensor decompositions, we can factorize an exponentially large interaction space into a sequence of small, interconnected low-rank matrices or core tensors. This shifts the computational and parameter complexity from exponential ($O(d^N)$) to linear or polynomial ($O(d \cdot r)$), making explicit high-order interactions practical.

The Core Intuition: Factoring the Interaction Space

To understand why tensor decomposition works, let us look at the simplest case: a rank-1 decomposition of a 3-way interaction tensor.

Suppose we have three feature vectors $\mathbf{x}, \mathbf{y}, \mathbf{z} \in \mathbb{R}^d$, and we want to compute a scalar interaction score using a full 3D weight tensor $\mathcal{W} \in \mathbb{R}^{d \times d \times d}$:

$$f(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \sum_{i=1}^d \sum_{j=1}^d \sum_{k=1}^d \mathcal{W}_{ijk} x_i y_j z_k$$

Computing this directly requires $O(d^3)$ parameters and operations. However, if we assume $\mathcal{W}$ is a rank-1 tensor, it can be represented as the outer product of three vectors $\mathbf{a}, \mathbf{b}, \mathbf{c} \in \mathbb{R}^d$, meaning $\mathcal{W}_{ijk} = a_i b_j c_k$. Substituting this into the equation yields:

$$f(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \sum_{i=1}^d \sum_{j=1}^d \sum_{k=1}^d (a_i b_j c_k) x_i y_j z_k$$

Because multiplication is distributive, we can rearrange the summations:

$$f(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \left(\sum_{i=1}^d a_i x_i\right) \left(\sum_{j=1}^d b_j y_j\right) \left(\sum_{k=1}^d c_k z_k\right)$$

This algebraic rearrangement changes everything. Instead of iterating over a giant 3D grid, we compute three independent vector dot products in $O(d)$ time and multiply their scalar results. By summing $r$ of these rank-1 components—known as a Canonical Polyadic (CP) decomposition—we can approximate any tensor with a total complexity of $O(r \cdot d)$. The exponential wall is completely bypassed.

A Taxonomy of Low-Rank Formats

Depending on the structure of the data and the required expressivity, researchers leverage different tensor factorization formats to compress interaction spaces.

CP Decomposition (Canonical Polyadic)

CP decomposition represents a tensor as a sum of rank-1 tensors. Bokai Cao et al. utilized this format in Multi-view Machines to jointly factorize multi-view feature combinations into a shared latent subspace, achieving linear time complexity relative to the number of views. Similarly, Lifang He et al. applied CP decomposition in A Self-Organizing Tensor Architecture for Multi-View Clustering to capture hidden multi-way correlations without exponential parameter growth.

Tucker Decomposition

While CP forces factors to interact only along shared component indices, Tucker decomposition offers more flexibility by multiplying a smaller, dense "core tensor" by factor matrices along each mode. This allows every latent factor of one feature to interact with every latent factor of another.

Guosheng Hu et al. leveraged Tucker decomposition in Attribute-Enhanced Face Recognition with Neural Tensor Fusion Networks to constrain identity and facial attribute fusion to a low-rank form, preventing overfitting. For discrete structures, Benfeng Xu et al. used a grouped Tucker alignment strategy in EmRel: Joint Representation of Entities and Embedded Relations for Multi-triple Extraction to manage the ternary interactions between subjects, relations, and objects.

Tensor Train (TT) and Tensor Ring

When the interaction order $N$ becomes large (e.g., modeling 10th-order polynomials), even Tucker's core tensor suffers from exponential scaling ($O(r^N)$). The Tensor Train format solves this by factorizing the massive weight tensor into a linear chain of interconnected, low-rank 3D core tensors.

Alexander Novikov et al. introduced Exponential Machines, demonstrating that the TT format can represent an exponentially large weight tensor to capture all possible feature interaction orders simultaneously while keeping memory consumption linear. Building on this structural efficiency, Farzaneh Heidari et al. showed in Tractable Shapley Values and Interactions via Tensor Networks that factorizing large coefficient tensors into tensor trains allows higher-order feature explanations to be computed via a single polynomial-time tensor contraction.

CP Decomposition:      (Vector) ─── (Vector) ─── (Vector)  [Summed over r components]

Tucker Decomposition:  (Matrix) ─── [ Core Tensor ] ─── (Matrix)
                                          │
                                       (Matrix)

Tensor Train:          (Core 1) ─── (Core 2) ─── (Core 3) ─── (Core N)

Transforming Neural Architectures

Low-rank tensor factorization is not just an optimization tool for linear models; it serves as a foundational building block for expanding the expressivity of deep neural networks.

Deep Polynomial Networks

Instead of stacking standard layers to approximate non-linear functions, networks can be formulated as explicit high-degree polynomial expansions. Grigorios Chrysos et al. developed $\Pi$-nets in Deep Polynomial Neural Networks, utilizing coupled tensor factorizations to share parameters across different polynomial orders. This allows the network to capture complex high-dimensional distributions even without traditional activation functions.

Multiplicative Recurrence

Standard recurrent networks use additive transitions to update hidden states ($\mathbf{h}_t = \sigma(\mathbf{W}\mathbf{h}_{t-1} + \mathbf{U}\mathbf{x}_t)$). A more powerful approach is to let the input multiplicatively gate the hidden-to-hidden transitions via a 3-way interaction tensor.

The authors of a seminal text-generation paper, Generating Text with Recurrent Neural Networks, showed that decomposing this 3-way interaction tensor into shared factors creates a computational bottleneck that makes multiplicative recurrence scalable. Ben Krause et al. extended this concept to LSTMs in Multiplicative LSTM for sequence modelling, using factorized element-wise Hadamard products to approximate full 3-way tensors, allowing the network to dynamically re-weight its connections for every token.

Non-Linear Feature Aggregation

Tensor factorization also allows for parameter-efficient pooling and attention mechanisms across diverse domains:

By treating high-order interaction spaces not as dense matrices to be filled, but as low-rank structures to be factorized, these techniques allow machine learning models to capture multi-way dependencies with extreme parameter efficiency and rigorous structural regularization.

Key Foundational Work

Factored conditional restricted Boltzmann Machines for modeling motion style (2009) — contributed 2 concept elements to this direction.
Factored 3-Way Restricted Boltzmann Machines For Modeling Natural Images (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_low_rank_tensor_decomposition_63f9e85c,
  title = {low-rank tensor decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/low-rank-tensor-decomposition/rdr_63f9e85c36cc4c62a26d8fd995e85321},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_low_rank_tensor_decomposition_63f9e85c_v1,
  title = {low-rank tensor decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/low-rank-tensor-decomposition/rdr_63f9e85c36cc4c62a26d8fd995e85321/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake