Populations of Unlabeled Networks: Graph Space Geometry and Generalized Geodesic Principal Components

Overview

Sets of graphs arise in many different applications, from medicine to finance, from urban planning to social science. Analysing sets of graphs is far from trivial as they are strongly non Euclidean data type. There are two main sets of graphs:

• labelled: where there is the same sets of nodes across each observation;

• unlabelled: where there is no clear correspondence in the nodes across networks.

Unlabelled graphs poses high challenges from both the embedding prospective (which geometrical embedding is suitable for such graphs) and the statistical perspective (how can we extend basic tools to such embedding).

In the past years, scholars have been proposing different embedding strategies for unlabelled graphs. Among existing models: Ginestet et al. (2017) proposes a model where networks’ Laplacian matrices are smoothly injected into a sub-manifold of a Euclidean space; Simpson et al. (2013), Severn, Dryden, and Preston (2020) and Durante, Dunson, and Vogelstein (2017) face the problem of generating and performing tests on a population of networks; Lunagómez, Olhede, and Wolfe (2021) provide Bayesian modelling for discrete labeled graphs, and Chowdhury and Mémoli (2019) studies a metric space of networks up to weak isomorphism, which allows the grouping of similar nodes. In Calissano, Feragen, and Vantini (2023), we characterize geometrically the Graph Space quotient space introduced by Jain and Obermayer (2009) and we extended principal component analysis to sets of unlabelled graphs.

Graph Space

Consider \(G_1,\dots, G_k\) where each \(G_i=(N_i,E_i,a_i)\) sets of nodes \(N_i\), edges \(E_i\), and a real valued attribute function \(a_i :E_i \rightarrow \mathbb{R}\). Each graph can be described as a set of adjacency matrix \(x \in X=\mathbb{R}^{n\times n}\). We can embed unlabelled graphs in a quotient space \(X / T\) where \(T\) set of permutation matrices. Each graph is now represented by its equivalence class of permuted graphs: \[[x]=\{t^T x t: t\in T\}\]

Figure 1: Conceptual visualization of Graph Space.

By equipping the total space with a metric \((X,d_X)\) we can define a quotient metric on \(X / T\) as: \[d_{X/T}([x_1],[x_2])=min_{t\in T}d_X (t^T x_1 t, x_2)\] Such metric corresponds in finding the optimal candidate in the equivalence class which minimize the distance in the total space. The minimization problem is known as the Graph Matching problem, which is a broadly studied problem in optimization Conte et al. (2004) for a review). As we select \(d_X\) to be the Frobenius norm, we use the FAQ Graph matching Vogelstein et al. (2015).

Figure 2: Conceptual visualization of the distance in the Graph Space.

Generalized Geodesic Principal Components

Let’s move now to more complex estimators. To extend the Principal Component Analysis to Graph Space: (1) we firstly extend the concept of geodesic to Graph Space; (2) we define a way to align an equivalent class to a geodesic (i.e. optimal positioning).

Definition 1 (Generalized Geodesics):
Denote by \(\Gamma(X)\) the set of all straight lines (geodesics) in \(X\). Following Huckemann, Hotz, and Munk (2010), a curve \(\delta\) is a generalized geodesic on the Graph Space \(X/T\), if it is a projection of a straight line on \(X\): \[\begin{equation} \Gamma(X/T)=\{\delta=\pi \circ \gamma:\gamma\in\Gamma(X)\}. \end{equation}\] Where \(\pi: X\rightarrow X/T\) is the canonical quotient space projection.

Since Graph Space is not an inner product space, we define orthogonality as:

Definition 2: Two generalized geodesics \(\delta_1,\delta_2\in\Gamma(X/T)\) are orthogonal if they have representatives in \(\delta_1=\pi\circ\gamma_1,\delta_2=\pi\circ\gamma_2, \gamma_1,\gamma_2\in\Gamma(X)\) which are orthogonal \(<\gamma_1,\gamma_2>_X=0\).

In order to bridge computations in Graph Space \(X/T\) with computations in the total space \(X\), we introduce a concept of alignment in \(X\).

Definition 3 (Optimal position):
Given \(\tilde{x} \in X\) and \(t \in T\), the point \(t^T \tilde{x} t\) is in if \[ d_X(t^T \tilde{x}t,x)= d_{X/T}([\tilde{x}],[x]). \] That is, the equivalence class \([\tilde{x}] \in X/T\) contains (at least) one point \(t^T \tilde{x} t \in [\tilde{x}]\) which has minimal distance to \(x\), and this point is in optimal position to \(x\). Next, consider \([x] \in X/T\), \(t \in T\) and \(\delta\) a generalized geodesic in \(X/T\) with representative \(\gamma\in \Gamma(X)\). The graph representative \(t^T x t\in X\) is in optimal position to \(\gamma\in\Gamma(X)\) if \[d_X(t^T x t ,\gamma)=d_{X/T}([x],\delta).\]

Having concepts of generalized geodesic, optimal position and orthogonality, we now define a set of geodesic principal components:

Definition 4: Consider the canonical projection of the Graph Space \(\pi \colon X \rightarrow X/T\) of \(X\) and consider a set \(\{[x_1],\dots, [x_k]\} \subset X/T\) of graphs, \([x]\in X/T\), and \(\delta \in \Gamma(X/T)\). The Generalized Geodesic Principal Components (GGPCs) for the set \(\{[x_1],\dots, [x_k]\}\) are defined as:

• The first generalized geodesic principal component \(\delta_1 \in \Gamma(X/T)\) is the generalized geodesic minimizing the sum of squared residuals: \[\begin{equation}\label{eq:wrtdelta} \delta_1 = \underset{\delta \in \Gamma(X/T)}{\operatorname{argmin}} \sum_{i=1}^{k}{(d_{X/T}^2([x_i],\delta))} \end{equation}\]

• The second generalized geodesic principal component \(\delta_2 \in \Gamma(X/T)\) minimizes (2) over all \(\delta \in \Gamma(X/T)\), having at least one point in common with \(\delta_1\) and being orthogonal to \(\delta_1\) at all points in common with \(\delta_1\).

• The point \(\mu\in X/T\) is called Principal Component Mean if it minimizes \[\begin{equation}\label{eq:wrtpoint} \sum_{i=1}^{k}{(d_{X/T}^2([x_i],[\mu])^2)} \end{equation}\] where \([\mu]\) only runs over points \(\tilde{x}\) in common with \(\delta_1\) and \(\delta_2\).

• The \(j^{th}\) generalized geodesic principal component is a \(\delta_j \in \Gamma(X/T)\) if it minimizes (2) over all generalized geodesics that meet orthogonally \(\delta_1,\dots, \delta_{j-1}\) and cross \(\mu\).
  

Conceptualized in Figure 4, the actual estimation of the GPCA in Graph Space is done via AAC: (1) Randomly pick some candidates in the equivalence classes; (2) estimate the standard PCA in \(X\); (3) Select new optimally aligned candidates wrt the current PCA estimation.

Figure 4: Conceptual visualization of the AAC for the estimation of the first generalized geodesic principal component.

The AAC converge in finite time and to a local minima as proven in Theorem 2 and 3 Calissano, Feragen, and Vantini (2023). All the algorithms and the framework is implemeted in the geomstats python package.

An Example

As an intuitive visual example with real data and associated vectors attributes, we subsample \(20\) cases of the letter A from the well known hand written letters dataset Kersting et al. (2016), Riesen and Bunke (2008). As shown in the left panel of Figure 5, every network has node attributes consisting of the node’s \(x\)– and \(y\)-coordinates, and binary \((0/1\)) edge attributes indicating whether nodes are connected by lines.

Figure 5: Left: A datum extracted from the \(A\) dataset. Every unlabelled node has a bi-dimensional real valued attribute, while every edge has a \({0,1}\) attribute. The Fréchet mean. Right: Visualization of the GGPCs. \({0.1,0.25,0.5,0.75,0.9}\) quantile of the projected scores are shown for the first three GGPCs.

Conclusion

Graph Space is an intuitive embedding for sets of graphs with unlabelled sets of nodes. Even if its geometry is far from trivial, we can easily estimate intrinsic statistics by using the Align All and Compute algorithm. In Calissano, Feragen, and Vantini (2023) we detailed the geometry of Graph Space, we define the AAC algorithm and the Generalized Geodesic Principal Components for a set of graphs. Regression with unlabelled network outputs is also available in Calissano, Feragen, and Vantini (2022). All the framework is available as part of the geomstats python package Miolane et al. (2020).

References