A Spectral Framework for Tracking Communities in Evolving Networks

• URL: http://arxiv.org/abs/2412.07378v1
• Date: Tue, 10 Dec 2024 10:22:34 GMT
• Title: A Spectral Framework for Tracking Communities in Evolving Networks
• Authors: Jacob Hume, Laura Balzano,
• Abstract summary: We show improved approximation of the low-rank static community detection problem. We learn the Grassmann hierarchical community detection scheme which best fits the data.
• Score: 6.21540494241516
• License:
• Abstract: Discovering and tracking communities in time-varying networks is an important task in network science, motivated by applications in fields ranging from neuroscience to sociology. In this work, we characterize the celebrated family of spectral methods for static clustering in terms of the low-rank approximation of high-dimensional node embeddings. From this perspective, it becomes natural to view the evolving community detection problem as one of subspace tracking on the Grassmann manifold. While the resulting optimization problem is nonconvex, we adopt a block majorize-minimize Riemannian optimization scheme to learn the Grassmann geodesic which best fits the data. Our framework generalizes any static spectral community detection approach and leads to algorithms achieving favorable performance on synthetic and real temporal networks, including those that are weighted, signed, directed, mixed-membership, multiview, hierarchical, cocommunity-structured, bipartite, or some combination thereof. We demonstrate how to specifically cast a wide variety of methods into our framework, and demonstrate greatly improved dynamic community detection results in all cases.

Related papers

• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant [1.8606770727950463]
  We propose several GNN-based architectures to tackle the graph partitioning problem for Markov Chains described as kinetic networks. This approach aims to minimize how much a proposed partitioning changes the Kemeny constant. We show how simple GraphSAGE-based GNNs with linear layers can outperform much larger and more expressive attention-based models in this context.
  arXiv  Detail & Related papers  (2023-12-22T17:19:50Z)
• The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks [0.716879432974126]
  Community detection is an essential tool for unsupervised data exploration and revealing the organisational structure of networked systems. We consider the map equation, a popular information-theoretic objective function for unsupervised community detection, and express it in differentiable tensor form for gradient through descent. Our formulation turns the map equation compatible with any neural network architecture, enables end-to-end learning, incorporates node features, and chooses the optimal number of clusters automatically.
  arXiv  Detail & Related papers  (2023-10-02T12:32:18Z)
• Safe Multi-agent Learning via Trapping Regions [89.24858306636816]
  We apply the concept of trapping regions, known from qualitative theory of dynamical systems, to create safety sets in the joint strategy space for decentralized learning. We propose a binary partitioning algorithm for verification that candidate sets form trapping regions in systems with known learning dynamics, and a sampling algorithm for scenarios where learning dynamics are not known.
  arXiv  Detail & Related papers  (2023-02-27T14:47:52Z)
• MGTCOM: Community Detection in Multimodal Graphs [0.34376560669160383]
  MGTCOM is an end-to-end framework optimizing network embeddings, communities and the number of communities in tandem. Our method is competitive against state-of-the-art and performs well in inductive inference.
  arXiv  Detail & Related papers  (2022-11-10T16:11:03Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Consistency and Diversity induced Human Motion Segmentation [231.36289425663702]
  We propose a novel Consistency and Diversity induced human Motion (CDMS) algorithm. Our model factorizes the source and target data into distinct multi-layer feature spaces. A multi-mutual learning strategy is carried out to reduce the domain gap between the source and target data.
  arXiv  Detail & Related papers  (2022-02-10T06:23:56Z)
• Soft Hierarchical Graph Recurrent Networks for Many-Agent Partially Observable Environments [9.067091068256747]
  We propose a novel network structure called hierarchical graph recurrent network(HGRN) for multi-agent cooperation under partial observability. Based on the above technologies, we proposed a value-based MADRL algorithm called Soft-HGRN and its actor-critic variant named SAC-HRGN.
  arXiv  Detail & Related papers  (2021-09-05T09:51:25Z)
• A Comprehensive Survey on Community Detection with Deep Learning [93.40332347374712]
  A community reveals the features and connections of its members that are different from those in other communities in a network. This survey devises and proposes a new taxonomy covering different categories of the state-of-the-art methods. The main category, i.e., deep neural networks, is further divided into convolutional networks, graph attention networks, generative adversarial networks and autoencoders.
  arXiv  Detail & Related papers  (2021-05-26T14:37:07Z)
• A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network Representation Learning [52.83948119677194]
  We propose a multi-semantic metapath (MSM) model for large scale heterogeneous representation learning. Specifically, we generate multi-semantic metapath-based random walks to construct the heterogeneous neighborhood to handle the unbalanced distributions. We conduct systematical evaluations for the proposed framework on two challenging datasets: Amazon and Alibaba.
  arXiv  Detail & Related papers  (2020-07-19T22:50:20Z)
• Network Clustering Via Kernel-ARMA Modeling and the Grassmannian The Brain-Network Case [6.78543866474958]
  This paper introduces a clustering framework for networks with nodes annotated with time-series data. The framework addresses all types of network-clustering problems: state clustering, node clustering within states, and even subnetwork-state-sequence identification/tracking.
  arXiv  Detail & Related papers  (2020-02-18T19:48:38Z)

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.