Abstract
Bipartite graphs are essential for modeling interactions between distinct entity sets, such as users and items. While self-supervised learning has advanced graph representation, traditional instance-wise contrastive methods often suffer from cluster-level errors, where semantically similar but unconnected nodes are treated as negatives. We present COIN (Co-Cluster Infomax), a framework that maximizes mutual information between "co-clusters" to capture high-level structural patterns. COIN achieves state-of-the-art performance across link prediction, recommendation, and co-clustering tasks.
Introduction
Bipartite graphs represent relationships between two disjoint sets of nodes, $U$ and $V$. Learning effective embeddings for these nodes is critical for downstream applications like recommendation systems. Most existing methods rely on instance-wise contrastive learning, which aims to pull connected nodes together and push unconnected nodes apart. However, this approach often ignores the underlying group structure. For example, two users with similar interests might not be connected to the same items, yet instance-wise methods might treat them as negative pairs, introducing noise into the embedding space and confusing the model.
The COIN Framework
COIN addresses these limitations by shifting focus from individual nodes to cluster-level interactions. The framework consists of three primary modules:
- Shared Graph Encoder: A bipartite Graph Neural Network (GNN) that aggregates local neighborhood information to generate initial node embeddings.
- Dual Cluster Networks: Two neural networks, $C_U$ and $C_V$, map node embeddings to soft cluster assignment probabilities.
- Co-Cluster Infomax Objective: Instead of using unstable neural estimators, COIN directly calculates the mutual information $I(K; L)$ between the cluster distributions of the two node sets.
By maximizing this mutual information alongside a standard instance-wise loss (InfoNCE), COIN captures both local connectivity and global categorical structures. The authors provide a mathematical proof showing that maximizing the mutual information of the clusters effectively acts as a lower bound for maximizing the mutual information of the node embeddings themselves.
Experimental Evaluation
The researchers evaluated COIN on six public datasets across three tasks: link prediction (Wikipedia), recommendation (MovieLens 100K and 10M), and co-clustering (WebKB, Wisconsin, and IMDB).
Key Results
COIN consistently outperforms both specialized bipartite models (e.g., BiGI) and general graph methods (e.g., DeepWalk, NGCF).
- Link Prediction: On the Wikipedia dataset, COIN achieved an AUC-ROC of 95.30%, surpassing the previous state-of-the-art.
- Recommendation: COIN showed significant gains in recommendation accuracy. On the ML-100K dataset, it achieved an F1@10 of 24.78%, a notable improvement over baselines like BiGI (23.36%) and NGCF (21.64%).
- Co-Clustering: COIN achieved the highest Normalized Mutual Information (NMI) scores across all tested datasets, proving its effectiveness at discovering latent categories within bipartite data.
Discussion and Conclusion
A key innovation of COIN is the direct, differentiable calculation of mutual information, which provides a more stable training signal than variational estimators like MINE. Furthermore, the use of a Multi-Layer Perceptron (MLP) for measuring node similarity was found to be superior to standard cosine similarity, likely due to its ability to model non-linear relationships.
While COIN is sensitive to the predefined number of clusters, its ability to align global structural patterns makes it a robust tool for bipartite graph representation learning. Future research may extend this framework to more complex structures, such as hypergraphs or multiplex bipartite graphs.
Summary updated