Graph recovery from graph wave equation

Let $V$ be a finite set $\{1,2,\cdots,n\}$ and let $\mathcal{A}_{V}$ denote the set of functions $\{f\colon V\rightarrow\mathbb{R}\}$, which is an $\mathbb{R}$-vector space. When $n=1$, $\mathcal{A}_{V}$ is identified with $\mathbb{R}$. We define two constant functions $0_{V}(\mathrm{x}):=0$ and $1_{V}(\mathrm{x}):=1$ for any $\mathrm{x}\in V$.

In addition, let $\{z_{1},\cdots,z_{M}\}$ be roots of a polynomial equation

Needless to say, each coefficient is represented by $c_{j}=(-1)^{j+1}e_{j}(z_{1},\cdots,z_{M})$, where $e_{j}$ denotes the $j$-th elementary symmetric polynomial. We assume that the roots $\{z_{j}\}$ are distinct, and then define a time-series model $F$ as the time evolution of the roots

where $\alpha_{j}\in\mathcal{A}_{V}\otimes\mathbb{C}\setminus 0_{V}$. We can define $F$ for $t\in\mathbb{R}$ by fixing $\arg z_{j}$, although this definition is not used herein. In this context, we just refer to the roots $\{z_{j}\}$ and coefficients $\{\alpha_{j}\}$ as the modes and amplitudes, respectively, of $F$. Now, we assume that the amplitudes satisfy a non-degenerate condition

Note that this condition is always satisfied by taking subset $V^{\prime}\subset V$ and considering all of the above over $V^{\prime}$ if necessary. Then, because of (2.1), time-series model $F$ satisfies

for any $\mathrm{x}\in V$ and any $t\in\mathbb{Z}$. This relation is regarded as a linear equation of the coefficients $\{c_{j}\}$. Hence the modes $\{z_{j}\}$ of $F$ can be determined from temporal observed sets $\{F(\cdot,t)\}$.

This result is viewed as Prony’s method [19] when $n=1$, and the dynamic mode decomposition [20] when $n\geq M$.

Now, we consider a special case of (2.2). In practice, the time-series model $F$ often contains a constant term, which is represented as a mode $Z=1$. In addition, it is usual to suppose that other modes are stationary and $F$ is $\mathbb{R}$-valued.

These conditions indicate a particular representation

where $\alpha_{0}\in\mathcal{A}_{V}\setminus 0_{V}$, $\alpha_{j}\in\mathcal{A}_{V}\otimes\mathbb{C}\setminus 0_{V}$ and $\{z_{j}\in\mathbb{C}\mid\mathop{\mathrm{Im}}\nolimits z_{j}>0,|z_{j}|=1$ for $1\leq j\leq N$ and are distinct from each other$\}$. This form is also viewed as a general form of the inverse discrete Fourier transform (DFT), the modes of which are given by $\{z_{j}=\exp(2\pi\mathrm{i}j/N)\}$. See the difference of mode sets in Figure 2.1. As above, we assume that the amplitudes satisfy the non-degenerate condition

Then, as a special case of (2.4), we have the following lemma;

The above lemma helps us to determine the modes from fewer observation points than Proposition 2.5, which needs $L+M=2N+2+\max(2N+1-n,0)$ observation points for model (2.11).

Once the modes $\{z_{j}\}$ in the general model (2.2) or the particular model (2.8) are obtained, the corresponding amplitudes $\{\alpha_{j}\}$ are also calculated by the curve fitting method. For model (2.2), we have

for any $T\in\mathbb{Z}_{>0}$. Since the Vandermonde matrix on the right has rank $M$ when $T\geq M$, observed values at $M$ integer points $\{F(\cdot,t)\in\mathcal{A}_{V}\otimes\mathbb{C}\mid t=1,2,\cdots,M\}$ determine all of the amplitudes $\{\alpha_{j}\}$.

Likewise, for model (2.8), we have

for any $T\in\mathbb{Z}_{>0}$. Hence, the observed values at $2N+1$ integer points $\{F(\cdot,t)\in\mathcal{A}_{V}\mid t=1,2,\cdots,2N+1\}$ determine all of the amplitudes $\{\alpha_{j}\}$. More generally, even for a dataset not generated from model (2.8), we can obtain this expansion. In other words, the following lemma holds.

In either case, the number of observation points needed to determine the amplitudes is less than that needed to determine the modes shown in Propositions 2.5 and 2.13. Therefore, the mode expansion techniques are summarized as follows:

We can use the estimated mode expansion for forecasting unobserved data.

Here, let us consider the following $n=1$ time-series data for example;

for $t=1,2,\cdots,100$. See the plots in Figure 2.2.

By applying Proposition 2.5 for $M=7$ and $L=7$ to $\{F(t)\in\mathbb{R}\mid t=1,2,\cdots,14\}$, we estimate modes and amplitudes, and then forecast the remaining values for $t>14$. As is well known, Prony’s method is too sensitive to extract precise modes from numerical values, given as 64-bit floating point numbers in our case. Therefore, the results in Figure 2.3 show that the estimated modes are slightly different from the true values, and then such error accumulates to give a bad forecast.

On the other hand, Proposition 2.13 for $N=3$ and $L=3$ gives better results from a smaller number of values $\{F(t)\in\mathbb{R}\mid t=1,2,\cdots,10\}$, as in Figure 2.4. This is because the absolute values of extracted modes are controlled to be $1$, as explained in Figure 2.1.

In §4, we explain a more detailed algorithm with a graph recovery procedure.

Let $\{w_{\mathrm{x}\mathrm{y}}\}$ be graph weights that satisfy $w_{\mathrm{y}\mathrm{x}}=w_{\mathrm{x}\mathrm{y}}\geq 0$ and $w_{\mathrm{x}\mathrm{x}}=0$ for $\mathrm{x}\neq\mathrm{y}\in V$. In the present paper, we regard $(V,\{w_{\mathrm{x}\mathrm{y}}\})$ as a weighted undirected graph that has an edge $\mathrm{x}$-$\mathrm{y}$ if and only if $w_{\mathrm{x}\mathrm{y}}>0$.

For a function $f\in\mathcal{A}_{V}$, we define the graph Laplacian $\mathcal{L}\colon\mathcal{A}_{V}\rightarrow\mathcal{A}_{V}$ as

where $\deg(\mathrm{x}):=\sum_{\mathrm{y}\in V}w_{\mathrm{x}\mathrm{y}}$. Note that graph weights $\{w_{\mathrm{x}\mathrm{y}}\}$ are defined as a metric of $1$-forms over a discrete set $V$, and the graph Laplacian is given as the Laplace-Beltrami operator with an inner product $\langle f,g\rangle_{V}:=\sum_{\mathrm{x}\in V}f(\mathrm{x})g(\mathrm{x})$ [22]. Since the Laplacian $\mathcal{L}$ is self-adjoint for this inner product, we can take eigenfunctions $\{v_{k}\in\mathcal{A}_{V}\mid 0\leq k\leq n-1\}$ as follows:

Here, we see $v_{0}=n^{-1/2}1_{V}$ and $v_{k}\perp 1_{V}$ for $k\geq 1$. Although the eigenfunctions $\{v_{k}\}$ have ambiguity regarding their signs even when the eigenvalues $\{\rho_{k}\}$ are distinct, we assume that the eigenfunctions are fixed in a certain manner. Moreover, in the present paper, we assume that a weighted graph $(V,\{w_{\mathrm{x}\mathrm{y}}\})$ is always connected, so that $\rho_{1}>0$. The upper and lower bounds of the eigenvalues are well studied; for example, we have

The proof and other bounds of graphs are shown in [6].

Set $\mathcal{F}[f]_{k}:=\langle f,v_{k}\rangle_{V}\in\mathbb{R}$ for $f\in\mathcal{A}_{V}$. Then, the eigenfunction expansion is given as

When the eigenvalues $\{\rho_{k}\}$ are distinct, this expansion is unique. In signal processing, the transformation $\mathcal{F}\colon\mathcal{A}_{V}\ni f\mapsto\mathcal{F}[f]\in\mathbb{R}^{n}$ is called the graph Fourier transform [13]. For the support function $\chi_{\mathrm{x}}$ on $\mathrm{x}\in V$, i.e., $\chi_{\mathrm{x}}(\mathrm{y})=\delta_{\mathrm{x},\mathrm{y}}$, we have $\mathcal{F}[\chi_{\mathrm{x}}]_{k}=\langle\chi_{\mathrm{x}},v_{k}\rangle_{V}=v_{k}(\mathrm{x})$. This calculation formally rewrites the eigenfunction decomposition of the graph Laplacian $\mathcal{L}$ in (3.2) as the following identity concerning the graph weight:

Similarly, the graph Fourier transform for a cycle graph is known as the discrete Fourier transform (DFT) in signal processing and image processing [4].

By use of the graph Laplacian, we can define the following graph wave equation [11] for $U\in\mathcal{A}_{V}\otimes\mathcal{C}^{2}(\mathbb{R};\mathbb{R})$:

for a certain $c>0$ and given $f,g\in\mathcal{A}_{V}$. For a solution $U(\mathrm{x},t)$, the graph Fourier coefficient $\mathcal{F}[U(\cdot,t)]$ becomes the harmonic oscillator