Revisiting Dynamic Graph Clustering via Matrix Factorization

• URL: http://arxiv.org/abs/2502.06117v1
• Date: Mon, 10 Feb 2025 02:57:46 GMT
• Title: Revisiting Dynamic Graph Clustering via Matrix Factorization
• Authors: Dongyuan Li, Satoshi Kosugi, Ying Zhang, Manabu Okumura, Feng Xia, Renhe Jiang,
• Abstract summary: Matrix factorization-based methods are promising approaches for this task. They tend to lack robustness and are vulnerable to real-world noisy data. We propose temporal separated matrix factorization, bi-clustering regularization, and selective embedding updating.
• Score: 26.290080380814196
• License:
• Abstract: Dynamic graph clustering aims to detect and track time-varying clusters in dynamic graphs, revealing the evolutionary mechanisms of complex real-world dynamic systems. Matrix factorization-based methods are promising approaches for this task; however, these methods often struggle with scalability and can be time-consuming when applied to large-scale dynamic graphs. Moreover, they tend to lack robustness and are vulnerable to real-world noisy data. To address these issues, we make three key contributions. First, to improve scalability, we propose temporal separated matrix factorization, where a single matrix is divided into multiple smaller matrices for independent factorization, resulting in faster computation. Second, to improve robustness, we introduce bi-clustering regularization, which jointly optimizes graph embedding and clustering, thereby filtering out noisy features from the graph embeddings. Third, to further enhance effectiveness and efficiency, we propose selective embedding updating, where we update only the embeddings of dynamic nodes while the embeddings of static nodes are fixed among different timestamps. Experimental results on six synthetic and five real-world benchmarks demonstrate the scalability, robustness and effectiveness of our proposed method. Source code is available at https://github.com/Clearloveyuan/DyG-MF.

Related papers

• LOCAL: Learning with Orientation Matrix to Infer Causal Structure from Time Series Data [13.390666123493409]
  LOCAL is a highly efficient, easy-to-implement, and constraint-free method for recovering dynamic causal structures. ACML generates causal masks using learnable priority vectors and the Gumbel-Sigmoid function. DGPL transforms causal learning into decomposed matrix products, capturing the dynamic causal structure of high-dimensional data.
  arXiv  Detail & Related papers  (2024-10-25T10:48:41Z)
• Modularity aided consistent attributed graph clustering via coarsening [6.522020196906943]
  Graph clustering is an important unsupervised learning technique for partitioning graphs with attributes and detecting communities. We propose a loss function incorporating log-determinant, smoothness, and modularity components using a block majorization-minimization technique. Our algorithm seamlessly integrates graph neural networks (GNNs) and variational graph autoencoders (VGAEs) to learn enhanced node features and deliver exceptional clustering performance.
  arXiv  Detail & Related papers  (2024-07-09T10:42:19Z)
• TimeGraphs: Graph-based Temporal Reasoning [64.18083371645956]
  TimeGraphs is a novel approach that characterizes dynamic interactions as a hierarchical temporal graph. Our approach models the interactions using a compact graph-based representation, enabling adaptive reasoning across diverse time scales. We evaluate TimeGraphs on multiple datasets with complex, dynamic agent interactions, including a football simulator, the Resistance game, and the MOMA human activity dataset.
  arXiv  Detail & Related papers  (2024-01-06T06:26:49Z)
• Unified and Dynamic Graph for Temporal Character Grouping in Long Videos [31.192044026127032]
  Video temporal character grouping locates appearing moments of major characters within a video according to their identities. Recent works have evolved from unsupervised clustering to graph-based supervised clustering. We present a unified and dynamic graph (UniDG) framework for temporal character grouping.
  arXiv  Detail & Related papers  (2023-08-27T13:22:55Z)
• Deep Temporal Graph Clustering [77.02070768950145]
  We propose a general framework for deep Temporal Graph Clustering (GC) GC introduces deep clustering techniques to suit the interaction sequence-based batch-processing pattern of temporal graphs. Our framework can effectively improve the performance of existing temporal graph learning methods.
  arXiv  Detail & Related papers  (2023-05-18T06:17:50Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)
• Semi-Supervised Clustering via Dynamic Graph Structure Learning [12.687613487964088]
  Most existing semi-supervised graph-based clustering methods exploit the supervisory information by refining the affinity matrix or constraining the low-dimensional representations of data points. We propose a novel dynamic graph learning method for semi-supervised graph clustering.
  arXiv  Detail & Related papers  (2022-09-06T14:05:31Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
  Bilinear pooling achieves great success in fine-grained visual recognition (FGVC) Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features. We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
  arXiv  Detail & Related papers  (2020-03-30T08:40:35Z)

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.