ASALSAN is a new algorithm for computing three-way DEDICOM, which is a linear algebra model for analyzing intrinsically asymmetric relationships, such as trade among nations or the exchange of emails among individuals, that incorporates a third mode of the data, such as time. ASALSAN is unique because it enables computing the three-way DEDICOM model on large, sparse data. A nonnegative version of ASALSAN is described as well. When we apply these techniques to adjacency arrays arising from directed graphs with edges labeled by time, we obtain a smaller graph on latent semantic dimensions and gain additional information about their changing relationships over time. We demonstrate these techniques on international trade data and the Enron email corpus to uncover latent components and their transient behavior. The mixture of roles assigned to individuals by ASALSAN showed strong correspondence with known job classifications and revealed the patterns of communication between these roles. Changes in the communication pattern over time, e.g., between top executives and the legal department, were also apparent in the solutions.

Links:

• Earlier versions released as Sandia Technical Report SAND2006-7744, September, 2006 and SAND2006-2161, April 2006.

DEDICOM is an algebraic model for analyzing intrinsically asymmetric relationships, such as the balance of trade among nations or the flow of information among organizations or individuals. It provides information on latent components in the data that can be regarded as "properties" or "aspects" of the objects, and it finds a few patterns that can be combined to describe many relationships among these components. When we apply this technique to adjacency matrices arising from directed graphs, we obtain a smaller graph that gives an idealized description of its patterns. Three-way DEDICOM is a higher-order extension of the model that has certain uniqueness properties. It allows for a third mode of the data, such as time, and permits the analysis of semantic graphs. We present an improved algorithm for computing three-way DEDICOM on sparse data and demonstrate it by applying it to the adjacency tensor of a semantic graph with time-labeled edges. Our application uses the Enron email corpus, from which we construct a semantic graph corresponding to email exchanges among Enron personnel over a series of 44 months. Meaningful patterns are recovered in which the representation of asymmetries adds insight into the social networks at Enron.

As the size of the web increases, it becomes more and more important to analyze link structure while also considering context. Multilinear algebra provides a novel tool for incorporating anchor text and other information into the authority computation used by link analysis methods such as HITS. Our recently proposed TOPHITS method uses a higher-order analogue of the matrix singular value decomposition called the PARAFAC model to analyze a three-way representation of web data. We compute hubs and authorities together with the terms that are used in the anchor text of the links between them. Adding a third dimension to the data greatly extends the applicability of HITS because the TOPHITS analysis can be performed in advance and offline. Like HITS, the TOPHITS model reveals latent groupings of pages, but TOPHITS also includes latent term information. In this paper, we describe a faster mathematical algorithm for computing the TOPHITS model on sparse data, and Web data is used to compare HITS and TOPHITS. We also discuss how the TOPHITS model can be used in queries, such as computing context-sensitive authorities and hubs. We describe different query response methodologies and present experimental results.

Linear algebra is a powerful and proven tool in web search. Techniques, such as the PageRank algorithm of Brin and Page and the HITS algorithm of Kleinberg, score web pages based on the principal eigenvector (or singular vector) of a particular non-negative matrix that captures the hyperlink structure of the web graph. We propose and test a new methodology that uses multilinear algebra to elicit more information from a higher-order representation of the hyperlink graph. We start by labeling the edges in our graph with the anchor text of the hyperlinks so that the associated linear algebra representation is a sparse, three-way tensor. The first two dimensions of the tensor represent the web pages while the third dimension adds the anchor text. We then use the rank-1 factors of a multilinear PARAFAC tensor decomposition, which are akin to singular vectors of the SVD, to automatically identify topics in the collection along with the associated authoritative web pages.

Links:

• Previous version released as Sandia Technical Report SAND2005-4548. (July 2005) - PDF.

This paper investigates the performance of tensor methods for solving small- and large-scale systems of nonlinear equations where the Jacobian matrix at the root is ill-conditioned or singular. This condition occurs on many classes of problems, such as identifying or approaching turning points in path following problems. The singular case has been studied more than the highly ill-conditioned case, for both Newton and tensor methods. It is known that Newton-based methods do not work well with singular problems because they converge linearly to the solution and, in some cases, with poor accuracy. On the other hand, direct tensor methods have performed well on singular problems and have superlinear convergence on such problems under certain conditions. This behavior originates from the use of a special, restricted form of the second-order term included in the local tensor model that provides information lacking in a (nearly) singular Jacobian. With several implementations available for large-scale problems, tensor methods now are capable of solving larger problems. We compare the performance of tensor methods and Newton-based methods for both small- and large-scale problems over a range of conditionings, from well-conditioned to ill-conditioned to singular. Previous studies with tensor methods only concerned the ends of this spectrum. Our results show that tensor methods are increasingly superior to Newton-based methods as the problem grows more ill-conditioned.

Links:

• Available as Sandia Technical Report SAND2004-1944, September, 2004.

This paper develops and investigates iterative tensor methods for solving large-scale systems of nonlinear equations. Direct tensor methods for nonlinear equations have performed especially well on small, dense problems where the Jacobian matrix at the solution is singular or ill-conditioned, which may occur when approaching turning points, for example. This research extends direct tensor methods to large-scale problems by developing three tensor-Krylov methods that base each iteration upon a linear model augmented with a limited second-order term, which provides information lacking in a (nearly) singular Jacobian. The advantage of the new tensor-Krylov methods over existing large-scale tensor methods is their ability to solve the local tensor model to a specified accuracy, which produces a more accurate tensor step. The performance of these methods in comparison to Newton-GMRES and tensor-GMRES is explored on three Navier--Stokes fluid flow problems. The numerical results provide evidence that tensor-Krylov methods are generally more robust and more efficient than Newton-GMRES on some important and difficult problems. In addition, the results show that the new tensor-Krylov methods and tensor-GMRES each perform better in certain situations.

Links:

• Earlier version available as Sandia Technical Report SAND2004-1837 (August 2004)

Tensors (also known as mutidimensional arrays or N-way arrays) are used in a variety of applications ranging from chemometrics to psychometrics. We describe four MATLAB classes for tensor manipulations that can be used for fast algorithm prototyping. The tensor class extends the functionality of MATLAB's multidimensional arrays by supporting additional operations such as tensor multiplication. The tensor_as_matrix class supports the "matricization" of a tensor, i.e., the conversion of a tensor to a matrix (and vice versa), a commonly used operation in many algorithms. Two additional classes represent tensors stored in decomposed formats: cp_tensor and tucker_tensor. We describe all of these classes and then demonstrate their use by showing how to implement several tensor algorithms that have appeared in the literature.

Links:

• Webpage: MATLAB Tensor Toolbox
• Software: released under SAND2004-5189 and is available in TGZ or ZIP format.
• Technical Report SAND2004-5187 (October 2004) pdf
• A previous version was released as Tech. Rep. SAND2004-3487 (July 2004)
• Revision: July 20, 2005 (Paper in PDF, 0.3 MB) (Code in TGZ, 29 kb)

We describe a large-scale, stochastic-perturbation global optimization algorithm used for determining the structure of proteins. The method incorporates secondary structure predictions (which describe the more basic elements of the protein structure) into the starting structures, and thereafter minimizes using a purely physics-based energy model. Results show this method to be particularly successful on protein targets where structural information from similar proteins is unavailable, i.e., the most difficult targets for most protein structure prediction methods. Our best result to date is on a protein target containing over 4000 atoms and 12,000 cartesian coordinates.

Links:

• Published online © Springer-Verlag 2004 - Online access

This paper presents a curvilinear linesearch for use when solving nonlinear equations with tensor methods. Standard tensor methods use a combination of the tensor step and Newton step in a linesearch, but they are handled separately and in an ad hoc manner. Our curvilinear linesearch combines the two directions in a single parametric step, which guarantees a monotonic decrease on the tensor model and also asymptotically approaches the Newton direction as the step length shrinks to zero, thus guaranteeing descent on the nonlinear equations. Numerical experiments on a set of 35 small-scale problems, drawn primarily from the CUTE collection, show an 18--23\% improvement (in terms of function evaluations) over previous tensor linesearches when using quadratic backtracking and a 41--83\% improvement when halving $\lambda$ before each trial. Our results also suggest that the curvilinear linesearch is more robust than linesearch-based Newton's method or the standard tensor linesearch, producing fewer failures than either method. Experiments on two large-scale fluid flow problems complement the small-scale results and give preliminary indication of the applicability of the tensor method and the efficiency of the curvilinear linesearch. The theoretical properties, coupled with the better performance, make this a desirable improvement over previous tensor method linesearches.

Links:

• Published online © SIAM (Nov. 2003) - online access.

Cultivation of MRC-5 cells and attenuated hepatitis A virus (HAV) for the production of VAQTA, an inactivated HAV vaccine (1), is performed in the CellCube reactor, a laminar flow fixed-bed bioreactor with an unusual diamond-shaped, diverging-converging flow geometry. These disposable bioreactors have found some popularity for the production of cells and gene therapy vectors at intermediate scales of operation (2, 3). Early testing of the CellCube revealed that the fluid mechanical environment played a significant role in nonuniform cell distribution patterns generated during the cell growth phase. Specifically, the reactor geometry and manufacturing artifacts, in combination with certain inoculum practices and circulation flow rates, can create cell growth behavior that is not simply explained. Via experimentation and computational fluid dynamics simulations we can account for practically all of the observed cell growth behavior, which appears to be due to a complex mixture of flow distribution, particle deposition under gravity, fluid shear, and possibly nutritional microenvironment.

Links:

• Published online © 2003 by American Chemical Society and American Institute of Chemical Engineers - Online access

We describe our global optimization method called Stochastic Perturbation with Soft Constraints (SPSC), which uses information from known proteins to predict secondary structure, but not in the tertiary structure predictions or in generating the terms of the physics-based energy function. Our approach is also characterized by the use of an all atom energy function that includes a novel hydrophobic solvation function derived from experiments that shows promising ability for energy discrimination against misfolded structures. We present the results obtained using our SPSC method and energy function for blind prediction in the 4^th Critical Assessment of Techniques for Protein Structure Prediction competition, and show that our approach is more effective on targets for which less information from known proteins is available. In fact our SPSC method produced the best prediction for one of the most difficult targets of the competition, a new fold protein of 240 amino acids.

Links:

• Published online © 2002 by the Biophysical Society - Online access

Treatment of human natural killer (NK) cells with phospholipase A₂ (PLA₂) inhibitors, mepacrine and 4-bromophenacyl bromide (BPB), diminished their ability to lyse K562 target cells by as much as 100%. The ability of NK cells to bind to K562 cells was significantly affected by BPB above 2 µM, but not by mepacrine at any concentration tested. This indicates that BPB is having effects on NK cells unrelated to its inhibition of PLA₂ activity at concentrations above 2 µM. The activation of phospholipase C in response to K562 cell binding (as measured by inositol phosphate turnover) was unaffected by inhibition of the PLA₂ activity. The products of PLA₂ catabolism are a fatty acid (often arachidonic acid) and a lysophospholipid. Inhibition of NK cytotoxicity by mepacrine or BPB is reversed significantly when lysophosphatidylcholine, but no other lysolipid, is added back to the NK cells before assaying for cytotoxicity. Arachidonic acid, but not linoleic acid, also significantly reverses inhibition of NK cytotoxicity. Finally, the 15-lipoxygenase product, 15S-hydroperoxyeicosatetraenoic acid (15S-HPETE), is also able to reverse mepacrine-induced inhibition of NK cytotoxicity. The 5-lipoxygenase product 5S-HPETE was not effective. These data indicate that PLA₂ activation is a necessary signal in human NK cytotoxicity and that it is not involved in protein tyrosine kinase and subsequent phospholipase C activation; these latter two enzymes are also required in the cytotoxic response. Thus PLA₂ activation is either a more distal signal, dependent on activation of some earlier signal, or an independent cosignal stimulated by tumor-target binding which generates lysophosphatidylcholine, arachidonic acid, and/or a lipoxygenase product(s).

Links:

• Published online © 1999 S. Karger AG, Basel - Online access

Workshop on Algorithms for Modern Massive Data Sets
Stanford University and Yahoo! Research, Palo Alto, CA, June 21-24, 2006.

This presentation introduces the DEDICOM (DEcomposition into DIrectional COMponents) family of models from the psychometrics literature for analyzing asymmetric relationships in data and applies it to new applications in data mining, in particular social network analysis. In this work we present an improved algorithm for computing the 3-way DEDICOM model with modifications that make it possible to handle large, sparse data sets. We demonstrate the capabilities of DEDICOM as a new tool for reporting latent relationships in large semantic graphs, which we represent by an adjacency tensor. For an application we consider the email communications of former Enron employees that were made public, and posted to the web, by the U.S. Federal Energy Regulatory Commission during its investigation of Enron. We represent the Enron email network as a directed graph with edges labeled by time. Using the three-way DEDICOM model on this data, we show unique latent relationships that exist between types of employees and study their communication patterns over time.

Joint work with Richard Harshman and Tamara G. Kolda.

Links:

• Slides online

SIAM Annual Meeting 2004
Portland, OR, July 12-16, 2004.

We present a tensor method that is easy to implement in large-scale applications. Tensor methods are an alternative to Newton-based methods and are based on using a quadratic local model rather than a linear model. The advantage of this method is that it can use any existing linear solver. We will also discuss a special globalization technique and other modifications for added robustness. We present numerical results showing computational advantages over Newton-GMRES on some realistic problems.

Links:

• See Copper Mountain slides online

Copper Mountain Conference on Iterative Methods 2004
Copper Mountain, CO, March 28 - April 2, 2004.

We compare and contrast a variety of iterative tensor methods for solving large-scale systems of nonlinear equations. Tensor methods are an alternative to Newton-based methods and are based on using a limited quadratic local model rather than a linear model. These higher order models often provide information that is lacking in a (nearly) singular Jacobian, thus making the solver more efficient when solving difficult problems.

This talk has three areas of emphasis. First, we introduce several new and recent iterative tensor methods for solving large-scale problems, including tensor-Krylov methods and a new implementation that can use a stand-alone linear solver. The methods have a range of characteristics and other considerations for a practical implementation, which we discuss. Second, we apply a curvilinear linesearch globalization technique to the tensor methods that smoothly combines the Newton and tensor directions. Our results show that the curvilinear linesearch is more robust and efficient than other linesearch implementations. Finally, we explore the performance of these large-scale tensor methods in comparison to Newton-GMRES on several realistic problems, including some Navier-Stokes fluid flow problems. All methods are implemented in an object-oriented nonlinear software package called NOX that is being developed at Sandia National Laboratories. Our results show that the iterative tensor methods have computational advantages over Newton-GMRES, especially when the Jacobian at the root is ill-conditioned or singular.

Links:

• Slides online

Solution Methods for Large-scale Nonlinear Problems 2003
Hilton Garden Inn, Livermore, CA, August 6-8, 2003.

This talk will introduce several iterative, Krylov-subspace based approaches for solving large-scale systems of nonlinear equations using tensor methods. Standard tensor methods have performed especially well on small, dense problems where the Jacobian matrix at the solution is singular or ill-conditioned, something that happens on many classes of large-scale problems, such as bifurcation tracking. This research extends tensor methods to large-scale problems by developing a class of tensor-Krylov methods that base each iteration on a linear model augmented with a limited second-order term and employ a line search globalization scheme that imitates a trust region method. Two advantages over existing methods are an ability to solve the local tensor model to a specified accuracy and a reliance on block methods, which can be more memory efficient than standard techniques. In addition, the tensor-Krylov methods still exhibit the super linear convergence behavior of direct tensor methods on singular and ill-conditioned problems. Numerical comparisons with Newton-GMRES on several benchmark fluid flow problems are presented and provide evidence that tensor-Krylov methods are more robust and efficient than Newton-GMRES on some important and difficult problems.

Links:

• Abstracts and slides online