Abstract:
Network scientists have shown that there is great value in studying pairwise interactions between components in a system. From a linear algebra point of view, this involves defining and evaluating functions of the associated adjacency matrix. Recent work indicates that there are further benefits from accounting directly for higher order interactions, notably through a hypergraph representation where an edge may involve multiple nodes. Building on these ideas, we motivate, define and analyze a class of spectral centrality measures for identifying important nodes and hyperedges in hypergraphs, generalizing existing network science concepts.
...
Read more
--- Different nonlinear eigenvector centrality models recognize different important nodes on the nonuniform sunflower.
Paper accepted on The Web Conference 2021
I am very happy to hear that our paper Nonlinear Higher-order Label Spreading – with Austin Benson and Konstantin Prokopchik – has been accepted on the proceedings of this year’s WWW conference.
Presenting today @ Cornell
Presenting today my work on nonlinear eigenvectors and nonlinear Perron-Frobenius theory at the SCAN seminar at Cornell University (USA). Thanks Austin Benson for the kind invitation!
Presenting today @ UniPisa
Presenting today our work on semi-supervised learning at the NumPi seminar at University of Pisa (Italy), joint work with Austin Benson and Konstantin Prokopchik. Thanks Leo Robol for the kind invitation!
Paper accepted on ESAIM: Math Modelling and Num Analysis
We will introduce the concept of multihomogeneous operators and we will present the state-of-the-art version of the nonlinear Perron-Frobenius theorem for nonnegative nonlinear mappings. We will discuss several numerical optimization implications connected to nonlinear and higher-order versions of the Power and the Sinkhorn methods and several open challenges, both from the theoretical and the computational viewpoints. We will also discuss numerous problems in data mining, machine learning and network science which can be cast in terms of nonlinear eigenvalue problems with eigenvector nonlinearities and we will show how the nonlinear Perron-Frobenius theory can help solve them.
Editor for SIAM Review
I have accepted an invite to serve as associate editor in the Survey & Review section of SIAM Review (SIREV), the flagship section of one of the highest impact applied math journal. Excited and looking forward to starting!
Last day of the first virtual SIAM Imaging Science conference today. I am presenting a talk at the minisymposium Nonlinear Spectral Analysis with Applications in Imaging and Data Science organized by Leon Bungert (Friedrich-Alexander Universitaet Erlangen-Nuernberg, Germany), Guy Gilboa (Technion Israel Institute of Technology, Israel) and Ido Cohen (Israel Institute of Technology, Israel).
These are title and abstract of my talk:
Nodal Domain Theorem for the p-Laplacian on Graphs and the Related Multiway Cheeger Inequality We consider the p-Laplacian on discrete graphs, a nonlinear operator that generalizes the standard graph Laplacian (obtained for p=2). We consider a set of variational eigenvalues of this operator and analyze the nodal domain count of the corresponding eigenfunctions. In particular, we show that the famous Courant’s nodal domain theorem for the linear Laplacian carries over almost unchanged to the nonlinear case. Moreover, we use the nodal domains to prove a higher-order Cheeger inequality that relates the k-way graph cut to the k-th variational eigenvalue of the p-Laplacian.
Below you can find my slides, in case you wish to have a look at them
My poster session room will be on nonlinear eigenevector centralities and will be on for 45 min starting at 4pm Pacific Time (midnight UK, 1am EU). Lots of coffee is planned for that day. You may wish to have a look at my poster:
MSCA Day @ GSSI
We are organizing a “Marie Skłodowska Curie Action Day” virtual event to illustrate some fundamental aspects of Horizon 2020 MSC fellowships. We will discuss some of the application rules, evaluation criteria, how do we think a successful application should be written and we will share personal experiences as recipients and supervisors of MSC individual fellowships.
This event has been promoted and coordinated by my amazing colleague Elisabetta Baracchini
The event will be held virtually on July 2, 9am — 1pm (Italian CET time) via this Zoom meeting room. Details on the program can be found here. Participation is open to everyone and is totally free.
Virtual minisymposium @ SIAM MDS
Michael Schaub, Santiago Segarra and I are organizing a virtual minisymposium on Learning from data on networks within the SIAM Conference on Mathematics of Data Science 2020, happening virtually during the whole month of June. See also the conference’s virtual program.
Our mini will take place on June 30, staring at 10:00 am Eastern time (Boston)
[7am California, 9am Texas, 3pm UK, 4pm EU, 10pm China]
For more details and to register to join the event online (free of charge), please see the minisymposium webpage.
Abstract
Modern societies increasingly depend on complex networked systems to support our daily routines. Electrical energy is delivered by the power grid; the Internet enables almost instantaneous world-wide interactions; our economies rest upon a complex network of inter-dependencies spanning the globe. Networks are ubiquitous in complex biological, social, engineering, and physical systems. Understanding structures and dynamics defined over such networks has thus become a prevalent challenge across many disciplines. A recurring question which appears in a wide variety of problems is how one can exploit the interplay between the topological structure of the system and available measurements at the nodes (or edges) of the networks. The goal of this minisymposium is to bring together researchers from different mathematical communities – from network science, machine learning, statistics, signal processing and optimization – to discuss and highlight novel approaches to understand and learn from data defined on networks.
Speakers:
Michael Schaub — Learning from graphs and data on networks: overview and outlook
Caterina De Bacco — Incorporating node attributes in community detection for multilayer networks
Danai Koutra — The Power of Summarization in Network Representation Learning (and beyond)
Ekaterina Rapinchuk — Applications of Auction Dynamics to Data Defined on Networks
David Gleich — Nonlinear processes on networks
Jan Overgoor — Choosing To Grow a Graph: Modeling Network Formation as Discrete Choice
Abstract:
Label spreading is a general technique for semi-supervised learning with point cloud or network data, which can be interpreted as a diffusion of labels on a graph. While there are many variants of label spreading, nearly all of them are linear models, where the incoming information to a node is a weighted sum of information from neighboring nodes. Here, we add nonlinearity to label spreading through nonlinear functions of higher-order structure in the graph, namely triangles in the graph.
...
Read more
--- Accuracy of Nonlinear Higher-order Label Spreading on synthetic stochastic block models. Table entries are the average accuracy over 10 random instances.
Data Science Open Day @ Uni of Padua
Excited to take part today at the Open House event for the Master’s Degree in Data Science at the Department of Mathematics of the University of Padova. I will give a high-level introduction to the problem of link prediction in networks and how to use PageRank eigenvectors to compute a mathematically informed prediction. The live streaming of the event is available on youtube.
Abstract:
The use of higher-order stochastic processes such as nonlinear Markov chains or vertex-reinforced random walks is significantly growing in recent years as they are much better at modeling high dimensional data and nonlinear dynamics in numerous application settings. In many cases of practical interest, these processes are identified with a stochastic tensor, and their stationary distribution is a tensor Z-eigenvector. However, fundamental questions such as the convergence of the process towards a limiting distribution and the uniqueness of such a limit are still not well understood and are the subject of rich recent literature.
...
Read more
One World seminars
The COVID19 pandemic resulted in the mass cancellation of in-person conferences and seminars across the globe. Wonderful initiatives have resulted as a response to this unfortunate situation. For example, many scientific communities worldwide have started “One World” online seminar series and several conference committees are working in order to put forward online versions of traditional meetings.
Here I would like to list the initiatives related to my research interests that I am aware of. If you know of any other online meeting I have missed, please do let me know!
Abstract:
We analyze the global convergence of the power iterates for the computation of a general mixed-subordinate matrix norm. We prove a new global convergence theorem for a class of entrywise nonnegative matrices that generalizes and improves a well-known results for mixed-subordinate $\ell^p$ matrix norms. In particular, exploiting the Birkoff–Hopf contraction ratio of nonnegative matrices, we obtain novel and explicit global convergence guarantees for a range of matrix norms whose computation has been recently proven to be NP-hard in the general case, including the case of mixed-subordinate norms induced by the vector norms made by the sum of different $\ell^p$-norms of subsets of entries.
...
Read more
Talk @ Rutherford Appleton Laboratory
I am in Oxford (UK) today, giving a talk at the Rutherford Appleton Lab and Uni of Oxford’s Numerical Analysis group joint seminar on Computational Mathematics and Applications. Thank you
Michael Wathen and Tyrone Rees for the invitation!
I have been invited to give a plenary talk this summer at the Householder Symposium XXI. You can read the abstract of my talk from the book of abstracts. Looking forward for this exciting opportunity!
Abstract:
In this work we introduce and study a nonlocal version of the PageRank. In our approach, the random walker explores the graph using longer excursions than just moving between neighboring nodes. As a result, the corresponding ranking of the nodes, which takes into account a long-range interaction between them, does not exhibit concentration phenomena typical for spectral rankings taking into account just local interactions. We show that the predictive value of the rankings obtained using our proposals is considerably improved on different real world problems.
...
Read more
Konstantin successfully passed today his preliminary PhD exam. Congratulations!
We invite contributions focused on all aspects of mathematical, algorithmic, data analysis, and computational techniques in network science and its applications. Accepted submissions will be featured in the workshop as a 20-minute talk, 5-minute talk, or poster.
The school is meant for both final years undergraduate and graduate students who are intrigued by Applied Mathematics and Matrix Methods. The summer school takes place over the course of one entire month—in the two beautiful cities of Rome (Italy) and Moscow (Russia)—and thus it allows the students to really work over the topics that are discussed. Also it is a wonderful occasion to meet new people in the field of Applied Linear Algebra. I have been student of several editions of the school and strongly encourage participation. Please, feel free to contact me if you have questions.
Abstract:
We study the task of semi-supervised learning on multilayer graphs by taking into account both labeled and unlabeled observations together with the information encoded by each individual graph layer. We propose a regularizer based on the generalized matrix mean, which is a one-parameter family of matrix means that includes the arithmetic, geometric and harmonic means as particular cases. We analyze it in expectation under a Multilayer Stochastic Block Model and verify numerically that it outperforms state of the art methods.
...
Read more
--- Poster that will be presented at NeurIPS19, by Pedro Mercado
Abstract:
We propose and analyse a general tensor-based framework for incorporating second order features into network measures. This approach allows us to combine traditional pairwise links with information that records whether triples of nodes are involved in wedges or triangles. Our treatment covers classical spectral methods and recently proposed cases from the literature, but we also identify many interesting extensions. In particular, we define a mutually-reinforcing (spectral) version of the classical clustering coefficient.
...
Read more
--- Nodes with largest spectral clustering coefficient in the karate club network, for different tensors.
Abstract:
Being able to produce synthetic networks by means of generative random graph models and scalable algorithms is a recurring tool-of-the-trade in network analysis, as it provides a well founded basis for the statistical analysis of various properties in real-world networks. In this paper, we illustrate how to generate large random graphs having a power-law degree profile by means of the Chung-Lu model. In particular, we are concerned with the fulfillment of a fundamental hypothesis that must be placed on the model parameters, without which the generated graphs loose all the theoretical properties of the model, notably, the controllability of the expected node degrees and the absence of correlations between the degrees of two nodes joined by an edge.
...
Read more
--- The power law degree distribution of random graphs in the Chung-Lu model.
Abstract:
This work is concerned with the computation of $\ell^p$-eigenvalues and eigenvectors of square tensors with $d$ modes. In the first part we propose two possible shifted variants of the popular (higher-order) power method for the computation of $\ell^p$-eigenpairs proving the convergence of both the schemes to the Perron $\ell^p$-eigenvector of the tensor, and the maximal corresponding $\ell^p$-eigenvalue, when the tensor is entrywise nonnegative and $p$ is strictly larger than the number of modes.
...
Read more
Paper accepted on NeurIPS19
I am delighted to hear that our paper Generalized Matrix Means for Semi-Supervised Learning with Multilayer Graphs – with Pedro Mercado and Matthias Hein – has been accepted on the proceedings of this year’s NeurIPS conference.
Abstract:
Many graph mining tasks can be viewed as classification problems on high dimensional data. Within this class we consider the issue of discovering core-periphery structure, which has wide applications in the economic and social sciences. In contrast to many current approaches, we allow for weighted and directed edges and we do not assume that the overall network is connected. Our approach extends recent work on a relevant relaxed nonlinear optimization problem.
...
Read more
--- Edge probability $p_{ij}(u)$ in the logistic core-periphery random graph model.
Abstract:
Maximizing the modularity of a network is a successful tool to identify an important community of nodes. However, this combinatorial optimization problem is known to be NP-hard. Inspired by recent nonlinear modularity eigenvector approaches, we introduce the modularity total variation $TV_Q$ and show that its box-constrained global maximum coincides with the maximum of the original discrete modularity function. Thus we describe a new nonlinear optimization approach to solve the equivalent problem leading to a community detection strategy based on $TV_Q$.
...
Read more
The University of Strathclyde is hosting two major conferences this summer:
The 28th Biennial Numerical Analysis Conference (see also my previous post), where I will give the talk Networks core-periphery detection with nonlinear Perron eigenvectors and the 17th Workshop on Advances in Continuous Optimization, where I will give the talk Leading community detection in networks via total variation optimization.
Abstract:
Nonnegative tensors arise very naturally in many applications that involve large and complex data flows. Due to the relatively small requirement in terms of memory storage and number of operations per step, the (shifted) higher-order power method is one of the most commonly used technique for the computation of positive Z-eigenvectors of this type of tensors. However, unlike the matrix case, the method may fail to converge even for irreducible tensors.
...
Read more
I am organizing a minisymposium and giving a talk:
Minisymposium:Matrix methods for networks
jointly organized with Francesca Arrigo Abstract: There is a strong relationship between network science and linear algebra, as complex networks can be represented and manipulated using matrices. Some popular tasks in network science, such as ranking nodes, identifying hidden structures, or classifying and labelling components in networks, can be tackled by exploiting the matrix representation of the data. In this minisymposium we sample some recent contributions that build on an algebraic representation of standard and higher-order networks to design models and algorithms to address a diverse range of network problems, including (but not limited to) core-periphery detection and centrality.
Speakers:
Francesca Arrigo (Strathclyde)
Mihai Cucuringu (Oxford)
Gissell Estrada-Rodriguez (Heriot-Watt)
Dario Fasino (Udine)
Philip Knight (Strathclyde)
Francesco Tudisco (Strathclyde)
My talk will be on Networks core-periphery detection with nonlinear Perron eigenvectors
Abstract:
Signed graphs encode positive (attractive) and negative (repulsive) relations between nodes. We extend spectral clustering to signed graphs via the one-parameter family of Signed Power Mean Laplacians, defined as the matrix power mean of normalized standard and signless Laplacians of positive and negative edges. We provide a thorough analysis of the proposed approach in the setting of a general Stochastic Block Model that includes models such as the Labeled Stochastic Block Model and the Censored Block Model.
...
Read more
--- SBM spectral embeddings for different power mean Laplacians
Abstract:
We introduce a ranking model for temporal multi-dimensional weighted and directed networks based on the Perron eigenvector of a multi-homogeneous order-preserving map. The model extends to the temporal multilayer setting the HITS algorithm and defines five centrality vectors: two for the nodes, two for the layers, and one for the temporal stamps. Nonlinearity is introduced in the standard HITS model in order to guarantee existence and uniqueness of these centrality vectors for any network, without any requirement on its connectivity structure.
...
Read more
ICIAM19: International Congress on Industrial and Applied Mathematics
I am organizing a 16 speakers (super-)minisymposium and giving a talk at the next ICIAM19 conference in Valencia (Spain), July 15-19.
Abstract: The analysis of complex networks is a rapidly growing field with applications in many diverse areas. A typical computational paradigm is to reduce the system to a set of pairwise relationships modeled by a graph (matrix) and employ tools within this framework. However, many real-world networks feature temporally evolving structures and higher-order interactions. Such components are often missed when using static and lower-order methods. This minisymposium explores recent advances in models, theory, and algorithms for dynamic and higher-order interactions and data, spanning a broad range of topics including persistent homology, tensor analysis, random walks with memory, and higher-order network analysis.
Group1 – Community detection and clustering
Christine Klymko, LLNL
Improving seed set expansion with semi-supervised information
Tim La Fond, LLNL
Representing the Evolution of Communities in Dynamic Networks
Nate Veldt, Purdue
Algorithmic Advances in Higher-Order Correlation Clustering
Marya Bazzi, ATI
Community structure in temporal multilayer networks
Group2 – Simplicial complexes
Heather Harrington, Oxford
Topological data analysis for investigation of dynamics and biological networks
Alice Patania, Indiana
Null hypothesis for simplicial complexes
Braxton Osting, Utah
Spectral Sparsification of Simplicial Complexes for Clustering and Label Propagation
Austin Benson, Cornell
Simplicial closure and higher-order link prediction.
Group3 – Tensor methods and high-performance computing
Francesca Arrigo
Eigenvector-based Centrality Measures in Multilayer Networks
Orly Alter, Utah
Multi-Tensor Decompositions for Personalized Cancer Diagnostics, Prognostics, and Therapeutics.
Chunxing Yin, GA Tech
A New Algorithm Model for Massive-Scale Streaming Graph Analysis
Tahsin Reza, UBC
Distributed Algorithms for Exact and Fuzzy Graph Pattern Matching
Group4 – Higher-order random walks
Eisha Nathan, LLNL
Nonbacktracking Walks in Dynamic Graphs
Michael Schaub, MIT
Random walks on simplicial complexes and the normalized Hodge Laplacian
Keita Iwabuchi, LLNL
Francesco Tudisco, Strathclyde
Higher-order ergodicity coefficients
This event is part of the research project MAGNET for which I would like to acknowledge support from the Marie Curie individual fellowship scheme.
Abstract:
We derive and analyse a new iterative algorithm for detecting network core–periphery structure. Using techniques in nonlinear Perron-Frobenius theory, we prove global convergence to the unique solution of a relaxed version of a natural discrete optimization problem. On sparse networks, the cost of each iteration scales linearly with the number of nodes, making the algorithm feasible for large-scale problems. We give an alternative interpretation of the algorithm from the perspective of maximum likelihood reordering of a new logistic core–periphery
...
Read more
--- Top ten core train stations in the city of London
ALAMA NLA 2019
I have accepted the kind invitation of José Mas and Fernando de Terán Vergara to give a two-hour lecture in June (17-19) at the ALAMA (Spanish Society for Linear Agebra, Matrix Analysis and Applications) 2019 workshop at the Polytechnic University of Valencia.
Research visit @ Uni of Udine
This week I am visiting the Department of Mathematics, Computer Science and Physics of the University of Udine (Italy), invited by Dario Fasino (thanks Dario!). We are planning to work hard to finalize our work on Higher-order ergodicity coefficients for tensors. I will also give a seminar, you can see the details in the flyer below. I am looking forward to exciting days of math and some authentic frico!
Brief lecture course at Rome-Moscow school 2018
I will be visiting the Department of Mathematics of University of Rome “Tor Vergata”, my alma mater, from Monday September 17 to Friday 21 and in occasion of the Rome-Moscow school on Matrix Methods and Applied Linear Algebra. See also my previous post. I will teach a brief course on nonlinear spectral methods for higher-order centrality and core-periphery detection in networks. I hope to finish my notes and the associated Julia Notebooks soon, and post them here. A quick look to the weather forecast: today the temperature in Rome is more than twice (30C) the one here in Scotland (14C).
Abstract:
With the notion of mode-$j$ Birkhoff contraction ratio, we prove a multilinear version of the Birkhoff-Hopf and the Perron-Fronenius theorems, which provide conditions on the existence and uniqueness of a solution to a large family of systems of nonlinear equations of the type $$f_i(x_1,…,x_ν)= λ_i x_i, ,$$ being $x_i$ and element of a cone $C_i$ in a Banach space $V_i$. We then consider a family of nonlinear integral operators $f_i$ with positive kernel, acting on product of spaces of continuous real valued functions.
...
Read more
Visiting KTH Royal Institute of Technology
I look forward to visit and give a seminar talk at the Numerical Analysis group of the Department of Mathematics of KTH in Stockholm, Sweden. I will stay there for two weeks: Sunday August 26 to Saturday September 8. Thanks Elias for the kind invitation and for hosting me!
Two conferences in June
I am participating at two exciting conferences next June 2018:
The program of both events looks very exciting, I am really looking forward for them.
At SIAM IS I will present my work on Community detection with nonlinear modularity (based on this paper) at the minisymposium Optimization for Imaging and Big Data (see here) organized by Francesco Rinaldi and Margherita Porcelli.
At IMA NLA OPT I will present my work on Small updates of function of adjacency matrices (based on this paper) at the minisymposium Matrix Functions and
Quadrature Rules with Applications to Complex Network (see here) organized by Francesca Arrigo and Stefano Pozza.
I am flying to Hong Kong today to attend the SIAM Applied Linear Algebra conference 2018 where I am organizing a minisymposium on Nonlinear Perron-Frobenius theory and applications and giving a talk titled A new Perron-Frobenius theorem for nonnegative tensors. See also my previous post.