Effective Clustering for Large Multi-Relational Graphs

• URL: http://arxiv.org/abs/2508.17388v1
• Date: Sun, 24 Aug 2025 14:51:38 GMT
• Title: Effective Clustering for Large Multi-Relational Graphs
• Abstract summary: Multi-relational graphs (MRGs) are an expressive data structure for modeling diverse interactions/relations among real objects (i.e., nodes)<n>In this paper, we present DEMM and DEMM+, two effective MRGC approaches to address the limitations above.
• Score: 14.055388501740326
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-relational graphs (MRGs) are an expressive data structure for modeling diverse interactions/relations among real objects (i.e., nodes), which pervade extensive applications and scenarios. Given an MRG G with N nodes, partitioning the node set therein into K disjoint clusters (MRGC) is a fundamental task in analyzing MRGs, which has garnered considerable attention. However, the majority of existing solutions towards MRGC either yield severely compromised result quality by ineffective fusion of heterogeneous graph structures and attributes, or struggle to cope with sizable MRGs with millions of nodes and billions of edges due to the adoption of sophisticated and costly deep learning models. In this paper, we present DEMM and DEMM+, two effective MRGC approaches to address the limitations above. Specifically, our algorithms are built on novel two-stage optimization objectives, where the former seeks to derive high-caliber node feature vectors by optimizing the multi-relational Dirichlet energy specialized for MRGs, while the latter minimizes the Dirichlet energy of clustering results over the node affinity graph. In particular, DEMM+ achieves significantly higher scalability and efficiency over our based method DEMM through a suite of well-thought-out optimizations. Key technical contributions include (i) a highly efficient approximation solver for constructing node feature vectors, and (ii) a theoretically-grounded problem transformation with carefully-crafted techniques that enable linear-time clustering without explicitly materializing the NxN dense affinity matrix. Further, we extend DEMM+ to handle attribute-less MRGs through non-trivial adaptations. Extensive experiments, comparing DEMM+ against 20 baselines over 11 real MRGs, exhibit that DEMM+ is consistently superior in terms of clustering quality measured against ground-truth labels, while often being remarkably faster.

Related papers

• Beyond the Aggregation Dilemma: Prior-Retaining Decoupled Learning for Multimodal Graphs [69.56407708794845]
  MultimodalAttributed Graph Learning (MAGL) integrates node attributes with structural topology via graph aggregation.<n>As pretrained encoders evolve into Large Foundation Models (LFMs), the landscape of MAGL fundamentally shifts.<n>Under high-confidence LFM priors, mandatory aggregation introduces topological intrinsic noise that overwhelms discriminative signals.<n>We propose SUPRA (Shared-Unique Prior-Retaining Architecture), a decoupled dual-pathway paradigm.<n> SUPRA processes modality-specific features through topology-agnostics while capturing structural synergy via a lightweight shared GNN, with auxiliary deep supervision counteracting gradient starvation.
  arXiv  Detail & Related papers  (2026-05-23T17:42:25Z)
• Efficient Differentiable Causal Discovery via Reliable Super-Structure Learning [51.20606796019663]
  We propose ALVGL, a novel and general enhancement to the differentiable causal discovery pipeline.<n>ALVGL employs a sparse and low-rank decomposition to learn the precision matrix of the data.<n>We show that ALVGL not only achieves state-of-the-art accuracy but also significantly improves optimization efficiency.
  arXiv  Detail & Related papers  (2026-01-09T02:18:59Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  We propose textbfLighter-X, an efficient and modular framework that can be seamlessly integrated with existing GNN-based recommender architectures.<n>Our approach substantially reduces both parameter size and computational complexity while preserving the theoretical guarantees and empirical performance of the base models.<n>Experiments demonstrate that Lighter-X achieves comparable performance to baseline models with significantly fewer parameters.
  arXiv  Detail & Related papers  (2025-10-11T08:33:08Z)
• An Enhanced Model-based Approach for Short Text Clustering [58.60681789677676]
  Short text clustering has become increasingly important with the popularity of social media like Twitter, Google+, and Facebook.<n>Existing methods can be broadly categorized into two paradigms: topic model-based approaches and deep representation learning-based approaches.<n>We propose a collapsed Gibbs Sampling algorithm for the Dirichlet Multinomial Mixture model (GSDMM), which effectively handles the sparsity and high dimensionality of short texts.<n>Based on several aspects of GSDMM that warrant further refinement, we propose an improved approach, GSDMM+, designed to further optimize its performance.
  arXiv  Detail & Related papers  (2025-07-18T10:07:42Z)
• Neural Graduated Assignment for Maximum Common Edge Subgraphs [8.399955426185244]
  MCES problem is crucial challenge in domains such as biology and chemistry.<n>Traditional approaches, which include transformations into max-clique and search-based algorithms, suffer from scalability issues when dealing with larger instances.<n>This paper introduces Neural Graduated Assignment'' (NGA), a simple, scalable, unsupervised-training-based method that addresses these limitations.
  arXiv  Detail & Related papers  (2025-05-18T09:43:35Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  We propose ScaleGNN, a novel framework that adaptively fuses multi-hop node features for scalable and effective graph learning.<n>We show that ScaleGNN consistently outperforms state-of-the-art GNNs in both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-04-22T14:05:11Z)
• Reinforced Model Merging [53.84354455400038]
  We present an innovative framework termed Reinforced Model Merging (RMM), which encompasses an environment and agent tailored for merging tasks.<n>By utilizing data subsets during the evaluation process, we addressed the bottleneck in the reward feedback phase, thereby accelerating RMM by up to 100 times.
  arXiv  Detail & Related papers  (2025-03-27T08:52:41Z)
• Wavefunction optimization at the complete basis set limit with Multiwavelets and DMRG [0.0]
  We develop an algorithm integrating DMRG within the multiwavelet-based multiresolution analysis (MRA)<n>We adopt a pre-existing Lagrangian optimization algorithm for orbitals represented in the MRA domain and improve its computational efficiency.<n>We apply our method to small systems such as H2, He, HeH2, BeH2 and N2.
  arXiv  Detail & Related papers  (2025-03-13T18:59:03Z)
• Spectral Subspace Clustering for Attributed Graphs [3.974852803981998]
  Subspace clustering seeks to identify subspaces that segment a set of n data points into k (kn) groups. This paper presents two effective and efficient algorithms, S2CAG and M-S2CAG, for SCAG computation.
  arXiv  Detail & Related papers  (2024-11-17T13:22:15Z)
• MG-GNN: Multigrid Graph Neural Networks for Learning Multilevel Domain Decomposition Methods [0.0]
  We propose multigrid graph neural networks (MG-GNN) for learning optimized parameters in two-level domain decomposition methods. We show that MG-GNN outperforms popular hierarchical graph network architectures for this optimization.
  arXiv  Detail & Related papers  (2023-01-26T19:44:45Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Are Message Passing Neural Networks Really Helpful for Knowledge Graph Completion? [49.858038034580005]
  We show that simple models are able to achieve comparable performance to MPNNs. We show careful scoring function and loss function design has a much stronger influence on KGC model performance.
  arXiv  Detail & Related papers  (2022-05-21T18:14:52Z)
• MGAE: Masked Autoencoders for Self-Supervised Learning on Graphs [55.66953093401889]
  Masked graph autoencoder (MGAE) framework to perform effective learning on graph structure data. Taking insights from self-supervised learning, we randomly mask a large proportion of edges and try to reconstruct these missing edges during training.
  arXiv  Detail & Related papers  (2022-01-07T16:48:07Z)
• Effective and Scalable Clustering on Massive Attributed Graphs [25.161619807810215]
  We propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. ACMin consistently outperforms all competitors in terms of result quality measured against ground-truth labels, while being up to orders of magnitude faster. In particular, on the Microsoft Academic Knowledge Graph dataset with 265.2 million edges and 1.1 billion attribute values, ACMin outputs high-quality results for 5-AGC within 1.68 hours using a single CPU core, while none of the 11 competitors finish within 3 days.
  arXiv  Detail & Related papers  (2021-02-07T15:50:28Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  We propose a framework for deep-unfolding, where a general form of iterative algorithm induced deep-unfolding neural network (IAIDNN) is developed. An efficient IAIDNN based on the structure of the classic weighted minimum mean-square error (WMMSE) iterative algorithm is developed. We show that the proposed IAIDNN efficiently achieves the performance of the iterative WMMSE algorithm with reduced computational complexity.
  arXiv  Detail & Related papers  (2020-06-15T02:57:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.