Spectral embedding and the latent geometry of multipartite networks

Alexander Modell, Ian Gallagher, Joshua Cape, Patrick Rubin‐DelanchyarXiv 2022 · DOI · arXiv

Abstract

Spectral embedding finds vector representations of the nodes of a network, based on the eigenvectors of a properly constructed matrix, and has found applications throughout science and technology. Many networks are multipartite, meaning that they contain nodes of fundamentally different types, e.g. drugs, diseases and proteins, and edges are only observed between nodes of different types. When the network is multipartite, this paper demonstrates that the node representations obtained via spectral embedding lie near type-specific low-dimensional subspaces of a higher-dimensional ambient space. For this reason we propose a follow-on step after spectral embedding, to recover node representations in their intrinsic rather than ambient dimension, proving uniform consistency under a low-rank, inhomogeneous random graph model. We demonstrate the performance of our procedure on a large 6-partite biomedical network relevant for drug discovery.

Introduction

Graph embedding is a standard tool for transforming nodes in a network into points in a vector space, facilitating downstream tasks like clustering or link prediction. However, most existing methods rely on the "homophily" principle, assuming that similar nodes are more likely to connect. This assumption is fundamentally violated in multipartite networks, such as medical databases linking drugs, diseases, and proteins. In these networks, nodes of the same type do not connect to each other, resulting in an adjacency matrix with large blocks of zeros. Standard spectral embedding techniques often ignore these structural constraints, forcing all node types into a single "ambient" high-dimensional space, which may not accurately reflect their true underlying geometry.

The Geometry of Multipartite Networks

The core insight of this work is that the latent positions of a single node type in a multipartite graph are "totally isotropic" with respect to an indefinite inner product. Geometrically, this means that when nodes are embedded into an ambient space, they do not form simple clusters but instead align along type-specific, low-dimensional linear subspaces.

The latent geometry of multipartite networks: estimated node positions (right) align along subspaces corresponding to the true latent structure (left).

As shown in the figure above, while the global embedding might place nodes in a high-dimensional "ambient" space, the nodes of each type (represented by different colors) are concentrated near specific lines or rays emanating from the origin. This mismatch between the ambient representation and the true, lower-dimensional intrinsic geometry is a key challenge addressed by this paper.

Methodology: Multipartite Adjacency Spectral Embedding (MASE)

To address this geometric structure, the authors propose Multipartite Adjacency Spectral Embedding (MASE), a two-stage process:

  1. Global Embedding: A standard Adjacency Spectral Embedding (ASE) is performed on the entire network, placing all nodes in a high-dimensional ambient space $\mathbb{R}^r$.
  2. Type-Specific Projection: Recognizing the subspace structure, the method applies an uncentered Principal Component Analysis (PCA) to each node type separately. This projects the nodes into their lower-dimensional "intrinsic" space $\mathbb{R}^{r_k}$.
The two-step MASE process: Global embedding (left) places nodes in an ambient space where they align along subspaces. Type-specific projection (right) recovers their intrinsic low-dimensional representations.

The paper provides a rigorous statistical foundation for this approach, proving uniform consistency under a "multipartite bilinear random graph model." This ensures that as the network grows, the estimated positions converge to the true latent positions of the nodes.

Results on Biomedical Discovery Networks

The MASE procedure was evaluated on a massive 6-partite biomedical network comprising drugs, diseases, targets, pathways, variant locations, and haplotypes.

The "elbow method" for dimension selection confirmed the subspace hypothesis: while the ambient dimension was 214, the intrinsic dimensions for specific types were significantly lower (e.g., Haplotypes required only 19 dimensions). This reduction effectively removes noise, leading to highly coherent functional clusters. For instance, one drug cluster identified by the method contained almost exclusively hypnotics and sedatives, while a pathway cluster grouped various cancer-related pathways with high precision.

Furthermore, the authors demonstrate that embedding the entire multipartite graph is superior to analyzing individual bipartite slices. Communities that appear indistinguishable in a single bipartite view often become clearly separated when additional node types and their connections are integrated into the global embedding.

Conclusion

This research highlights that the geometry of multipartite networks is fundamentally different from that of unipartite graphs. By accounting for type-specific subspaces, the MASE algorithm provides a more accurate and powerful framework for network analysis. Future work may address the challenges of optimal dimension selection and the performance of spectral methods in extremely sparse regimes.

Summary updated

Abstract

Spectral embedding finds vector representations of the nodes of a network, based on the eigenvectors of a properly constructed matrix, and has found applications throughout science and technology. Many networks are multipartite, meaning that they contain nodes of fundamentally different types, e.g. drugs, diseases and proteins, and edges are only observed between nodes of different types. When the network is multipartite, this paper demonstrates that the node representations obtained via spectral embedding lie near type-specific low-dimensional subspaces of a higher-dimensional ambient space. For this reason we propose a follow-on step after spectral embedding, to recover node representations in their intrinsic rather than ambient dimension, proving uniform consistency under a low-rank, inhomogeneous random graph model. We demonstrate the performance of our procedure on a large 6-partite biomedical network relevant for drug discovery.
BibTeX
@misc{modell2022spectral,
  author = {Alexander Modell and Ian Gallagher and Joshua Cape and Patrick Rubin‐Delanchy},
  title = {{Spectral embedding and the latent geometry of multipartite networks}},
  year = {2022},
  eprint = {2202.03945},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.03945},
}
Figure