Learning low-rank latent mesoscale structures in networks

Hanbaek Lyu, Yacoub H. Kureh, Joshua Vendrow, Mason A. PorterarXiv 2021 · OpenReview

Abstract

It is common to use networks to encode the architecture of interactions between entities in complex systems in the physical, biological, social, and information sciences. To study the large-scale behavior of complex systems, it is useful to examine mesoscale structures in networks as building blocks that influence such behavior. We present a new approach for describing low-rank mesoscale structures in networks, and we illustrate our approach using several synthetic network models and empirical friendship, collaboration, and protein--protein interaction (PPI) networks. We find that these networks possess a relatively small number of latent motifs' that together can successfully approximate most subgraphs of a network at a fixed mesoscale. We use an algorithm fornetwork dictionary learning' (NDL), which combines a network-sampling method and nonnegative matrix factorization, to learn the latent motifs of a given network. The ability to encode a network using a set of latent motifs has a wide variety of applications to network-analysis tasks, such as comparison, denoising, and edge inference. Additionally, using a new network denoising and reconstruction (NDR) algorithm, we demonstrate how to denoise a corrupted network by using only the latent motifs that one learns directly from the corrupted network.

Introduction

In network science, analysis typically focuses on either the microscale (individual nodes and edges) or the macroscale (global properties like degree distributions). However, the mesoscale—the intermediate structure of subgraphs—is often where the most significant "behavioral" building blocks of a complex system reside. While "motifs" (statistically overrepresented subgraphs) have been studied extensively, utilizing them as fundamental building blocks to reconstruct or denoise a global network has remained a challenge.

This research addresses the problem of finding a "low-rank" representation of these mesoscale structures. By identifying a compressed "dictionary" of patterns, or latent motifs, we can faithfully rebuild, clean, or compare networks. This approach suggests that real-world networks are fundamentally low-rank at the mesoscale, meaning a small number of motifs can approximate the vast majority of local structures.

Methodology: NDL and NDR

The proposed framework consists of two primary algorithms: Network Dictionary Learning (NDL) and Network Denoising and Reconstruction (NDR).

Network Dictionary Learning (NDL)

NDL identifies a set of "latent motifs" by sampling the network and applying matrix factorization.

  • Sampling: The algorithm uses Markov-chain Monte Carlo (MCMC) to sample $k$-paths (sequences of $k$ distinct, connected nodes). The authors demonstrate that sampling paths is superior to sampling walks, as walks can introduce spurious hub structures in the learned motifs.
  • Learning: Online Non-negative Matrix Factorization (NMF) is applied to these samples, decomposing the subgraphs into a dictionary of basis elements (the latent motifs) and corresponding coefficients.

Network Denoising and Reconstruction (NDR)

The NDR algorithm utilizes the learned dictionary to generate a "best linear approximation" of the network. By averaging motif-based approximations across many overlapping subgraphs, it produces a weighted reconstruction. In this reconstruction, edge weights represent the confidence that an edge is a true part of the network's underlying structure rather than noise.

Overview of the NDL and NDR framework for network denoising and reconstruction.

A critical technical component is the "thinning parameter" ($\xi$), which allows the algorithm to distinguish between true edges and additive noise (false edges) by de-emphasizing the edges that define the sampling path itself.

Results and Interpretability

The approach was validated across 16 diverse networks, including real-world Facebook friendship networks, Protein-Protein Interaction (PPI) networks, and various synthetic models (Erdős–Rényi, Barabási–Albert, etc.).

Latent Motifs as Structural Signatures

A key finding is that the mesoscale is indeed low-rank. For instance, just 25 motifs can reconstruct the Caltech Facebook network with over 80% accuracy. Unlike "black-box" graph embeddings, NDL produces visualizable motifs that reveal distinct social or biological architectures.

Latent motifs learned from various real-world and synthetic networks.

As shown in the figure above, motifs from different networks exhibit characteristic shapes: Caltech’s motifs are dense and community-heavy, while UCLA’s are significantly sparser. These motifs serve as a structural signature for the network.

Performance in Denoising and Inference

In tasks involving the detection of "anomalous" edges (additive noise), the NDL+NDR approach significantly outperformed classical methods like the Jaccard Index and Adamic-Adar, as well as modern embedding techniques like DeepWalk and node2vec. On the Coronavirus PPI network, the method achieved an impressive AUC of 0.94–0.97. Furthermore, as the number of motifs ($r$) increases, the global properties of the reconstructed networks (such as degree distributions and clustering coefficients) converge toward those of the original "true" network.

Conclusion and Future Directions

This work demonstrates that complex networks can be effectively represented through a small dictionary of latent mesoscale motifs. This low-rank approximation provides a powerful tool for denoising, reconstruction, and cross-network comparison.

However, some limitations remain. The parameter $k$ (motif size) acts as a scale parameter; while $k=21$ proved effective for many tasks, larger values increase computational complexity. Additionally, the learned dictionaries are not necessarily unique. Future research may extend this framework to temporal networks and multilayer networks, which involve multiple types of concurrent interactions.

Summary updated

Abstract

It is common to use networks to encode the architecture of interactions between entities in complex systems in the physical, biological, social, and information sciences. To study the large-scale behavior of complex systems, it is useful to examine mesoscale structures in networks as building blocks that influence such behavior. We present a new approach for describing low-rank mesoscale structures in networks, and we illustrate our approach using several synthetic network models and empirical friendship, collaboration, and protein--protein interaction (PPI) networks. We find that these networks possess a relatively small number of `latent motifs' that together can successfully approximate most subgraphs of a network at a fixed mesoscale. We use an algorithm for `network dictionary learning' (NDL), which combines a network-sampling method and nonnegative matrix factorization, to learn the latent motifs of a given network. The ability to encode a network using a set of latent motifs has a wide variety of applications to network-analysis tasks, such as comparison, denoising, and edge inference. Additionally, using a new network denoising and reconstruction (NDR) algorithm, we demonstrate how to denoise a corrupted network by using only the latent motifs that one learns directly from the corrupted network.
BibTeX
@misc{lyu2021learning,
  author = {Hanbaek Lyu and Yacoub H. Kureh and Joshua Vendrow and Mason A. Porter},
  title = {{Learning low-rank latent mesoscale structures in networks}},
  year = {2021},
  eprint = {2102.06984},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.06984},
}
Figure