Stochastic Deep Graph Clustering for Practical Group Formation

Junhyung Park, Hyungjin Kim, Seokho Ahn, Young-Duk SeoarXiv 2025 · DOI · arXiv

Abstract

DeepForm is a novel framework for Group Recommender Systems (GRSs) designed to automate the group formation process in real-time. Unlike traditional methods that rely on static group assignments or computationally expensive heuristics, DeepForm utilizes a lightweight Graph Convolutional Network (GCN) combined with stochastic cluster learning. This approach allows the system to dynamically adjust the number of groups ($K$) at inference time without retraining. Our evaluation shows that DeepForm significantly outperforms existing baselines in recommendation accuracy while maintaining near-constant computational efficiency across varying group sizes.

Introduction

While most research in Group Recommender Systems (GRSs) focuses on aggregating individual preferences for pre-existing groups, the challenge of forming those groups—the "who" of the recommendation—is often overlooked. Existing group formation techniques typically suffer from three critical limitations:

  1. Neglect of High-Order Relationships: Heuristic methods like Cosine similarity treat users as isolated vectors, failing to capture the complex "friend-of-a-friend" structures inherent in interaction graphs.
  2. Static Constraints: Many deep learning models are optimized for a fixed number of groups ($K$), requiring costly retraining if operational needs change.
  3. Efficiency Gaps: Real-world applications require group formation in milliseconds, a target that iterative optimization or traditional deep graph methods often fail to meet.

DeepForm addresses these issues by learning a scale-invariant embedding space that supports ad-hoc group formation at any granularity.

Methodology

The DeepForm architecture is divided into three primary modules that work in tandem to produce robust user embeddings suitable for clustering at any scale.

DeepForm Architecture Overview: From high-order modeling to stochastic cluster learning and inference.

1. High-Order Representation Modeling

To capture both structural connectivity and raw preference attributes, DeepForm employs a dual-stream encoder. A propagation-only GCN (inspired by LightGCN) operates on a user-user similarity graph to extract high-order structural signals. Simultaneously, an Autoencoder (AE) compresses the raw user-item rating matrix. These representations are aligned to ensure the final embeddings reflect both "who a user is" and "where they sit" in the social/interaction graph.

2. Stochastic Cluster Learning

The core innovation of DeepForm is its training regime. Rather than optimizing for a fixed $K$, the model randomly samples the number of clusters from a uniform distribution ($K \sim \text{Uniform}(2, K_{max})$) at each training iteration. This forces the model to learn embeddings that remain discriminative regardless of the desired cluster density.

3. Cluster Contrastive Learning

To stabilize learning under a varying number of clusters, the framework utilizes two contrastive losses:

  • Triplet Loss: Anchors users near their assigned cluster centers while maximizing distance from other clusters.
  • InfoNCE Loss: Enhances intra-cluster cohesion by maximizing similarity between members of the same provisional group.

At inference time, the model applies a standard K-Means algorithm to the learned embeddings for any requested $K$, requiring no further training.

Experimental Evaluation

DeepForm was evaluated on three real-world datasets: Amazon Baby, Amazon Clothing, and CAMRa2011. The Amazon datasets were used to simulate large-scale ad-hoc group formation, while CAMRa2011 provided explicit group labels for comparison.

Recommendation Accuracy

DeepForm consistently achieved top-tier performance across NDCG and Hit Rate (HR) metrics. Notably, on the CAMRa2011 dataset, groups formed by DeepForm achieved 32.57% higher recommendation accuracy than the "natural" groups defined in the dataset. This suggests that data-driven clustering can identify latent preference alignments that explicit social groupings may overlook.

Computational Efficiency

A key advantage of DeepForm is its inference speed. In tests on the Amazon Baby dataset, DeepForm was approximately 88.03% faster than the leading deep graph clustering baseline, SDCN.

Group Formation Efficiency: DeepForm maintains low, stable formation times as the number of groups (K) increases.

As shown in the efficiency analysis, while other deep methods exhibit increasing time complexity as $K$ grows, DeepForm’s overhead remains nearly flat. This is because the model avoids iterative optimization during the group formation phase, relying instead on the pre-trained, scale-invariant embeddings.

Discussion and Future Work

DeepForm demonstrates that granularity invariance is achievable in graph clustering. By training across a range of $K$ values, the system becomes highly flexible, capable of serving requests for a few large groups or hundreds of small groups instantly.

However, some limitations remain. The stochastic training process can increase initial training time, though this is offset by inference gains. Additionally, the model's reliance on interaction data means it still faces "cold-start" challenges for new users. Future research will explore integrating external metadata (e.g., user profiles) and distributed processing techniques to scale the system to hundreds of millions of nodes.

Conclusion

DeepForm represents a significant step toward practical, real-time group formation in recommender systems. By combining high-order graph modeling with stochastic learning, it provides a solution that is both more accurate than heuristics and more flexible than traditional deep learning models.

Summary updated

BibTeX
@misc{park2025stochastic,
  author = {Junhyung Park and Hyungjin Kim and Seokho Ahn and Young-Duk Seo},
  title = {{Stochastic Deep Graph Clustering for Practical Group Formation}},
  year = {2025},
  eprint = {2511.02879},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.02879},
}
Figure