On the Stability of Low Pass Graph Filter With a Large Number of Edge
  Rewires
  Recently, the stability of graph filters has been studied as one of the key
theoretical properties driving the highly successful graph convolutional neural
networks (GCNs). The stability of a graph filter characterizes the effect of
topology perturbation on the output of a graph filter, a fundamental building
block for GCNs. Many existing results have focused on the regime of small
perturbation with a small number of edge rewires. However, the number of edge
rewires can be large in many applications. To study the latter case, this work
departs from the previous analysis and proves a bound on the stability of graph
filter relying on the filter's frequency response. Assuming the graph filter is
low pass, we show that the stability of the filter depends on perturbation to
the community structure. As an application, we show that for stochastic block
model graphs, the graph filter distance converges to zero when the number of
nodes approaches infinity. Numerical simulations validate our findings.
