Edge Bundling as a Multi-Objective Optimization Problem

A large variety of methods exist that realize edge bundling, see e. g. [3, 7, 4]. A formalization of some explicit edge bundling optimization problems has been proposed in [1]. Among those problems, the General-Based Edge Bundling (GBEB) Problem was introduced that aims at minimizing the number of bundles and at maximizing a given set of compatibility measures. The authors investigated in [1] a specific version of the GBEB, which consists of maximizing a weighted sum of two objective components: 1) the reciprocal of the number of bundles; and 2) the sum of the compatibility value for every bundle, calculated using the product of distinct compatibility measures for each pair of edges grouped together and a threshold to regulated the signal of the component. An evolutionary algorithm for the problem was designed and achieved good results. In a further work presented in [6], the authors treated the GBEB as a clustering problem and employed a combination of clustering and clustering-ensemble methods to solve it. The new approach led to better solutions than when using the evolutionary algorithm. However, both studies adopted an objective function that combines distinct objectives in a fixed way, thus limiting the space of possibly desirable solutions.

This paper investigates the GBEB problem as a multi-objective optimization problem, by searching for the Pareto frontier considering all objectives independently, instead of combining them in a single objective function. The multi-objective version of GBEB (abbreviated here as MEB) is still treated as a clustering problem, as done in [6], but we go beyond the previous methodological approaches: a step-by-step method is adopted that combines bundling strategies with a meta-heuristic to extensively explore the solution space and find good compromise solutions.

We aim at finding clustering solutions that maximize seven distinct aspects: 1) the reciprocal of the number of edge bundles (number of edge clusters), 2)-5) four compatibility measures proposed by Holten in [3] (angle, scale, position and visibility compatibilities), 6) the distance compatibility presented in [1], and 7) a new topological compatibility measure, which is defined as the distance between edge embeddings obtained with the node2vec method [2]. Note that only aspects 2) to 7) are compatibility measures. Here, the measurements in every quality aspect are normalized with maximum value =1.0.

The well known concept of dominance is used for comparing clustering solutions. A set of solutions can be divided into a hierarchical sequence of dominance classes by the following recursive procedure: solutions not dominated by any other solution in the set comprises the first class (called the non-dominated class); then, these solutions are removed from the set and the process repeats for the remaining set. While a class contains only equivalent solutions, any class is considered better than the subsequent classes. The first class constitutes the Pareto frontier. Our optimization method inputs a given graph $G=(V,E)$ and a straight-line drawing $D$ of $G$, and performs the following three steps, where the first two are similar to what was done in [6]:

• $\mathrm{■}$

  Step 1 – Creating edge representations: Given $G$ and $D$, an edge-to-edge compatibility matrix (dimension $|E|\times |E|$) is created for every compatibility measure. The $i$-th line of the $j$-th matrix, with $1\le i\le |E|$ and $1\le j\le 6$, is the feature representation of edge $i$ according to the compatibility measure $j$.

• $\mathrm{■}$

  Step 2 – Producing first solutions via clustering algorithms: Four standard clustering algorithms (Agglomerative Hierarchical, K-Means, K-Means with Mini Batch, and Spectral Clustering) with various parameter configurations are employed to cluster the graph edges for each compatibility measure individually, using their related edge feature representation. A normalized quality vector (with seven values, representing the measurement for seven previously mentioned quality aspects) is computed for every solution. Finally, the $1000$ solutions with the quality vector closest to $[1,1,1,1,1,1,1]$ are taken to the next step.

• $\mathrm{■}$

  Step 3 – Improving solutions via multi-objective consensus: This step runs an Asynchronous Team (A-Team) of autonomous agents [5] to improve the clustering solutions generated in Step 2, as an evolving group of dominance classes. The A-Team architecture consists of a shared memory with a predefined number $N$, of clustering solutions, and eighteen agents, which were formed by three clustering consensus algorithms with different setup parameters. Each agent reads up to $k$ solutions randomly chosen from the memory ($k$ is also predefined), runs a clustering consensus strategy, and writes its resultant solution to the shared memory. Every new solution produced may cause the dominance classes to be recalculated and an earlier solution (preferably from the latest dominance classes) to be removed. The A-Team runs until a pre-specified stop condition is reached, when the non-dominated class of solutions (the final Pareto frontier) is outputted.

The solutions in the Pareto frontier can be graphically rendered by using the adapted force-directed edge bundling method described in [1]. It takes the graph, the position of its vertices and a list of sets of edges (clusters) and produces an edge-bundling graph drawing.

In order to validate the new multi-objective optimization approach, experiments were performed with five sparse graphs from the literature, with sizes ranging from 20 to 160 vertices, and from 28 to 161 edges. We also set $N=1000$ and $k=10$ in Step 3, and ran the A-Team algorithm for one hour (this was sufficient for producing good quality solutions).

As the main result, the A-Team algorithm was capable of improving the set of solutions by finding new non-dominated ones. It also reduced the size of the non-dominated class for all graphs, demonstrating that many solutions generated in Step 2 could be replaced by a few better ones. Another important contribution of the general approach is the diversification of compromise solutions, with regard to the distinct quality aspects, which becomes ready for human evaluation, as illustrated in Figure 1 (blue lines indicate the largest bundle).