Associate Professor (Reader) in Machine Learning
School of Mathematics, The University of Edinburgh
The Maxwell Institute for Mathematical Sciences
Alan Turing Institute | Bayes Centre | Gen AI Lab
School of Mathematics, Gran Sasso Science Institute
email: f dot tudisco at ed.ac.uk
Abstract: Multilayer graphs encode different kind of interactions between the same set of entities. When one wants to cluster such a multilayer graph, the natural question arises how one should merge the information form different layers. We introduce in this paper a one-parameter family of matrix power means for merging the Laplacians from different layers and analyze it in the stochastic block model. We show that this family allows to recover ground truth clusters under different settings and verify this in real world data. ... Read more
Abstract: We provide explicit expressions for the eigenvalues and eigenvectors of matrices that can be written as the Hadamard product of a block partitioned matrix with constant blocks and a rank one matrix. Such matrices arise as the expected adjacency or modularity matrices in certain random graph models that are widely used as benchmarks for community detection algorithms. Please cite this work as: @article{fasino2018expected, title={The expected adjacency and modularity matrices in the degree corrected stochastic block model}, author={Fasino, Dario and Tudisco, Francesco}, journal={Special Matrices}, volume={6}, pages={110--121}, year={2018} }
I will be visiting the Department of Mathematics of University of Padua from Monday 5 to Friday 9 February. Very excited to meet some of my past colleagues and to have the chance to work over various ongoing collaborations. Moreover, the Italian workshop “Due Giorni” on Numerical Linear Algebra will take place in the Department on Thursday 8 and Friday 9. According to the list of participants and their abstracts a lot of interesting work will be presented. I will give a talk on Multi-dimensional nonlinear Perron-Frobenius theorem and its application to network centrality. Here is my abstract.
Abstract: We introduce the concept of shape partition of a tensor and formulate a general tensor eigenvalue problem that includes all previously studied eigenvalue problems as special cases. We formulate irreducibility and symmetry properties of a nonnegative tensor $T$ in terms of the associated shape partition. We recast the eigenvalue problem for $T$ as a fixed point problem on a suitable product of projective spaces. This allows us to use the theory of multihomogeneous order-preserving maps to derive a new and unifying Perron–Frobenius theorem for nonnegative tensors which either implies earlier results of this kind or improves them, as weaker assumptions are required. ... Read more
I will be visiting the Department of Mathematics of Tufts University in Boston, Massachusetts from Wednesday 20 to Friday 22 December.
I am organizing a minisymposium and giving a talk at next SIAM Applied Linear Algebra conference in Hong Kong. Below are some detail of my contributions. This event is part of the research project MAGNET for which I would like to acknowledge support from the Marie Curie individual fellowship scheme.
Minisymposium: Nonlinear Perron-Frobenius theory and applications
jointly organized with Antoine Gautier
Abstract: Nonlinear Perron-Frobenius theory addresses problems such as existence, uniqueness and maximality of positive eigenpairs of different types of nonlinear and order-preserving mappings.In recent years tools from this theory have been successfully exploited to address problems arising from a range of diverse applications and various areas, such as graph and hypergraph analysis, machine learning, signal processing, optimization and spectral problems for nonnegative tensors. This minisymposium sample some recent contributions in this field, covering advances in both the theory and the applications of Perron-Frobenius theory for nonlinear mappings.
Speakers:
Contributed talk: A new Perron-Frobenius theorem for nonnegative tensors
Abstract: Based on the concept of dimensional partition we consider a general tensor spectral problem that includes all known tensor spectral problems as special cases. We formulate irreducibility and symmetry properties in terms of the dimensional partition and use the theory of multi-homogeneous order-preserving maps to derive a general and unifying Perron-Frobenius theorem for nonnegative tensors that either includes previous results of this kind or improves them by weakening the assumptions there considered.
You may wish to have a look at my slides:
I am very happy to hear from Carmine di Fiore that the 6th edition of the Rome Moscow summer school on Matrix Methods and Applied Linear Algebra will take place next summer, between August 25 and September 23, 2018.
This summer school is very peculiar because is long (one month!) and thus allows 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.
Getting ready for the ZiF final conference in Bielefeld. I will talk about the nodal domains of the $p$-Laplacian operator on discrete graphs.
Precisely, this is the abstract of my talk: The number of nodal domains induced by the eigenfunctions of the Laplacian operator has been completely described both for graphs and for continuous domains. For $p\geq 1$, the $p$-Laplacian is a nonlinear operator which reduces to the standard Laplacian when $p=2$. This nonlinear operator has gained popularity in recent years as, for instance, it can be used to improve data clustering algorithms. We consider a set of variational eigenvalues of the $p$-Laplacian on discrete graphs and analyze the nodal domain structure of the associated eigenfunctions. We show that when $p>1$, the upper bound in the linear nodal domain theorem carries over unchanged to the nonlinear setting, whereas some properties are lost when $p=1$. We also discuss an higher-order Cheeger inequality that can be obtained by exploiting the nodal structure of the $p$-Laplacian.
Abstract: Eigenvector-based centrality measures are among the most popular centrality measures in network science. The underlying idea is intuitive and the mathematical description is extremely simple in the framework of standard, mono-layer networks. Moreover, several efficient computational tools are available for their computation. Moving up in dimensionality, several efforts have been made in the past to describe an eigenvector-based centrality measure that generalizes Bonacich index to the case of multiplex networks. In this work, we propose a new definition of eigenvector centrality that relies on the Perron eigenvector of a multi-homogeneous map defined in terms of the tensor describing the network. ... Read more
Abstract: Nodal theorems for generalized modularity matrices ensure that the cluster located by the positive entries of the leading eigenvector of various modularity matrices induces a connected subgraph. In this paper we obtain lower bounds for the modularity of that set of nodes showing that, under certain conditions, the nodal domains induced by eigenvectors corresponding to highly positive eigenvalues of the normalized modularity matrix have indeed positive modularity, that is they can be recognized as modules inside the network. ... Read more
Abstract: In a graph or complex network, communities and anti-communities are node sets whose modularity attains extremely large values, positive and negative, respectively. We consider the simultaneous detection of communities and anti-communities, by looking at spectral methods based on various matrix-based definitions of the modularity of a vertex set. Invariant subspaces associated to extreme eigenvalues of these matrices provide indications on the presence of both kinds of modular structure in the network. ... Read more
Abstract: Identifying important components in a network is one of the major goals of network analysis. Popular and effective measures of importance of a node or a set of nodes are defined in terms of suitable entries of functions of matrices $f(A)$. These kinds of measures are particularly relevant as they are able to capture the global structure of connections involving a node. However, computing the entries of $f(A)$ requires a significant computational effort. ... Read more
Abstract: Revealing a community structure in a network or dataset is a central problem arising in many scientific areas. The modularity function $Q$ is an established measure quantifying the quality of a community, being identified as a set of nodes having high modularity. In our terminology, a set of nodes with positive modularity is called a module and a set that maximizes $Q$ is thus called leading module. Finding a leading module in a network is an important task, however the dimension of real-world problems makes the maximization of $Q$ unfeasible. ... Read more
Today is the first day of my new academic position as Marie Curie Fellow at the department of Mathematics and Statistics of University of Strathclyde.
Abstract: Let $S$ be a column stochastic matrix with at least one full row. Then $S$ describes a Pagerank-like random walk since the computation of the Perron vector $x$ of $S$ can be tackled by solving a suitable M-matrix linear system $Mx = y$, where $M = I − \tau A$, $A$ is a column stochastic matrix and $\tau$ is a positive coefficient smaller than one. The Pagerank centrality index on graphs is a relevant example where these two formulations appear. ... Read more
Abstract: Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to the assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. ... Read more
Abstract: We consider the nonlinear graph $p$-Laplacian and its set of eigenvalues and associated eigenfunctions of this operator defined by a variational principle. We prove a nodal domain theorem for the graph $p$-Laplacian for any $p\geq 1$. While for $p>1$ the bounds on the number of weak and strong nodal domains are the same as for the linear graph Laplacian ($p=2$), the behavior changes for $p=1$. We show that the bounds are tight for $p\geq 1$ as the bounds are attained by the eigenfunctions of the graph $p$-Laplacian on two graphs. ... Read more
Abstract: The Perron-Frobenius theory for nonnegative matrices has been generalized to order-preserving homogeneous mappings on a cone and more recently to nonnegative multilinear forms. We unify both approaches by introducing the concept of order-preserving multi-homogeneous mappings, their associated nonlinear spectral problems and spectral radii. We show several Perron-Frobenius type results for these mappings addressing existence, uniqueness and maximality of nonnegative and positive eigenpairs. We prove a Collatz-Wielandt principle and other characterizations of the spectral radius and analyze the convergence of iterates of these mappings towards their unique positive eigenvectors. ... Read more
Abstract: We propose a new localization result for the leading eigenvalue and eigenvector of a symmetric matrix $A$. The result exploits the Frobenius inner product between $A$ and a given rank-one landmark matrix $X$. Different choices for $X$ may be used, depending on the problem under investigation. In particular, we show that the choice where $X$ is the all-ones matrix allows to estimate the signature of the leading eigenvector of $A$, generalizing previous results on Perron-Frobenius properties of matrices with some negative entries. ... Read more
Abstract: Various modularity matrices appeared in the recent literature on network analysis and algebraic graph theory. Their purpose is to allow writing as quadratic forms certain combinatorial functions appearing in the framework of graph clustering problems. In this paper we put in evidence certain common traits of various modularity matrices and shed light on their spectral properties that are at the basis of various theoretical results and practical spectral-type algorithms for community detection. ... Read more
Abstract: Signed networks allow to model positive and negative relationships. We analyze existing extensions of spectral clustering to signed networks. It turns out that existing approaches do not recover the ground truth clustering in several situations where either the positive or the negative network structures contain no noise. Our analysis shows that these problems arise as existing approaches take some form of arithmetic mean of the Laplacians of the positive and negative part. ... Read more
Abstract: We prove that the Bernoulli numbers satisfy some special lower triangular Toeplitz systems of linear equations. One of these systems has a strong link with eleven Ramanujan’s linear equations satisfied by the first eleven Bernoulli numbers. Please cite this work as: @article{difiore2016lower, title={Lower triangular Toeplitz--Ramanujan systems whose solution yields the Bernoulli numbers}, author={Di Fiore, Carmine and Tudisco, Francesco and Zellini, Paolo}, journal={Linear Algebra and its Applications}, volume={496}, pages={510--526}, year={2016}, publisher={Elsevier} }
Abstract: We investigate two ergodicity coefficients $\phi_{|| \cdot ||}$ and $\tau_{n-1}$, originally introduced to bound the subdominant eigenvalues of nonnegative matrices. The former has been generalized to complex matrices in recent years and several properties for such generalized version have been shown so far. We provide a further result concerning the limit of its powers. Then we propose a generalization of the second coefficient $\tau_{n-1}$ and we show that, under mild conditions, it can be used to recast the eigenvector problem $Ax = x$ as a particular $M$-matrix linear system, whose coefficient matrix can be defined in terms of the entries of $A$. ... Read more
Abstract: In this paper we study adaptive $L(k)QN$ methods, involving special matrix algebras of low complexity, to solve general (non-structured) unconstrained minimization problems. These methods, which generalize the classical BFGS method, are based on an iterative formula which exploits, at each step, an ad hoc chosen matrix algebra $L(k)$. A global convergence result is obtained under suitable assumptions on $f$. Please cite this work as: @article{cipolla2015adaptive, title={Adaptive matrix algebras in unconstrained minimization}, author={Cipolla, Stefano and Di Fiore, Carmine and Tudisco, Francesco and Zellini, Paolo}, journal={Linear Algebra and its Applications}, volume={471}, pages={544--568}, year={2015}, publisher={Elsevier} }
Abstract: Power nonnegative matrices are defined as complex matrices having at least one nonnegative integer power. We exploit the possibility of deriving a Perron–Frobenius-like theory for these matrices, obtaining three main results and drawing several consequences. We study, in particular, the relationships with the set of matrices having eventually nonnegative powers, the inverse of M-type matrices and the set of matrices whose columns (rows) sum up to one. Please cite this work as: @article{tudisco2015complex, title={On complex power nonnegative matrices}, author={Tudisco, Francesco and Cardinali, Valerio and Di Fiore, Carmine}, journal={Linear Algebra and its Applications}, volume={471}, pages={449--468}, year={2015}, publisher={Elsevier} }
Abstract: One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix $M$, defined in terms of the adjacency matrix and a rank one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency, incidence and Laplacian matrices. ... Read more
Abstract: When a linear system $Ax = y$ is solved by means of iterative methods (mainly CG and GMRES) and the convergence rate is slow, one may consider a preconditioner $P$. The use of such preconditioner changes the spectrum of the matrix defining the system and could result into a great acceleration of the convergence rate. The construction of optimal rank preconditioners is strongly related to the possibility of splitting $A$ as $A = P + R + E$, where $E$ is a small perturbation and $R$ is of low rank. ... Read more
Abstract: Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler-Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra $\mathcal U$ of matrices, thereby obtaining an ER-$\mathcal U$ method, and we observe that ER-$\mathcal U$ can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. ... Read more
Abstract: We propose a novel methodology to solve a key eigenvalue optimization problem which arises in the contractivity analysis of neural ODEs. When looking at contractivity properties of a one layer weight-tied neural ODE $\dot{u}(t)=σ(Au(t)+b)$ (with $u,b \in {\mathbb R}^n$, $A$ is a given $n \times n$ matrix, $σ: {\mathbb R} \to {\mathbb R}^+$ denotes an activation function and for a vector $z \in {\mathbb R}^n$, $σ(z) \in {\mathbb R}^n$ has to be interpreted entry-wise), we are led to study the logarithmic norm of a set of products of type $D A$, where $D$ is a diagonal matrix such that ${\mathrm{diag}}(D) \in σ'({\mathbb R}^n)$. ... Read more