Preprints

On the Notion of Weak Isometry for Finite Metric Spaces
A. De Gregorio, U. Fugacci, F. Memoli, F. Vaccarino
Under submission, preprint available at arXiv.org
[arXiv]

Abstract Finite metric spaces are the object of study in many data analysis problems. We examine the concept of weak isometry between finite metric spaces, in order to analyse properties of the spaces that are invariant under strictly increasing rescaling of the distance functions. In this paper, we analyse some of the possible complete and incomplete invariants for weak isometry and we introduce a dissimilarity measure that asses how far two spaces are from being weakly isometric. Furthermore, we compare these ideas with the theory of persistent homology, to study how the two are related.

Multiparameter Persistent Homology for Shape Analysis
U. Fugacci, F. Iuricich, S. Scaramuccia, L. De Floriani
Under submission

Abstract Topological data analysis has proved to be a promising tool for shape analysis. Topological descriptors can be extracted from a shape using multiple functions and, instead of considering each function independently, one could group them in a single vector-valued function. Building a descriptor for a multivariate function allows representing features that are generally missed when working with the functions one by one. This idea is made practicable by multiparameter persistent homology, a new tool in topological data analysis. In this work, we provide an overview of the theoretical guarantees provided by multiparameter persistent homology and review and analyse available algorithms and techniques with a specific focus on shape analysis.

2022

Persistent Homology: a Topological Tool for Higher-Interaction Systems
F. Vaccarino, U. Fugacci, S. Scaramuccia
In Higher-Order Systems, Springer International Publishing, pages 97-139, 2022
[bibtex] [doi]

Abstract The aim of this chapter is to give a handy but thorough introduction to persistent homology and its applications. The chapter's path is made by the following steps. First, we deal with the constructions from data to simplicial complexes according to the kind of data: filtrations of data, point clouds, networks, and topological spaces. For each construction, we underline the possible dependence on a fixed scale parameter. Secondly, we introduce the necessary algebraic structures capturing topological informations out of a simplicial complex at a fixed scale, namely the simplicial homology groups and the Hodge Laplacian operator. The so-obtained linear structures are then integrated into the multiscale framework of persistent homology where the entire persistence information is encoded in algebraic terms and the most advantageous persistence summaries available in the literature are discussed. Finally, we introduce the necessary metrics in order to state properties of stability of the introduced multiscale summaries under perturbations of input data. At the end, we give an overview of applications of persistent homology as well as a review of the existing tools in the broader area of Topological Data Analysis (TDA).

Chanalyzer: a Computational Geometry Approach for the Analysis of Protein Channel Shape and Dynamics
A. Raffo, L. Gagliardi, U. Fugacci, L. Sagresti, S. Grandinetti, G. Brancato, S. Biasotti, W. Rocchia
In Frontiers in Molecular Biosciences, vol. 9, 2022
[bibtex] [doi] [code]

Abstract Morphological analysis of protein channels is a key step for a thorough understanding of their biological function and mechanism. In this respect, molecular dynamics (MD) is a very powerful tool, enabling the description of relevant biological events at the atomic level, which might elude experimental observations, and pointing to the molecular determinants thereof. In this work, we present a computational geometry-based approach for the characterization of shape and dynamics of biological ion channels or pores to be used in combination with MD trajectories. This technique relies on the earliest works of Edelsbrunner and on the NanoShaper software, which makes use of the alpha shapes theory to build the solvent excluded surface of a molecular system in aqueous solution. In this framework, a channel can be simply defined as a cavity with two entrances on the opposite sides of a molecule. Morphological characterization, which includes identification of the main axis, the corresponding local radius, and the detailed description of the global shape of the cavity, is integrated with a physico-chemical description of the surface facing the pore lumen. Remarkably, the possible existence or temporarily appearance of fenestrations from channel interior towards the outer lipid matrix is also accounted. As a test case, we applied the present approach to the analysis of an engineered protein channel, the mechanosensitive channel of large conductance.

Compression for 2-Parameter Persistent Homology
U. Fugacci, M. Kerber, A. Rolle
In Computational Geometry, page 101940, 2022
[bibtex] [doi] [code] [arXiv]

Abstract Compression aims to reduce the size of an input, while maintaining its relevant properties. For multi-parameter persistent homology, compression is a necessary step in any computational pipeline, since standard constructions lead to large inputs, and computational tasks in this area tend to be expensive. We propose two compression methods for chain complexes of free 2-parameter persistence modules. The first method extends the multi-chunk algorithm for one-parameter persistent homology, returning the smallest chain complex among all the ones quasi-isomorphic to the input. The second method produces minimal presentations of the homology of the input; it is based on an algorithm of Lesnick and Wright, but incorporates several improvements that lead to substantial performance gains. The two methods are complementary, and can be combined to compute minimal presentations for complexes with millions of generators in a few seconds. The methods have been implemented, and the software is publicly available. We report on experimental evaluations, which demonstrate substantial improvements in performance compared to previously available compression strategies.

SHREC 2022: Protein-Ligand Binding Site Recognition
L. Gagliardi, A. Raffo, U. Fugacci, S. Biasotti, W. Rocchia, et al.
In Computers and Graphics, vol. 107, pages 20-31, 2022
[bibtex] [doi] [slides] [code] [arXiv]

Abstract This paper presents the methods that have participated in the SHREC 2022 contest on protein-ligand binding site recognition. The prediction of protein-ligand binding regions is an active research domain in computational biophysics and structural biology and plays a relevant role for molecular docking and drug design. The goal of the contest is to assess the effectiveness of computational methods in recognizing ligand binding sites in a protein based on its geometrical structure. Performances of the segmentation algorithms are analyzed according to two evaluation scores describing the capacity of a putative pocket to contact a ligand and to pinpoint the correct binding region. Despite some methods perform remarkably, we show that simple non-machine-learning approaches remain very competitive against data-driven algorithms. In general, the task of pocket detection remains a challenging learning problem which suffers of intrinsic difficulties due to the lack of negative examples (data imbalance problem).

2021

Homological Scaffold via Minimal Homology Bases
M. Guerra, A. De Gregorio, U. Fugacci, G. Petri, F. Vaccarino
In Scientific Reports, vol. 11(1), page 5355, 2021
[bibtex] [doi] [poster] [arXiv]

Abstract The homological scaffold leverages persistent homology to construct a topologically sound summary of a weighted network. However, its crucial dependency on the choice of representative cycles hinders the ability to trace back global features onto individual network components, unless one provides a principled way to make such a choice. In this paper, we apply recent advances in the computation of minimal homology bases to introduce a quasi-canonical version of the scaffold, called minimal, and employ it to analyze data both real and in silico. At the same time, we verify that, statistically, the standard scaffold is a good proxy of the minimal one for sufficiently complex networks.

Design Optimization of Renewable Energy Systems for NZEBs based on Deep Residual Learning
M. Ferrara, F. Della Santa, M. Bilardo, A. De Gregorio, A. Mastropietro, U. Fugacci, F. Vaccarino, E. Fabrizio
In Renewable Energy, vol. 176, pages 590-605, 2021
[bibtex] [doi]

Abstract The design of renewable energy systems for Nearly Zero Energy Buildings (NZEB) is a complex optimization problem. In recent years, simulation-based optimization has demonstrated to be able to support the search for optimal design, but improvements to the method that are able to reduce the high computation time are needed. This study presents a new approach based on deep residual learning to make the search for optimal design solutions more efficient. It is applied to the problem of system design optimization for an Italian multi-family building case-study equipped with a solar cooling system. Given a design space defined by set of variables related to Heating, Ventilation and Air Conditioning systems (HVAC) and renewable systems, a machine learning method based on residual neural networks to predict and minimize the objective function characterizing non-renewable primary energy consumptions is proposed. Results have shown that the approach is able to successfully identify optimized design solutions (energy performance improved by 47%) with good prediction accuracy (error smaller than 3%) while reducing the overall computation time and maximizing the exploration of the design space, paving the way for further advancements in simulation-based optimization for NZEB design.

SHREC 2021: Retrieval and Classification of Protein Surfaces Equipped with Physical and Chemical Properties
A. Raffo, U. Fugacci, S. Biasotti, W. Rocchia, et al.
In Computers and Graphics, vol. 99, pages 1-21, 2021
[bibtex] [doi] [slides] [video] [code] [arXiv]

Abstract This paper presents the methods that have participated in the SHREC 2021 contest on retrieval and classification of protein surfaces on the basis of their geometry and physicochemical properties. The goal of the contest is to assess the capability of different computational approaches to identify different conformations of the same protein, or the presence of common sub-parts, starting from a set of molecular surfaces. We addressed two problems: defining the similarity solely based on the surface geometry or with the inclusion of physicochemical information, such as electrostatic potential, amino acid hydrophobicity, and the presence of hydrogen bond donors and acceptors. Retrieval and classification performances, with respect to the single protein or the existence of common sub-sequences, are analysed according to a number of information retrieval indicators.

2020

Topology-Preserving Terrain Simplification
U. Fugacci, M. Kerber, H. Manet
In 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 36-47, 2020
[bibtex] [doi] [slides] [poster] [video] [code] [arXiv]

Abstract We give necessary and sufficient criteria for elementary operations in a two-dimensional terrain to preserve the persistent homology induced by the height function. These operations are edge flips and removals of interior vertices, re-triangulating the link of the removed vertex. This problem is motivated by topological terrain simplification, which means removing as many critical vertices of a terrain as possible while maintaining geometric closeness to the original surface. Existing methods manage to reduce the maximal possible number of critical vertices, but increase thereby the number of regular vertices. Our method can be used to post-process a simplified terrain, drastically reducing its size and preserving its favorable properties.

Application of Deep Learning to Design Renewable Energy Systems for a Zero Energy Multifamily Building
F. Della Santa, M. Ferrara, M. Bilardo, A. De Gregorio, U. Fugacci, A. Mastropietro, E. Fabrizio, F. Vaccarino
In 15th Conference on Sustainable Development of Energy, Water and Environment Systems, 2020
[bibtex] [doi]

Abstract The Zero Energy Building design, briefly, ZEB design, is a complex optimization problem. In recent years, simulation-based optimization has demonstrated to be able to support the search for optimal design, but improvements to the method that are able to reduce the high computation are needed. This paper presents a new approach to speed up the search for optimal ZEB design solutions based on deep learning. It is applied to the problem of system design optimization for an Italian multi-family building case-study. More specifically, given a set of variables related to HVAC and renewables for describing the design space, a machine learning method that learns how to predict the objective function characterizing non-renewable primary energy consumptions is proposed. Results have shown that the approach is able to successfully drive towards optimized design (energy performance improved by 47%) while maintaining a good level of accuracy of the energy performance (error smaller than 3%) with less time and the exhaustive exploration of the design space.

Betti Splitting from a Topological Point of View
D. Bolognini, U. Fugacci
In Journal of Algebra and Its Applications, vol. 19(6), page 2050116, 2020
[bibtex] [doi] [code] [arXiv]

Abstract A Betti splitting I = J + K of a monomial ideal I ensures the recovery of the graded Betti numbers of I starting from those of J,K and J ∩ K. In this paper, we introduce an analogous notion for simplicial complexes, using Alexander duality, proving that it is equivalent to a recursive splitting condition on links of some vertices. We provide results ensuring the existence of a Betti splitting for a simplicial complex Δ, relating it to topological properties of Δ. Among other things, we prove that orientability for a manifold without boundary is equivalent to the admission of a Betti splitting induced by the removal of a single facet. Taking advantage of our topological approach, we provide the first example of a monomial ideal which admits Betti splittings in all characteristics but with characteristic-dependent resolution. Moreover, we introduce new numerical descriptors for simplicial complexes and topological spaces, useful to deal with questions concerning the existence of Betti splitting.

Efficient Homology-Preserving Simplification of High-Dimensional Simplicial Shapes
R. Fellegara, F. Iuricich, L. De Floriani, U. Fugacci
In Computer Graphics Forum, vol. 39(1), pages 244-259, 2020
[bibtex] [doi] [video]

Abstract Simplicial complexes are widely used to discretize shapes. In low dimensions, a 3D shape is represented by discretizing its boundary surface, encoded as a triangle mesh, or by discretizing the enclosed volume, encoded as a tetrahedral mesh. High-dimensional simplicial complexes have recently found their application in topological data analysis. Topological data analysis aims at studying a point cloud P, possibly embedded in a high-dimensional metric space, by investigating the topological characteristics of the simplicial complexes built on P. Analyzing such complexes is not feasible due to their size and dimensions. To this aim, the idea of simplifying a complex while preserving its topological features has been proposed in the literature. Here, we consider the problem of efficiently simplifying simplicial complexes in arbitrary dimensions. We provide a new definition for the edge contraction operator, based on a top-based data structure, with the objective of preserving structural aspects of a simplicial shape (i.e., its homology), and a new algorithm for verifying the link condition on a top-based representation. We implement the simplification algorithm obtained by coupling the new edge contraction and the link condition on a specific top-based data structure, that we use to demonstrate the scalability of our approach.

Critical Sets of PL and Discrete Morse Theory: a Correspondence
U. Fugacci, C. Landi, H. Varli
In Computers and Graphics, vol. 90, pages 43-50, 2020
[bibtex] [doi] [slides] [video] [arXiv]

Abstract Piecewise-linear (PL) Morse theory and discrete Morse theory are used in shape analysis tasks to investigate the topological features of discretized spaces. In spite of their common origin in smooth Morse theory, various notions of critical points have been given in the literature for the discrete setting, making a clear understanding of the relationships occurring between them not obvious. This paper aims at providing equivalence results about critical points of the two discretized Morse theories. First of all, we prove the equivalence of the existing notions of PL critical points. Next, under an optimality condition called relative perfectness, we show a dimension agnostic correspondence between the set of PL critical points and that of discrete critical simplices of the combinatorial approach. Finally, we show how a relatively perfect discrete gradient vector field can be algorithmically built up to dimension 3. This way, we guarantee a formal and operative connection between critical sets in the PL and discrete theories.

2019

Chunk Reduction for Multi-Parameter Persistent Homology
U. Fugacci, M. Kerber
In 35th International Symposium on Computational Geometry, vol. 129, pages 37:1-37:14, 2019
[bibtex] [doi] [slides] [code] [arXiv]

Abstract The extension of persistent homology to multi-parameter setups is an algorithmic challenge. Since most computation tasks scale badly with the size of the input complex, an important pre-processing step consists of simplifying the input while maintaining the homological information. We present an algorithm that drastically reduces the size of an input. Our approach is an extension of the chunk algorithm for persistent homology (Bauer et al., Topological Methods in Data Analysis and Visualization III, 2014). We show that our construction produces the smallest multi-filtered chain complex among all the complexes quasi-isomorphic to the input, improving on the guarantees of previous work in the context of discrete Morse theory. Our algorithm also offers an immediate parallelization scheme in shared memory. Already its sequential version compares favorably with existing simplification schemes, as we show by experimental evaluation.

A Kernel for Multi-Parameter Persistent Homology
R. Corbet, U. Fugacci, M. Kerber, C. Landi, B. Wang
In Computer and Graphics, vol. 2, page 100005, 2019
[bibtex] [doi] [poster] [video] [arXiv]

Awarded as Best Paper at SMI 2019
Abstract Topological data analysis and its main method, persistent homology, provide a toolkit for computing topological information of high-dimensional and noisy data sets. Kernels for one-parameter persistent homology have been established to connect persistent homology with machine learning techniques with applicability on shape analysis, recognition and classification. We contribute a kernel construction for multi-parameter persistence by integrating a one-parameter kernel weighted along straight lines. We prove that our kernel is stable and efficiently computable, which establishes a theoretical connection between topological data analysis and machine learning for multivariate data analysis.

Computing Discrete Morse Complexes from Simplicial Complexes
U. Fugacci, F. Iuricich, L. De Floriani
In Graphical Models, vol. 103, page 101023, 2019
[bibtex] [doi] [arXiv]

Abstract We consider the problem of efficiently computing a discrete Morse complex on simplicial complexes of arbitrary dimension and very large size. Based on a common graph-based formalism, we analyze existing data structures for simplicial complexes, and we define an efficient encoding for the discrete Morse gradient on the most compact of such representations. We theoretically compare methods based on reductions and coreductions for computing a discrete Morse gradient, proving that the combination of reductions and coreductions produces new mutually equivalent approaches. We design and implement a new algorithm for computing a discrete Morse complex on simplicial complexes. We show that our approach scales very well with the size and the dimension of the simplicial complex also through comparisons with the only existing public-domain algorithm for discrete Morse complex computation. We discuss applications to the computation of multi-parameter persistent homology and of extremum graphs for visualization of time-varying 3D scalar fields.

2018

Clique Community Persistence: a Topological Visual Analysis Approach for Complex Networks
B. Rieck, U. Fugacci, J. Lukasczyk, H. Leitte
In IEEE Transactions on Visualization and Computer Graphics, vol. 24(1), pages 822-831, 2018
[bibtex] [doi] [slides] [video] [short video] [code] [other]

Abstract Complex networks require effective tools and visualizations for their analysis and comparison. Clique communities have been recognized as a powerful concept for describing cohesive structures in networks. We propose an approach that extends the computation of clique communities by considering persistent homology, a topological paradigm originally introduced to characterize and compare the global structure of shapes. Our persistence-based algorithm is able to detect clique communities and to keep track of their evolution according to different edge weight thresholds. We use this information to define comparison metrics and a new centrality measure, both reflecting the relevance of the clique communities inherent to the network. Moreover, we propose an interactive visualization tool based on nested graphs that is capable of compactly representing the evolving relationships between communities for different thresholds and clique degrees. We demonstrate the effectiveness of our approach on various network types.

2016

Persistent Homology: a Step-by-Step Introduction for Newcomers
U. Fugacci, S. Scaramuccia, F. Iuricich, L. De Floriani
In Smart Tools and Apps for Graphics - Eurographics Italian Chapter Conference, 2016
[bibtex] [doi] [slides] [video] [code] [other]

Abstract Persistent homology is a powerful notion rooted in topological data analysis which allows for retrieving the essential topological features of an object. The attention on persistent homology is constantly growing in a large number of application domains, such as biology and chemistry, astrophysics, automatic classification of images, sensor and social network analysis. Thus, an increasing number of researchers is now approaching to persistent homology as a tool to be used in their research activity. At the same time, the literature lacks of tools for introducing beginners to this topic, especially if they do not have a strong mathematical background in algebraic topology. We propose here two complementary tools which meet this requirement. The first one is a web-based user-guide equipped with interactive examples to facilitate the comprehension of the notions at the basis of persistent homology. The second one is an interactive tool, with a specific focus on shape analysis, developed for studying persistence pairs by visualizing them directly on the input complex.

Analysis of Geolocalized Social Networks based on Simplicial Complexes
R. Fellegara, U. Fugacci, F. Iuricich, L. De Floriani
In 9th ACM SIGSPATIAL International Workshop on Location-Based Social Networks (LSBN), pages 5:1-5:8, 2016
[bibtex] [doi]

Abstract A common issue in network analysis consists in the detection and characterization of the key vertices and communities. To this purpose, visualization tools could be of great help to support domain experts in analyzing this kind of data. However, the size of real networks can seriously affect the practical usage of these tools, thus, requiring the definition of suitable simplification procedures that preserve the core network information. In this work, we focus on geolocalized social networks, and we describe a tool for the analysis of this kind of data based on topological information. Supported by recent trends in network analysis, our approach uses simplicial complexes as a model for social networks. A homology-preserving simplification is used for dealing with the data complexity and for reducing the information to be visualized to the essential. By combining the representation based on simplicial complexes and the simplification tool, we can efficiently retrieve topological information useful for the network analysis. Both the effectiveness and scalability of our approach are experimentally demonstrated.

Homological Shape Analysis through Discrete Morse Theory
L. De Floriani, U. Fugacci, F. Iuricich
In Perspectives in Shape Analysis, Springer Berlin Heidelberg, pages 187-209, 2016
[bibtex] [doi]

Abstract Homology and persistent homology computation are fundamental tools for shape analysis and understanding that recently gathered a lot of interest, in particular for analyzing multidimensional data. In this context discrete Morse theory, a combinatorial counterpart of smooth Morse theory, provides an excellent basis for reducing computational complexity in homology detection. A discrete Morse complex, computed over a given complex discretizing a shape, drastically reduces the number of cells of the latter while maintaining the same homology. Here, we consider the problem of shape analysis through discrete Morse theory, and we review and analyze algorithms for computing homology and persistent homology based on such theory.

2015

Topologically-Consistent Simplification of Discrete Morse Complex
F. Iuricich, U. Fugacci, L. De Floriani
In Computer and Graphics, vol. 51, pages 157 - 166, 2015
[bibtex] [doi] [slides]

Awarded with a Honorable Mention at SMI 2015
Abstract We address the problem of simplifying Morse–Smale complexes computed on volume datasets based on discrete Morse theory. Two approaches have been proposed in the literature based on a graph representation of the Morse–Smale complex (explicit approach) and on the encoding of the discrete Morse gradient (implicit approach). It has been shown that this latter can generate topologically-inconsistent representations of the Morse–Smale complex with respect to those computed through the explicit approach. We propose a new simplification algorithm that creates topologically-consistent Morse–Smale complexes and works both with the explicit and the implicit representations. We prove the correctness of our simplification approach, implement it on volume data sets described as unstructured tetrahedral meshes and evaluate its simplification power with respect to the usual Morse simplification algorithm.

Morse Complexes for Shape Segmentation and Homological Analysis: Discrete Models and Algorithms
L. De Floriani, U. Fugacci, F. Iuricich, P. Magillo
In Computer Graphics Forum, vol. 34(2), pages 761-785, 2015
[bibtex] [doi] [slides]

Abstract Morse theory offers a natural and mathematically-sound tool for shape analysis and understanding. It allows studying the behavior of a scalar function defined on a manifold. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the function. Such decompositions, called Morse complexes, provide a segmentation of a shape and are extensively used in terrain modeling and in scientific visualization. Discrete Morse theory, a combinatorial counterpart of smooth Morse theory defined over cell complexes, provides an excellent basis for computing Morse complexes in a robust and efficient way. Moreover, since a discrete Morse complex computed over a given complex has the same homology as the original one, but fewer cells, discrete Morse theory is a fundamental tool for efficiently detecting holes in shapes through homology and persistent homology. In this survey, we review, classify and analyze algorithms for computing and simplifying Morse complexes in the context of such applications with an emphasis on discrete Morse theory and on algorithms based on it.

2014

Topological Modifications and Hierarchical Representation of Cell Complexes in Arbitrary Dimensions
L. Comic, L. De Floriani, F. Iuricich, U. Fugacci
In Computer Vision and Image Understanding, vol. 121, pages 2-12, 2014
[bibtex] [doi] [poster]

Abstract We propose a set of atomic modeling operators for simplifying and refining cell complexes in arbitrary dimensions. Such operators either preserve the homology of the cell complex, or they modify it in a controlled way. We show that such operators form a minimally complete basis for updating cell complexes, and we compare them with various operators previously proposed in the literature. Based on the new operators, we define a hierarchical model for cell complexes, that we call a Hierarchical Cell Complex (HCC), and we discuss its properties. An HCC implicitly encodes a virtually continuous set of complexes obtained from the original complex through the application of our operators. Then, we describe the implementation of a version of the HCC based on the subset of the proposed modeling operators which preserve homology. We apply the homology-preserving HCC to enhance the efficiency in extracting homology generators at different resolutions. To this aim, we propose an algorithm which computes homology generators on the coarsest representation of the original complex, and uses the hierarchical model to propagate them to complexes at any intermediate resolution, and we prove its correctness. Finally, we present experimental results showing the efficiency and effectiveness of the proposed approach.

Efficient Computation of Simplicial Homology Through Acyclic Matching
U. Fugacci, L. De Floriani, F. Iuricich
In 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2014), pages 587-593, 2014
[bibtex] [doi] [slides]

Abstract We consider the problem of efficiently computing homology with Z coefficients as well as homology generators for simplicial complexes of arbitrary dimension. We analyze, compare and discuss the equivalence of different methods based on combining reductions, coreductions and discrete Morse theory. We show that the combination of these methods produces theoretically sound approaches which are mutually equivalent. One of these methods has been implemented for simplicial complexes by using a compact data structure for representing the complex and a compact encoding of the discrete Morse gradient. We present experimental results and discuss further developments.