Georgia Institute of Technology College of Sciences

We study the problem of estimating the left and right singular subspaces for a collection of heterogeneous random graphs with a shared common structure. We analyze an algorithm that first estimates the orthogonal projection matrices corresponding to these subspaces for each individual graph, then computes the average of the projection matrices, and finally finds the matrices whose columns are the eigenvectors corresponding to the d largest eigenvalues of the sample averages. We show that the algorithm yields an estimate of the left and right singular vectors whose row-wise fluctuations are normally distributed around the rows of the true singular vectors. We then consider a two-sample hypothesis test for the null hypothesis that two graphs have the same edge probabilities matrices against the alternative hypothesis that their edge probabilities matrices are different. Using the limiting distributions for the singular subspaces, we present a test statistic whose limiting distribution converges to a central chi-square (resp. non-central chi-square) under the null (resp. alternative) hypothesis. Finally, we adapt the theoretical analysis for multiple networks to the setting of distributed PCA; in particular, we derive normal approximations for the rows of the estimated eigenvectors using distributed PCA when the data exhibit a spiked covariance matrix structure.

Abstract: While spectral methods provide far-ranging insights on graph structure, there remain significant challenges in their application to real data. Most notably, spectral methods do not incorporate information that maybe available beyond adjacency.  A common approach to incorporating such additional information is encode this information in an ad-hoc manner into weights associated with the edges. Not only does this have limited expressivity, but is also restricted by graph structure: if two vertices are not adjacent, then edge weights cannot capture any closeness implied by metadata.

We address this issue by introducing the inner product Hodge Laplacian for an arbitrary simplicial complex.  Within this framework we prove generalizations of foundational results in spectral graph theory, such as the Cheeger inequality and the expander mixing lemma, and show our framework recovers the usual combinatorial and normalized Laplacians as special cases. Our framework allows for the principled synthesis of combinatorial approaches in network science with more metadata driven approaches by using latent space encodings of the metadata to define an inner product both the vertices and the edges.

(Coffee will be available at 3:30 before this talk, following the speaker's Professional Development Seminar at 2:30pm.)

This talk will present an overview of the behavior of the eigenvalues of the fractional Brownian matrix motion and other related matrix processes. We will do so by emphasizing the dynamics of the eigenvalues processes, the non-colliding property, the limit of the associated empirical process, as well as the free Brownian motion and the non commutative fractional Brownian motion.

The dynamic shortest path problem seeks to maintain the shortest paths/distances between pairs of vertices in a graph that is subject to edge insertions, deletions, or weight changes. The aim is to maintain that information more efficiently than naive recomputation via, e.g., Dijkstra's algorithm.
We present the first fully dynamic algorithm maintaining exact single source distances in unweighted graphs. This resolves open problems stated in [Demetrescu and Italiano, STOC'03], [Thorup SWAT'04], [Sankowski, COCOON 2005] and [vdBrand and Nanongkai, FOCS 2019].
In this talk, we will see how ideas from fine-grained complexity theory, computer algebra, and graph theory lead to insights for dynamic shortest paths problems.