Gradient flow-based modularity maximization for community detection in multiplex networks

Kai Bergermann, Martin Stoll

TL;DR

Researchers have developed two new methods, MPBTV and DGFM3, that transform the complex combinatorial problem of community detection in multiplex networks into efficient "gradient flows." By leveraging a graph-based Merriman–Bence–Osher (MBO) scheme and spectral truncation, these methods achieve community detection results competitive with state-of-the-art algorithms while being up to five orders of magnitude faster on large-scale networks.

What Problem Does This Paper Address?

In network science, "communities" are groups of nodes more densely connected to each other than to the rest of the network. While well-understood for single-layer graphs, real-world systems are often multiplex: they consist of multiple layers representing different types of relationships between the same set of entities (e.g., a social network where layers represent Facebook, Twitter, and LinkedIn connections).

Detecting communities in these networks typically involves maximizing a quality metric called modularity. However, modularity maximization is an NP-complete problem. Existing heuristic solvers, like the popular GenLouvain, struggle with scalability as the number of nodes and layers grows. The authors aim to bridge this gap by providing a mathematically elegant and computationally efficient alternative that scales linearly with the number of node-layer pairs.

Methods

The authors propose two approaches based on gradient flows—mathematical "paths" that move toward the optimal value of a function:

  1. MPBTV (Multiplex Balanced Total Variation): This method is based on a surprising equivalence: maximizing multiplex modularity is mathematically identical to minimizing a "balanced total variation" functional. The authors use a Ginzburg–Landau-type energy functional to approximate this, which leads to an Allen–Cahn-type differential equation.
  2. DGFM3 (Direct Gradient Flow Multiplex Modularity Maximization): This method skips the equivalence and directly formulates a gradient flow to maximize the modularity functional.

To solve the resulting matrix-valued ordinary differential equations (ODEs), they employ a graph MBO scheme. This involves two alternating steps:

  • Diffusion: A linear step solved efficiently using truncated eigendecompositions. Instead of computing the full matrix exponential, they only use the top $k$ eigenvalues and eigenvectors, which captures the most important structural information of the network.
  • Thresholding: A non-linear step that "snaps" nodes back into discrete community assignments.

Datasets

The methods were evaluated on a diverse set of real-world multiplex networks:

  • Small-scale: Genetic and social networks including Danio rerio (zebrafish), Florentine families, Hepatitis C, Human herpes 4, and Oryctolagus (rabbit).
  • Medium-scale (with ground truth): 3sources, BBC, BBCS, Citeseer, Cora, WebKB, and Wikipedia. These include feature-vector data where layers represent different data sources.
  • Image Data: A custom-labeled test image (293 × 520 pixels) where layers represent RGB color channels and spatial (xy) coordinates.

Key Insights and Ideas

  • The Modularity-TV Link: The proof that multiplex modularity maximization is equivalent to balanced total variation minimization is a major theoretical "aha" moment. It allows researchers to apply mature tools from image processing and PDEs to network science.
  • Spectral Truncation is Enough: The paper demonstrates that you don't need the full spectrum of the network's Laplacian or modularity matrix. Using just a few dozen eigenvectors (the "truncated" part) is sufficient to find high-quality communities, which is the secret to their massive speedup.
  • MBO for Modularity: While MBO schemes are common in semi-supervised learning (where some labels are known), this paper successfully adapts them for unsupervised community detection by using the modularity matrix itself to drive the diffusion.

Key Results

  • Speed: The most striking result is the runtime. For a large multiplex network derived from an image ($nL \approx 300,000$), the proposed methods were approximately 100,000 times faster than the function-handle version of GenLouvain.
  • Scalability: As shown in Figure 3, while traditional matrix-based methods hit memory limits or exhibit quadratic time scaling, MPBTV and DGFM3 scale almost linearly with the network size.
Comparison of offline runtimes (eigenvalue computations) and runtimes per iteration for different methods as the network size (nL) increases.
  • Accuracy: On the image segmentation task, MPBTV achieved a classification accuracy of 0.976 and an NMI score of 0.909, outperforming several established competitors.

The original test image (a), ground truth labels (b), and the community detection results for the RGB layer (c) and xy layer (d) using MPBTV. MPBTV community detection result for the two layers of the multiplex network corresponding to the test image.

Limitations and Future Work

  • Small Communities: The authors acknowledge that their methods sometimes struggle to identify very small communities accurately, a common trade-off when using spectral approximations.
  • Hyperparameter Tuning: The number of eigenvalues ($k$) and the number of communities ($n_c$) are hyperparameters that currently require some manual tuning or grid searching.
  • Future Directions: The authors suggest extending these gradient flow techniques to semi-supervised cases (incorporating prior knowledge) and applying them to even higher-dimensional data like hyperspectral imaging.

Summary updated

Abstract

We propose two methods for the unsupervised detection of communities in undirected multiplex networks. These networks consist of multiple layers that record different relationships between the same entities or incorporate data from different sources. Both methods are formulated as gradient flows of suitable energy functionals: the first (MPBTV) builds on the minimization of a balanced total variation functional, which we show to be equivalent to multiplex modularity maximization, while the second (DGFM3) directly maximizes multiplex modularity. The resulting nonlinear matrix-valued ordinary differential equations (ODEs) are solved efficiently by a graph Merriman-Bence-Osher (MBO) scheme. Key to the efficiency is the approximate integration of the discrete linear differential operators by truncated eigendecompositions in the matrix exponential function. Numerical experiments on several real-world multiplex networks show that our methods are competitive with the state of the art with respect to various metrics. Their major benefit is a significant reduction of computational complexity leading to runtimes that are orders of magnitude faster for large multiplex networks.This article is part of the theme issue 'Partial differential equations in data science'.
BibTeX
@inproceedings{bergermann2025gradient,
  author = {Kai Bergermann and Martin Stoll},
  title = {{Gradient flow-based modularity maximization for community detection in multiplex networks}},
  booktitle = {Philosophical},
  year = {2025},
  doi = {10.1098/rsta.2024.0244},
}

Loading related content...

Figure