De Bruijn Goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphs

Lisi Qarkaxhija, Vincenzo Perri, Ingo Scholtes
Proceedings of the First Learning on Graphs Conference, PMLR 198:51:1-51:21, 2022.

Abstract

We introduce De Bruijn Graph Neural Networks (DBGNNs), a novel time-aware graph neural network architecture for time-resolved data on dynamic graphs. Our approach accounts for temporal-topological patterns that unfold in the causal topology of dynamic graphs, which is determined by \emph{causal walks}, i.e. temporally ordered sequences of links by which nodes can influence each other over time. Our architecture builds on multiple layers of higher-order De Bruijn graphs, an iterative line graph construction where nodes in a De Bruijn graph of order \textdollar k\textdollar represent walks of length \textdollar k-1\textdollar , while edges represent walks of length \textdollar k\textdollar . We develop a graph neural network architecture that utilizes De Bruijn graphs to implement a message passing scheme that considers non-Markovian characteristics of causal walks, which enables us to learn patterns in the causal topology of dynamic graphs. Addressing the issue that De Bruijn graphs with different orders \textdollar k\textdollar can be used to model the same data, we apply statistical model selection to determine the optimal graph to be used for message passing. An evaluation in synthetic and empirical data sets suggests that DBGNNs can leverage temporal patterns in dynamic graphs, which substantially improves performance in a node classification task.

Cite this Paper

BibTeX
@InProceedings{pmlr-v198-qarkaxhija22a, title = {De Bruijn Goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphs}, author = {Qarkaxhija, Lisi and Perri, Vincenzo and Scholtes, Ingo}, booktitle = {Proceedings of the First Learning on Graphs Conference}, pages = {51:1--51:21}, year = {2022}, editor = {Rieck, Bastian and Pascanu, Razvan}, volume = {198}, series = {Proceedings of Machine Learning Research}, month = {09--12 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v198/qarkaxhija22a/qarkaxhija22a.pdf}, url = {https://proceedings.mlr.press/v198/qarkaxhija22a.html}, abstract = {We introduce De Bruijn Graph Neural Networks (DBGNNs), a novel time-aware graph neural network architecture for time-resolved data on dynamic graphs. Our approach accounts for temporal-topological patterns that unfold in the causal topology of dynamic graphs, which is determined by \emph{causal walks}, i.e. temporally ordered sequences of links by which nodes can influence each other over time. Our architecture builds on multiple layers of higher-order De Bruijn graphs, an iterative line graph construction where nodes in a De Bruijn graph of order \textdollar k\textdollar represent walks of length \textdollar k-1\textdollar , while edges represent walks of length \textdollar k\textdollar . We develop a graph neural network architecture that utilizes De Bruijn graphs to implement a message passing scheme that considers non-Markovian characteristics of causal walks, which enables us to learn patterns in the causal topology of dynamic graphs. Addressing the issue that De Bruijn graphs with different orders \textdollar k\textdollar can be used to model the same data, we apply statistical model selection to determine the optimal graph to be used for message passing. An evaluation in synthetic and empirical data sets suggests that DBGNNs can leverage temporal patterns in dynamic graphs, which substantially improves performance in a node classification task.} }
Endnote
%0 Conference Paper %T De Bruijn Goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphs %A Lisi Qarkaxhija %A Vincenzo Perri %A Ingo Scholtes %B Proceedings of the First Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2022 %E Bastian Rieck %E Razvan Pascanu %F pmlr-v198-qarkaxhija22a %I PMLR %P 51:1--51:21 %U https://proceedings.mlr.press/v198/qarkaxhija22a.html %V 198 %X We introduce De Bruijn Graph Neural Networks (DBGNNs), a novel time-aware graph neural network architecture for time-resolved data on dynamic graphs. Our approach accounts for temporal-topological patterns that unfold in the causal topology of dynamic graphs, which is determined by \emph{causal walks}, i.e. temporally ordered sequences of links by which nodes can influence each other over time. Our architecture builds on multiple layers of higher-order De Bruijn graphs, an iterative line graph construction where nodes in a De Bruijn graph of order \textdollar k\textdollar represent walks of length \textdollar k-1\textdollar , while edges represent walks of length \textdollar k\textdollar . We develop a graph neural network architecture that utilizes De Bruijn graphs to implement a message passing scheme that considers non-Markovian characteristics of causal walks, which enables us to learn patterns in the causal topology of dynamic graphs. Addressing the issue that De Bruijn graphs with different orders \textdollar k\textdollar can be used to model the same data, we apply statistical model selection to determine the optimal graph to be used for message passing. An evaluation in synthetic and empirical data sets suggests that DBGNNs can leverage temporal patterns in dynamic graphs, which substantially improves performance in a node classification task.
APA
Qarkaxhija, L., Perri, V. & Scholtes, I.. (2022). De Bruijn Goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphs. Proceedings of the First Learning on Graphs Conference, in Proceedings of Machine Learning Research 198:51:1-51:21 Available from https://proceedings.mlr.press/v198/qarkaxhija22a.html.

Related Material