Spatio-temporal time series are widely used in real-world applications, including traffic prediction and weather forecasting. They are sequences of observations over extensive periods and multiple locations, naturally represented as multidimensional data. Forecasting is a central task in spatio-temporal analysis, and numerous deep learning methods have been developed to address it. However, as dataset sizes and model complexities continue to grow in practice, training deep learning models has become increasingly time- and resource-intensive. A promising solution to this challenge is dataset distillation, which synthesizes compact datasets that can effectively replace the original data for model training. Although successful in various domains, including time series analysis, existing dataset distillation methods compress only one dimension, making them less suitable for spatio-temporal datasets, where both spatial and temporal dimensions jointly contribute to the large data volume. To address this limitation, we propose STemDist, the first dataset distillation method specialized for spatio-temporal time series forecasting. A key idea of our solution is to compress both temporal and spatial dimensions in a balanced manner, reducing training time and memory. We further reduce the distillation cost by performing distillation at the cluster level rather than the individual location level, and we complement this coarse-grained approach with a subset-based granular distillation technique that enhances forecasting performance. On five real-world datasets, we show empirically that, compared to both general and time-series dataset distillation methods, datasets distilled by our STemDist method enable model training (1) faster (up to 6X) (2) more memory-efficient (up to 8X), and (3) more effective (with up to 12% lower prediction error).

The problem of predicting node properties (e.g., node classes) in graphs has received significant attention due to its broad range of applications. Graphs from real-world datasets often evolve over time, with newly emerging edges and dynamically changing node properties, posing a significant challenge for this problem. In response, temporal graph neural networks (TGNNs) have been developed to predict dynamic node properties from a stream of emerging edges. However, our analysis reveals that most TGNN-based methods are (a) far less effective without proper node features and, due to their complex model architectures, (b) vulnerable to distribution shifts. In this paper, we propose SPLASH, a simple yet powerful method for predicting node properties on edge streams under distribution shifts. Our key contributions are as follows: (1) we propose feature augmentation methods and an automatic feature selection method for edge streams, which improve the effectiveness of TGNNs, (2) we propose a lightweight MLP-based TGNN architecture that is highly efficient and robust under distribution shifts, and (3) we conduct extensive experiments to evaluate the accuracy, efficiency, generalization, and qualitative performance of the proposed method and its competitors on dynamic node classification, dynamic anomaly detection, and node affinity prediction tasks across seven real-world datasets.

Do real-world hypergraphs obey any patterns? Are power laws fundamental in hypergraphs as they are in real-world graphs? What generator can reproduce these patterns? A hypergraph is a generalization of a conventional graph, and it consists of nodes and hyperedges, with each hyperedge joining any number of nodes. Hypergraphs are adept at representing group interactions where two or more entities interact simultaneously, such as collaborative research and group discussions. In a wide range of real-world hypergraphs, we discover power-law or log-logistic distributions in eight structural properties. To simulate these observed patterns, we introduce HyRec, a tractable and realistic generative model leveraging the Kronecker product. We mathematically demonstrate that HyRec accurately reproduces both the patterns we observed and typical evolutionary trends found in real-world hypergraphs. To fit the parameters of HyRec to large-scale hypergraphs, we design SingFit, a fast and space-efficient algorithm successfully applied to eleven real-world hypergraphs with up to one million nodes and hyperedges. This paper makes the following contributions: (a) Discoveries: we identify multiple patterns that real-world hypergraphs obey, (b) Model: we propose HyRec, a tractable and realistic model capable of reproducing real-world hypergraphs efficiently (spec., with fewer than 1,000 parameters) with the support of SingFit, and (c) Proofs: we prove that HyRec adheres to these patterns.

Abstract Many real-world data from various domains can be represented as tensors, and a significant portion of them is large scale. Thus, tensor compression is crucial for their storage and transmission. Recently, deep learning-based methods have emerged to enhance compression performance. However, they require considerable compression time to fulfill their performance. In this work, to achieve both speed and performance, we develop ELiCiT, an effective and lightweight lossy tensor compression method. When designing ELiCiT, we avoid deep auto-regressive neural networks and index reordering, which incur high computational costs of deep learning-based tensor compression. Specifically, instead of using the orders of indices as parameters, we introduce a feature-based model for indices, which enhances the model’s expressive capacity and simplifies the overall end-to-end training procedure. Moreover, to reduce the size of the parameters and computational cost for inference, we adopt end-to-end clustering-based quantization, as an alternative to deep auto-regressive architecture. As a result, ELiCiT becomes easy to optimize with enhanced expressiveness. We prove that it (partially) generalizes deep learning-based methods and also traditional ones. Using eight real-world tensors, we show that ELiCiT yields compact outputs that fit the input tensor accurately. Compared to the best competitor with similar fitness, it offers 1.51 $$-$$ - 5.05 $$\times $$ × smaller outputs. Moreover, compared to deep learning-based compression methods, ELiCiT is 11.8 $$-$$ - 96.0 $$\times $$ × faster with 5–48% better fitness for a similarly sized output. We also demonstrate that ELiCiT is extended to matrix completion, neural network compression , and tensor stream summarization, providing the best trade-offs between model size and application performance.

Abstract Many real-world datasets are represented as tensors, i.e., multi-dimensional arrays of numerical values. Storing them without compression often requires substantial space, which grows exponentially with the order. While many tensor compression algorithms are available, many of them rely on strong data assumptions regarding its order, sparsity, rank, and smoothness. In this work, we propose TensorCodec, a lossy compression algorithm for general tensors that do not necessarily adhere to strong input data assumptions.TensorCodec incorporates three key ideas. The first idea is neural tensor-train decomposition (NTTD) where we integrate a recurrent neural network into Tensor-Train Decomposition to enhance its expressive power and alleviate the limitations imposed by the low-rank assumption. Another idea is to fold the input tensor into a higher-order tensor to reduce the space required by NTTD. Finally, the mode indices of the input tensor are reordered to reveal patterns that can be exploited by NTTD for improved approximation. In addition, we extend TensorCodec to enable the lossy compression of tensors with missing entries, often found in real-world datasets. Our analysis and experiments on 8 real-world datasets demonstrate that TensorCodec is (a) Concise: it gives up to $$7.38 \times $$ 7.38 × more compact compression than the best competitor with similar reconstruction error, (b) Accurate: given the same budget for compressed size, it yields up to $$3.33\times $$ 3.33 × more accurate reconstruction than the best competitor, (c) Scalable: Its empirical compression time is linear in the number of tensor entries, and it reconstructs each entry in logarithmic time. Our code and datasets are available at https://github.com/kbrother/TensorCodec .

Continual Learning (CL) is the process of learning ceaselessly a sequence of tasks. Most existing CL methods deal with independent data (e.g., images and text) for which many benchmark frameworks and results under standard experimental settings are available. Compared to them, however, CL methods for graph data (graph CL) are relatively underexplored because of (a) the lack of standard experimental settings, especially regarding how to deal with the dependency between instances, (b) the lack of benchmark datasets and scenarios, and (c) high complexity in implementation and evaluation due to the dependency. In this paper, regarding (a) we define four standard incremental settings (task-, class-, domain-, and time-incremental) for node-, link-, and graph-level problems, extending the previously explored scope. Regarding (b), we provide 35 benchmark scenarios based on 24 real-world graphs. Regarding (c), we develop BeGin , an easy and fool-proof framework for graph CL. BeGin is easily extended since it is modularized with reusable modules for data processing, algorithm design, and evaluation. Especially, the evaluation module is completely separated from user code to eliminate potential mistakes. Regarding benchmark results, we cover \(3\times\) more combinations of incremental settings and levels of problems than the latest benchmark. All assets for the benchmark framework are publicly available at https://github.com/ShinhwanKang/BeGin .

Many real-world data from various domains can be represented as tensors, and a significant portion of them is large-scale. Thus, tensor compression is crucial for their storage and transmission. Recently, deep-learning-based methods have emerged to enhance compression performance. However, they require considerable compression time to fulfill their performance. In this work, to achieve both speed and performance, we develop ELICIT, an effective and lightweight lossy tensor compression method. When designing ELICIT, we avoid deep auto-regressive neural networks and index reordering, which incur high computational costs of deep-learning-based tensor compression. Specifically, instead of using the orders of indices as parameters, we introduce a feature-based model for indices, which enhances the model's expressive capacity and simplifies the overall end-to-end training procedure. Moreover, to reduce the size of the parameters and computational cost for inference, we adopt end-to-end clustering-based quantization, as an alter-native to deep auto-regressive architecture. As a result, ELICIT becomes easy to optimize with enhanced expressiveness. We prove that it (partially) generalizes deep-learning-based methods and also traditional ones. Using eight real-world tensors, we show that ELICIT yields compact outputs that fit the input tensor accurately. Compared to the best competitor with similar fitness, it offers 1.51-5.05 × smaller outputs. Moreover, compared to deep-learning-based compression methods, ELICIT is 11.8-96.0 × faster with 5-48% better fitness for a similarly sized output. We also demonstrate that ELICIT is extended to matrix completion and neural network compression, providing the best tradeoffs between model size and application performance.

An irregular tensor is a collection of matrices with different numbers of rows. Real-world data from diverse domains, including medical and stock data, are effectively represented as irregular tensors due to the inherent variations in data length. For their analysis, various tensor decomposition methods (e.g., PARAFAC2) have been devised. While they are expected to be effective in compressing large-scale irregular tensors, akin to regular tensor decomposition methods, our analysis reveals that their compression performance is limited due to the larger number of first mode factor matrices.

Many real-world datasets are represented as tensors, i.e., multi-dimensional arrays of numerical values. Storing them without compression often requires substantial space, which grows exponentially with the order. While many tensor compression algorithms are available, many of them rely on strong data assumptions regarding its order, sparsity, rank, and smoothness. In this work, we propose TENSORCODEC, a lossy compression algorithm for general tensors that do not necessarily adhere to strong input data assumptions. TENSORCODEC incorporates three key ideas. The first idea is Neural Tensor-Train Decomposition (NTTD) where we integrate a recurrent neural network into Tensor-Train Decomposition to enhance its expressive power and alleviate the limitations imposed by the low-rank assumption. Another idea is to fold the input tensor into a higher-order tensor to reduce the space required by NTTD. Finally, the mode indices of the input tensor are reordered to reveal patterns that can be exploited by NTTD for improved approximation. Our analysis and experiments on 8 real-world datasets demonstrate that TENSORCODEC is (a) Concise: it gives up to $7.38 \times$ more compact compression than the best competitor with similar reconstruction error, (b) Accurate: given the same budget for compressed size, it yields up to $3.33 \times$ more accurate reconstruction than the best competitor, (c) Scalable: its empirical compression time is linear in the number of tensor entries, and it reconstructs each entry in logarithmic time. Our code and datasets are available at https://github.com/kbrother/TensorCodec.

Many real-world data are naturally represented as a sparse reorderable matrix, whose rows and columns can be arbitrarily ordered (e.g., the adjacency matrix of a bipartite graph). Storing a sparse matrix in conventional ways requires an amount of space linear in the number of non-zeros, and lossy compression of sparse matrices (e.g., Truncated SVD) typically requires an amount of space linear in the number of rows and columns. In this work, we propose NeuKron for compressing a sparse reorderable matrix into a constant-size space. NeuKron generalizes Kronecker products using a recurrent neural network with a constant number of parameters. NeuKron updates the parameters so that a given matrix is approximated by the product and reorders the rows and columns of the matrix to facilitate the approximation. The updates take time linear in the number of non-zeros in the input matrix, and the approximation of each entry can be retrieved in logarithmic time. We also extend NeuKron to compress sparse reorderable tensors (e.g. multi-layer graphs), which generalize matrices. Through experiments on ten real-world datasets, we show that NeuKron is (a) Compact: requiring up to five orders of magnitude less space than its best competitor with similar approximation errors, (b) Accurate: giving up to 10 × smaller approximation error than its best competitors with similar size outputs, and (c) Scalable: successfully compressing a matrix with over 230 million non-zero entries.

A variety of tasks on dynamic graphs, including anomaly detection, community detection, compression, and graph understanding, have been formulated as problems of identifying constituent (near) bi-cliques (i.e., complete bipartite graphs). Even when we restrict our attention to maximal ones, there can be exponentially many near bi-cliques, and thus finding all of them is practically impossible for large graphs. Then, two questions naturally arise: (Q1) What is a ''good'' set of near bi-cliques? That is, given a set of near bi-cliques in the input dynamic graph, how should we evaluate its quality? (Q2) Given a large dynamic graph, how can we rapidly identify a high-quality set of near bi-cliques in it? Regarding Q1, we measure how concisely, precisely, and exhaustively a given set of near bi-cliques describes the input dynamic graph. We combine these three perspectives systematically on the Minimum Description Length principle. Regarding Q2, we propose CutNPeel, a fast search algorithm for a high-quality set of near bi-cliques. By adaptively re-partitioning the input graph, CutNPeel reduces the search space and at the same time improves the search quality. Our experiments using six real-world dynamic graphs demonstrate that CutNPeel is (a) High-quality: providing near bi-cliques of up to 51.2% better quality than its state-of-the-art competitors, (b) Fast: up to 68.8X faster than the next-best competitor, and (c) Scalable: scaling to graphs with 134 million edges. We also show successful applications of CutNPeel to graph compression and pattern discovery.

Consider traffic data (i.e., triplets in the form of source-destination-timestamp) that grow over time. Tensors (i.e., multi-dimensional arrays) with a time mode are widely used for modeling and analyzing such multi-aspect data streams. In such tensors, however, new entries are added only once per period, which is often an hour, a day, or even a year. This discreteness of tensors has limited their usage for real-time applications, where new data should be analyzed instantly as it arrives.How can we analyze time-evolving multi-aspect sparse data `continuously' using tensors where time is `discrete'? We propose SLICENSTITCH for continuous CANDECOMP/PARAFAC (CP) decomposition, which has numerous time-critical applications, including anomaly detection, recommender systems, and stock market prediction. SLICENSTITCH changes the starting point of each period adaptively, based on the current time, and updates factor matrices (i.e., outputs of CP decomposition) instantly as new data arrives. We show, theoretically and experimentally, that SLICENSTITCH is (1) `Any time': updating factor matrices immediately without having to wait until the current time period ends, (2) Fast: with constant-time updates up to 464× faster than online methods, and (3) Accurate: with fitness comparable (specifically, 72 - 100%) to offline methods.