HiSE Motif Workflow: Harvesting, Mutation, and Hierarchical Representations¶

This document provides a comprehensive, mathematically rigorous guide to the Coarse-to-Fine Hierarchical Structure Mining Engine (ezga.hise.motifs) implemented in EZGA.

The framework is designed to discover, statistically validate, mutate, and hierarchically represent complex multi-atom structural features (motifs) directly from high-throughput structural search data (e.g., Genetic Algorithm exploration or Monte Carlo trajectories).

High-Level Concept in Simple Terms¶

If you want to understand how the system works without getting lost in the math, here is the intuitive step-by-step process of how we turn raw atomic coordinates into human-understandable structural insights:

[GA/MC Exploration] ──> [Filter Stable Structures] ──> [Extract Isolated Clusters]
                                                                  │
[Hierarchical Graph] <── [Verify Energy Significance] <── [SVD Template Grouping]

1. Filtering by Energy (Focusing on the Good Stuff)¶

During a Genetic Algorithm (GA) or Monte Carlo (MC) search, the simulator generates thousands of candidate structures. Most of these are random, high-energy, unstable configurations. Instead of wastefully mining all of them, the engine selects only a thermodynamically relevant subset (either using Boltzmann weighting or stratified energy slicing). We only inspect configurations that represent stable, physical, real-world patterns.

2. Covalent Network Partitioning (Finding Isolated Clusters)¶

For each sampled structure, we translate its list of $(x, y, z)$ coordinates into a physical network graph of chemical bonds: - We automatically ignore static, rigid background atoms (like the bulk metal slab). - We look up covalent radii for the active adsorbate atoms and connect any atoms within bonding distance. - We group these connected networks into isolated molecular fragments (e.g., separating an $O_2$ dimer on one side of the surface from an $O_3$ cluster on the other).

3. Geometric Template SVD Matching (Collapsing Coordinates to Motif Families)¶

Once we have extracted thousands of physical fragments across all structures, we want to group identical shapes together. Since fragments are oriented in all directions, we use the SVD-Kabsch alignment algorithm: - It centers, rotates, and projects every fragment onto candidate templates. - It measures geometric similarity via an RMSD fitting score. - This collapses thousands of raw coordinates into a small, clean library of canonical Motif Families (e.g., all O-O pairs are grouped under the "Oxygen Dimer" motif family).

4. Thermodynamic Relevance Analysis (Filtering by Physical Metrics)¶

Just because a shape appears frequently doesn't mean it is physically relevant (atoms can group together randomly by chance). We filter the library using two key metrics: - Mann-Whitney Energy Ranking: We verify if structures that contain a specific motif have statistically lower/more stable energy than structures without it. - Multinomial Enrichment: We compute a baseline element composition model. If a motif contains multiple O or Ni atoms, we ensure its occurrence rate is significantly higher than what would happen by pure random chance in dense compositions.

5. Coarse-to-Fine Hierarchical Graphing (Scaling Up the Analysis)¶

Finally, we project these validated motifs back onto our material system, shifting our perspective to a higher-level space: - Layer 0 (Atomic): We see individual atoms and bonds. - Layer 1 (Motifs): Atoms are grouped and replaced by our certified motif templates. - Layer 2 (Interactions): We represent how these motifs interact with each other (measuring their center-of-mass distances and relative orientation tilt angles). - Layer 3 (Domains): We partition the entire network into distinct macro-communities/domains of interacting adsorbates.

Workflow Overview¶

The motif-centric architecture consists of six fundamental phases:

graph TD
    A["Raw Exploration Trajectories (GA/MC Database)"] --> B["Phase 1: Thermodynamic Structural Sampling"]
    B --> C["Phase 2: Covalent Network Partitioning & Clustering"]
    C --> D["Phase 3: SVD-Kabsch Alignment & Deduplication"]
    D --> E["Phase 4: Statistical Significance & Filtering"]
    E --> F["Phase 5: Coarse-to-Fine Hierarchy (Layers 0-3)"]
    F --> G["Phase 6: Dynamic D3.js Visual Dashboards"]

Phase 1: Thermodynamic Structural Sampling¶

Analyzing millions of coordinates from search databases is computationally expensive. Therefore, we sample a representative subset of structures prioritizing thermodynamically stable (low-energy) configurations where chemically meaningful motifs reside.

1. Boltzmann Sampling Mode¶

Structures are drawn according to a Boltzmann probability distribution defined by an effective temperature $T_{\text{eff}}$:

$$P_i = \frac{e^{-\frac{E_i}{k_B T_{\text{eff}}}}}{\sum_{j} e^{-\frac{E_j}{k_B T_{\text{eff}}}}}$$

Where: - $E_i$ is the potential energy of structure $i$. - $T_{\text{eff}}$ governs the sampling selective pressure (higher values yield uniform-like samples; lower values isolate the lowest-lying local minima).

2. Stratified Sampling Mode¶

To prevent over-sampling highly degenerate structural configurations (e.g., identical local energy basins), energies are divided into $M$ quantile bins. An equal number of configurations are randomly drawn from each bin, preserving structural diversity across the entire low-energy window:

$$\text{Bin}k = \left[ E{(k/M)}, E_{((k+1)/M)} \right]$$

Phase 2: Covalent Network Partitioning & Clustering¶

Once structures are selected, the system builds an undirected covalent graph to group atoms into individual connected fragments (adsorbates/clusters), isolating them from the rigid substrate.

       [Atom A] 
         /   \      <-- Covalent Bonds
   [Atom B] [Atom C]
         \   /
       [Atom D]     <-- Form an isolated Connected Fragment

1. Covalent Distance Graph¶

For any two active atoms $i$ and $j$ with positions $r_i$ and $r_j$, a covalent bond exists if:

$$d_{ij} \le \lambda_{\text{scale}} \cdot \left( r^{\text{cov}}_i + r^{\text{cov}}_j \right)$$

Where: - $d_{ij}$ is the Euclidean distance computed under Periodic Boundary Conditions (PBC). - $r^{\text{cov}}i, r^{\text{cov}}_j$ are the database-tabulated covalent radii of elements $i$ and $j$. - $\lambda{\text{scale}}$ is an adjustable multiplier (default: $1.25$) to accommodate structural stress.

2. Subgraph Connected Component Finding¶

An adjacency list is built using a spatial KDTree query. A Breadth-First Search (BFS) or Depth-First Search (DFS) algorithm partitions the active atom network into isolated connected fragments. Substrate atoms (e.g., static metal slabs) are excluded using custom boolean spatial constraints:

$$\mathcal{C} = { \text{atom } k \mid \text{substrate_constraint}(k) = \text{False} }$$

Phase 3: SVD-Kabsch Alignment & Deduplication¶

Discovered fragments have varying orientations and translation offsets. To group geometrically identical structures into unified Motif Families, we project fragments onto each other using the optimal rotational alignment algorithm.

1. Centering the Configurations¶

Given a fragment coordinate set $P \in \mathbb{R}^{N \times 3}$ and a candidate template set $Q \in \mathbb{R}^{N \times 3}$:

$$\mu_P = \frac{1}{N}\sum_{k=1}^N P_k, \quad \mu_Q = \frac{1}{N}\sum_{k=1}^N Q_k$$

$$P_c = P - \mu_P, \quad Q_c = Q - \mu_Q$$

2. Computing the Rotation Matrix¶

The cross-covariance matrix $H \in \mathbb{R}^{3 \times 3}$ is defined as:

$$H = P_c^T Q_c$$

We resolve $H$ using Singular Value Decomposition (SVD):

$$H = U \Sigma V^T$$

The optimal rotation matrix $R$ mapping $P$ to $Q$ is:

$$R = V U^T$$

Reflection Correction¶

To prevent unphysical coordinate inversions (reflections, where $\det(R) = -1$), we modify the sign of the last column of $V$:

$$V_c = V \cdot \begin{pmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & \det(V U^T) \end{pmatrix}$$

$$R_{\text{opt}} = V_c U^T$$

3. Translation and Root-Mean-Square Deviation (RMSD)¶

The optimal translation vector mapping centers of mass is:

$$t_{\text{opt}} = \mu_Q - R_{\text{opt}} \mu_P$$

The alignment fit is measured via RMSD:

$$\text{RMSD}(P, Q) = \sqrt{\frac{1}{N} \sum_{k=1}^N | R_{\text{opt}} P_{c, k} - Q_{c, k} |^2}$$

Fragments are grouped into the same Motif Family if they share a chemical formula and their mutual alignment yields $\text{RMSD} \le \text{rmsd_cutoff}$ (typically $0.5$ Å).

Phase 4: Statistical Significance & Filtering¶

To distinguish physically meaningful motifs from random atomic fluctuations, the engine subjects each discovered motif family to rigorous statistical validation.

                  [ Discovered Motif Family ]
                             |
         +-------------------+-------------------+
         |                                       |
  [ Mann-Whitney U Test ]               [ Enrichment Metric ]
  Tests if structures containing        Measures frequency relative
  the motif have significantly          to element compositional abundance
  lower physical energies.              null-models.

1. Thermodynamic Enrichment Ratio¶

Measures whether a motif appears more frequently in low-energy regions than expected under a random compositional null-model:

$$\text{Enrichment}(M) = \frac{\rho_{\text{low}}(M)}{\rho_{\text{bg}}(M) \cdot P_{\text{null}}(M)}$$

Where: - $\rho_{\text{low}}$ is the density of the motif in the low-energy quantile. - $\rho_{\text{bg}}$ is the background density across all database structures. - $P_{\text{null}}(M)$ is the compositional baseline probability representing element abundances:

$$P_{\text{null}}(M) = \prod_{a \in M} \left( \frac{N_a}{N_{\text{total}}} \right)^{n_a}$$

2. Mann-Whitney U Energy Difference Test¶

We partition the structure energies into two sets: $E_{\text{with}}$ (containing motif $M$) and $E_{\text{without}}$ (lacking motif $M$).

We execute a one-sided Wilcoxon-Mann-Whitney Rank-Sum Test to determine if the median energy of structures containing the motif is statistically lower than those without it:

$$U = n_1 n_2 + \frac{n_1(n_1+1)}{2} - R_1$$

Where: - $n_1, n_2$ are the sizes of the two partitions. - $R_1$ is the sum of ranks for the $E_{\text{with}}$ partition.

The resulting asymptotic p-value $p$ is corrected for multiple comparisons using the Benjamini-Hochberg False Discovery Rate (FDR) procedure:

$$q_i = \min_{j \ge i} \left( p_{(j)} \cdot \frac{N_{\text{tests}}}{j} \right)$$

Families yielding $q \le 0.05$ and a negative energy delta $\Delta E$ are classified as highly significant active motifs.

Phase 5: Coarse-to-Fine Hierarchical Representations¶

Hierarchical mapping translates atomic configurations into multi-level complexity graphs (Layers 0 to 3), enabling coarse-to-fine navigation.

[ LAYER 3: Communities ]      ==>  Macro-domains of interacting clusters
          |
[ LAYER 2: Interactions ]     ==>  Red of proximity, sharing nodes & orientations
          |
[ LAYER 1: Instances ]        ==>  SVD-aligned geometric Motif templates
          |
[ LAYER 0: Atomic Covalent ]  ==>  Fine covalent atom-bond network

Layer 0: Atomic Covalent Network¶

Nodes: Individual active atoms (identified by element, ID, and Cartesian coordinates).
Edges: Covalent bonds mapping the atomic skeleton.

Layer 1: Motif Instance Mapping¶

Nodes: Fully mapped motif templates.
Individual atoms from Layer 0 are grouped into high-fidelity instances based on SVD-Kabsch RMSD matching.

Layer 2: Motif Interaction Network¶

Nodes: Motif instances from Layer 1.
Edges: Proximity or edge-sharing interactions.
Metrics:
Center-of-Mass Distance: $D_{\text{COM}} = |\text{COM}_A - \text{COM}_B|$
Relative Orientation Tilt Angle ($\theta$): Computed from the SVD rotation matrices of the two aligned templates:

$$\theta_{AB} = \arccos\left( \frac{\text{Trace}(R_A^T R_B) - 1}{2} \right)$$

Layer 3: Coarse Domains¶

Nodes: Coarse community partitions.
Logic: Layer 2 interactions are partitioned using connected component community segmentation. This isolates independent reacting adsorbate domains acting on the substrate surface.

Phase 6: Interactive Visual Dashboards¶

Visualizing hierarchical networks statically is highly challenging. The engine includes standalone HTML/D3.js dashboard generators.

Layer 0 Node-Link Force Field: Models physical atomic structures.
Layer 1 & 2 Force Simulation: Simulates coarse-grained motif interactions. Node volumes scale with motif sizing, and links are annotated with center-of-mass separation distances.
Layer 3 Color Grouping: Identifies macro-domain community modules.
Dynamic Transition Toggles: Implements smooth transition paths to dynamically morph between layers without losing user coordinate context.

Usage in Genetic Algorithm Mutation¶

In evolutionary optimization runs, the generated library acts as a structural mutation operator (mutation_add_motif_from_library):

Probability Bias Selection: A motif template is selected from the library using a roulette-wheel selection biased by thermodynamic significance scores:

$$\text{Prob}(M) = \frac{\text{Score}(M)}{\sum_j \text{Score}(j)}$$

Spatial Projection: A random active substrate site is selected. The template positions are projected onto the surface, applying a random 2D rotation ($R_z(\theta)$) and tilt perturbation ($R_{\text{tilt}}$).
Steric Collision Verification: Covalent overlap checks ensure no active atoms collide with existing surface configurations:

$$d(\text{new}, \text{old}) \ge \gamma_{\text{collision}} \cdot \left( r^{\text{cov}}{\text{new}} + r^{\text{cov}}{\text{old}} \right)$$

If the placement is collision-free, the mutated child structure is successfully added to the active search pool.

Step 4 — Generation & Assembly¶

Once a motif vocabulary is harvested, scored, and (optionally) compressed (steps 1–3), the assembly engine (ezga.hise.motifs.assembly) turns it into new structures by fusing motifs at their linker ports. One four-primitive engine (place · fuse · complete · validate) over a shared AssemblyState backs three entry points that reuse the same primitives:

One-shot — generate_structure(vocab, config=AssemblyConfig(...), hamiltonian=...) places a seed motif and completes the structure (port-directed WFC), wrapped in a robustness ladder (portfolio restarts, void-filling repair, spring-relax). Returns validated, optionally energy-ranked structures.
Few-step — StepBuilder: place / complete a handful of operations at a time, snapshot / rollback, then hand a (possibly half-built) structure to the optimizer.
Reversible MC/MH moves — motif_assembly_moves(levels, ...) bundles the detailed-balance (child, log_q_fwd, trace, get_log_q_rev) operators (birth/death + editing) for Variation_Operator + a surrogate-energy kernel.

Placement is by linkers (a port's outward direction meets a host port head-on at bond distance); under-coordinated ports are completed to their coordination_capacity; candidates are weighted by the effective Hamiltonian (HamiltonianScorer, linear in motif counts); and validity branches on closure (a finite cluster vs. a periodic framework, with percolation detection). Super-motifs (level ≥ 2) assemble too, with ports derived geometrically from their faithful atom cloud.

See docs/design/motif_generation_step4.md (as-built) and docs/design/motif_generation_step4_plan.md (full design), and the runnable examples examples/hise_advanced/assembly_*.py.