Non-Negative Matrix Factorizations for Multiplex Network Analysis

Vladimir Gligorijevic, Yannis Panagakis, Stefanos Zafeiriou

TL;DR

This paper introduces NF-CCE (Network Fusion for Composite Community Extraction), a framework that identifies shared communities across "multiplex" networks—complex systems where the same set of nodes are connected by multiple types of relationships (layers). By using a two-step non-negative matrix factorization (NMF) process and subspace analysis on Grassmann manifolds, the authors successfully extract "composite" communities that are more robust to noise and more informative than those found in any single network layer.

What Problem Does This Paper Address?

Most network analysis focuses on "monoplex" networks, where only one type of interaction exists (e.g., a list of friends). However, real-world data is often multiplex: a social network might have layers for "friendship," "professional advice," and "co-working."

The challenge is "composite community detection": finding groups of nodes that belong together across all these modalities. Previous approaches often just averaged the layers together, which unfortunately averages the noise as well, leading to poor results. Other state-of-the-art methods struggle to balance "complementary information" (what one layer adds to another) with "noise" (irrelevant connections in a specific layer).

Methods

The authors propose a framework called NF-CCE, which operates in two distinct steps:

  1. Denoising (Step 1): Each network layer is factorized individually using NMF. This produces a low-dimensional "feature representation" for each layer, effectively filtering out local noise.
  2. Fusion (Step 2): These individual representations are fused into a single consensus representation ($H$) via collective factorization.

To find this consensus, the authors treat the low-dimensional subspaces of each layer as points on a Grassmann manifold. They minimize the "projection distance" between the individual layer subspaces and the shared consensus subspace.

The paper develops four specific algorithmic variants based on different NMF techniques:

  • CSNMF: Collective Symmetric NMF.
  • CPNMF: Collective Projective NMF.
  • CSNMTF: Collective Symmetric Non-negative Matrix Tri-Factorization.
  • CSsemi-NMTF: A "semi" version that allows for some negative entries in the factor matrices.

To optimize these, they use natural gradients, which ensure the resulting matrices remain orthonormal (a mathematical property that makes the clusters easier to interpret).

Datasets

The authors evaluated their methods on a massive variety of data:

  • Synthetic Networks: Designed to test how the algorithms handle varying levels of noise (SYNTH-N) and varying amounts of complementary information (SYNTH-C).
  • Bibliographic Data: CiteSeer and CoRA (citation and word-similarity layers).
  • Social/Communication Data: MIT Mobile Phone Data (location, bluetooth, calls) and a Law Partnership network.
  • Biological Networks: Human, Yeast, and Mouse protein-protein interaction and co-expression networks.
  • Economic/Brain Data: World Trade Networks (different products as layers) and Worm Brain Networks (different synapse types).

Key Insights and Ideas

  • The "Denoise-then-Fuse" Philosophy: Unlike previous methods that try to factorize everything at once, NF-CCE's two-step approach acts as a filter. By getting a "clean" version of each layer first, the final fusion is much more stable.
  • Subspaces as Geometry: By using Grassmann manifolds, the authors move away from simple matrix averaging and toward a geometric understanding of how different network layers relate to one another.
  • CPNMF for Discovery: One surprising insight was that the Projective NMF variant (CPNMF) was exceptionally good at picking up complementary information from very sparse layers, though it was more sensitive to noise than the other variants.
  • Averaging is Harmful: The results strongly suggest that the common practice of simply averaging adjacency matrices before clustering is one of the worst ways to handle multiplex data.

Key Results

  • Superior Accuracy: NF-CCE variants consistently outperformed state-of-the-art methods like PMM, SC-ML, and SNF across almost all real-world datasets in terms of Purity, Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI).
  • Robustness to Noise: In synthetic tests, while other methods' performance plummeted as noise increased, the NF-CCE methods (particularly CSNMF and CSNMTF) maintained high accuracy.
  • Biological Consistency: In the Human Biological Network (HBN), the communities found by NF-CCE had significantly higher "redundancy" (a measure of functional consistency based on Gene Ontology) than those found in any single layer. This proves that integrating layers reveals biological truths that are invisible in isolation.

Limitations and Future Work

  • Fixed Cluster Count: The algorithms require the number of clusters ($k$) to be specified in advance. In many real-world scenarios, $k$ is unknown.
  • Node Alignment: The model assumes that every layer contains the exact same set of nodes. Future work could extend this to "multilayer" networks where nodes might only exist in a subset of layers.
  • Computational Complexity: While efficient, the iterative nature of NMF and the calculation of natural gradients might face scaling challenges on truly massive networks (billions of edges) without further optimization.

Summary updated

Abstract

Networks have been a general tool for representing, analyzing, and modeling relational data arising in several domains. One of the most important aspect of network analysis is community detection or network clustering. Until recently, the major focus have been on discovering community structure in single (i.e., monoplex) networks. However, with the advent of relational data with multiple modalities, multiplex networks, i.e., networks composed of multiple layers representing different aspects of relations, have emerged. Consequently, community detection in multiplex network, i.e., detecting clusters of nodes shared by all layers, has become a new challenge. In this paper, we propose Network Fusion for Composite Community Extraction (NF-CCE), a new class of algorithms, based on four different non-negative matrix factorization models, capable of extracting composite communities in multiplex networks. Each algorithm works in two steps: first, it finds a non-negative, low-dimensional feature representation of each network layer; then, it fuses the feature representation of layers into a common non-negative, low-dimensional feature representation via collective factorization. The composite clusters are extracted from the common feature representation. We demonstrate the superior performance of our algorithms over the state-of-the-art methods on various types of multiplex networks, including biological, social, economic, citation, phone communication, and brain multiplex networks.
BibTeX
@article{gligorijevic2019non,
  author = {Vladimir Gligorijevic and Yannis Panagakis and Stefanos Zafeiriou},
  title = {{Non-Negative Matrix Factorizations for Multiplex Network Analysis}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2019},
  url = {https://openreview.net/forum?id=Ky5ntKeTsH},
}

Loading related content...

Figure