Distance plays a crucial role in determining the degree of resemblance between two objects of interest. A wide range of learning tasks in statistics and machine learning, including classification, shape matching, dimension reduction, and clustering, are directly dependent on the measure of dissimilarity between observations. Consequently, it is of utmost necessity to have a distance measure capable of accurately including the underlying data structure. In this paper, an unique distance metric for network-valued data is proposed. Our major breakthrough is to construct a distance that can represent the topological properties of the data based on the long-term diffusion behavior of the entire network. On the basis of the Laplacian flow dynamic system on graphs, a unique distance measure termed network flow distance is established. A second contribution consists in proposing a computational pipeline for the network flow distance that makes use of simple concepts from numerical linear algebra, so making it an easily available alternative to other distance measurements. Using simulated examples, we demonstrate the utility of the proposed distance measure and its advantages over other existing measures. We also employ the distance for an unsupervised learning task of clustering network-valued data.

In this work, we propose to train a graph neural network via resampling from a graphon estimate obtained from the underlying network data. More specifically, the graphon or the link probability matrix of the underlying network is first obtained from which a new network will be resampled and used during the training process at each layer. Due to the uncertainty induced from the resampling, it helps mitigate the well-known issue of over-smoothing in a graph neural network (GNN) model. Our framework is general, computationally efficient, and conceptually simple. Another appealing feature of our method is that it requires minimal additional tuning during the training process. Extensive numerical results show that our approach is competitive with and in many cases outperform the other over-smoothing reducing GNN training methods.

In this work, we propose to employ information-geometric tools to optimize a graph neural network architecture such as the graph convolutional networks. More specifically, we develop optimization algorithms for the graph-based semi-supervised learning by employing the natural gradient information in the optimization process. This allows us to efficiently exploit the geometry of the underlying statistical model or parameter space for optimization and inference. To the best of our knowledge, this is the first work that has utilized the natural gradient for the optimization of graph neural networks that can be extended to other semi-supervised problems. Efficient computations algorithms are developed and extensive numerical studies are conducted to demonstrate the superior performance of our algorithms over existing algorithms such as ADAM and SGD.

A weighted directed network (WDN) is a directed graph in which each edge is associated to a unique value called weight. These networks are very suitable for modeling real-world social networks in which there is an assessment of one vertex toward other vertices. One of the main problems studied in this paper is prediction of edge weights in such networks. We introduce, for the first time, a metric geometry approach to studying edge weight prediction in WDNs. We modify a usual notion of WDNs, and introduce a new type of WDNs which we coin the term almost-weighted directed networks (AWDNs). AWDNs can capture the weight information of a network from a given training set. We then construct a class of metrics (or distances) for AWDNs which equips such networks with a metric space structure. Using the metric geometry structure of AWDNs, we propose modified k nearest neighbors (kNN) methods and modified support-vector machine (SVM) methods which will then be used to predict edge weights in AWDNs. In many real-world datasets, in addition to edge weights, one can also associate weights to vertices which capture information of vertices; association of weights to vertices especially plays an important role in graph embedding problems. Adopting a similar approach, we introduce two new types of directed networks in which weights are associated to either a subset of origin vertices or a subset of terminal vertices. We, for the first time, construct novel classes of metrics on such networks, and based on these new metrics propose modified kNN and SVM methods for predicting weights of origins and terminals in these networks. We provide experimental results on several real-world datasets, using our geometric methodologies.