PaperlayerView exact revision on arXiv

Source-linked AI summary

Degree-Corrected Joint Matrix Factorization for Multilayer Community Detection

Alexandra Dache, Manon Rustin, Arnaud Vandaele, Nicolas Gillis

arXiv:2610.01361v1cs.SIcs.LG

TL;DR

Multilayer community detection must identify shared groups despite differences in connectivity and node degrees across layers. mFROST jointly factorizes the layer graphs, sharing community assignments while allowing layer-specific sociability and interactions. Experiments report strong, competitive performance across diverse synthetic and real-world settings.

  • Problem

    Multilayer community detection seeks shared communities across layers even though connectivity patterns and node degree distributions can vary substantially.

    Source: §I · p. 1

  • Method

    mFROST jointly factorizes layer graphs with shared community assignments and layer-specific node sociabilities and community interactions.

    Source: §V · pp. 10–11

  • Results

    Experiments show consistently strong mFROST performance across diverse community interactions and degree distributions, including settings with isolated nodes.

    Source: §V · p. 11

  • Takeaways & Limitations

    mFROST remains competitive across varied structural conditions, including when degree heterogeneity occurs within and across layers.

    Source: §V · p. 11

    The current orthogonality constraints enforce disjoint communities; supporting overlapping communities would require replacing them.

    Source: §V · p. 11

Abstract

from arXiv · show

Multilayer networks allow the modeling of interactions between the same entities across different contexts, such as temporal observations, varying settings, or interactions of different types. The goal of community detection in multilayer networks is to identify groups of nodes exhibiting similar connectivity patterns, which may vary across layers. We propose a method based on a joint nonnegative symmetric matrix trifactorization for community detection in multilayer networks, where each graph is approximated by a nonnegative symmetric matrix trifactorization. Our approach enforces constraints on the factor matrices so that communities are disjoint and shared across layers, while allowing each layer to have its own connectivity patterns and node degrees. This flexibility enables the model to capture both local and global structural variations across layers. We also develop an algorithm to efficiently solve this problem. We evaluate multilayer community detection methods using the multilayer degree-corrected stochastic block model (MDCBM), a flexible framework for generating realistic multilayer graphs with heterogeneous degrees and varying connectivity patterns. Experiments show that our method reliably detects communities across diverse regimes, whereas existing state-of-the-art approaches are often limited by restrictive structural assumptions.

I. INTRODUCTION

Multilayer community detection seeks shared groups of nodes across graphs representing different contexts, even when their connectivity patterns and degree distributions vary by layer. mFROST uses joint nonnegative symmetric matrix trifactorization to model shared memberships alongside layer-specific sociability and interactions.

I. INTRODUCTION

  • Multilayer networks consist of graphs over the same nodes, each associated with a context or interaction type.Examples include social, transportation, and biological systems.Source: §I · p. 1
  • Communities are defined by similar patterns of interaction with all communities, not only by dense within-community connections.This broader definition follows the stochastic block model perspective.Source: §I · p. 1
  • A shared community structure can summarize multiple layer-specific views, but connectivity patterns and node degree distributions may vary substantially across layers.The passage relates this setting to multi-view clustering, where views are jointly clustered to uncover common latent structure.Source: §I · p. 1
  • Flattening can lose layer-specific structure, while aggregation assumes each layer independently provides a reliable community structure; direct methods partition all layers jointly.Aggregation may be sensitive to layers with weak or noisy community structure.Source: §I · p. 1
  • mFROST jointly estimates shared community memberships, node sociabilities, and layer-specific interaction matrices, and performs well across diverse network conditions.The method is evaluated on synthetic and real-world networks and is described as robust relative to methods with stronger structural assumptions.Source: §I · p. 2

II. NMF BACKGROUND

The section introduces nonnegative matrix factorization and constrained variants for representing data and graph structure. Orthogonality can yield hard cluster assignments, while a community-interaction matrix extends symmetric factorization to interactions between communities.

II. NMF BACKGROUND

  • NMF represents a nonnegative matrix as a product of lower-rank nonnegative factors, with coefficients that indicate each data point’s contributions from latent components.The factor matrix contains basis vectors, while the other factor contains the corresponding coefficients.Source: §II · p. 2
  • Imposing HH⊤ = Ir in ONMF makes each data point belong to at most one component, yielding an explicit hard clustering.The constrained formulation is closely related to k-means clustering.Source: §II · p. 2
  • SymNMF approximates a symmetric matrix as ZZ⊤, but works best without interactions between communities and can produce only positive semidefinite matrices.For undirected graphs, preserving symmetry can improve the representation.Source: §II · p. 2
  • TrisymNMF adds a nonnegative matrix θ to ZZ⊤, allowing θ to represent interactions between communities.OtrisymNMF additionally imposes Z⊤Z = Ir to obtain disjoint communities.Source: §II · p. 2

III. OUR MODEL

The model approximates each layer’s adjacency matrix with a nonnegative symmetric trifactorization. It shares node community assignments across layers while allowing sociability and community interactions to vary by layer.

III. OUR MODEL

  • Each layer’s adjacency matrix is approximated by a nonnegative symmetric trifactorization, with Z_l encoding memberships and θ_l encoding community interactions.θ_l is not constrained to be diagonal, so communities can interact.Source: §III · p. 2
  • The nonnegativity and orthogonality constraints make each row of Z_l contain at most one nonzero entry, supporting interpretable memberships.The value at that entry quantifies the node’s sociability, and θ_l quantifies interaction strength between communities.Source: §III · p. 2
  • A shared binary matrix V fixes each node’s community across layers, while diagonal D_l allows its sociability to vary by layer.A zero sociability value lets the model represent a node isolated in a particular layer.Source: §III · p. 3
  • The optimization minimizes the sum of squared Frobenius reconstruction errors across layers, with shared V identifying the communities.V also determines the possible positions of nonzero entries in each Z_l.Source: §III · p. 3

A. mFROST: Our Algorithm for (1)

mFROST jointly updates shared community assignments while allowing node values and interaction matrices to vary by layer. Its alternating procedure uses candidate community updates, consensus-based initialization, and multiple restarts to seek low reconstruction error.

A. mFROST: Our Algorithm for (1)

  • The algorithm alternates updates of Z_l and θ_l, with each θ_l update computed for fixed Z_l.The matrices Z_l are initialized first; θ_l is then updated while Z_l is held fixed, and vice versa.Source: A. mFROST: Our Algorithm for (1) · p. 3
  • mFROST updates each node’s rows across all layers together, choosing one shared community assignment while optimizing layer-specific values.For each candidate community, it evaluates the resulting total reconstruction error across layers.Source: A. mFROST: Our Algorithm for (1) · pp. 3–4
  • For each node-community candidate, the algorithm solves a one-dimensional problem and selects a nonnegative value that minimizes the fourth-order polynomial.It uses Cardano’s method to find extrema, then chooses the candidate yielding the largest reconstruction-error decrease.Source: A. mFROST: Our Algorithm for (1) · pp. 3–4
  • Because the objective is nonnegative and each update decreases or preserves it, the sequence of objective values converges.The method uses multiple initializations and retains the solution with the smallest reconstruction error because the problem is non-convex.Source: A. mFROST: Our Algorithm for (1) · pp. 3–4
  • Initialization combines independent layer partitions into a consensus partition, then sets layer-specific nonzero membership values proportionally to node degrees.The consensus partition determines the support of each Z_l; the initialization procedure relies on randomness.Source: A. mFROST: Our Algorithm for (1) · p. 4
  • Each iteration scales as O(r Σ_l nnz(A_l)), with memory complexity O(Lnr + Lr^2 + Σ_l nnz(A_l)).The implementation stores layer-specific node values and one shared community assignment vector.Source: A. mFROST: Our Algorithm for (1) · p. 4

B. Related Work

Related approaches to multilayer community detection include spectral, probabilistic, and matrix-factorization methods. Their assumptions about shared representations, degree variation, and community structure differ from the layer-specific factors used in mFROST.

B. Related Work

  • Spectral methods embed nodes using graph matrices and then cluster; multilayer variants average adjacency matrices or combine layer embeddings into a shared representation.Degree normalization is used in DC-MASE to address node-specific degree variation.Source: B. Related Work · p. 5
  • Probabilistic approaches infer community structure under stochastic block models using methods such as expectation-maximization, variational inference, or Bayesian MCMC.The MDCBM allows shared communities with layer-specific block connectivity matrices and node degree parameters.Source: B. Related Work · p. 5
  • Matrix-factorization approaches vary in whether they share factors across layers, constrain them to be orthogonal, or permit layer-specific interactions.Some shared-Z formulations constrain relative node sociability across layers, while OtrisymNMF-based CSNMTF permits layer-specific interactions.Source: B. Related Work · pp. 5–6
  • Semi-supervised joint NMF targets assortative communities by integrating motif-based prior information before jointly decomposing layer matrices.Its communities are inferred from a common basis matrix.Source: B. Related Work · p. 6

IV. EXPERIMENTS

The evaluation compares mFROST with spectral, Bayesian, linked-matrix, and NMF-based baselines on synthetic MDCBM networks and real-world multilayer datasets. Baseline implementations and most experimental settings follow the protocol used in.

IV. EXPERIMENTS

  • Experiments use synthetic networks generated from the MDCBM and multilayer networks constructed from real-world datasets.The comparison includes baseline methods evaluated in and CSNMTF.Source: §IV · p. 6
  • The comparison includes four spectral methods, graph-tool Bayesian inference, OLMF, and CSNMTF [17].The spectral methods use spherical clustering; graph-tool uses multilayer degree-corrected stochastic block model inference with a fixed community count.Source: §IV · p. 6
  • Baseline methods generally use the default settings and protocol of, while CSNMTF uses adapted public code and matched restart counts.Synthetic runs use three restarts, while other runs use ten by default; experiments were performed on a laptop.Source: §IV · p. 6

A. Synthetic MDCBM

On synthetic MDCBM networks, mFROST performs especially well when connectivity matrices differ across layers or degree patterns alternate. Its performance also compares favorably with baselines across most tested sparsity settings.

A. Synthetic MDCBM

  • The first simulation varies layer count across connectivity and degree regimes on 150-node, three-community MDCBM graphs, averaging results over 100 samples.Degree regimes include heterogeneous but shared degrees, independently generated layer degrees, and alternating high/low degrees; average degree is about 10.Source: A. Synthetic MDCBM · p. 6
  • mFROST achieves the best performance when connectivity matrices differ across layers or degree distributions alternate.With identical connectivity matrices and non-alternating degrees, Sum A is better for L < 10, after which the difference is marginal.Source: A. Synthetic MDCBM · pp. 6–7
  • At L = 15, mFROST reaches error < 10^-3 versus L = 40 for DC-MASE under identical connectivity matrices and different degree corrections.Across tested scenarios, only mFROST and DC-MASE consistently improve with more layers until perfect clustering; mFROST outperforms DC-MASE.Source: A. Synthetic MDCBM · p. 7, Figure 2 · p. 7
  • The sparsity simulation fixes L = 20 and varies expected edge density from 2/150 to 24/150.CSNMTF uses α = 0.1, selected for the lowest error across tested configurations of the initial synthetic experiment.Source: A. Synthetic MDCBM · pp. 6–7
  • As edge density increases, mFROST, DC-MASE, and graph-tool improve; mFROST outperforms DC-MASE and graph-tool except when degrees differ across layers.In that exception, graph-tool performs slightly better, with the difference most pronounced in very sparse settings with identical connectivity matrices and marginal when matrices differ.Source: A. Synthetic MDCBM · p. 7

B. Real-world datasets

The real-world evaluation spans multilayer networks and multi-view datasets, using NMI and ARI to compare methods against ground-truth communities. mFROST performs competitively across datasets, with results varying by dataset and metric.

B. Real-world datasets

  • The evaluation distinguishes real multilayer networks, where ground-truth communities may be unavailable or metadata may not reflect observed structure, from labeled multi-view datasets.The latter are expected to exhibit assortative structures, while real multilayer networks can provide less controlled tests of meaningful group recovery.Source: B. Real-world datasets · p. 7
  • AUCS represents five online and offline relationship layers among 61 employees, while HS11 records daily contacts over four days with school classes as ground truth.AUCS uses research groups as labels; HS11 treats teachers as a separate group.Source: B. Real-world datasets · pp. 7–8
  • Cora uses citation and cosine-similarity layers for 1,662 papers, with research-area labels and an unweighted, undirected graph setting.Its similarity layer connects each paper to its 20 nearest neighbors; mFROST also supports weighted graphs, left for future work here.Source: B. Real-world datasets · p. 8
  • Caltech forms a six-layer network from six image-feature representations, with 9,144 images across 102 categories and 2.6 million edges.Each layer is a 50-nearest-neighbor graph; across the datasets, community sizes range from balanced to highly unbalanced.Source: B. Real-world datasets · p. 8
  • NMI measures normalized information shared between partitions, while ARI measures pairwise community agreement adjusted for chance; higher values indicate greater agreement.A value of 1 on either metric corresponds to identical partitions.Source: B. Real-world datasets · pp. 8–9
  • mFROST achieves the highest NMI and ARI on HS11, the highest ARI on Caltech, and second place on both metrics on AUCS.Graph-tool is the strongest competitor overall, particularly on Cora; OLMF runs out of memory on Caltech.Source: Table II · p. 9, B. Real-world datasets · p. 9

C. Ablation study

The ablation compares mFROST with a variant that shares Z across layers, with and without a regularized normalized Laplacian. mFROST performs especially better when node degrees differ across layers, while the gap narrows as layer count increases.

C. Ablation study

  • mFROST-Zshared uses one Z across layers and optimizes it against total reconstruction error, with or without the regularized normalized Laplacian.The comparison tests shared versus layer-varying memberships and the effect of Laplacian regularization.Source: C. Ablation study · p. 9
  • In the same-degree scenario, mFROST achieves results similar to mFROST-Zshared, even though the latter is the more constrained variant.Using the regularized Laplacian slightly improves mFROST-Zshared in this scenario.Source: C. Ablation study · p. 9
  • When node degrees differ across layers, mFROST clearly outperforms both shared-Z variants, though the gap narrows as the number of layers increases.The passage attributes the narrowing to independently drawn degree parameters averaging toward greater stability as L grows.Source: Figure 4 · p. 9, C. Ablation study · p. 9

D. Empirical stability and convergence

Across real-world datasets, mFROST reaches its stopping criterion in at most 20 iterations, with small NMI variation across restarts. Its proposed initialization generally converges faster and yields higher mean NMI than random initialization.

D. Empirical stability and convergence

  • The proposed initialization generally yields faster convergence, higher mean NMI, and lower variability across restarts than random initialization.Relative error and NMI stabilize after relatively few iterations across AUCS, HS11, Cora, and Caltech.Source: Figure 5 · p. 10, D. Empirical stability and convergence · p. 10
  • The algorithm stops when the change in relative error between consecutive iterations falls below δ = 10^-5.The stopping rule uses reconstruction error, not NMI.Source: D. Empirical stability and convergence · p. 10
  • Across 10 restarts, mFROST's mean NMI is close to the value reported when retaining the run with the lowest reconstruction error.The authors attribute the similar-quality solutions despite randomized initialization to smoothed separable NMF providing a data-driven starting point.Source: D. Empirical stability and convergence · p. 10
  • At most 20 iterations are needed to reach the stopping criterion across tested cases, and Caltech's 2.6 million edges and 102 communities take about 4 minutes per restart.Runtime is consistent with scaling approximately with the number of communities times the number of edges; NMI standard deviation across restarts stays below 5%.Source: Table III · p. 10, D. Empirical stability and convergence · p. 10

V. CONCLUSION

mFROST jointly estimates a common community structure while allowing community interactions and node sociability to vary across layers. Experiments show strong performance across diverse network settings, and future work would extend the method to partially observed networks and overlapping communities.

V. CONCLUSION

  • The joint trifactorization recovers common community assignments while allowing community interactions and node sociability to vary across layers.Its relationship with the multilayer degree-corrected stochastic block model provides an interpretable representation of memberships, degree heterogeneity, and interactions between communities.Source: §V · p. 10
  • Layer-specific sociability lets nodes’ relative sociability within each community vary across layers while preserving common assignments, accounting for degree heterogeneity within and across layers.The ablation study finds that modeling layer-specific sociabilities improves performance when node degrees vary across layers without compromising performance when they remain the same.Source: §V · pp. 10–11
  • mFROST performs consistently strongly on synthetic and real-world multilayer networks across diverse community interactions and degree distributions, including settings with isolated nodes.Other state-of-the-art methods perform well in some configurations but lose substantial accuracy in others; mFROST remains competitive across these settings.Source: §V · p. 11
  • The block coordinate descent algorithm yields a nonincreasing objective and converges rapidly empirically, with per-iteration cost linear in the product of edge count and community count.The initialization strategy further improves convergence speed and reduces variability in clustering quality across restarts.Source: §V · p. 11
  • Future work could extend mFROST to partially observed networks and to overlapping communities, which would require replacing the orthogonality constraints that enforce disjoint communities.For partially observed networks, a proposed extension restricts reconstruction error to observed entries; shared assignments could let other layers contribute to clustering partially observed nodes.Source: §V · p. 11
Loading 2610.01361v1…