Metric MDS: SGD, SMACOF, and stress weighting

metric.mds() fits Euclidean coordinates to graph shortest-path distances. The default backend='sgd' moves pairs of vertices in shuffled order, following Zheng, Pawar and Goodman (2018), with a selectable learning-rate schedule. Legacy graph calls default to the hybrid schedule adapted from the implementation of Hangan, Kobourov and Miller (2026); prepare.sparse.mds() inputs default to Zheng’s weight-dependent fixed-budget exponential schedule (scheduler="zheng"). backend='smacof' updates the full configuration using the optional smacof package. Its majorization steps are designed to reduce total stress; individual SGD pair adjustments need not.

This guide illustrates the differences using existing saved synthetic examples. For a broader comparison of the methods, see Hangan, Kobourov and Miller (2026). The complete experiment retains all 420 original fits, the separate 60-fit weighting comparison, failed outcomes, numerical results, and reproduction instructions.

For higher-dimensional fitting followed by PCA and optional free 3D refinement, see Higher-dimensional metric MDS for 3D visualization.

To record and animate actual SGD pair updates, see Animating metric MDS: paraboloid and saddle.

Fit a graph with either backend

g <- suitesparse.graph('dwt_307')
sgd <- metric.mds(edges=g$edges,n=g$n,dim=3,seed=1,
                  init='random',max.iter=100,diagnostics=FALSE)
smacof.fit <- metric.mds(edges=g$edges,n=g$n,dim=3,seed=1,
                  init='random',max.iter=100,diagnostics=FALSE,
                  backend='smacof',eps=1e-8)

This is a usage recipe, not a new benchmark on dwt_307. Both backends support uniform and inverse-squared stress weights. The default full mode uses uniform weights. An SGD pass and a SMACOF iteration are different amounts of work; compare achieved error and elapsed time, not iteration counts alone. SGD’s schedule completion reports iteration_limit, which does not certify convergence. The hybrid tuning defaults remain provisional calibration choices. The saved backend comparisons do not isolate the learning-rate schedule and therefore do not establish that hybrid is better than "zheng". Hangan et al.’s fixed-switch rationale concerns the usual uniform-weight MDS setting; it is not evidence of superiority for inverse-squared regional sparse stress. See ?metric.mds, under “Learning-rate schedules and evidence,” for the provenance, precise defaults and published-schedule controls.

Two distance targets on the same saddle

The saved experiment uses 64- and 144-point clouds, five paired random starts, and separate allowances of 10, 30, or 100 passes/iterations. Both methods receive the same starting coordinates within each pair. Here we show the 144-point saddle at seed 1 and allowance 100, with uniform stress weights. These displayed runs were selected in advance, not chosen for their appearance.

Ambient distances are straight-line distances between generating points; an exact 3D realization exists. Local graph paths sum edge lengths along a finite grid with horizontal, vertical, and diagonal edges. They are not exact geodesics on the continuous saddle, and their best 3D drawing need not reproduce the generating surface.

Ambient Euclidean

|Backend | Normalized error| Fit seconds| Passes/iterations|Termination | |:——-|—————-:|———–:|—————–:|:—————-| |sgd | 0e+00| 0.122| 100|iteration_limit | |smacof | 2e-04| 0.074| 95|stress_tolerance |

Local graph paths

|Backend | Normalized error| Fit seconds| Passes/iterations|Termination | |:——-|—————-:|———–:|—————–:|:—————| |sgd | 0.0323| 0.120| 100|iteration_limit | |smacof | 0.0409| 0.063| 100|iteration_limit |

Gray shows the generating reference; blue is SGD and orange is SMACOF. The ambient case uses matched-vertex alignment. The local-graph case uses surface-shape alignment: translation, rotation, and reflection match nearby surface locations without requiring vertex labels to agree. Neither alignment resizes or deforms the layouts. Scores use the original returned coordinates.

Normalized error is the square root of raw stress divided by the sum of squared target distances; lower is better. The figures below summarize both cloud sizes across five starts, with median errors and fitting times and interquartile ranges. Each point is a separate fit restarted with its own iteration allowance, not a checkpoint along one run. Fitting times exclude shared graph preparation, alignment, and rendering.

The effect of stress weighting

Uniform weighting minimizes squared errors in distance units. The paper’s inverse-squared weighting minimizes squared relative distance errors:

\[ \sum_{i<j} \frac{(\lVert z_i-z_j\rVert-d_{ij})^2}{d_{ij}^2}. \]

An error of 0.2 on a target distance of 1 then counts as much as an error of 2 on a target of 10. Edge lengths determine the target distances; pair.weights determines their influence on the objective.

fit <- metric.mds(edges=g$edges,n=g$n,dim=3,
  pair.weights='inverse_squared',backend='sgd',seed=1)

The following comparison uses the saved 64-vertex saddle graph, seed 1, and allowance 100 for each backend and weighting. All four layouts use surface-shape alignment without resizing. Select a method and weighting below the figure, or show all four.

	backend	pair_weights	uniform_error	relative_error	seconds
sgd_uniform	sgd	uniform	0.0344	0.0435	0.027
sgd_inverse_squared	sgd	inverse_squared	0.0382	0.0401	0.027
smacof_uniform	smacof	uniform	0.0462	0.0536	0.018
smacof_inverse_squared	smacof	inverse_squared	0.0385	0.0403	0.018

Compare errors within the same column: uniform and relative error express different priorities. The complete results include the five-start summaries, paraboloid and helix examples, and the surface-registration checks. For larger graphs, continue to Sparse SGD.