Exploration of graph structures is an important topic in data mining and data visualization. This work presents a novel technique for visualizing neighbourhood and cluster relationships in graphs; we also show how this methodology can be used within the setting of a recommendation system. Our technique works by projecting the original object distances onto two dimensions while carefully retaining the ‘backbone’ of important distances. Cluster information is also overlayed on the same projected space. A significant advantage of our approach is that it can accommodate both metric and non-metric distance functions. Our methodology is applied to a visual recommender system for movies to allow easy exploration of the actor–movie bipartite graph. The work offers intuitive movie recommendations based on a selected pivot movie and allows the interactive discovery of related movies based on both textual and semantic features.
HoaglinDCMostellerFTukeyJW. Understanding robust and exploratory data analysis. Wiley, New York; 1983.
2.
WattenbergM. Visual exploration of multivariate graphs. In: Proceedings of the SIGCHI conference on human factors in computing systems, 2006, pp.811–819.
3.
TretheweyPHöllererT. Interactive manipulation of large graph layouts. Technical Report, University of Calfornia, Santa Barbara, CA, USA, 2009.
GretarssonBO’DonovanJBostandjievS. Smallworlds: visualizing social recommendations. Comput Graph Forum2010; 29(3): 833–842.
6.
WongPCFooteHMackeyP. A dynamic multiscale magnifying tool for exploring large sparse graphs. Inform Vis2008; 7(2): 105–117.
7.
HermanIMelanconGMarshallM. Graph visualization and navigation in information visualization: a survey. IEEE Tran Vis Comput Graph2000; 6(1): 24–43.
8.
CuiW. A survey on graph visualization. PhD Qualifying Exam (PQE) Report, Computer Science Department, Hong Kong University of Science and Technology, 2007.
TenenbaumJBde SilvaVLangfordJC. A global geometric framework for nonlinear dimensionality reduction. Science2000; 290(5500): 2319–2323.
11.
BelkinMNiyogiP. Laplacian Eigenmaps for dimensionality reduction and data representation. Neural Comput2003; 15(6): 1373–1396.
12.
DonohoDLGrimesC. Hessian Eigenmaps: new locally linear embedding techniques for high-dimensional data. Proc Nat Acad Sci USA2003; 100(10): 5591–5596.
13.
RoweisSSaulL. Nonlinear dimensionality reduction by locally linear embedding. Science2000; 290(5500): 2323–2326.
14.
YangL. Distance-preserving projection of high-dimensional data for nonlinear dimensionality reduction. IEEE Trans Pattern Anal Mach Intell2004; 26(9): 1243–1246.
15.
LeeJVerleysenM. Nonlinear dimensionality reduction of data manifolds with essential loops. Neurocomputing2005; 67: 29–53.
16.
CarterKM. Dimensionality reduction on statistical manifolds. PhD Thesis, University of Michigan, USA, 2009.
17.
BourgainJ. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J Math1985; 52: 46–52.
18.
HristescuGFarach-ColtonM. Cluster-preserving embedding of proteins. Technical Report 99-50, Computer Sscience Department, Rutgers University, New Brunswick, NJ, USA, 1999.
19.
FaloutsosCLinKI. FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In: International conference on management of data (SIGMOD), 1995, pp.163–174.
20.
AthitsosVAlonJSclaroffS. BoostMap: an embedding method for efficient nearest neighbor retrieval. IEEE Trans Pattern Anal Mach Intell2008; 30(1): 89–104.
21.
GionisAIndykPMotwaniR. Similarity search in high dimensions via hashing. In: International conference on very large databases (VLDB), 1999, pp.518–529.
22.
AndoniAIndykP. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In: IEEE symposium on foundations of computer science (FOCS), 2006, pp.459–468.
23.
AthitsosVPotamiasMPapapetrouP. Nearest neighbor retrieval using distance-based hashing. In: Proceedings of international conference on data engineering (ICDE), 2008, pp.327–336.
24.
SvonavaDVlachosM. Visualization graph using minimum spanning dendrograms. In: Proceedings of the 2010 IEEE international conference on data mining, 2010, pp.1073–1078.
25.
AggarwalCCWolfJLWuK-L. Horting hatches an egg: a new graph-theoretic approach to collaborative filtering. In: Proceedings of the fifth ACM SIGKDD international conference on knowledge discovery and data mining, 1999, pp.201–212.
26.
HuangZChungWChenH. A graph model for e-commerce recommender systems. JASIST2004; 55(3): 259–274.
27.
DavidsonJLiebaldBLiuJ. The YouTube video recommendation system. In: Proceedings of the 4th ACM conference on recommender systems (RecSys ‘10), 2010, pp.293–296.
28.
MeiTYangBHuaX-S. VideoReach: an online video recommendation system. In: Proceedings of international conference on information retrieval (SIGIR), 2007, pp.767–768.
29.
BennettJLanningS. The Netflix prize. In: Proceedings of KDD cup and workshop, 2007.
30.
EyjolfsdottirEATilakGLiN. MovieGEN: a movie recommendation system. Technical Report, University of California, Santa Barbara, CA, USA, 2010.
31.
GruvstadFGuptaNAgrawalS. Shiniphy – visual data mining of movie recommendations. Technical Report, Stanford University, Stanford, CA, USA, 2009.
32.
MillerBNAlbertILamSK. MovieLens unplugged: experiences with an occasionally connected recommender system. In: Proceedings of international conference on intelligent user interfaces (IUI), 2003, pp.263–266.
33.
O’DonovanJSmythBGretarssonB. Peerchooser: visual interactive recommendation. In: Proceeding of the twenty-sixth annual SIGCHI conference on human factors in computing systems, 2008, pp.1085–1088.
34.
KhoshneshinMStreetN. Collaborative filtering via Euclidean embedding. In: Proceedings of ACM recommender systems, Barcelona, Spain, September 2010, pp.87–94.
35.
ChenKLiuL. Vista: validating and refining clusters via visualization. Inform Vis2004; 3(4): 257–270.
36.
RheingansPLandrethC. Principles for effective visualizations. In: GrinsteinGLevkowitzH (eds) Perceptual issues in visualization. Berlin: Springer-Verlag, 1995, pp.59–73.
37.
LeeRSlagleJBlumH. A triangulation method for the sequential mapping of points from N-Space to two-space. IEEE Trans Comput1977; C-26(3): 288–292.
38.
OtenRde FigueiredoR. Topological dimensionality determination and dimensionality reduction based on minimum spanning trees. In: Proceedings of IEEE international symposium on circuits and systems, Monterey, CA, 31 May–3 June 1998, pp.366–369.
39.
KeimDAMansmannFSchneidewindJ. Visual analytics: scope and challenges. In: SimoffSJBöhlenMHMazeikaA (eds) Visual data mining: theory, techniques and tools for visual analytics. Berlin Heidelberg: Springer, 2008, pp.76–90.
40.
HuangWEadesPHongS-H. Measuring effectiveness of graph visualizations: a cognitive load perspective. Inform Vis2009; 8(3): 139–152.
41.
CernyV. A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Opt Theory Appl1985; 45: 41–51.
42.
KeoghE. Exact indexing of dynamic time warping. In: Proceedings of 28th international conference on very large data bases, 2002, pp.406–417.
43.
VlachosMKolliosGGunopulosD. Discovering similar multidimensional trajectories. In: Proceedings of international conference on data engineering (ICDE), 2002, pp.673–684.
44.
ChazelleB. A minimum spanning tree algorithm with inverse-ackermann type complexity. J ACM2000; 47: 1028–1047.
45.
KargerDRKleinPNTarjanRE. A randomized linear-time algorithm to find minimum spanning trees. J ACM1995; 42(2): 321–328.
46.
LipkusA. A proof of the triangle inequality for the Tanimoto distance. J Math Chem1999; 26: 263–265.
LeeMDWelshM. An empirical evaluation of models of text document similarity. In: BaraBGBarsalouLBucciarelliN (eds) 27th Annual meeting of the cognitive science, 2005, pp.1254–1259.
49.
AndoRK. Latent semantic space: iterative scaling improves precision of inter-document similarity measurement. In: Proceedings of the 23rd annual ACM SIGIR conference on research and development in information retrieval (SIGIR-2000), 2000, pp.216–223.
