Ranking and sparsifying a connection graph. (English) Zbl 1461.05205
Summary: Many problems arising in dealing with high-dimensional data sets involve connection graphs in which each edge is associated with both an edge weight and a \(d\)-dimensional linear transformation. We consider vectorized versions of PageRank and effective resistance that can be used as basic tools for organizing and analyzing complex data sets. For example, generalized PageRank and effective resistance can be utilized to derive and modify diffusion distances for vector diffusion maps in data and image processing. Furthermore, the edge-ranking of the connection graphs determined by vectorized PageRank and effective resistance are an essential part of sparsification algorithms that simplify and preserve the global structure of connection graphs. In addition, we examine consistencies in a connection graph, particularly in the applications of recovering low-dimensional data sets and the reduction of noise. In these applications, we analyze the effect of deleting edges with high edge rank.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68M11 | Internet topics |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | [Achlioptas 01] D. Achlioptas. “Database-Friendly Random Projections.” In Proceedings of the 20th ACM Symposium on Principles of Database Systems, pp. 274-281, 2001. |
| [2] | [Agarwal et al. 09] S. Agarwal, N. Snavely, I. Simon, S. M. Seitz, and R. Szeliski. “Building Rome in a Day.” In Proceedings of the 12th IEEE International Conference on Computer Vision, pp. 72-79, 2009. |
| [3] | [Andersen et al. 06] R. Andersen, F. Chung, and K. Lang. “Local Graph Partitioning Using PageRank Vectors.” Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pp. 475-486, 2006. |
| [4] | [Anderson et al. 10] G. W. Anderson, A. Guionnet, and O. Zeitouni. An Introduction to Random Matrices. Cambridge University Press, 2010. · Zbl 1184.15023 |
| [5] | [Bandeira et al. 12] A. S. Bandeira, A. Singer, and D. A. Spielman. “A Cheeger Inequality for the Graph Connection Laplacian.” Available online (http://arxiv.org/pdf/1204.3873v1.pdf, 2012. · Zbl 1287.05081 |
| [6] | [Benczúr and Karger 96] A. A. Benczúr and D. R. Karger. “Approximating \(s-t\) Minimum Cuts in \(Õ(n2)\) Time.” In Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 47-55, 1996. · Zbl 0924.68150 |
| [7] | [Berkhin 06] P. Berkhin. “Bookmark-Coloring Approach to Personalized PageRank Computing.” Internet Mathematics 3 (2006), 41-62. · Zbl 1113.68375 |
| [8] | [Borgs et al. 12] C. Borgs, M. Brautbar, J. Chayes, and S.-H. Teng. “A Sublinear Time Algorithm for PageRank Computations.” In Proceedings of the 9th International Workshop on Algorithms and Models for the Web Graph, pp. 49-53, 2012. · Zbl 1342.05181 |
| [9] | [Brin and Page 98] S. Brin and L. Page. “The Anatomy of a Large-Scale Hypertextual Web Search Engine.” Computer Networks and ISDN Systems 30 (1998), 107-117. · doi:10.1016/S0169-7552(98)00110-X |
| [10] | [Chung and Radcliffe 11] F. Chung and M. Radcliffe. “On the Spectra of General Random Graphs.” Electronic Journal of Combinatorics 18 (2011), 215-229. · Zbl 1229.05248 |
| [11] | [Chung and Sternberg 92] F. Chung and S. Sternberg. “Laplacian and Vibrational Spectra for Homogeneous Graphs.” J. Graph Theory 16 (1992), 605-627. · Zbl 0768.05049 · doi:10.1002/jgt.3190160607 |
| [12] | [Chung and Zhao 10] F. Chung and W. Zhao. “A Sharp PageRank Algorithm with Applications to Edge Ranking and Graph Sparsification.” In Proceedings of Workshop on Algorithms and Models for the Web Graph (WAW) 2010, pp. 2-14. Stanford, California, 2010. · Zbl 1253.68042 |
| [13] | [Cristofides and Markstr¨om 08] D. Cristofides and K. Markström. “Expansion Properties of Random Cayley Graphs and Vertex Transitive Graphs via Matrix Martingales.” Random Structures Algorithms 32 (2008), 88-100. · Zbl 1130.05030 · doi:10.1002/rsa.20177 |
| [14] | [Cucuringu et al. 12] M. Cucuringu, Y. Lipman, and A. Singer. “Sensor Network Localization by Eigenvector Synchronization over the Euclidean Group.” ACM Transactions on Sensor Networks 8 (2012), No. 19. · doi:10.1145/2240092.2240093 |
| [15] | [Firat et al. 07] A. Firat, S. Chatterjee, and M. Yilmaz. “Genetic Clustering of Social Networks Using Random Walks.” Computational Statistics and Data Analysis 51 (2007), 6285-6294. · Zbl 1445.91042 · doi:10.1016/j.csda.2007.01.010 |
| [16] | [Fouss et al. 07] F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. “Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation.” Knowledge and Data Engineering 19 (2007), 355-369. · doi:10.1109/TKDE.2007.46 |
| [17] | [Golub and Van Loan 96] G. H. Golub and C. F. Van Loan. Matrix Computations, 3rd ed. Johns Hopkins Univ. Press, 1996. · Zbl 0865.65009 |
| [18] | [Hadani and Singer 11] R. Hadani and A. Singer. “Representation Theoretic Patterns in Three Dimensional Cryo-electron Microscopy I: The Intrinsic Reconstitution Algorithm.” Annals of Mathematics 174 (2011), 1219-1241. · Zbl 1227.92036 · doi:10.4007/annals.2011.174.2.11 |
| [19] | [Herbster et al. 08] M. Herbster, M. Pontil, and Sergio Rojas. “Fast Prediction on a Tree.” Proceedings of the Neural Information Processing Systems Foundation 21 (2008), 657-664. |
| [20] | [Horn and Johnson 85] R. Horn and C. Johnson. Matrix Analysis. Cambridge University Press, 1985. · Zbl 0576.15001 · doi:10.1017/CBO9780511810817 |
| [21] | [Jeh and Widom 03] G. Jeh and J. Widom. “Scaling Personalized Web Search.” Proceedings of the 12th World Wide Web Conference WWW, pp. 271-279, 2003. |
| [22] | [Jolliffe 02] I. T. Jolliffe. Principal Component Analysis, Springer Series in Statistics, 2nd ed. Springer, 2002. · Zbl 1011.62064 |
| [23] | [Karger 94] D. R. Karger. “Using Randomized Sparsification to Approximate Minimum Cuts.” In Proceedings of the 15th ACM symposium on Discrete Algorithms, pp. 424-432, 1994. · Zbl 0873.68164 |
| [24] | [Karger 99] D. R. Karger. “Random Sampling in Cut, Flow, and Network Design Problems.” Mathematics of Operations Research 24, (1999), 383-413. · Zbl 0977.90074 · doi:10.1287/moor.24.2.383 |
| [25] | [Karger 00] D. R. Karger, “Minimum Cuts in Near-Linear Time.” Journal of the ACM 47 (2000), 46-76. · Zbl 1094.68613 · doi:10.1145/331605.331608 |
| [26] | [Kirchhoff 47] F. Kirchhoff. “Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird.” Ann. Phys. chem. 72 (1847), 497-508. · doi:10.1002/andp.18471481202 |
| [27] | [Koutis 10] I. Koutis, G. L. Miller, and R. Peng. “Approaching Optimality for Solving SDD Linear Systems.” In Proceedings of 51st IEEE Symposium on Foundations of Computer Science, pp. 235-244, 2010. · Zbl 1310.68274 |
| [28] | [Lowe 99] D. G. Lowe. “Object Recognition from Local Scale-Invariant Features.” In Proceedings of the 7th IEEE International Conference on Computer Vision, pp. 1150-1157, 1999. |
| [29] | [Penrose 55] R. Penrose. “A Generalized Inverse for Matrices.” Cambridge Philosophical Society 51 (1955), 406-413. · Zbl 0065.24603 · doi:10.1017/S0305004100030401 |
| [30] | [Recht 11] B. Recht. “Simpler Approach to Matrix Completion.” Journal of Machine Learning Research 12 (2011), 3413-3430. · Zbl 1280.68141 |
| [31] | [Singer 11] A. Singer. “Angular Synchronization by Eigenvectors and Semidefinite Programming.” Applied and Computational Harmonic Analysis 30, (2011), 20-36. · Zbl 1206.90116 · doi:10.1016/j.acha.2010.02.001 |
| [32] | [Singer and Wu 12] A. Singer and H.-T. Wu. “Vector Diffusion Maps and the Connection Laplacian.” Communications on Pure and Applied Mathematics 65 (2012), 1067-1144. · Zbl 1320.68146 · doi:10.1002/cpa.21395 |
| [33] | [Singer et al. 11] A. Singer, Z. Zhao, Y. Shkolnisky, and R. Hadani. “Viewing Angle Classification of Cryo-electron Microscopy Images Using Eigenvectors.” SIAM Journal on Imaging Sciences 4 (2011), 723-759. · Zbl 1216.92046 · doi:10.1137/090778390 |
| [34] | [Spielman and Srivastava 08] D. A. Spielman and N. Srivastava. “Graph Sparsification by Effective Resistances.” In Proceedings of 40th ACM symposium on Theory of Computing, pp. 563-568, 2008. · Zbl 1231.68184 |
| [35] | [Spielman and Teng 04] D. A. Spielman and S.-H. Teng. “Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems.” In Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 81-90, 2004. · Zbl 1192.65048 |
| [36] | [Spielman and Teng 06] D. A. Spielman and S.-H. Teng. “Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems.” Available online (http://www.arxiv.org/abs/cs.NA/0607105), 2006. · Zbl 1311.65031 |
| [37] | [Spielman and Teng 10] D. A. Spielman and S.-H. Teng, “Spectral Sparsification of Graphs.” SIAM Journal on Computing 40 (2011), 981-1025. · Zbl 1228.68040 · doi:10.1137/08074489X |
| [38] | [Tropp 11] J. Tropp. “User-Friendly Tail Bounds for Sums of Random Matrices.” Available online (http://arxiv.org/abs/1004.4389), 2011. · Zbl 1259.60008 |
| [39] | [Vershynin 08] Roman Vershynin. “A Note on Sums of Independent Random Matrices after Ahlswede-Winter.” Available online (http://www-personal.umich.edu/\(∼\) romanv/teaching/reading-group/ahlswede-winter.pdf), 2008. |
| [40] | [Vu 07] V. Vu. “Spectral Norm of Random Matrices.” Combinatorica 27 (2007), 721-736. · Zbl 1164.05066 · doi:10.1007/s00493-007-2190-z |
| [41] | [Wigderson and Xiao 08] A. Wigderson and D. Xiao. “Derandomizing the Ahlswede-Winter Matrix-Valued Chernoff Bound Using Pessimistic Estimators, and Applications.” Theory of Computing 4 (2008), 53-76. · Zbl 1213.68697 · doi:10.4086/toc.2008.v004a003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
