Abstract
Cyberspace hosts abundant interactions between users and different kinds of objects, and their relations are often encapsulated as bipartite graphs. Detecting user community in such heterogeneous graphs is an essential task to uncover user information needs and to further enhance recommendation performance. While several main cyber domains carry high-quality graphs, unfortunately, most others can be quite sparse. However, as users may appear in multiple domains (graphs), their high-quality activities in the main domains can supply community detection in the sparse ones, e.g., user behaviors on Google can help thousands of applications to locate his/her local community when s/he uses Google ID to login those applications. In this paper, our model, Pairwise Cross-graph Community Detection (PCCD), is proposed to cope with the sparse graph problem by involving external graph knowledge to learn user pairwise community closeness instead of detecting direct communities. Particularly in our model, to avoid taking excessive propagated information, a two-level filtering module is utilized to select the most informative connections through both community and node level filters. Subsequently, a Community Recurrent Unit (CRU) is designed to estimate pairwise user community closeness. Extensive experiments on two real-world graph datasets validate our model against several strong alternatives. Supplementary experiments also validate its robustness on graphs with varied sparsity scales.
Introduction
Community detection—the process of grouping users based on shared interests or behaviors—is a cornerstone of modern recommendation systems. Traditional algorithms, such as spectral clustering or modularity-based methods, typically rely on dense, well-connected bipartite graphs to function effectively. However, a significant challenge in the digital ecosystem is the "graph cold start" problem. While "giant" platforms like Amazon or Google possess high-quality, dense graphs, thousands of smaller applications suffer from extreme data sparseness.
As illustrated in Figure 1, the core idea of this research is to leverage the fact that many users maintain a consistent identity across multiple domains. By propagating the rich community structure from a "main" domain (e.g., online shopping), the model can organize users in a sparse "target" domain (e.g., a cooking app) even when their local activity is minimal.
Methodology: The PCCD Model
The proposed Pairwise Cross-graph Community Detection (PCCD) model shifts the objective from direct cluster assignment to a pairwise ranking task. By training the model to predict the relative closeness of user triplets $\langle u_i, u_j, u_k \rangle$, the authors effectively augment the available signal, turning a sparse unsupervised problem into a dense supervised ranking task.
Key Components
- Two-Level Filtering: To prevent irrelevant noise from the main graph from polluting the target domain, PCCD employs both Community-level and Node-level filters. These use attention mechanisms to select only the most pertinent connections for a specific user.
- Community Recurrent Unit (CRU): This specialized neural architecture maintains a "community memory." It estimates the strength of a user's belonging to various latent communities and updates these representations dynamically.
- Pairwise Learning: The model predicts whether user $u_j$ is closer to $u_i$ than user $u_k$. This approach provides $O(N^3)$ potential training signals from $N$ users, significantly mitigating the impact of sparsity.
Experimental Evaluation
The model was evaluated using real-world data from the Alibaba ecosystem, utilizing a dense online shopping platform as the main graph and two sparse targets: a news portal (SH-NE) and a cooking website (SH-CO).
PCCD demonstrated significant superiority over state-of-the-art baselines like node2vec and WMW. On the SH-CO dataset, PCCD achieved an Accuracy of 0.774 and an F1-score of 0.775, outperforming the best baseline by over 10%. Furthermore, ablation studies revealed that the Node-level filter is the most critical component, as its removal led to a performance drop of up to 26%. This underscores the necessity of fine-grained, selective information propagation in cross-domain tasks.
Conclusion and Future Work
PCCD effectively addresses the data sparseness problem by reframing community detection as a cross-graph pairwise learning task. It successfully predicts community closeness even for users with zero behavior in the target graph, provided they have a history in the main domain. Future research will focus on making the initial community labeling process end-to-end and scaling the architecture to handle multiple simultaneous graphs and heterogeneous features like textual profiles.
Summary updated