# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 5 Divide-And-Conquer for Fast Graph Spectrum Estimation
### Accuracy-Complexity Trade-Off  
Until this point, we only have provided theoretical guarantees for a graph decomposition with a single level, i.e., depth \(d=1\). In the following, we introduce the main theorems of this work with respect to both the quality and complexity of the DC approach for graph spectrum approximation. For this analysis, we consider the case where the merge routine solely sorts its input, incurring a complexity of \(O(n\log n)\) for inputs of size \(n/2\) each.  
Before proceeding, we first introduce the following definition.  
Definition 2: [Linearly separable graph family] The set \(\mathcal{S}_{c}\) of graphs for which a \(\mathcal{O}(n^{c})\)-separator theorem exists, with \(c<1\), and whose subgraphs are also contained in the set, is called a \(c\)-separable graph family. Furthermore, if the separator is efficiently computable in (approximately) linear time then the set is a \(c\)-linearly separable graph family and it is denoted as \(\mathcal{S}_{c}^{l}\).  
For the sake of simplicity, we restrict our results to the family of graphs \(\mathcal{S}_{1/2}^{l}\). This family includes planar graphs, geometric graphs in 2-D, and graphs with a restricted minor [9]. However, the results hold for any \(c\)-separable graph family as long as the exponents are modified appropriately. In the following, the main results with respect to approximate graph spectrum estimation are presented.  
Theorem 2: _For a graph \(\mathcal{G}\in\mathcal{S}_{1/2}^{l}\), Algorithm 1 with a decomposition tree of depth given by \(d^{*}=\mathcal{O}((1-2\delta)\log n)\) for \(\delta\in(0,1/2)\), provides an \(\mathcal{O}(1/n^{\delta})\)-approximation of the spectrum of \(\mathcal{G}\) w.r.t. the Wasserstein distance in \(\mathcal{O}(n^{1+4\delta})\) time._  
Proof: See Appendix C.  
From this result, two direct corollaries providing the limits of the proposed method for the family \(\mathcal{S}_{1/2}^{l}\), in terms of accuracy and time complexity, can be directly obtained as follows.  
Corollary 1: _An \(\mathcal{O}(1)\)-approximation (constant factor) for the spectrum of \(\mathcal{G}\in\mathcal{S}_{1/2}^{l}\) is achievable in \(\mathcal{O}(n\log n)\) time when the depth of the decomposition tree for Algorithm 1 is chosen to be \(d=\lceil\log n\rceil\)._  
Corollary 2: _An \(\mathcal{O}(1/\sqrt[4]{n})\)-approximation for the spectrum of \(\mathcal{G}\in\mathcal{S}_{1/2}^{l}\) is achievable in \(\mathcal{O}(n^{2})\) time when the depth of the decomposition tree for Algorithm 1 is chosen to be \(d=\lceil\frac{1}{2}\log n\rceil\)._  
These results provide the following two insights. First, for large-size graphs the approximation is tight, i.e., it vanishes as \(n\) grows. Hence, the proposed method is _asymptotically efficient_ in the size of the graph. Second, the time complexity of the method is bounded below by the so-desired \(\mathcal{O}(n\log n)\) complexity, and above by the (naive) cubic complexity, \(\mathcal{O}(n^{3})\). Therefore, as pointed out in Corollary 2, a good compromise between the decay rate of the error and complexity can be achieved when we fix \(\delta\) to \(1/4\).  
Although a discussion about parallelization is not the main aim of this work, we want to stress that, as most of the divide-and-conquer approaches, the proposed method is _parallel friendly_. That is, as each of the subproblems (at the leaves) are disjoint, they can easily be parallelized providing a significant reduction in the time complexity. However, this analysis is outside the scope of this work and it does not provide any further insights into the proposed method.