Interesting paths in the mapper complex

Given a high dimensional point cloud of data with functions defined on the points, the mapper algorithm produces a compact summary in the form of a simplicial complex connecting the points. This summary offers insightful data visualizations, which have been employed in applications to identify subsets of points, i.e., subpopulations, with interesting properties. These subpopulations typically appear as long paths, flares (i.e., branching paths), or loops in the mapper complex. We study the problem of quantifying the interestingness of subpopulations in a given mapper complex. First, we create a weighted directed graph G=(V,E) using the 1-skeleton of the mapper complex. We use the average values at the vertices (i.e., clusters) of the target function (i.e., a dependent variable) to direct the edges from low to high values. We set the difference between the average values at the vertices (high-low) as the weight of the edge. Covariation of the remaining h functions (i.e., independent variables) is captured by a h-bit binary signature assigned to the edge. An interesting path in G is a directed path whose edges all have the same signature. Further, we define the interestingness score of such a path as a sum of its edge weights multiplied by a nonlinear function of their corresponding ranks, i.e., the depths of the edges along the path. Such a nonlinear function could model application use-cases where the growth in the dependent variable values is expected to be concentrated in specific intervals of a path, e.g., plant growth accelerating later in the season, or a terminally ill patient's health condition deteriorating rapidly toward the end. Second, we study three optimization problems on this graph G to quantify interesting subpopulations. In the problem MaxIP, the goal is to find the most interesting path in G, i.e., an interesting path with the maximum interestingness score. For the case where G is a directed acyclic graph (DAG), which could be a typical setting in many applications, we show that MaxIP can be solved in polynomial time---in O(mnd_in) time and O(mn) space, where m,n, and d_in are the numbers of edges, vertices, and the maximum indegree of a vertex in G, respectively. In the more general problem IP, the goal is to find a collection of interesting paths that are edge-disjoint, and the sum of interestingness scores of all paths is maximized. We also study a variant of IP termed k-IP, where the goal is to identify a collection of edge-disjoint interesting paths each with k edges, and the total interestingness score of all paths is maximized. While k-IP can be solved in polynomial time for k <= 2, we show k-IP is NP-complete for k >= 3 even when G is a DAG. We develop heuristics for IP and k-IP on DAGs, which use the algorithm for MaxIP on DAGs as a subroutine, and run in O(mnd_in) and O(mkd_in) time for IP and k-IP, respectively.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.