---
title: "Sparse metric MDS: complete experiment"
output:
  rmarkdown::html_vignette:
    toc: true
vignette: >
  %\VignetteIndexEntry{Sparse metric MDS: complete experiment}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

<style>
body { max-width: 1050px; }
body:has(nav.navbar) { max-width: none; }
.ivue-legend { max-width: 100%; }
.rglWebGL { max-width: 100%; }
th, td { vertical-align: top; }
pre { overflow-x: auto; }
</style>

<style>
body { max-width: 1000px; }
table { width: 100%; }
.rglWebGL { max-width: 100%; }
</style>

```{r setup, include=FALSE}
library(grip)
knitr::opts_chunk$set(dev="jpeg", dev.args=list(quality=90), fig.retina=1, dpi=72, collapse=TRUE,comment='#>',out.width='100%')
source(system.file('scripts','vignette-views.R',package='grip'),local=TRUE)
source(system.file('scripts','metric-mds-surface-alignment.R',package='grip'),local=TRUE)
source(system.file('scripts','sparse-mds-comparison.R',package='grip'),local=TRUE)
bundle <- readRDS(system.file('extdata','sparse-mds-comparison','benchmark.rds',package='grip'))
rows <- sparse_comparison_rows(bundle)
summary <- sparse_comparison_summary(bundle)
have.ivue <- isTRUE(getOption('grip.vignette.interactive',
    identical(Sys.getenv("IN_PKGDOWN"), "true"))) &&
  requireNamespace('ivue',quietly=TRUE) && requireNamespace('rgl',quietly=TRUE) &&
  'layer3D.callback' %in% getNamespaceExports('ivue') &&
  'limits' %in% names(formals(ivue::plot3D.plain))
method_label <- function(x) ifelse(x=='full','Full SGD',ifelse(x=='grip','Weighted GRIP',
  paste('Sparse SGD:',sub('sparse','',x),'pivots')))
```

The installed benchmark bundle retains every attempted-fit summary, including
failures, scores and timings, and the fixed seed-1 layouts shown here. Complete
layouts and evaluation targets are retained in the source checkout under
`tools/pkg/fixtures/documentation-data/` for independent recomputation.
Static figures are used by default; set `options(grip.vignette.interactive = TRUE)`
with ivue and rgl installed to render the interactive views.

## From all pairs to representative vertices

Full metric MDS fits all pairs of vertices. That makes both the distance
calculation and fitting expensive as a graph grows. `metric.mds(approximation = "sparse")` keeps
all graph edges and approximates longer-range influences using representative
vertices, called **pivots**. A pivot's contribution depends on the nearby
vertices it represents. This is the sparse model of
[Ortmann, Klimenta and Brandes (2017)](https://doi.org/10.7155/jgaa.00440),
with the SGD updates of
[Zheng, Pawar and Goodman (2018)](https://doi.org/10.1109/TVCG.2018.2859997).

With `n` vertices, `m` edges and `h` pivots, storage and work per fitting pass
are proportional to roughly `m + n*h`, rather than all `n*(n-1)/2` pairs.
Preparation computes shortest paths from the pivots. The two endpoints of a
sparse constraint can have different influences: a vertex may move toward a
pivot without moving that pivot. This is why selecting a few pairs from an
ordinary symmetric MDS fit is not the same algorithm.

Usage and the two principal examples are in [Sparse SGD](sparse-metric-mds.html).

## What the saved experiment compares

The experiment uses a saddle, a paraboloid, and a spatial helix with 64 vertices
each; the 307-vertex structural graph `dwt_307` supplied with grip; and a larger
saddle with 4,096 vertices. It compares:

- Full SGD with inverse-squared stress weights.
- Sparse SGD with 8 and 32 pivots on the smaller examples, and 32, 128 and 200 on the larger saddle.
- Weighted GRIP, using `metric='edge_length'`, `length.normalization='none'`, and its default layout settings.

There are three runs of each setting, with seeds 1–3. Both SGD methods use the
same supplied random coordinate matrix, the default hybrid learning-rate
schedule, and 100 epochs. Full MDS fits the coordinate scale and retains its
best checkpoint; sparse SGD returns its terminal iterate without fitting the
scale. GRIP uses its own multiscale initialization. Thus these are comparisons
of the documented methods, not identical initialization trajectories or equal
work per iteration. Each worker has a 90-second limit and the experiment has a
20-minute limit. Failed attempts remain in the saved results.

Full SGD is deliberately omitted above 512 vertices in this bounded experiment;
that cutoff is an experiment choice, not a measured limit of the full method.
For the smaller examples, the reported error is the root-mean-square relative
error over **all graph shortest-path distances**. For the larger saddle, it is
estimated using all distances from 32 uniformly sampled source vertices. Those
sources are chosen independently of the fitting pivots, and the same distances
are used to evaluate every layout. The independent evaluator uses igraph's
Dijkstra implementation. The first error column uses returned coordinates without further scaling.

After inspecting the completed run, we added a **scale diagnostic** because
weighted GRIP returned substantially larger layouts than the distance targets.
For every method, we also fit one positive multiplier to minimize relative error
on the same assessment distances. The second error column reports that
scale-adjusted error. Original coordinates and errors are retained. This
additional diagnostic was not used to tune or rerun any layout.

**Total seconds** includes graph preparation and layout fitting, but excludes
package loading and the independent quality evaluation. **Peak MiB** is measured
maximum resident memory of a separate R worker, including package loading and
result serialization. It is not an estimate from the number of pairs and it
includes the R process baseline. Preparation and fitting times are separately
available for sparse SGD in the saved rows; these phases are not exposed
separately for the other two methods.

The experiment returned coordinates for **`r sum(rows$status=='ok')` of
`r nrow(rows)` attempted fits**. These results do not establish convergence.
Tables show medians over the successful runs, alongside the number attempted.
The figures always show seed 1, rather than choosing the best-looking run.
The displayed layouts use their independently fitted scale multipliers, listed
below each table for the exact displayed runs. The saddle examples then use
**surface-shape alignment**, matching nearby locations on the triangulated
surfaces without requiring vertex labels to agree. Translation, rotation and
reflection are allowed, with no further resizing or deformation. The other
examples use vertex-based Procrustes alignment;
for `dwt_307`, full SGD supplies the alignment reference, not a known true shape.

Surface alignment uses the same 48-start nearest-surface matching procedure as
the [SGD–SMACOF comparison](metric-mds-backends.html). The 64-vertex saddle uses
nine area-weighted samples per triangle. For the 4,096-vertex saddle, the original
64-by-64 grid supplies 7,938 triangles; one sample per triangle is used for
registration. All vertices and edges remain in the display. The original and
scale-adjusted error tables are unchanged by this alignment.

In interactive rendering, use the **Layout** selector to show one method or all
layouts together. Generating coordinates remain visible where available.
Drag to rotate and scroll to zoom; switching layouts preserves the camera and
scale.

```{r sparse-gallery, results='asis', echo=FALSE}
for (id in names(bundle$cases)) {
  case <- bundle$cases[[id]]
  cat('\n\n### ',case$label,' (',case$n,' vertices)\n\n',sep='')
  cat(if(bundle$evaluation[[id]]$mode=='full') 'Error uses all vertex pairs.\n\n' else
    'Error is estimated from 32 independently sampled source vertices. Full SGD was not attempted.\n\n')
  med <- summary[summary$case==id,]; med$method <- method_label(med$method)
  cat(knitr::kable(med[,c('method','returned','attempted','relative_error','profiled_relative_error','seconds','peak_mib')],
    row.names=FALSE,digits=3,col.names=c('Method','Returned','Attempted','Original error','Scale-adjusted error','Total seconds','Peak MiB')),sep='\n')
  selected <- Filter(function(f) f$row$case==id && f$row$seed==1,bundle$fits)
  fits <- stats::setNames(selected,vapply(selected,function(f) f$row$method,''))
  cat('\n\nDisplayed seed-1 scale multipliers: ',paste(vapply(fits,function(f) paste(method_label(f$row$method),format(f$row$relative_scale,digits=3)),''),collapse='; '),'.\n\n',sep='')
  child <- c(sprintf('```{r sparse-view-%s, echo=FALSE}',id),
    'sparse_comparison_view(case,fits,saved.display=TRUE)','```')
  if (id %in% c('dwt_307','saddle-4096')) {
    cat('\n\n[Interactive figure in the main guide](sparse-metric-mds.html).\n\n')
    next
  }
  cat(knitr::knit_child(text=child,envir=environment(),quiet=TRUE),sep='\n')
}
failed <- rows[rows$status!='ok',c('case','seed','method','failure')]
if(nrow(failed)) { cat('\n\n### Unsuccessful attempts\n\n'); cat(knitr::kable(failed),sep='\n') }
```

A larger number of pivots increases work and memory; a better layout is not
guaranteed for each seed. Compare the full or independently sampled error above,
rather than comparing the sparse proxy between methods or pivot counts. The
[SGD–SMACOF comparison](metric-mds-backends.html) separately illustrates the
effect of uniform versus inverse-squared stress weights.

## Repeating the experiment

Building this vignette displays saved results; it does not run the experiment.
Install a fresh copy of grip and use the explicit script in the source repository:

```sh
mkdir -p ../comparison-library
R CMD INSTALL --preclean --library=../comparison-library . > ../comparison-install.log 2>&1
Rscript tools/pkg/build-sparse-mds-comparison.R ../fresh-sparse-results ../comparison-library ../comparison-install.log
```

The script also needs `processx`, `withr`, `igraph`, `ivue`, and the
system `time` command on macOS or Linux. It saves all attempts and resource logs.
See the [reproduction guide](https://github.com/pgajer/grip/blob/main/tools/README.md)
for rendering the saved 3D views.

## References

- Ortmann, M., Klimenta, M., and Brandes, U. (2017). *A Sparse Stress Model*.
  Journal of Graph Algorithms and Applications, 21(5), 791–821.
  [doi:10.7155/jgaa.00440](https://doi.org/10.7155/jgaa.00440).
- Zheng, J. X., Pawar, S., and Goodman, D. F. M. (2018).
  *Graph Drawing by Stochastic Gradient Descent*.
  [doi:10.1109/TVCG.2018.2859997](https://doi.org/10.1109/TVCG.2018.2859997).
- Hangan, D., Kobourov, S., and Miller, J. (2026).
  *Bridging Graph Drawing and Dimensionality Reduction with Stochastic Stress
  Optimization*. [arXiv:2605.00641](https://arxiv.org/abs/2605.00641).