Does coarsening always preserve connectivity?

The aggregation described preserves intergroup adjacency, but that is not a guarantee about every detailed connectivity measure or arbitrary coarsening scheme.

Can a coarse solution be mapped back?

Yes, if group membership is retained. Refinement may then change assignments of individual vertices.

Is a smaller graph automatically faster overall?

No. Coarsening, solving and refinement all contribute to total cost.

AI Glossary / Mathematics and optimization / Advanced

Graph Coarsening Algorithm

Definition

A graph coarsening algorithm creates a smaller graph by combining selected vertices into groups and aggregating their connections. It is commonly part of a multilevel optimization method that solves a smaller problem first, then transfers and refines the solution on progressively finer graphs.

What it means

Coarsening replaces individual vertices with representatives, often called supernodes. The resulting graph can make a large problem easier to process, but it no longer exposes every distinction between the original vertices.

The grouping rule and aggregation scheme depend on the task. A method designed to support balanced partitioning need not preserve shortest-path distances, individual centrality rankings or every property needed by a graph-learning model.

How it works

In a matching-based scheme, select disjoint pairs of adjacent vertices and contract each pair. Unmatched vertices remain as individual groups. Sum member vertex weights to preserve quantities such as computational load, and sum edge weights between groups to represent their combined connection weight.

Heavy-edge matching favors strong connections between eligible unmatched neighbors. Its greedy choices depend on visit order and do not guarantee a globally maximum-weight matching. Several coarsening levels may be created before solving the reduced problem.

During uncoarsening, each coarse assignment is transferred to its member vertices. Refinement can then move individual vertices and improve the solution at finer resolution. The mapping between levels is essential: it connects the compact representation to the original problem and enables detailed evaluation.

Three practical examples

1. Parallel computation: partition a graph representing simulation work while balancing vertex workloads and reducing communication across partitions. Coarsening makes the initial partitioning problem smaller.

2. Network visualization: aggregate groups to present broad connectivity patterns, while retaining a way to inspect their member vertices.

3. Graph-learning research: reduce graph size while tracking how aggregation affects the downstream task. Good compression alone does not demonstrate that important predictive information has been preserved.

Think of it this way

Imagine replacing a city street map with a map of districts. Connections between districts summarize many streets, helping with a broad allocation problem. You still need the original map when deciding which individual street belongs in a boundary area or calculating a detailed route.

Worked example

Consider an original undirected weighted graph with six vertices, A through F, each having vertex weight one. Its edges are AB with weight 8, CD with 7, EF with 6, AC with 2, BD with 3, CE with 1, DF with 4, and BE with 2. No other edges exist.

Choose the disjoint pairs AB, CD and EF for contraction. They can arise from a suitable heavy-edge matching visit order, but the example stipulates the pairs rather than claiming that every order selects them. Call the resulting supernodes X = {A, B}, Y = {C, D} and Z = {E, F}.

Each supernode has vertex weight two. The X - Y edge has weight 2 + 3 = 5, from AC and BD. The Y - Z edge has weight 1 + 4 = 5, from CE and DF. The X - Z edge has weight 2, from BE.

The internal edges AB, CD and EF no longer appear as edges between supernodes. The original total edge weight is 33, and the coarse intergroup total is 12. The difference, 21, is exactly the sum of the three contracted internal weights.

Now place X on one side of a cut and Y with Z on the other. Its coarse cut weight is 5 + 2 = 7. Expanding the assignment gives {A, B} versus {C, D, E, F}; the crossing original edges are AC, BD and BE, also totaling 7.

This equality holds for cuts that keep every group intact under the stated aggregation. It does not mean all original cuts remain available. For example, a partition with three original vertices on each side cannot be represented using only these weight-two supernodes. Uncoarsening and refinement are needed to permit such a split.

The example therefore preserves the weight of a represented cut while restricting which cuts can be expressed.

Illustrative case study

In a fictional simulation project, engineers partition a workload graph across processors. Coarsening reduces the graph enough to obtain an initial partition quickly, but an aggressive grouping choice combines several high-load vertices into indivisible coarse units.

The coarse solution has a small edge cut yet poor load balance. The team revisits group-size limits, preserves workload weights and evaluates refinement on the original graph. It compares total runtime and final balance alongside communication estimates.

A smaller graph is useful only if the final expanded solution still meets the operational requirements.

Common misconceptions and mistakes

Coarsening is not simply deleting low-weight edges. It changes the vertex representation, while graph sparsification can reduce edges without merging vertices.

A supernode's degree is not generally the degree of any one member. Internal connections and combined external connections change the interpretation.

Heavy-edge matching is a heuristic, not an assurance of the best matching or best final partition. Its effect depends on the graph and later refinement.

Do not assume that preserving aggregated cut weights preserves every graph property. Paths, labels, feature distributions and small structures can require additional treatment.

Business use

Coarsening can support large network-analysis or allocation workloads when processing the full graph directly is costly. Its value should be measured against the quality and cost of the complete downstream result, including uncoarsening and refinement.

Document what vertex and edge weights mean, how groups are formed and which properties must be retained. Compare the final result on the original graph, particularly for balance requirements or important small groups that an aggregate view could obscure.

Check your understanding

What is the X - Y edge weight in the example?

Answer: Five, from original edges of weights two and three.

Why is the represented cut weight seven?

Answer: It crosses X - Y and X - Z, with weights five and two.

Can the three coarse vertices express an exactly balanced three-versus-three split?

Answer: No; each represents two original vertices.

Related terms

Graph partitioning
edge contraction
matching
heavy-edge matching
multilevel optimization
graph sparsification
graph pooling

Learn next

Enumerate cuts of the six-vertex example and identify which survive the chosen grouping. Then change the matching and compare both the representable cuts and the work required during refinement.

Sources

George Karypis and Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, 1998, coarsening and refinement framework: https://people.eecs.berkeley.edu/~jordan/sail/readings/karypis-kumar.pdf

The weighted graph calculations and simulation case are original illustrations.

Previous: Graph clustering Next: Graph coloring