Efficient Sparsification of Simplicial Complexes via Local Densities of States
SIAM Journal on Mathematics of Data Science, 2026
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 …
Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex
SIAM Journal on Matrix Analysis and Applications, 2024
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 …
Learning the effective order of a hypergraph dynamical system
Science Advances, 2024
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 …
Laplacian-based Semi-Supervised Learning in Multilayer Hypergraphs by Coordinate Descent
EURO Journal on Computational Optimization, 2023
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 …
Quantifying the structural stability of simplicial homology
Journal of Scientific Computing, vol. 97, 2023
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 …
Hitting times for second-order random walks
European Journal of Applied Mathematics, vol. 34, pp. 642–666, 2022
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 …
Nonlinear Feature Diffusion on Hypergraphs
International Conference on Machine Learning (ICML), 2022
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 …
Node and Edge Eigenvector Centrality for Hypergraphs
Communications Physics, vol. 4:201, 2021
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 …
Nonlinear Higher-Order Label Spreading
The Web Conference (WWW), pp. 2402–2413, 2021
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 …
A framework for second order eigenvector centralities and clustering coefficients
Proceedings of the Royal Society A, vol. 476, pp. 20190724, 2020
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 …