# Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering
## 3 Topological Graph Theory
### Graph Separators  
Let us consider an undirected graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) and \(\mathcal{E}\) denotes its vertex set and edge set, respectively. In many instances, we desire to find a partition \(\{\mathcal{P}_{i}\}_{i=1}^{\mathcal{Q}}\) of the vertices in \(\mathcal{G}\), i.e., \(\mathcal{V}=\cup_{i=1}^{\mathcal{Q}}\mathcal{P}_{i}\), such that the members of such groups are balanced, i.e., \(|\mathcal{P}_{i}|\approx|\mathcal{P}_{j}|,\ \forall\ i,j\in\{1,2,\ldots,Q\}\), and either (i) the number of edges connecting the different partitions is minimized or (ii) the number of vertices that are needed to be removed to disconnect the graph is minimized. A common partition strategy is based on the field of _graph separators_[27]. In general, there are two kinds of graph separators: _vertex separators_ and _edge separators_. In the case of vertex separators (see Figure 1), the vertices \(\mathcal{V}\) are partitioned in three sets \(\mathcal{A}\), \(\mathcal{B}\) and \(\mathcal{C}\). The goal of this partition is to disconnect \(\mathcal{A}\) and \(\mathcal{B}\) while minimizing the number of vertices in \(\mathcal{C}\) and maintaining a balance between \(\mathcal{A}\) and \(\mathcal{B}\), i.e., \(|\mathcal{A}|\approx|\mathcal{B}|\). Since there are no edges between \(\mathcal{A}\) and \(\mathcal{B}\), vertex separators are also known as _bisectors_ or _bifurcators_. For the case of _edge separators_ (see Figure 2), the vertices are partitioned in two balanced sets, \(\mathcal{A}\), and \(\mathcal{B}\) such that the number of _cut edges_, i.e., edges between the two sets, is minimized. As there are (possibly) many ways to _separate_ a graph, we first make the following remarks:  
1. Finding optimal graph separators is _hard_. 2. Graphs whose graph separators are _sublinear_ in size are considered as _good graph separators_. That is, the number of vertices (edges) that needs to be removed to partition the graph in balanced sets is \(o(n)\)  
Figure 1: Illustration of a vertex separator. The vertex set \(\mathcal{V}\) is divided in three subsets \(\mathcal{A}\), \(\mathcal{B}\), \(\mathcal{C}\) such that \(\mathcal{A}\) and \(\mathcal{B}\) are disconnected, while minimizing the size of \(\mathcal{C}\) and maintaining a balance (in terms of the number of vertices) between \(\mathcal{A}\) and \(\mathcal{B}\). Figure 2: Illustration of an edge separator. The vertex set \(\mathcal{V}\) is divided in balanced subsets \(\mathcal{A}\) and \(\mathcal{B}\) such that the number of edges between them are few. 3. Graphs with _good recursive_ graph separators are graphs whose resulting partitions have _good separators_ themselves. For instance, if the class \(\mathcal{S}\) of graphs has good graph separators, and \(\mathcal{S}\) is closed under vertex (edge) deletion, then the graphs in \(\mathcal{S}\) have good recursive graph separators. Now, we clarify further these remarks. We make the distinction between graph separators and _good graph separators_ due to the fact that we are interested in graphs that can be partitioned in balanced sets by removing just a _few_ vertices (edges). Since algorithmic reasons dictate properties that can be propagated to the subsequent partitions, we stress the importance of graphs with _good recursive separators_. This is important for the design of divide-and-conquer algorithms or for parallel processing because it implies the possibility of generating increasingly small graphs by recursively splitting the problem into many subproblems. Therefore, identifying structured graphs accepting good recursive separators are of high importance from an algorithmic perspective. Finally, despite the discouraging result (i), fortunately, there are types of graphs that have good separators [cf. (ii)] and there exist efficient algorithms for finding them. As a last comment, let us discuss briefly the relationship between vertex and edge separators.