Principal manifolds and graphs in practice: from molecular biology to dynamical systems

1. Introduction

• The paper applies principal-manifold and graph methods to political science, molecular biology, and dynamical systems, addressing approximation of high-dimensional datasets by regular low-dimensional objects.The target is a finite subset of a regular low-dimensional object in Rm that approximates a finite dataset D.Source: §1 · p. 1
• PCA tests whether data lie near a low-dimensional affine manifold by minimizing average squared distance to the data points.The candidate affine objects include a point, line, or plane.Source: §1 · p. 1
• Kohonen introduced Self-Organizing Maps (SOM) in 1982 as a neural-network approach amid efforts to generalize PCA nonlinearly.The introduction characterizes SOM as a seminal approach to nonlinear generalization.Source: §1 · p. 1
• SOM maps a finite metric space of neurons into Rm, balancing preservation of its structure against approximation of the dataset.At each step, a data point is assigned to its nearest image neuron, and setup variables regulate the tradeoff.Source: §1 · p. 1
• Despite its flexibility, SOM lacks an independent definition beyond its algorithm, and attempts to define it through energy minimization were unsuccessful.The update uses a step size and a monotonically decreasing function of distance from the data point’s owner neuron.Source: §1 · p. 1
• For finite datasets, principal-manifold construction uses smoothers to prevent overfitting, with self-consistency requiring each manifold point to be the conditional expectation of data projected there.The projection and manifold need not be linear.Source: §1 · p. 2
• SOMs approximate principal manifolds using regular-grid neuron spaces, while an elastic-energy method introduced in 1996 uses quadratic smoothness penalties and sparse linear systems.The introduction also notes algorithms for principal curves and surfaces and describes the elastic method as an analogy to membranes and plates.Source: §1 · p. 2

2.1. Principal graphs and manifolds

• An elastic principal manifold minimizes weighted mean squared distance from data to its vertices plus elastic energy, which penalizes departures from smooth configurations.Elastic maps extend the embedded graph to a continuous manifold by interpolation; the Euclidean optimization can use an EM algorithm.Source: §2.1 · pp. 2–3

2.2. Pluriharmonic graphs as ideal approximators

• For branched data, principal graphs add branching points to curves, while pluriharmonic embeddings serve as ideal forms penalized for deviation.For primitive graphs, zero star penalties mean each non-terminal vertex maps to the mean of its neighbors.Source: §2.2 · p. 3

2.3. Complexity of principal graphs

• Principal graphs control geometric complexity through elastic energy, structural complexity through counts of graph elements, and construction complexity through grammar operations.An elastic principal graph minimizes embedding energy subject to upper bounds on structural and construction complexity.Source: §2.3 · pp. 3–4

3.1. Happiness (quality of life) is non-linear

• 93% vs 76% of explained variance favored the nonlinear principal curve over the principal line; the nonlinear index also changed country rankings.In 2005, Russia ranked 86th under the first principal component, after Iran (74th) and Egypt (84th), but 71st under the nonlinear index, before Iran (77th) and Egypt (85th).Source: §3.1 · pp. 5–6

3.2. Dimension reduction for microarrays

• Nonlinear 2D principal manifolds performed systematically better or equally across all four criteria than same-dimensional linear manifolds, matching 3D–4D linear manifolds.The comparison covers mean-squared error, distance mapping, neighborhood preservation, and group compactness; the 2D elastic-map approach also matched 4D linear approximations on MSE.Source: Figure 3 · p. 7, Figure 4 · p. 7, §3.2 · pp. 8–9
• For compact heterogeneous classes, nonlinear projections often improved class compactness, but near-random, dispersed classes produced unstable values and occasional linear wins.Dimension reduction improved compactness for the breast-cancer basal subtype and bladder-cancer Grade 2 and T1/T2+ classes; better nonlinear compactness than both alternatives appeared for the basal subtype and bladder T2+ and Grade 2 subtypes, supporting classification regularization.Source: §3.2 · pp. 8–9

3.3. Principal trees and Metro Maps

• Principal trees [12,14] reduce multidimensional data to a tree and visualize samples while preserving path-based distances between nodes.The construction iteratively selects permissible growth or shrinkage operations under a structural-complexity ceiling to minimize elastic energy; trimming removes excess branching and can fuse stars separated by short bridges. Metro-map nodes can show projected sample counts and class composition.Source: §3.3 · pp. 9–10, Figure 8 · p. 10

3.4. Principal manifolds for dynamical systems analysis

• In the 35-variable NFkB signaling model [26], dynamics near its limit cycle were characterized by a two-dimensional invariant manifold [27].The authors sampled 50,000 trajectory points near the cycle, approximated them with a nonlinear 2D elastic-map manifold, and proposed projecting dynamics onto it for model reduction.Source: §3.4 · p. 11
• Principal manifold methodology approximates a two-dimensional invariant manifold from dynamical-system trajectory snapshots; a shown trajectory quickly approaches the manifold and converges along it to a limit cycle.The manifold is shown in the 3D projection of the first three principal components.Source: Figure 9 · p. 11
• The approach is called a non-linear Karhunen-Loéve expansion for reducing the complexity of the dynamics.Source: §3.4 · p. 11

• Principal manifolds, graphs, and trees can approximate complex data distributions when linear approximation is insufficient, and the paper proposes benchmarking criteria to assess their advantages.Source: §4 · p. 11
• The elastic graph approach occupies an intermediate position between the flexibility of neural gas and the greater restrictions of Self-Organizing Maps and elastic maps.Source: §4 · p. 11
• Efficient elastic graph implementations make principal graphs and manifolds relatively easy and fast to apply, as demonstrated in political science, molecular biology, and biochemical dynamical systems.Source: §4 · pp. 11–12