Page 1 of 58

Graphical Abstract

Distributed Approximate Minimal Steiner Trees with Millions of

Seed Vertices on Billion-Edge Graphs

Tahsin Reza, Trevor Steil, Geoffrey Sanders, Roger Pearce

1

(a) Input Graph and Seed Vertices (b) Output Steiner Tree

5

6 7

8

9

2

4

3

16

18 20

4 2

2

4

2

1

1

2

2

1

5

6 7

8

9

2

4

3

16

18 20

4 2

2

4

2

1

1

2

2

Page 2 of 58

Highlights

Distributed Approximate Minimal Steiner Trees with Millions of

Seed Vertices on Billion-Edge Graphs

Tahsin Reza, Trevor Steil, Geoffrey Sanders, Roger Pearce

• Voronoi cell computation is an enabler for scaling to large graphs and

seed sets.

• Message prioritization accelerates convergence of distance computation.

• Combining vertex- and edge- centric processing can bring forth superior

performance.

• 2-approx. MST can preserve the theoretical bound of a 2-approx.

Steiner tree algo.

Page 3 of 58

Distributed Approximate Minimal Steiner Trees with

Millions of Seed Vertices on Billion-Edge Graphs

Tahsin Reza∗

, Trevor Steil, Geoffrey Sanders, Roger Pearce

aCenter for Applied Scientific Computing, Lawrence Livermore National

Laboratory, 7000 East Ave, Livermore, 94550, CA, USA

Abstract

In this paper, we present a parallel 2-approximation Steiner minimal tree

algorithm and its MPI-based distributed implementation. In place of expen- sive distance computations between all pairs of seed vertices, the solution we

employ exploits a cheaper Voronoi cell computation. Our design leverages

asynchronous processing and message prioritization to accelerate convergence

of distance computations, and harnesses vertex and edge centric processing

to offer fast time-to-solution. We demonstrate scalability and performance

using real-world graphs with up to 128 billion edges and 512 compute nodes,

and show the ability to find Steiner trees with up to one million seed vertices.

Using 12 data instances, we present comparison with the state-of-the-art ex- act solver, SCIP-Jack, and two sequential 2-approximate algorithms. We

empirically show that, on average, the total distance of the Steiner tree iden- tified by our solution is 1.1290 times greater than the Steiner minimal tree –

well within the theoretical approximation bound of 2.

Keywords: distributed computing, hpc, asynchronous processing,

∗Corresponding author

Email addresses: reza2@llnl.gov (Tahsin Reza), steil1@llnl.gov (Trevor Steil),

sanders29@llnl.gov (Geoffrey Sanders), rpearce@llnl.gov (Roger Pearce)

Preprint submitted to JPDC, SI-IPDPS-2022 May 13, 2023

Page 4 of 58

distributed graph processing, parallel graph algorithms, steiner tree

PACS: 0000, 1111

2000 MSC: 0000, 1111

1. Introduction

A network is often represented by a distance-weighted graph G(V, E, d),

with data entities represented by vertices V, their relationships represented by

edges E ⊂ V × V, and distances d : E → [1,∞). In this work, smaller weights

represent stronger relationships (or closer distances between the underlying

data entities). For {u, v} ∈ V, the weight or distance of (u, v) ∈ E is written

d(u, v), and for a knowledge network, is often a function of the metadata

living on u, v, (u, v) and the relationship type of (u, v). The total weight or

total distance of a set of edges associated with a subgraph H (e.g., a cluster,

a tree or a path) is the sum of the distances D(H) = P

(u,v)∈H d(u, v). For

{u, v} ∈ V and (u, v) ̸∈ E, d1(u, v) is the shortest total distance of any path

from u to v.

We call the user’s entities of interest the seed vertices, S ⊂ V. Various ap- plications need different magnitudes of seed set sizes. The goal is to compute

a tree subgraph T that minimally connects all vertices in S, preferring edges

that have low distance over those that are larger – known in the literature

as the Steiner minimal tree problem (1).

Given a set of seed vertices S (also called terminal vertices in the liter- ature), a Steiner tree T (VT , ET , d) of G(V, E, d) is an acyclic subgraph that

connects all of S. A Steiner tree T is called a Steiner minimal tree if its

total distance D(T ) = P

e∈ET

d(e) is minimal among all Steiner trees for

2

Page 5 of 58

1

(a) Input Graph and Seed Vertices (b) Output Steiner Tree

5

6 7

8

9

2

4

3

16

18 20

4 2

2

4

2

1

1

2

2

1

5

6 7

8

9

2

4

3

16

18 20

4 2

2

4

2

1

1

2

2

Figure 1: (a) A data graph G, and given seed vertices S, have red fill. (b) A Steiner tree

T of G. Steiner vertices S

′ ∈ V \ S have blue fill. Vertices and edges not in the Steiner

tree T have light grey outline and fill.

G and S ⊂ V. In the literature, the vertex set S

′ = VT \ S is commonly

refereed as Steiner vertices. A Steiner vertex may not be required to be

in a Steiner tree but its inclusion may lower the total distance (2; 3; 1).

Fig. 1 shows an example. Gilbert and Pollack (2) are often credited for

formalising the Steiner minimal tree problem which has direct applications

to VLSI design (4; 5), communication network optimization (6; 7), compu- tational and systems biology (8; 9), and knowledge discovery and manage- ment (10; 11). The problem of finding a Steiner minimal tree of a graph

and arbitrary seed vertices is known to be NP-hard (the decision variant is

NP-complete) (1; 12). Therefore, polynomial time algorithms for finding a

Steiner tree T with a total distance D(T ) close to the total distance of a

Steiner minimal tree Dmin(G) are sought due to their practical relevance.

There has been continuing interest in practical polynomial-time solutions

with tight approximation bounds. Takahashi et al. (13) presents an algo- rithm with the approximation bound D(T )/Dmin(G) ≤ 2(1 − 1/|S|). The

algorithm by Kou et al. (14) (known as the KMB algorithm) improves the

3

Page 6 of 58

bound to D(T )/Dmin(G) ≤ 2(1 − 1/l) where l is the minimum number of

leaves in any Steiner minimal tree for G and S. A corpus of algorithms cap- italize over the KMB algorithm and offer improved sequential runtime com- plexity while preserving the 2-approximation bound: algorithms by Wu et

al. (15) (known as the WWW algorithm), Widmayer (16) and Mehlhorn (17)

are some of the most well known 2-approximation solutions.

Despite its rich theoretical literature, work related to scalable implemen- tations of parallel Steiner minimal tree computations is rather scarce. In (18),

we presented a parallel 2-approximation Steiner minimal tree algorithm and

its MPI-based distributed implementation. The solution is based on com- puting Voronoi cells similar to the algorithm in (17): Mehlhorn replaces the

most computationally expensive task in the KMB algorithm, i.e., computing

all-pairs-shortest-paths (APSP) between the vertices in S, with a Voronoi

cell computation of each s ∈ S. This solution approach stems from the ob- servations that, in practice, the Voronoi cell approach is less expensive then

APSP computation (see Table 1), and has higher parallel efficiency than min- imum spanning tree (MST) computation on the entire graph (19) (that the

WWW and Widmayer algorithms do). In (18), we demonstrated, scalability

and performance of this distributed solution using eight real-world graphs

with up to 128 billion edges and up to 512 compute nodes (8K processes),

achieving up to 90% efficient strong scaling that, to the best of our knowl- edge, is the largest scale to date for the Steiner tree problem. We showed

the ability to find Steiner trees with up to 10K seed vertices in under one

minute. On average, the total distance D(T ) of the Steiner tree identified by

our solution in (18) is 1.0527 times greater than the Steiner minimal tree –

4

Page 7 of 58

Table 1: Runtime comparison of all-pairs-shortest-path (APSP) and Voronoi cell (VC)

computation using two graphs and three seed sets. All experiments use a single thread.

Dataset details are in §5, Table 4.

|S| 10 100 1000

APSP VC APSP VC APSP VC

LVJ 49.7s 30.0s 539.2s 35.1s 5,813.3s 104.5s

PTN 26.7s 12.9s 270.3s 26.6s 2,767.4s 85.5s

well within the theoretical bound.

In this paper, we report recent advancements in our distributed 2-approximate

Steiner minimal tree solution and their experimental demonstration. To dis- tinguish the two solution approaches, in the remainder of the paper, we refer

to the work presented in (18) as D-1, and call the new solution D-2. The ex- tended work D-2 addresses key limitations of our earlier effort in D-1: in (18)

we mentioned that, on our testbed (§5), going from 1K seed to 10K seeds,

we had to double the number of compute nodes to meet increased memory

demands of D-1. The high memory usage is due to large message buffers

required to perform MPI collective operations on the distance graph (§2).

The issue is compounded by the design choice to compute the exact MST

of the distance graph using a serial algorithm (locally on a compute node).

Since the size of the distance graph grows proportionally with the number

of seeds, D-1’s design offers limited scalability in that regard. D-2 addresses

each of these limitations of D-1 and embraces a fully scale out design that

imposes no limitations on the size of the graph dataset and number of seed

vertices it can support. Below we summarize the new contributions in this

paper.

5

Page 8 of 58

(i) We present a memory efficient scale out solution for 2- and 2β-approximate

Steiner minimal tree computation. Similar to D-1 (18), the extended solu- tion D-2 is also based on Voronoi cell identification for distance computa- tion. However, D-2 significantly differs from D-1 with respect to distance

graph construction and operations on the distance graph towards identi- fying the Steiner tree (§3 and §4).

(ii) D-2 replaces the serial routine in D-1 for computing exact MST of the

distance graph with a distributed approximate spanning tree algorithm

(A-MST) (20). This enables D-2 to accommodate larger seed sets more

efficiently. We provide theoretical guarantees that the distributed A-MST

approach is guaranteed to produce Steiner trees whose total distance is

within a factor 2β of an actual minimal Steiner tree, where β is a con- figurable approximation bound on the approximate MST algorithm (§4.3

and § Appendix A).

(iii) D-1 partially relies on MPI collective operations for distance graph con- struction and distributing the MST of the distance graph to data par- titions. With an increasing number of seeds, growing message buffers

associated with MPI collective operations become the primary memory

bottleneck. D-2 introduces new asynchronous distributed routines that

eliminate the need for MPI collective operations, hence improving re- source efficiency (§4).

(iv) We demonstrate scalability and performance using eight real-world graphs

with up to 128 billion edges and up to 512 compute nodes (8K processes)

(§5.4) and show the ability to find Steiner trees with up to 1M seed vertices

6