Signal Processing over Multilayer Graphs: Theoretical Foundations and Practical Applications

Signal processing on graphs [1, 3, 2] studies signals that are discrete in some dimensions by representing the irregular signal structure using a graph $\mathcal{G}=\{\mathcal{V},\mathbf{F}\}$, where $\mathcal{V}=\{v_{1},v_{2},\cdots,v_{N}\}$ is a set of $N$ nodes, and $\mathbf{F}\in\mathbb{R}^{N\times N}$ is the representing matrix (e.g., adjacency/Laplacian) describing the geometric structure of the graph $\mathcal{G}$. Graph signals are the attributes of nodes that underlie the graph structure. A graph signal can be written as vector $\mathbf{s}=[s_{1},s_{2},\cdots,s_{N}]^{\mathrm{T}}\in\mathbb{R}^{N}$ where the superscript $(\cdot)^{\mathrm{T}}$ denotes matrix/vector transpose.

With a graph representation $\mathbf{F}$ and a signal vector $\mathbf{s}$, the basic graph filtering (shifting) is defined via

The graph spectrum space, also known as the graph Fourier space is defined based on the eigenspace of the representing matrix. Let the eigen-decomposition of $\mathbf{F}$ be given by $\mathbf{F}=\mathbf{V}\mathbf{\Lambda}\mathbf{V}^{-1}$, where $\mathbf{V}$ is the matrix with eigenvectors of $\mathbf{F}$ as columns, and diagonal matrix $\mathbf{\Lambda}$ consists of the corresponding eigenvalues. The graph Fourier transform (GFT) is defined as

whereas the inverse GFT is given by $\mathbf{s}=\mathbf{V}\hat{\mathbf{s}}$.

From definitions of GFT, other concepts, such as sampling theory [21], filter design [22], and frequency analysis [4] can be developed for signal processing and data analysis tasks.

Before introducing the fundamentals of M-GSP, we first review some basics on tensors that are useful for multilayer graph analysis. Tensors can be viewed as multi-dimensional arrays. The order of a tensor is the number of indices needed to label a component of that array [23]. For example, a third-order tensor has three indices. More specially, a scalar is a zeroth-order tensor; a vector is a first-order tensor; a matrix is a second-order tensor; and an $M$-dimensional array is an $M$th-order tensor. For convenience, we use bold letters to represent the tensors excluding scalars, i.e., $\mathbf{A}\in\mathbb{R}^{I_{1}\times I_{2}\cdots\times I_{N}}$ represents an $N$th-order tensor with $I_{k}$ being the dimension of the $k$th order, and use $A_{{i_{1}}\cdots i_{N}}$ to represent the entry of $\mathbf{A}$ at position $(i_{1},i_{2},\cdots,i_{N})$ with $1\leq i_{k}\leq I_{k}$ in this work. If $\mathbf{A}_{f}$ has a subscript $f$, we use $[A_{f}]_{{i_{1}}\cdots i_{N}}$ to denote its entries.

We now start with some useful definitions and tensor operations for the M-GSP framework [23].

Multilayer graph, also referred to as multilayer network, is an important geometric model in complex systems [10]. In this work, we refrain from using the “network” terminology because of its diverse meanings in various field ranging from communication networking to deep learning. From here onward, unless otherwise specified, we shall use the less ambiguous term of multilayer graph.

We first provide definitions of multilayer graphs (MLG).

Note that, we mainly focus on the layer-disjoint multilayer graph [10] where each node exists exactly in one layer, since layers denote different phenomena. For example, in a smart grid, a station with functions in both power grid and communication network, is usually modeled as two nodes in a two-layer graph for the network analysis [28].

In multilayer graphs, edges connect nodes in the same layer (intralayer edges) or nodes of different layers (interlayer edges) [29]. There are two main types of multilayer graphs: multiplex graph and interconnected graph [30]. In a multiplex graph, each layer has the same number of nodes, and each node only connects with their 1-to-1 matching counterparts in other layers to form interlayer connections. Typically, multiplex graphs characterize different types of interactions among the same (or a similar) set of physical entities. For example, the spatial-temporal connections among a set of nodes can be intuitively modeled as a multiplex graph [30]. In the interconnected graphs, each layer may have different numbers of nodes without a 1-to-1 counterpart. Their interlayer connections could be more flexible. Examples of a three-layer multiplex graph and a three-layer interconnected graph are shown in Fig. 3, where different colors represent different layers, solid lines represent intralayer connections, and dash lines indicate interlayer connections.

To capture the high-dimensional ‘multilayer’ interactions between different nodes, we use tensor as algebraic representation of MLG for the proposed M-GSP framework [11].

In this part, we introduce the flattening of the multilayer graph, which could simplify some operations in the tensor-based M-GSP. For a multilayer graph $\mathcal{M}=\{\mathcal{V},\mathcal{L},\mathbf{F}\}$ with $M$ layers and $N$ nodes in each layer, its fourth-order representing tensor $\mathbf{F}\in\mathbb{R}^{M\times N\times M\times N}$ can be flattened into a second-order matrix to capture the overall edge weights. There are two main flattening schemes in the sense of entities and layers, respectively:

• •

  Layer-wise Flattening: The representing tensor $\mathbf{F}$ can be flattened into $\mathbf{F}_{FL}\in\mathbb{R}^{MN\times MN}$ with each element

  $${[F_{FL}]}_{{N(\alpha-1)+i,N(\beta-1)+j}}=F_{\alpha i\beta j}.$$

  (13)

• •

  Entity-wise Flattening: The representing tensor $\mathbf{F}$ can be flattened into $\mathbf{F}_{FN}\in\mathbb{R}^{NM\times NM}$ with each element

  $${[F_{FN}]}_{{M(i-1)+\alpha,M(j-1)+\beta}}=F_{\alpha i\beta j}.$$

  (14)

These two flattening methods provide two ways to interpret the graph structure. In the first method, the flattened multilayer graph has $M$ clusters with $N$ nodes in each cluster. The nodes in the same cluster have the same function (belong to the same layer). In the second method, the flattened graph has $N$ clusters with $M$ nodes in each cluster. Here, the nodes in the same cluster are from the same entity. Examples of the tensor flattening of a two-layer graph with $3$ nodes in each layer are shown in Fig. 4. From the examples, we can see that the diagonal blocks in $\mathbb{R}^{N\times N}$ are the intralayer connections for each layer and other blocks describe the interlayer connections through layer-wise flattening; and the diagonal block in $\mathbb{R}^{M\times M}$ describe the ‘intra-entity’ connections and other elements represent the ‘inter-entity’ connections in entity-wise flattening. Although these two flattening schemes define the same MLG with a different indexing of vertices, they are still helpful to analyze the MLG spectrum space.

For a multilayer graph $\mathcal{M}=\{\mathcal{V},\mathcal{L},\mathbf{F}\}$ with $M$ layers and $N$ nodes, the eigen-tensor $\mathbf{V}\in\mathbb{R}^{M\times N}$ of the representing tensor $\mathbf{F}$ is defined in the tensor-based multilayer graph theory [11] as

More specifically, $\mathbf{F}\in\mathbb{R}^{M\times N\times M\times N}$ can be decomposed as

where $\lambda_{k}$ is the eigenvalues and $\mathbf{V}_{k}\in\mathbb{R}^{M\times N}$ is the corresponding eigen-tensor. Note that $\mathbf{V}_{\alpha i}$ just relabels the index of $\mathbf{V}_{k}$, and there is no specific order for $\mathbf{V}_{\alpha i}$ here.

Similar to the traditional GSP where the graph Fourier space is defined by the eigenvectors of the representing matrix, we define the joint MLG Fourier space as follows.

Recall that in GSP, the GFT is defined based on the inner product of $\mathbf{V}^{-1}$ and the signals $\mathbf{s}$ defined in Eq. (2). Similarly, we can define the M-GFT based on the spectral tensors of the representing tensor $\mathbf{F}$ to capture joint features of inter- and intra- layer interactions as follows.

Now, we show how to obtain the eigen-tensors. Implementing the flattening analysis, we have the following properties.

This property shows that the flattened tensors are the reshaped original representing tensor, and could capture some of the spectral properties as follows.

The Property 2 shows that we can calculate the eigen-tensor from the flattened tensor to simplify the decomposition operations. Moreover, the M-JGFT is the bijection of GFT in the flattened MLG, with vertices indexed by both the layers and the entities. However, such M-JGFT analyzes the inter- and intra- layer connections jointly while ignoring the individual features of entities and layers. Next, we will show how to implement the order-wise frequency analysis in M-GSP based on tensor decomposition.

In an undirected multilayer graph, the representing tensor (adjacency/Laplacian) $\mathbf{F}$ is partially symmetric between orders one and three, and between orders two and four, respectively. Then, the representing tensor can be written with the consideration of the multilayer graph structure under orthogonal CP-decomposition [26] as follows:

where $\mathbf{f}_{\alpha}\in\mathbb{R}^{M}$ are orthonormal, $\mathbf{e}_{i}\in\mathbb{R}^{N}$ are orthonormal and $\tilde{\mathbf{V}}_{\alpha i}=\mathbf{f}_{\alpha}\circ\mathbf{e}_{i}\in\mathbb{R}^{M\times N}$.

The CP decomposition factorizes a tensor into a sum of component rank-one tensors, which describe the underlying features of each order. Although approximated algorithms are implemented to obtain the optimal decomposition, CP decomposition still achieves great success in real scenarios, such as feature extraction [32] and tensor-based PCA analysis [33]. A detailed discussion of tensor decomposition and its implementation in M-GSP are provided in Section VII-D. In Eq. (29), $\mathbf{f}_{\alpha}$ and $\mathbf{e}_{i}$ capture the features of layers and entities, respectively, which can be interpreted as the subspaces of the MLG. More discussions about the frequency interpretation of order-wise M-GSP spectrum and connections to MWGSP spectrum are presented in Section VII-C.

Note that, if there is only one layer in the multilayer graph, Eq. (29) reduces to the eigen-decomposition of a normal single-layer graph, i.e., $\mathbf{F}=\sum_{i=1}^{N}\lambda_{i}\mathbf{e}_{i}\circ\mathbf{e}_{i}$

With the decomposed representing tensor in Eq. (29), the order-wise MLG spectrum is defined as follows.

With the definition of order-wise MLG spectral pair, we now explore their properties. Considering $\tilde{\mathbf{V}}_{\alpha i}=\mathbf{f}_{\alpha}\circ\mathbf{e}_{i}$, we have the following property, which indicates the availability of a joint MLG analysis based on order-wise spectrum.

This property indicates the relationship between the order-wise MLG spectral pair and the joint eigen-tensors.

By constructing a fourth-order tensor $\tilde{\mathbf{U}}_{\mathcal{F}}\in\mathbb{R}^{M\times N\times M\times N}$ with $\tilde{\mathbf{V}}_{\alpha i}$ as its elements, i.e., $[\tilde{U}_{\mathcal{F}}]_{\alpha i\beta j}=[\tilde{V}_{\alpha i}]_{\beta j}$, we can have the following property.

This property generalizes the orthogonality of the spectral tensor into a similar definition of matrix.

We now introduce the order-wise MLG spectral transform. Similar to Eq. (24), the joint transform can be defined as

Note that each element of $\hat{\mathbf{s}}$ in Eq. (37) can be calculated as

Let $\mathbf{E}_{f}=[\mathbf{f}_{1}\cdots\mathbf{f}_{M}]\in\mathbb{R}^{M\times M}$ and $\mathbf{E}_{e}=[\mathbf{e}_{1}\cdots\mathbf{e}_{N}]\in\mathbb{R}^{N\times N}$. We then have

with each element

Clearly, the M-GFT can be obtained as

Then, we have the following definition of M-GFT based on order-wise spectrum.

If there is only one layer in the multilayer graph, the M-GFT calculated with $\mathbf{s}^{T}\in\mathbb{R}^{N}$ as $(\hat{\mathbf{s}}_{N})^{\mathrm{T}}=(\mathbf{s}\mathbf{E}_{e})^{\mathrm{T}}\in\mathbb{R}^{N}$, which has the same form as the traditional GFT in Eq. (2).

In addition, since $\mathbf{f}_{\alpha}$ and $\mathbf{e}_{i}$ are orthonormal basis of undirected MLG, the inverse M-GFT can be calculated as

Different from joint MLG Fourier space in Section V-A, the order-wise MLG spectrum provides an individual analysis on layers and entities separately, and a reliable approximated analysis on the underlying MLG structures jointly. To minimize confusion, we abbreviate joint M-GFT in Eq. (24) as M-JGFT. M-GFT refers to the order-wise transform in Eq. (46) in the remaining parts if there is no specification.

In addition to the eigen-decomposition, the singular value decomposition (SVD) is another important decomposition to factorize a matrix. In this part, we provide the higher-order SVD (HOSVD) [25] of the representing tensor as an alternative definition of spectrum for the multilayer graphs.

Given the multilayer graph $\mathcal{M}=\{\mathcal{V},\mathcal{L},\mathbf{F}\}$ with $M$ layers and $N$ nodes in each layer, its representing tensor $\mathbf{F}\in\mathbb{R}^{M\times N\times M\times N}$ can be decomposed via HOSVD as

where $\mathbf{U}^{(n)}=[\mathbf{U}^{(n)}_{1}\quad\mathbf{U}^{(n)}_{2}\quad\cdots\quad\mathbf{U}^{(n)}_{I_{n}}]$ is a unitary $(I_{n}\times I_{n})$ matrix, with $I_{1}=I_{3}=M$ and $I_{2}=I_{4}=N$. $\mathbf{S}$ is a complex $(I_{1}\times I_{2}\times I_{3}\times I_{4})$-tensor of which the subtensor $\mathbf{S}_{i_{n}}$ obtained by fixing $n$th index to $\alpha$ have

• •

  $<\mathbf{S}_{i_{n}=\alpha},\mathbf{S}_{i_{n}=\beta}>=0$ where $\alpha\neq\beta$.

• •

  $||\mathbf{S}_{i_{n}=1}||\geq||\mathbf{S}_{i_{n}=2}||\geq\cdots\geq||\mathbf{S}_{i_{n}=I_{n}}||\geq 0$.

The Frobenius-norms $\sigma_{i}^{(n)}=||\mathbf{S}_{i_{n}=i}||$ is the $n$-mode singular value, and $\mathbf{U}^{(i)}$ are the corresponding $n$-mode singular vectors. For an undirected multilayer graph, the representing tensor is symmetric for every 2-D combination. Thus, there are two modes of singular spectrum, i.e., $(\gamma_{\alpha},\mathbf{f}_{\alpha})$ for mode $1,3$, and $(\sigma_{i},\mathbf{e}_{i})$ for mode $2,4$. More specifically, $\mathbf{U}^{(1)}=\mathbf{U}^{(3)}=(\mathbf{f}_{\alpha})$ and $\mathbf{U}^{(2)}=\mathbf{U}^{(4)}=(\mathbf{e}_{i})$. Since the joint singular tensor captures the consistent information of entities and layers, it can be calculated as

Note that the diagonal entries of $\mathbf{S}$ are not the eigenvalues or frequency coefficients of the representing tensor in general. The multilayer graph singular space is defined as follows.

Similar to order-wise spectral analysis in Section V-B, we can define the MLG singular tensor transform (M-GST) based on the singular tensors as follows.

Compared to the eigen-tensors in Eq. (22), the singular tensors come from the combinations of the singular vectors, thus are capable of capturing information of layers and entities more efficiently. Eigen-decomposition, however, focuses more on the joint information and approximate the separate information of layers and entities. We shall provide further discussion on the performance of different decomposition methods in Section VII-D. The intuition of applying HOSVD in MLG analysis and its correlations to GSP are also provided in Section VII-A3.

In traditional GSP, the frequencies are defined by the eigenvalues of the shift, whereas the total variation is an alternative measurement of the order of the graph frequencies [3]. Similarly, we use the total variation of $\lambda_{\alpha i}$ based on the spectral tensors to rank the MLG frequencies. Let $|\lambda|_{max}$ be the joint eigenvalue of the adjacency tensor $\mathbf{A}$ with the largest magnitude. The M-GSP total variation is defined as follows:

where $||\cdot||_{1}$ is the element-wise $l_{1}$ norm. Other norms could also be used to define the total variation. For example, the $l_{2}$ norm could be efficient in signal denoising [3]. The graph frequency related to $\lambda_{\alpha i}$ is said to be a higher frequency if its total variation $TV(\mathbf{V}_{\alpha i})$ is larger, and its corresponding spectral tensor $\mathbf{V}_{\alpha i}$ is a higher frequency spectrum. If the representation tensor refers to Laplacian tensor, i.e., $\mathbf{L=D-A}$, the frequency order is in contract to the adjacency tensor $\mathbf{A}$ as GSP [3]. We shall provide more details on interpretation of MLG frequency in Section VII-A.

Polynomial filters are basic filters in GSP [7, 34]. In M-GSP, first-order filtering consists of basic signal filtering, i.e.,

Similarly, a second order filter can be defined as additional filtering on first-order filtered signal, i.e.,

whose entries $s_{\alpha i}^{\prime\prime}$ are calculated as