PaperlayerView exact revision on arXiv

Source-linked AI summary

MHeatmap: Two-Walk Laplacian Reordering and Mosaic Layout for Rectangular Matrix Visualization

Juntang Wang, Sheng'en Li, Liming Zhu, Yihan Wang, Siyuan Cao, Hao Wu, Man Zhang, Shixin Xu, Dongmian Zou

arXiv:2610.29114v1cs.LGcs.HC

TL;DR

Arbitrary row and column orders can scatter related entities in rectangular-matrix heatmaps. MHeatmap combines Two-Walk seriation, which incorporates shared-neighbor structure, with a proportional Mosaic layout; the paper reports that the full table shows when this structure improves recovery and where alternatives remain competitive.

  • Problem

    Rectangular matrices often have input orders unrelated to relational structure, leaving related entities scattered and harder to inspect.

    Source: §1 · p. 1

  • Method

    Two-Walk adds shared-neighbor affinities to direct bipartite relations for coordinated ordering, while Mosaic scales rectangle dimensions by row and column marginals and uses color for observed entries.

    Source: §1 · pp. 1–2

  • Results

    The paper reports that its full table shows when shared-neighbor structure improves recovery and where alternative assumptions remain competitive.

    Source: §6 · p. 8

  • Takeaways & Limitations

    Mosaic makes row and column marginals visible within the matrix body while retaining observed values in color, useful when marginal context affects interpretation.

    Source: §6 · p. 8

    Mosaic claims concern encoding semantics and qualitative use, not universal perceptual superiority; area judgments are less precise than aligned position and length judgments.

    Source: §2.3 · p. 3

Abstract

from arXiv · show

Weighted rectangular matrices record relations between two types of objects, such as occupations and industries, documents and terms, origins and destinations, or annotated classes and computed clusters. Their heatmaps become difficult to read when arbitrary row and column orders scatter related objects, while equal size cells hide large differences in row and column totals. We present MHeatmap (Mosaic Heatmap), which addresses these problems in two stages. Two-Walk spectral seriation first represents the matrix as a weighted bipartite graph. Ordinary bipartite ordering uses only observed row to column links. Two-Walk also uses length-two walks, so rows that share columns and columns that share rows receive explicit similarity links. Sorting a Fiedler vector of the resulting graph Laplacian gives coordinated row and column orders. The Mosaic layout then partitions a unit square so that row height is proportional to the row total and column width is proportional to the column total, while color represents the observed entry. We prove how the Two-Walk energy combines direct alignment with shared-neighbor smoothness, derive an exact matrix vector product that permits sparse computation, and formalize the tiling and area semantics of Mosaic. Across 300 synthetic matrices and seven real data sets, Two-Walk obtains the lowest normalized 2-SUM in all 15 synthetic regimes and the highest Band@10% in 14. The largest gains occur when shared neighborhoods express the latent relational structure.

1 Introduction

MHeatmap addresses scattered relationships in rectangular matrices with coordinated row and column seriation, then uses proportional rectangles and color to display margins and observed entries.

1 Introduction

  • Arbitrary input orders can scatter related entities in rectangular relation matrices, complicating inspection of correspondences, overlaps, splits, merges, and unexpected mass.Examples include author–topic, document–term, and commuting-flow matrices.Source: §1 · p. 1
  • Two-Walk combines direct row–column links with similarities between rows sharing columns and columns sharing rows, then sorts a Fiedler vector for coordinated orders.The paper contrasts this with One-Walk, whose adjacency contains only direct cross-partition edges.Source: §1 · p. 1
  • Mosaic partitions a unit square into adjacent rectangles, scaling row height and column width by their respective marginals while color encodes each observed entry.For contingency tables, cell area is the product of the row and column proportions.Source: §1 · pp. 1–2
  • The paper analyzes Two-Walk energy, scale invariance, its One-Walk limit, and sparse matrix–vector computation, and evaluates 300 synthetic matrices and seven real relation matrices.It also formalizes Mosaic tiling and area semantics.Source: §1 · p. 2

2 Related Work

Related work places coordinated rectangular seriation among spectral and bipartite methods, and distinguishes MHeatmap’s marginal geometry and heatmap color from established display lineages.

2.1 Matrix Seriation and Reordering

  • Prior seriation approaches include spectral ordering, clustering, sparse-matrix reduction [21], and bipartite layouts; this paper studies coordinated rectangular orders.Most classical formulations assume a square similarity matrix or order the two axes independently.Source: §2.1 · p. 2

2.2 Bipartite Spectral Methods and Shared Neighborhoods

  • Unlike spectral co-clustering and paired-coordinate methods, seriation returns continuous orders; Two-Walk combines direct links with shared-neighbor affinities.The joint formulation uses length-two walks alongside direct relations.Source: §2.2 · p. 2

2.3 Mosaic, Sieve, and Product Plots

  • MHeatmap combines sieve-like marginal geometry with heatmap color, while its Mosaic claims concern encoding semantics and qualitative use, not universal perceptual superiority.The proportional-tiling idea has established precedents in mosaic, sieve, and product plots.Source: §2.3 · pp. 2–3

3 Method

The method coordinates row and column orders with a spectral seriation that combines direct relations and shared-neighbor similarities. MHeatmap can then render the reordered matrix with Mosaic geometry, which encodes row and column totals separately from cell color.

3.1 Preliminaries and One-Walk Seriation

  • One-Walk orders rows and columns by separately sorting the two parts of a Fiedler vector from the bipartite lift’s Laplacian.The active matrix removes zero-marginal rows and columns, which have no incident graph edge or informative spectral coordinate.Source: §3.1 · p. 3

3.2 Two-Walk Spectral Seriation

  • Two-Walk adds shared-neighbor affinities to direct row–column relations, then sorts the row and column coordinates of a Fiedler vector separately.Its Laplacian energy balances smoothness among rows sharing columns, smoothness among columns sharing rows, and alignment of directly related vertices.Source: §3.2 · p. 3

3.3 Exact Matrix Vector Product

  • The exact matrix-vector product applies the Two-Walk Laplacian using sparse matrix products, with O(nnz(B)) arithmetic per application.This avoids explicitly forming the Gram matrices, which can destroy sparsity.Source: §3.3 · p. 4

3.4 Mosaic Layout

  • Mosaic assigns row height and column width in proportion to their normalized marginals, while a monotone mapping of each observed entry determines its fill color.Its rectangles tile the unit square; for a contingency table, cell area equals the independence expected count divided by the total.Source: §3.4 · p. 4
  • Mosaic geometry encodes marginals, not observed cell values; rare rows or columns can become too narrow for precise cell-value comparison.The layout is intended for overview and mass context, while color encodes the observed entry.Source: §3.4 · p. 4

4 Evaluation

The evaluation tests ordering quality across synthetic structures and diverse real matrices, and separately examines what Mosaic geometry adds when the ordering is fixed. Quantitative metrics assess orderings; controlled visual comparisons assess Mosaic’s encoding.

4.1 Evaluation Questions and Scope

  • The evaluation asks whether Two-Walk improves block and band recovery over representative baselines and One-Walk, where shared-neighbor affinities help, and what Mosaic reveals.The Mosaic question holds row and column order fixed to isolate the information added by its geometry.Source: §4.1 · p. 4

4.2 Controlled Synthetic Benchmark

  • The synthetic benchmark varies five structural families across three matrix sizes and 20 random seeds per family-size combination, with methods given permuted matrices but no block labels.The families range from clean one-to-one blocks to shared or nested structure, noise, and cross-block leakage.Source: §4.2 · pp. 4–5

4.3 Real Matrix Benchmark

  • The real benchmark includes seven nonnegative matrices spanning classification crosswalks, flows, text, transit, and author-topic relations.Subsets are fixed before ordering, complete official crosswalks are used when available, and only structurally empty rows and columns are removed.Source: §4.3 · p. 5

4.4 Compared Methods

  • Seven orderings represent distinct choices, including supplied order, marginal sorting, profile clustering, One-Walk, correspondence analysis, and alternating median.One-Walk is the central ablation because it shares Two-Walk’s spectral pipeline but excludes the length-two terms.Source: §4.4 · p. 5

4.5 Structure-Recovery Metrics

  • Normalized rectangular 2-SUM measures weighted diagonal dispersion, with lower values indicating more mass near corresponding normalized positions on the two axes.Band@10% measures the fraction of mass within a fixed normalized half-width; it can disagree with R2S when a few entries remain distant.Source: §4.5 · p. 5

4.6 Parameter Selection and Reporting Protocol

  • Adaptive Two-Walk selects alpha by internal MWB-AUC without synthetic block labels or external task labels, but fixed baselines receive no data-dependent choice.The main comparison instead uses R2S and Band@10%, neither of which selects alpha; tables report synthetic means over 20 seeds and each real matrix once.Source: §4.6 · pp. 5–6
  • The Mosaic comparison holds matrix values and Two-Walk row and column permutations fixed, changing only equal-area geometry to marginal-proportional geometry.Its qualitative purpose is to assess encoding interpretability, not universal perceptual superiority over equal-area heatmaps or marginal bar charts.Source: §4.1 · p. 4, §4.6 · p. 6

5 Results

Two-Walk is strongest on synthetic matrices overall, with the clearest gains where shared-neighbor profiles capture relational structure. Real-matrix results and baseline comparisons show that its advantages depend on the matrix’s organization, while Mosaic makes marginal sizes visible through geometry.

5 Results

  • Two-Walk has the lowest R2S in all 15 synthetic regimes, the highest Band@10% in 14, and the highest or tied-highest MWB-AUC in all 15.Across regimes, 102×R2S falls from 1.150 for One-Walk to 0.983 for Two-Walk, a 14.5% reduction; mean Band@10% rises from 0.718 to 0.765. MWB-AUC is expected to favor Two-Walk because it selects α; R2S and Band@10% are not used for selection.Source: §5.1 · p. 6, Table 1 · p. 7

5.1 Synthetic Structure Recovery

  • Two-Walk improves R2S even on clean blocks, with clearer gains for overlapping, nested, and noisy shared-prototype patterns; on the largest leakage matrix, MD instead leads Band@10%.For Family B at 200 × 180, Two-Walk changes R2S from 1.15 to 0.82 and Band@10% from 0.67 to 0.78; for Family D at the largest size, R2S changes from 1.28 to 1.00 and Band@10% from 0.63 to 0.70. In Family E at 400 × 360, MD has Band@10% 0.60 versus Two-Walk’s 0.56, while Two-Walk’s R2S is 1.87 versus MD’s 2.65.Source: §5.1 · p. 6

5.2 Real Matrix Results

  • Two-Walk’s strongest improvements occur in relational matrices where same-side entities are compared through shared neighbors; it is not a universal substitute for geometric, spatial, or very low-dimensional ordering criteria.For SIC to NAICS, Two-Walk lowers 102×R2S from 0.68 for One-Walk to 0.18, though Band@10% is 0.96 versus 0.98; for CIP to SOC, its R2S falls from 2.52 to 1.67 and Band@10% rises from 0.43 to 0.61. On 20 Newsgroups, Two-Walk ties One-Walk at R2S 0.43 and raises Band@10% from 0.94 to 0.95; on OpenAlex, R2S falls from 0.98 to 0.92 and Band@10% reaches 1.00; for ACS (24 × 10), CA gives the best R2S and Band@10%, while on MBTA, MD has the best Band@10% and MWB-AUC.Source: §5.2 · pp. 6–7

5.3 Baseline Behavior Across Regimes

  • Marginal sorting exposes large rows and columns but not cross-axis correspondences, while hierarchical clustering helps yet does not match joint spectral methods on relational motifs.CA is most competitive when few factor coordinates describe the matrix; MD performs well when local neighborhood updates match the target, including leakage and transit cases, but not consistently on nested regimes.Source: §5.3 · p. 7

5.4 Consistency Across Matrix Size

  • As synthetic matrices grow from 100×90 to 400×360, Two-Walk retains the best R2S in every family and the best Band@10% except for the largest leakage matrix.Reported values need not vary monotonically with size because the generator changes the weighted relations by seed; the synthetic entries are means across matched instances, without hypothesis tests.Source: §5.4 · p. 7

5.5 What the Three Metrics Reveal

  • R2S, Band@10%, and MWB-AUC capture different properties, so a method may improve one without improving all three; the benchmark emphasizes consistency across the two metrics not used for selection.SIC to NAICS and the largest Family E leakage case each show a different ordering between R2S and Band@10%.Source: §5.5 · p. 7

5.6 Mosaic Case Analysis

  • In the tissue examples, changing order moves dominant correspondences toward the diagonal, while Mosaic geometry expands high-mass categories and contracts rare ones.Rectangle area represents the independence-baseline area, not the observed count; color represents the observed entry. Very small marginals can be hard to inspect, and unequal geometry weakens exact cell-to-cell comparison, so the figure supports an overview rather than every matrix-reading task.Source: §5.6 · p. 8

6 Discussion and Conclusion

Two-Walk extends bipartite spectral seriation with shared-neighbor structure, while Mosaic renders row and column marginals proportionally. The discussion qualifies where the ordering and layout are useful and what the evaluation does not establish.

6 Discussion and Conclusion

  • Two-Walk coordinates row and column orders by balancing shared-neighbor smoothness with alignment of directly related vertices.Mosaic provides a proportional rendering when row and column mass matters to the analysis.Source: §6 · p. 8
  • Two-Walk is consistently strong when shared profiles define overlapping or nested groups, but its benefit is smaller when one-step structure suffices, matrices are very small, or spatial and route locality govern the desired order.The two-walk terms do not directly encode geography, time, or route continuity unless those concepts appear in the neighborhoods.Source: §6 · p. 8
  • The benchmark metrics favor mass near matched positions on normalized axes, so hub, checkerboard, and spatial patterns need not become narrowly diagonal.LODES and MBTA illustrate this boundary; the metrics do not represent every meaningful matrix objective.Source: §6 · p. 8
  • Adaptive selection of α gives Two-Walk more flexibility than a fixed method, so the reported conclusion is limited to the adaptive procedure and independent outcome metrics.MWB-AUC is identified as selection aligned; the principal comparison uses R2S and Band@10%, which do not choose α.Source: §6 · p. 8
  • The sparse matrix-vector product avoids dense Gram matrices, but eigensolver convergence also depends on eigengap, conditioning, and tolerance, and no empirical runtime or memory superiority is claimed.The experiments evaluate ordering quality.Source: §6 · p. 8
  • Repeated eigenvalues or tied coordinates can make a Fiedler order nonunique, while weighted shared-neighbor Gram terms can emphasize high-mass vertices despite maximum-entry normalization.A degree-normalized variant may suit profile shape over shared mass, but is outside the method.Source: §6 · p. 8
  • Mosaic makes row and column marginals visible while color retains observed values, but can compress rare categories and does not replace equal-area heatmaps for precise comparison.The paired panels hold order fixed to isolate layout; they establish interpretability, not universal perceptual superiority.Source: §6 · p. 8

A Additional Qualitative Benchmark Cases

The appendix presents two additional full-workflow examples: the SIC-to-NAICS crosswalk and the OpenAlex author-by-topic matrix.

A Additional Qualitative Benchmark Cases

B Reproducibility Materials

The reproducibility materials include benchmark code and supporting artifacts; the accompanying figure caption identifies two additional qualitative examples.

B Reproducibility Materials

  • The code package includes the benchmark implementation, data construction scripts or download instructions, synthetic generators, and baseline wrappers.Source: B Reproducibility Materials · p. 9
  • It also includes per-instance permutations and metric records, selected α values, and scripts to regenerate the complete table and every submitted figure.Source: B Reproducibility Materials · p. 9
  • The additional examples are a SIC-to-NAICS crosswalk and an OpenAlex author-by-topic matrix, shown across input order, Two-Walk equal-area, and Mosaic views.Source: Figure 3 · p. 10
Loading 2610.29114v1…