# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 5 Divide-And-Conquer for Fast Graph Spectrum Estimation  
Conceptually, the proposed divide-and-conquer approach is straightforward. Starting from a large graph, we perform, recursively, bisections, i.e., partition the graph in two subgraphs, until the subgraphs are of a _manageable size_, i.e., computations are affordable. Then, the spectra of the reduced-size graphs are obtained and later _stitched_ bottom-up until the top level is reached. This approach is analogous to the divide-and-conquer approach used for computing the spectrum of tridiagonal matrices [30]. In this particular case, it is easy to see that the \"graph\" can be split directly in the \"middle\", i.e., in the middle of the rows and columns. The two parts are _approximately_ disjoint, hence after computing the spectrum of each part the two parts can be stitched to obtain an exact spectrum. Notice, that although we use the term \"exact\", a more appropriate term is \"\(e\)-close\" spectrum. The divide-and-conquer (DC) method is summarized in Algorithm 1 and an illustration of the approach is shown in Figure 3. In this figure, it is shown how a binary tree is generated by recursive bisections until the desired depth is reached (divide). Afterwards, the spectrum is constructed at each parent node, in a bottom-up fashion, by the union of the spectra of its children (conquer). ```
Input: Graph \(\mathcal{G}\), function for computing eigenvalues \(h:\mathcal{S}\mapsto\lambda\) for graph family \(\mathcal{S}\), and depth \(d\). 1 if\(d==0\)then
2\(\hat{\lambda}\gets h(\mathcal{G})\)
3 else
4\(\{\mathcal{H}_{1},\mathcal{H}_{2}\}\leftarrow\texttt{bisectGraph}(\mathcal{G})\);
5\(\lambda_{1}\leftarrow\texttt{\small{-DC\_Approx\_Graph\_Spectrum}}(\mathcal{H}_{1},h,d-1)\);
6\(\lambda_{2}\leftarrow\texttt{\small{-DC\_Approx\_Graph\_Spectrum}}(\mathcal{H}_{2},h,d-1)\);
7\(\hat{\lambda}\leftarrow\texttt{\small{merge}}(\lambda_{1},\lambda_{2})\);
8
9 end while Result:\(\hat{\lambda}:\) Approximate spectrum of \(\mathcal{G}\)
```  
**Algorithm 1**DC_Approx_Graph_Spectrum \((\mathcal{G},h,d)\). Notice that in Algorithm 1 there are several things left undefined: (i) the function \(h\) which maps a graph to its spectrum, e.g., standard eigenvalue decomposition, (ii) the depth of the binary tree and the (iii) merge routine, e.g., union of elements. Although in principle, the method can be applied for any given functions \(h\), merge, and depth \(d\), we decided to keep the algorithm description as general as possible due to the fact that these three free parameters impact the method in the following ways. 1. The function \(h\) directly affects the computational complexity as it is the core operation of the algorithm. In addition, if \(h\) is not an exact algorithm but a randomized or approximate method, then it will impact as well the quality of the final approximation. 2. The merge function is the _conquer_ step that stitches back the solution of the leaves. As this function is called at every non-leaf node, dealing with increasing-size arguments (traversing the tree upward), it must be a low-complexity routine to not blow up the computational complexity of the method. 3. The depth of the tree, i.e., the number of recursive bisections, affects both the computational complexity and approximation quality. As each bisection worsens the approximation, deeper binary trees (theoretically) worsen the quality of the approximated spectrum. In addition, as the depth parameter controls the base case of the recursion for applying \(h\), its value also impacts the final complexity of the algorithm. Figure 3: Illustration of the divide and conquer approach described in Algorithm 1. First, a binary tree with successive graph bisections is constructed (divide). The graph spectrum is reconstructed by stitching back together the pieces of the spectra of the reduced-size graphs (conquer). An interesting property of this method is that it can be extended to other kinds of tasks.