Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces

Paaßen B, Göpfert C, Hammer B (2018)
Neural Processing Letters 48(2): 669-689.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Abstract / Bemerkung
Graphs are a flexible and general formalism providing rich models in various important domains, such as distributed computing, intelligent tutoring systems or social network analysis. In many cases, such models need to take changes in the graph structure into account, that is, changes in the number of nodes or in the graph connectivity. Predicting such changes within graphs can be expected to yield important insight with respect to the underlying dynamics, e.g. with respect to user behaviour. However, predictive techniques in the past have almost exclusively focused on single edges or nodes. In this contribution, we attempt to predict the future state of a graph as a whole. We propose to phrase time series prediction as a regression problem and apply dissimilarity- or kernel-based regression techniques, such as 1-nearest neighbor, kernel regression and Gaussian process regression, which can be applied to graphs via graph kernels. The output of the regression is a point embedded in a pseudo-Euclidean space, which can be analyzed using subsequent dissimilarity- or kernel-based processing methods. We discuss strategies to speed up Gaussian Processes regression from cubic to linear time and evaluate our approach on two well-established theoretical models of graph evolution as well as two real data sets from the domain of intelligent tutoring systems. We find that simple regression methods, such as kernel regression, are sufficient to capture the dynamics in the theoretical models, but that Gaussian process regression significantly improves the prediction error for real-world data.
Stichworte
Structured Data; Graphs; Time Series Prediction; Gaussian Processes; Kernel Space
Erscheinungsjahr
2018
Zeitschriftentitel
Neural Processing Letters
Band
48
Ausgabe
2
Seite(n)
669-689
ISSN
1370-4621
eISSN
1573-773X
Page URI
https://pub.uni-bielefeld.de/record/2911900

Zitieren

Paaßen B, Göpfert C, Hammer B. Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces. Neural Processing Letters. 2018;48(2):669-689.
Paaßen, B., Göpfert, C., & Hammer, B. (2018). Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces. Neural Processing Letters, 48(2), 669-689. doi:10.1007/s11063-017-9684-5
Paaßen, B., Göpfert, C., and Hammer, B. (2018). Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces. Neural Processing Letters 48, 669-689.
Paaßen, B., Göpfert, C., & Hammer, B., 2018. Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces. Neural Processing Letters, 48(2), p 669-689.
B. Paaßen, C. Göpfert, and B. Hammer, “Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces”, Neural Processing Letters, vol. 48, 2018, pp. 669-689.
Paaßen, B., Göpfert, C., Hammer, B.: Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces. Neural Processing Letters. 48, 669-689 (2018).
Paaßen, Benjamin, Göpfert, Christina, and Hammer, Barbara. “Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces”. Neural Processing Letters 48.2 (2018): 669-689.
Link(s) zu Volltext(en)
Access Level
OA Open Access
Material in PUB:
In sonstiger Relation
Time Series Prediction for Relational and Kernel Data
Paaßen B (2017)
Bielefeld University.

Externes Material:
Forschungsdaten
Beschreibung
MiniPalindrome Dataset
Forschungsdaten
Beschreibung
Sorting Dataset

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

arXiv: 1704.06498

Suchen in

Google Scholar