Predictive graph analytics and propagation of information in networks

Explaining the science

Summary

This project is developing algorithms to gain an understanding of how news sentiment propagates through the network, from the news-affected companies (the minority class) to the remaining companies (the majority class). This approach is broadly applicable to instances where one has available a sparse signal (e.g., news sentiment for a subset of nodes) and would like to understand how the available signal measurements propagate through the network to the remaining nodes.

Technical description

This approach can be seen as an instance of the group synchronisation problem over Z_2 with anchor information, where one would like to estimate n unknown group elements from noisy pairwise ratios of group elements, subject to the constraint that a subset of the elements (denoted as the anchor set) is known a-priori. The empirical correlation matrix (or various denoised version) serves as the matrix of weighted pairwise group ratios, and one would like to find an assignment of ±1 to the n nodes of the signed graph, subject to the constraint that some node group elements are known (+1 for positive news, and −1 for negative news). In prior work, motivated by structural biology applications, the researchers have solved such instances via semidefinite programming (SDP) and quadratically constrained quadratic programming, and more recently via methods inspired from non-convex optimisation and fast SDP via a Burer-Monteiro approach.

On the clustering side, the researchers have recently developed algorithms for clustering of signed networks. Clustering is one of the most widely used techniques in data analysis, and aims to identify groups of nodes that exhibit similar features. Much of the existing literature has focused on unsigned networks, whose edges only have non-negative real weights. However, negative weights can be used to denote dissimilarity or distance between a pair of nodes in a network. In this case, the resulting network arising from the correlation of historical returns of the S&P 500 instruments displays both positive and negative values. To this end, the researchers rely on techniques they recently developed, that proposed new principled clustering algorithms that explicitly take into account the negative weights by redesigning the graph-based objective function to be optimised.

References

M. Cucuringu, A. Pizzoferrato, News sentiment propagation in financial networks via constrained optimization, (in progress)

M. Cucuringu, A. Pizzoferrato, Y. van Gennip, An MBO scheme for clustering and semi-supervised clustering of signed networks, arXiv:1901.03091 (2019), https://arxiv.org/abs/1901.03091

M. Cucuringu, P. Davies, A. Glielmo, H. Tyagi, "SPONGE: A generalized eigenproblem for clustering signed networks", AISTATS 2019, https://arxiv.org/abs/1904.08575