Construct Gradient Flow Graph from Merged Basins

Constructs the gradient flow graph, which is the 1-skeleton of the nerve simplicial complex associated with a collection of merged basins of attraction. This graph captures the topological structure of how basins cover the point set through their vertex intersections.

Usage

construct.gflow.graph(
  merged.basins,
  min.intersection = 1,
  edge.type = c("all", "ms_only", "same_type")
)

Arguments

merged.basins

An object of class "basins_of_attraction" returned by merge.clustered.basins containing merged basin structures. This object should have both ascending and descending basins merged according to their clustering. The function works with the basin structure after both maximum and minimum clustering and merging have been performed.

min.intersection

Integer specifying the minimum number of shared vertices required for an edge to appear in the gradient flow graph. Default is 1, meaning any nonempty intersection creates an edge. Larger values filter out weak connections and focus on more substantial basin overlaps.

edge.type

Character string specifying which types of edges to include in the graph. Options are:

"all": Include all edges between any pair of basins with sufficient intersection (default).
"ms_only": Include only Morse-Smale edges connecting ascending (minimum) basins to descending (maximum) basins, creating a bipartite graph that captures saddle connections.
"same_type": Include only edges between basins of the same type, either both ascending or both descending, revealing competition within extrema of the same orientation.

Value

An object of class "gflow_graph" containing:

adjacency.list

List of integer vectors representing the graph adjacency structure. Each element corresponds to a basin vertex and contains indices of adjacent basins in the gradient flow graph. Indices refer to positions in the combined vertex list (ascending basins followed by descending basins).

weight.list

List of numeric vectors representing edge weights. Each weight equals the number of shared vertices between the corresponding basin pair, normalized by the size of the smaller basin to give a similarity measure.

intersection.matrix

Symmetric matrix where entry (i,j) records the number of vertices shared between basin i and basin j. Diagonal entries give basin sizes. This matrix provides complete information about pairwise basin overlaps.

basin.metadata

Data frame with one row per basin vertex containing:

index: Sequential index in the combined vertex list.
label: Basin label (e.g., "m1", "M2") from the merged basin structure.
type: Basin type, either "ascending" for minima or "descending" for maxima.
size: Number of vertices in the basin.
extremum.vertex: 1-based vertex index of the basin's extremum.
extremum.value: Function value at the extremum.

n.ascending

Number of ascending basin vertices in the graph.

n.descending

Number of descending basin vertices in the graph.

edge.type

Character string recording which edge type was used.

min.intersection

Integer recording the minimum intersection threshold used.

Details

Consider a collection of basins, each representing a region of the graph where the function exhibits monotonic behavior toward a local extremum. These basins form a covering of the vertex set, though not necessarily a disjoint one. Two basins may share vertices, particularly near boundaries where the gradient flow exhibits ambiguous behavior or where noise in the data creates overlapping influence regions.

We begin with a fundamental construction from algebraic topology. Given any covering of a space by open sets, the nerve complex records which collections of sets have nonempty intersection. A vertex in the nerve corresponds to each set in the covering, and a simplex appears whenever the corresponding sets intersect. This construction preserves essential topological information about the covering and, under suitable conditions, about the underlying space itself.

For our gradient flow basins, the nerve complex takes a particularly natural form. Each basin becomes a vertex in the complex. An edge connects two vertices when the corresponding basins share at least one point from the original graph. Higher dimensional simplices would appear when three or more basins have common vertices, but for the gradient flow graph we focus only on the 1-skeleton, which captures the essential connectivity structure.

The motivation for studying this 1-skeleton becomes clear when we consider the problem of understanding function structure on discrete graphs. Local extrema and their basins fragment the space into regions of monotonic behavior. The gradient flow graph reveals how these fragments connect, which basins border each other, and ultimately the large-scale structure of the function landscape. An edge in this graph indicates that gradient flow from different extrema can reach a common region, suggesting either a saddle point connection or a region where multiple basins compete for influence.

The construction proceeds in three stages. First, we extract the vertex sets from all basins, both ascending and descending. Second, we compute pairwise intersections between all basin vertex sets to identify which pairs share vertices. Third, we build the graph adjacency structure, creating an edge between basins whenever their intersection is nonempty. The resulting graph encodes the combinatorial structure of the basin covering, with edge weights reflecting the size of shared vertex sets.

This graph serves multiple purposes in data analysis. It provides a discrete representation of the Morse-Smale complex and enables downstream regression and classification tasks that respect the structure of the feature space. The vertex set of the gradient flow graph consists of both ascending and descending basins, while edges may connect any pair of basins regardless of type, capturing the full structure of how different flow regions interact.

Examples

if (FALSE) { # \dontrun{
# Compute basins and cluster extrema
basins <- compute.basins.of.attraction(adj.list, weight.list, y)
edgelen.list <- compute.edge.lengths(adj.list, weight.list)

# Cluster and merge maxima
max.clusters <- cluster.local.extrema(basins, edgelen.list,
                                      extrema.type = "max",
                                      overlap.threshold = 0.15)
merged.max.basins <- merge.clustered.basins(basins, max.clusters,
                                            extrema.type = "max")

# Cluster and merge minima
min.clusters <- cluster.local.extrema(merged.max.basins, edgelen.list,
                                      extrema.type = "min",
                                      overlap.threshold = 0.15)
merged.basins <- merge.clustered.basins(merged.max.basins, min.clusters,
                                        extrema.type = "min")

# Construct gradient flow graph
gflow.graph <- construct.gflow.graph(merged.basins)

# Examine the structure
print(gflow.graph)
cat("Number of vertices:", length(gflow.graph$adjacency.list), "\n")
cat("Number of edges:", sum(sapply(gflow.graph$adjacency.list, length)) / 2, "\n")

# Find which basins connect to a specific basin
basin.idx <- 1
neighbors <- gflow.graph$adjacency.list[[basin.idx]]
neighbor.labels <- gflow.graph$basin.metadata$label[neighbors]
cat("Basin", gflow.graph$basin.metadata$label[basin.idx],
    "connects to:", paste(neighbor.labels, collapse = ", "), "\n")

# Construct only Morse-Smale edges
ms.graph <- construct.gflow.graph(merged.basins, edge.type = "ms_only")

# Use stricter intersection threshold
filtered.graph <- construct.gflow.graph(merged.basins, min.intersection = 5)
} # }

Usage

Arguments

Value

Details

See also

Examples