liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 24) Show all publications
Savas, B. & Eldén, L. (2013). Krylov-type methods for tensor computations I. Linear Algebra and its Applications, 438(2), 891-918
Open this publication in new window or tab >>Krylov-type methods for tensor computations I
2013 (English)In: Linear Algebra and its Applications, ISSN 0024-3795, E-ISSN 1873-1856, Vol. 438, no 2, p. 891-918Article in journal (Refereed) Published
Abstract [en]

Several Krylov-type procedures are introduced that generalize matrix Krylov methods for tensor computations. They are denoted minimal Krylov recursion, maximal Krylov recursion, and contracted tensor product Krylov recursion. It is proved that, for a given tensor A with multilinear rank-(p; q; r), the minimal Krylov recursion extracts the correct subspaces associated to the tensor in p+q+r number of tensor-vector-vector multiplications. An optimized minimal Krylov procedure is described that, for a given multilinear rank of an approximation, produces a better approximation than the standard minimal recursion. We further generalize the matrix Krylov decomposition to a tensor Krylov decomposition. The tensor Krylov methods are intended for the computation of low multilinear rank approximations of large and sparse tensors, but they are also useful for certain dense and structured tensors for computing their higher order singular value decompositions or obtaining starting points for the best low-rank computations of tensors. A set of numerical experiments, using real-world and synthetic data sets, illustrate some of the properties of the tensor Krylov methods.

Place, publisher, year, edition, pages
Elsevier, 2013
Keywords
Tensor, Krylov-type method, tensor approximation, Tucker model, multilinear algebra, multilinear rank, sparse tensor, information science
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-73727 (URN)10.1016/j.laa.2011.12.007 (DOI)000313226900017 ()
Note

Special Issue on Tensors and Multilinear Algebra

Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2017-12-08Bibliographically approved
Song, H. H., Savas, B., Cho, T. W., Dave, V., Lu, Z., Dhillon, I. S., . . . Qiu, L. (2012). Clustered Embedding of Massive Social Networks. In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems: . Paper presented at the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, June 11-15, London, UK (pp. 331-342). Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Clustered Embedding of Massive Social Networks
Show others...
2012 (English)In: Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2012, , p. 27p. 331-342Conference paper, Published paper (Other academic)
Abstract [en]

The explosive growth of social networks has created numerous exciting research opportunities. A central concept in the analysis of social networks is a proximity measure, which captures the closeness or similarity between nodes in a social network. Despite much research on proximity measures,  there is a lack of techniques to eciently and accurately compute proximity measures for large-scale social networks. In this paper, we develop a novel dimensionality reduction technique, called clustered spectral graph embedding, to embed the graphs adjacency matrix into a much smaller matrix. The embedded matrix together with the embedding subspaces capture the essential clustering and spectral structure of the original graph and allows a wide range of analysis tasks to be performed in an ecient and accurate fashion. To evaluate our technique, we use three large real-world social  network datasets: Flickr, LiveJournal and MySpace, with up to 2 million nodes and 90 million links. Our results clearly demonstrate the accuracy, scalability and  exibility of our approach in the context of three importantsocial network analysis tasks: proximity estimation, missing link inference, and link prediction.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2012. p. 27
Series
ACM SIGMETRICS Performance Evaluation Review, ISSN 0163-5999 ; Vol. 40, Iss.1
National Category
Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-86053 (URN)10.1145/2254756.2254796 (DOI)978-1-4503-1097-0 (ISBN)
Conference
the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, June 11-15, London, UK
Available from: 2012-12-06 Created: 2012-12-06 Last updated: 2018-01-12Bibliographically approved
Sui, X., Lee, T.-H., Whang, J. J., Savas, B., Jain, S., Pingali, K. & Dhillon, I. S. (2012). Parallel clustered low-rank approximation of graphs and its application to link prediction. In: Proceedings of the International Workshop on Languages and Compilers for Parallel Computing: . Paper presented at 25th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2012), 11-13 September 2012, Tokyo, Japan (pp. 76-95). Springer Berlin Heidelberg
Open this publication in new window or tab >>Parallel clustered low-rank approximation of graphs and its application to link prediction
Show others...
2012 (English)In: Proceedings of the International Workshop on Languages and Compilers for Parallel Computing, Springer Berlin Heidelberg , 2012, p. 76-95Conference paper, Published paper (Other academic)
Abstract [en]

Social network analysis has become a major research area that has impact in diverse applications ranging from search engines to product recommendation systems. A major problem in implementing social network analysis algorithms is the sheer size of many social networks, for example, the Facebook graph has more than 900 million vertices and even small networks may have tens of millions of vertices. One solution to dealing with these large graphs is dimensionality reduction using spectral or SVD analysis of the adjacency matrix of the network, but these global techniques do not necessarily take into account local structures or clusters of the network that are critical in network analysis. A more promising approach is clustered low-rank approximation: instead of computing a global low-rank approximation, the adjacency matrix is first clustered, and then a low-rank approximation of each cluster (i.e., diagonal block) is computed. The resulting algorithm is challenging to parallelize not only because of the large size of the data sets in social network analysis, but also because it requires computing with very diverse data structures ranging from extremely sparse matrices to dense matrices. In this paper, we describe the first parallel implementation of a clustered low-rank approximation algorithm for large social network graphs, and use it to perform link prediction in parallel. Experimental results show that this implementation scales well on large distributed-memory machines; for example, on a Twitter graph with roughly 11 million vertices and 63 million edges, our implementation scales by a factor of 86 on 128 processes and takes less than 2300 seconds, while on a much larger Twitter graph with 41 million vertices and 1.2 billion edges, our implementation scales by a factor of 203 on 256 processes with a running time about 4800 seconds.

Place, publisher, year, edition, pages
Springer Berlin Heidelberg, 2012
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 7760
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-86055 (URN)10.1007/978-3-642-37658-0_6 (DOI)978-3-642-37657-3 (ISBN)978-3-642-37658-0 (ISBN)
Conference
25th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2012), 11-13 September 2012, Tokyo, Japan
Available from: 2012-12-06 Created: 2012-12-06 Last updated: 2018-01-31
Savas, B. & Dhillon, I. S. (2011). Clustered low rank approximation of graphs in information science applications. In: Proceedings of the SIAM International Conference on Data Mining (SDM) (pp. 164-175).
Open this publication in new window or tab >>Clustered low rank approximation of graphs in information science applications
2011 (English)In: Proceedings of the SIAM International Conference on Data Mining (SDM), 2011, p. 164-175Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we present a fast and accurate procedure called clusteredlow rank matrix approximation for massive graphs. The procedure involvesa fast clustering of the graph and then approximates each clusterseparately using existing methods, e.g. the singular value decomposition,or stochastic algorithms. The cluster-wise approximations are thenextended to approximate the entire graph. This approach has severalbenets: (1) important community structure of the graph is preserveddue to the clustering; (2) highly accurate low rank approximationsare achieved; (3) the procedure is ecient both in terms of computationalspeed and memory usage; (4) better performance in problems from variousapplications compared to standard low rank approximation. Further,we generalize stochastic algorithms to the clustered low rank approximationframework and present theoretical bounds for the approximation error.Finally, a set of experiments, using large scale and real-world graphs,show that our methods outperform standard low rank matrix approximationalgorithms.

National Category
Computational Mathematics Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-73728 (URN)
Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2018-01-12
Eldén, L. & Savas, B. (2011). Perturbation Theory and Optimality Conditions for the Best Multilinear Rank Approximation of a Tensor. SIAM Journal on Matrix Analysis and Applications, 32(4), 1422-1450
Open this publication in new window or tab >>Perturbation Theory and Optimality Conditions for the Best Multilinear Rank Approximation of a Tensor
2011 (English)In: SIAM Journal on Matrix Analysis and Applications, ISSN 0895-4798, E-ISSN 1095-7162, Vol. 32, no 4, p. 1422-1450Article in journal (Refereed) Published
Abstract [en]

The problem of computing the best rank-(p,q,r) approximation of a third order tensor is considered. First the problem is reformulated as a maximization problem on a product of three Grassmann manifolds. Then expressions for the gradient and the Hessian are derived in a local coordinate system at a stationary point, and conditions for a local maximum are given. A first order perturbation analysis is performed using the Grassmann manifold framework. The analysis is illustrated in a few examples, and it is shown that the perturbation theory for the singular value decomposition is a special case of the tensor theory.

Place, publisher, year, edition, pages
SIAM, 2011
Keywords
tensor, multilinear rank, best rank-(p, q, r) approximation, perturbation theory, first order optimality conditions, second order optimality conditions, Grassmann manifold, stationary point
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-72910 (URN)10.1137/110823298 (DOI)000298373400017 ()
Note
funding agencies|Swedish Research Council||Institute for Computational Engineering and Sciences at The University of Texas at Austin||| Dnr 2008-7145 |Available from: 2011-12-16 Created: 2011-12-09 Last updated: 2017-12-08Bibliographically approved
Vasuki, V., Natarajan, N., Lu, Z., Savas, B. & Dhillon, I. S. (2011). Scalable Affiliation Recommendation using Auxiliary Networks. ACM Transactions on Intelligent Systems and Technology, 3(1), 3:1-3:20
Open this publication in new window or tab >>Scalable Affiliation Recommendation using Auxiliary Networks
Show others...
2011 (English)In: ACM Transactions on Intelligent Systems and Technology, ISSN 2157-6904, Vol. 3, no 1, p. 3:1-3:20Article in journal (Refereed) Published
Abstract [en]

Social network analysis has attracted increasing attention in recent years. In many social networks, besides friendship links among users, the phenomenon of users associating themselves with groups or communities is common. Thus, two networks exist simultaneously: the friendship network among users, and the affiliation network between users and groups. In this article, we tackle the affiliation recommendation problem, where the task is to predict or suggest new affiliations between users and communities, given the current state of the friendship and affiliation networks. More generally, affiliations need not be community affiliations—they can be a user?s taste, so affiliation recommendation algorithms have applications beyond community recommendation. In this article, we show that information from the friendship network can indeed be fruitfully exploited in making affiliation recommendations. Using a simple way of combining these networks, we suggest two models of user-community affinity for the purpose of making affiliation recommendations: one based on graph proximity, and another using latent factors to model users and communities. We explore the affiliation recommendation algorithms suggested by these models and evaluate these algorithms on two real-world networks, Orkut and Youtube. In doing so, we motivate and propose a way of evaluating recommenders, by measuring how good the top 50 recommendations are for the average user, and demonstrate the importance of choosing the right evaluation strategy. The algorithms suggested by the graph proximity model turn out to be the most effective. We also introduce scalable versions of these algorithms, and demonstrate their effectiveness. This use of link prediction techniques for the purpose of affiliation recommendation is, to our knowledge, novel.

National Category
Computational Mathematics Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-73726 (URN)10.1145/2036264.2036267 (DOI)
Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2018-01-12
Savas, B. & Dhillon, I. S. (2010). Fast and accurate low rank approximation of massive graphs. Department of Computer Science, The University of Texas at Austin
Open this publication in new window or tab >>Fast and accurate low rank approximation of massive graphs
2010 (English)Report (Other academic)
Place, publisher, year, edition, pages
Department of Computer Science, The University of Texas at Austin, 2010
Series
Department of Computer Science, The University of Texas at Austin ; TR-10-18
National Category
Computational Mathematics Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-73723 (URN)
Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2018-01-12
Lu, Z., Savas, B., Tang, W. & Dhillon, I. S. (2010). Link prediction using multiple sources of information. Department of Computer Science, The University of Texas at Austin
Open this publication in new window or tab >>Link prediction using multiple sources of information
2010 (English)Report (Other academic)
Place, publisher, year, edition, pages
Department of Computer Science, The University of Texas at Austin, 2010
Series
Department of Computer Science, The University of Texas at Austin ; TR-10-35
National Category
Computational Mathematics Probability Theory and Statistics Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-73724 (URN)
Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2018-01-12
Savas, B. & Lim, L.-H. (2010). Quasi-Newton Methods on Grassmannians and Multilinear Approximations of Tensors. SIAM Journal on Scientific Computing, 32(6), 3352-3393
Open this publication in new window or tab >>Quasi-Newton Methods on Grassmannians and Multilinear Approximations of Tensors
2010 (English)In: SIAM Journal on Scientific Computing, ISSN 1064-8275, Vol. 32, no 6, p. 3352-3393Article in journal (Refereed) Published
Abstract [en]

In this paper we proposed quasi-Newton and limited memory quasi-Newton methods for objective functions defined on Grassmannians or a product of Grassmannians. Specifically we defined BFGS and limited memory BFGS updates in local and global coordinates on Grassmannians or a product of these. We proved that, when local coordinates are used, our BFGS updates on Grassmannians share the same optimality property as the usual BFGS updates on Euclidean spaces. When applied to the best multilinear rank approximation problem for general and symmetric tensors, our approach yields fast, robust, and accurate algorithms that exploit the special Grassmannian structure of the respective problems and which work on tensors of large dimensions and arbitrarily high order. Extensive numerical experiments are included to substantiate our claims.

Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics, 2010
Keywords
Grassmann manifold, Grassmannian, product of Grassmannians, Grassmann quasi-Newton, Grassmann BFGS, Grassmann limited memory BFGS, multilinear rank, symmetric multilinear rank, tensor, symmetric tensor, approximations
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-64571 (URN)10.1137/090763172 (DOI)000285551800009 ()
Available from: 2011-01-28 Created: 2011-01-28 Last updated: 2013-10-11
Lu, Z., Savas, B., Tang, W. & Dhillon, I. S. (2010). Supervised Link Prediction Using Multiple Sources. In: Proceedings of the IEEE International Conference on Data Mining (ICDM). Paper presented at 10th International Conference on Data Mining (ICDM), 13-17 Dec. 2010, Sydney, NSW (pp. 923-928).
Open this publication in new window or tab >>Supervised Link Prediction Using Multiple Sources
2010 (English)In: Proceedings of the IEEE International Conference on Data Mining (ICDM), 2010, p. 923-928Conference paper, Published paper (Refereed)
Abstract [en]

Link prediction is a fundamental problem in social network analysis and modern-day commercial applications such as Facebook and Myspace. Most existing research approaches this problem by exploring the topological structure of a social network using only one source of information. However, in many application domains, in addition to the social network of interest, there are a number of auxiliary social networks and/or derived proximity networks available. The contribution of the paper is twofold: (1) a supervised learning framework that can effectively and efficiently learn the dynamics of social networks in the presence of auxiliary networks; (2) a feature design scheme for constructing a rich variety of path-based features using multiple sources, and an effective feature selection strategy based on structured sparsity. Extensive experiments on three real-world collaboration networks show that our model can effectively learn to predict new links using multiple sources, yielding higher prediction accuracy than unsupervised and singlesource supervised models.

National Category
Computational Mathematics Probability Theory and Statistics Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-73725 (URN)10.1109/ICDM.2010.112 (DOI)
Conference
10th International Conference on Data Mining (ICDM), 13-17 Dec. 2010, Sydney, NSW
Available from: 2012-01-12 Created: 2012-01-12 Last updated: 2018-01-12
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-1542-2690

Search in DiVA

Show all publications