Online Algorithm for Node Feature Forecasting in Temporal Graphs

• URL: http://arxiv.org/abs/2401.16800v2
• Date: Wed, 22 May 2024 20:36:13 GMT
• Title: Online Algorithm for Node Feature Forecasting in Temporal Graphs
• Authors: Aniq Ur Rahman, Justin P. Coon,
• Abstract summary: In this paper, we propose an online mspace for forecasting node features in temporal graphs. We show that mspace performs at par with the state-of-the-art and even surpasses them on some datasets. We also propose a technique to generate synthetic datasets to aid in evaluating node feature forecasting methods.
• Score: 12.667148739430798
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we propose an online algorithm mspace for forecasting node features in temporal graphs, which captures spatial cross-correlation among different nodes as well as the temporal auto-correlation within a node. The algorithm can be used for both probabilistic and deterministic multi-step forecasting, making it applicable for estimation and generation tasks. Comparative evaluations against various baselines, including temporal graph neural network (TGNN) models and classical Kalman filters, demonstrate that mspace performs at par with the state-of-the-art and even surpasses them on some datasets. Importantly, mspace demonstrates consistent performance across datasets with varying training sizes, a notable advantage over TGNN models that require abundant training samples to effectively learn the spatiotemporal trends in the data. Therefore, employing mspace is advantageous in scenarios where the training sample availability is limited. Additionally, we establish theoretical bounds on multi-step forecasting error of mspace and show that it scales linearly with the number of forecast steps $q$ as $\mathcal{O}(q)$. For an asymptotically large number of nodes $n$, and timesteps $T$, the computational complexity of mspace grows linearly with both $n$, and $T$, i.e., $\mathcal{O}(nT)$, while its space complexity remains constant $\mathcal{O}(1)$. We compare the performance of various mspace variants against ten recent TGNN baselines and two classical baselines, ARIMA and the Kalman filter across ten real-world datasets. Additionally, we propose a technique to generate synthetic datasets to aid in evaluating node feature forecasting methods, with the potential to serve as a benchmark for future research. Lastly, we have investigate the interpretability of different mspace variants by analyzing model parameters alongside dataset characteristics to derive model and data-centric insights.

Related papers

• Scalar Field Prediction on Meshes Using Interpolated Multi-Resolution Convolutional Neural Networks [0.0]
  We propose a method to predict scalar fields on arbitrary meshes. The model is trained on finite element von Mises stress fields, and once trained it can estimate stress values at each node on any input mesh. We also demonstrate the model on a temperature field in a heat conduction problem, where its predictions have a median R-squared value of 0.99.
  arXiv  Detail & Related papers  (2024-10-07T21:59:34Z)
• Neural Spacetimes for DAG Representation Learning [23.54420278189682]
  We propose a class of trainable deep learning-based geometries called Neural Spacetimes. We encode both graph edge weights in its spatial dimensions and causality in the form of edge directionality in its temporal dimensions. Our main theoretical guarantee is a universal embedding theorem, showing that any $k$-point DAG can be embedded into an NST with $1+mathcalO(log(k))$ distortion.
  arXiv  Detail & Related papers  (2024-08-25T16:26:55Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Spatio-temporal DeepKriging for Interpolation and Probabilistic Forecasting [2.494500339152185]
  We propose a deep neural network (DNN) based two-stage model fortemporal-temporal and forecasting. We adopt the quant-based loss function in the processes to provide probabilistic forecasting. It is suitable for large-scale prediction of complex-temporal processes.
  arXiv  Detail & Related papers  (2023-06-20T11:51:44Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Community recovery in non-binary and temporal stochastic block models [0.17188280334580194]
  This article studies the estimation of latent community memberships from pairwise interactions in a network of $N$ nodes. We introduce a block model with a general measurable interaction space $mathcal S$, for which we derive information-theoretic bounds for the minimum achievable error rate. We also present fast online estimation algorithms which fully utilise the non-binary nature of the observed data.
  arXiv  Detail & Related papers  (2020-08-11T15:33:59Z)
• Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks [91.65637773358347]
  We propose a general graph neural network framework designed specifically for multivariate time series data. Our approach automatically extracts the uni-directed relations among variables through a graph learning module. Our proposed model outperforms the state-of-the-art baseline methods on 3 of 4 benchmark datasets.
  arXiv  Detail & Related papers  (2020-05-24T04:02:18Z)
• Using Machine Learning to predict extreme events in the H\'enon map [0.0]
  We analyze the performance of one algorithm for the prediction of extreme events in the two-dimensional H'enon map at the classical parameters. Similar relations between the intrinsic chaotic properties of the dynamics and ML parameters might be observable in other systems as well.
  arXiv  Detail & Related papers  (2020-02-20T15:56:20Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.