Cross-Entropy Directed Embedding of Network Data

Takeshi Yamada
yamada@cslab.kecl.ntt.co.jp
Kazumi Saito
saito@cslab.kecl.ntt.co.jp
Naonori Ueda
ueda@cslab.kecl.ntt.co.jp
NTT Communication Science Laboratories, 2-4 Hikaridai Seika-cho Soraku-gun Kyoto, 619-0237 JAPAN

Abstract
We present a novel approach to embedding
data represented by a network into a lowdimensional Euclidean space. Unlike existing methods, the proposed method attempts
to minimize an energy function based on
the cross-entropy between desirable and embedded node configurations without directly
utilizing pairwise distances between nodes.
We also propose a natural criterion to effectively evaluate an embedded network layout in terms of how well node connectivities are preserved. Experimental results
show that the proposed method provides better layouts than those produced by some of
the well-known embedding methods in termsof the proposed criterion. We believe that
our method produces a natural embeddingof a large-scale network suitable for analyzing by manual browsing in a two- or threedimensional Euclidean space.

1. Introduction
In many scientific and engineering domains, complicated relational data structures are frequently represented by networks or, equivalently, graphs. For example, WWW (World Wide Web) sites are often represented by hyperlink networks, with pages as nodes andhyperlinks between pages as edges, the interactions
between genes, proteins, metabolites and other small
molecules in an organism are represented by gene regulatory networks, and the relationships between people and other social entities are characterized by social
networks. This is because network representations often provide important insights for researchers to understand the intrinsic data structure with the helpof some mathematical tools such as graph theory, as
well as by examining an embedded layout in a lowdimensional Euclidean space.

However, when the size of the network grows large andcomplicated, it becomes extremely difficult to obtainrelevant embedding of networks. Therefore, developing a network embedding algorithm that encourages
researchers to make scientific discoveries about underlying knowledge or principles from network data is aquite challenging and important task in the field ofmachine learning.
One of the most fundamental methods to study a network and intuitively understand its inherent structures
is browsing over a network layout embedded in a lowdimensional Euclidean space; to examine nodes manually one by one by following their connections and bycomparing their connectivities with other nodes. Our
goal is to develop an algorithm that embeds a network
into a low-dimensional Euclidean space in a mannerthat is suitable for browsing.
It is difficult to evaluate whether a given network layout is suitable for browsing or not. Aesthetically pleasing measures have been used in the literature, but they
depend on subjective concepts. In this paper, we startfrom the following simple and basic principle:
Principle A: connectivity preserving principle
Each node attempts to place its adjacent (i.e.,
directly connected) nodes relatively more closelythan non-adjacent ones.
We propose an algorithm that fulfills this principle byonly using connectivity information between nodes asa direct criterion, based on the cross-entropy directedenergy function for minimizing. On the other hand, alarge body of exiting work assumes pairwise distances
between nodes. For example, the spring method proposed by Kamada and Kawai (1989) (hereafter referred to as the KK spring method) first calculates
graph-theoretic distances for each pair of nodes. The
graph-theoretic distance can be calculated using theshortest path algorithm on a graph, such as the Floyd’s
algorithm (Floyd, 1962). It then embeds nodes into

Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

the low-dimensional Euclidean space such that thesegraph-theoretic distances are most preserved. In otherwords, the KK spring method attempts to fulfill thefollowing principle:
Principle B: distance preserving principle
Each pair of nodes attempts to place each othersuch that their Euclidean distance restores theirgraph-theoretic distance.
It is clear that the complete fulfillment of principle B
implies principle A, however the converse is not true.
We will show that an attempt to fulfill the stronger
principle B may often fail and end up with a biased
embedding that also fails to fulfill principle A, and is
not suitable for browsing, especially when the network
size is large.
When browsing a large and complex network, we often
want to focus our attention on some restricted portion of the network by removing nodes and connections that are out of our focus, and by re-optimizingthat portion at full scale for more detailed browsing.
When this re-optimization does not change the basic
structure of the layout drastically, we describe that theebmedding algorithm has good clipping stability.
Removing a certain amount of nodes may change thegraph-theoretic distances between the remaining nodes
drastically, and therefore, completely change the embedding results produced by the KK spring methodthat is based on principle B. We will see that the proposed approach performs quite well in this sense.

2. Cross-Entropy Approach
2.1. Objective Function
Consider a network (graph) with N nodes (vertices),
where its adjacency matrix is denoted by A = (ai,j ).
In this paper, we focus on undirected graphs, i.e.,ai,j ∈ {0, 1}, ai,i = 1, and ai,j = aj,i , but our approach
can be easily extended to directed ones. For a given
network, our objective is to compute a K-dimensional
embedding of the N nodes such that principle A statedin Section 1 is fulfilled in terms of the K-dimensional
Euclidean norm.
Let x1 , x2 , · · · , xN be the positions of the N nodes in a
K dimensional space. As usual, the Euclidean distance
between xi and xj is defined as follows:
di,j = kxi − xj k2 =KX(xi,k − xj,k )2 .

(1)and ρ(∞) = 0. Here ρ(di,j ) can be regarded as a continuous similarity function between xi and xj . The
basic idea is to consider a modified version of principle
A using the concept of similarity; each node attempts
to place other nodes such that the similarities between
the node and its adjacent nodes are higher than thosebetween the node and its non-adjacent nodes. Thisagain can be reformulated in a slightly relaxed form interms of ai,j and ρ(di,j ); each node attempts to place
other nodes such that the continuous similarity function ρ(di,j ) becomes the closest approximation of thediscrete similarity measure ai,j as possible.
To approximate ai,j by ρ(di,j ), a cross-entropy function between ai,j and ρ(di,j ) is introduced as follows:
Ei,j = −ai,j ln ρ(di,j ) − (1 − ai,j ) ln(1 − ρ(di,j )). (2)Equation (2) attains its minimum when ρ(di,j ) = ai,jwith respect to xi and xj ; i.e., when the discrete similarity measure and the continuous measure become
identical. Keeping the symmetric nature of Ei,j in
mind, we consider the following total energy function
to be minimized with respect to x1 , · · · , xN :E=

NX

Ei,j .

(3)

i=1 j=i+1

When node i is fixed, ai,j can be viewed as a binaryclass label of node j; i.e., if ai,j = 1, then node j haslabel 1, and, because ai,i = 1, this means that node jbelongs to the same class with node i. Otherwise, if
ai,j = 0, then node j has label 0 and belongs to a different class from node i. The problem can be viewed asa set of N binary classification tasks, and Equation (3)as a standard cost function of classification problems
with parameters x1 , · · · , xN . Namely, the main characteristic of our approach is to solve the embedding
problem the same way we would train a classification
function.
In this paper, we use ρ(u) = exp(−u/2) as the similarity function. Note that our approach is not limited
to this particular type of ρ(u). The energy function
corresponding to Equation (2) can be reformulated asfollows:
Ei,j= ai,j 21 kxi − xj k2−(1−ai,j ) ln(1−exp(− 21 kxi − xj k2 )).

(4)

Finally, we define the following objective function witha regularization (weight-decay) term that controls thesize of the resultant embeddings:

k=1

We now introduce a monotonic decreasing function
ρ(u) ∈ [0, 1] with respect to u ≥ 0, where ρ(0) = 1

N
−1
X

J=

N
−1
X

N
X

i=1 j=i+1

N

Ei,j +µX
kxi k2 ,
2 i=1

(5)

N × N adjacency matrix A = (ai,j ), embedding dimensionality K, and the convergence precision  aregiven as inputs.
1. Set t = 1, and initialize points x1 , · · · , xN randomly.
(1)(1)
2. Calculate gradient vectors Jx1 , · · · , JxN .
(t)
3. Select xi such that i = arg maxj {kJxj k2 }.
(t)

4. If kJxi k2 < , output x1 , · · · , xN and terminate.
5. Calculate modification vector ∆xi .
(t+1)
(t+1)
6. Update gradient vectors Jx1 , · · · , JxN from(t)(t)
Jx1 , · · · , JxN .
7. Update xi by xi = xi + ∆xi .
8. Set t = t + 1 and go to Step 3.
Figure 1. CE Learning Algorithm for Network Embedding

where µ is a predetermined constant. Hereafter,
our method is referred to as the CE (Cross-Entropy)
method.
2.2. Learning Algorithm
The basic structure of our CE learning algorithm inherits the fundamental idea of the KK spring algorithm. More specifically, instead of all the N points being moved simultaneously, a point xi having the maximum gradient vector norm is selected and is moved
using the Newton-Raphson method, while the otherpoints are fixed. This learning scheme, together withthe objective function, can be interpreted as on-line
learning of a classification problem using cross-entropy
with a weight-decay term, which is well-known in thefield of artificial neural networks.
The CE algorithm can be summarized as shown in Figure 1. Here, Jxi is the gradient vector of the objectivefunction J with respect to xi calculated as follows:Jxi =X ∂Ei,j∂J=+ µxi ,
∂xi
∂xi

(6)

j6=i

where the derivative of Ei,j isai,j − exp(− 21 kxi − xj k2 )∂Ei,j(xi − xj ).
=∂xi
1 − exp(− 12 kxi − xj k2 )(7)

Step 2 initially calculates the gradient vectors for all
points by using Equation (6). Assuming that dimensionality K is much smaller than N , the computational
complexity for this calculation is O(N 2 ). However,when updating the gradient vectors in Step 6, only
the gradient vector for the selected point xi must be
calculated from scratch, and those for the other points

can be efficiently updated by only calculating the differences as follows:
(t+1)

Jxj

∂E

(t)

(t+1)

∂Ei,j
∂xj
(t)
(t+1)
∂Ei,j
∂Ei,j
(t)
Jxj + ∂xi − ∂xi .
(t)= Jxj − ∂xi,j
+
j
=

(8)

This is because of the following equalities:
(t)

(t+1)

(t)

∂Ej,h
∂Ei,j
∂Ej,i
=−
and
∂xj
∂xi
∂xj

(t)

=

∂Ej,h
∂xj

,

(9)

where h denotes an index such that h 6= i, j. Thus,
Step 6 can be performed in O(N ).
In Step 5, according to the Newton-Raphson method,∆xi is calculated using the Hessian matrix H as follows:∆xi = −H−1 Jx(t),iwhere H =∂ 2 J (t).
∂xi ∂x0i(10)Here, x0 denotes a transposed vector of x. The KK
spring method also uses Equation 10. However, because the Hessian matrix H is not always positive definite, either in the KK spring method whose energyfunction is described later in Equation 16 or in the CE
method, we cannot guarantee that J (t+1) < J (t) for
all t. Therefore, in the CE method, if J increases after
Equation 10 is applied, we undo it and instead resort
to Equation 11 as follows:∆xi = λJx(t)
,
i

(11)

where the step-length λ is chosen so that J (t+1) < J (t) .
(t)Note that since Jxi is the gradient direction, J always
decreases as long as a sufficiently small λ is chosen andthus, the algorithm is guaranteed to converge. J canbe updated in O(N ) by only calculating the differences
as follows:
P
(t+1)
(t)
J (t+1) −J (t) = j6=i (Ei,j −Ei,j )(12)+ µ2 {kxi +∆xi k2 −kxi k2 }.
In our experiments, the regularization term added in
Equation 10 is observed to encourage H being positive
definite as much as possible, and resorting to Equation 11 happens only occasionally. In such cases, each
iteration of the above algorithm can be performed inapproximately O(N ).

3. Evaluations by Experiments
3.1. Embedding Methods
In our experiments, we compared our method withthree representative conventional methods: the classical Multidimensional Scaling (MDS) developed by

Torgerson (1958), the spectral clustering method (Nget al., 2002), and the KK spring method. In the following, we briefly review each method.
Let G = (gi,j ) be a pairwise graph-theoretic distancematrix, and O = (oi,j ) be a matrix defined by oi,j =2gi,j. Let X = [x1 , · · · xN ]0 be the N × K matrix ofcoordinates in a K dimensional Euclidean space. The
classical MDS has the following objective function to
be minimized:
1
JCMDS = trace{(− YOY − XX0 )2 }.
2Here, Y denotes the N -dimensional
Householder transformation matrix.

(13)
Young-Let B = (bi,j ) be an affinity matrix defined by bi,j =exp(−gi,j /2) if i 6= j and bi,i = 0. The spectral clustering method has the following objective function to
be minimized:
JSC = trace{(D−1/2 BD−1/2 − XX0 )2 }.

(14)

Here, D denotes a diagonal matrix whose (i, i)-element
is the sum of the i-th row of B. In this method, thefinal embedded points are obtained by re-normalizing
each row of X to have unit length, i.e.,xi,jxbi,j = qP
N

.

(15)

j=1 xi,j

The KK spring method has the following objectivefunction to be minimized:
JKK =N −1 N
1 X X (gi,j − kxi − xj k)2.
2
2 i=1 j=i+1
gi,jTable 1. Summary statistics of networks.
Name

3.2. Experimental Data
Three different types of networks assembled from real
data are used to evaluate the proposed method. The
first network data, denoted as E.Coli, is biology originated. E.Coli is the gene regulatory network of thebacterium Escherichia Coli as described by Shen-Orr
et al. (2002). The second data, denoted as NIPS,
is human relation data generated by assembling a coauthorship relations in the conference papers appearedin NIPS (Neural Information Processing Systems) volumes 1 to 12, obtained from the web site of Roweis(2002), in which two persons who have at least one
joint paper are directly linked. The third data, denoted as NTT, is a WWW hyperlink network. NTT
is generated by collecting all WWW pages that are located in NTT (Nippon Telegraph and Telephone Corporation) domain and have “www.ntt.co.jp” in common in their URL (Universal Resource Locator).

L

L̄

L◦

Ḡ

G◦

C

N2

E.Coli 328 456 2.78 72 4.83 13 29 12
NIPS 1061 2080 3.92 45 7.23 17 235 37
NTT 3870 9337 4.83 279 6.41 17 76 54

In our experiments, we first transform these networks
into undirected ones, extract the maximally connectedcomponents, and then apply embedding methods tothem. If we need to embed the whole network, thenwe can treat each connected component separately.
Table 1 shows the statistics of the extracted connected
networks. In the table, N denotes the number ofnodes, and L, L̄ and L◦ denote total, average andmaximum number of links respectively. Let Li be thenumber of links connected with i. They are then calculated as follows:
N
N
1X
1X
L=
Li , L̄=
Li and L◦ = max{Li }. (17)
i
2 i=1
N i=1

Ḡ and G◦ denote the average and maximum value of
pairwise graph-theoretic distances in each graph respectively. Let gi,j be the graph-theoretic distances
between nodes i and j. They are then calculated asfollows:
Ḡ=

(16)

N

N
−1 X
N
X
2
gi,j and G◦ = max{gi,j }. (18)i,jN (N −1) i=1 j=i+1

Here, we emphasize that these networks are all sparsein terms of the adjacency matrices, but have different
statistics to some degree. C denotes total number ofconnected components in the original networks andN2 denotes the number of nodes in the second largest
component, which is much smaller than N .
3.3. Evaluation Measure
In Section 1, we claimed that network embedding
should fulfill principle A and proposed an embedding
algorithm based on cross-entropy and local connectivities in Section 2. In this section, we attempt to evaluate the embedded results in a strictly quantitative
fashion.
Assume we have an embedding of a network with N
nodes, with x1 , x2 , · · · , xN as their corresponding embedded positions in a K-dimensional space. Consider aK-dimensional ball Bi (ri ) with its center xi and radius
ri . From principle A, it is expected that in an idealembedding, each node i can maintain Bi (ri ) with anappropriately chosen radius ri such that it includes all
the points corresponding to the adjacent nodes (i.e.,
nodes directly connected with i) and excludes all the
non-adjacent ones. In reality, however, especially when
K is small, there may not exist such ri for each i. However, it may be still possible to find an optimal ri interms of some relevant criterion.
In a sparse network, where there are many more nonadjacent nodes than adjacent ones, the standard accuracy measure that counts the number of correctly
included points and correctly excluded points is not
appropriate to determine the optimal radius. This isbecause high accuracy can be achieved even if it excludes all the points regardless of their connectivities.
Instead, we adopt the idea of the F-measure that is
widely used in the field of information retrieval.
The F-measure is defined as the weighted harmonic
average of precision and recall. Let #X be the numberof elements in set X. The precision Pi (ri ) for the ith ball Bi (ri ) corresponding to xi and ri is defined asfollows:
Pi (ri ) =#{j|xj ∈ Bi (ri ), ai,j = 1, j 6= i},#{j|xj ∈ Bi (ri ), j 6= i}(19)while the recall Ri (ri ) is defined as:
Ri (ri ) =#{j|xj ∈ Bi (ri ), ai,j = 1, j 6= i}.
#{j|aij = 1, j 6= i}(20)

Roughly speaking, high precision favors a small ri andhigh recall favors a large ri ; the optimal ri should befound in between. We choose the optimal radius rbi foreach i that maximizes the following F-measure withweight α. (α = 1/2 is used throughout our experiments.)1
1+ (1 − α)Fi (ri ) = 1/ α.
(21)
Pi (ri )Ri (ri )The proposed measure, denoted as the connectivity Fmeasure, to evaluate an embedded network layout isdefined as the average over all N points as follows:
F =

N
X
Fi (b
ri )
i=1

N

.

(22)

It may be arguable to straightforwardly apply ourcriterion to the embeddings produced by the othermethods based on principle B, because their objectivefunctions do not directly incorporate this F -measure.
However, the complete fulfillment of principle B implies principle A. In fact, when principle B is fulfilled,

F = 1 is achieved by setting the optimal radius rbi = 1
for each i. Therefore, our criterion can be thought ofas a reasonable measure for evaluating any embedding
method.
3.4. Comparisons Using the Connectivity
F -measure
We applied our method together with the three conventional methods, the classical MDS, the KK spring
method, and the spectral clustering method, to thethree different kinds of networks mentioned above, andobtained embedding results in K-dimensional spaces.
We then quantitatively evaluated these results according to the proposed connectivity F-measure. In theexperiments, we changed K from 2 to 25 for E.Coli
and from 2 to 9 for NIPS and NTT respectively.
Figure 2 summerizes the experimental results. The
axis of ordinates shows the values of the connectivity
F-measure and the axis of abscissas shows the dimensionalities of the embedded space. For the CE andthe KK spring methods, the results of five trials withdifferent random initializations are plotted to see ifthese methods suffer from the local optimality problem. One can see that variances are very small for all
networks, and therefore the local optimality problem
is almost negligible in our experiments. The performances of all methods are monotonically improved as
the dimensionality K, and thus the degree of freedom,
increases.
As expected, the performance of the CE method is better than those of the other methods, especially in thelower dimensions, where embeddings are more difficult. In particular, the experiments using NTT, whichis the largest in size and the most complicated, mostimpressively demonstrate that the CE method significantly outperforms the others. Figure 2 only shows
the F-measure, but more detailed analysis reveals that,in low dimensions, all the methods show high recall
values, more or less 90%, but poor precision values,
except for the CE method.
3.5. Two Dimensional Visualizations
Each of the pictures on the left of Figure 3 shows a twodimensional embedding result obtained by the classical
MDS, the KK spring method, and the CE method forNTT, the WWW network data. The results of thespectral clustering method are not included here because it embeds on the surface of a sphere, as describedin Equation 15.
As discussed earlier, it would be difficult to evaluate
these results in the sense of the aesthetically pleasingconnectivity F-measure1
0.8

connectivity F-measure
1
CE

CE

0.6

0.6
CMDS

0.4

0.8

SC

10

15

E.Coli

20

25
dim.

0

KK

0.4

0.2
5

CE

0.6

CMDS

0.4

SC

0.2
0

KK

0.8
KK

connectivity F-measure
1

SC

0.2
2

3

4

5

6

NIPS

7

8

9

dim.

0

CMDS
2

3

4

5

6

NTT

7

8

9

dim.

Figure 2. Experimental comparisons of the connectivity F-measure between the classical MDS (labeled CMDS), the spectral clustering method (labeled SC), the KK spring method (labeled KK) and the proposed CE method (labeld CE) using
the E.Coli, NIPS and NTT networks.

measure. Nevertheless, some characteristic features ofeach method can be observed below. The result of
the classical MDS shown in Figure 3(a) is problematicfor visualization: many nodes are collapsed to a single
point, which is not desirable for a browsing purpose.
This seems to be a limitation of the linear projection
methods.
In contrast, the result of KK spring method shownin Figure 3(b) and the result of the proposed CE
method shown in Figure 3(c) do not suffer from thenode collapse problem. Looking at Figures 3(b) and3(c) carefully, one can observe that in the former
picture, many nodes tend to be arranged densely insemi-circles, which is characterized as a dandelion effect (Buja et al., in press), while in the latter picture,
nodes are laid more uniformly in a radial manner. The
CE method appears to exploit the space more efficiently than the KK spring method. This agrees with
the quantitative evaluation results using the connectivity F-measure, and also agrees with the fact that
the KK spring method tries to preserve the pairwise
graph-theoretic distances that take only discrete values. Besides, it appears that it is harder for the former
to follow links, especially in a relatively congested area,
than for the latter.
As mentioned earlier, we may want to look into some
portions of the network in detail. For this purpose, thesub network shown in the dotted circle in the left ofeach picture in Figure 3 is clipped out by removing thenodes and connections outside this circle, and is reembedded. Note that each clipped region corresponds
to the same sub network. The re-embedded results
are shown on the right of Figure 3. It can be seenthat the embedded network layouts before and after
the clipping are quite different from each other in thecase of the classical MDS and KK spring methods,
although the layouts in the dotted circles shown on theleft and right of each picture correspond to the same
sub network. In contrast, the CE method is much morestable with the clipping than the classical MDS andthe KK spring method, and thus has better clipping
stability. We believe that the clipping stability is an
important property for browsing nodes and discoveringknowledge from given networks.

4. Related Works and Discussion
Several other embedding methods based on the
eigenvector analysis other than the classical MDS
and the spectral clustering methods exist, including
Isomap (Tenenbaum et al., 2000) and LLE (Roweis& Saul, 2000). These methods assume high dimensional coordinates or at least pairwise distances between nodes. In contrast, our method only assumes
the adjacency matrix. Stochastic embedding, recently
proposed by Hinton and Roweis (in press), also assumes pairwise distances.
Eades (1984) first proposed a spring-directed graphembedding algorithm. In his algorithm, each pair ofadjacent nodes is linked by a spring of length one, andeach non-adjacent pair by a spring of infinite length.
He claims that the linear spring that obeys Hooke’s
law is too strong and that a logarithmic version should
be used. Eades’ algorithm was the basis for the subsequent spring methods. The KK spring method has
extended Eades’ idea and proposed an algorithm inwhich each pair of nodes is linked by a spring of length
equal to the graph-theoretic distance between those
nodes. This method is much more popular than its
ancestor and is widely refered to as the spring method.

The well-known state-of-the-art graph drawing program called “NEATO” in the graph-viz software package (North, 1992) includes an almost literal implementation of the KK spring method.

believe that the cross-entropy approach is suitable forpreserving the principle. However, we need to perform
further experiments to confirm this claim.

Many of the existing algorithms, including the classical MDS and KK spring methods utilize the pairwise
distances between nodes. Because the distance matrix
is not sparse (even if the network is sparse), they needto deal with a huge non-sparse matrix, especially for alarge network. In such cases, it is possible to modify
the matrix sparse by thresholding large distances toinfinity (or, equivalently, small affinities to zero), but
still necessary to find an appropriate threshold. Our
CE approach only deals with the sparse adjacency matrix when the network is sparse, and needs no such
thresholding.

References

5. Directions for Future Research
Although we have been encouraged by our results todate, there remain a number of directions in which
we must extend our approach before it can become auseful tool for scientific discovery. One promising direction might be to combine our method with existing
discovery systems such as the IPM (Inductive Process
Modeler) proposed by Langley et al. (2002). For instance, we can regard a process model as relationaldata, with processes as nodes and shared variables between them as links. Our method can be directly incorporated as an interface to support the browsing oflarge scale process models obtained by the IPM using
empirically observed data.
The WWW is a complex system that changes overtime. It would be more difficult than any other dynamic system, but still highly expected, to understandits inherent structures in scientific terms and to reveal regularities in its complicated behavior. Thus,
another direction would be to develop a discovery system for the WWW. To this end, we need to extend
our method by incorporating a number of importantcharacteristics of the Web networks, such as network
motifs (Shen-Orr et al., 2002). As the first step, weare planing to evaluate our method by using a wider
variety of the Web networks.
In this paper, we have newly proposed the connectivity F-measure based on the connectivity preserving
principle. However, it seems quite difficult to develop
an algorithm for obtaining results by direct optimization on this measure due to its non-smoothness. On
the other hand, our method based on the cross-entropy
energy function works reasonably well on this measure,as shown in our experiments. From these results, weBuja, A., Swayne, D. F., Littman, M., Dean, N., &Hofmann, H. (in press). Xgvis: Interactive data visualization with multidimensional scaling. Journalof Computational and Graphical Statistics.
Eades, P. (1984). A heuristic for graph drawing. Congressus Numerantium, 42, 149–160.
Floyd, R. W. (1962). Algorithm 97: shortest path.
Communications of the ACM, 5, 345.
Hinton, G., & Roweis, S. T. (in press). Stochastic
neighbor embedding. Advances in Neural Information Processing Systems 15. Cambridge, MA.: MIT
Press.
Kamada, T., & Kawai, S. (1989). An algorithm fordrawing general undirected graph. Information Processing Letters, 32, 7–15.
Langley, P., Sanchez, J., Todorovski, L., & Dzeroski,
S. (2002). Inducing process models from continuous
data. Proceedings of the Nineteenth International
Conference on Machine Learning (pp. 347–354). San
Francisco: Morgan Kaufmann.
Ng, A., Jordan, M., & Weiss, Y. (2002). On spectralclustering: Analysis and an algorithm. Advances in
Neural Information Processing Systems 14. Cambridge, MA.: MIT Press.
North, S. C. (1992). NEATO user’s guide. AT&A Bell
Laboratories.
Roweis, S. T. (2002).
Data for MATLAB
hackers:
NIPS conference papers Vols 0–12.
http://www.cs.toronto.edu/˜roweis/data.html.
Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding.
Science, 290, 2323–2326.
Shen-Orr, S. S., Milo, R., Mangan, S., & Alon, U.
(2002). Network motifs in the transcriptional regulation network of escherichia coli. Nature Genetics,
31(1), 64–68.
Tenenbaum, J. B., de Silva, V., & Langford, J. C.
(2000). global geometric framework for nonlinear
dimensionality reduction. Science, 290, 2319–2323.
Torgerson, W. S. (1958). Theory and methods of scaling. New York: Wiley.

(a) CMDS(b) KK(c) CE

Figure 3. 2-dimensional layouts of the NTT Web network data produced by the classical MDS (a), the KK spring method(b) and our CE method (c). Each picture on the left shows the whole network and the sub network in the dotted circle
is re-embedded and shown on the right.