Eigensolver Methods for Progressive Multidimensional Scaling of Large Data

Brandes, Ulrik and Pich, Christian (2007) Eigensolver Methods for Progressive Multidimensional Scaling of Large Data. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 42-53 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_6).

Full text not available from this repository.

Abstract

We present a novel sampling-based approximation technique for classical multidimensional scaling that yields an extremely fast layout algorithm suitable even for very large graphs. It produces layouts that compare favorably with other methods for drawing large graphs, and it is among the fastest methods available. In addition, our approach allows for progressive computation, i.e. a rough approximation of the layout can be produced even faster, and then be refined until satisfaction.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_6
Classifications:M Methods > M.100 Algebraic
P Styles > P.720 Straight-line
ID Code:760

Repository Staff Only: item control page

References

W. Basalaj. Incremental multidimensional scaling method for database visualization. In Proc. VDA, pages 149-158, 1999.

Y. Bengio, J.-F. Paiement, P. Vincent, O. Delalleau, N. Le Roux, and M. Ouimet. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. In NIPS, pages 307-311, 2004.

I. Borg and P. Groenen. Modern Multidimensional Scaling. Springer, 2005.

A. Buja and D. F. Swayne. Visualization methodology for multidimensional scaling. J. Classification, 19:7-43, 2002.

C. J. C. Burges. Geometric methods for feature extraction and dimensional reduction. Technical report, Microsoft Research, 2004.

M. Chalmers. A linear iteration time layout algorithm for visualizing highdimensional data. In Proc. InfoVis, pages 127-132. IEEE, 1996.

A. Civril, M. Magdon-Ismail, and E. Bocek-Rivele. SDE: Graph drawing using spectral distance embedding. In Proc. Graph Drawing, pages 512-513, 2005.

J. D. Cohen. Drawing graphs to convey proximity. ACM Transactions on Computer-Human Interaction, 4(3):197-229, 1997.

T. Cox and M. Cox. Multidimensional Scaling. CRC/Chapman and Hall, 2001.

V. de Silva and J. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. In Proc. NIPS, pages 721-728, 2003.

C. Faloutsos and K. Lin. FastMap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In Proc. ACM SIGMOD, pages 163-174, 1995.

E.R. Gansner, Y. Koren, and S. North. Graph drawing by stress majorization. In Proc. Graph Drawing, pages 239-250, 2004.

G. H. Golub and C. F. van Loan. Matrix computations. Johns Hopkins University Press, 1996.

S. Hachul and M. Jünger. An experimental comparison of fast algorithms for drawing general large graphs. In Proc. Graph Drawing, pages 235-250, 2005.

D. Harel and Y. Koren. Graph drawing by high-dimensional embedding. In Proc. Graph Drawing, pages 388-393, 2002.

F. Jourdan and G. Melancon. Multiscale hybrid MDS. In Proc. IV, pages 388-393. IEEE, 2004.

Charles Kadushin. Personal communication.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31:7-15, 1989.

Y. Koren. Graph drawing by subspace optimization. In Proc. VisSym, pages 65-74, 2004.

Y. Koren, L. Carmel, and D. Harel. ACE: A fast multiscale eigenvectors computation for drawing huge graphs. In Proc. InfoVis, pages 137-144. IEEE, 2002.

Y. Koren and D. Harel. One-dimensional layout optimization, with applications to graph drawing by axis separation. Computational Geometry: Theory and Applications, 32:115-138, 2005.

J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1-27, 1964.

J. B. Kruskal and R. E. Hart. A geometric interpretation of diagnostic data from a digital machine: Based on a study of the Morris, Illinois, Electronic Central Office. Bell Sys. Tech. J., 45(8):1299-1338, 1966.

J. B. Kruskal and D. Seery. Designing network diagrams. In Proc. First General Conference on Social Graphics, pages 22-50, 1980.

A. Morrison and M. Chalmers. Improving hybrid MDS with pivot-based searching. In Proc. InfoVis, pages 85-90. IEEE, 2003.

A. Morrison, G. Ross, and M. Chalmers. A hybrid layout algorithm for subquadratic multidimensional scaling. In Proc. InfoVis, pages 152-158. IEEE, 2002.

J. C. Platt. FastMap, MetricMap, and Landmark MDS are all Nystršom Algorithms. Technical report, Microsoft Research, 2004.

L. K. Saul, K. Q. Weinberger, J. H. Ham, F. Sha, and D. D. Lee. Spectral methods for dimensionality reduction. In B. Schölkopf, O. Chapelle, and A. Zien, editors, Semi-Supervised Learning. MIT Press, 2006. To appear.

J. G. Silva, J. S. Marques, and J. M. Lemos. Selecting landmark points for sparse manifold learning. In Proc. NIPS, 2005.

W. S. Torgerson. Multidimensional scaling: I. Theory and Method. Psychometrika, 17:401-419, 1952.

J. T.-L. Wang, X. Wang, K. Lin, D. Shasha, B. A. Shapiro, and K. Zhang. Evaluating a class of distance-mapping algorithms for data mining and clustering. In Proc. KDD, pages 307-311, 1999.

M. Williams and T. Munzner. Steerable, progressive multidimensional scaling. In Proc. InfoVis, pages 57-64. IEEE, 2004.