Abstract
In network science, identifying overlapping communities is a critical task. Most existing models rely on the "Community-to-Link" assumption, where community memberships dictate link formation. This paper introduces HNMF (Homophily-based Non-negative Matrix Factorization), a model that treats homophily as a bidirectional relationship. By combining traditional Matrix Factorization with network embedding techniques, HNMF captures both how communities generate links and how links define community profiles. Experimental results on large-scale datasets like Amazon and DBLP demonstrate that HNMF significantly outperforms state-of-the-art baselines in both accuracy and modularity.
Introduction
Communities in real-world networks—such as social circles, professional affiliations, or product categories—frequently overlap. A central challenge in community detection is accurately modeling these overlaps. Standard Matrix Factorization (MF) approaches typically adopt a "Community-to-Link" perspective: if two nodes share many communities, they are likely to be linked.
However, this ignores the "Link-to-Community" perspective, which suggests that a node's community membership can be inferred from its neighbors. The authors argue that homophily is symmetric. To support this, they analyzed the Amazon and DBLP datasets, finding that linked nodes share significantly more communities (6.7 on average for Amazon) compared to random pairs (0.17). This empirical evidence strongly supports the need for a bidirectional model.
Methodology: The HNMF Model
The proposed HNMF model unifies two distinct perspectives into a single objective function:
- Community-to-Link (Pairwise Preference): This component assumes that nodes sharing more communities have a higher probability of being linked. It uses a pairwise objective function to maximize the likelihood of observed links based on community overlap.
- Link-to-Community (Network Embedding): Inspired by the Skip-Gram model (e.g., DeepWalk), this component treats a node’s neighbors as its "context." It learns community representations such that a node's profile can effectively predict the profiles of its neighbors.
To ensure scalability for networks with millions of nodes, the authors implemented the model using Asynchronous Stochastic Gradient Descent, a lock-free approach that enables efficient parallel training. The full algorithm is detailed below.
Experimental Results
The authors evaluated HNMF against several baselines, including BigCLAM and PNMF, using both large-scale networks and small benchmark datasets.
Large-Scale Performance
On the Amazon product co-purchasing network (335k nodes), HNMF achieved an F1 score of 0.122, nearly tripling the performance of BigCLAM (0.044) and PNMF (0.042). Similar improvements were observed on the DBLP scientific co-authorship network (317k nodes).
Modularity and Scalability
On Newman’s benchmark datasets (e.g., Dolphins, Les Misérables, American College Football), HNMF consistently achieved the highest modularity scores, outperforming every baseline. Furthermore, the model demonstrated strong scalability, converging in approximately 4 to 6 hours on a standard 24-core server for the largest datasets.
Conclusion
HNMF successfully bridges the gap between Matrix Factorization and network embedding for community detection. By modeling the bidirectional homophily effect, it provides a more robust representation of overlapping groups. While the model requires a threshold for final community assignments and careful tuning of the homophily coefficient ($\beta$), its performance gains make it a powerful tool for large-scale network analysis. Future work could extend this framework to directed or weighted networks.
Summary updated