Matrix Decomposition on Graphs: A Simplified Functional View

Abhishek Sharma, Maks OvsjanikovICASSP 2022 · DOI

Abstract

This paper introduces a unified, functional view of matrix decomposition problems on graphs, such as geometric matrix completion and graph-regularized dimensionality reduction. By representing the target matrix in the reduced basis of the row and column graph Laplacians, the authors show that the parameterization itself acts as a powerful regularizer, naturally enforcing a low-rank structure while bypassing complex optimization steps and running significantly faster than prior state-of-the-art methods.

Problem Statement

In many machine learning tasks, high-dimensional data resides on smooth, low-dimensional manifolds that can be represented as graphs (e.g., networks of similar users or items). Two classic problems that benefit from this graph structure are dimensionality reduction (e.g., PCA) and matrix completion (e.g., filling in missing entries in a recommender system).

Historically, incorporating graph structures into these problems has been computationally expensive. Traditional methods like Fast Robust PCA on Graphs (FRPCAG) rely on iterative Singular Value Decomposition (SVD) steps that scale poorly. More recent deep learning approaches, such as Spectral Geometric Matrix Completion (SGMC), introduce complex, non-convex formulations with numerous hyperparameters. This paper proposes a simpler, convex, and computationally efficient framework that addresses both problems without sacrificing accuracy.

Methodology: The Functional Map Framework

The authors adapt the functional map framework—a concept widely used in 3D shape processing—to matrix decomposition. Instead of directly optimizing a massive $m \times n$ matrix $X$, they factor it using the first few eigenvectors of the row and column graph Laplacians: $X = \Phi C \Psi^\top$, where $\Phi$ and $\Psi$ are pre-computed graph eigenbases and $C$ is a small coupling matrix.

This approach offers two major methodological advantages:

  1. Implicit Regularization: By restricting $X$ to the span of low-frequency graph eigenvectors, the model inherently enforces a low-rank, smooth approximation. The authors prove that if the underlying matrix is "basis consistent," simply minimizing reconstruction error over $C$ is sufficient for recovery.
  2. Laplacian Commutativity: A simple convex regularizer encourages the functional map to commute with graph Laplacians. This penalizes high-frequency noise and preserves global, low-frequency signals defined on the graphs.

Experimental Results

The framework was evaluated on dimensionality reduction (clustering/classification) and geometric matrix completion tasks using standard benchmarks like ORL, COIL20, MFEAT, BCI, Movielens-100K, and Flixster.

Clustering purity comparison across various datasets, showing the proposed method ("Ours") consistently matching or outperforming established baselines.

Key Findings

  • Massive Speedups: On synthetic matrix completion tasks, the proposed method runs at least 20 times faster than competing algorithms like SGMC because it optimizes far fewer variables and avoids iterative SVD.
  • Robustness to Sparsity: In data-poor regimes (e.g., only 1% sampling density), the functional method achieved an RMSE of $2 \times 10^{-2}$, significantly outperforming SGMC's $1 \times 10^{-1}$.
  • Real-World Competitiveness: On real-world recommender benchmarks, the method achieved test errors highly competitive with state-of-the-art deep learning approaches like GC-MC, despite its relative simplicity.
Test error (RMSE) on Flixster and Movielens-100K datasets. The proposed method achieves performance comparable to complex deep learning models.

Conclusion and Future Work

The core insight of this work is that appropriate parameterization can serve as a powerful form of regularization. By bypassing iterative SVD and using a single interpretable regularizer, the authors achieve state-of-the-art performance with massive speedups. While the method currently assumes "basis consistency," future work aims to scale this framework to massive graph-structured problems in domains like few-shot learning and knowledge-graph-based NLP.

Summary updated

BibTeX
@inproceedings{sharma2022matrix,
  author = {Abhishek Sharma and Maks Ovsjanikov},
  title = {{Matrix Decomposition on Graphs: A Simplified Functional View}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  doi = {10.1109/icassp43922.2022.9746243},
}

Loading related content...

Figure