Barycentric subspace analysis of network-valued data

Elodie Maignant, Xavier Pennec, Alain Trouvé, Anna CalissanoarXiv 2025 · DOI · arXiv

Abstract

Certain data are naturally modeled by networks or weighted graphs, be they arterial networks or mobility networks. When there is no canonical labeling of the nodes across the dataset, we talk about unlabeled networks. In this paper, we focus on the question of dimensionality reduction for this type of data. More specifically, we address the issue of interpreting the feature subspace constructed by dimensionality reduction methods. Most existing methods for network-valued data are derived from principal component analysis (PCA) and therefore rely on subspaces generated by a set of vectors, which we identify as a major limitation in terms of interpretability. Instead, we propose to implement the method called barycentric subspace analysis (BSA), which relies on subspaces generated by a set of points. In order to provide a computationally feasible framework for BSA, we introduce a novel embedding for unlabeled networks where we replace their usual representation by equivalence classes of isomorphic networks with that by equivalence classes of cospectral networks. We then illustrate BSA on simulated and real-world datasets, and compare it to tangent PCA.

Introduction

Network-valued data, such as brain connectivity maps or transportation grids, are increasingly common. A significant challenge arises when these networks are "unlabeled," meaning there is no fixed correspondence between nodes across different samples. Traditional dimensionality reduction techniques like Principal Component Analysis (PCA) struggle here. PCA constructs subspaces from vectors; however, because graphs are discrete structures, linear combinations of these vectors often produce "franken-graphs"—mathematical constructs with negative edge weights or impossible topologies that lack physical meaning.

Methodology: From Vectors to Points

To resolve the interpretability issues of PCA, the authors propose Barycentric Subspace Analysis (BSA). Unlike PCA, which uses a basis of vectors, BSA defines a subspace through a set of reference points—in this case, actual, valid networks from the dataset.

Geometric representation of a barycentric subspace defined by reference points.

Spectral Graph Spaces

Computing distances between unlabeled graphs is typically a combinatorial nightmare involving graph permutations. The authors introduce a "Spectral Graph Space" by quotienting adjacency matrices by the continuous orthogonal group rather than the discrete permutation group. This relaxation identifies cospectral networks (those with the same eigenvalues). This transformation maps the complex graph space to a convex cone of sorted eigenvalues, making distance calculations and geodesic projections computationally efficient.

The authors specifically employ Sample-limited Convex BSA, which restricts the algorithm to selecting reference points from the existing dataset. This ensures that the "axes" of the reduced subspace are real, archetypal networks.

Results and Insights

The method was tested on simulated datasets and a real-world dataset of European airline route maps.

Interpretability and Archetypes

A key advantage of BSA is its ability to maintain structural integrity. While Tangent PCA might achieve low error, it often generates nonsensical intermediate states. In contrast, BSA uses actual graphs as anchors, making the resulting subspace intuitively understandable.

Visualization of graph projections onto a subspace defined by archetypal reference networks (a star graph and a complete graph).

In the airline dataset, BSA successfully mapped complex routing strategies onto a 1D subspace. The two reference networks identified by the algorithm represented distinct business models: the highly centralized "star" topology of national carriers (e.g., Swiss) versus the highly connected "meshed" topology of low-cost carriers (e.g., easyJet).

Conclusion

Barycentric Subspace Analysis provides a robust and interpretable framework for reducing the dimensionality of unlabeled network data. By leveraging spectral relaxations and point-based subspaces, it avoids the pitfalls of vector-based methods. Future research will focus on extending this framework to Laplacian matrices and applying it to larger-scale biological data like structural brain connectivity.

Summary updated

Abstract

Certain data are naturally modeled by networks or weighted graphs, be they arterial networks or mobility networks. When there is no canonical labeling of the nodes across the dataset, we talk about unlabeled networks. In this paper, we focus on the question of dimensionality reduction for this type of data. More specifically, we address the issue of interpreting the feature subspace constructed by dimensionality reduction methods. Most existing methods for network-valued data are derived from principal component analysis (PCA) and therefore rely on subspaces generated by a set of vectors, which we identify as a major limitation in terms of interpretability. Instead, we propose to implement the method called barycentric subspace analysis (BSA), which relies on subspaces generated by a set of points. In order to provide a computationally feasible framework for BSA, we introduce a novel embedding for unlabeled networks where we replace their usual representation by equivalence classes of isomorphic networks with that by equivalence classes of cospectral networks. We then illustrate BSA on simulated and real-world datasets, and compare it to tangent PCA.
BibTeX
@misc{maignant2025barycentric,
  author = {Elodie Maignant and Xavier Pennec and Alain Trouvé and Anna Calissano},
  title = {{Barycentric subspace analysis of network-valued data}},
  year = {2025},
  eprint = {2507.23559},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.23559},
  howpublished = {arXiv},
}
Figure