Crossing Minimization within Graph Embeddings

Amina Shabbeer, Cagri Ozcaglar, Kristin P. BennettarXiv 2012 · DOI · arXiv

TL;DR

Researchers have developed a novel way to create cleaner graph visualizations by turning the discrete problem of "edge crossings" into a continuous optimization challenge. By leveraging Farkas’ Lemma—a classic tool from linear programming—they’ve created an algorithm that minimizes crossings while simultaneously preserving the high-dimensional relationships between data points.

What Problem Does This Paper Address?

When we visualize complex data as a graph, we usually have two competing goals. First, we want proximity preservation: nodes that are similar in high-dimensional space should be close together on our 2D screen. Second, we want readability: we want to minimize edge crossings, as "spaghetti" graphs are notoriously difficult for the human brain to process.

The catch? Minimizing edge crossings is an NP-complete problem, meaning it's computationally "hard." Most existing tools either focus on preserving distances (like Multidimensional Scaling) but ignore crossings, or they focus on planarity (drawing without crossings) but distort the actual data relationships. This paper bridges that gap, offering a way to optimize for both at the same time.

Methods

The core innovation of this paper is the Crossing Reduction with Stress Majorization (CR-SM) algorithm.

The authors move away from traditional integer programming (which is slow and discrete) and instead treat edge crossing as a geometric separation problem. They use Farkas’ Lemma to prove that if two edges do not cross, there must exist a linear hyperplane (a line in 2D) that separates them.

This allows them to:

  1. Formulate Constraints: Express the "no-crossing" condition as a system of nonlinear inequality constraints.
  2. Borrow from SVMs: Much like Support Vector Machines (SVMs) find a "maximum margin" to separate data classes, this method creates a penalty function that is zero when edges don't cross and increases as they overlap.
  3. Integrate with Stress Majorization: They plug these penalties into a standard Multidimensional Scaling (MDS) framework. The algorithm iteratively nudges nodes to reduce "stress" (distance errors) while slowly cranking up the penalty on any remaining edge crossings.

Datasets

The authors evaluated their approach on two distinct types of data:

  • Spoligoforests (Real-world): These are phylogenetic forests representing strains of Mycobacterium tuberculosis. Each node is a DNA fingerprint, and edges represent mutations. This is a "heterogeneous" dataset where the genetic distance between strains is just as important as the tree structure itself.
  • Synthetic Planar Graphs: A suite of 160 randomly generated graphs in high-dimensional space ($R^n$). These were specifically designed to be "tricky"—they have a known planar (no-crossing) layout, but that layout has very high "stress," making it a difficult balancing act for any algorithm.

Key Insights and Ideas

  • The Continuous Shift: The most significant "aha moment" is realizing that edge crossing—traditionally a combinatorial problem—can be handled using the tools of continuous optimization and convex geometry.
  • Guiding the Search: Interestingly, the authors found that adding edge-crossing penalties sometimes helped the algorithm find better overall layouts. Because the "stress" function in MDS is non-convex (full of local minima), the crossing penalties act as a guide, pushing the optimization out of poor local minima and toward more globally desirable configurations.
  • Beyond Edges: The math used here isn't limited to lines. The authors note that this framework can be generalized to prevent overlaps between any convex shapes, such as labels or node icons, which is a common headache in automated map and graph labeling.

Key Results

The CR-SM algorithm demonstrated a clear advantage over state-of-the-art methods like Graphviz NEATO, Laplacian Eigenmaps, and Stochastic Neighborhood Embedding (SNE):

  • Drastic Crossing Reduction: In the "SpolDB4" dataset, standard MDS produced 51 crossings. CR-SM reduced this to just 2 crossings with only a 6% increase in stress.
  • Superior Readability: Compared to Laplacian Eigenmaps and SNE—which often caused nodes to collapse into dense, unreadable clusters—CR-SM maintained a clear radial structure that reflected the underlying evolutionary distances.
  • Efficiency in High Dimensions: For the synthetic 50-node graphs, CR-SM frequently found layouts with zero crossings, whereas standard MDS often left hundreds of crossings behind.

Limitations and Future Work

While the results are promising, the authors acknowledge a few hurdles:

  • Scalability: The current implementation relies on general-purpose optimization functions in Matlab (fminunc). For massive graphs with thousands of nodes, the $O(\ell^2)$ penalty terms (where $\ell$ is the number of edges) could become a bottleneck.
  • Local Optima: While the penalties help, the problem remains non-convex. The algorithm's success can still depend on its starting point.
  • Future Directions: The authors suggest that specialized, "massively scalable" linear SVM algorithms could be adapted to handle the edge-crossing constraints, potentially opening the door to visualizing much larger datasets.

Summary updated

Abstract

We propose a novel optimization-based approach to embedding heterogeneous high-dimensional data characterized by a graph. The goal is to create a two-dimensional visualization of the graph structure such that edge-crossings are minimized while preserving proximity relations between nodes. This paper provides a fundamentally new approach for addressing the crossing minimization criteria that exploits Farkas' Lemma to re-express the condition for no edge-crossings as a system of nonlinear inequality constraints. The approach has an intuitive geometric interpretation closely related to support vector machine classification. While the crossing minimization formulation can be utilized in conjunction with any optimization-based embedding objective, here we demonstrate the approach on multidimensional scaling by modifying the stress majorization algorithm to include penalties for edge crossings. The proposed method is used to (1) solve a visualization problem in tuberculosis molecular epidemiology and (2) generate embeddings for a suite of randomly generated graphs designed to challenge the algorithm. Experimental results demonstrate the efficacy of the approach. The proposed edge-crossing constraints and penalty algorithm can be readily adapted to other supervised and unsupervised optimization-based embedding or dimensionality reduction methods. The constraints can be generalized to remove overlaps between any graph components represented as convex polyhedrons including node-edge and node-node intersections.
BibTeX
@misc{shabbeer2012crossing,
  author = {Amina Shabbeer and Cagri Ozcaglar and Kristin P. Bennett},
  title = {{Crossing Minimization within Graph Embeddings}},
  year = {2012},
  eprint = {1210.2041},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1210.2041},
}
Figure