Graphs are traditionally represented by adjacency matrices, where an entry $A_{ij}$ captures a relationship between exactly two nodes. However, real-world systems rarely operate in isolated pairs. Whether it is a research team of three scientists, a metabolic pathway of multiple proteins, or a multi-way feature affinity in computer vision, relationships are inherently polyadic.
When we force these group interactions into a standard graph, we suffer from pairwise collapse. For example, if nodes $i$, $j$, and $k$ participate in a single joint interaction, a standard graph represents this as three independent edges: $(i,j)$, $(j,k)$, and $(i,k)$. This representation completely loses the context of the group; it becomes impossible to distinguish a single three-way interaction from three independent two-way interactions. As Shi et al. argue in Higher-Order Clustering in Heterogeneous Information Networks, this collapse discards rich semantic context. To preserve the structural cohesion of groups, we must move beyond flat matrices to multi-dimensional arrays: tensors.
From Adjacency Matrices to Adjacency Tensors
To represent a hypergraph—a generalization of a graph where edges can connect any number of vertices—we can use an $N$-th order adjacency tensor. For an $m$-uniform hypergraph (where every hyperedge contains exactly $m$ vertices), the structure maps naturally to an $m$-order, $n$-dimensional tensor, as detailed by Sun et al. in Estrada index and subgraph centrality of hypergraphs via tensors.
In this tensor $\mathcal{A}$, an entry $\mathcal{A}_{i_1, i_2, \dots, i_m}$ is non-zero if and only if the tuple of vertices $(i_1, i_2, \dots, i_m)$ shares a hyperedge. This formulation allows models to process ternary, quaternary, and higher-order relations efficiently within a single unified framework, as shown in HyperLearn: A Distributed Approach for Representation Learning in Datasets With Many Modalities.
Matrix Representation (2nd-Order) Tensor Representation (3rd-Order)
Node j Node j
┌───┐ ┌───┐
Node i │ 1 │ (Pairwise Edge) Node i │ 1 │ \
└───┘ └───┘ \ Node k
└───┐
│ 1 │ (Triadic Hyperedge)
└───┘
Tensors can also represent higher-order structures within standard graphs or multi-layered networks. For instance, Arrigo et al. in A framework for second-order eigenvector centralities and clustering coefficients define cubic (3D) tensors to explicitly track network motifs like triangles, clustering coefficients, and local closure potentials. Similarly, Marques et al. demonstrate in A Recurrent Graph Neural Network for Multi-relational Data that multi-relational tensors prevent information loss when multiple distinct relationship layers are collapsed into a single adjacency matrix. By upgrading the dimensionality of the underlying array, Vempala et al. utilize a parity-based tensor representation in Random Tensors and Planted Cliques to capture higher-order vertex subset interactions that remain completely invisible to standard matrix representations.
Why Tensors Work: Preserving Latent Geometry
The core intuition behind tensor-based representations is that higher-order arrays provide the geometric information necessary to resolve structural ambiguities that matrices flatten away.
Consider the problem of overlapping communities. In a social network, an individual might belong to multiple overlapping circles. In A tensor approach to learning mixed membership community models, Anandkumar et al. demonstrate that second-order matrix representations (like standard covariance or pairwise adjacency) are mathematically insufficient to uniquely isolate these overlapping memberships. By counting three-node "stars" to construct a third-order moment tensor, they unlock unique tensor decompositions that reveal the exact latent memberships.
This preservation of structural cohesion is a recurring theme across representation learning:
- Preserving Group Context: Cao et al. show in Network Embedding via Coupled Kernelized Multi-Dimensional Array Factorization that modeling cliques or co-authorship teams as $n$-dimensional arrays prevents the loss of group context during embedding generation.
- Expressive Deep Learning: In deep learning, Keriven proves in Universal Invariant and Equivariant Graph Neural Networks that for a Graph Neural Network (GNN) to achieve universal approximation capabilities, its internal layers must utilize tensors of order greater than two. Without this higher-order tensor space, the network cannot capture the complex structural dependencies required to approximate arbitrary graph functions.
- Decoupling Symmetries: Bevilacqua et al. show in Holographic Node Representations: Pre-training Task-Agnostic Node Embeddings that mapping nodes to multi-dimensional tensors allows a model to store complex structural relationships that can be filtered or reduced later depending on whether the downstream task requires node-level or pair-level invariance.
- Explicit Clique Modeling: Li et al. demonstrate in TP-GCL: graph contrastive learning from the tensor perspective that transforming standard graphs into hypergraphs via clique expansion and representing them with high-order adjacency tensors captures group-level structures that standard pairwise adjacency matrices overlook.
Generalizing Graph Operations to Higher Dimensions
Moving to a tensor representation requires redefining our fundamental graph toolkits—such as random walks, spectral clustering, and network alignment—using multilinear algebra.
Spectral Analysis and Clustering
In standard graphs, spectral clustering relies on the Singular Value Decomposition (SVD) of an adjacency or Laplacian matrix. For hypergraphs, the authors of Spectral Clustering Using Multilinear SVD: Analysis, Approximations and Applications generalize this by applying multilinear SVD to symmetric affinity tensors. This allows the algorithm to maximize multi-way similarities simultaneously, making it possible to recover complex intersecting structures (like motion trajectories) that pairwise matrices fail to segment.
Random Walks and Transitions
Instead of a standard transition matrix, Peng et al. construct a "cross-order neighbor tensor" based on multi-step Markov transition probabilities in Cross-View Diversity Embedded Consensus Learning for Multi-View Clustering. This simulates higher-order random walks to uncover latent connections across multiple data views.
Network Generation and Alignment
To generate massive synthetic graphs with realistic higher-order features, Eikmeier et al. introduce the The HyperKron Graph Model for higher-order features, which applies Kronecker powering to a multi-dimensional initiator tensor rather than a 2D matrix. For network alignment, Mohammadi leverages tensor-based representations in Triangular Alignment (TAME): A Tensor-Based Approach for Higher-Order Network Alignment to calculate multi-node structural motifs, enabling the discovery of conserved biological machinery across species. Similarly, Duchenne et al. show in A Tensor-Based Algorithm for High-Order Graph Matching that formulating graph matching as a hypergraph task using tensor power iterations captures higher-order affinities between feature tuples.
Tensor Contraction as the Engine of Higher-Order Learning
How do these models actually compute with tensors without exploding in complexity? The answer lies in tensor contraction and decomposition.
In Recognizable Series on Hypergraphs, Bailly et al. demonstrate an elegant framework where tensors are assigned to vertices, and hyperedges act as the "wiring" that dictates how these tensors are contracted. Tensor contraction generalizes standard matrix multiplication to complex relational data, allowing the evaluation of structured inputs through localized algebraic reductions.
Matrix Multiplication (2D) Tensor Contraction (Higher-Order)
┌───┐ ┌───┐ ┌───┐ ┌───┐
│ A │ × │ B │ │ A ├─────┤ B │
└───┘ └───┘ └─┬─┘ └─┬─┘
│ ┌───┐ │
└───┤ C ├───┘
└───┘
Furthermore, tensor decompositions like the Canonical Polyadic (CP) decomposition allow researchers to define a Fourier transform for hypergraphs, as shown by Schaub et al. in Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond. By decomposing the multi-dimensional tensor, signals residing on complex group interactions can be analyzed in the frequency domain.
This structural decomposition also dramatically reduces computational overhead in dynamic systems; for instance, Dong et al. use tensor decompositions in On Complexity of Stability Analysis in Higher-order Ecological Networks through Tensor Decompositions to efficiently compute the Jacobian matrix for large, multi-species ecosystems. By shifting from flat matrices to higher-order tensors, these diverse frameworks ensure that the multi-node context of real-world systems is preserved, analyzed, and leveraged rather than flattened away.
Key Foundational Work
Report on the First International Workshop on Mining Graphs and Complex Structures (MGCS'07) (2008) — contributed 1 concept elements to this direction.
Random Tensors and Planted Cliques (2009) — contributed 1 concept elements to this direction.