Abstract
Bipartite data is common in data engineering and brings unique challenges, particularly when it comes to clustering tasks that impose strong structural assumptions. This work presents an unsupervised method for assessing similarity in bipartite data. Similar to some co-clustering methods, the method is based on regular equivalence in graphs. The algorithm uses spectral properties of a bipartite adjacency matrix to estimate similarity in both dimensions. The method is reflexive in that similarity in one dimension is used to inform similarity in the other. Reflexive regular equivalence can also use the structure of transitivities—in a network sense—the contribution of which is controlled by the algorithm's only free-parameter, $\alpha$. The method is completely unsupervised and can be used to validate assumptions of co-similarity, which are required but often untested, in co-clustering analyses. Three variants of the method with different normalizations are tested on synthetic data. The method is found to be robust to noise and well-suited to asymmetric co-similar structure, making it particularly informative for cluster analysis and recommendation in bipartite data of unknown structure. In experiments, the convergence and speed of the algorithm are found to be stable for different levels of noise. Real-world data from a network of malaria genes are analyzed, where the similarity produced by the reflexive method is shown to out-perform other measures' ability to correctly classify genes.
Introduction: The Challenge of Bipartite Data
Bipartite data structures, where connections exist exclusively between two distinct sets of entities—such as users and products, or genes and amino acid sequences—are ubiquitous in modern data engineering. Analyzing these networks often involves identifying latent groups through co-clustering. However, traditional co-clustering methods rely heavily on the assumption of "co-similarity": the premise that similarity in one dimension must strictly correspond to similarity in the other.
In practice, real-world data is frequently asymmetric or noisy. For instance, multiple groups of users might interact with overlapping sets of products in distinct ways, breaking the rigid one-to-one mapping required by many algorithms. Furthermore, existing techniques often require the number of clusters to be specified a priori, which is problematic when the underlying structure is unknown.
Methodology: Reflexive Regular Equivalence
To address these limitations, this work introduces Reflexive Regular Equivalence, an unsupervised framework for measuring similarity that avoids hard partitioning. The method is rooted in the concept of regular equivalence: two nodes are considered similar if they are connected to neighbors who are themselves similar.
The proposed algorithm introduces two primary innovations:
- Reflexivity: A feedback mechanism where similarity in Dimension A is derived from the similarity of its neighbors in Dimension B, which is simultaneously informed by Dimension A.
- Local Transitivity ($\alpha$): A tuning parameter that balances global structural equivalence with local transitivity. When $\alpha = 0$, the model focuses on global patterns; as $\alpha$ increases, it rewards nodes sharing common neighbors that are themselves highly similar.
The algorithm leverages the spectral properties of the bipartite adjacency matrix. To ensure numerical stability across iterations, the authors provide three normalization variants based on $L_1, L_2,$ and $L_\infty$ norms.
Experimental Evaluation
The method was rigorously tested using both synthetic and real-world datasets:
- Synthetic Benchmarks: The authors generated matrices with known block-diagonal structures, intentionally creating "unbalanced" versions (e.g., 3 row clusters vs. 5 column clusters) and introducing Gaussian noise ($\sigma$) to evaluate robustness.
- Biological Case Study: A network of 297 malaria Var genes and 803 amino acid substrings was analyzed. The goal was to correctly classify genes into Highly Variable Regions (HVRs), a task where ground truth is biologically established.
Key Results and Insights
The reflexive method demonstrated significant advantages over standard metrics like Jaccard, Cosine, and Pearson correlation:
- Accuracy in Noise: The $L_\infty$ variant, particularly with $\alpha > 0.5$, consistently outperformed baseline metrics in noisy synthetic environments. The $\alpha$ parameter effectively acts as a filter, distinguishing structural signals from random noise.
- Handling Asymmetry: Unlike rigid co-clustering, the reflexive approach allows each dimension to maintain its own independent similarity structure while still benefiting from the cross-dimensional feedback loop.
- Biological Validation: In the malaria dataset, the reflexive method was superior at identifying genes within the same HVR class, proving its utility for complex biological discovery.
- Computational Efficiency: While the underlying matrix operations are polynomial, the number of iterations required for convergence scales linearly with data size, ensuring viability for moderately large-scale applications.
Conclusion
Reflexive Regular Equivalence provides a robust, unsupervised alternative to traditional co-clustering for bipartite data. By allowing similarity to "reflect" between dimensions and incorporating a tunable local transitivity parameter, the method excels in identifying latent structures in noisy and asymmetric datasets. Future work will focus on formal convergence proofs and extending the framework to k-partite structures using tensor algebra.
Summary updated