Search

Simplicial complexes (SCs), a generalization of graph models for relational data that account for higher-order relations between data items, have become a popular abstraction for analyzing complex data using tools from topological data analysis or topological signal processing. However, the analysis of many real-world datasets leads to dense SCs with a large number of higher-order interactions. Unfortunately, analyzing such large SCs often has a prohibitive cost in terms of computation time and memory consumption. The sparsification of such complexes, i.e., the approximation of an original SC with a sparser simplicial complex with only a log-linear number of high-order simplices while maintaining a spectrum close to the original SC, is of broad interest. In this work, we develop a novel method for a probabilistic sparsifaction of SCs. At its core lies the efficient computation of sparsifying sampling probability through local densities of states as functional descriptors of the spectral information. To avoid pathological structures in the spectrum of the corresponding Hodge Laplacian operators, we suggest a "kernel-ignoring" decomposition for approximating the sampling probability; additionally, we exploit error estimates to show asymptotically prevailing algorithmic complexity of the developed method. The performance of the framework is demonstrated on the family of Vietoris--Rips filtered simplicial complexes., Comment: 10 pages, 7 figures more...

Oversmoothing is a fundamental challenge in graph neural networks (GNNs): as the number of layers increases, node embeddings become increasingly similar, and model performance drops sharply. Traditionally, oversmoothing has been quantified using metrics that measure the similarity of neighbouring node features, such as the Dirichlet energy. While these metrics are related to oversmoothing, we argue they have critical limitations and fail to reliably capture oversmoothing in realistic scenarios. For instance, they provide meaningful insights only for very deep networks and under somewhat strict conditions on the norm of network weights and feature representations. As an alternative, we propose measuring oversmoothing by examining the numerical or effective rank of the feature representations. We provide theoretical support for this approach, demonstrating that the numerical rank of feature representations converges to one for a broad family of nonlinear activation functions under the assumption of nonnegative trained weights. To the best of our knowledge, this is the first result that proves the occurrence of oversmoothing without assumptions on the boundedness of the weight matrices. Along with the theoretical findings, we provide extensive numerical evaluation across diverse graph architectures. Our results show that rank-based metrics consistently capture oversmoothing, whereas energy-based metrics often fail. Notably, we reveal that a significant drop in the rank aligns closely with performance degradation, even in scenarios where energy metrics remain unchanged. more...

We propose a method to enhance the stability of a neural ordinary differential equation (neural ODE) by means of a control over the Lipschitz constant $C$ of its flow. Since it is known that $C$ depends on the logarithmic norm of the Jacobian matrix associated with the neural ODE, we tune this parameter at our convenience by suitably perturbing the Jacobian matrix with a perturbation as small as possible in Frobenius norm. We do so by introducing an optimization problem for which we propose a nested two-level algorithm. For a given perturbation size, the inner level computes the optimal perturbation with a fixed Frobenius norm, while the outer level tunes the perturbation amplitude. We embed the proposed algorithm in the training of the neural ODE to improve its stability. Numerical experiments on the MNIST and FashionMNIST datasets show that an image classifier including a neural ODE in its architecture trained according to our strategy is more stable than the same classifier trained in the classical way, and therefore, it is more robust and less vulnerable to adversarial attacks., Comment: 22 pages, 3 figures, 2 tables more...

Multilayer networks provide a powerful framework for modeling complex systems that capture different types of interactions between the same set of entities across multiple layers. Core-periphery detection involves partitioning the nodes of a network into core nodes, which are highly connected across the network, and peripheral nodes, which are densely connected to the core but sparsely connected among themselves. In this paper, we propose a new model of core-periphery in multilayer network and a nonlinear spectral method that simultaneously detects the corresponding core and periphery structures of both nodes and layers in weighted and directed multilayer networks. Our method reveals novel structural insights in three empirical multilayer networks from distinct application areas: the citation network of complex network scientists, the European airlines transport network, and the world trade network. more...

Foundation models have demonstrated remarkable success across various scientific domains, motivating our exploration of their potential in solar physics. In this paper, we present Solaris, the first foundation model for forecasting the Sun's atmosphere. We leverage 13 years of full-disk, multi-wavelength solar imagery from the Solar Dynamics Observatory, spanning a complete solar cycle, to pre-train Solaris for 12-hour interval forecasting. Solaris is built on a large-scale 3D Swin Transformer architecture with 109 million parameters. We demonstrate Solaris' ability to generalize by fine-tuning on a low-data regime using a single wavelength (1700 {\AA}), that was not included in pre-training, outperforming models trained from scratch on this specific wavelength. Our results indicate that Solaris can effectively capture the complex dynamics of the solar atmosphere and transform solar forecasting. more...

We analyze various formulations of the $\infty$-Laplacian eigenvalue problem on graphs, comparing their properties and highlighting their respective advantages and limitations. First, we investigate the graph $\infty$-eigenpairs arising as limits of $p$-Laplacian eigenpairs, extending key results from the continuous setting to the discrete domain. We prove that every limit of $p$-Laplacian eigenpair, for $p$ going to $\infty$, satisfies a limit eigenvalue equation and establish that the corresponding eigenvalue can be bounded from below by the packing radius of the graph, indexed by the number of nodal domains induced by the eigenfunction. Additionally, we show that the limits, for $p$ going to $\infty$, of the variational $p$-Laplacian eigenvalues are bounded both from above and from below by the packing radii, achieving equality for the smallest two variational eigenvalues and corresponding packing radii of the graph. In the second part of the paper, we introduce generalized $\infty$-Laplacian eigenpairs as generalized critical points and values of the $\infty$-Rayleigh quotient. We prove that the generalized variational $\infty$-eigenvalues satisfy the same upper bounds in terms of packing radii as the limit of the variational eigenvalues, again with equality holding between the smallest two $\infty$-variational eigenvalues and the first and second packing radii of the graph. Moreover, we establish that any solution to the limit eigenvalue equation is also a generalized eigenpair, while any generalized eigenpair satisfies the limit eigenvalue equation on a suitable subgraph. more...

Low-Rank Adaptation (LoRA) has become a widely used method for parameter-efficient fine-tuning of large-scale, pre-trained neural networks. However, LoRA and its extensions face several challenges, including the need for rank adaptivity, robustness, and computational efficiency during the fine-tuning process. We introduce GeoLoRA, a novel approach that addresses these limitations by leveraging dynamical low-rank approximation theory. GeoLoRA requires only a single backpropagation pass over the small-rank adapters, significantly reducing computational cost as compared to similar dynamical low-rank training methods and making it faster than popular baselines such as AdaLoRA. This allows GeoLoRA to efficiently adapt the allocated parameter budget across the model, achieving smaller low-rank adapters compared to heuristic methods like AdaLoRA and LoRA, while maintaining critical convergence, descent, and error-bound theoretical guarantees. The resulting method is not only more efficient but also more robust to varying hyperparameter settings. We demonstrate the effectiveness of GeoLoRA on several state-of-the-art benchmarks, showing that it outperforms existing methods in both accuracy and computational efficiency. more...

Adversarial attacks on deep neural network models have seen rapid development and are extensively used to study the stability of these networks. Among various adversarial strategies, Projected Gradient Descent (PGD) is a widely adopted method in computer vision due to its effectiveness and quick implementation, making it suitable for adversarial training. In this work, we observe that in many cases, the perturbations computed using PGD predominantly affect only a portion of the singular value spectrum of the original image, suggesting that these perturbations are approximately low-rank. Motivated by this observation, we propose a variation of PGD that efficiently computes a low-rank attack. We extensively validate our method on a range of standard models as well as robust models that have undergone adversarial training. Our analysis indicates that the proposed low-rank PGD can be effectively used in adversarial training due to its straightforward and fast implementation coupled with competitive performance. Notably, we find that low-rank PGD often performs comparably to, and sometimes even outperforms, the traditional full-rank PGD attack, while using significantly less memory. more...

Authors of COVID-19 papers produced during the pandemic were overwhelmingly not subject matter experts. Such a massive inflow of scholars from different expertise areas is both an asset and a potential problem. Domain-informed scientific collaboration is the key to preparing for future crises. more...

Using drones to perform human-related tasks can play a key role in various fields, such as defense, disaster response, agriculture, healthcare, and many others. The drone delivery packing problem (DDPP) arises in the context of logistics in response to an increasing demand in the delivery process along with the necessity of lowering human intervention. The DDPP is usually formulated as a combinatorial optimization problem, aiming to minimize drone usage with specific battery constraints while ensuring timely consistent deliveries with fixed locations and energy budget. In this work, we propose two alternative formulations of the DDPP as a quadratic unconstrained binary optimization (QUBO) problem, in order to test the performance of classical and quantum annealing (QA) approaches. We perform extensive experiments showing the advantages as well as the limitations of quantum annealers for this optimization problem, as compared to simulated annealing (SA) and classical state-of-the-art commercial tools for global optimization., Comment: 16 pages, 6 figures, 7 tables more...

Implicit-depth neural networks have grown as powerful alternatives to traditional networks in various applications in recent years. However, these models often lack guarantees of existence and uniqueness, raising stability, performance, and reproducibility issues. In this paper, we present a new analysis of the existence and uniqueness of fixed points for implicit-depth neural networks based on the concept of subhomogeneous operators and the nonlinear Perron-Frobenius theory. Compared to previous similar analyses, our theory allows for weaker assumptions on the parameter matrices, thus yielding a more flexible framework for well-defined implicit networks. We illustrate the performance of the resulting subhomogeneous networks on feedforward, convolutional, and graph neural network examples. more...

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)=\sigma(Au(t)+b)$ (with $u,b \in {\mathbb R}^n$, $A$ is a given $n \times n$ matrix, $\sigma : {\mathbb R} \to {\mathbb R}$ denotes an activation function and for a vector $z \in {\mathbb R}^n$, $\sigma(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 \sigma'({\mathbb R}^n)$. Specifically, given a real number $c$ (usually $c=0$), the problem consists in finding the largest positive interval $\text{I}\subseteq \mathbb [0,\infty)$ such that the logarithmic norm $\mu(DA) \le c$ for all diagonal matrices $D$ with $D_{ii}\in \text{I}$. We propose a two-level nested methodology: an inner level where, for a given $\text{I}$, we compute an optimizer $D^\star(\text{I})$ by a gradient system approach, and an outer level where we tune $\text{I}$ so that the value $c$ is reached by $\mu(D^\star(\text{I})A)$. We extend the proposed two-level approach to the general multilayer, and possibly time-dependent, case $\dot{u}(t) = \sigma( A_k(t) \ldots \sigma ( A_{1}(t) u(t) + b_{1}(t) ) \ldots + b_{k}(t) )$ and we propose several numerical examples to illustrate its behaviour, including its stabilizing performance on a one-layer neural ODE applied to the classification of the MNIST handwritten digits dataset., Comment: 26 pages, 6 figures, 4 tables more...

Recent work in deep learning has shown strong empirical and theoretical evidence of an implicit low-rank bias: weight matrices in deep networks tend to be approximately low-rank and removing relatively small singular values during training or from available trained models may significantly reduce model size while maintaining or even improving model performance. However, the majority of the theoretical investigations around low-rank bias in neural networks deal with oversimplified deep linear networks. In this work, we consider general networks with nonlinear activations and the weight decay parameter, and we show the presence of an intriguing neural rank collapse phenomenon, connecting the low-rank bias of trained networks with networks' neural collapse properties: as the weight decay parameter grows, the rank of each layer in the network decreases proportionally to the within-class variability of the hidden-space embeddings of the previous layers. Our theoretical findings are supported by a range of experimental evaluations illustrating the phenomenon. more...

Techniques based on $k$-th order Hodge Laplacian operators $L_k$ are widely used to describe the topology as well as the governing dynamics of high-order systems modeled as simplicial complexes. In all of them, it is required to solve a number of least square problems with $L_k$ as coefficient matrix, for example in order to compute some portions of the spectrum or integrate the dynamical system. In this work, we introduce the notion of optimal collapsible subcomplex and we present a fast combinatorial algorithm for the computation of a sparse Cholesky-like preconditioner for $L_k$ that exploits the topological structure of the simplicial complex. The performance of the preconditioner is tested for conjugate gradient method for least square problems (CGLS) on a variety of simplicial complexes with different dimensions and edge densities. We show that, for sparse simplicial complexes, the new preconditioner reduces significantly the condition number of $L_k$ and performs better than the standard incomplete Cholesky factorization., Comment: 22 pages, 8 figures more...

Core-periphery detection aims to separate the nodes of a complex network into two subsets: a core that is densely connected to the entire network and a periphery that is densely connected to the core but sparsely connected internally. The definition of core-periphery structure in multiplex networks that record different types of interactions between the same set of nodes on different layers is nontrivial since a node may belong to the core in some layers and to the periphery in others. We propose a nonlinear spectral method for multiplex networks that simultaneously optimises a node and a layer coreness vector by maximising a suitable nonconvex homogeneous objective function by a provably convergent alternating fixed point iteration. We derive a quantitative measure for the quality of a given multiplex core-periphery structure that allows the determination of the optimal core size. Numerical experiments on synthetic and real-world networks illustrate that our approach is robust against noisy layers and significantly outperforms baseline methods while improving the latter with our novel optimised layer coreness weights. As the runtime of our method depends linearly on the number of edges of the network it is scalable to large-scale multiplex networks. more...

Dynamical systems on hypergraphs can display a rich set of behaviours not observable for systems with pairwise interactions. Given a distributed dynamical system with a putative hypergraph structure, an interesting question is thus how much of this hypergraph structure is actually necessary to faithfully replicate the observed dynamical behaviour. To answer this question, we propose a method to determine the minimum order of a hypergraph necessary to approximate the corresponding dynamics accurately. Specifically, we develop an analytical framework that allows us to determine this order when the type of dynamics is known. We utilize these ideas in conjunction with a hypergraph neural network to directly learn the dynamics itself and the resulting order of the hypergraph from both synthetic and real data sets consisting of observed system trajectories. more...

With the growth of model and data sizes, a broad effort has been made to design pruning techniques that reduce the resource demand of deep learning pipelines, while retaining model performance. In order to reduce both inference and training costs, a prominent line of work uses low-rank matrix factorizations to represent the network weights. Although able to retain accuracy, we observe that low-rank methods tend to compromise model robustness against adversarial perturbations. By modeling robustness in terms of the condition number of the neural network, we argue that this loss of robustness is due to the exploding singular values of the low-rank weight matrices. Thus, we introduce a robust low-rank training algorithm that maintains the network's weights on the low-rank matrix manifold while simultaneously enforcing approximate orthonormal constraints. The resulting model reduces both training and inference costs while ensuring well-conditioning and thus better adversarial robustness, without compromising model accuracy. This is shown by extensive numerical evidence and by our main approximation theorem that shows the computed robust low-rank network well-approximates the ideal full model, provided a highly performing low-rank sub-network exists. more...

Clustering (or community detection) on multilayer graphs poses several additional complications with respect to standard graphs as different layers may be characterized by different structures and types of information. One of the major challenges is to establish the extent to which each layer contributes to the cluster assignment in order to effectively take advantage of the multilayer structure and improve upon the classification obtained using the individual layers or their union. However, making an informed a-priori assessment about the clustering information content of the layers can be very complicated. In this work, we assume a semi-supervised learning setting, where the class of a small percentage of nodes is initially provided, and we propose a parameter-free Laplacian-regularized model that learns an optimal nonlinear combination of the different layers from the available input labels. The learning algorithm is based on a Frank-Wolfe optimization scheme with inexact gradient, combined with a modified Label Propagation iteration. We provide a detailed convergence analysis of the algorithm and extensive experiments on synthetic and real-world datasets, showing that the proposed method compares favourably with a variety of baselines and outperforms each individual layer when used in isolation. more...

Reducing parameter redundancies in neural network architectures is crucial for achieving feasible computational and memory requirements during training and inference phases. Given its easy implementation and flexibility, one promising approach is layer factorization, which reshapes weight tensors into a matrix format and parameterizes them as the product of two small rank matrices. However, this approach typically requires an initial full-model warm-up phase, prior knowledge of a feasible rank, and it is sensitive to parameter initialization. In this work, we introduce a novel approach to train the factors of a Tucker decomposition of the weight tensors. Our training proposal proves to be optimal in locally approximating the original unfactorized dynamics independently of the initialization. Furthermore, the rank of each mode is dynamically updated during training. We provide a theoretical analysis of the algorithm, showing convergence, approximation and local descent guarantees. The method's performance is further illustrated through a variety of experiments, showing remarkable training compression rates and comparable or even better performance than the full baseline and alternative layer factorization strategies. more...

The modeling of opinion dynamics has seen much study in varying academic disciplines. Understanding the complex ways information can be disseminated is a complicated problem for mathematicians as well as social scientists. We present a nonlinear model of opinion dynamics that utilizes an environmental averaging protocol similar to the DeGroot and Freidkin-Johnsen models. Indeed, the way opinions evolve is complex and nonlinear effects ought to be considered when modelling. For this model, the nonlinearity destroys the translation invariance of the equations, as well as the convexity of the associated payout functions. The standard theory for well-posedness and convergence no longer applies and we must utilize the Brouwer topological degree and nonconvex analysis in order to achieve these results. Numerical simulations of the model reveal that the nonlinearity behaves similarly to the well-known Friedkin-Johnsen for so-called "reasonable" opinions, but better models the way agents that hold "extreme" opinions are more stubborn than their reasonable counterparts. more...

We consider the problem of attaining either the maximal increase or reduction of the robustness of a complex network by means of a bounded modification of a subset of the edge weights. We propose two novel strategies combining Krylov subspace approximations with a greedy scheme and an interior point method employing either the Hessian or its approximation computed via the limited-memory Broyden-Fletcher-Goldfarb-Shanno algorithm (L-BFGS). The paper discusses the computational and modeling aspects of our methodology and illustrates the various optimization problems on networks that can be addressed within the proposed framework. Finally, in the numerical experiments we compare the performances of our algorithms with state-of-the-art techniques on synthetic and real-world networks. more...

Graph Semi-Supervised learning is an important data analysis tool, where given a graph and a set of labeled nodes, the aim is to infer the labels to the remaining unlabeled nodes. In this paper, we start by considering an optimization-based formulation of the problem for an undirected graph, and then we extend this formulation to multilayer hypergraphs. We solve the problem using different coordinate descent approaches and compare the results with the ones obtained by the classic gradient descent method. Experiments on synthetic and real-world datasets show the potential of using coordinate descent methods with suitable selection rules., Comment: 24 pages, 10 figures more...

The homology groups of a simplicial complex reveal fundamental properties of the topology of the data or the system and the notion of topological stability naturally poses an important yet not fully investigated question. In the current work, we study the stability in terms of the smallest perturbation sufficient to change the dimensionality of the corresponding homology group. Such definition requires an appropriate weighting and normalizing procedure for the boundary operators acting on the Hodge algebra's homology groups. Using the resulting boundary operators, we then formulate the question of structural stability as a spectral matrix nearness problem for the corresponding higher-order graph Laplacian. We develop a bilevel optimization procedure suitable for the formulated matrix nearness problem and illustrate the method's performance on a variety of synthetic quasi-triangulation datasets and transportation networks., Comment: 25 pages, 9 figures more...

Nonlinear eigenvalue problems for pairs of homogeneous convex functions are particular nonlinear constrained optimization problems that arise in a variety of settings, including graph mining, machine learning, and network science. By considering different notions of duality transforms from both classical and recent convex geometry theory, in this work we show that one can move from the primal to the dual nonlinear eigenvalue formulation maintaining the spectrum, the variational spectrum as well as the corresponding multiplicities unchanged. These nonlinear spectral duality properties can be used to transform the original optimization problem into various alternative and possibly more treatable dual problems. We illustrate the use of nonlinear spectral duality in a variety of example settings involving optimization problems on graphs, nonlinear Laplacians, and distances between convex bodies. more...

Neural networks have achieved tremendous success in a large variety of applications. However, their memory footprint and computational demand can render them impractical in application settings with limited hardware or energy resources. In this work, we propose a novel algorithm to find efficient low-rank subnetworks. Remarkably, these subnetworks are determined and adapted already during the training phase and the overall time and memory resources required by both training and evaluating them are significantly reduced. The main idea is to restrict the weight matrices to a low-rank manifold and to update the low-rank factors rather than the full matrix during training. To derive training updates that are restricted to the prescribed manifold, we employ techniques from dynamic model order reduction for matrix differential equations. This allows us to provide approximation, stability, and descent guarantees. Moreover, our method automatically and dynamically adapts the ranks during training to achieve the desired approximation accuracy. The efficiency of the proposed method is demonstrated through a variety of numerical experiments on fully-connected and convolutional networks. more...

Core-periphery detection is a key task in exploratory network analysis where one aims to find a core, a set of nodes well-connected internally and with the periphery, and a periphery, a set of nodes connected only (or mostly) with the core. In this work we propose a model of core-periphery for higher-order networks modeled as hypergraphs and we propose a method for computing a core-score vector that quantifies how close each node is to the core. In particular, we show that this method solves the corresponding non-convex core-periphery optimization problem globally to an arbitrary precision. This method turns out to coincide with the computation of the Perron eigenvector of a nonlinear hypergraph operator, suitably defined in term of the incidence matrix of the hypergraph, generalizing recently proposed centrality models for hypergraphs. We perform several experiments on synthetic and real-world hypergraphs showing that the proposed method outperforms alternative core-periphery detection algorithms, in particular those obtained by transferring established graph methods to the hypergraph setting via clique expansion. more...

We propose a new kernel that quantifies success for the task of computing a core-periphery partition for an undirected network. Finding the associated optimal partitioning may be expressed in the form of a quadratic unconstrained binary optimization (QUBO) problem, to which a state-of-the-art quantum annealer may be applied. We therefore make use of the new objective function to (a) judge the performance of a quantum annealer, and (b) compare this approach with existing heuristic core-periphery partitioning methods. The quantum annealing is performed on the commercially available D-Wave machine. The QUBO problem involves a full matrix even when the underlying network is sparse. Hence, we develop and test a sparsified version of the original QUBO which increases the available problem dimension for the quantum annealer. Results are provided on both synthetic and real data sets, and we conclude that the QUBO/quantum annealing approach offers benefits in terms of optimizing this new quantity of interest. more...

Inspired by the linear Schr\"odinger operator, we consider a generalized $p$-Laplacian operator on discrete graphs and present new results that characterize several spectral properties of this operator with particular attention to the nodal domain count of its eigenfunctions. Just like the one-dimensional continuous $p$-Laplacian, we prove that the variational spectrum of the discrete generalized $p$-Laplacian on forests is the entire spectrum. Moreover, we show how to transfer Weyl's inequalities for the Laplacian operator to the nonlinear case and prove new upper and lower bounds on the number of nodal domains of every eigenfunction of the generalized $p$-Laplacian on generic graphs, including variational eigenpairs. In particular, when applied to the linear case $p=2$, in addition to recovering well-known features, the new results provide novel properties of the linear Schr\"odinger operator. more...

The self-consistent field (SCF) iteration, combined with its variants, is one of the most widely used algorithms in quantum chemistry. We propose a procedure to adapt the SCF iteration for the p-Laplacian eigenproblem, which is an important problem in the field of unsupervised learning. We formulate the p-Laplacian eigenproblem as a type of nonlinear eigenproblem with one eigenvector nonlinearity , which then allows us to adapt the SCF iteration for its solution after the application of suitable regularization techniques. The results of our numerical experiments confirm the viablity of our approach. more...

In this paper, we focus on the community detection problem in multiplex networks, i.e., networks with multiple layers having same node sets and no inter-layer connections. In particular, we look for groups of nodes that can be recognized as communities consistently across the layers. To this end, we propose a new approach that generalizes the Louvain method by (a) simultaneously updating average and variance of the modularity scores across the layers, and (b) reformulating the greedy search procedure in terms of a filter-based multiobjective optimization scheme. Unlike many previous modularity maximization strategies, which rely on some form of aggregation of the various layers, our multiobjective approach aims at maximizing the individual modularities on each layer simultaneously. We report experiments on synthetic and real-world networks, showing the effectiveness and the robustness of the proposed strategies both in the informative case, where all layers show the same community structure, and in the noisy case, where some layers represent only noise. more...

A second-order random walk on a graph or network is a random walk where transition probabilities depend not only on the present node but also on the previous one. A notable example is the non-backtracking random walk, where the walker is not allowed to revisit a node in one step. Second-order random walks can model physical diffusion phenomena in a more realistic way than traditional random walks and have been very successfully used in various network mining and machine learning settings. However, numerous questions are still open for this type of stochastic processes. In this work we extend well-known results concerning mean hitting and return times of standard random walks to the second-order case. In particular, we provide simple formulas that allow us to compute these numbers by solving suitable systems of linear equations. Moreover, by introducing the "pullback" first-order stochastic process of a second-order random walk, we provide second-order versions of the renowned Kac's and random target lemmas. more...

Hypergraphs are a common model for multiway relationships in data, and hypergraph semi-supervised learning is the problem of assigning labels to all nodes in a hypergraph, given labels on just a few nodes. Diffusions and label spreading are classical techniques for semi-supervised learning in the graph setting, and there are some standard ways to extend them to hypergraphs. However, these methods are linear models, and do not offer an obvious way of incorporating node features for making predictions. Here, we develop a nonlinear diffusion process on hypergraphs that spreads both features and labels following the hypergraph structure, which can be interpreted as a hypergraph equilibrium network. Even though the process is nonlinear, we show global convergence to a unique limiting point for a broad class of nonlinearities, which is the global optimum of a interpretable, regularized semi-supervised learning loss function. The limiting point serves as a node embedding from which we make predictions with a linear model. Our approach is much more accurate than several hypergraph neural networks, and also takes less time to train. more...

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. By exploiting the latest developments in nonlinear Perron-Frobenius theory, we show how the resulting constrained nonlinear eigenvalue problems have unique solutions that can be computed efficiently via a nonlinear power method iteration. We illustrate the measures on realistic data sets. more...

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. For a broad class of nonlinear functions, we prove convergence of our nonlinear higher-order label spreading algorithm to the global solution of a constrained semi-supervised loss function. We demonstrate the efficiency and efficacy of our approach on a variety of point cloud and network datasets, where the nonlinear higher-order model compares favorably to classical label spreading, as well as hypergraph models and graph neural networks. more...

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. Finally, we use the new results combined with hypercontractive inequalities to prove a new lower bound on the logarithmic Sobolev constant of a Markov chain. more...

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 \textit{long-range interaction} between them, does not exhibit concentration phenomena typical of spectral rankings which take 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. more...

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. Moreover, we introduce a matrix-free numerical scheme based on contour integral quadratures and Krylov subspace solvers that scales to large sparse multilayer graphs., Comment: Accepted in NeurIPS 2019 more...

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. The underlying object of study is a constrained nonlinear eigenvalue problem associated with a cubic tensor. Using recent results from nonlinear Perron--Frobenius theory, we establish existence and uniqueness under appropriate conditions, and show that the new spectral measures can be computed efficiently with a nonlinear power method. To illustrate the added value of the new formulation, we analyse the measures on a class of synthetic networks. We also give computational results on centrality and link prediction for real-world networks. more...

Random graph models are a recurring tool-of-the-trade for studying network structural properties and benchmarking community detection and other network algorithms. Moreover, they serve as test-bed generators for studying diffusion and routing processes on networks. In this paper, we illustrate how to generate large random graphs having a power-law degree distribution using the Chung--Lu model. In particular, we are concerned with the fulfilment of a fundamental hypothesis that must be placed on the model parameters, without which the generated graphs lose 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. We provide explicit formulas for the model parameters to generate random graphs that have several desirable properties, including a power-law degree distribution with any exponent larger than $2$, a prescribed asymptotic behaviour of the largest and average expected degrees, and the presence of a giant component., Comment: Typos corrected, references and introduction modified, additional experiments more...

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. Then, motivated by the slow rate of convergence that the proposed methods achieve for certain real-world tensors, when $p\approx d$, the number of modes, in the second part we introduce an extrapolation framework based on the simplified topological $\varepsilon$-algorithm to efficiently accelerate the shifted power sequences. Numerical results on synthetic and real world problems show the improvements gained by the introduction of the shifting parameter and the efficiency of the acceleration technique. more...

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-complete. 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$. The proposed approach relies on the use of a fast first-order method that embeds a tailored active-set strategy. We report extensive numerical comparisons with standard matrix-based approaches and the Generalized RatioDCA approach for nonlinear modularity eigenvectors, showing that our new method compares favourably with state-of-the-art alternatives. more...

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. Ergodicity coefficients for stochastic matrices provide a valuable and widely used tool to analyze the long-term behavior of standard, first-order, Markov processes. In this work, we extend an important class of ergodicity coefficients to the setting of stochastic tensors. We show that the proposed higher-order ergodicity coefficients provide new explicit formulas that (a) guarantee the uniqueness of Perron $Z$-eigenvectors of stochastic tensors, (b) provide bounds on the sensitivity of such eigenvectors with respect to changes in the tensor and (c) ensure the convergence of different types of higher-order stochastic processes governed by cubical stochastic tensors. Moreover, we illustrate the advantages of the proposed ergodicity coefficients on several example application settings, including the analysis of PageRank vectors for triangle-based random walks and the convergence of lazy higher-order random walks., Comment: New title, shorter proof of main results and improved experimental section more...

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. Moreover, when it converges, its convergence rate can be very slow. These two drawbacks often make the computation of the eigenvectors demanding or unfeasible for large problems. In this work we consider a particular class of nonnegative tensors associated to the multilinear PageRank modification of higher-order Markov chains. Based on the simplified topological ${\epsilon}$-algorithm in its restarted form, we introduce an extrapolation-based acceleration of power method type algorithms, namely the shifted fixed-point method and the inner-outer method. The accelerated methods show remarkably better performance, with faster convergence rates and reduced overall computational time. Extensive numerical experiments on synthetic and real-world datasets demonstrate the advantages of the introduced extrapolation techniques., Comment: This version corrects an error in Theorem 1 of the previous version more...

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. We show that in expectation the signed power mean Laplacian captures the ground truth clusters under reasonable settings where state-of-the-art approaches fail. Moreover, we prove that the eigenvalues and eigenvector of the signed power mean Laplacian concentrate around their expectation under reasonable conditions in the general Stochastic Block Model. Extensive experiments on random graphs and real world datasets confirm the theoretically predicted behaviour of the signed power mean Laplacian and show that it compares favourably with state-of-the-art methods., Comment: final version accepted at ICML 2019 more...

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. We introduce a globally convergent power iteration like algorithm for the computation of the centrality vectors. Numerical experiments on real-world networks are performed in order to assess the effectiveness of the proposed model and showcase the performance of the accompanying algorithm. more...

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,\dots,x_\nu)= \lambda_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. In this setting we provide an explicit formula for the mode-$j$ contraction ratio which is particularly relevant in practice as this type of operators play a central role in numerous models and applications. more...

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 random graph model. This viewpoint also gives a new basis for quantitatively judging a core--periphery detection algorithm. We illustrate the algorithm on a range of synthetic and real networks, and show that it offers advantages over the current state-of-the-art. more...

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 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 expectation 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. While computing the matrix power mean can be very expensive for large graphs, we introduce a numerical scheme to efficiently compute its eigenvectors for the case of large sparse graphs., Comment: 19 pages, 3 figures. Accepted in Artificial Intelligence and Statistics (AISTATS), 2018 more...