Multi-way set enumeration in weight tensors

Elisabeth Georgii, Koji Tsuda, Bernhard SchölkopfMachine Learning 2011 · DOI · OpenReview

Introduction

Data mining traditionally focuses on two-dimensional itemsets—identifying groups of items that frequently co-occur in transactions. However, modern datasets are increasingly multi-dimensional (multi-way). For instance, a sales database might track products across various regions and time periods. Finding meaningful patterns in such "tensors" requires looking across all dimensions simultaneously.

Existing "n-set" mining techniques often rely on binary data, where an association either exists or does not. This "all-or-nothing" approach is fragile; in real-world weighted data (like ratings or communication frequency), a single missing or noisy observation can obscure a significant pattern. This paper introduces DCE (Dense Cluster Enumeration), an algorithm designed to find dense clusters in multi-way tensors by focusing on average weight rather than binary existence.

The DCE Algorithm

The DCE algorithm identifies subtensors where the average weight of all possible associations exceeds a specified threshold. This density-based approach allows the algorithm to tolerate noise and missing links. Its efficiency is rooted in two primary mechanisms:

1. Reverse Search Strategy

Standard mining often uses a lexicographical tree to explore combinations. DCE instead employs a "reverse search" strategy based on a reduction map. In this framework, a "parent" cluster is defined by removing the "weakest link"—the element with the minimum degree—from a child cluster. This ensures that every valid dense cluster is reachable from a simple root (a single high-weight element) without redundant traversals.

2. Density-Based Pruning

A key mathematical property leveraged by DCE is that removing the minimum-degree instance from a cluster never decreases the cluster's average density. This "anti-monotonicity" allows the algorithm to aggressively prune branches of the search tree that fall below the density threshold, as they can never lead to a valid dense solution.

Comparison of search space structures: (a) weight matrix, (b) full graph, (c) lexicographical tree, and (d) the proposed reverse search tree.

To further enhance performance, the authors introduce Branching Restrictions, a heuristic that limits exploration to the $k$ most promising paths. This significantly reduces computation time while still capturing the most significant patterns.

Experimental Evaluation

The researchers evaluated DCE using both synthetic and real-world datasets, including the ENRON email dataset and yeast coexpression networks.

  • Scalability and Robustness: Synthetic tests demonstrated that DCE's runtime scales linearly with the number of instances per dimension. The branching heuristic (with $k=3$ or $4$) reduced runtimes by orders of magnitude in high-noise scenarios while maintaining nearly 100% recall.
  • Real-World Insights: On the ENRON dataset (Sender $\times$ Recipient $\times$ Week), DCE identified a core group of 3 senders and 4 recipients with intense communication over a 4-week window, revealing organizational sub-structures.
  • Biological Relevance: In yeast coexpression data (Gene $\times$ Gene $\times$ Experiment), the clusters found were highly homogeneous, with grouped genes independently verified to share biological functions.

Conclusion

DCE provides a robust framework for mining complex, high-dimensional relationships in noisy, weighted data. As a "polynomial-delay" algorithm, it offers theoretical guarantees on efficiency. While setting low density thresholds can lead to an overwhelming number of solutions, the integration of additional anti-monotonic constraints and refined heuristics remains a promising path for future optimization.

Summary updated

Abstract

The analysis of n-ary relations receives attention in many different fields, for instance biology, web mining, and social studies. In the basic setting, there are n sets of instances, and each observation associates n instances, one from each set. A common approach to explore these n-way data is the search for n-set patterns, the n-way equivalent of itemsets. More precisely, an n-set pattern consists of specific subsets of the n instance sets such that all possible associations between the corresponding instances are observed in the data. In contrast, traditional itemset mining approaches consider only two-way data, namely items versus transactions. The n-set patterns provide a higher-level view of the data, revealing associative relationships between groups of instances. Here, we generalize this approach in two respects. First, we tolerate missing observations to a certain degree, that means we are also interested in n-sets where most (although not all) of the possible associations have been recorded in the data. Second, we take association weights into account. In fact, we propose a method to enumerate all n-sets that satisfy a minimum threshold with respect to the average association weight. Technically, we solve the enumeration task using a reverse search strategy, which allows for effective pruning of the search space. In addition, our algorithm provides a ranking of the solutions and can consider further constraints. We show experimental results on artificial and real-world datasets from different domains.
BibTeX
@article{georgii2011multi,
  author = {Elisabeth Georgii and Koji Tsuda and Bernhard Schölkopf},
  title = {{Multi-way set enumeration in weight tensors}},
  journal = {Machine Learning},
  year = {2011},
  doi = {10.1007/s10994-010-5210-y},
}
Figure