Spectral embedding and the latent geometry of multipartite networks

• URL: http://arxiv.org/abs/2202.03945v1
• Date: Tue, 8 Feb 2022 15:52:03 GMT
• Title: Spectral embedding and the latent geometry of multipartite networks
• Authors: Alexander Modell, Ian Gallagher, Joshua Cape, Patrick Rubin-Delanchy
• Abstract summary: Many networks are multipartite, meaning their nodes can be divided into partitions and nodes of the same partition are never connected. This paper demonstrates that the node representations obtained via spectral embedding live near partition-specific low-dimensional subspaces of a higher-dimensional ambient space. We propose a follow-on step after spectral embedding, to recover node representations in their intrinsic rather than ambient dimension.
• Score: 67.56499794542228
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral embedding finds vector representations of the nodes of a network, based on the eigenvectors of its adjacency or Laplacian matrix, and has found applications throughout the sciences. Many such networks are multipartite, meaning their nodes can be divided into partitions and nodes of the same partition are never connected. When the network is multipartite, this paper demonstrates that the node representations obtained via spectral embedding live near partition-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. Our method naturally generalizes bipartite spectral embedding, in which node representations are obtained by singular value decomposition of the biadjacency or bi-Laplacian matrix.

Related papers

• Implications of sparsity and high triangle density for graph representation learning [67.98498239263549]
  Recent work has shown that sparse graphs containing many triangles cannot be reproduced using a finite-dimensional representation of the nodes. Here, we show that such graphs can be reproduced using an infinite-dimensional inner product model, where the node representations lie on a low-dimensional manifold.
  arXiv  Detail & Related papers  (2022-10-27T09:15:15Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  Learning node representations benefits various downstream tasks in graph analysis such as community detection and node classification. We propose Geometric Graph Representation Learning (G2R) to learn node representations in an unsupervised manner. G2R maps nodes in distinct groups into different subspaces, while each subspace is compact and different subspaces are dispersed.
  arXiv  Detail & Related papers  (2022-02-13T07:46:24Z)
• Reflected entropy in random tensor networks [0.0]
  In holographic theories, the reflected entropy has been shown to be dual to the area of the entanglement wedge cross section. We analyze the important non-perturbative effects that smooth out the discontinuity in the reflected entropy across the Page phase transition. By summing over all such effects, we obtain the reflected entanglement spectrum analytically, which agrees well with numerical studies.
  arXiv  Detail & Related papers  (2021-12-16T18:59:00Z)
• Community detection for weighted bipartite networks [1.0965065178451106]
  citerohe2016co proposed co-Blockmodel (ScBM) as a tool for detecting community structure of binary bipartite graph data in network studies. Here, to model a weighted bipartite network, we introduce a Bipartite Distribution-Free model by releasing ScBM's distribution restriction. Our models do not require a specific distribution on generating elements of the adjacency matrix but only a block structure on the expected adjacency matrix.
  arXiv  Detail & Related papers  (2021-09-21T17:01:36Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Pseudo-Euclidean Attract-Repel Embeddings for Undirected Graphs [73.0261182389643]
  Dot product embeddings take a graph and construct vectors for nodes such that dot products between two vectors give the strength of the edge. We remove the transitivity assumption by embedding nodes into a pseudo-Euclidean space. Pseudo-Euclidean embeddings can compress networks efficiently, allow for multiple notions of nearest neighbors each with their own interpretation, and can be slotted' into existing models.
  arXiv  Detail & Related papers  (2021-06-17T17:23:56Z)
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel [5.156484100374058]
  A novel spectral clustering algorithm is proposed for community detection under the degree-corrected blockmodel. Results show improved performance over competing methods in representing computer networks.
  arXiv  Detail & Related papers  (2020-11-09T16:55:38Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.