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.
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