## 2 Background Knowledge  
### Mathematical Description of the Circuit-Partitioning Problem  
The circuit is abstracted as an undirected graph \(G(V,E)\), where \(V\) denotes the set of circuit modules, and \(E=\{e(v_{i},v_{j})\mid v_{i},v_{j}\in V\}\) denotes the set of undirected edges representing the connections between the modules. The number of vertices in the graph \(G\) where \(|V|\) denotes the set of circuit modules and \(E=\{e(v_{i},v_{j})\mid v_{i}\in V,v_{j}\in V\}\) denotes the set of undirected edges representing the connections between the modules. The number of vertices in graph \(G\) is denoted as \(|V|=n\), with individual vertices denoted as \(v_{1},v_{2},\cdots,v_{n}\). Each vertex \(v_{i}\) is assigned a weight \(a_{i}\), and the total vertex weight of the graph \(G(V,E)\) is denoted as \(A_{G}=\sum_{i=1}^{n}a_{i}\). The degree of vertex \(v_{i}\) is defined as the sum of the connection weights between \(v_{i}\) and all other vertices, denoted as \(d_{i}=\sum_{j=1}^{n}e(i,j)\). In multi-level partitioning algorithms, coarsening is an important step aimed at improving partitioning efficiency by simplifying the problem scale. The coarsening process constructs a hierarchical structure by progressively reducing the size of the graph, typically by matching nodes and merging them into smaller graphs. The weight of the merged vertex is the sum of the weights of the two merged vertices:  
\[a_{(i,j)}=a_{i}+a_{j} \tag{1}\]  
where \(a_{i}\) and \(a_{j}\) are the weights of vertices \(v_{i}\) and \(v_{j}\), respectively. For the coarsened graph \(G^{\prime}(V^{\prime},E^{\prime})\), each edge \(e(v_{i},v_{j})\) will affect the new edge \(e(v_{(i,j)},v_{k})\) (where \(v_{(i,j)}\) is the merged vertex and \(v_{k}\) is any other vertex connected to \(v_{i}\) or \(v_{j}\)). The weight of the new edge can be defined as:  
\[w(e(v_{(i,j)},v_{k}))=w(e(v_{i},v_{k}))+w(e(v_{j},v_{k})) \tag{2}\]  
where \(w(e(v_{i},v_{k}))\) and \(w(e(v_{j},v_{k}))\) are the weights of the edges between vertices \(v_{i}\) and \(v_{k}\), and \(v_{j}\) and \(v_{k}\), respectively, in the original graph. The coarsened graph reduces the size from the original \(n\) vertices to a smaller number \(n^{\prime}\). The goal of the coarsening process is to iteratively reduce the size of the graph by selecting appropriate matchings until the graph becomes small enough to allow for finer partitioning:  
\[n^{\prime}=\text{floor}\Big{(}\frac{n}{2}\Big{)} \tag{3}\]  
where \(\text{floor}()\) denotes the floor operation, meaning that after each coarsening step, the number of vertices approximately halves. The total weight of the coarsened graph \(A^{\prime}_{G}\) is the sum of the weights of all merged vertices:  
\[A^{\prime}_{G}=\sum_{i=1}^{n^{\prime}}a^{\prime}_{i} \tag{4}\]For a circuit graph \(G(V,E)\), if it is partitioned into \(k\) subgraphs \(G_{1}(V_{1},E_{1})\), \(G_{2}(V_{2},E_{2})\), \(\cdots\), \(G_{k}(V_{k},E_{k})\), and \(V_{1}\cup V_{2}\cup\cdots\cup V_{k}=V\), then all the subsets are referred to as the \(k\)-way partition of graph \(G\), denoted as \(P_{G}^{k}\). In the partitioning, the total vertex weight of the subgraph \(G_{i}(V_{i},E_{i})\) is \(A_{G}^{i}\), and the total number of vertices is \(n_{i}\). The edges broken by the partition are called cut edges, and the total number of these cut edges is denoted as \(Cut(P_{G}^{k})\). Thus, the objective function for searching for the minimum cut edges can be simply denoted as \(\text{Min}(Cut(P_{G}^{k}))\). A balance factor \(\beta\) is introduced to ensure the load balance of each partition subset, and the following condition must be satisfied:  
\[(1-\beta)\cdot\frac{A_{G}}{k}<A_{G}^{i}<(1+\beta)\cdot\frac{A_{G}}{k},\text{ where }1\leq i\leq k. \tag{5}\]  
The partition connectivity is an indicator to measure the closeness of a vertex to a partition.