Multi-Level Graph Representation

RWG1: Reyan Ahmed, Hang Chen, Alon Efrat, David Glickenstein, Iqbal Hossain, Stephen Kobourov, Richard Spence, Joe Watkins

Motivation

• Many real-world graphs are large (millions of vertices, billions of edges)
• Analyzing such graphs is computationally expensive

​

Motivation

• Many real-world graphs are large (millions of vertices, billions of edges)
• Analyzing such graphs is computationally expensive
• Graph mining and graph statistics are often used

Example: simple connected graph G=(V,E): |V|=12, |E|=21, ▲=10, L=2.0

​

Motivation

• Many real-world graphs are large (millions of vertices, billions of edges)
• Analyzing such graphs is computationally expensive
• Graph mining and graph statistics are often used

Example: simple connected graph G=(V,E): |V|=12, |E|=21, ▲=10, L=2.0

​

|V|=12, |E|=21

▲=10, L=2.0

|V|=12, |E|=21

▲=10, L=2.0

|V|=12, |E|=21

▲=10, L=2.0

|V|=12, |E|=21

▲=10, L=2.0

Not Surprising Given Anscombe’s Quartet

Traditional Multi-Level Representation

• Hierarchical clustering of the graph
• Abstract levels-of-detail: meta-nodes and meta-edges
• Some Issues
• Balanced clustering
• Interpreting clusters (meta-nodes)
• Interpreting links (meta-edges)
• Confusing visualizations
• Difficult to interact with (search, zoom, pan)

​

More Intuitive Multi-Level Representation

• Borrow from the details-on-demand map metaphor
• On every level of the hierarchy we have a graph with real vertices and edges
• The graph on each level is “similar” to the original graph
• Important vertices and paths are shown on high levels
• Less important vertices and paths appear when zooming in
• What is the notion of importance?
• Do vertices and edges come with importance values?
• If not, use centrality metrics (e.g., degree, betweenness)

Using the Map Metaphor

• How can we define a natural “semantic zoom” representation?

Using the Map Metaphor

​

• How can we define a natural “semantic zoom” representation?

Using the Map Metaphor

• How can we define a natural “semantic zoom” representation?

Using the Map Metaphor

​

How can we define a natural “semantic zoom” representation?

• We can often group vertices by importance (at what level of detail do they show)
• But what about the edges?

Starting Simple: Steiner Trees

“A very simple but instructive problem was treated by Jacob Steiner, the famous representative of geometry at the University of Berlin in the early nineteenth century. Three villages A,B,C are to be joined by a system of roads of minimum length.” Courant and Robbins, 1941

Fermat in 1679 already mentions the problem of “finding for three given points in the plane a fourth one in such a way that the sum of its distances to the given points is minimized.”

Torricelli found a geometrical solution for this problem in 1640.

​

​

​

​

A

B

C

Starting Simple: Steiner Trees

​

“A very simple but instructive problem was treated by Jacob Steiner, the famous representative of geometry at the University of Berlin in the early nineteenth century. Three villages A,B,C are to be joined by a system of roads of minimum length.” Courant and Robbins, 1941

Fermat in 1679 already mentions the problem of “finding for three given points in the plane a fourth one in such a way that the sum of its distances to the given points is minimized.”

Torricelli found a geometrical solution for this problem in 1640.

​

​

​

​

Steiner Problem in Graphs

Given: A connected graph G=(V,E) and set K ⊆ V of terminals.

Find: A Steiner minimum tree for K in G, that is, a Steiner tree T for K such that |E(T)|=min{|E(T’)|, where T’ is a Steiner tree for K in G}.

In the weighted variant edges have weights and the goal is to minimize the sum of edges in the tree (rather than just the number of edges).

Both variants are NP-hard…

but there are good approximation algorithms

The Multi-Level Steiner Tree (MLST) Problem

Given: graph G=(V,E), along with a vertex filtration V⊃V₁⊃V₂⊃...⊃Vᵢ

Find: a set of Steiner trees T⊃T₁⊃T₂⊃...⊃Tᵢ such that Tᵢ spans Vᵢ and the total number of edges is minimized.

In the weighted variant edges have weights and the goal is to minimize the sum of edges in all the trees.

​

The Multi-Level Steiner Tree (MLST) Problem

What do we know?

• The MLST problem is NP-hard
• Efficient 4k-approximation, k is the number of levels
• We don’t know if MLST is approximable within a constant

Many variants to consider:

• Edge-weighted, vertex-weighted, both, either, none
• What function is optimized (e.g., bottleneck MLST should be easy)?
• What is given (e.g., what if we can compute the vertex filtration)?

What might work well in practice?

​

Graph Spanners

Given a connected graph G=(V,E) and integer t ≥ 1, S=(V,E’) is a t-spanner of G, if for every pair of vertices u,v ∈ V, the distance between u,v in S is at most t times the distance between u,v in G.

​

Goal: remove as many edges as possible from G while still approximately preserving distances between all pairs of vertices.

​

​

The Multi-Level Graph Spanner Problem

Given: graph G=(V,E), along with a vertex filtration V⊃V₁⊃V₂⊃...⊃Vᵢ and t₁≤t₂≤...≤tᵢ

Find: a set of spanners S₁⊃S₂⊃...⊃Sᵢ such that Sᵢ is a tᵢ-spanner for Vᵢ and the total number of edges is minimized.

Note: when the t-values are large, we get the MLST problem

​

What Was the Problem?

We wanted to find multi-level representations of graphs:

• On every level we have a graph with real vertices and edges
• Important vertices and paths shown on high levels
• Less important vertices and paths appear lower
• The graph on each level is similar to the input graph

​

What are we doing instead?

• two new problems: MLST and MLGS

​

RWG1: Large Graphs

Alon Efrat, David Glickenstein, Stephen Kobourov, Joe Watkins, Felice De Luca, Keaton Hamm, Iqbal Hossain, Vahan Huroyan, Raymundo Navarrete, Faryad Sahneh, Reyan Ahmed, Hang Chen, Mohammad Latifi, Richard Spence

Meeting: Thursdays, 3-4:15pm, Gould-Simpson 737

​

• R. Ahmed, P. Angelini, F. Sahneh, A. Efrat, D. Glickenstein, M. Gronemann, N. Heinsohn, S. Kobourov, R. Spence, J. Watkins, A. Wolff, “Multi-Level Steiner Trees,” Symposium on Experimental Algorithms (SEA), 2018.
• R. Ahmed, K. Hamm, M. Jebelli, S. Kobourov, F. Darabi Sahneh and R. Spence, “Approximation algorithms and an integer program for multi-level graph spanners,” Symposium on Experimental Algorithms (SEA), 2019.
• F. Darabi Sahneh, A. Efrat, S. Kobourov, R. Spence, “Computing Vertex-Weighted Multi-Level Steiner Trees,” arXiv:1811.11700, 2019.
• R. Ahmed, K. Hamm, M. Jebelli, S. Kobourov, F. Sahneh, R. Spence, “A General Framework for Multi-level Subsetwise Graph Sparsifiers,” arXiv:1905.00536, 2019.
• F. De Luca, I. Hossain, S. Kobourov, K. Börner, “Multi-level tree based approach for interactive graph visualization with semantic zoom,” arXiv:1906.05996, 2019.

​

​

​

​