Maximizing algebraic connectivity for graph sparsification

MAC is an algorithm for solving the maximum algebraic connectivity augmentation problem. Specifically, given a graph containing a (potentially empty) set of "fixed" edges and a set of "candidate" edges, as well as a cardinality constraint K, MAC tries to find the set of K cadidate edges whose addition to the fixed edges produces a graph with the largest possible algebraic connectivity. MAC does this by solving a convex relaxation of the maximum algebraic connectivity augmentation problem (which is itself NP-hard). The relaxation allows for "soft" inclusion of edges in the candidate set. When a solution to the relaxation is obtained, we round it to the feasible set for the original problem.

NOTE [3/28/2024]: We will soon be merging a set of widespread changes in PR #5. These changes bring new randomized rounding procedures, new experimements, unit tests, and documentation. See PR #5 for details, or to try out the latest MAC updates before they are merged.

Install MAC locally with

pip install -e .

Now you are ready to use MAC.

From the examples directory, run:

python3 random_graph_sparsification.py

which demonstrates our sparsification approach on an Erdos-Renyi graph.

In the same directory, running:

python3 petersen_graph_sparsification.py

will show the results of our approach on the Petersen graph.

In each case, the set of fixed edges is a chain, and the remaining edges are considered candidates.

For the pose graph examples, you will need to install SE-Sync with Python bindings.

Once that is installed, you need to modify the SE-Sync path in g2o_experiment.py:

# SE-Sync setup
sesync_lib_path = "/path/to/SESync/C++/build/lib"
sys.path.insert(0, sesync_lib_path)

Finally, run:

python3 g2o_experiment.py [path to .g2o file]

to run MAC for pose graph sparsification and compute SLAM solutions. Several plots will be saved in the examples directory for inspection.

If you found this code useful, please cite our paper here:

@article{doherty2022spectral,
  title={Spectral {M}easurement {S}parsification for {P}ose-{G}raph {SLAM}},
  author={Doherty, Kevin J and Rosen, David M and Leonard, John J},
  journal={arXiv preprint arXiv:2203.13897},
  year={2022}
}

• Currently mac.py assumes that there is at most one candidate edge between any pair of nodes. If your data includes multiple edges between the same pair of nodes, you can combine the edges into a single edge with weight equal to the sum of the individual edge weights before using MAC.