Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders

• URL: http://arxiv.org/abs/2007.06662v2
• Date: Wed, 25 Aug 2021 15:08:07 GMT
• Title: Predicting Sequences of Traversed Nodes in Graphs using Network Models with Multiple Higher Orders
• Authors: Christoph Gote, Giona Casiraghi, Frank Schweitzer, and Ingo Scholtes
• Abstract summary: We develop a technique to fit such multi-order models in empirical sequential data and to select the optimal maximum order. We evaluate our model based on six empirical data sets containing sequences from website navigation as well as public transport systems. We further demonstrate the accuracy of our method during out-of-sample sequence prediction and validate that our method can scale to data sets with millions of sequences.
• Score: 1.0499611180329802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel sequence prediction method for sequential data capturing node traversals in graphs. Our method builds on a statistical modelling framework that combines multiple higher-order network models into a single multi-order model. We develop a technique to fit such multi-order models in empirical sequential data and to select the optimal maximum order. Our framework facilitates both next-element and full sequence prediction given a sequence-prefix of any length. We evaluate our model based on six empirical data sets containing sequences from website navigation as well as public transport systems. The results show that our method out-performs state-of-the-art algorithms for next-element prediction. We further demonstrate the accuracy of our method during out-of-sample sequence prediction and validate that our method can scale to data sets with millions of sequences.

Related papers

• Efficient Model Selection for Predictive Pattern Mining Model by Safe Pattern Pruning [14.892080531048956]
  We propose the Safe Pattern Pruning (SPP) method to address the explosion of pattern numbers in predictive pattern mining. To demonstrate the effectiveness of the proposed method, we conduct numerical experiments on regression and classification problems involving sets, graphs, and sequences.
  arXiv  Detail & Related papers  (2023-06-23T15:34:20Z)
• SequenceMatch: Imitation Learning for Autoregressive Sequence Modelling with Backtracking [60.109453252858806]
  A maximum-likelihood (MLE) objective does not match a downstream use-case of autoregressively generating high-quality sequences. We formulate sequence generation as an imitation learning (IL) problem. This allows us to minimize a variety of divergences between the distribution of sequences generated by an autoregressive model and sequences from a dataset. Our resulting method, SequenceMatch, can be implemented without adversarial training or architectural changes.
  arXiv  Detail & Related papers  (2023-06-08T17:59:58Z)
• Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionality [84.94877848357896]
  Recent datasets expose the lack of the systematic generalization ability in standard sequence-to-sequence models. We analyze this behavior of seq2seq models and identify two contributing factors: a lack of mutual exclusivity bias and the tendency to memorize whole examples. We show substantial empirical improvements using standard sequence-to-sequence models on two widely-used compositionality datasets.
  arXiv  Detail & Related papers  (2022-11-28T17:36:41Z)
• Sequence-to-Set Generative Models [9.525560801277903]
  We propose a sequence-to-set method to transform any sequence generative model into a set generative model. We present GRU2Set, which is an instance of our sequence-to-set method and employs the famous GRU model as the sequence generative model. A direct application of our models is to learn an order/set distribution from a collection of e-commerce orders.
  arXiv  Detail & Related papers  (2022-09-19T07:13:51Z)
• Conditional set generation using Seq2seq models [52.516563721766445]
  Conditional set generation learns a mapping from an input sequence of tokens to a set. Sequence-to-sequence(Seq2seq) models are a popular choice to model set generation. We propose a novel algorithm for effectively sampling informative orders over the space of label orders.
  arXiv  Detail & Related papers  (2022-05-25T04:17:50Z)
• Improving Graph-based Sentence Ordering with Iteratively Predicted Pairwise Orderings [38.91604447717656]
  We propose a novel sentence ordering framework which introduces two classifiers to make better use of pairwise orderings for graph-based sentence ordering. Our model achieves state-of-the-art performance when equipped with BERT and FHDecoder.
  arXiv  Detail & Related papers  (2021-10-13T02:18:16Z)
• Time series forecasting based on complex network in weighted node similarity [12.246860992135783]
  In time series analysis, visibility graph theory transforms time series data into a network model. The node similarity index is used as the weight coefficient to optimize the prediction algorithm. The method has more accurate forecasting ability and can provide more accurate forecasts in the field of time series and actual scenes.
  arXiv  Detail & Related papers  (2021-03-14T01:01:41Z)
• Predicting Temporal Sets with Deep Neural Networks [50.53727580527024]
  We propose an integrated solution based on the deep neural networks for temporal sets prediction. A unique perspective is to learn element relationship by constructing set-level co-occurrence graph. We design an attention-based module to adaptively learn the temporal dependency of elements and sets.
  arXiv  Detail & Related papers  (2020-06-20T03:29:02Z)
• Document Ranking with a Pretrained Sequence-to-Sequence Model [56.44269917346376]
  We show how a sequence-to-sequence model can be trained to generate relevance labels as "target words" Our approach significantly outperforms an encoder-only model in a data-poor regime.
  arXiv  Detail & Related papers  (2020-03-14T22:29:50Z)
• ProphetNet: Predicting Future N-gram for Sequence-to-Sequence Pre-training [85.35910219651572]
  We present a new sequence-to-sequence pre-training model called ProphetNet. It introduces a novel self-supervised objective named future n-gram prediction. We conduct experiments on CNN/DailyMail, Gigaword, and SQuAD 1.1 benchmarks for abstractive summarization and question generation tasks.
  arXiv  Detail & Related papers  (2020-01-13T05:12:38Z)

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.