Recent Trends in Graph Decomposition

Let a HyperDAG (or, alternatively, a DAH – directed acyclic hypergraph) represent a computation and be given by a set of vertices and directed hyperedges, i.e., $\mathscr{H}=(𝒱,𝒩)$. Here, $𝒱=𝒮\cup 𝒯\cup 𝒪$ while every directed hyperedge $n\in 𝒩$ consists of a source and an arbitrary number of destination vertices; i.e., $n\in 𝒱\times 𝒫(𝒱)$, where $𝒫(𝒱)$ is the power set of $𝒱$. The vertices $𝒮$ are the input (source) data of the computation, the outputs are in $𝒪$, while intermediate computations are captured by computing tasks in $𝒯$.

Scheduling the computation on a parallel system with $p$ processing units requires assigning each vertex $v\in V$ a time step $t_v$ and a location $s_v\in \{0,1,\mathrm{\dots },p-1\}$ that define when and where to execute the intermediate computation in the case of $v\in 𝒯$, or when and where an input (or output) should be available in the case of $v\in 𝒮$ (or $v\in 𝒪$).

Let us initially consider a machine model that costs communication and computation, though does not consider weights for simplicity of presentation – i.e., each data element $v\in 𝒮\cup 𝒪$ uniformly costs some unit storage; $v\in 𝒯$ generates intermediate data that costs the same unit storage; and $v\in 𝒯$ costs some unit time to compute.

Approaching the scheduling problem from a hypergraph partitioning point of view generates a mutually disjoint ${𝒱}_0,\mathrm{\dots },{𝒱}_{p-1}$ partition of $𝒱$ under some allowed load imbalance $ϵ$, and minimizes the traditional $\lambda -1$-metric ${\sum }_{n_i\in 𝒩}\left({\lambda }_i-1\right)$; i.e., minimizes the communication volume of data units between parts of the partition⁷⁷7Here, ${\lambda }_i$ is defined as the connectivity of the $i$th hyperedge, i.e., the number of parts of the partition the vertices in that hyperedge span.. However, even a perfectly balanced and optimal partitioning may lead to a division of the HyperDAG across the $p$ compute units that exposes no parallelism whatsoever. One solution is to divide the HyperDAG into $s$ layers ${ℒ}_0,\mathrm{\dots },{ℒ}_{s-1}$, where vertices $v\in {ℒ}_{\le i}$ are predecessors of those in ${ℒ}_{>i}$, and then to partition each layer separately. Recent results show, amongst other results, that the resulting HyperDAG partitioning problem is NP-hard, and also that no polynomial-time approximation algorithm exists [52]. An additional problem is determining an appropriate $s$, which is a hard problem on its own.

Algebraic programming, or ALP for short, enables writing programs with explicit algebraic information passed into the programming framework. Examples of such algebraic information are binary operators and their properties such as associativity, commutativity, etc., as well as richer algebraic structures such as monoids and semirings. A semiring embodies the rules under which linear algebra takes place, but allows its generalization to any pair of additive and multiplicative operations under which those rules hold; for example, while the plus-times semiring enables standard numerical linear algebra, the min-plus semiring enables shortest-paths computations. The following two observations are core to GraphBLAS: a) most graph algorithms can be expressed in (generalized) linear algebra; and b) our deep understanding of optimizing sparse linear algebra (thus) applies to graph computations.

The recent nonblocking mode of ALP/GraphBLAS performs fusion of linear algebraic primitives under any algebraic structure, at run-time. It achieves up to $16.1\times$ and $12.2\times$ speedup over the similar state-of-the-art frameworks of SuiteSparse:GraphBLAS and Eigen on ten matrices for the PageRank algorithm, with similar results for a Conjugate Gradient (CG) solver and sparse deep neural network inference [46, 45]. Other recent work introduces support for dense linear algebra, matrix structures (e.g., triangular), and views (e.g., permutations or outer products) [71]. It furthermore enables automatic distributed-memory execution of sequential ALP code [86, 68].

Given an $m\times n$ matrix $A$ with $N$ nonzeros, the sparse matrix partitioning problem seeks a partition of $A$ into $p$ disjoint parts $A={\cup }_{i=0}^{p-1}{A}_i$ such that the number of nonzeros in part $A_i$ satisfies $|A_i|\le (1+\epsilon )\lceil \frac{N}{p}\rceil$ for , where $\epsilon \ge 0$ is a given load-imbalance parameter. Important questions for the area of sparse matrix partitioning as well as graph and hypergraph partitioning are: How good is heuristic bipartitioning compared to exact bipartitioning? How good is recursive bipartitioning into $k$ parts compared to direct $k$-way partitioning?

To answer these questions, we can solve a set of small- and medium-size problem instances to optimality using an exact algorithm either based on the branch-and-bound (BB) approach, or on an integer linear programming (ILP) approach. To answer the first question, a set of 839 matrices has been bipartitioned by the programs MondriaanOpt [58] and MatrixPartioner [34]. To answer the second question, an exact bipartitioner has been employed within a recursive bipartitioning program for $k=4$ and it has been compared with an exact direct 4-way partitioner using the program General Matrix Partitioner (GMP) [31] and the commercial ILP solver CPLEX.

We would like to scale up these initial results, to reach larger problems and be able to answer the main questions with more confidence. Since for $k=2$ the bipartitioner MP works best, we ask whether its algorithm and implementation can be further improved. Parallelization should also help to enlarge our database of solved problems. One might interpret this database as a training set for learning (by either machines or humans) about properties of optimal solutions.

For $k>2$, we surprisingly found that a basic formulation as an ILP solved by a commercial ILP solver was far superior to the BB solver GMP, and this poses the question what we can learn from the ILP solvers. Furthermore, can we use them for certain types of sparse matrix/graph partitioning? Finally, can we improve the basic formulation of the ILP to solve even larger problems?

Scalability of high quality parallel (hyper)graph partitioning remains an active area of research. In particular, achieving good scalability and quality on large distributed memory machines is still a challenge, but even on shared-memory machines, scalability to a large number of threads seems difficult. Even more difficult is aligning the inherent complexity and irregularity of state-of-the-art algorithms with the restrictions of GPUs or SIMD instructions. Another conundrum is that, for good memory access locality during partitioning, (hyper)graphs need to already be partitioned reasonably well. Hierarchies of supercomputers have to be taken into account during partitioning. This can be done by using multi-recursive approaches taking the system hierarchy into account or by adapting the deep multilevel partitioning approach sketched above to the distributed memory case. When arriving at a compute-node level, additional techniques are necessary to employ the full capabilities of a parallel supercomputer. For example, many of those machines have GPUs on a node level. Recently, researchers started to develop partitioning algorithms that run on GPUs and, while of independent interest, partitioning algorithms developed for this type of hardware can help in that regard. Hence, future parallel algorithms have to compute partitions on and for heterogeneous machines. On the other hand, algorithms should be energy-efficient and performance per watt has to be considered. Lastly, future hardware platforms have to be taken into consideration when developing such algorithms. One way to achieve this will be to use performance portable programming ecosystems like the Kokkos library [76].

The generally accepted formulation of the edge partitioning problem imposes a load balancing constraint on the number of edges per partition (cf., e.g., [47], [48]): $\forall p_i\in P:|p_i|\le \alpha \ast \frac{|E|}{k}$ for a given $\alpha \ge 1,\alpha \in ℛ$, where $|p_i|$ denotes the number of edges in partition $p_i$. However, balancing only the number of edges does not always lead to good load balancing in distributed graph processing, as shown in [49]. In some cases, it is better to balance the number of vertex replicas – vertex copies produced whenever incident edges are placed in different partitions. The open problem is to achieve an edge partitioning that is balanced both in the number of edges and vertices while minimizing the vertex replication factor. First thoughts in that direction may lead to the formulation of a multi-constraint partitioning problem.

Today almost all of the state-of-the-art graph and hypergraph partitioning tools utilize multi-level approaches that are comprised of three phases: coarsening, initial partitioning and uncoarsening/refinement. Even though numerous different coarsening techniques have been proposed and many are shown to be effective in multi-level partitioning, we still do not have a provably effective and efficient coarsening technique for graph or hypergraph partitioning problems. The situation is more dire for directed graph and hypergraph partitioning for acyclic partitioning. Keeping acyclicity during coarsening is a desirable property, yet, it is computationally expensive to ensure and maintain acyclicity, with flexible coarsening techniques.

Today we also do not have a well-defined objective for coarsening. In other words, we do not have well-agreed upon desirable properties of the coarsened graph. Overall we want to solve a partitioning problem, but in multi-level partitioning the overall success of the algorithm is a complex function of the three phases of the multi-level approach. We have many counterexample results showing that the best initial partitioning solution does not always yield the best result. Hence, it is even more difficult to define a goal for coarsening.

In undirected graph and hypergraph partitioning, many successful tools use randomized heavy edge matching/clustering techniques, where vertices are visited in random order, and they are matched with their unmatched neighbor with the heaviest connection. This randomization helps to “maintain” the graph’s structure. Hence, one potential direction for successful coarsening techniques is randomized algorithms (see Section 5.2).

Randomized algorithms on networks often involve sampling nodes, edges, or subnetworks [24, 25, 35, 72]. These sampling techniques are used as subroutines (1) for the solution of fundamental problems on networks, such as connected components, the assignment problem, breadth-first search on long-diameter graphs, or global minimum cut, and (2) for graph learning problems trained with variants of mini-batch stochastic gradient. These problems are widely encountered in the US DOE applications, e.g., the use of the assignment problem in optimal transport (transforming probability distributions) for cosmology, the use of connected components in genomics problems. Sketching and sparsification, which are other randomization techniques used for networks, can be used to find approximate solutions for higher-level problems where the network problem is a subroutine. The computational science applications include domain-decomposition solvers, iterative solvers, preconditioning for sparse systems using approximate factorization. Sampling and sketching can also be used as a coarsening technique in multilevel graph partitioning. Unfortunately, the impressive advances in the theory of randomized algorithms for networks has not been translated into practical demonstrations. There are ample research opportunities to bridge this gap between theory and practice, and hence, to produce high-quality software running on modern HPC hardware with demonstrations on application codes.

In streaming edge partitioning, edges are presented one at a time in a stream and must be assigned to a partition irrevocably at the moment they are encountered. Degree-based hashing has been proven effective for streaming edge partitioning, however, its potential benefits in the context of streaming vertex partitioning remain to be explored. An open problem is to investigate the benefits and challenges associated with using degree-based hashing techniques specifically for streaming vertex partitioning. Another notable limitation in the current literature on streaming partitioning algorithms is the predominant focus on common ordering strategies for the input (hyper)graph, such as random ordering, breadth-first search, and depth-first search orders. While these ordering strategies provide valuable insights into the performance of partitioning algorithms, they may not fully capture the challenges posed by real-world scenarios. Hence, it is an open problem to test streaming partitioning algorithms under adversarial node and edge orderings, particularly in the context of buffered streaming algorithms, where locality has a large impact on the quality of the result.

An open problem in the field of streaming process mapping is to address the problem when the underlying topology cannot be faithfully represented as a hierarchy, but only as a graph or hypergraph. Existing streaming algorithms either ignore the topology, i.e., solve the graph partitioning problem, or optimize directly for hierarchical topologies. However, many real-world scenarios involve complex interconnections that form graph-based topologies.

Solving the graph bipartitioning problem to optimality using branch-and-bound algorithms has recently been shown to be highly effective if the optimum solution value is very small. For example, Delling et al. [20] can solve instances with millions of vertices to optimality in a reasonable amount of time. It is still open whether such solvers also exist for balanced (hyper)graph partitioning problems where $k$ is significantly larger than $2$. The difficulty here comes from the fact that larger values of $k$ introduce a large amount of symmetry in the problem, i.e., if you have some partition of the graph, then any permutation of the block ids is also a partition of the graph that has the same balance and objective. Another problem of current solvers is how to handle dense instances or, more precisely, instances in which the objective function is large.

We investigate the scalability of the graph- and hypergraph-based sparse matrix partitioning methods in terms of being able to obtain high quality solutions in large problem instances. The quality measure that we are interested is the connectivity$-1$ metric, which usually measures the total volume of communication when vertices represent data items/computations and the hyperedges represent the dependencies. Ideally, theoretical investigations help explain the scalability or success of the methods. However, the current algorithms in use are too sophisticated to lend themselves to such an approach. We are thus looking for sound experimental methodology.

One approach is to take a subclass of problems, develop special partitioners, and compare the hypergraph partitioners with those. We take five-point stencil computations in two-dimensions (2D) for which we have a special linear-time partitioner [26, 77] and see how good the current partitioning methods are on these cases. We compare the performance of hypergraph partitioners on these. A rectangular 2D domain is discretized with the five point stencil and a mesh of size $X\times Y$ is obtained whose points are placed at integer locations. Two points $(x_1,y_1)$ and $(x_2,y_2)$ of the resulting mesh are neighbors iff $|x_1-x_2|+|y_1-y_2|=1$. A sample mesh resulting from the discretization of a square domain with five points in each dimension is shown in Figure 1. The figure also shows the connections of a point. After an ordering of the mesh points, one can obtain an $X^2\times Y^2$ matrix. The matrix obtained from the shown mesh after a row-major ordering is shown in Figure 1.

A partitioning of the points of the mesh $ℳ$ corresponds to a row-wise or a column-wise partitioning of the associated matrix ${𝐀}_{ℳ}$. Without loss of generality let us focus on the row-wise partitionings of ${𝐀}_{ℳ}$. The standard column-net hypergraph ${\mathscr{H}}_{CN}$ model [11] can be used for this purpose. Partitioning the vertices of the hypergraph ${\mathscr{H}}_{CN}$ among $K$ parts will therefore correspond to partitioning the stencil computations among $K$ processors; the connectivity$-1$ metric of the cut will measure the total communication volume; and the balance of part weights in terms of vertices will correspond to balance of the loads of the processors. We assume unit vertex weights here, the effect of having less operations on the border points of the mesh will be ignored for simplicity (and is negligible).

With the special partitioning methods by Grandjean and Uçar, we obtain the total communication volume listed in Table 1. While the communication volume listed in the table is obtained with the routine itself, we note that it is given by the formula

which is claimed to be optimal for $X>16$ in the table (for $X=16$, the optimal communication volume is claimed to be 57).

This formula requires some conditions on $X$, which we do not give here. Are the connectivity$-1$ values given in Table 1 optimal for a perfectly balanced 4-way partitioning of the two mesh of $X\times X$ points discretizing a square domain with a five point stencil? For the $16\times 16$ mesh, Gurobi solver [28] also finds a cut of value 57 in a few minutes under an additional constraint to assign the four corners to four different parts). The solution obtained by the Gurobi solver is at the close neighborhood of what is shown in Figure 2; by the method of Grandjean and Uçar is easily updated to mimic Gurobi’s result.

Another point that arise from the given 4-way partitioning is that these partitions cannot be obtained in a recursive bisubsection scheme where each step greedily optimizes the cut hyperedges with perfect balance. This is so, as the first cut vertically cuts the mesh into two equally sized parts with perfect balance and optimal cut. Simon and Teng [70] delve more into this point in the context of graph partitioning.

We note that more results of the sort are given elsewhere [26]. The same reference also surveys some results from the literature, including references on discrete isoperimetric problems [81], which can be used to guide algorithms. Two things are of particular note: in the corners, the optimal parts are triangle-like, as in two corners in Figure 2 (left), and in the interior the optimal parts are diamond-like as in Figure 2 (right).

Bisseling and McColl [9] propose digital diamonds to partition similar meshes with wrap-around connections. Digital diamonds are ${\mathrm{\ell }}_1$-spheres defined with a center $(c_x,c_y)$ and a radius $\rho$. Such a diamond contains all mesh points $(p_x,p_y)$ where with $|p_x-c_y|+|p_y-c_y|\le \rho$. Grandjean and Uçar give formulas for the total communication volume when one uses digital diamonds. They also specify conditions on mesh and part sizes under which a partition by digital diamonds are possible. Basic diamonds proposed by Bisseling [8, Section 4.8] trim off two borders from the digital diamonds to address partitioning of another set of mesh and part sizes – these conditions as well as the total volume of communication are also specified by Grandjean and Uçar. Digital diamonds and basic diamonds are believed to be asymptotically optimal in terms of the total communication volume, but obtain disconnected partitions on the borders of the mesh when there are no round-around connections – which is not desirable in certain applications.

Another approach is to take general sparse matrices boost the data in a way, reason about it and evaluate the performance of hypergraph partitioners on these. For example, suppose we partition a matrix $A$ row-wise into $k$ parts, and obtain a total communication volume of $T_V$ units in SpMxV. Then, if we partition the matrix $B=[A,A]$ row-wise again into $k$ parts, then the first partition should be good for $B$ with $2\times T_V$ communication volume. If our partitioning tool is good, such a performance is expected; if the answers were not $T_V$ vs $2\times T_V$, we could either improve the partition of $A$ or $B$. Similarly, a $k$-way row-wise partition of $C=[A;A]$ – this time two copies of $A$ are stacked to have twice as many rows – should have a communication volume of $T_V$ units. Some experimental investigation with PaToH [12] using these matrix repetition schemes [77] reveals a good behavior. What else can we say about the behavior of partitioning tools on more general problems?

Many distributed numerical simulations rely on mesh partitioning to improve the balance of their computations on every computing unit, thus increasing their efficiency and scalability. A mesh is modeled by its dual graph or hypergraph as input to a partitioner: each vertex corresponds to a cell of the mesh, and the vertex weight is the computing cost of this cell. Good quality hexahedral meshes have a reasonably regular topology, mostly looking like a 2D or 3D grid. However, the vertex weight distribution can be highly spread out for various applications like Monte-Carlo particle transport simulations. For this kind of instance, classic multi-level approaches of the existing graph partitioner can have some quality issues, symmetric to the ones observed in Section 5.2. Multi-level graph partitioners focus on topological properties, and here, taking more into account vertex weight distribution should lead to better and faster obtained partitions.

Directly addressing data in memory is crucial in achieving high performance when running on modern architectures, especially on GPU. Grids allow direct access to neighbor cells for mesh computations, making stencil computations like the one presented in Section 5.2 very efficient. However, standard partitioning approaches lead to non-rectangular parts, making distributed applications less efficient. Thus, a new problem is partitioning a grid into parts that are all a subgrid or a set of subgrids. Such a partitioning model will also work to partition block structured meshes that often arise for hexahedral meshes.

The partitioning community has long focused on instances with a regular structure, e.g., mesh graphs or instances from circuit design. However, it becomes more and more important to find high-quality solutions for instances with an irregular structure, such as those derived from social networks. Surprisingly, we found a subclass of these instances where current state-of-the-art partitioning algorithms compute solutions that are far from optimal. The identified instances – referred to as star instances – are characterized by a core of a few highly-connected nodes (core nodes) with only sparse connections to the remaining nodes (peripheral nodes). One example of such an instance is the Twitter graph. Here, we found that partitioning the nodes into low- and high-degree vertices ($\le$ median degree) induces a bipartition that cuts half the edges as any of the existing multilevel partitioning tools. We identified several other social networks where we observed the same behavior. Thus, it becomes increasingly important to develop efficient partitioning techniques that can handle such instances. From a theoretical perspective, we were already able to present an $(R+1)$-approximation for star instances, where $R$ is the ratio of an approximation algorithm for the min-knapsack problem. This is a remarkable result since there exists no constant factor approximation for the general graph partitioning problem.

For some graph algorithms, there is an implicit rank over the vertices. For instance, 2-hop indexing generates a label cover that can be used for answering pairwise shortest-distance queries. Classical algorithms, e.g., Pruned Landmark Labeling (Pll) [1] and its variants, leverage a ranking that has a drastic impact on the number of entries stored at local vertex indexes. In the distributed setting, the amount of entries in the cut, i.e., the ones replicated and/or communicated among the nodes, depends on this ranking. Especially when the number of nodes is high, this communication can create a bottleneck. For distributed execution, ranking the vertices also changes the loads on each part. In that sense, another problem at hand is given the rank, the amount of data stored at each vertex needs to be estimated well enough so that the part weights incur an acceptable level of imbalance. Hence, the problem is given a graph $G=(V,E)$, what is the best vertex ranking and partitioning pair that yields the best performance in terms of execution time and maximum memory used at each node?

In a variety of fields, computational optimization challenges often arise when modeling large and complex systems, presenting significant hurdles for solving algorithms, even when high-performance computing resources are deployed. These obstacles are frequently due to a multitude of factors such as an extensive number of variables and the complexity in describing each variable or interaction. Problems involving combinatorial and mixed-integer optimization add extra layers of complexity. Specifically, the presence of integer variables frequently results in NP-hard problems, particularly in contexts where nonlinearity and nonconvexity are factors.

A widely adopted strategy for tackling these challenges involves the use of iterative algorithms. While these algorithms may be grounded in divergent algorithmic paradigms, they often exhibit a similar pattern: rapid improvement during initial iterations followed by a phase of slower progress. In the realm of iterative algorithms, utilizing first-order optimization techniques like gradient descent or methods that rely on limited observable data, such as local search, often leads to a local optimum that is usually suboptimal when compared to the true global optimum. Additionally, the algorithms employed within each iterative cycle are not always exact, further complicating the optimization process. To speed up these algorithms at each iterative step, various strategies including heuristics, parallelization, and different ad hoc techniques are commonly employed, albeit often at the expense of solution quality. Being trapped in local optimum of unacceptable quality is one of the most important issues of such algorithms.

Multilevel methodologies have been introduced to address the challenges of large-scale optimization, offering a strategy that reduces the chances of being trapped in low-quality local optimum. These techniques are complementary to stochastic and multistart approaches, which also help the algorithm escape local optima. While there’s no one-size-fits-all prescription for designing multilevel algorithms, their core philosophy revolves around global considerations while executing local actions based on a hierarchy of increasingly simplified representations of the original complex problem.

In practice, a multilevel algorithm initiates the optimization process by generating a hierarchy of progressively simplified (or coarser) problem representations. Each subsequent coarser level aims to approximate the problem at the current level but with fewer degrees of freedom, facilitating a more efficient solution process. After solving the coarsest problem, its solution is extrapolated back to the more detailed level for further refinement – a phase termed as “uncoarsening.” Employing this multilevel approach frequently results in substantial improvements in both computational efficiency and the quality of solutions. There are many broad impact open questions in designing multilevel algorithms for (hyper)graphs some of which we mention here.

In the correlation clustering problem the input is a graph with edges labeled with $+$ and $-$ (or simply with $+1$ and $-1$). $+$ indicates that the endpoints of the edge should be in the same cluster, and $-$ means that the endpoints of the edge should be in different clusters. The goal of correlation clustering is to find a clustering that respects as many of these requirements as possible. Of course respecting all of them is in general not possible, and so a commonly studied objective is to minimize the number of disagreements.

There is a big discrepancy between the theory work on correlation clustering and what is done in practical solutions. For example, while the famous PIVOT algorithm provides $3$-approximation for complete graphs, if the algorithm is run on a sparse graph (i.e., one where $+$ edges induce a sparse graph) the algorithm often gives a solution that is worse than leaving each node in a cluster of size $1$. Better approximation algorithms are known, but they are not as scalable, as they rely on solving an LP or SDP. In the case of weighted or not-complete graphs the best known approximation ratio is $O(\log n)$.

Despite all of these theoretical advances, the solutions that are implemented in practice are based on local swaps and a multilevel approach. In particular, the basic operation that these algorithms make is moving a node to a neighboring cluster, only if this increases the overall objective. This way, the algorithm essentially treats the objective function as a blackbox and does not leverage all the structural properties of the problem, which are used to give approximation algorithms.

While the practical implementations are quite scalable, there is probably room for improvement, as the number of logical rounds needed to obtain a good solution goes in hundreds. This in particular makes these algorithms not easy to use in distributed settings.

An interesting open problem is to bridge the gap between theory and practice for correlation clustering with the goal of obtaining better practical implementations. Specifically, it would be interesting to develop algorithms requiring fewer rounds, which will make them amenable to an efficient distributed implementation.

Edge-Colored Clustering is a categorical clustering framework [2] whose input is an edge-colored hypergraph and output is an assignment of colors to nodes which minimizes the number of edges where any vertex has a color different from its own (mistakes). We are interested in variants of this problem which allow budgeted overlap. Specifically, the following three notions were defined in [17]. LocalECC allows up to $b$ of color assignments at each node. GlobalECC allows one “free” color assignment for each node, plus $b$ additional assignments across all nodes. RobustECC allows each node to either receive exactly 1 color, except that at most $b$ nodes are assigned every color. Equivalently, at most $b$ nodes are deleted.

Each of these problems generalizes ECC, with equivalence for the first coming at $b=1$ and for the latter two at $b=0$. Consequently, they are each NP-hard (Angel et al. [2]). We (Crane et al. [17]) showed that greedy algorithms give an $r$-approximation on the number of edge mistakes, where $r$ is the maximum hyperedge size. Further, for LocalECC, a $(b+1)$-approximation can be achieved with LP-rounding. More generally, we ask about bicriteria $(\alpha ,\beta )$-approximations, where $\alpha$ is the approximation factor on edge mistakes and $\beta$ is the approximation factor on the budget $b$, and show that all three variants have such approximation algorithms, though the factors are no longer constants for GlobalECC.

Dense Graph Partition, introduced by Darley et al. [19], models finding a community structure in a social network. Formally, given an undirected graph $G=(V,E)$, the task is finding a partition $𝒫=\{P_1,\mathrm{\dots },P_k\}$ of $V$, for some $k\ge 1$, of maximum density. With $E(P_i)$ denoting the number of edges among vertices in $P_i$, the density of $𝒫$ given by $d(𝒫)={\sum }_{i=1}^k\frac{|E(P_i)|}{|P_i|}$. Note that there is no restriction on the number of communities which yields some difference to the problem of partitioning into cliques. While there exists a partition into exactly $k$ sets of density $(n-k)/2$ if and only if the input graph can be partitioned into $k$ cliques [6], there can be a partition into less than $k$ sets with a density higher than $(n-k)/2$ even if the input cannot be partitioned into $k$ cliques. Alternatively, Dense Graph Partition can be modeled from a game theoretic perspective. Aziz et al. [4] study the Max Utilitarian Welfare problem where the vertices in a graph $G=(V,E)$ are agents, and each agent $x\in V$ validates its coalition $P\subseteq V$ with $x\in P$ by $\frac{1}{|P|}|\{u\in P\mid \{u,v\}\in E\}|$. Maximizing social welfare for this model is equivalent to Dense Graph Partition.

It is known that maximum matching is a 2-approximation [4], and there are a few improvements on specific graph classes: polynomial-time solvability on trees [19], $\frac{4}{3}$-approximation on maximum degree 3 graphs, and EPTAS for everywhere dense graphs [6]. This in particular gives rise to the questions: Can the 2-approximation be improved, at least on some more non-trivial graph classes? Does there exist a polynomial-time approximation scheme on general instances? Is it true that there is always an optimum solution where all parts induce a graph of diameter at most 2, a so-called 2-club clustering? What is the complexity on graphs of bounded treewidth?

Streaming Graph Clustering is commonly defined as follows: given a graph $G=(V,E)$, find a clustering $𝒞:V\to 𝒩$ that maximizes a quality score such as modularity, using at most $O(|V|)$ memory. In the one-pass version, $E$ is an ordered list of edges and each edge can be read only once. A popular heuristic for this problem is SCoDA [29].

This matches well with real-world applications where graphs are discovered over time, e.g. in online social networks, as well as for graphs which are too large to cluster using standard $O(|E|)$ memory algorithms. However, the one-pass version is quite limiting and often results in low clustering quality [38].

The Incremental Graph Clustering model [38] is a buffered variant of the one-pass model where the ordered edge list is subdivided into batches. Unlike in buffered streaming graph partitioning [21], the batches are assumed to be given and not selected by the algorithm. Edges in a batch are read and processed in memory together. The algorithm can use $O(|E|)$ memory, but we require that running time for processing each batch does not depend on $|E|$, only on the size of the batch.

The Neighborhood-to-community link counting (NCLiC) [38] is a heuristic for this variant. For modularity clustering, it provides strong modularity retention compared to offline algorithms. It applies the Leiden Algorithm to each new batch and then merges it with the already processed graph.

Most balanced (hyper)graph partitioning formulations are NP-hard: it is believed that no polynomial-time algorithm exists that always finds an optimal solution. However, many NP-hard problems have been shown to be fixed-parameter tractable (FPT): large inputs can be solved efficiently and provably optimally, as long as some problem parameter is small. Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. Moreover, in recent years a range of methods from the area have been shown to improve implementations drastically. For example for the maximum (weight) independent set problem [27]. Here, data reductions rules transform the input into a smaller one that still contains enough information to be able to recover the optimum solution. For the maximum independent set problem, this enabled highly scalable exact solvers that can solve instances with millions of vertices to optimality. For balanced partitioning this has currently not been carefully investigated. However, here are some very simple data reduction rules. For example, removing a vertex of degree one, then solving the smaller subproblem with same balance constraint and afterwards assigning the vertex to a block with leftover capacity, is a valid data reductions rule. This yields the natural open questions: are there more and highly effective data reduction rules for balanced (hyper)graph partitioning problems? These rules could be helpful in two ways: they could speedup current heuristic solvers, e.g. multilevel (hyper)graph partitioning algorithms, and they could help to build more scalable exact partitioning algorithms (see Section 5.2).

After all reduction rules for kernel computations have been applied, the final smaller instance can still be too large to be solved to optimality within a reasonable time bound. This is a serious problem as the overall goal of the algorithms is to solve the given problem instance. The idea of lossy kernelization is as follows: when no more reductions can be applied, i.e. a problem core has been computed, one may shrink the input further while guaranteeing that the optimal solution value changes only slightly. Then a good approximate solution of the reduced input can be lifted to a good approximate solution of the original input. This has recently been done for the vertex cover problem [40]. The natural question that arises is can these techniques be applied to balanced (hyper)graph partitioning as well?

As the (lossy) kernel/core still contains the optimum solution (or some approximation thereof) in some sense, this has a large potential to speed up the (multilevel) heuristic while not sacrificing solution quality. Additionally, running a fast algorithm on the large kernel can help to identify parts of the instances that are likely to be in a good solution. Those parts can then be put into a partial solution and the remaining instance can be reduced recursively.

It could also be possible to use machine learning to learn lossy reductions for a wide-range of problems in this area. For example, one could use learning to predict if two vertices should be clustered together or to decide if an edge is a cut edge or not. The basic idea is then to use a classification model to learn which parts of the input can be pruned, i.e. are unlikely or highly likely in an optimum solution. In the first case, a solution omits this part of the input, in the latter case this part of the input will be included in the solution. For example, [39] propose to use machine learning frameworks to automatically learn lossy reductions for the maximum clique enumeration problem and [74] shows that this learning-to-prune framework is effective on a range of other combinatorial optimization problems. The classification model can be a deep neural network in an end-to-end framework or a classifier with significantly fewer parameters such as SVM or random forest if a deeper integration of machine learning and algorithmic techniques is done. The latter will require carefully engineered features based on existing heuristics.

Machine learning techniques can also be used to learn more efficient refinement steps. Existing refinement steps in multi-level graph partitioning techniques rely on solving a flow problem or iterative moves of Kernighan–Lin or Fiduccia–Mattheyses heuristic. However, solving flow problems can be quite slow (given the number of times it is called). Similarly, the number of possible moves that need to be explored for finding a good step using Kernighan–Lin or Fiduccia–Mattheyses can be quite high. It is worthwhile exploring if learning techniques can be used to predict good regions where the flow algorithm can focus. This can improve the trade-off between the time to solve the flow problem and the gain from it for the refinement part. For the case of the Kernighan–Lin or Fiduccia–Mattheyses heuristic, the interesting question is whether learning techniques such as reinforcement learning can be used to learn a good sequence of moves for these local search heuristics. This has the potential to reduce the search space that needs to be explored to find good local moves. For training the learning techniques, the R-MAT graph generator from the Graph500 benchmark can be used.

Process mapping is a super-problem of graph partitioning, in which vertices of some source graph $S$ have to be assigned (i.e., mapped) to vertices of some target graph $T$, by way of a mapping function ${\tau }_{S,T}:V(S)⟶V(T)$, so that an objective function is minimized. In the field of parallel computing, source graphs commonly represent computations to be performed, usually multiple times in sequence, while target graphs represent processing elements and interconnection networks of multi-processor and/or multi-computer hardware architectures. The objective function to minimize is the amount of data to be exchanged across the interconnection network, so as to reduce its congestion, provided that every processing element in $V(T)$ receives roughly the same number of vertices of $S$ (or, more generally, equivalent vertex weights with respect to its compute power), to minimize computation imbalance. In this context, partitioning some graph $S$ into $k$ parts amounts to mapping $S$ onto $K(k)$, the complete graph of order $k$, since in this case all processing elements are at the same distance from all the others.

In the Dual Recursive Bipartitioning (DRB) algorithm [54] used by the Scotch software, computing the mapping of $S$ onto $T$ requires to be able to estimate the shortest-path distance in $T$ between any two vertex subsets of $V(T)$ called the subdomains of $V(T)$. These subdomains are not arbitrary, since they result from recursively bipartitioning the graph $T$ into pieces of roughly the same size in a way that minimizes the cut of the interconnection network. Being able to compute the distance between any two subdomains allows the DRB algorithm to estimate the penalty of assigning some vertex $v$ of $S$ to either one of two sibling subdomains of $T$, by estimating the distance between these subdomains and those to which all the neighbor vertices $v$ of $u$ have already been mapped. When the recursive bipartitioning of $T$ is perfectly balanced, the number of subdomains of $T$ is $2|V(t)|-1$.

A way to quickly obtain the distance between any two subdomains of some target graph $T$ is to pre-compute a distance matrix between all of them, of a size in $O({|V(T)|}^2)$. While this solution works for small target graphs, it is no longer applicable when mapping onto big parts of very big target architectures. To solve this problem, one has to find a more compact (in terms of data storage) and quick (in terms of retrieval time) method to produce these distance estimates. An important condition on these approximations is that distances should become more accurate as subdomains are smaller and closer to each other in $T$.

In [55, 56], it has been shown that, for target architectures for which the recursive bipartitioning of subdomains, and the distances between subdomains, can be computed algorithmically, by way of explicit functions (e.g. , for regular vendor architectures such as meshes, butterfly graphs, etc.), a bipartition tree, created by way of recursive matching and coarsening of the whole target graph, allows one to represent any subset, even disconnected, of the processing elements of these target architectures. The DRB algorithm can therefore be applied to them.

However, for irregular architectures (e.g. , those represented by irregular graphs), the question remains open. It can be expressed in the following form: “How can one get cheaply (both in terms of memory and computation time) approximate distances between any pair of the subgraphs yielded by the recursive bipartition of some irregular graph?”

When one opens up a publication regarding planar graph bisubsections, one often reads a sentence akin to: Without loss of generality, assume that the input graph is embedded in the plane and maximal planar. Famous works that makes use of this specific property is the balanced separator theorem due to Lipton et al. [42], which states that every planar graph has a balanced vertex separator of size $O(\sqrt{n})$. Standard recursive bisubsection algorithms for planar graphs are based on this theorem, which are able to construct the entire recursive bisubsection in linear time [33]. Often it is easy to assume such an embedding, as it can be computed in linear time using $O(n\log n)$ bits of space, i.e., a linear number of words. In sub-linear space settings one can compute an embedding in polynomial time (albeit with an extremely large polynomial degree). Now, the question remains: what can one achieve when aiming for a linear time algorithm, while using $o(n\log n)$ bits, or ideally, $O(n)$ bits? The standard linear time algorithms are quite involved, but on the most basic level many of them use a simple depth-first tree and compute a constant number of, but seemingly critical, variables per vertex. Even when aiming for a much lower goal: check if the input graph is planar within $O(n\log n)$ time while using $o(n\log n)$ bits, there is no obvious way to tackle this problem. As graphs grow larger and larger, such questions of space-efficiency become of higher interest. Especially with the direct application of graph partitioning algorithms that rely on such embeddings.

In graph theory, given a graph with degree $d$ and diameter $k$, the largest number of vertices in that graph can be determined using the Moore bound. Recent technological advances in photonics technology have greatly increased the number of links – or degree $d$ – of the network routers, improving the scalability of large supercomputers. While Moore-bound-optimal diameter-2 graphs have recently been engineered to span a few thousand nodes [36], emerging AI and graph applications are demanding larger configurations. Unfortunately, diameter-3 graphs are still elusive, with Moore’s bound efficiencies of only 15%. The construction of more efficient diameter-3 graphs would directly impact the design of emerging photonics systems for large scale graphs [36, 37], data analysis, and AI applications.

Edge (resp. Vertex) Bisubsection is one the fundamental graph partitioning problems, where given a graph $G$ and an integer $k$, the goal is to find a set of at most $k$ edges (resp. vertices), say $S$, such that the vertex set of $G\setminus S$ can be partitioned into two almost equal parts $V_1$ and $V_2$, that is $||V_1|-|V_2||\le 1$, and there are no edges between a vertex of $V_1$ and $V_2$, that is $E(V_1,V_2)=\mathrm{\varnothing }$. In the regime of parameterized complexity, Edge Bisubsection admits a fixed-parameter tractable (FPT) algorithm parameterized by the solution size $k$. In particular, it admits an algorithm running in time $2^{O(k\log k)}{n}^{O(1)}$ [18], where $n$ is the number of vertices in the input graph.

The first open question here is if Densest $k$-Subgraph FPT parameterized by modular-width? Given a graph $G$ and an integer $k$, the Densest $k$-Subgraph problem asks for a subgraph of $G$ with at most $k$ vertices maximizing the number of edges. It is known that this problem is FPT by stronger parameters such as neighborhood diversity and twin cover, yet it is W[1]-hard by weaker clique-width. Modular-width is defined using the standard concept of modular decomposition [23]. Any graph can be produced via a sequence of the following operations:

1. 1.

   Introduce: Create an isolated vertex.

2. 2.

   Union $G_1\oplus G_2$: Create the disjoint union of two graphs $G_1$ and $G_2$.

3. 3.

   Join: Given two graphs $G_1$ and $G_2$, create the complete join $G_3$ of $G_1$ and $G_2$. That is, a graph $G_3$ with vertices $V(G_1)\cup V(G_2)$ and edges $E(G_1)\cup E(G_2)\cup \{(v,w):v\in G_1,w\in G_2\}$.

4. 4.

   Substitute: Given a graph $G$ with vertices $v_1,\mathrm{\dots },v_n$ and given graphs $G_1,\mathrm{\dots },G_n$, create the substitution of $G_1,\mathrm{\dots },G_n$ in $G$. The substitution is a graph $𝒢$ with vertex set ${\bigcup }_{1\le i\le n}V(G_i)$ and edge set ${\bigcup }_{1\le i\le n}E(G_i)\cup \{(v,w):v\in G_i,w\in G_j,(v_i,v_j)\in E(G)\}$. Each graph $G_i$ is substituted for a vertex $v_i$, and all edges between graphs corresponding to adjacent vertices in $G$ are added.

These operations, taken together in order to construct a graph, form a parse-tree of the graph. The width of a graph is the maximum size of the vertex set of $G$ used in operation (O4) to construct the graph. The modular-width is the minimum width such that $G$ can be obtained from some sequence of operations (1)-(4). Finding a parse-tree of a given graph, called a modular decomposition, can be done in linear-time [75].
The second open question is whether we can develop a framework of approximate modular decomposition applicable to real-world datasets? Unfortunately, most real-world graphs tend to have larger modular-width. It would be beneficial if we can efficiently build non-exact parse trees with much lower width but without losing much information. Possible avenues of exploration include graph editing, a relaxed definition of the parse-tree, and a data-driven approach.

One of the most explored topics in parameterized complexity are so called distance to triviality problems (see, for example, [22, 30]). The intuitive question behind these problems is always “can we make a small change to our input so that it takes on some property?”. In terms of graph problems, one can state a meta-problem as follows, where $𝒫$ is a graph property Vertex-Deletion-To-$𝒫$: given a graph $G$, an integer $k$ as well as a parameter $k$, the question is can we delete at most $k$ vertices from $G$, such that the resulting graph has property $𝒫$?

For many graph properties for which one can consider this meta-problem, either tractable algorithms or complexity lower bounds are known. On the other hand, in some application areas it could be useful to delete as many vertices as possible, while ensuring that the resulting graph has a certain property. This leads to the Max-Vertex-Deletion-To-$𝒫$ problem: given a graph $G$, an integer $k$ as well as a parameter $k$, the question is can we delete at least $k$ vertices from $G$, such that the resulting graph has property $𝒫$?

While the change to the problem statement is deceptively simple, we have to this date no complexity-theoretic insight into this class of problems. Note that this problem also differs from the widely used kernelization techniques, as in kernelization, we ask for the resulting input size to be bounded by, for example, $f(k)$. As parameterized complexity can be seen as providing a mathematically rigorous framework of preprocessing through the rich methods of kernelization techniques and algorithmics for distance to triviality problems, extending this framework to further variants of preprocessing seems very natural and could provide further complexity-theoretic and algorithmic insights. These techniques could potentially be useful in the area of (hyper)graph decomposition.