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: 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
Abstract: Influence Maximization (IM) is a pivotal concept in social network analysis, involving the identification of influential nodes within a network to maximize the number of influenced nodes, and has a wide variety of applications that range from viral marketing and information dissemination to public health campaigns. IM can be modeled as a combinatorial optimization problem with a black-box objective function, where the goal is to select seed nodes that maximize the expected influence spread. ... Read more