CS Paper Radar

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

cs.LG cs.HC ·submitted 2026-10-21 02:55 UTC · v1
theoryunusual

Abstract

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.

Comment
10 pages, 3 figures, 1 table

Closest papers

Nearest neighbours by meaning across the whole index.

Pattern-Based Matrix Analysis Under Permutations

cs.LG ·2026-11-13 ·Andrei Ermakov
top venue similarity 0.57
Abstract · Accepted at NeurIPS 2026 (The Fortieth Annual Conference on Neural Information Processing Systems)

Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.

0.38

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

cs.LG cs.SI ·2026-08-30 ·Lutz Oettershagen, Honglian Wang, Aristides Gionis
top venue similarity 0.55
Abstract · Accepted at ICDM 2026

We study unsupervised hypergraph alignment, where the goal is to infer node correspondences between two hypergraphs using only structural information, without node features, labels, seed matches, or side information. Direct higher-order formulations can represent hyperedge interactions faithfully, but they can be computationally demanding and cumbersome for non-uniform hypergraphs. Graph-reduction approaches introduce a different challenge: clique expansions keep the alignment problem on the original node set but collapse all hyperedge evidence into one pairwise graph, whereas bipartite expansions preserve incidence structure but enlarge the problem from nodes to nodes plus hyperedges. We introduce FALCON (Filtration-based hypergrAph aLignment via Cross-scale Optimal traNsport), an unsupervised optimal-transport framework for hypergraph alignment. Instead of representing each hypergraph by a single collapsed clique graph, FALCON constructs a filtration-induced sequence of clique-based co-occurrence dissimilarity matrices and jointly aligns all levels through one shared multi-scale Gromov--Wasserstein (GW) objective. The shared transport plan enforces a globally consistent node correspondence across filtration levels while avoiding the auxiliary hyperedge nodes introduced by bipartite expansion. Experiments on perturbation benchmarks derived from real-world hypergraphs show that FALCON is robust to structural noise and in almost all cases outperforms strong graph- and hypergraph-alignment baselines.

0.43

Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time

cs.DS ·2026-10-07 ·Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen +2 more
similarity 0.54
Abstract · 38 pages, 4 figures

A graph $G$ is $k$-degenerate if there exists an ordering $v_1, v_2, \dots, v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j < i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1, 2, \dots, n\}$ in which every vertex $i$ has at most $k$ neighbors among $1, 2, \dots, i-1$. We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered $k$-degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered $k$-degenerate graph in constant amortized time per graph, using $O(n^2)$ space, while ranking and unranking take $O(n^2)$ time and $O(n^2)$ space.

0.30

Federated Community Detection in Bipartite Networks

cs.LG stat.MLstat.COstat.ME ·2026-10-19 ·Wanjie Wang
similarity 0.53
Abstract · 47 pages, 10 figures, 6 tables

We study federated spectral estimation when a large matrix is horizontally partitioned across servers that cannot share raw data. We propose FLICKER, a target-specific gradient-based power iteration that recovers a singular direction associated with a prescribed spectral target using only matrix-vector products on local blocks. Different target directions can be recovered independently and in parallel. We establish non-asymptotic convergence guarantees and provide a recursive grid-search procedure for spectral target selection. Building on FLICKER, we develop BiFLICKER for federated community detection in bipartite networks, together with a sequential projected variant for nearby or repeated singular directions. Under a sparse bipartite stochastic block model, we show that properly rescaled leading singular values from a reference server provide valid global targets, and that Sequential BiFLICKER achieves a vanishing misclustering rate and exact recovery under stronger sparsity conditions. Simulations show that BiFLICKER remains close to centralized spectral clustering and is more robust than existing federated spectral baselines when local sample sizes are small. On a LastFM user-artist network naturally partitioned by country, Sequential BiFLICKER attains an overall ARI of 0.94 against centralized clustering while revealing cross-country communities with distinct listening profiles.

0.22

CorrFlow: Exact and Permutation-Equivariant Flow Matching on the Correlation Elliptope

cs.LG stat.MLq-fin.RM ·2026-10-09 ·Gautier Marti
publishedcode/data similarity 0.53
Abstract · Accepted at NeurReps 2026, the NeurIPS workshop on Symmetry and Geometry in Neural Representations. Code: https://github.com/gautiermarti/Co…

Correlation matrices combine nonlinear positive-definiteness constraints with a simultaneous row-column permutation symmetry. Their generation therefore involves two distinct problems. First, every output must remain on the correlation elliptope, irrespective of how its variables are ordered. Second, the generator must learn the domain-specific distribution occupied by empirical data inside that valid space. Existing financial image generators mix these problems: they learn ordered matrix entries and repair invalid draws afterward. We introduce CorrFlow, which separates them. A generalized Fisher transform maps full-rank correlation matrices bijectively to unconstrained coordinates, guaranteeing valid outputs without projection. A graph flow-matching network learns the empirical distribution in those coordinates and is permutation equivariant: reordering the variables only reorders the output. We compare a conditional CorrGAN reimplementation, image diffusion, and CorrFlow on $80\times80$ Taiwan equity matrices using five seeds per neural method. CorrFlow produces 100% valid draws without repair and obtains feature sliced-Wasserstein distance $.712\pm.141$, versus $4.339\pm.252$ for CorrGAN and $4.610\pm.191$ for image diffusion after their invalid outputs are projected back to the correlation space. It also improves this distance over historical lookup, while lookup retains higher local coverage. These results support the combined construction under the evaluated training budget; they do not establish superiority over fully tuned image models or isolate the contribution of each component.

0.48

Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra

cs.DS ·2026-10-26 ·Gonzalo Navarro
survey similarity 0.52
Abstract

Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies \emph{computation-friendly} compression: formats that are not only small, but let us carry out matrix--vector products, and in some cases matrix--matrix products, sums and closures, directly on the compressed representation {\em in time proportional to that compressed size}. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros ($k^2$-trees and their variants), similarity between rows (Boldi--Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the representation, the algorithms, the theoretical guarantees and the empirical performance. Further, we show that the last three families are instances of a single general scheme, which we call a {\em sparse straight-line factorization} of the matrix, whose forward and backward substitutions evaluate right and left products in time proportional to the size of the representation, and that the product of two such factorizations is again one, which gives matrix--matrix products with a compressed output. We also relate the model to linear circuits, give simple recompression steps, and study the size of the smallest factorization: worst-case bounds, separations from each family, and parallelism. We close with a cross-family comparison and a list of open problems.

0.42

Notrix: Understanding Machine Learning Solutions Across Computational Notebooks at Scale

cs.HC ·2026-09-18 ·Xiaotian Su, Hongxin Fu, Xiaoyu Zhang, April Yi Wang
similarity 0.52
Abstract

Computational notebooks make problem-solving visible, but typically only one notebook at a time. Meanwhile, in data science platforms like Kaggle, one competition can accumulate hundreds of notebooks. Effective collection-level analysis requires characterizing recurring solution patterns across all notebooks, as well as isolating specific notebooks for closer examination and learning. However, standard notebooks provide no common basis for this. Their workflows are nonlinear, cells declare no intent, and identical code can serve different ends, leaving hundreds of notebooks as separate documents. In this paper, we present Notrix, an interactive visual analytics tool for profiling hundreds of notebooks as one collection. Inspired by a formative study (N = 11), Notrix classifies every cell into one of thirteen machine learning (ML) stages, turning each notebook into a stage sequence, and clusters those sequences by structure rather than by code. To keep the representation constant as the scope narrows from the whole collection to a single cell, Notrix features three coordinated views---Workflow, Structural Matrix, and Detail---that appear at all four levels of granularity. In a within-subject study (N = 17) using two Kaggle collections of over 400 notebooks each, we observed participants answered questions about all notebooks more accurately with Notrix (median 88% vs. 50%) while opening 80% fewer notebooks per minute. Notably, four of the fourteen answered it without opening a single notebook (interaction logs, N = 14). Participants also reported significantly lower mental demand, temporal demand, and stress with Notrix (Holm-Bonferroni adjusted).

0.27

A Sparse Low-Rank Biclique Decomposition for Graphs

cs.LG ·2026-11-19 ·Antoine Vialle, Sergei Gerasimov, Aref Einizade, Antonio Ortega, Fragkiskos D. Malliaros +1 more
top venuecode/data similarity 0.52
Abstract · Accepted at NeurIPS 2026. 29 pages, including references and appendices

Low-rank plus sparse decompositions, such as robust PCA, typically model the low-rank component as dense and the sparse component as corruption. This viewpoint is poorly suited to graph adjacency matrices, where sparsity is structural and dense low-rank factors destroy the combinatorial and computational properties of the graph. We propose signed biclique decomposition (SBD), a sparse low-rank decomposition for integer-weighted graphs that represents the structured component as a sum of sparse signed binary rank-one factors, together with a sparse signed residual. The resulting representation remains discrete, interpretable, sparse, and compatible with standard linear algebra. We formulate fixed-rank and greedy SBD objectives and derive a gain-based greedy algorithm with theoretical guarantees. Empirically, SBD recovers block structure in noisy graphs, while its factorized representation enables efficient sparse matrix-matrix multiplication (SpMM). On real graphs with strong shared-neighborhood structure, SBD achieves compression factors above $10$ and SpMM speedups up to $6\times$ over cuSPARSE, suggesting a practical alternative to dense low-rank decompositions for graphs. Code is available at https://github.com/IAntoineV/sbd.

0.50