Characterizing Distances of Networks on the Tensor Manifold
Bipul Islam Ji Liu Romeil Sandhu








Stony Brook University, Stony Brook NY 08544, USA,

romeil.sandhu@stonybrook.edu



Characterizing Distances of Networks on the Tensor Manifold
    Bipul Islam1, Ji Liu 1, Romeil Sandhu1
    Received: December 30, 2023/ Accepted: December 30, 2023
============================================================




At the core of understanding dynamical systems is the ability to maintain and control the systems behavior that includes notions of robustness, heterogeneity, and/or regime-shift detection.  Recently, to explore such functional properties, a convenient representation has been to model such dynamical systems as a weighted graph consisting of a finite, but very large number of interacting agents. This said, there exists very limited relevant statistical theory that is able cope with real-life data, i.e., how does perform analysis and/or statistics over a “family” of networks as opposed to a specific network or network-to-network variation.  Here, we are interested in the analysis of network families whereby each network represents a “point” on an underlying statistical manifold.  To do so, we explore the Riemannian structure of the tensor manifold developed by Pennec previously applied to Diffusion Tensor Imaging (DTI) towards the problem of network analysis. In particular, while this note focuses on Pennec definition of “geodesics” amongst a family of networks, we show how it lays the foundation for future work for developing measures of network robustness for regime-shift detection.  We conclude with experiments highlighting the proposed distance on synthetic networks and an application towards biological (stem-cell) systems.





§ INTRODUCTION

Notions of robustness, heterogeneity, and phase changes are ubiquitous concepts employed in understanding complex dynamical systems with a variety of applications <cit.>. This is seen in Figure <ref>A. While recent advancements in network analysis has arisen through the usage of spectral techniques <cit.>, expander graphs <cit.>, percolation theory <cit.>, information theoretic approaches <cit.>, scale-free networks <cit.>, and a myriad of graph measures reliant on the underlying discrete graph space (e.g., degree distribution, shortest path, centrality <cit.>), such measures rarely incorporate the underlying dynamics in its construction. To this end, we have previously developed fundamental relationships between network functionality <cit.> and certain topological and geometric properties of the corresponding graph <cit.>. In particular, recent work of ours has shown the geometric notion of curvature (a measure of “flatness”) is positively correlated with a system's robustness or its ability to adapt to dynamic changes <cit.>.  This can be seen in Figure <ref>B.

Here, we are interested in expounding upon previous work <cit.> in order to exploit distances (and eventually statistics, robustness) over a family of networks. In particular, as vector-valued networks are becoming increasingly important, we believe such a framework may be of interest to broader complex network community.  To do so, we are interested in studying geometry of networks as a dynamical system that evolves over time in which each given network or observation may represent a “point” (encoded by some matrix-based positive definite model) on an underlying Riemannian manifold.  From this, we are interested in applying the framework of Pennec <cit.> to define geodesics such that distances between “points” (networks) in a given family can be measured as seen in Figure <ref>.  This said, we note significant related work on employing statistical analysis for Riemannian manifolds has focused on directional statistics, statistics on shape spaces, as well as specific manifolds - we refer the reader <cit.> and references therein.   While these methods are mostly extrinsic whereby one embeds the manifold in an ambient Euclidean space, we are interested in studying intrinsic Riemannian metrics that can be naturally applied to the network setting without restrictions on the network topology. As such, the remainder of the present paper is outlined as follows: In the next section, we provide preliminaries regarding the framework by Pennec <cit.> primarily used for DTI imaging.  From this, we then show how this framework is a natural towards networks with a particular remarks on how we can begin on constructing robustness over network families.  Section 4 presents preliminary results on synthetic and biological data and Section 5 concludes with future work.



§ PRELIMINARIES

This section focuses on developing a measures of distance amongst networks in the context of developing measures of network robustness (future work).


 §.§ Geodesics on the Network Manifold

Let us consider a dynamical system that evolves over time and whose information is encapsulated by a positive definite matrix (tensor). In this regard, it is well-known that the space of tensors is not a vector space, but instead forms a Riemannian manifold M <cit.>.  In particular, we will leverage the theory of symmetric spaces which has been extensively studied since the seminal work of Nomizu <cit.>; a comprehensive work on tensor manifolds can be found in <cit.>. Riemannian manifolds are endowed with a metric that smoothly assign to each point ρ∈ M an inner product on 𝒯_ρ, the tangent space to M at ρ.  More formally, let us denote Υ and Υ^+ and  as the set of all Hermitian matrices and the cone of positive-definite matrices, respectively. We consider the following:

    Λ_+ := {ρ∈Υ^+    |   tr(ρ)=1 }    𝒯_ρ := {χ∈Υ   |   tr(χ)=0 }

where Λ_+ represents our space of networks and 𝒯_ρ is the corresponding tangent space.  From this, we let the observations of our dynamic system be recorded as {ρ_0,ρ_1,ρ_2,...,ρ_t} and where each “point” (network) ρ_i∈Υ^+ is given by a tensor.  As seen in Figure <ref>, we need a sensible notion of distance that is dependent on the underlying geometry. To do so, one defines the exponential map as the function that maps to each vector ρ_0 ρ_1∈𝒯_ρ_0, the point ρ_1∈Λ^+ on the manifold M that is reached after unit time by the geodesic starting at ρ_0 with this tangent vector.  The exponential map, herein denoted as exp_ρ:𝒯_ρ↦ M at point ρ is defined on the whole tangent space and for the particular space of tensors, this map is also one-to-one.  Moreover, one can also define a unique inverse map denoted as the logarithm map Log_ρ_0 : M ↦𝒯_ρ_0 that maps a point ρ_1 ∈ M to the unique tangent vector χ∈𝒯_ρ_0 at ρ_0 whose initial velocity is that of the unique geodesic γ  with γ(0) = ρ_0 and γ(1)= ρ_1.  Thus, the problem of computing distances amongst networks (encapsulated by a positive defense matrix) amounts to being able to properly computing geodesics on this space and for which, we must now consider a family of curves γ(t) on the manifold and its speed vector γ̇(t).  Then, we seek the minimum distance (length) for any two points, e.g., ρ_0 and ρ_1 as

    ℒ_ρ_0^ρ_1   = min_γ∫_ρ_0^ρ_1‖γ̇(t)‖_γ(t) dt = min_γ∫_ρ_0^ρ_1(⟨γ̇(t),γ̇(t)⟩_γ(t))

where γ(0)=ρ_0 and γ(1)=ρ_1.  For this note, we relax the restriction upon trace one matrices for sake of clarity (without obfuscating the conceptual motivation).



 §.§ Revisiting Riemannian Framework for Tensors

As highlighted, we seek to leverage Pennec <cit.> framework towards the network setting.  While this framework has popularized most recently in the field of DTI <cit.>, the mechanics can be used to analyze network functionality with this note focusing on the computation of distances amongst such networks.  In particular, the authors utilize a result from differential geometry regarding geodesics for invariant metrics on affine symmetric spaces <cit.> together with the Sylvester equation from control to propose an affine invariant metric whereby the unique geodesic curve from point ρ (and at the origin) on our tensor (network) manifold with a tangent vector χ can be shown as

    γ(t)_(ρ,χ)   = ρ^1/2exp(tρ^-1/2χρ^-1/2)ρ^1/2  and  γ(t)_(I,χ)= exp(tχ)

where exp(χ)=∑_k=0^+∞=χ^k/k! is the usual matrix exponential.  From this, we have:

    dγ(t)/dt   = d/dtexp(tχ) 
       =d/dt(Q [ [ e^tχ_1,1        0      ...        0;        0 e^tχ_2,2      ...        0;        0        0      ... e^tχ_n,n ]] Q^T) 
       = Q DIAG(χ_iexp(tχ_i))Q^T 
       = exp(tχ)^1/2χexp(tχ)^1/2) 
       =γ(t)_(I,χ)^1/2⋆χ

where the A⋆ B=ABA^T.  Noting the geodesic γ(t)_(ρ,χ) between any two points ρ_0, ρ_1∈ M where ρ_1=exp_ρ_0(χ) at t=1, the logarithm map can be seen as

    γ(1)_(ρ_0,χ)   =ρ_1 = ρ_0^1/2exp(ρ_0^-1/2χρ_0^-1/2)ρ_0^1/2
    log(ρ_0^-1/2ρ_1ρ_0^-1/2)   =ρ_0^-1/2χρ_0^-1/2
    ρ_0^1/2log(ρ_0^-1/2ρ_1ρ_0^-1/2)ρ_0^1/2   =χ = ρ_0ρ_1=Log_ρ_0(ρ_1)

From this, the distance between tensors can finally be computed as

    dist^2(ρ_0,ρ_1)    = ‖Log_ρ_0(ρ_1) ‖^2_ρ_0 =‖log(ρ_0^-1/2ρ_1ρ_0^-1/2)‖^2_2.

We now have a natural distance that measures the length of the geodesic curve that connects any two “points” on our tensor (network) manifold.  This is particularly important as it allows for characterization of functionality over a family of networks as we will highlight in the next sections.  


 §.§ Mean, Variance, and Gaussian Distributions

Given the above geodesic distance, one can formulate necessary statistics and most importantly form distributions.  Specifically, with the above affine invariant metric, the unique mean ρ̅ of N “points” {ρ_0,ρ_1,ρ_2,...,ρ_N} on the tensor manifold can be computed via gradient descent:

    ρ̅_t+1=ρ̅_t^1/2exp(1/N∑_i=1^Nlog(ρ̅_t^-1/2ρ_iρ̅_t^-1/2))ρ̅_t^1/2

It has been noted that although no closed form expression for the mean exists, the above converges towards a steady-state solution in a few iterations.   As in the traditional Euclidean distance and similar to the Karcher or Frechet mean, the above mean is constructed on the premise that we seek a “point” that minimizes the sum of squared distance.e., ρ=∑_i=1^Ndist^2(ρ,ρ_i).  In a similar fashion, the variance can be computed as follows:

    Σ = 1/N-1∑_i=1^NVec_ρ̅(Log_ρ̅(ρ_i))Vec_ρ̅(Log_ρ̅(ρ_i))^T

where Vec_ρ̅(ρ_i)=Vec_I(log(ρ̅⋆ρ_i)) and where the operation Vec_I(A) is a vectorized projection of the independent coefficients of our tensor in the above formulation, i.e., Vec_I(A) = (a_1,1,√(2)a_1,2,...√(2)a_1,n,...√(2)a_n-1,n, a_n,n). From this, one obtains a generalized form of the Gaussian distribution on the tensor manifold:

    N_(ρ̅,Σ)(ρ_i)=kexp(1/2Vec_ρ̅(Log_ρ̅(ρ_i))^TΣ^-1Vec_ρ̅(Log_ρ̅(ρ_i))

With the above, we can now begin to stylize how such a framework can be utilized towards characterizing network families.


§ APPLICATION TO NETWORK CHARACTERIZATION

This section presents how the above framework can be used to generalize notions of robustness to a family of networks.  While the experiments focus on the fitness of “distance”, we provide further information to put this note in context.


 §.§ Network Robustness From Scalar to Matrix Setting

As highlighted, our main underlying interest is to understand the functionality over network families.  Recently, it has been
shown that Ricci curvature (herein denoted “Ric”) from geometry is intrinsically connected to Boltzmann entropy H <cit.> as well as functional robustness of networks R or the ability to maintain functionality in the presence of random fluctuations, i.e., Δ Ric×Δ R≥ 0 <cit.>.  Given that geometry (curvature) of networks seemingly plays an integral role in understanding functionality, we require an appropriate discretization applicable to a particular network.  To this end, one can discretely defined Ricci Curvature (due to Ollivier <cit.>) between any two “points” x and y as:

    κ(x,y) := 1 - W_1(μ_x,μ_y)/d(x,y)

This definition, motivated by coarse geometry, is applicable to the graph setting whereby the geodesic distance d(x,y) is given by the hop metric and W_1 can be computed simply via linear programming. However, this measure is limited to local network-to-network variation as opposed to a family of networks.  That is, the definition of equation (<ref>) in the current setting has been used to analyze a given networks robustness through changes of curvature between any two end networks configurations.  Therefore, our primary motivation is focused on developing a matrix-valued curvature measure such that we can analyze Ricci curvature over a family of networks in a more global setting.  In particular, Ollivier's definition is rooted in the concept of providing an “indicator” between negative, Euclidean “flat”, and positive curved spaces by measuring the ratio (distance) of the centers of a geodesic ball against that of the transport distance of ball's distributions (via Wasserstein-1).  Similarly, one can naturally expand this definition to the problem of a family of networks. To do so, we first need a geodesic distance d_M(x,y) provided by equation (<ref>) amongst networks along with the appropriate transport distance W_p.   For the case of Euclidean geometry, one can define the transport distance between two Gaussians μ _1=𝒩(m_1,C_1) and μ _2=𝒩(m_2,C_2), where m_1 and m_2∈ℝ ^n m_2∈ℝ ^n are the means and C_1 and C_2∈ℝ ^n× n C_2∈ℝ ^n× n are the covariances, as:

    W_2(μ _1,μ _2)^2=m_1-m_2_2^2+trace (C_1+C_2-2 (C_2^1/2C_1C_2^1/2 )^1/2 ).
 Comparing this definition to the structure presented in Section 2, the difference lies with respect to the underlying geometry for which Pennec <cit.> provides the mathematical tools to generalize W_2 to our tensor manifold.  While the generalization is on-going and future work, this puts experimental results of d_M(x,y) in context; e.g., our framework interest is to naturally generalize to functionality.


 §.§ Appropriate Matrix-Based Model: Graph Laplacian


Given our interest in network control, a natural network model for encapsulation is an approximated graph Laplacian whose structure provides a global representation of a given network with many useful properties that are intrinsically tied to system functionality.  While a complete review is beyond the scope of this note (we refer the reader to <cit.>), a few areas that have garnered attention have included construction of expander graphs <cit.> to Cheegers inequality with increasing attention on connections between spectral graph theory and its respective geometry <cit.>.  Mathematically, one can define the Laplacian operator for a specific network as Δ f(x)= f(x) - ∑_y f(y)μ_x(y) with f being a real-valued function which coincides with the usual normalized graph Laplacian given by:

    L = I - D^-1/2AD^-1/2

It is interesting to note in this connection that if k ≤κ(x,y) is a lower bound for Ricci curvature defined in equation (<ref>), then the eigenvalues of Laplacian is bounded k ≤λ_2 ≤ . . . ≤λ_N ≤ 2-k <cit.>.  This relationship is important since 2-λ_N measures the deviation of the graph from being bipartite, i.e., a graph whose vertices can be divided into two disjoints sets U and V such that every edge connects a vertex in U to one in V.  As such ideas appear in resource allocation and control, the study of such structures in the time-varying setting motivate our focus on the Laplacian matrix.  Lastly, while one can form a normalized Laplacian with unitary trace, we note that the Laplacian matrix by definition is a positive semi-definite matrix.  Therefore, to enforce positive definiteness, we utilized an approximated Laplacian L̂:= L+ϵ_LI where 0<ϵ_L << 1 such that x^TL̂x>0 for all nonzero x∈ℝ^n.  



§ RESULTS

We now present preliminary results to highlight potential for network analysis and set the foundation for future work in network robustness. 


 §.§ Toy Network Configurations

To provide initial intuition of the proposed framework, we constructed three toy “communication” based networks.  As one can see in Figure <ref>, the networks are composed of 200 nodes and 400 edges with varying topology that represents a chain, a random, and a star-like network.  Similar to our earlier work <cit.>, we are interested in using the proposed framework to measure distances amongst these structures under varying “noise”. As highlighted by network curvature <cit.> and network entropy <cit.>, one should expect from a communication perspective the star-like network is “closer” to a “random” network.  That is, given that their functional properties such as robustness (a measure of “flatness”) are similar compared towards the chain-like network, we should expect that such networks on the manifold lie closer to one another.  This is exactly what is shown in Figure <ref>B.  Moreover, as we move from an unweighted graph to a weighted graph in which weights are chosen randomly in a uniform manner, this relationship still holds.  On the other hand, if we utilize the classical Euclidean distance (Frobenius norm) to measure network-to-network distance, we find that the chain-like network is in fact “closer” to the star-like network which is against intuition.


 §.§ Scale-Free and Random Networks


This section presents clustering results and importance of accounting for the underlying geometry.  In particular, we generate 50 scale-free networks <cit.> and 50 random (Erdos-Renyi) networks with each network composed 200 nodes and 1164 edges (differences are only in topology).  We then compute pairwise distances amongst all potential network pairs based on the Euclidean distance, defined by the Frobenius norm, as well as the Riemannian distance, defined by (<ref>).  Figure <ref>A presents a “heat map” of the distances while Figure <ref>B presents average distance .  As one can see, Euclidean distance fails to cluster networks as the distance between scale-free to random networks are “closer” than random to random networks.   On the other hand, the framework proposed here is able to properly cluster the aforementioned networks which is an intuitive result given a basic understanding of geometry.  However, this motivates this framework for further study on network robustness.  We note if experiments are repeated and/or the number of nodes/edges are changed, the clustering result still holds.


 §.§ Waddingtons Landscape: Cell Differentiation

In this section, we apply the proposed distance measure towards cellular differentiation as depicted in Figure <ref>.  This epigenetic landscape provides a stylistic hierarchal view cellular differentiation, i.e., elevation associates to degrees of pluripotency or the ability for a cell to differentiate.  At a high level, one can consider the intricate and complex processes of cellular differentiation as a network whereby such bifurcations relate to differentiated states <cit.>. To illustrate this, we accessed the Gene Expression Omnibus (GEO) of two public datasets, GSE11508 and GSE 30652, that possess 59 pluripotent / 160 non-pluripotent and 159 pluripotent / 32 non-pluripotent cell samples, respectively.  Within each pluripotent samples, there contains tissue types that include human embryonic stem cells (hESCs) and induced pluripotent stem cells (iPSCs).  This results in a potential mix of differentiation, i.e., iPSCs pluripotency may be much lower than hESCs yet are deemed pluripotent.  Here, we are interested to examine how “far” apart differentiated samples are from their counterparts.  As such, we construct a single pluripotent network similar to previous work <cit.> where the weights are the gene-to-gene correlation.  This was done similarly for a single non-pluripotent network.  Together, this was repeated to generate 50 pluripotent and non-pluripotent networks from each GSE11508 and GSE 30652.  Figure <ref> presents heat map results as well as the average network distance between such networks.  As one can see, we see a marked increase in distance between pluro and non-pluro samples.  We note while the Frobenius norm follows the same pattern, this is primarily due to the topology being fixed amongst samples as well as sparse interactions compared to work by Teschnedorff <cit.>. We provide this to highlight the tacit topological dependence on distance which requires further study that is on-going (e.g., accounting for signaling interactome hierarchy).
 
  


§ CONCLUSION

This note introduces a statistical geometric framework <cit.> previously applied to DTI Imaging <cit.> toward the problem of network analysis.  To illustrate the importance of geometry in this setting, we presented preliminary results that show classical Euclidean distances are unable to properly differentiate between not only toy network configurations, but that of scale-free and random networks.  The results set the foundation for a more expansive study on global notions of robustness for which we will explore notions of network family curvatures.
99
 


Bara1
A. Barabasi. “The Network Takeover,” Nature Physics. 2012.

Dem1
L. Demetrius and T. Manke. “Robustness and Network Evolution: Entropic principle.” Physica A: Statistical Mechanics and its Applications. 2005.

Tesch1
J. West, G. Bianconi, S. Severini, and A. Teschendorff. “Differential Network Entropy Reveals Cancer System Hallmarks.” Nature (Scientific reports) 2012.

Bara2
A. Barbasi and R. Albert. “Emergence of Scaling Networks.” Science. 1999.

Chung
R.K. Fan Chung. “Spectral Graph Theory.” American Mathematical Society. 1997.

Widgerson
S. Hoory, N. Linial, and A. Widgerson. “Expander Graphs and Their Applications.” American Mathematical Society. 2006.

Aharony
D. Stauffer and A. Aharony. “Introduction to Percolation Theory.” Taylor and Francis. 1994

Borgatti1
S. Borgatti. “Centrality and Network Flow.” Social Networks. (2005).

Bara3 
G. Ghoshal and A. Barabasi. “Ranking Stability and Super-Stable Nodes in Complex Networks.” Nature Communications. 2011.

Varadhan
S. R. S. Varadhan. “Large Deviations and Applications.” SIAM. 1984.

Ollivier1
Y. Ollivier. “Ricci Curvature of Markov Chains on Metric spaces.” Journal of Functional Analysis. 2009.

Ollivier2
Y. Ollivier. “Ricci Curvature of Metric Spaces.” Math. Acad. Sci. Paris. 2007.

Sandhu1
 R. Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov, Y. Senbabaoglu, and A. Tannenbaum. “Graph Curvature for Differentiating Cancer Networks.” Nature (Scientific Reports). 2015.
 
Sandhu2
R. Sandhu, T. Georgiou, and A. Tannenbaum. “Ricci Curvature: An Economic Indicator for Market Fragility and Systemic Risk.” Science Advances. 2016.

Pennec1
X. Pennec, P. Fillard, and N. Ayache. “A Riemannian Framework for Tensor Computing.” IJCV. 2005.

Pennec2
V. Arsingy, P. Fillard, X. Pennec, and N. Ayache. “Log-Euclidean metrics for fast and simple calculus on diffusion tensors.” Magnetic Resonance in Medicine. 2006.

Mardia
P. Jupp and K. Mardia. “A unfied view of the theory of directional statistics.” International Statistical Review. 1989.

Moahker2
M. Moakher. “Means and averaging in the group of rotations.” SIAM Journal of Matrix Analysis and Applications. 2002.

Smith
A. Edelman, T. Arias, and S Smith. “The Geometry of Algorithms with Orthonganlity Constraints.” SIAM Journal of Matrix Analysis and Applications. 2002.

DoCarmo
M. DoCarmo. Riemannian Geometry. Birkhauser. 1992.

Joshi
P. Fletcher and S. Joshi. “Principal geodesic analysis on symmetric spaces: Statistics of diffusion tensors.” ECCV. 2004.

Nom
K. Nomizu. “Invariant affine connections on homogeneous spaces.” American Journal of Math. 1954.

Yogesh
Y. Rathi, A. Tannenbaum, O. Michailovich. “Segmenting Images on the Tensor Manifold.” CVPR. 2007.

Affine1
S. Helgason. Differential Geometry, Lie Groups, and Symmetric Spaces. 1978.

LV
J. Lott and C. Villani. “Ricci Curvature for Metric-Measure Spaces via Optimal Transport.” Annals of Mathematics. 2009.

Sturm
K. Sturm. “On the geometry of metric measure spaces.” Acta Math. 2006.

Jost
F. Bauer, J. Jost, and S. Liu. “Ollivier-Ricci Curvature and the Spectrum of the Normalized Graph Laplace Operator.” arXiv. 2013.



 