FORECASTING GRAPH SIGNALS WITH RECURSIVE MIMO GRAPH FILTERS Jelmer van der Hoeven Alberto Natali and Geert Leus Faculty of Electrical Engineering Mathematics and Computer Science

2025-05-06 0 0 235.5KB 5 页 10玖币

侵权投诉

FORECASTING GRAPH SIGNALS WITH RECURSIVE MIMO GRAPH FILTERS

Jelmer van der Hoeven, Alberto Natali and Geert Leus

Faculty of Electrical Engineering, Mathematics and Computer Science

Delft University of Technology, Delft, The Netherlands

ABSTRACT

Forecasting time series on graphs is a fundamental problem in graph

signal processing. When each entity of the network carries a vector of

values for each time stamp instead of a scalar one, existing approaches

resort to the use of product graphs to combine this multidimensional

information, at the expense of creating a larger graph. In this paper,

we show the limitations of such approaches, and propose extensions

to tackle them. Then, we propose a recursive multiple-input multiple-

output graph ﬁlter which encompasses many already existing models

in the literature while being more ﬂexible. Numerical simulations on

a real world data set show the effectiveness of the proposed models.

Index Terms—

Forecasting, Graph Signal Processing, Product

Graph, Multi-dimensional graph signals

1. INTRODUCTION

Forecasting time series collected by entities of a network is a central

problem in graph signal processing (GSP) [

], ﬁnding applications in

sensor [

] and social networks [

], to name a few. Accounting for

the network structure in the forecasting model serves as an inductive

bias to reduce the number of estimation parameters of the model [

] compared to classical vector autoregressive (VAR) models [

However, existing models under a GSP lens consider a scalar value

at each node for each time instant [

], which is a limitation in

networks where a (feature) vector of measurements is available at

each node for each time instant, such as in meteorological sensor

networks or 3D point clouds.

This multidimensional case has been recently addressed in [

]

with the introduction of a so-called feature graph, capturing the possi-

ble relationships among the features of a node of the network. There,

the authors make use of product graphs [

] to create a new larger

graph that combines in a principled way the original and the feature

graphs, which is then used to forecast these multidimensional content

by taking into account relationships among features of different nodes.

However, the knowledge of which product graph to use and how to

construct the feature graph has not been properly elaborated.

This work can be considered an extension of [

] in that: i)

we ﬁrst delineate drawbacks of the proposed model and introduce

minor extensions to tackle them; then, ii) we propose a recursive

multiple-input multiple-output (MIMO) graph ﬁlter which general-

izes the already existing ﬁlters while being more ﬂexible; ﬁnally, iii)

we put forth a method which learns the weights of the feature graph

during the training process. We limit our exposition to linear mod-

els, although non-linear autoregressive models are a subject worth

investigating. Numerical experiments on real-world data show the

effectiveness of the proposed approaches.

E-mails:{Jelmer.van.der.hoeven@pwc.com}

{a.natali;g.j.t.leus}@tudelft.nl;

2. BACKGROUND

Consider an

-dimensional time series

xt∈RN

, where entry

xt(i)

represents the value at time

associated to the entry

. For instance,

xt(i)

might represent the amount of water in the

th reservoir of a

water network at time

. When the relationships between the different

time series of

can be captured by a network, let the graph

G:=

(V,E,S)

model such network, where

V={v1,...,vN}

is the set

nodes,

E ⊆ V × V

is the set of edges, and

S∈RN×N

the matrix representation of the graph, which captures its sparsity

pattern; i.e.,

Sij 6= 0

if and only if

(vi, vj)∈ E

vi=vj

. We refer

to matrix

as the graph shift operator (GSO), examples of which

include the adjacency matrix and the Laplacian matrix [

]. In

this context, xtis called a graph signal.

We can instantly process a graph signal

to obtain a new graph

signal ytby means of the so-called graph convolution [1]:

yt=

K−1

k=0

hkSkxt,(1)

where

H(S) := PK−1

k=0 hkSk

is the graph ﬁlter [

] of order

K−1

with scalar coefﬁcients

h0,...,hK−1

. Because matrix

is sparse,

the computational complexity of the graph ﬁltering operation

(1)

O(|E|K)

. To forecast time series residing on the nodes, a graph

vector autoregressive (G-VAR) model has been introduced in [

] as

the combination of a ﬁnite number of graph convolutions; speciﬁcally:

xt=−

p=1

Hp(S)xt−p=−

p=1

K−1

k=0

hkpSkxt−p,(2)

where

xt−p

represents the graph signal at time instant

t−p

and

hkp

represents the

th scalar ﬁlter coefﬁcient of the

-th graph ﬁlter

Hp(S)

. The computational complexity of

(2)

O(P K|E|)

and the

number of parameters of the ﬁlter is

P K

, both independent of the

size of the network.

Multidimensional.

When each node of the network carries a vec-

tor of

values (features) for each time instant

, we refer to such

a graph signal as being

-dimensional, and denote it as

xt=

[x>

t(1),...,x>

t(F)]>∈RNF

, where each

xt(f)∈RN

is the

one-dimensional graph signal associated to feature

. In other words,

is the concatenation of

graph signals, each one representing the

graph signal associated to one speciﬁc feature.

To efﬁciently deal with such multi-dimensional graph signals, the

work in [

] proposes to model the dependencies among the features

with a so-called feature graph deﬁned as

GF:= (VF,EF,SF)

where

VF={f1, ...., fF}

is the set of

nodes representing the

features,

EF⊆ VF× VF

is the set of edges deﬁning how the features

are connected, and

is the associated GSO. To formally capture

the dependencies among features of different nodes,

and

can be

combined with the use of product graphs [

] to create a new graph

arXiv:2210.15258v1 [eess.SP] 27 Oct 2022

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

FORECASTINGGRAPHSIGNALSWITHRECURSIVEMIMOGRAPHFILTERSJelmervanderHoeven,AlbertoNataliandGeertLeusFacultyofElectricalEngineering,MathematicsandComputerScienceDelftUniversityofTechnology,Delft,TheNetherlandsABSTRACTForecastingtimeseriesongraphsisafundamentalproblemingraphsignalprocessing.Wheneachentity...

展开>> 收起<<

FORECASTING GRAPH SIGNALS WITH RECURSIVE MIMO GRAPH FILTERS Jelmer van der Hoeven Alberto Natali and Geert Leus Faculty of Electrical Engineering Mathematics and Computer Science.pdf

共5页,预览1页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

FORECASTING GRAPH SIGNALS WITH RECURSIVE MIMO GRAPH FILTERS Jelmer van der Hoeven Alberto Natali and Geert Leus Faculty of Electrical Engineering Mathematics and Computer Science

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: