Multilinear algebra for analyzing data with multiple linkages.

Daniel Dunlavy, Tamara G. Kolda2006 · DOI

TL;DR

This paper introduces a novel approach to analyzing complex datasets with multiple types of relationships (linkages) between data points. By representing these relationships as a multi-dimensional tensor and applying multilinear algebra techniques like PARAFAC decomposition, the authors can uncover hidden structures and derive richer insights than traditional methods. This framework is demonstrated on a publication dataset to identify communities, disambiguate authors, and predict journal publications.

What Problem Does This Paper Address?

In many real-world scenarios, data points are connected by more than one type of relationship. For instance, in a social network, individuals might be linked by direct communication, organizational structure, or shared interests. Similarly, academic papers can be linked by citations, co-authorship, shared keywords, or similar titles. Traditional link analysis methods, like those based on singular value decomposition (SVD) of adjacency matrices, typically focus on a single type of connection. This limitation prevents a comprehensive understanding of complex, multi-faceted relationships. The authors aim to bridge this gap by developing a method that can simultaneously analyze multiple linkage types, providing a more nuanced and complete picture of the data's underlying structure.

Methods

The core of the paper's methodology lies in the application of multilinear algebra, specifically tensor decomposition, to analyze data with multiple linkages.

  1. Tensor Representation: The authors represent the multi-link data as a three-way array (tensor) of size $N \times N \times K$. Here, $N$ is the number of data points (e.g., documents), and $K$ is the number of distinct link types. An entry $X_{ijk}$ in this tensor is non-zero if data point $i$ is connected to data point $j$ by link type $k$.
  2. PARAFAC Decomposition: They employ the PARAFAC (Parallel Factor Analysis) decomposition, which is a higher-order analogue of SVD. PARAFAC decomposes the tensor $X$ into a sum of $R$ rank-1 tensors, approximating $X \approx \sum_{r=1}^R \mathbf{h}_r \circ \mathbf{a}_r \circ \mathbf{c}_r$, where $\mathbf{h}_r$, $\mathbf{a}_r$, and $\mathbf{c}_r$ are vectors representing the "hub," "authority," and "link type" components for the $r$-th factor, respectively. The matrices $\mathbf{H}$, $\mathbf{A}$, and $\mathbf{C}$ formed by these vectors provide latent feature representations for documents and link types.
  3. Alternating Least Squares (ALS): The PARAFAC decomposition is solved using an Alternating Least Squares (ALS) algorithm. This iterative process optimizes one component matrix at a time while holding the others fixed, efficiently computing the decomposition.
  4. Derived Feature Vectors: The resulting hub ($\mathbf{H}$) and authority ($\mathbf{A}$) matrices provide derived feature vectors for each document. These vectors capture latent information about the documents based on the multi-link structure and can be used for various downstream tasks.

Datasets

The primary dataset used in this paper is a collection of ISI publication metadata from eleven SIAM journals and SIAM proceedings for the period 1999-2004.

  • Size: The dataset contains 5022 articles.
  • Link Types: Five types of linkages were considered:
  • Abstract similarity (cosine similarity of abstracts)
    • Title similarity (cosine similarity of titles)
    • Keyword similarity (cosine similarity of author-supplied keywords)
    • Author similarity (derived from author-document matrix)
    • Citation information (whether one document cites another)

The paper does not introduce new benchmark datasets but rather uses this existing publication data to demonstrate the effectiveness of their multi-link analysis approach.

Key Insights and Ideas

  • Uncovering Hidden Communities: The PARAFAC factors reveal distinct "communities" within the data, where each factor highlights different combinations of link types and their importance. This allows for a more nuanced understanding of how documents are related beyond simple co-occurrence or citation patterns.
  • Latent Document Similarity: By using the derived hub and authority feature vectors from the PARAFAC decomposition, the authors can compute a latent document similarity score. This score goes beyond direct text or citation analysis, potentially capturing deeper semantic relationships.
  • Author Disambiguation Power: The derived feature vectors are effective for disambiguating authors with similar names. By comparing centroids of author-specific document sets, the method can identify instances where different names likely refer to the same individual, a crucial task in bibliometric analysis.
  • Journal Prediction Insights: The feature vectors derived from the PARAFAC decomposition can be used to predict the journal in which an article was published. While accuracy might be moderate, the analysis reveals interesting similarities and confusions between journals, offering insights into their thematic overlap.
  • The Importance of Rank Selection: The quality of the results, particularly for similarity measures, is shown to be highly dependent on the chosen rank ($R$) of the PARAFAC decomposition. This highlights the heuristic nature of selecting the number of latent factors.

Key Results

  • Community Identification: For $R=30$, the first PARAFAC factor strongly emphasized title and keyword similarity, grouping papers related to "conservation laws." The tenth factor, however, was dominated by citation links, suggesting a focus on "preconditioning" topics, even when titles didn't explicitly match.
  • Latent Document Similarity: When comparing the similarity of articles to the "Link Analysis: Hubs and Authorities on the World Wide Web" paper, a higher rank ($R=30$) yielded more focused and relevant results compared to a lower rank ($R=10$). This suggests that a higher rank can capture more specific thematic connections.
  • Analyzing a Body of Work: When analyzing articles related to "GMRES," the combined hub and authority scores provided a more balanced similarity measure than using hubs or authorities alone. Similarly, for author V. KUMAR, the method identified papers closely related to his work, even those not directly linked by co-authorship or citation.
  • Author Disambiguation: The method successfully identified potential author aliases. For example, it showed strong confidence (0.98) that "V. TORCZON" and "V. J. TORCZON" referred to the same person. It also helped differentiate between authors with similar names, like "T. CHAN" versus "T. F. CHAN" and "T. M. CHAN."
  • Journal Prediction: The journal prediction task achieved an average accuracy of 45.3% across folds using bagged ensembles of decision trees. The confusion matrix revealed that journals with similar thematic focuses (e.g., "SIAM J APPL MATH" and "SIAM J MATH ANAL") were more frequently confused, which is an expected outcome.

Limitations and Future Work

  • Orthogonality of Factors: A key limitation of PARAFAC is that its factor matrices are not orthogonal, unlike the SVD. This means that the decomposition of rank $R$ is not simply the first $R$ factors of a decomposition of rank $S > R$, making it difficult to simply overestimate $R$ and select the best factors. The authors suggest considering Tucker decomposition as an alternative, which produces orthogonal component matrices.
  • Choosing Rank ($R$): The selection of the optimal rank $R$ is heuristic and significantly impacts the quality of the results. The paper notes that experimentation is often required.
  • Weighting Tensor Entries: The method for choosing the weights of the tensor entries is heuristic, and an open research question is how to best determine these weights.
  • Combining Hub and Authority Matrices: The paper explores different ways to combine hub and authority matrices for similarity measures but relegates detailed investigation to future work.
  • Adding Authors as Nodes: The authors plan to extend the model by adding authors as nodes in the network, creating a more comprehensive representation that captures document-author and author-author connections.
  • Incorporating Time: To analyze trends over time and make predictions, the authors intend to incorporate a temporal dimension into the data representation.
  • Symmetric vs. Asymmetric Connections: The choice of symmetric or non-symmetric connections for link types affects the output. The paper notes that for future research, they might explore constraining symmetric factors.

Summary updated

Abstract

Abstract Not Provided
BibTeX
@misc{dunlavy2006multilinear,
  author = {Daniel Dunlavy and Tamara G. Kolda and Tamara Kolda},
  title = {{Multilinear algebra for analyzing data with multiple linkages.}},
  year = {2006},
  doi = {10.2172/883132},
}
Figure