Multi-Objective Graph Optimization: NSGA-II and Pareto Fronts in TGraphX

Many graph-design problems pull in opposite directions. You want a network that is well-connected and sparse; robust and cheap; clustered and low-diameter. These objectives conflict, so there is no single "best" graph — improving one usually costs another. The right answer is not one graph but a set: the Pareto front of solutions where you cannot improve any objective without sacrificing another. TGraphX implements the classic multi-objective evolutionary algorithm, NSGA-II, for exactly this, in tgraphx/evolutionary. This note explains the math and where it lives in the code.

It deepens the introductory Evolutionary Optimization of Graph Structures.

Pareto dominance, precisely

With objectives f₁, …, f_m (say, all to be maximised), solution a dominates solution b when a is at least as good on every objective and strictly better on at least one:

a ≻ b   ⟺   fᵢ(a) ≥ fᵢ(b) for all i,  and  fⱼ(a) > fⱼ(b) for some j
        

A solution is Pareto-optimal if nothing dominates it. The set of all such solutions is the Pareto front — the trade-off curve a decision-maker actually wants, because it shows the achievable frontier rather than collapsing the choice into one weighted score prematurely.

NSGA-II in two ideas

NSGA-II (Deb et al.) is built from two mechanisms, both present in tgraphx/evolutionary/multi_objective.py:

1. Non-dominated sorting (non_dominated_sort) ranks the population into fronts: front 0 is the non-dominated set, front 1 is what becomes non-dominated once front 0 is removed, and so on. Selection prefers lower-numbered fronts, pushing the population toward Pareto-optimality.
2. Crowding distance (crowding_distance) measures how isolated a solution is along the front. When two solutions share a front, the one in a less crowded region is preferred, which spreads the population along the trade-off curve instead of clumping it. The result is wrapped in a ParetoFront object that carries the solutions and their crowding distances.

Together these give NSGA-II its signature behaviour: converge toward the front (sorting) while preserving diversity across it (crowding). TGraphX also ships single-objective optimizers — GeneticAlgorithmOptimizer, SimulatedAnnealingOptimizer, HillClimbingOptimizer — for when you genuinely have one objective.

Encoding graphs and scoring them

The thing being evolved is a GraphGenome, mutated and recombined by operators such as mutate_add_node, mutate_add_edge, mutate_node_feature, and edge_set_crossover. Objectives come from tgraphx/evolutionary/fitness.py, which provides ready-made fitness functions:

A multi-objective run might pair connectivity_fitness against sparsity_fitness — the canonical "connected but sparse" tension — and NSGA-II returns the Pareto front of graphs that trade the two off.

Honest framing

Several honest qualifications. The evolutionary subsystem is Beta — tested and documented, but evolutionary search is inherently sample-inefficient and stochastic; results depend on population size, mutation rates, and seeds, so report them and do not expect determinism without fixing a seed. NSGA-II finds an approximation of the Pareto front, not a proven-optimal one. And whether evolutionary optimization beats a problem-specific heuristic is task-dependent and should be profiled and measured against the source, not assumed — the package provides the algorithm, not a benchmark that would justify a general performance claim. If your objectives can be made differentiable, gradient methods may be more efficient; evolutionary search shines when the objective is black-box or discrete.

Reading a Pareto front

A returned ParetoFront is a set of solutions, and reading it well is part of the method. Plot the front in objective space: each point is a graph you cannot improve on one objective without sacrificing another, and the shape of the curve shows how steep the trade-off is. A nearly flat region means one objective can be improved cheaply; a sharp knee is often the most interesting operating point, because it is where further gains on one axis start to cost a lot on the other. The crowding distances the ParetoFront carries indicate how evenly the front is sampled — large gaps suggest running the optimiser longer or with a larger population to fill them in.

When to prefer single-objective

If your objectives can honestly be combined into one — a fixed weighting you can defend, or a hard constraint plus a single objective — a single-objective optimiser (GeneticAlgorithmOptimizer, SimulatedAnnealingOptimizer, or a gradient method when the objective is differentiable) is simpler and usually cheaper than NSGA-II. Reserve multi-objective search for when the trade-off itself is the deliverable and you genuinely cannot pick weights in advance. Choosing NSGA-II when a weighted sum would do adds stochastic cost for a front you were never going to use.

And as with any stochastic search, fix and report your seed: a Pareto front from one run is a sample of the true frontier, and a second seed will give a slightly different set. Reporting the seed and population size is what makes a multi-objective result reproducible rather than anecdotal.

Related guides

• Evolutionary Optimization of Graph Structures
• Measuring Generated Graphs
• Graph Generation with Tensor-Valued Node Features

Conclusion

When graph objectives conflict, the honest output is a Pareto front, and NSGA-II — non-dominated sorting for convergence, crowding distance for diversity — is the standard way to approximate it. TGraphX implements both in tgraphx/evolutionary/multi_objective.py, with a library of graph fitness functions and mutation operators. Treat it as a Beta, stochastic optimiser for black-box or discrete objectives, report your seeds, and you get a principled view of the trade-offs your graph design actually faces.