Reflexive Regular Equivalence for Bipartite Data

Aaron Gerow, Mingyang Zhou, Stan Matwin, Feng Shi

TL;DR

This paper introduces Reflexive Regular Equivalence, an unsupervised method for measuring similarity in bipartite (two-mode) networks. By iteratively using similarity in one dimension to inform the other, the algorithm effectively handles noisy and asymmetric data, outperforming standard metrics like Jaccard or Cosine similarity in identifying latent structures.

What Problem Does This Paper Address?

Bipartite data—where connections exist between two distinct sets of entities (e.g., users and products, or genes and amino acid sequences)—is everywhere. Traditionally, researchers use co-clustering to find groups in this data. However, co-clustering relies on a heavy assumption: "co-similarity." This is the idea that if two rows are similar, they must be similar across the same columns, and vice versa.

In the real world, data is often "asymmetric" (e.g., three groups of users might all be interested in the same five groups of products in different ways) or riddled with noise. Existing methods often require you to guess the number of clusters beforehand or struggle when the data isn't binary. The authors sought a way to measure similarity that doesn't force a rigid clustering structure but instead lets the inherent "reflexive" relationship between the two dimensions reveal the true similarity.

Methods

The core of the paper is an iterative algorithm based on regular equivalence. In graph theory, two nodes are "regularly equivalent" if they are connected to neighbors who are themselves similar.

The authors extend this with two key innovations:

  1. Reflexivity: They define a feedback loop where similarity in Dimension A is calculated using the similarity of its neighbors in Dimension B, which in turn was calculated using Dimension A.
  2. Local Transitivity ($\alpha$): They introduce a free parameter, $\alpha$, which acts as a "tuning knob." When $\alpha = 0$, the model looks at global regular equivalence. As $\alpha$ increases, the model gives more weight to "local transitivity"—essentially rewarding nodes that share common neighbors who are themselves similar.

The algorithm uses spectral properties of the bipartite adjacency matrix and offers three normalization variants ($L_1, L_2,$ and $L_\infty$ norms) to ensure numerical stability and interpretability.

Datasets

The authors evaluated their method using two primary sources:

  • Synthetic Data: They generated semi-random matrices with known block-diagonal structures. They specifically created "unbalanced" versions (e.g., 3 clusters in one dimension vs. 5 in the other) and added varying levels of Gaussian noise ($\sigma$) to test robustness.
  • Malaria Var Genes: A real-world biological dataset consisting of 297 genes and 803 amino acid substrings. This is a sparse, binary bipartite network where the "ground truth" is the biological classification of genes into Highly Variable Regions (HVRs).

Key Insights and Ideas

  • The Power of the Feedback Loop: By allowing similarity to "reflect" back and forth between dimensions, the algorithm can uncover relationships that a single-pass pairwise metric (like Cosine similarity) would miss.
  • $\alpha$ as a Noise Filter: One of the most interesting findings is that increasing $\alpha$ (incorporating local structure) significantly boosts performance in noisy datasets. It helps the algorithm distinguish between meaningful structural patterns and random "links" created by noise.
  • Handling Asymmetry: Unlike co-clustering, which often forces a one-to-one mapping between row clusters and column clusters, this reflexive method allows each dimension to have its own independent similarity structure while still informing the other.
  • No "Cluster Guessing": The method produces a continuous similarity matrix rather than a hard partition, meaning researchers don't need to specify the number of clusters ($k$) upfront.

Key Results

  • Superior Accuracy: On synthetic noisy data, the $L_\infty$ variant of the reflexive method consistently outperformed Jaccard, Cosine, and Pearson correlation metrics, especially when $\alpha > 0.5$.
  • Biological Validation: In the malaria gene analysis, the reflexive method was significantly better at correctly pairing genes belonging to the same HVR class compared to standard pairwise measures.
  • Predictable Scaling: While the runtime scales polynomially (as expected for matrix operations), the number of iterations required for convergence scales linearly with the size of the data, making it viable for moderately large datasets.
  • Robustness: The method proved stable across different noise intensities, with the $L_1$ and $L_2$ norms showing particular resilience when noise levels were very high ($\sigma > 0.2$).

Limitations and Future Work

The authors note a few areas for further exploration:

  • Convergence Guarantees: While the algorithm converged consistently in experiments, a formal mathematical proof of convergence for all possible adjacency structures is still missing.
  • Degenerate Cases: Certain "degenerate" or poorly conditioned matrices might cause numerical instabilities, potentially requiring pre-conditioning steps.
  • Higher-Order Structures: The paper briefly mentions that this framework could be generalized to k-partite structures (networks with more than two types of nodes), which would involve complex tensor algebra.
  • Parameter Selection: While $\alpha$ is the only free parameter, a formal heuristic for choosing the "optimal" $\alpha$ for a given dataset (without knowing the ground truth) remains an open question.

Summary updated

Abstract

Bipartite data is common in data engineering and brings unique challenges, particularly when it comes to clustering tasks that impose on 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, $α$. 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.
BibTeX
@inproceedings{gerow2017reflexive,
  author = {Aaron Gerow and Mingyang Zhou and Stan Matwin and Feng Shi},
  title = {{Reflexive Regular Equivalence for Bipartite Data}},
  booktitle = {Canadian ai},
  year = {2017},
  doi = {10.1007/978-3-319-57351-9\_9},
}

Loading related content...

Figure