\documentclass{article}
\usepackage{graphicx,bm}
%\usepackage{graphicx,psfrag,fleqn,txfonts,listings}
%\newcommand{\vct}[1]{{\mathbf #1}}
\newcommand{\vct}[1]{{\bm #1}}
\newcommand{\mat}[1]{{\mathbf #1}}
%\newcommand{\vct}[1]{\mbox{\rm\boldmath $#1$}}
%\newcommand{\vct}[1]{\mbox{$\rm\bf #1$}}
%\newcommand{\vct}[1]{{\itshape\bfseries #1}}
%\newcommand{\mat}[1]{\mbox{\boldmath $#1$}}}
\newcommand{\diff}[2]{\frac{{\rm d}#1}{{\rm d}#2}}
\newcommand{\difft}[2]{\frac{{\rm d^2}#1}{{\rm d}#2^2}}
%
%\setlength{\topmargin}{-5mm}
%\setlength{\textwidth}{160mm}
%\setlength{\textheight}{240mm}
%\setlength{\oddsidemargin}{0mm}
%\setlength{\evensidemargin}{0mm}
%

\author{Tim McGraw}
\title{Progress on STEP Visualization\\ NETL / WVU NARA project}
\date{September 2008}
\begin{document}
%
\noindent
\maketitle
\section{Introduction}
We are currently developing techniques for visualizing collections of STEP files. Here we will describe the methods used and present preliminary results. Our preliminary results use small synthetic
graphs as input to the system. In these examples the nodes may represent STEP files, and the edges represent references between them, just as the assembly of a large structure may reference
smaller subassemblies. At another scale the graph may represent the structure within a single step file.
It is important to note that the nodes and edges we visualize are not necessarily the vertices and edges of the 2D/3D geometry contained in a STEP file. We are developing large graph visualization methods as an approach to solving the problem of visualizing STEP data and the relationships among datasets in a repository.

The traditional approach to displaying graphs is to render a small symbol (a circle, or sphere) for each node, and then draw the edges in the graph as curves between the nodes. Such a visualization becomes unsatisfactory for moderately sized graphs. The overlapping edges leads to visual clutter which can obfuscate the relations between nodes. We illustrate part of our approach with an example.
Consider the two graphs in Figure \ref{fig:graphs}. Are they equivalent? (The graphs are equivalent if there is a one-to-one mapping between the nodes in one graph and the nodes in the other graph such that the mapping preserves edge connectivity). Even for this small example it is not trivial to determine the equivalence visually.
    \begin{figure}[htbp]
    \begin{center}
      \includegraphics[keepaspectratio,width=50mm]{img/graphs2.eps}
    \end{center}
    \caption{Two graphs. Are they the same? It is difficult to determine visually.}
    \label{fig:graphs}
\end{figure}
Now consider the two shapes in Figure \ref{fig:torii}. Are they equivalent? In this case they are equivalent, and it is fairly easy to come to this conclusion by visual inspection. The intuitive and visual notion of shape is invariant to many transformations. For instance, one can easily identify a cube, regardless of position, orientation and size.
    \begin{figure}[htbp]
    \begin{center}
      \includegraphics[keepaspectratio,width=50mm]{img/torii2.eps}
    \end{center}
    \caption{Two shapes. Are they the same? It is easy to determine visually.}
    \label{fig:torii}
    \end{figure}
 There is another important connection between the graph in Figure \ref{fig:graphs} and the shape in Figure \ref{fig:torii}. The given graph is not embeddable in the plane - there is no set of node positions in the plane such that no two graph edges overlap.
The given graph is, however, embeddable on the torus as shown in Figures \ref{fig:torus1} and \ref{fig:torus2}. Our visualization approach is to map graph structure to geometric shape and other visual properties which are easily discernable. We consider the torus in this case to be a visual representation of the graph. In addition, we would also like to support the option of seeing the nodes and edges embedded on the surface. The physically-based method for achieving this is described in section \ref{sect:graph}.

The graph in Figure \ref{fig:graphs} is known as $K_5$, the completely connected graph of 5 nodes. It can be proven that every graph which is not embeddable in the plane has $K_5$ or $B_{3,3}$ (the complete bipartite graph with 3 nodes in each partition) as a subgraph. Furthermore, by removing the $K_5$ and $B_{3-3}$ subgraphs from a nonplanar graph we can obtain a graph which is embeddable in the plane.

The approach we will take for visualizing global graph structure is to represent the graph as a surface which that graph is embeddable on. In general, a graph may have multiple $K_5$ and $B_{3,3}$ subgraphs, so we may need a high genus surface on which to embed the graph. The genus of this surface can be determined by graph segmentation since the number of $K_5$ and $B_{3,3}$ subgraphs determine the genus of the visualization surface.

The embedding surface shape alone is not the sole method of visualizing a graph. However, this surface acts as a canvas for visualizing other properties of the graph. We propose a hierarchical mapping from graph structure to visual appearance for further visualization which is summarized in Figure \ref{fig:hierarchy}.
    \begin{figure}[htbp]
    \begin{center}
      \includegraphics[keepaspectratio,width=60mm]{img/hierarchy.eps}
    \end{center}
    \caption{A hierarchy of graph properties and visual properties.}
    \label{fig:hierarchy}
    \end{figure}
We also propose to take a multiscale approach to visualization. Using clustering approaches we can collapse highly connected groups of nodes at one scale to a single node at the next higher scale.
A spectral clustering approach is described in section \ref{sect:clusterering} which will allow us to deal with a moderate number of nodes at each scale during visualization will and require render embedding surfaces of moderate
genus. Strictly speaking, the full graph is then visualized as a sequence of surfaces with increasing scale.

\section{Methods}

\subsection{Graph Drawing Algorithm}\label{sect:graph}
%
Given an arbitrary graph and a manifold, consider embedding the graph on the manifold.
In order to make the graph visually comprehensible we wish to embed all the vertices and edges of the graph on the manifold so that there are no overlapping edges.
Our approach is to convert the given graph into a mass-spring system \cite{particle}.
In order to constrain the motion of the vertices within the manifold we utilize constrained dynamics \cite{constrained}. At the same time, we apply repulsive electric forces and damping forces among all the vertices so that they maintain a certain distance from each other.
We initialize the positions of the particles randomly or manually and simulate the motion of the particles until those positions converge to their steady state.
%
\subsubsection{Mass-spring System Representation of Graph}
Consider a graph $G = (V,E)$ where $V$ is a set of $N$ vertices $\{v_1, v_2, \ldots , v_N\}$ and $E$ is a set of $M$ edges $\{e_1, e_2, \ldots , e_M\}$.
Each edge is given by a pair of vertices $(v_i, v_j), \, i, j = 1,\ldots,N$.

We construct a particle system that corresponds to $G$ as follows:
\begin{itemize}
\item For each vertex, assign a particle.
\item For each edge, subdivide the edge into multiple segments and assign a spring to each segment and a particle to each joint between the setments. Let the total number of the particles that are assigned to the joints be $L$.
\end{itemize}

Thus in total we have $K = N+L$ particles in the particle system.
Let the total number of the springs be $K_s$.
The motion of this particle system is governed by Newton's second law of motion
%
\begin{equation}
  \mat{M} \ddot{\vct{q}} = \vct{Q} + \hat{\vct{Q}}
  \label{eq:eqmotion}
\end{equation}
%
where $\vct{q}$ is the vector of the position of particles defined as
%
\[
 \vct{q} = [x_1, y_1, z_1, x_2, y_2, z_2, \ldots, x_K, y_K, z_K]^T,
\]
%
$\mat{M} = \mathrm{diag}(m_1, m_1, m_1, m_2, m_2, m_2, \ldots , m_K, m_K, m_K)$ is the mass matrix, $\vct{Q}$ is the external force, and $\hat{\vct{Q}}$ is the constraint force.

The external force $\vct{Q}$ is a sum of the repulsive electric forces $\vct{F}^{(e)}$, spring forces $\vct{F}^{(s)}$, and damping forces $\vct{F}^{(d)}$ given by
\begin{equation}
  \vct{Q} = \vct{F}^{(e)} + \vct{F}^{(s)} + \vct{F}^{(d)}.
  \label{eq:forces}
\end{equation}
%
Each term in the right hand side of Equation (\ref{eq:forces}) are comprised of the combination of the following components.
The repulsive electric force between the particle $p_i$ and $p_j$ follows Coulomb's law given by
\[
  \vct{f}^{(e)}_{ij}
  =
  k_e \frac{q_i q_j}{||\vct{r}_{ij}||^2}
  \frac{\vct{r}_{ij}}{||\vct{r}_{ij}||}
\]
where $k_e$ is a coefficient that determines the strength of the force, $q_i$ is the charge of the particle $p_i$, and $\vct{r}_{ij} = \vct{r_i} - \vct{r_j}$ where $\vct{r}_i$ is the position vector of the particle $p_i$.
The spring force between the particle $p_i$ and $p_j$ follows Hooke's law given by
\[
  \vct{f}^{(s)}_{ij}
  =
  -k_s (||\vct{r}_{ij}|| - d_{ij})  \frac{\vct{r}_{ij}}{||\vct{r}_{ij}||}
\]
where $k_s$ is the spring constant and $d_{ij}$ is the rest length of the spring.
Finally the damping force for each particle $p_i$ is given by
\[
  \vct{f}^{(d)}_{i} = -k_d \vct{v}_i,
\]
where $\vct{v}_i$ is the velocity of particle $p_i$.

Thus we have computed the external force $\vct{Q}$.
%
%
%The entire graph is graphically represented as a set of particles that obey the equation of motion.
%A particle is assigned for each vertex. We subdivide curvilinear edges into multiple line segments.
%A particle is also assigned to the connecting points of these line segments.
%Springs are inserted at each line segment so that the particles between the line segments are connected. At the same time, we apply repulsive electric forces among all the particles so that the vertices and edges are separated.
%
%
\subsubsection{Constrained Dynamics}
In order to solve Equation (\ref{eq:eqmotion}), we need to know the constraint force $\hat{\vct{Q}}$.
This is the force that constrains the motion of the particles on the given manifold.
The manifold is given as an implicit surface $F(x,y,z) = 0$.
We wish all the particles' motion to be constrained on this surface. Thus, $F(q_{3i},q_{3i+1},q_{3i+2}) = 0, \,  i=1,\ldots,N$. We combine all these constraint equations into a vector equation
  $\vct{C}(\vct{q}) = \vct{0}$.
To calculate $\hat{\vct{Q}}$ we utilize constrained dynamics \cite{constrained}.
%
%By the chain rule the time derivative of the constraint equation is given by
%\[
% \dot{\vct{C}} = \frac{\partial \vct{C}}{\partial \vct{q}}\dot{\vct{q}} = \mat{J}\dot{\vct{q}}
%\]
%
%\[
%  \ddot{\vct{C}} = \dot{\mat{J}} \dot{\vct{q}} + \mat{J}\ddot{\vct{q}}
%\]
%
Utilizing the formulation described in \cite{constrained} the final equation to be solved can be described as a linear system
\begin{equation}
  \mat{J}\mat{W}\mat{J}^T \vct{\lambda}
  =
  -\dot{\mat{J}}\dot{\vct{q}} - \mat{J}\mat{W}\mat{Q} - k_s\vct{C} - k_d\dot{\vct{C}}
\label{eq:equation}
\end{equation}
%
where $\mat{W} = \mat{M}^{-1}$, $\mat{J} = \frac{\partial \vct{C}}{\partial \vct{q}}$ is the Jacobian, $\vct{\lambda}$ is the Lagrange multiplier, $k_s$ and $k_d$ are feedback parameters for numerical stabilization. The constraint force $\hat{\vct{Q}}$ is
given by
%
\begin{equation}
  \hat{\vct{Q}} = \mat{J}^T \vct{\lambda}.
\label{eq:lambda}
\end{equation}
%
We solve Equation (\ref{eq:equation}) for $\vct{\lambda}$ and then constraint force $\hat{\vct{Q}}$ is obtained by Equation (\ref{eq:lambda}).
%
Now that we know all the terms in the right hand side of Equation (\ref{eq:eqmotion}),
we can solve it for $\vct{q}$.
Eventually the value of $\vct{q}$ will converge to its steady state (due to the damping force) and thus the particles' positions are determined.
%
\subsection{Rendering Manifolds}
Presently, the embedding surface is rendered with a simple shading model. Future work will involve assigning material properties and local perturbations which will represent graph
structural information. We use the marching cubes algorithm \cite{lorensen}\cite{pbourke} for rendering the manifold since it is represented an implicit surface.
%
\subsection{Hyperbolic Geometry}
Hyperbolic geometry creates a fisheye lens effect.
This characteristics is useful to display and navigate large graphs in a limited display area.
There are various methods that implement the hyperbolic geometry \cite{hyperbolic1}\cite{hyperbolic2}\cite{hyperbolic3}.
We used a simple geometric method shown in Figure \ref{fig:hyperbolic1} to examine the effect of the hyperbolic geometry. The transformation is done by the following steps:
\begin{enumerate}
\item The input coordinates $P(p_x, p_y, 0)$ are transformed by
the hyperboloid
\[
  H: \left(\frac{x}{a}\right)^2 + \left(\frac{y}{b}\right)^2 - \left(\frac{z}{c}\right)^2 = -1.
\]
\item Project $P(p_x, p_y, 0)$ onto $H$ and let the projection be $P'(p_x, p_y, p_z)$.
\item Calculate the intersection $Q'(q_x,q_y,c)$ of line $\mathrm{OP'}$ and the plane $z=c$.
\item Project $Q'$ onto $z=0$ and let the projection be $Q(q_x, q_y, 0)$.
\end{enumerate}
In future work this type of mapping will be useful for navigating and visualizing the planar portions of the graph.
\subsection{Spectral Clustering}\label{sect:clustering}
Clustering is an important part of our proposed multiscale visualization technique. It will be used to minimize visual clutter at each scale of the visualization.
Spectral Clustering \cite{spectclust1}\cite{spectclust2}\cite{spectclust3} is a clustering method that has many fundamental advantages compared to traditional clustering methods. One of the advantages is that it can cluster data points that are not necessarily comprised of convex subsets. We apply this method to find distinct clusters in the graph. We examined the unnormalized spectral clustering algorithm that is described in \cite{spectclust1}. The algorithm is as follows:
\begin{itemize}
\item Input: Similarity matrix $S \in \mathbf{R}^{n \times n}$, number $k$ of clusters to construct.
\item Construct a similarity graph. Let $W$ be its weighted adjacency matrix.
\item Compute the unnormalized Laplacian $L$.
\item Compute the first $k$ eigenvectors $u_1,\ldots,u_k$ of $L$.
\item Let $U \in \mathbf{R}^{n \times k}$ be the matrix containing the vectors $u_1,\ldots,u_k$ as columns.
\item For $i=1,\ldots,n$, let $y_i \in \mathbf{R}^{k}$ be the vector corresponding to the $i$-th row of $U$.
\item Cluster the points $(y_i)_{i=1,\ldots,n}$ in $\mathbf{R}^{k}$ with $k$-means algorithm into clusters $C_1,\ldots,C_k$.
\item Output: Clusters $A_1,\ldots,A_k$ with $A_i = \{j | y_j \in C_i \}$.
\end{itemize}
%
%
\section{Preliminary Results}
The methods of the previous sections have been implemented and tested on small synthetic graphs.

\subsection{Graph Embedding on Torus}
We attempted to embed a perfect graph with five nodes ($K_5$) on a torus.
$K_5$ is known to be impossible to embed on a plane and it requires a torus with genus one to be embedded on.
The equation of the torus that we used is given by
\[
  F(x,y,z) = (x^2 + y^2 + z^2 + r_1^2 - r_2^2)^2 - 4r_1^2(x^2 + y^2) = 0
\]
where $r_1$ is the major radius and $r_2$ is the minor radius.
We manually initialized the position of particles and edges as in Figure \ref{fig:torus1}.
Starting with this initial condition the positions of particles evolve until they reach the steady state.
Figure \ref{fig:torus2} shows the final (converged) positions of the particles.
We confirmed that our algorithm creates reasonably smooth graph layouts.
%
\subsection{Hyperbolic Geometry}
We implemented the hyperbolic mapping technique and generated the images of large graphs. An example output is shown in Figure \ref{fig:hyperbolic2}. Note that it creates the fisheye lens effect that emphasizes the detail in the center. Though the detail in the periphery is greatly distorted, some features are still discernable. By allowing the user to change the location of the center of projection it is possible to implement a movable lens feature in the user interface of our proposed software. This will be useful for navigating and visualizing the large planar portions of graphs.
Adopting this method to the nonplanar regions is proposed for future work.
%
\begin{figure}[htbp]
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[keepaspectratio,width=60mm]{img/hyperbolic.eps}
    \end{center}
    \caption{Hyperbolic geometry.}
    \label{fig:hyperbolic1}
  \end{minipage}
  \hfill
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[keepaspectratio,width=50mm]{img/hyperbolic2.eps}
    \end{center}
    \caption{Effect of hyperbolic geometry.}
    \label{fig:hyperbolic2}
  \end{minipage}
\end{figure}
%
%
\begin{figure}[htbp]
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[keepaspectratio,width=50mm]{img/torus1.eps}
    \end{center}
    \caption{Graph on a torus (initialized).}
    \label{fig:torus1}
  \end{minipage}
  \hfill
  \begin{minipage}{0.5\hsize}
    \begin{center}
      \includegraphics[keepaspectratio,width=50mm]{img/torus2.eps}
    \end{center}
    \caption{Graph on a torus (converged).}
    \label{fig:torus2}
  \end{minipage}
\end{figure}
%
\subsection{Spectral Clustering}
We implemented the spectral clustering technique \ref{spectclust1} and examined the performance with synthetic inputs.
We show the results for 50 data points that are expected to be clustered into 3 clusters in Figure \ref{fig:clustinput}.
The similarity graph is constructed by the Gaussian similarity function $s(\vct{x}_i, \vct{x}_j) = \exp(-||\vct{x}_i - \vct{x}_j||^2 / (2 \sigma^2))$ where $\sigma = 1.0$ and $\vct{x}_i$ is the position of data point $i$.
Figure \ref{fig:clustresult} shows that the input data is successfully clustered into the 3 expected clusters.
%
\begin{figure}[htbp]
    \begin{center}
      \includegraphics[keepaspectratio,width=70mm]{img/clustinput.eps}
    \end{center}
    \caption{Input data for spectral clustering.}
    \label{fig:clustinput}
\end{figure}

\begin{figure}[htbp]
    \begin{center}
      \includegraphics[keepaspectratio,width=70mm]{img/clustresult.eps}
    \end{center}
    \caption{Result of spectral clustering.}
    \label{fig:clustresult}
\end{figure}

\section{Conclusion}
We have presented a description of our proposed visualization methods, and described some of the computational machinery needed to implement it. The preliminary results have confirmed that these tools are valid for the visualization of small synthetic graphs. A physically-based graph layout algorithm was described which can be used to draw graphs on embedding surfaces has been developed. In the future this method can be used to draw graph nodes and edges directly, or be used to position the local deformations and material properties which will represent graph properties. Code for performing hyperbolic mapping has been developed which will be used in the user interface implementation. A clustering method
has been implemented and tested. Such a clustering method is important to our multiscale approach to visualization.
Future work towards development and testing the proposed methods on real STEP datasets will involve the following tasks:
\begin{itemize}
  \item STEP parsing and large graph generation.
  \item Multiscale graph decomposition using clustering.
  \item Embedding surface formulation.
  \item Preliminary user interface development.
\end{itemize}


\begin{thebibliography}{9}
\bibitem{particle} Andrew Witkin: Physically Based Modeling: Principles and Practice, Particle System Dynamics, SIGGRAPH '97 course notes.
\bibitem{constrained} Andrew Witkin: Physically Based Modeling: Principles and Practice, Constrained Dynamics, SIGGRAPH '97 course notes.
\bibitem{lorensen} W.E. Lorensen and H.E. Cline: Marching Cubes: a high resolution 3D surface reconstruction algorithm, Computer Graphics, Vol. 21, No. 4, pp. 163-169 (Proc. of SIGGRAPH), 1987.
\bibitem{pbourke} Paul Bourke: Polygonising A Scalar Field, http://local.wasp.uwa.edu.au/\~{}pbourke/geometry/polygonise/
\bibitem{hyperbolic1} John Lamping and Ramana Rao: The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies, Journal of Visual Languages and Computing, vol. 7, no. 1, pp. 33-55, 1995.
\bibitem{hyperbolic2} Tamara Munzner: H3: Laying Out Large Directed Graphs in 3D Hyperbolic Space, Proceedings of the 1997 IEEE Symposium on Information Visualization, pp. 2-10, 1997.
\bibitem{hyperbolic3} Mark Phillips and Charlie Gunn: Visualizing hyperbolic space: unusual uses of 4x4 matrices, SI3D '92: Proceedings of the 1992 Symposium on Interactive 3D graphics, pp. 209-214, 1992.
\bibitem{spectclust1} Ulrike von Luxburg: A Tutorial on Spectral Clustering, Statistics and Computing, vol. 17, issue 4 (December 2007), pp. 395-416, 2007.
\bibitem{spectclust2} Marina Meila and Jianbo Shi: Learning Segmentation with Random Walk, Neural Information Processing Systems, NIPS, 2001.
\bibitem{spectclust3} Jianbo Shi and Jitendra Malik: Normalized Cuts and Image Segmentation,
IEEE Transactions on Pattern Analysis and Machine Intelligence(PAMI), Vol. 22, No. 8, pp. 888-905, 2000.
\end{thebibliography}
%
\end{document}