BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Facundo Mémoli

Facundo Mémoli contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Geometrymath.ATMachine Learningmath.MGmath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and its Applications

The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval $I$ of a $\mathbb{Z}^2$-indexed persistence module $M$ is equal to the generalized rank of the zigzag module that is induced on a certain path in $I$ tracing mostly its boundary. Hence, we can compute the generalized rank over $I$ by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing $M$ to that path. If the bifiltration and $I$ have at most $t$ simplices and points respectively, this computation takes $O(t^ω)$ time where $ω\in[2,2.373)$ is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module $M$, determine whether $M$ is interval decomposable and, if so, compute all intervals supporting its summands.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distance distributions and inverse problems for metric measure spaces

Applications in data science, shape analysis and object classification frequently require comparison of probability distributions defined on different ambient spaces. To accomplish this, one requires a notion of distance on a given class of metric measure spaces -- that is, compact metric spaces endowed with probability measures. Such distances are typically defined as comparisons between metric measure space invariants, such as distance distributions (also referred to as shape distributions, distance histograms or shape contexts in the literature). Generally, distances defined in terms of distance distributions are actually pseudometrics, in that they may vanish when comparing nonisomorphic spaces. The goal of this paper is to set up a formal framework for assessing the discrimininative power of distance distributions, i.e., the extend to which these pseudometrics fail to define proper metrics. We formulate several precise inverse problems in terms of these invariants and answer them in several categories of metric measure spaces, including the category of plane curves, where we give a counterexample to the Curve Histogram Conjecture of Brinkman and Olver, the categories of embedded and Riemannian manifolds, where we obtain sphere rigidity results, and the category of metric graphs, where we obtain a local injectivity result along the lines of classical work of Boutin and Kemper on point cloud configurations. The inverse problems are further contextualized by the introduction of a variant of the Gromov-Wasserstein distance on the space of metric measure spaces, which is inspired by the original Monge formulation of optimal transport.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Extracting Persistent Clusters in Dynamic Data via Möbius inversion

Identifying and representing clusters in time-varying network data is of particular importance when studying collective behaviors emerging in nature, in mobile device networks or in social networks. Based on combinatorial, categorical, and persistence theoretic viewpoints, we establish a stable functorial pipeline for the summarization of the evolution of clusters in a time-varying network. We first construct a complete summary of the evolution of clusters in a given time-varying network over a set of entities $X$ of which takes the form of a formigram. This formigram can be understood as a certain Reeb graph $\mathcal{R}$ which is labeled by subsets of $X$. By applying Möbius inversion to the formigram in two different manners, we obtain two dual notions of diagram: the maximal group diagram and the persistence clustergram, both of which are in the form of an `annotated' barcode. The maximal group diagram consists of time intervals annotated by their corresponding maximal groups -- a notion due to Buchin et al., implying that we recognize the notion of maximal groups as a special instance of generalized persistence diagram by Patel. On the other hand, the persistence clustergram is mostly obtained by annotating the intervals in the zigzag barcode of the Reeb graph $\mathcal{R}$ with certain merging/disbanding events in the given time-varying network. We show that both diagrams are complete invariants of formigrams (or equivalently of trajectory grouping structure by Buchin et al.) and thus contain more information than the Reeb graph $\mathcal{R}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Interleaving by Parts: Join Decompositions of Interleavings and Join-Assemblage of Geodesics

Metrics of interest in topological data analysis (TDA) are often explicitly or implicitly in the form of an interleaving distance $d_{\mathrm{I}}$ between poset maps (i.e. order-preserving maps), e.g. the Gromov-Hausdorff distance between metric spaces can be reformulated in this way. We propose a representation of a poset map $\mathbf{F}:\mathcal{P}\to\mathcal{Q}$ as a join (i.e. supremum) $\bigvee_{b\in B} \mathbf{F}_b$ of simpler poset maps $\mathbf{F}_b$ (for a join dense subset $B\subset \mathcal{Q}$) which in turn yields a decomposition of $d_{\mathrm{I}}$ into a product metric. The decomposition of $d_{\mathrm{I}}$ is simple, but its ramifications are manifold: (1) We can construct a geodesic path between any poset maps $\mathbf{F}$ and $\mathbf{G}$ with $d_{\mathrm{I}}(\mathbf{F},\mathbf{G})<\infty$ by assembling geodesics between all $\mathbf{F}_b$s and $\mathbf{G}_b$s via the join operation. This construction generalizes at least three constructions of geodesic paths that have appeared in the literature. (2) We can extend the Gromov-Hausdorff distance to a distance between simplicial filtrations over an arbitrary poset with a flow, preserving its universality and geodesicity. (3) We can clarify equivalence between several known metrics on multiparameter hierarchical clusterings. (4) We can illuminate the relationship between the erosion distance by Patel and the graded rank function by Betthauser, Bubenik, and Edwards, which in turn takes us to an interpretation on the representation $\bigvee_b \mathbf{F}_b$ as a generalization of persistence landscapes and graded rank functions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Persistent Homotopy Groups of Metric Spaces

We study notions of persistent homotopy groups of compact metric spaces together with their stability properties in the Gromov-Hausdorff sense. We pay particular attention to the case of fundamental groups, for which we obtain a more precise description. Under fairly mild assumptions on the spaces, we proved that the classical fundamental group has an underlying tree-like structure (i.e. a dendrogram) and an associated ultra-metric.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Persistent Laplacians: properties, algorithms and implications

We present a thorough study of the theoretical properties and devise efficient algorithms for the \emph{persistent Laplacian}, an extension of the standard combinatorial Laplacian to the setting of pairs (or, in more generality, sequences) of simplicial complexes $K \hookrightarrow L$, which was independently introduced by Lieutier et al. and by Wang et al. In particular, in analogy with the non-persistent case, we first prove that the nullity of the $q$-th persistent Laplacian $Δ_q^{K,L}$ equals the $q$-th persistent Betti number of the inclusion $(K \hookrightarrow L)$. We then present an initial algorithm for finding a matrix representation of $Δ_q^{K,L}$, which itself helps interpret the persistent Laplacian. We exhibit a novel relationship between the persistent Laplacian and the notion of Schur complement of a matrix which has several important implications. In the graph case, it both uncovers a link with the notion of effective resistance and leads to a persistent version of the Cheeger inequality. This relationship also yields an additional, very simple algorithm for finding (a matrix representation of) the $q$-th persistent Laplacian which in turn leads to a novel and fundamentally different algorithm for computing the $q$-th persistent Betti number for a pair $(K,L)$ which can be significantly more efficient than standard algorithms. Finally, we study persistent Laplacians for simplicial filtrations and present novel stability results for their eigenvalues. Our work brings methods from spectral graph theory, circuit theory, and persistent homology together with a topological view of the combinatorial Laplacian on simplicial complexes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Weisfeiler-Lehman meets Gromov-Wasserstein

The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we propose the Weisfeiler-Lehman (WL) distance, a notion of distance between labeled measure Markov chains (LMMCs), of which labeled graphs are special cases. The WL distance is polynomial time computable and is also compatible with the WL test in the sense that the former is positive if and only if the WL test can distinguish the two involved graphs. The WL distance captures and compares subtle structures of the underlying LMMCs and, as a consequence of this, it is more discriminating than the distance between graphs used for defining the state-of-the-art Wasserstein Weisfeiler-Lehman graph kernel. Inspired by the structure of the WL distance we identify a neural network architecture on LMMCs which turns out to be universal w.r.t. continuous functions defined on the space of all LMMCs (which includes all graphs) endowed with the WL distance. Finally, the WL distance turns out to be stable w.r.t. a natural variant of the Gromov-Wasserstein (GW) distance for comparing metric Markov chains that we identify. Hence, the WL distance can also be construed as a polynomial time lower bound for the GW distance which is in general NP-hard to compute.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Gaussian Transform

We introduce the Gaussian transform (GT), an optimal transport inspired iterative method for denoising and enhancing latent structures in datasets. Under the hood, GT generates a new distance function (GT distance) on a given dataset by computing the $\ell^2$-Wasserstein distance between certain Gaussian density estimates obtained by localizing the dataset to individual points. Our contribution is twofold: (1) theoretically, we establish firstly that GT is stable under perturbations and secondly that in the continuous case, each point possesses an asymptotically ellipsoidal neighborhood with respect to the GT distance; (2) computationally, we accelerate GT both by identifying a strategy for reducing the number of matrix square root computations inherent to the $\ell^2$-Wasserstein distance between Gaussian measures, and by avoiding redundant computations of GT distances between points via enhanced neighborhood mechanisms. We also observe that GT is both a generalization and a strengthening of the mean shift (MS) method, and it is also a computationally efficient specialization of the recently proposed Wasserstein Transform (WT) method. We perform extensive experimentation comparing their performance in different scenarios.

0 citations0 reviewsNo code linkedOpen access