# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 7 Approximation of Graph Filtering
That is, we approximate \(\mathbf{y}=\mathbf{H}\mathbf{x}\) with  
\[\tilde{\mathbf{y}}=\text{merge}(\{\mathbf{H}_{t}\mathbf{x}_{t}\}_{t\in\text{leafs}( \mathcal{T})}) \tag{8}\]  
where \(\mathbf{H}_{t}\) and \(\mathbf{x}_{t}\) are the shift-invariant graph filter and the graph signal partition associated with the leaf \(t\) of the partition \(\mathcal{T}\), respectively. Here, the simplest merge operation could be just the union of the result of the disjoint node partitions, however, more complex merging routines are possible. In the following theorem, we provide the first result in approximate graph filters by means of graph bisection for the union merging routine and for a generic matrix representation of the graph, \(\mathbf{S}\), typically known within GSP as the _graph shift operator_, see, e.g., [2]. **Theorem 5**. : _Let \(\mathcal{G}\) be a graph, \(\mathbf{S}\) its matrix representation satisfying \(\|\mathbf{S}\|_{2}<1\) and \(\mathbf{H}=\sum_{k=0}^{K}\alpha_{k}\mathbf{S}^{k}\) a graph filter defined on \(\mathcal{G}\) such that \(\|\mathbf{H}\mathbf{x}\|_{2}=\|\mathbf{x}\|_{2}\), where \(\mathbf{x}\) is a signal defined over the nodes of \(\mathcal{G}\). Then, the block diagonal matrix \(\tilde{\mathbf{S}}\), obtained by the bisection of \(\mathcal{G}\) and removal of the connections between the connected components, can implement a graph filter \(\tilde{\mathbf{H}}=\sum_{k=0}^{K}\alpha_{k}\tilde{\mathbf{S}}^{k}\), over the induced graph \(\tilde{\mathcal{G}}\) such that_  
\[\frac{\|\mathbf{H}\mathbf{x}-\tilde{\mathbf{H}}\mathbf{x}\|_{2}}{\|\mathbf{H}\mathbf{x}\|_{2}}= \mathcal{O}(\epsilon), \tag{9}\]  
_where \(K\) is the order of the graph filter and \(\epsilon\triangleq\|\mathbf{S}-\tilde{\mathbf{S}}\|_{2}\)._  
Proof. : See Appendix F.  
This result shows that even for graphs with good partitions, there is no straightforward asymptotic efficient approximation for graph filtering. However, it encourages its use for the families presented in this work as the growth rate of the error is not fast. That is, by inspection it can be seen that \(\epsilon\) is directly proportional to the graph edit distance, i.e., if \(\mathbf{S}\) is considered a scaled adjacency matrix then \(\epsilon\) can be directly upper bounded with the Frobenius norm which translates to the edit distance. Hence, for the family \(\mathcal{S}_{1/2}^{\prime}\) the error grows at most following a square-root law in the size of the graph. Numerical experiments in the next section illustrate this behavior. From the result of Theorem 5, where a single bisection is considered (\(d=1\)), we can expect that for higher order recursions, i.e., decomposition depth, the graph filter approximation quality degrades further. The reason for this issue is that the difference between the approximation error of the matrix representation of the graph only worsens with increasing decomposition depth. Hence, a _stitching_ method is required in order to improve the approximation at the cost of increasing the communication and implementation cost of the method. This is left for immediate future research, where the low-rank structure of the off-diagonal blocks, guaranteed by the separator theorem, can be leveraged to obtain a better merging strategy than only working on the leaves of the decomposition.