# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 7 Approximation of Graph Filtering  
The main workhorse of graph signal processing is graph filtering. In many instances of the GSP field, we appreciate the _distributable_ capabilities of a graph filter. However, this term is only applicable when the communication graph matches the data graph. When all the data resides on a single location, e.g., centralized data management, a distributed graph filter does not necessarily lead to an efficient distributed implementation, i.e., a parallel-friendly computation. As noticed in [5], the main bottleneck of the polynomial graph filter implementation is the queuing effect when performing local computations, i.e., performing a dense matrix-vector multiplication might end up more efficient than sequential sparse matrix-vector multiplications (queuing effect). In [5], the authors propose to compute support-disjoint sparse matrices to perform an approximate GFT. This somehow effectively alleviates the queuing problem as the different matrix-vector multiplications can be carried out in parallel. However, despite that this approach provides a parallel-friendly model for data processing, it still requires a shared memory location, i.e., the matrices operate over the full data vector regardless of the matrix support. Data most of the time is _geographically restricted_. That is, the transmission and storage of data are usually constrained by the distance to the source. For example, although it is possible to mirror all possible information from different networks in different geographical regions, their storage is often local, i.e., the most accessed data is usually related to the local region (the last use/generated--first fetch principle for caching). Therefore, it makes sense to keep processing local as well and establish a hierarchical  
Figure 6: Illustration of the method for the Minnesota graph, a close-to-planar graph. (**a**) Comparison of the true (red) and approximate (green) spectrum of its Laplacian matrix. (**b**) Comparison of the true (red) and approximate (green) cumulative spectral density of the Laplacian spectrum. (**c**) Minnesota graph with partition obtained by the graph separator. Figure 7: (**a**) Absolute value of inner products between the approximate, \(\hat{\mathbf{U}}\), and the true graph modes, i.e., \(||\hat{\mathbf{U}}^{T}\mathbf{U}||_{ij}|\). (**b**) Absolute value of the approximate diagonalization of the original Laplacian, i.e., \(||[\hat{\mathbf{U}}^{T}\mathbf{L}\hat{\mathbf{U}}]_{ij}|\). (**c**) Comparison of the original permuted graph (red and blue) and its block diagonal approximation (blue). processing chain to minimize both the data management and communication protocol complexity. Luckily, the previously discussed recursive graph partition provides an alternative to deal with data processing in such domains. This is due to the fact that geographically restricted data, usually spawn from social relations or sensor networks, can be (approximately) modeled using planar or geometrical graphs which are structured graphs admitting good recursive graph separators. Examples for such networks can be found in traffic networks or range-limited transmission wireless networks, as discussed in Section 3. To leverage the recursive decomposition presented in Section 5 for fast approximate graph filtering, we propose to use this hierarchical graph decomposition to compute disjoint graph filters that can be solved locally within the localized node clusters given by the partition. More specifically, we can state this in the following way. Considering a graph \(\mathcal{G}\), and a hierarchical decomposition \(\mathcal{T}\) [cf. Figure 3]. We approximate the _action_ of a desired shift-invariant graph filter [37], \(\mathbf{H}\), defined by a set of \(K\) polynomial coefficients \(\{\alpha_{k}\}_{k=0}^{K}\) and a graph matrix representation \(\mathbf{S}\), e.g., graph shift-operator in GSP [1] using the structure in \(\mathcal{T}\).