Global and Local Structure Learning for Sparse Tensor Completion
Dawon Ahn, Evangelos E. Papalexakis · 2025
Read Global and Local Structure Learning for Sparse Tensor Completion by Dawon Ahn, Evangelos E. Papalexakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20929.txt.
Introduction
Dawon Ahn and Evangelos Papalexakis tackle missing values in multi-way data in this 2025 paper. Such data, called tensors, can be pictured as tables with more than two axes. Filling in missing entries is a common task, but older methods do not learn how entries along each axis relate to each other.
Their method, called TGL, rebuilds the data with parts that learn both broad and local patterns. It uses a graph-based network to learn local links, with no prior facts needed about those links. Wide tests against other methods and data sets are used to judge the method. The authors aim for more exact fills than standard tools can give.
Catalog record
| CREATOR | Dawon Ahn, Evangelos E. Papalexakis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 8 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-20929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Global and Local Structure Learning for Sparse Tensor Completion
Dawon Ahn, Evangelos E. Papalexakis
Abstract
How can we accurately complete tensors by learning relationships of dimensions along each mode? Tensor completion, a widely studied problem, is to predict missing entries in incomplete tensors. Tensor decomposition methods, fundamental tensor analysis tools, have been actively developed to solve tensor completion tasks. However, standard tensor decomposition models have not been designed to learn relationships of dimensions along each mode, which limits to accurate tensor completion. Also, previously developed tensor decomposition models have required prior knowledge between relations within dimensions to model the relations, expensive to obtain. This paper proposes TGL (Tensor Decomposition Learning Global and Local Structures) to accurately predict missing entries in tensors. TGL reconstructs a tensor with factor matrices which learn local structures with GNN without prior knowledges. Extensive experiments are conducted to evaluate TGL with baselines and datasets.
I
Introduction
Given an incomplete tensor,
how can we predict missing values learning relations within dimensions?
A tensor is a natural way to represent multi-dimensional data.
For example, 3-mode tensor (user, movie, time) represents movie rating data where users give rates to movies at specific times.
The goal of tensor completion is to impute missing entries in incomplete tensors which are partially observed.
The tensor completion problems have been actively studied
across diverse domain of applications such as recommender system
[
1
,
2
,
3
]
,
anomaly detection
[
4
]
, computer vision
[
5
]
, and air quality analysis
[
6
]
.
Tensor decomposition methods have played a key role in tensor analysis
such that they have significantly been developed to solve the completion tasks.
CP (CANDECOMP/PARAFAC)
[
7
,
8
]
factorization is one of the most widely used tensor factorization models due to its simplicity and interpretability,
which factorizes a tensor into a set of factor matrices and a core tensor which is restricted to be diagonal. However, the design of standard CP decomposition model does not consider explicitly relations between dimensions,
which degrades the performance in missing entries prediction.
Recently, various types of tensor decomposition methods have been proposed to leverage
prior knowledges, such as temporal knowledge, correlations between dimensions, as a
regularization into loss function
[
9
,
6
]
.
However,
prior knowledges are expensive to obtain for general datasets.
In this paper, we propose
TGL
(Tensor Decomposition Learning Global and Local Structures) to learn relationships between dimensions without prior knowledges.
We leverage Graph Neural Networks (GNNs) to learn local structures.
TGL
initially produces representations with a standard CP decomposition
and then generates relation matrices with the representations.
With representation and relation matrices,
TGL
updates representations via GNNs for each mode.
We show
TGL
effectively learn relationships and achieve comparable accuracy compared to existing baselines in tensor completion.
II
Proposed Method
In this study,
we utilized both a CP decomposition method and GNNs
to learn relations within dimensions of each mode for incomplete tensors without prior knowledges.
In each iteration of training,
we generate K-nearest neighborhoods (KNN) graphs with the current factor matrices for each mode.
Then we update factor matrices using KNN graphs and GNNs.
With these newly updated factor matrices, we reconstruct a tensor to jointly train factor matrices and GNNs.
We generate graphs
\mathbf{R}_{A},\mathbf{R}_{B}
and
\mathbf{R}_{C}
with factor matrices
\mathbf{A}
,
\mathbf{B}
, and
\mathbf{C}
by computing pairwise cosine similarity for each mode.
A graph
G
contains a set of nodes
V(|V|=N)
, a set of edges
E
, and an adjacency matrix
\mathbf{R}\in\mathbb{R}^{N\times N}
as
G=(V,E)
.
Given the number of layers
l(1\leq l\leq L)
,
l+1
th hidden convolutional layer of GNNs takes feature matrix of the
l
th layer and the adjacency matrix
\mathbf{H}^{(l+1)}=f(\mathbf{H}^{(l)},\mathbf{R})=\sigma(\hat{\mathbf{R}}\mathbf{H}^{(l)}\mathbf{W}^{(l)})
where
\hat{\mathbf{R}}=\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{R}}\tilde{\mathbf{D}}^{\frac{1}{2}}
is a symmetric normalization of the self-connections added adjacency matrix
\tilde{\mathbf{R}}=\mathbf{R}+\mathbf{I}
,
\tilde{\mathbf{D}}
is the diagonal node degree matrix with
\tilde{d}_{ii}=\sum_{j}\tilde{r}_{ij}
,
\mathbf{W}^{(l)}\in\mathbb{R}^{d_{l}\times d_{l+1}}
is a trainable weight matrix.
\sigma
is a non-linear activation function.
Note that initial feature matrix
\mathbf{H}^{(0)}
is the factor matrix obtained.
Given factor matrices
\mathbf{A},\mathbf{B}
, and
\mathbf{C}
,
relation matrices
\mathbf{R}_{A},\mathbf{R}_{B}
and
\mathbf{R}_{C}
, and
GNN models
\{f_{1},f_{2},f_{3}\}
for each mode,
the new factor matrices are obtained by minimizing the following loss function:
\displaystyle\mathcal{L}\left(\mathbf{A},\mathbf{B},\mathbf{C}\right)
\displaystyle=\sum_{\forall\alpha\in\Omega}{\left({x}_{\alpha}-\sum_{r=1}^{R}\tilde{a}_{ir}\tilde{b}_{jr}\tilde{c}_{kr}\right)^{2}}
(1)
where
\tilde{a}_{ir}
,
\tilde{b}_{jr}
, and
\tilde{c}_{kr}
is the
(i,r)
th ,
(j,r)
th , and
(k,r)
th entry of
\tilde{\mathbf{A}}=f_{1}(\mathbf{A},\mathbf{R}_{\mathbf{A}})
,
\tilde{\mathbf{B}}=f_{2}(\mathbf{B},\mathbf{R}_{\mathbf{B}})
, and
\tilde{\mathbf{C}}=f_{3}(\mathbf{C},\mathbf{R}_{\mathbf{C}})
.
I will explain details of network hyper parameters in Section
III
.
III
Experiments
We perform experiments to evaluate the accuracy of
TGL
compared to baselines in tensor completion.
III-A
Experiments Setting
III-A
1
Datasets
We evaluate the performance of
TGL
and baselines on three real-world datasets.
Yelp
[
10
]
is
a business rating tensor with (user, business, time; rating) which includes
70,817 movies, 15,579 users, 108 year-month time duration, and 100,0836 ratings.
We sample each 5,000 in user and business such that the statistics of dataset used is
(5,000, 5,000, 108) since the proposed model can not handle too large dataset.
BBC-News
is a BBC news article tensor with (word, word, articles; co-occurrences) which includes
100 words and 400 articles.
We split each data into training, validation, and test sets with the ratio of 8:1:1 considering only observable entries and
use validation set for early stopping.
III-A
2
Baselines
There are two baselines:
CPD
[
11
]
is a standard CP decomposition model considering only nonzeros with gradient descent optimization.
CoSTCo
[
3
]
is a state-of-the-art tensor completion method exploiting Convolutional Neural Networks.
III-A
3
Metrics
We use NRE (Normalized Reconstruction Error) to evaluate the accuracy of tensor completion, which is defined as follows.
\text{NRE}=\frac{\sqrt{\sum_{\forall\alpha\in\Omega}{\left(x_{\alpha}-\hat{x}_{\alpha}\right)^{2}}}}{\sqrt{\sum_{\forall\alpha\in\Omega}{x_{\alpha}^{2}}}}.
(a)
Yelp
(b)
BBC-News
Fig. 1:
Comparison of test NRE of baselines on Yelp and BBC-News dataset with different size of ranks.
III-B
Tensor Completion Accuracy
Figure
1
show the performance of
TGL
and baselines.
with regard to test NRE.
TGL
shows the second best method
while CPD using the standard CP decomposition method shows large errors.
CoSTCo shows the lowest NRE among all methods
Even if
TGL
shows better performance than the standard model,
one potential reason that
TGL
shows limited performance is that
when training GNNs,
TGL
gives relation matrices and factor matrices which can have
redundant information since relation matrices are created based on factor matrices.
IV
Discussion & Conclusions
In this paper, we proposed
TGL
,
a tensor decomposition assisted with GNNs to learn global and local structures of a sparse tensor.
Experiment results show that
TGL
outperforms CPD and shows comparable performance as CoSTCo.
As mentioned in Experiments section,
a graph generated from
TGL
might give redundant information to GNNs
since relation matrices are made from factor matrices.