# How likely is a random graph shift-enabled?

Liyan Chen, Samuel Cheng1, Vladimir Stankovic, and Lina Stankovic L. Chen is
with Key Laboratory of Oceanographic Big Data Mining & Application of Zhejiang
Province, Zhejiang Ocean University, Zhoushan, Zhejiang 316022, China and the
Department of Computer Science and Technology, Tongji University, Shanghai,
201804 China (e-mail: chenliyan@tongji.edu.cn).S. Cheng is with the School of
Electrical and Computer Engineering, University of Oklahoma, OK 74105, USA
(email: samuel.cheng@ou.edu).V. Stankovic and L. Stankovic are with Department
of Electronic and Electrical Engineering, University of Strathclyde, Glasgow,
G1 1XW U.K. (e-mail:{vladimir.stankovic, lina.stankovic}@strath.ac.uk).1
Corresponding author.

###### Abstract

The shift-enabled property of an underlying graph is essential in designing
distributed filters. This article discusses when a random graph is shift-
enabled. In particular, popular graph models Erdős–Rényi (ER), Watts–Strogatz
(WS), Barabási–Albert (BA) random graph are used, weighted and unweighted, as
well as signed graphs. Our results show that the considered unweighted
connected random graphs are shift-enabled with high probability when the
number of edges is moderately high. However, very dense graphs, as well as
fully connected graphs, are not shift-enabled. Interestingly, this behaviour
is not observed for weighted connected graphs, which are always shift-enabled
unless the number of edges in the graph is very low.

###### Index Terms:

graph signal processing, shift-enabled graphs, undirected graph, random graph.

##  I Introduction

Graph signal processing (GSP) extends classical digital signal processing to
signals on graphs and provides a promising solution to numerous real-world
problems that involve data defined on topologically complicated domains [1].
For large graphs, graph signals need to be processed in a distributed rather
than centralized manner [2]. That is, a graph node may only have access to
graph signals acquired by nodes in its physical proximity. Furthermore, for
large graphs with millions of nodes, a centralised implementation of the graph
filter [3], [4] through direct matrix multiplication is computationally
intractable [5, 6]. Thus to make the graph filtering feasible, it is necessary
to perform the filtering operation locally [2]. For practical design purposes,
it is necessary to be in a position to decompose graph filters in a form of
polynomial of a shift matrix, of graph shift operator, $S$, that uniquely
defines graph topology (for example, graph adjacency or Laplacian matrix) [7],
[8]. However, not all graph filters can be represented as polynomials of the
shift matrix111The importance of this polynomial representation has been
reiterated in a recent survey paper [4]..

Given a graph, necessary conditions for a graph filter to be representable as
a polynomial of the graph shift matrix is discussed in [1] and [9], where the
notion of _shift-enabled_ graph is introduced as a graph where any shift-
invariant filter $H$ can be represented as a polynomial of the shift matrix.
It is shown in [1] and [9] that the shift-enabled condition [1] is important
for both directed and undirected graphs, and hence it needs to be taken into
account.

This paper focuses on finding a likelihood for a random graph to be shift
enabled. This problem has received relatively little attention in the research
community, since most researchers currently assume that the shift-enabled
condition simply holds or ignore the condition completely. To illustrate “how
likely is a graph shift-enabled”, we discuss the probability that some classic
random graphs are shift-enabled. In particular, the main contribution of this
paper is characterising the bahaviour of the probability that:

  * •

an unweighted random Erdős–Rényi (ER) graph, Watts–Strogatz (WS) graph and
Barabási–Albert (BA) graph is shift-enabled as a function of graph parameters;

  * •

the above three weighted random graphs are shift-enabled, where the weights
are generated based on exponential and Gaussian distribution;

  * •

a random signed graph is shift-enabled;

  * •

the analysis of the above results.

Our results show that the considered unweighted connected random graphs are
shift-enabled with high probability when the number of edges is moderately
high. However, very dense graphs, as well as fully connected graphs, are not
shift-enabled. Interestingly, this behaviour is not observed for weighted
connected graphs, which are always shift-enabled unless the number of edges in
the graph is very low.

The outline of the paper is as follows. Section II describes the basic
concepts and fundamental properties of a shift-enabled graph. Section III
provides the main results of the paper for unweighted graphs, that is, the
characterisation of the behaviour of the probability that a graph is shift
enabled. Section IV extends the results to weighted and signed graphs. Section
V concludes the paper.

##  II Basic concepts and properties of shift-enabled graphs

In this section, we introduce our notation and briefly review the concepts of
shift-enabled graphs and their properties relevant to this article. For more
details, see [2, 10, 3, 7].

Let $\mathcal{G}=(V,E,W)$ be a graph, where $V=\\{v_{1},v_{2},\cdots,v_{N}\\}$
is the vertex set, and $E\subset\\{1,\cdots,N\\}\times\\{1,\cdots,N\\}$ is the
edge set in which $(i,j)\in E$ if vertex $v_{i}$ and vertex $v_{j}$ have a
link. $W=(w)_{i,j=1}^{N}$ is the weighted adjacency matrix, in which $w_{i,j}$
represents the weight of the edge $(i,j)\in E$. Throughout this article, a
graph $\mathcal{G}$ is assumed to be simple, i.e. a finite, graph without
loops and/or multiple edges. Let $D=diag(D_{1},\cdots,D_{n})$, with
$D_{i}=\sum_{j=1}^{N}w_{i,j}$, be the degree matrix of $\mathcal{G}$[11].

The graph is shift-enabled if its shift matrix $S$ (see Remark 2 below)
complies with the following definition.

######  Definition 1 (Shift-enabled graph [1, 7]).

A graph ${\mathcal{G}}$ is shift-enabled if its corresponding shift matrix $S$
satisfies $p_{S}(\lambda)=m_{S}(\lambda)$, where $p_{S}(\lambda)$ and
$m_{S}(\lambda)$ are the minimum polynomial and the characteristic polynomials
of $S$, respectively. We also say that $S$ is shift-enabled when the above
condition is satisfied. Otherwise, $S$ and the corresponding graph, are non-
shift-enabled.

######  Remark 1.

The shift-enabled condition ($p_{S}(\lambda)=m_{S}(\lambda)$) is equivalent to
the condition that each Jordan block of the Jordan normal form of the shift
matrix has a distinct eigenvalue (see Proposition 6.6.2 in [12]).
Consequently, for real symmetric matrices, the above condition naturally
degenerates to the condition that all eigenvalues have to be distinct (see
details in Lemma 1).

######  Remark 2.

The graph adjacency matrix $A$, Laplacian $L=D-W$, the normalized Laplacian
matrix $\mathcal{L}=L^{-1/2}DL^{-1/2}$, the signless Laplacian matrix
$L^{+}=D+W$ and the probability transition matrix $T=D^{-1}W$ are generally
chosen as the graph shift operator or graph shift matrix [2, 10, 3, 13]. Here,
we use $S$ to denote the general shift matrix and select Laplacian matrix as
the shift matrix for the specific discussion in Section III and Section IV,
since Laplacian matrix is one of most popular shift matrix [13, 14, 15]. Most
of the conclusions in this paper, however, apply to other shift matrices (see
Figure 4).

For shift-enabled graphs, we have the following result.

######  Theorem 1.

The shift matrix $S$ is shift-enabled if and only if every matrix $H$
commuting with $S$ is a polynomial in $S$ [7].

A graph filter $H$ is linear shift-invariant (LSI) if $H$ commutes with shift
matrix $S$ ($HS=SH$). That is, the shifted and filtered operations are
commuted, i.e., the shifted filtered output is the same as filtered output of
a shifted input. Theorem 1 implies that an LSI filter naively designed cannot
always be represented as a polynomial of shift operators as is the case in
classical DSP; that is, as mentioned in Section I, whether the graph is
directed or undirected, the shift-enabled condition is important. Thus, it is
interesting to investigate “how likely is a graph shift-enabled?”. The next
section gives the answers for commonly used random graphs.

##  III Unweighted random graphs

In this section we focus on classic random unweighted graphs, namely, we will
consider ER, WS (small world model), and BA graphs (scale-free model), and
calculate probability $p$ that the random graph is shift enabled. We examine
how $p$ depends on the parameters used to generate the graph.

###  III-A Generic Random Graphs Models

Figure 1: Examples of generic random graph models with $N$=50 nodes. (a) ER
graph with the probability of generating edges $P=0.5$. ER random graph has no
central node, and most nodes are evenly connected. (b) WS graph with average
degree $K=4$ and rewriting probability $\beta=0.5$. WS graph has small-world
properties, including short average path lengths and high clustering. (c) BA
graph with the initial number of nodes $m_{0}=5$ and the number of edges for
each node addition $m=4$. BA graph is a scale-free network, in which the
connections between nodes are severely unevenly distributed: a few nodes in
the network called Hub points have extremely many connections, while most
nodes have only a small number of connections.

####  III-A1 Erdős–Rényi random graph (Figure 1 (a))

The Erdős–Rényi (ER) random graph is often used to model many real-world
inference problems, and it has been used in the context of graph filter
design, e.g., in [8], [16] and [17]. The ER graph topology can be defined in
two ways [18] as:

  * •

$\mathcal{G}(N,P)$ where $N$ and $P$ denote the number of nodes and the
probability that an edge is present, respectively.

  * •

$\mathcal{G}(N,M)$ where $M$ is the number of edges, which are randomly
distributed in the graph.

The relationship between the two models is $P=M/\binom{N}{2}$, and the two
models are asymptotic equivalent as $N$ increase (Theorem 1.4 in Ref. [18]).

####  III-A2 Watts-Strogatz random graph (Figure 1 (b))

The Watts-Strogatz (WS) model is a classic random graph generation model which
produces graphs with small-world properties [19]. WS graph has three
parameters, $N$, $K$ and $\beta$, and is denoted as
$\mathcal{G}=WS(N,K,\beta)$ where $N$ is the number of nodes, $K$ is the
average degree of nodes, and $\beta$ is the rewriting probability. If
$\beta=0$ WS graph is a regular ring lattice in which each node is connected
to the nearest $K$ nodes, and if $\beta=1$, the WS graph becomes an ER graph.

####  III-A3 Barabási–Albert random graph (Figure 1 (c))

The Barabási–Albert (BA) model is an algorithm for generating random scale-
free networks using a preferential attachment mechanism. It can model many
practical scale-free networks such as the World Wide Web, citation networks
and social networks. In contrast to the ER and the WS models, the BA model is
scale-free, and the connections between the nodes are severely unevenly
distributed: a few nodes in the network, called Hub points, have extremely
many connections, while most other nodes have only a small number of
connections. The BA random model has three parameters: the number of nodes
$N$, the initial number of nodes $m_{0}$, and the number of edges for each
node addition $m$, $m\leq m_{0}$, and is denoted by
$\mathcal{G}=BA(N,m_{0},m)$. New nodes are added according to the priority
strategy $-$ “the more connections between nodes, the greater the possibility
of receiving a new link” [20, 21, 22].

###  III-B Shift-enabled properties of ER graphs

Figure 2 shows the probability $p$ that an ER graph $\mathcal{G}(N,M)$ is
shift-enabled as a function of the number of edges $M$. The simulation results
are provided for $N$=50 nodes and the results are averaged over $10^{5}$ runs.
From the figure, we can identify three distinct regions: Region 1: a very
small $M$ where $p$ is zero; Region 2: the flat region when $p$ reached the
maximum close to 1; Region 3, where $p$ drops to 0 for very large $M$,
following a symmetric trend to Region 1.

Next, based on these heuristic findings, we separately treat the three
regions. We fix the number of nodes $N$ and change the number of edges $M$,
and theoretically analyse the behaviour of the probability $p$ that the
resulting graph is shift-enabled.

Figure 2: The shift-enabled probability of the unweighted ER graph with $N$=50
nodes: probability that the graph is shift-enabled $p$ vs. the number of edges
$M$.

####  III-B1 Region 1 $-$ $M$ is small

In this region, based on the following theorem, the probability of a graph
being shift-enabled is always zero.

######  Theorem 2.

If a graph $\mathcal{G}$ is unconnected then the shift matrix is not shift-
enabled.

###### Proof.

Assume $\mathcal{G}$ has two unconnected components ${\mathcal{G}}_{1}$ and
${\mathcal{G}}_{2}$, with corresponding Laplacian matrices $L_{1}$ and
$L_{2}$, respectively. Since both $L_{1}$ and $L_{2}$ have an eigenvalue equal
to zero, $L$, the Laplacian matrix of $\mathcal{G}$ will have the eigenvalue 0
with at least the multiplicity of two. Therefore, based on Lemma 1,
$\mathcal{G}$ is non-shift-enabled. ∎

Since an $N$-node connected graph has at least $N-1$ edges, we have the
following corollary.

######  Corollary 1.

If $M\leq N-2$ then the shift matrix $L$ of graph $\mathcal{G}$ is non-shift-
enabled.

According to Corollary 1 the probability of a graph being shift-enabled is
$p=0$ when $M$ is small with respect to $N$, that is, when $M\leq N-2$.

####  III-B2 Region 2 $-$ Moderate $M$

The following theorem shows that when $N$ is sufficiently large, and the
probability that an edge is present $P$ is far from 0 and 1 (alternatively,
$M$ is moderately large) then the eigenvalues of Laplacian matrix are
distinct. The uniqueness of the eigenvalues guarantees the shift-enable
property by Lemma 1.

######  Theorem 3 (Distinct eigenvalue, Theorem 1.3 in Ref. [23]).

Let $\mathcal{G}$ be a connected graph and $X_{N}=(x_{i,j})_{1\leq i,j\leq N}$
be an $N\times N$ real symmetric random matrix in which the upper-triangular
entries $x_{i,j}(i<j)$ are independent ((see Remark 3 (a)) and have non-
trivial distribution for some fixed $\mu>0$ (see Remark 3 (b)). Furthermore,
$x_{i,i}$ are independent of the upper diagonal entries $x_{i,j}(1\leq i<j\leq
N)$ (see details in Remark 3 (c)). Then for every fixed constant $c>0$ and $N$
sufficiently large (depending on $c$ and $\mu$), the eigenvalues of $X_{N}$
are distinct with probability at least $1-N^{-c}$. That is, for sufficiently
large $N$, the probability that the eigenvalues of $X_{N}$ are distinct tends
to 1.

Figure 3: For an ER graph, the relationship between the probability that the
graph is connected (red line) and the shift-enabled probability $p$ (blue
line). The horizontal axis shows the number of the edges $M$ and the vertical
axis is the probability $p$. (a) $N$=5 nodes; (b) $N$=10 nodes; (c) $N$=15
nodes.

######  Remark 3.

(a) The upper-triangular entries are independent since we focus on randomly
generated graphs. (b) Non-trivial distribution222A real-valued random variable
$\xi$ is non-trivial if there is a fixed $\mu>0$ such that $Pr\\{\xi=x\\}\leq
1-\mu$ (see Equation (1) in Ref. [23]). \- elements in Laplacian matrix of an
ER graph are non-trivial if $P$ (the probability that an edge is present)
stays bounded away from both 0 and 1. If $P=0$ or $P=1$, the entries in the
graph Laplacian matrix have trivial distribution, and Theorem 3 is not
applicable. (c) Since $x_{i,i}=0$ for $1\leq i\leq N$, diagonal entries
$x_{i,i}$ are independent of the upper diagonal entries.

As a result, the eigenvalues of Laplacian matrix are distinct (the graph is
shift-enabled, hence $p=1$) when the number of nodes $N$ is large enough, and
the number of edges $M$ is moderately large (very large $M$ implies $P$ close
to zero, where Theorem 3 does not hold).

Our experiments show that the behaviour of $p$ is very similar to the
probability of a random graph being connected (see Figure 3). Combining
Theorem 2, Theorem 3 and the relation between shift-enabled and connected
graphs, we claim that $p$ is close to 1 in Region 2, when the number of nodes
$N$ is large and the probability of an edge is bounded away from 0 and 1. When
$N$ is very small, Theorem 3 does not hold; indeed, it can be seen from Figure
3 that $p$ does not reach 1 for $N$=5 and 10.

####  III-B3 Region 3 $-$ Very large $M$

We analyse Region 3, that is, the case of very large $M$, by looking graph
complement and showing that a graph ${\mathcal{G}}$ and its complement
${\mathcal{G^{C}}}$ have the same shift-enabled probability. Let
$L_{\mathcal{G}}$ and $L_{\mathcal{G^{C}}}$ denote the Laplacian matrix of
${\mathcal{G}}$ and its complement ${\mathcal{G}^{C}}$, respectively. The
following theorem gives the condition that $\mathcal{G}$ and its complement
have the same shift-enabled property.

######  Theorem 4.

If for an $N$-node random graph $\mathcal{G}$, $N$ is not an eigenvalue of $L$
then $\mathcal{G}$ is a shift-enabled graph if and only if $\mathcal{G}^{C}$
is a shift enabled graph.

###### Proof.

By Lemma 3, if $N$ is not an eigenvalue of $L$ then $\mathcal{G}^{C}$ is a
connected graph. To prove the sufficiency, let
$Spec(L_{\mathcal{G}})=(\lambda_{1},\lambda_{2},\cdots,\lambda_{N-1},\lambda_{N}=0)$.
Then,
$Spec(L_{\mathcal{G^{C}}})=(N-\lambda_{1},N-\lambda_{2},\cdots,N-\lambda_{N-1},0)$
by Lemma 2.

If $\mathcal{G}$ is a shift-enabled graph, then $\lambda_{i}\neq\lambda_{j}$
according to Lemma 1. If in addition $N$ is not the eigenvalue of $L$, it can
be readily concluded that $N-\lambda_{i}\neq N-\lambda_{j}$ and
$N-\lambda_{k}\neq 0$ ($1\leq i<j\leq N-1$, $1\leq k\leq N-1$), i.e., all
eigenvalues in $L_{\mathcal{G}^{C}}$ are distinct. Consequently,
$\mathcal{G}^{C}$ is a shift-enabled graph by Lemma 1.

The necessity can be easily proven in the same way. To sum up, $\mathcal{G}$
is a shift-enabled graph if and only if $\mathcal{G}^{C}$ is a shift-enabled
graph. ∎

######  Corollary 2.

If $N$ is not an eigenvalue of $L$, then, for very large number of edges
relative to the number of nodes $N$ ($M>N(N-1)/2-N+2$) the graph is non-shift-
enabled.

Based on Theorem 4, the behaviour of $p$ for $\mathcal{G}$ and
$\mathcal{G}^{C}$ is symmetric. Since based on Corollary 1, $\mathcal{G}^{C}$
is non-shift-enabled when its number of edges is smaller or equal to $N-2$,
then, in Region 3, for a very large number of edges, $\mathcal{G}$ is also
non-shift-enabled. Note that this implies that fully connected ER graphs are
non-shift-enabled. Indeed, as we know, the eigenvalues of a fully connected
graph are ${\\{-1\\}}^{N-1}$ (the multiplicity of $-1$ is $N-1$) and $N-1$,
which ensures that the graph is not shift enabled.

The conclusions can be extended to other commonly used shift matrices.

######  Remark 4.

Commonly used shift matrices of $\mathcal{G}$ are: adjacency matrix $A$,
Laplacian matrix $L$, normalized Laplacian matrix $\mathcal{L}$, signless
Laplacian matrix $|L|$ and probability transition matrix $T$ which have
similar shift-enabled property rules (see Figure 4 for an illustration).

Figure 4: $p$ vs. the number of edges $M$ in an ER random graph with $N$=50
nodes. Adjacency matrix $A$, Laplacian matrix $L$, normal Laplacian matrix
$\mathcal{L}$, signless Laplacian matrix $|L|$ and probability transition
matrix $T$ have similar shift-enabled properties.

###  III-C Shift-enabled properties of WS graphs

In the previous subsection we discussed how, for fixed $N$, $p$ changes as the
number of edges $M$ varies in ER graphs. For an $\mathcal{G}=WS(N,K,\beta)$
graph, in this subsection, we investigate how $p$ depends on WS parameters,
namely, $K$, the average degree of nodes and $\beta$ the rewriting
probability. Note that the number of edges is $M=N\dot{K}$. We separately
discuss two cases.

####  III-C1 The number of nodes $N$ fixed, and the average degree $K$ and
rewriting probability $\beta$ vary

Figure 5: The effect of $\beta$ on the shift-enabled probability $p$ of WS
graphs. Except for $\beta=0$ where WS graph is a regular ring lattice, the
similar conclusions as for ER graphs can be taken.

As shown in Figure 5, except for $\beta=0$ where the WS graph is a regular
ring lattice (see Theorem 5), the discussions related to the ER graphs in
Section III-B1 and Section III-B2 apply to WS graphs as well.

######  Theorem 5.

Regular ring lattice is non-shift-enabled when the shift matrix is Laplacian
matrix.

###### Proof.

Regular ring lattice is a special circulant graph in which each node is
connected to the nearest $K$ nodes. Let $A_{cir}$ denote an $N\times N$
circulant matrix whose first row is $[0,1,0,\cdots,0]$ and the adjacency
matrix of regular ring lattice is $A_{ring}$ whose first row is
$[0,\underbrace{{1,1,\cdots,1}}_{K},0,\cdots,0,\underbrace{{1,1,\cdots,1}}_{K}]$.
Then,

$A_{ring}={\sum_{j=1}^{K}A_{cir}^{j}}+{\sum_{j={N-K}}^{N-1}A_{cir}^{j}}.$

Since the eigenvalues of $A_{ring}$ are $1,\omega,\omega^{N-1}$, where
$\omega=exp(2\pi i/N)=\cos\frac{2\pi}{N}+i\sin\frac{2\pi}{N},$ it can be
easily concluded that the eigenvalues of $A_{ring}$ are

$\displaystyle\lambda_{j}$
$\displaystyle=\omega^{j}+\cdots+\omega^{Kj}+\omega^{(N-K)j}+\cdots+\omega^{(N-1)j}$
$\displaystyle=2[\cos\frac{2\pi j}{N}+\cos\frac{4\pi
j}{N}+\cdots+\cos\frac{2K\pi j}{N}],$

where $j=0,1,\cdots,N-1$ [24]. It follows that

$\displaystyle~{}~{}\lambda_{N-1}$
$\displaystyle=2[\cos\frac{2(N-1)\pi}{N}+\cos\frac{4(N-1)\pi}{N}+\cdots+\cos\frac{2K(N-1)\pi}{N}]$
$\displaystyle=2[\cos\frac{2\pi}{N}+\cos\frac{4\pi}{N}+\cdots+\cos\frac{2K\pi}{N}]$
$\displaystyle=\lambda_{1}.$

Generally, $\lambda_{0}=2K$ and $\lambda_{j}=\lambda_{N-j}$, for
$j=1,2,\cdots,\lfloor\frac{N-1}{2}\rfloor$ 333$\lfloor\frac{N-1}{2}\rfloor$
denotes rounding down $\frac{N-1}{2}$..

Furthermore, the Laplacian matrix of the regular ring lattice is
$L_{ring}=D_{ring}-A_{ring}$ and the degree matrix $D_{ring}=2K\times I_{N}$
444$I_{N}$ is an identity matrix of size $N\times N$.. Therefore, the
eigenvalues of $L_{ring}$ are $2K-\lambda_{j}$ for $i=0,1,\cdots,N$ and
$2K-\lambda_{j}=2K-\lambda_{N-j}$ for
$j=1,2,\cdots,\lfloor\frac{N-1}{2}\rfloor$. Then, according to Lemma 1, the
regular ring lattice is not shift enabled.

∎

####  III-C2 Rewriting probability $\beta$ fixed and the number of nodes $N$
and the average node degree $K$ vary

As shown in Figure 6, similarly to ER graphs, as the number of nodes
increases, the shift-enabled property tends to be stable and has the
properties discussed in Section III-B1 and Section III-B2.

######  Remark 5.

Note that, the symmetry in Section III-B3 is not as obvious in Figure 5 and
Figure 6 as it is in Figure 2. This is because the horizontal axis in WS graph
is the average $K$ which is a non-negative even number, while the horizontal
axis in Figure 5 is the number of edges $M$. The symmetry of $p$ of
$\mathcal{G}$ and $\mathcal{G}^{C}$ in Theorem 4 is discussed based on $M$.
$K$ and $M$ are linearly dependent via $K=M/N$.

Figure 6: The shift-enabled probability $p$ of WS graph as a function of $K$.
With the increase of the number of nodes, $p$ follows the same trends as for
ER graphs. (a) $N=$10 nodes. (b) $N=$20 nodes. (c) $N=$50 nodes.

###  III-D Shift-enabled properties of BA graphs

Figure 7: The effect of $m_{0}$ on the shift-enabled probability $p$ in a BA
graph with $N=50$. (a) $m_{0}=1$; (b) $m_{0}=25$;  Figure 8: The BA graph with
$m_{0}=1$ and $N=50$. As $m=1$ the graph is a tree graph, in which case the
main components of the random model contain only a small number of nodes.
Figure 9: BA graph: $p$ vs. the number of nodes $N$ for $m_{0}=m=1$.

In Figure 7, we fixed the total number of nodes $N$, and change the initial
number of nodes $m_{0}$ from 1 to $N$ to study the probability $p$ of a graph
being shift-enabled for a range of $m_{0}$ values. The BA graph used in the
experiment was generated by $gsp\\_barabasi\\_albert.m$ function available in
GSPBox [25]. Note that the total number of edges is $M=(N-m_{0})\times m$.
Since $m\leq m_{0}$, the maximum total number of edges is
$|M|_{max}=(N-m_{0})\times m_{0}$. For fixed $N$, $|M|_{max}$ is
$m_{0}=\frac{N}{2}$. We provide the results for $m_{0}=\frac{N}{2}=25$.

Based on Figure 7, we make the following conclusions:

  * •

As can be seen from Figure 7 (a), when $m_{0}=1$, the number of edges for each
node addition, $m$, can only be equal to 1 (since $m\leq m_{0}$). In this case
the graph is a tree graph (Figure 8), in which few nodes have many
connections, while most nodes have very few connections, which reflects the
scale-free feature of the BA graph. As shown in Figure 9, as the number of
nodes $N$ increases, the connectivity of the vertex is increasingly
concentrated, and the probability $p$ tends to 0.

  * •

When $m_{0}=25$ and $m=1$, $M=25<N-1=49$, the graph is unconnected and hence
$p=0$. As $m$ increases, the probability that the graph is connected
increases, and as a result, $p$ increases.

##  IV Extension to Weighted and Signed graphs

In this section we extend the results to random weighted and signed graphs.

###  IV-A Weighted graphs

Many practical scenarios are modelled by weighted graphs, where Gaussian
distribution or Exponential distribution [26] are often used to define the
edge weights. Figures 10 and 11 show how $p$ varies with the number of edges
$M$ for the three considered random graph models with $N$=50 nodes.

Figure 10: The shift-enabled probability $p$ of weighted graphs with
exponentially distributed weights with $\lambda=10$. (a) ER graph; (b) WS
graph; (C) BA graph.

Figure 11: The shift-enabled probability $p$ of weighted graphs with Gaussian
distributed weights with $\mu=100$ and $\sigma=10$. (a) ER graph; (b) WS
graph; (C) BA graph.

######  Theorem 6.

Theorem 2, Corollary 1 and Theorem 3 still hold for weighted graphs.
Therefore, the probability $p$ of the graph being shift-enabled has the
following properties:

  * •

Region 1. The probability $p$ is $0$, when the number of edges $M$ is
relatively small which in accordance with Section III-B1 for an unweighted
graph.

  * •

Region 2. The probability $p$ is close to 1 when the number of edges increases
which is in accordance to Section III-B2.

In the last region, $p$ remains close $1$, which is different from the shift-
enabled probability behaviour of the unweighted graph. This is due to the
following theorem.

######  Theorem 7.

In the weighted graph, the probability $p$ is close to $1$ and does not drop
to zero for a large number of edges $M$.

###### Proof.

The results in Section III-B3 do no longer hold for the weighted graph since
Theorem 4 does not hold. Furthermore, the complements of weighted graph are
generally connected as the original graph is connected (Complement of
undirected weighted graph are defined in detail in Section 2.7.1 of Ref.
[27]), which implies that Theorem 3 still holds for the complement graph. So,
the probability $p$ remains close to $1$. ∎

Exponential distribution function $f(x)=\lambda e^{-\lambda x},(x>0)$ has one
parameter $\lambda$. As Figure 12 shows for $\lambda=0.1,1,10,100$, and the
parameter $\lambda$ has almost no effect on the shift-enabled properties.

Figure 12: ER graphs with the weights defined using exponential distribution.
The influence of parameter $\lambda$ on the shift-enabled probability $p$, for
an ER weighted graph with $N$=50 nodes. The horizontal axis shows the number
of edges $M$.

.

In Gaussian distribution, the distribution function
$f(x)={\frac{1}{\sigma{\sqrt{2\pi}}}}e^{-{\frac{1}{2}}\left({\frac{x-\mu}{\sigma}}\right)^{2}}$,
in which $\mu$ and $\sigma>0$ are mean and standard deviation of random
variable. The weight may be negative, and the graphs with negative weights are
called sign graphs which is discussed in Section IV-B. As Figure 13 shows,
(for positive weights) the parameters of Gaussian distribution have almost no
effect on the shift-enabled properties.

Figure 13: ER graphs with the weights defined using Gaussian distribution.
Probability $p$ vs the number of edges $M$ for three different values of (a)
$\mu$ (b) $\sigma$.

###  IV-B Signed Graphs

Up to now, only graphs with unweighted or positively weighted edges are
discussed. Some applications, however, involve signed graphs in which case
negative weights are admitted. In these cases, the negative edges are usually
used to measure the dissimilarity between nodes.

Signed graphs are widely used in social networks, in which case person
support/oppose each other, recommendation networks (likes/dislikes), and
biological networks (promote and inhibit relationships between neurons) [28,
29, 15]. This article studies the most simplest signed graphs with weights
equal to $1$ or $-1$ introduced by Harary [30] in 1953, to deal with social
relations including disliking, indifference, and liking. The results from the
previous section, can easily be extended to signed graphs.

The Laplacian matrix of signed graphs is defined as $L_{sign}=D_{sign}-W$,
where $D_{sign}=\sum_{j}|w_{ij}|$, i.e., the sum of the absolute weights of
incident edges [15, 31]. Signed graphs have two categories: balanced and
unbalanced graphs. A signed graph is balanced if the product of edge weights
around each cycle is positive [30]. Otherwise, the graph is unbalanced.
Balanced and unbalanced signed graphs have the distinct shift-enabled
properties. Next, the two cases are considered separately.

For balanced graphs, Laplacian matrix $L_{sign}$ has the following property.

######  Theorem 8 ([32]).

The eigenvalues of the Laplacian matrices of a balanced graph
$\mathcal{G}_{sign}$ and the corresponding unsigned graph $\mathcal{G}$ are
identical.

Based on this theorem it is easy to show the following shift-enabled
properties the signed graphs.

######  Theorem 9.

Balanced graphs and unbalanced graphs have the same shift-enabled properties
as the corresponding unsigned graphs and general random weighted graphs,
respectively.

###### Proof.

First of all, based on Lemma 1 and Theorem 8, it is obvious that a balanced
signed graph has the same shift-enabled properties as the corresponding
unsigned graph. In the considered case, the signed graph has weights $1$ and
$-1$. So, its shift-enabled properties are in accordance with the
corresponding unweighted graph (see Figure 14(a) for a simulation example).

For unbalanced graphs, it is easy to show that Theorem 6 and Theorem 7 still
hold, so its shift-enabled properties are in accordance with those of random
weighted graphs (see Figure 14(b)). ∎

######  Remark 6.

Random balanced graphs and unbalanced graphs are generated differently. A
usual way to generate a random unbalanced graph, is to start from an ER graph,
and then randomly replace all weights that are 1 by -1, i.e., to convert the
unsigned ER graph into a signed. Because balanced graphs require that the
product of edge weights around each cycle is positive, which is difficult to
satisfy when the number of edges is high, this method is not practical for
generating balanced graphs.

According to Lemma 4(3), a balanced signed graph can be generated in the
following way. Firstly, divide randomly the vertices into two sets $V_{1}$ and
$V_{2}$; then the weights of edges connecting two vertices that are both in
$V_{1}$ or both in $V_{2}$ are set to $1$; edges connecting one vertex from
$V_{1}$ with a vertex to $V_{2}$ are set to $-1$.

Figure 14: The shift-enabled properties of signed graph. Balanced graph has
the same shift-enabled properties as the corresponding unsigned graph.
Unbalanced graph‘s shift-enabled properties are in accordance with those of
general weighted graphs. $p$ vs. $M$, with $N$=50 nodes, for a signed (a)
Balanced; (b) Unbalanced graph.

##  V Conclusion

Recognising the importance of shift-enable property, the paper discusses when
a random graph is shift-enabled. The behaviour of the shift-enabled property
for weighted and unweighted graphs was discussed and the the design guidelines
that ensure the shift-enable property were given. A future direction is to
extend the findings to directed graphs and how to transform shift matrix when
the shift-enabled condition for $S$ is not satisfied. It is also interesting
to study if one may decompose non-shift-enabled graphs into shift-enabled
subgraphs, to optimize the design of the GSP filters.

## Appendix A

It is easily determined whether a graph is shift-enabled by the following
lemma.

######  Lemma 1.

If shift matrix $L$ is a real symmetric matrix, then $L$ is shift-enabled, if
and only if all eigenvalues of $L$ are distinct [4, 9].

Lemma 1 indicates that an undirected graph, which shift matrix is real
symmetric, is shift-enabled if and only if its eigenvalues are all distinct.

######  Lemma 2.

[33] Assume

$Spec(L_{\mathcal{G}})=(\lambda_{1},\lambda_{2},\cdots,\lambda_{N-1},\lambda_{N}=0),$

then

$Spec(L_{\mathcal{G^{C}}})=(N-\lambda_{1},N-\lambda_{2},\cdots,N-\lambda_{N-1},0).$

###### Proof.

Since $\lambda_{i}\neq 0$ for $i=1,\cdots,N-1$, $u=[1,1,\cdots,1]^{T}$ is the
only eigenvector of $L_{\mathcal{G}}$ with eigenvalue $0$. Let
$x_{1},x_{2},\cdots,x_{N-1}$ be the remaining eigenvectors of
$L_{\mathcal{G}}$. As $L_{\mathcal{G}}$ is symmetric and
$\lambda_{N}\neq\lambda_{i}$ for $i\neq N$, $u$ is orthogonal to
$x_{1},x_{2},\cdots,x_{N-1}$.

Let $L_{K_{N}}$ be the Laplacian matrix of a complete graph with $N$ vertices.
It is easily seen that

${}L_{\mathcal{G}}+L_{\mathcal{G}^{C}}=L_{K_{n}}=NI_{N}-J_{N},$ (1)

where $I_{N}$ and $J_{N}$ are identity matrix and all-1s matrix with $N$
vertices, respectively.

Therefore, according to Equation (1),

$L_{\mathcal{G}^{C}}x_{i}=(NI_{N}-J_{N}-L_{\mathcal{G}})x_{i}=Nx_{i}-J_{N}x_{i}-{\lambda}_{i}x_{i}=(N-{\lambda}_{i})x_{i},$

where $J_{N}x_{i}=0$ as $x_{i}$ is orthogonal to $u$. Thus,
$(N-{\lambda}_{i})\in Spec(L_{\mathcal{G}^{C}})$ for $i=1,\cdots,N-1$.

Finally, $0\in Spec(L_{\mathcal{G^{C}}})$ as $u=[1,1,\cdots,1]^{T}$ is still
an eigenvector of $L_{\mathcal{G}^{C}}$ with eigenvalue $0$. Hence,
$Spec(L_{\mathcal{G^{C}}})=(N-\lambda_{1},N-\lambda_{2},\cdots,N-\lambda_{N-1},0)$.
∎

######  Lemma 3.

[33] If $N$ is not the eigenvalue of $L_{\mathcal{G}}$, then $\mathcal{G}^{C}$
is a connected graph.

######  Lemma 4.

Let $\mathcal{G}$ be a connected signed graph, i.e., a graph whose non-zero
edge weights can take positive and negative values. The following conditions
are equivalent [34, 35, 15]:

  * (1)

$\mathcal{G}$ is balanced.

  * (2)

$L$ is positive definite, i.e., all the eigenvalues of $L$ are positive.

  * (3)

The vertices of $\mathcal{G}$ can be divided into two subsets: $V_{1}$ and
$V_{2}$, such that all edges connecting vertices that are both in $V_{1}$ and
all edges connecting the vertices that are both in $V_{2}$ are $+1$, whereas
the edges connecting a vertex in $V_{1}$ with a vertex in $V_{2}$ are $-1$.

## Acknowledgment

The authors thank Bochao Zhao and Kanghang He for helpful discussions. This
research was supported by the European Union’s Horizon 2020 research and
innovation programme under the Marie Sklodowska-Curie grant agreement number
734331, the National Key Research and Development Project under grant
2017YFE0119300 and general scientific research projects of Zhejiang Education
Department in 2020 under grant Y202044676.

## References

  * [1] L. Chen, S. Cheng, V. Stankovic, and L. Stankovic, “Shift-enabled graphs: Graphs where shift-invariant filters are representable as polynomials of shift operations,” _IEEE Signal Processing Letters_ , vol. 25, no. 9, pp. 1305–1309, 2018.
  * [2] A. Sandryhaila and J. M. Moura, “Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure,” _IEEE Signal Processing Magazine_ , vol. 31, no. 5, pp. 80–90, 2014.
  * [3] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE Signal Proc. Magazine_ , vol. 30, no. 3, pp. 83–98, 2013.
  * [4] A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [5] S. Segarra, A. G. Marques, and A. Ribeiro, “Optimal graph-filter design and applications to distributed linear network operators,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 15, pp. 4117–4131, 2017.
  * [6] M. Coutino, E. Isufi, and G. Leus, “Advances in distributed graph filtering,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 9, pp. 2320–2333, 2019.
  * [7] A. Sandryhaila and J. M. Moura, “Discrete signal processing on graphs,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [8] S. Segarra, A. G. Marques, G. Mateos, and A. Ribeiro, “Network topology inference from spectral templates,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 3, no. 3, pp. 467–483, 2017.
  * [9] L. Chen, S. Cheng, K. He, V. Stankovic, and L. Stankovic, “Undirected graphs: Is the shift-enabled condition trivial or necessary?” _IEEE Access_ , pp. 1–1, 2021.
  * [10] A. Sandryhaila and J. Moura, “Discrete signal processing on graphs: Frequency analysis,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 12, pp. 3042–3054, 2014.
  * [11] C. Poignard, T. Pereira, and J. P. Pade, “Spectra of laplacian matrices of weighted graphs: structural genericity properties,” _SIAM Journal on Applied Mathematics_ , vol. 78, no. 1, pp. 372–394, 2018.
  * [12] P. Lancaster and M. Tismenetsky, _The Theory of Matrices: with Applications_. Elsevier, 1985.
  * [13] A. Marque, S. Segarra, G. Leus, and A. Ribeiro, “Stationary graph processes and spectral estimation,” _IEEE Transactions on Signal Processing_ , vol. 65, pp. 5911–5926, 2017.
  * [14] X. Dong, D. Thanou, L. Toni, M. Bronstein, and P. Frossard, “Graph signal processing for machine learning: A review and new perspectives,” _IEEE Signal Processing Magazine_ , vol. 37, no. 6, pp. 117–127, 2020.
  * [15] T. Dittrich and G. Matz, “Signal processing on signed graphs Fundamentals and potentials,” _IEEE Signal Processing Magazine_ , vol. 37, no. 6, pp. 86–98, 2020.
  * [16] J. Mei and J. M. Moura, “Signal processing on graphs: Causal modeling of unstructured data,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 8, pp. 2077–2092, 2016.
  * [17] R. Nassif, C. Richard, J. Chen, and A. H. Sayed, “Distributed diffusion adaptation over graph signals,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2018, pp. 4129–4133.
  * [18] A. Frieze and M. Karoński, _Introduction to random graphs_. Cambridge University Press, 2015.
  * [19] D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks.” _Nature_ , 1998.
  * [20] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” _science_ , vol. 286, no. 5439, pp. 509–512, 1999.
  * [21] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” _Reviews of modern physics_ , vol. 74, no. 1, p. 47, 2002.
  * [22] A.-L. Barabási, “Network science,” _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , vol. 371, no. 1987, p. 20120375, 2013.
  * [23] T. Tao and V. Vu, “Random matrices have simple spectrum,” _Combinatorica_ , vol. 37, no. 3, pp. 539–553, 2017.
  * [24] J. TODD and C. WALL, “H. bass, jfc kingman, f. smithies.”
  * [25] N. Perraudin, J. Paratte, D. Shuman, L. Martin, V. Kalofolias, P. Vandergheynst, and D. K. Hammond, “Gspbox: A toolbox for signal processing on graphs,” _arXiv preprint arXiv:1408.5781_ , 2014.
  * [26] M. R. Spiegel, J. J. Schiller, R. A. Srinivasan, and M. LeVan, _Probability and statistics_. Mcgraw-hill, 2001, vol. 2.
  * [27] B. Hadorn. Graph Theory. (2016, September 11). [Online]. Available: http://www.xatlantis.ch/index.php/education/zeus-framework/15-graph-theory
  * [28] G. Cheung, W.-T. Su, Y. Mao, and C.-W. Lin, “Robust semisupervised graph classifier learning with negative edge weights,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 4, no. 4, pp. 712–726, 2018.
  * [29] C. Parisien, C. H. Anderson, and C. Eliasmith, “Solving the problem of negative synaptic weights in cortical models,” _Neural computation_ , vol. 20, no. 6, pp. 1473–1494, 2008.
  * [30] F. Harary _et al._ , “On the notion of balance of a signed graph.” _Michigan Mathematical Journal_ , vol. 2, no. 2, pp. 143–146, 1953.
  * [31] J.-B. Liu, J. Zhao, and Z.-Q. Cai, “On the generalized adjacency, laplacian and signless laplacian spectra of the weighted edge corona networks,” _Physica A: Statistical Mechanics and Its Applications_ , vol. 540, p. 123073, 2020.
  * [32] J. Kunegis, “On the spectral evolution of large networks,” 2011.
  * [33] R. Merris, “Laplacian matrices of graphs: a survey,” _Linear Algebra Its Applications_ , vol. 197-198, no. 2, pp. 143–176, 1994.
  * [34] T. Zaslavsky, “Signed graphs,” _Discrete Applied Mathematics_ , vol. 4, no. 1, pp. 47–74, 1982.
  * [35] Y. Hou, J. Li, and Y. Pan, “On the laplacian eigenvalues of signed graphs,” _Linear and Multilinear Algebra_ , vol. 51, no. 1, pp. 21–30, 2003.