MAC-MIGS Research Afternoon – Friday 1st July 2022

** Learning Complex Structures on Graphs **

The workshop will take place on the 1st July, 11am-3pm. This is a hybrid event with limited in-person spaces at Bayes Centre, University of Edinburgh. To register, please complete the  Registration Form

Graphs (or networks) are ubiquitous in many real-world scenarios, where nodes represent agents and edges capture interactions between the agents. Examples include social networks, protein-protein interaction networks in biology, and brain networks in neuroscience. Recent years have seen a surge in research on analyzing, visualizing, and learning the key properties of graphs due to increased data availability and computing power. Many graphs have inherent structures, such as modules, motifs or core-periphery hierarchy. Typically to recover these patterns, nodes need to be mapped into low-dimensional Euclidean space. The current research in this area is focused on designing and analysing algorithms, understanding the mechanisms behind them, and extending them beyond pair-wise interactions. Advances in the theory and algorithms led to new state-of-the-art results in many domains, including recommender systems, drug discovery, and computer vision. In this MAC-MIGS research afternoon session, we invited speakers to present recent advances in the research on learning graph structures, such as clustering and structure recovery on graphs and hypergraphs.

Timetable

Organisers: Xue Gong, Alix Leroy, Lukasz Sliwinski
Advisors: Desmond J. Higham, Konstantinos C. Zygalakis

Abstracts:

Sun He: Beyond Symmetric Clusters: Finding Inter-Cluster Structures in Graphs

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph.

In this talk I will address the natural question of whether the structure of clusters can be learned efficiently, present two new algorithms for learning the inter-cluster structure of graphs in both centralised and distributed settings, and discuss their applications in several real-world datasets.

This is based on joint work with Peter Macgregor, and these results appeared at ICML’21 and ICML’22.

Mihai Cucuringu : Spectral methods for graph clustering, ranking and group synchronization

Graph clustering problems typically arise in settings where there exists a discrepancy in the edge density within different parts of the graph. In this work, we consider several problem instances where the underlying cluster structure arises as a consequence of a signal present on the edges or on the nodes of the graph, and is not driven by edge density. In particular, we consider the problem of clustering in two important families of networks: signed and directed, both relatively less well explored compared to their unsigned and undirected counterparts. Both problems share an important common feature: they can be solved by exploiting the spectrum of certain graph Laplacian matrices or derivations thereof. In signed networks, the edge weights between the nodes may take either positive or negative values, encoding a measure of similarity or dissimilarity. We consider a generalized eigenvalue problem involving graph Laplacians, with performance guarantees under the setting of a signed stochastic block model, along with regularized versions to handle very sparse graphs. We also discuss a spectral clustering algorithm for directed graphs based on a complex-valued representation of the adjacency matrix, which is able to capture the underlying cluster structures, for which the information encoded in the direction of the edges is crucial. Finally, we discuss connections to ranking from pairwise comparison data and the heterogeneous group synchronization problem, of recovering group elements from a sparse set of noisy pairwise ratios of group elements.

Ginestra Bianconi: Higher-order networks and their dynamics

Higher-order networks [1] describe the many-body interactions of a large variety of complex systems, ranging from the brain to collaboration networks and social contact networks. Simplicial complexes are generalized network structures which allow us to capture the combinatorial properties, the topology and the geometry of higher-order networks. In this talk we will show that simplicial complexes provide a very general mathematical framework to reveal how higher-order dynamics including synchronization and epidemic spreading depends on simplicial network topology. We will show that higher-order synchronization describing the dynamics of topological signals defined on link, triangles and higher-dimensional simplices is explosive [2-4] and we will show that this rich dynamics can have an important role for understanding brain rhythms. We will also show how epidemic spreading on higher-order networks [5] can take into account for time-dependent contacts due to co-location in space and how this modelling can help us understand the spreading dynamics of airborne diseases.

[1]G. Bianconi, Higher-order networks: An introduction to simplicial complexes (Cambridge University Press, 2021)
[2] Millán, A.P., Torres, J.J. and Bianconi, G., 2020. Explosive higher-order Kuramoto dynamics on simplicial complexes.Physical Review Letters, 124(21), p.218301.
[3] Ghorbanchian, R., Restrepo, J.G., Torres, J.J. and Bianconi, G., 2021. Higher-order simplicial synchronization of coupled topological signals. Communications Physics, 4(1), pp.1-13.
[4] Calmon, L., Restrepo, J.G., Torres, J.J. and Bianconi, G., 2021. Topological synchronization: explosive transition and rhythmic phase. arXiv preprint arXiv:2107.05107.
[5] St-Onge, G., Sun, H., Allard, A., Hébert-Dufresne, L. and Bianconi, G., 2021. Universal nonlinear infection kernel from heterogeneous exposure on higher-order networks. Physical Review Letters, 127(15), p.158301.