NNP-NET: Accelerating t-SNE Graph Drawing for Very Large Graphs by Neural Networks

Hundreds of GD methods have been proposed in the past decades [19, 38]. We next focus on methods that aim to satisfy the contributions outlined in Sec. 1.

Given a dataset $\text{X}=\{{\text{x}}_i\}\subset {ℝ}^n$, dimensionality reduction (DR) methods, also called projections, $M:𝐗\to 𝐘$, create a dataset $\text{Y}=\{{\text{y}}_i\}\subset R^m$, $m\ll n$ which preserves the so-called data structure of $𝐗$, such that points close (resp. far) in $R^n$ are mapped to points close (resp. far) in $R^m$. DR methods accept as input either $𝐗$ or a matrix of the pairwise distances between its data points. Many DR methods exist, each of which preserves different data structure aspects and, as such, produce different drawings of the same dataset, differing significantly in terms of quality, speed, robustness, out-of-sample ability, and ease of use [15].

NNP (Neural Network Projection) [14] is a meta-approach that aims to solve the scalability and lack of out-of-sample ability for any other projection technique. Given a subset of ${𝐗}^{\prime }\subset 𝐗$ (a few thousand points) and its projection ${𝐗}^{\prime }$ computed by any user-chosen method, NNP learns the mapping $X^{\prime }\to M({𝐗}^{\prime })$ by a simple neural network (3 fully connected hidden layers, sizes 256, 512, 256). This mapping is used to project the entire dataset $𝐗$. NNP creates projections of quality close to the ground truth in time $O(|𝐗|)$; is robust to small changes in the input data [6]; can imitate any user-chosen projection; handles datasets of any dimensionality $n$; and has no free user set parameters. As such, NNP is an ideal candidate to replace t-SNE in tsNET for graph drawing. Yet, a key obstacle exists: NNP needs a high-dimensional dataset $𝐗$ as input, not a distance matrix computed on $𝐗$, making it not directly applicable to graphs. We describe next how we overcome this limitation.

NNP requires a dataset $𝐗=\{x_i\}\subset {ℝ}^n$ as input, where $n$ is a free-to-choose parameter. Creating $𝐗$ from $G$ in linear time in relation to the graph size, one of our key goals, rules out using $G$’s full distance matrix. We propose two methods to create the embedding $𝐄={\{e(v)\}}_{v\in V}$: (1) distance-to-pivot, uses a smaller matrix $A$ as $𝐄$, computed the same way as PMDS [4] computes its pivot matrix; and (2) projection, project $v$ to ${ℝ}^n$ dimensions via PMDS using $p=250$ pivots. Method (2) was chosen for its better layout quality while sacrificing speed (see Appendix A). Another advantage of (2) is that PMDS can be freely swapped with any other projection technique. Note also that, while PMDS cannot project data to 2D accurately in general, we only use it as an intermediate mapping (to $n\gg 2$ dimensions); the final 2D layout is created by NNP. Setting $n=50$ balances well between quality and computing time (see Appendix B).

To train NNP, we need to extract a small but representative subgraph $G^{\prime }\subset G$. Following various tests (Appendix C), we set the number of nodes in our subgraph of our training set to be equal to $S=10000$. Then $G^{\prime }=(V^{\prime },E^{\prime })$ and $S=|V^{\prime }|$. Many multilevel GD methods extract such a subgraph $G^{\prime }$, e.g., SFDP [27] and FM³ [22]. These multilevel layout techniques differ in that (1) they reduce $G$ until it is not useful to reduce any further, while we reduce to a fixed size $S$; (2) they care about all intermediate levels; we only care about the final $G^{\prime }$.

To consistently reduce $G$ to $S$ nodes, we use a multilevel scheme similar to DRGraph [47], i.e., coarsen $G$ into a sequence $G,G^1,G^2,\mathrm{\dots },G^{\prime }$ of increasingly smaller graphs. Each iteration, we repeatedly choose a center node $𝐜\in G^i$ from all not yet clustered nodes that has the lowest neighbor count. All not-yet-clustered direct neighbors of $𝐜$ are added to $𝐜$’s cluster. The iteration ends when all nodes of $G^i$ are clustered. Finally, we create $G^{i+1}$ using the cluster centers $𝐜$ as nodes, and connecting nodes corresponding to adjacent clusters. Iterations continue until we reach the target size $S$.

Not all graphs can be reduced to the target size $S$ by this coarsening method. To handle this, we use a stopping heuristic that exits coarsening when $|G^i|>0.95|G^{i-1}|$. We then use a slower backup method to create $G^{\prime }$ by selecting $S$ such points from $G^i$. This is done using pivot-points in a max-min approach, like PMDS [4]– choose a first node randomly, then add nodes in order of highest minimum distance to all already chosen nodes until we get $S$ nodes. This gives good results but has a complexity of $O(NS)$. Appendix D compares the pivot-points and coarsening methods showing that the latter yields better quality-vs-speed.

After constructing the subgraph $G^{\prime }$, we lay out $G^{\prime }$ using tsNET* and train NNP to mimic the produced layout when given its corresponding embedding.

Training NNP on the subgraph $G^{\prime }$ gives good results in terms of training error (see next Sec. 4). Yet, the produced layouts contain some amount of high-frequency noise, visible in e.g. graphs with a grid-like structure (Fig. 2 left). We remove such noise using three Laplacian smoothing iterations (Fig. 2 right). Weights were used as follows:

where $V_i$ are all direct neighbors of $v_i$. This is done for all nodes in the graph.

Table 1 shows the time complexity of all steps of our method. For creating the ${ℝ}^n$ embedding via PMDS (Sec. 3.1), both the dimension count $n$ and pivot count $p$ are constants, yielding linear complexity in the number of nodes $N$. For creating the subgraph $G^{\prime }$ (Sec. 3.2), if our coarsening successfully reaches the target size $S$, the cost reduces to $O(iN)$; the factor $|G^{\prime }|N$ accounts for using the pivot fallback. Moreover, when using coarsening, since $G^k$ is reduced by at least a factor of 5% at each coarsening step, $i$ is upper bounded by ${\sum }_{k=0}^{\mathrm{\infty }}{(0.95)}^k=20$, so the cost term $O(iN)$ is indeed linear in $N$. Generating ground truth by running ts-NET* on $G^{\prime }$ does not depend on the input size $N$. Training also does not depend on $N$ and is linear in the number of training epochs $\lambda$, which is set to a constant value. Inference is linear in $N$. Altogether, the end-to-end time complexity of NNP-NET is linear in its input size $N$. Separately, we note that NNP-NET’s space complexity is also linear in $N$.

We assess the quality of graph drawings using neighborhood preservation, stress, and Shepard diagrams, in line with [30, 47]. Metrics like edge length deviation [29], crossing number [37], and node-edge occlusion [12], though frequently used in GD literature, are not very informative for very large graphs.

Neighborhood preservation measures how well neighborhoods in $G$ are preserved in the drawing $𝐘$ [36]. Let $N_G(v_i,r_G)=\{v_j\in V|d_{ij}\le r_G\}$ be the set of nodes $v_j$ with a graph-theoretic distance $d_{ij}$ of at most $r_G$ from $v_i$; we set $r_G=2$ following [30]. Let $N_Y({𝐩}_i,k_i)$ be the set of nodes whose drawings ${𝐩}_j$ are the $k_i$-nearest-neighbors of ${𝐩}_i$ in the 2D layout space, where $k_i=|N_G(y_i,r_G)|$. Neighborhood preservation

measures how similar $N_G(v_i,r_G)$ and $N_Y({𝐩}_i,k_i)$ are (higher values are better).

Normalized stress measures how well the graph-theoretical distances $d_{ij}$ between all node pairs are preserved by Euclidean distances in the graph drawing by

with lower values indicating better distance preservation. The factor $a$ scales the drawing in order to minimize stress for a fair comparison. Following [23], we compute it using

Table 3 shows neighborhood preservation $\nu$ for all our tested drawings. Results for the largest graph com-LiveJournal are missing as it took too long to evaluate Eqn. 2. Other missing values tell that the respective GD method could not complete on the respective graph due to running out of RAM or took longer than 2 hours to compute. The NNP-NET results are very close to tsNET* for most graphs, with NNP-NET doing worse for e.g. MISKnowledgeMap and k49_norm_10NN but much better for fe_bcsstk32. NNP-NET results are consistently better than PMDS except for com_YouTube. When compared with DRGraph, results are more mixed, with no clear winner. Table 4 shows stress $\sigma$ for all generated drawings. NNP-NET yields very similar values to tsNET* (both versions). Similarly to $\nu$, we do not see a clear winner between NNP-NET and DRGraph. PMDS, SFDP and FM³ yield lower $\sigma$ values than NNP-NET – not surprising since these methods optimize for stress while NNP-NET (like t-SNE) optimizes for neighborhood preservation.

Shepard diagrams refine distance-preservation insights captured by stress. These diagrams are scatterplots that show how distances between point-pairs correlate over two different spaces [5, 17, 47], with graph distance on the x-axis. Figure 3 shows these diagrams for our tested graphs and methods. Scatterplots close to the main diagonal indicate cases where the layout preserves graph distances well, e.g., for dwt_1005 and ship_003, for all methods. Plots falling largely under this diagonal indicate layouts where the layout cannot “unclutter” the graph. We see how this occurs for some of the very large graphs e.g. com-YouTube and com-LiveJournal, unsurprising, given the difficulty to lay out such complex structures. Plots falling above the diagonal indicate layouts where points are placed too far away from each other, or, in other words, too long edges drawn in the layout, see e.g. fe_bccstk32 (ts-NET* approx). Overall, we see that SFDP, ${\mathrm{FM}}^3$, and PMDS preserve distances better than the other methods, which is expected given their design. The remaining methods – which all are based on ts-NET, so favor neighborhood preservation, have quite similar patterns of distance preservation on the smaller graphs (Fig. 3 left column). For the larger graphs, which only DRGraph and NNP-NET can handle, we observe either similar patterns or a tendency for DRGraph to underestimate 2D distances more than NNP-NET, i.e., clutter nodes – see e.g. tx_2010, CoPapers-CiteSeer, and ok_2010. Overall, we conclude that NNP-NET performs at least as well as the other t-SNE based methods with respect to distance preservation.

Table 5 shows the drawings created by all tested methods on all graphs, with edges drawn half-transparent to limit visual clutter. As in Tables 3 and 4, missing entries indicate methods that fail due to memory constraints or took too long to complete. We see that exact tsNET* cannot handle graphs larger than fe_4elt2 (11143 nodes) due to its high runtime cost. Approximate ts-NET* scales a bit better given its faster Barnes-Hut t-SNE implementation but hits a limit beyond ship_003 (121728 nodes). NNP-NET can handle all graphs. For the smaller graphs, NNP-NET yields drawings that are visually very similar to the ground-truth ones from approximate tsNET*. Interestingly, for fe_bcsstk32 and ship_003, approximate tsNET* shows unexpected behavior where all nodes snap to a grid structure. NNP-NET does not copy this behavior but yields more plausible drawings. For larger graphs (bcsstk36 and larger), NNP-NET creates different drawings from the other tested methods that can handle such dataset sizes, i.e., SFDP, ${\mathrm{FM}}^3$, PMDS, and DRGraph. NNP-NET spreads the drawing better over the 2D space. We argue that this is desirable as it allows one to better disentangle the depicted structures.

NNP-NET uses the edge weights of the graph if they are provided. To show their effect, we ran NNP-NET on a set of weighted graphs with and without using the weights (Fig. 4). We see that weights affect indeed the obtained drawings (as they should), most visibly for ok2010 and tx2010, where the unweighted drawings show more clutter and the weighted ones a more structured, network-of-corridors-like, one. Table 6 shows that both stress and neighborhood preservation improved when including weights.

Table 7 shows the execution times for all methods tested with missing values as already explained. NNP-NET takes significantly longer on smaller graphs due to the dominating high constant cost of computing the ground truth. For larger graphs, NNP-NET is slower than PMDS, but yields better quality (see Tabs. 4 and 3). Compared to DRGraph, we see a pattern reversal, with NNP-NET becoming faster for Flan_1565 and com-LiveJournal. To better examine scalability, Fig. 5 shows the time each step of NNP-NET takes vs the node count $N$ (both axes use a logarithmic scale). The following trends are visible:

Embedding creation

is roughly linear with $N$. The spiking outliers in the plot correspond to weighted graphs which require Dijkstra’s algorithm instead of the much faster Breadth-First Search (BFS) to compute shortest paths.

Subgraph creation

follows the same linear trend in $N$. The three outliers indicate graphs where our coarsening method could not reach the desired node count $S={10}^4$ and had to use the much slower pivot method (Sec. 3.2).

Ground truth creation

is roughly constant for $N>{10}^4$ nodes, a value matching $S$.

Training and inference

are roughly linear up to about ${10}^4$ nodes, mainly due to the training cost. After this point, training time becomes constant. The low curve slope for larger $N$ values tells that inference costs relatively very little and scales very well with $N$.

We further compare NNP-NET’s scalability with DRGraph, its strongest competitor vs ability to handle very large graphs with good quality values. For this, we took the following steps. (1) We ran NNP-NET using BFS for the weighted graphs when calculating graph distances, i.e., ignoring weights – a fair comparison since DRGraph does not use weights. (2) When using the slow pivot method for subgraph creation, we accounted a time of 1 second, equal to the largest cost for all cases where this slow fallback was not needed. This is to simulate a situation where the fallback is not needed.

Figure 6 compares the cost of DRGraph (blue) with NNP-NET ran normally (orange) and with the theoretical cost of NNP-NET where we would not need the slow pivot method (steps 1 and 2 above; green). DRGraph shows a linear time complexity. In contrast, NNP-NET starts with a much higher execution time. For over roughly $N={10}^4$ nodes, its cost appears almost constant (green curve) if we eliminate the effects due to (1) and (2). Actual timings show the same trend, albeit with a bit more noise (orange curve). As Tab. 7 also showed, we see how NNP-NET overtakes DRGraph at about $N={10}^6$ nodes. Given NNP-NET’s and DRGraph’s appearent trend, NNP-NET will likely stay faster compared to DRGraph for larger graphs.