Multiresolution Matrix Factorization and Wavelet Networks on Graphs

Truong Son Hy, Risi KondorTAG-ML 2022 · OpenReview

Abstract

Multiresolution Matrix Factorization (MMF) is unusual amongst fast matrix factorization algorithms in that it does not make a low rank assumption. This makes MMF especially well suited to modeling certain types of graphs with complex multiscale or hierarchical structure. While MMF promises to yield a useful wavelet basis, finding the factorization itself is hard, and existing greedy methods tend to be brittle. In this paper, we propose a "learnable" version of MMF that carefully optimizes the factorization with a combination of reinforcement learning and Stiefel manifold optimization through backpropagating errors. We show that the resulting wavelet basis far outperforms prior MMF algorithms and provides the first version of this type of factorization that can be robustly deployed on standard learning tasks. Furthermore, we construct the wavelet neural networks (WNNs) learning graphs on the spectral domain with the wavelet basis produced by our MMF learning algorithm. Our wavelet networks are competitive against other state-of-the-art methods in molecular graphs classification and node classification on citation graphs.

Introduction

Many real-world datasets, particularly graphs like social networks or molecular structures, are represented by large matrices with complex, hierarchical organizations. Traditional linear algebra methods often rely on a "low-rank assumption"—the idea that most of the important information can be squeezed into a much smaller space. However, hierarchical data often breaks this assumption, containing critical information at multiple scales.

Multiresolution Matrix Factorization (MMF) is designed to capture these multi-scale structures. While powerful in theory, MMF is notoriously difficult to implement because it requires solving two hard problems simultaneously: a combinatorial problem of deciding which specific indices to group and rotate at each level, and a continuous problem of finding the optimal rotation matrices. Previous attempts used "greedy" heuristics that were brittle and often led to sub-optimal results. This paper introduces a robust, end-to-end learning framework to replace these heuristics.

Learnable MMF and Wavelet Neural Networks

The proposed "learnable" MMF framework tackles optimization challenges using modern deep learning techniques:

  1. Reinforcement Learning (RL) for Index Selection: The combinatorial task of picking indices is framed as a Markov Decision Process. A Graph Convolutional Policy Network (GNN) acts as an agent that learns to select "pivots" and related indices for rotation, trained via the REINFORCE algorithm.
  2. Stiefel Manifold Optimization for Rotations: To ensure rotation matrices remain orthogonal, the authors use gradient descent specifically designed for the Stiefel manifold, optimizing all rotations across the hierarchy simultaneously.
  3. Wavelet Neural Networks (WNNs): The learned MMF provides a unique "wavelet basis" for convolutions in the spectral domain. Unlike standard Graph Fourier Transforms that use dense eigenbases, WNNs use these MMF wavelets, which are naturally sparse and localized.

Multiresolution Localization

A key advantage of MMF is the localization of its basis. Standard graph spectral methods often use global bases that fail to reflect local community structures. MMF wavelets are highly localized at low levels and become broader at higher levels, effectively capturing hierarchical structures.

Visualization of wavelets at different resolutions (l=1, 20, 39) on a Cayley tree. Low-index wavelets are highly localized, while high-index ones spread across the graph.

Experimental Evaluation

The model was evaluated on four standard molecular graph classification benchmarks: MUTAG, PTC, PROTEINS, and NCI1. These datasets range from mutagenic compounds to protein structures, representing various hierarchical complexities.

Key Results

The MMF-based Wavelet Neural Networks proved highly competitive against state-of-the-art (SOTA) graph learning methods. On the PROTEINS dataset, the WNN achieved an accuracy of 78.72%, outperforming all eight baseline methods, including popular architectures like DGCNN and PSCN.

Table 1: Molecular graph classification results comparing MMF to various baseline methods.

Beyond accuracy, MMF offers efficiency through sparsity. For instance, in the PROTEINS dataset, the learned wavelets contain only ~2.26% non-zero elements, allowing for significantly faster computations compared to dense matrix methods.

Conclusion

This work demonstrates that combining reinforcement learning with manifold optimization can unlock the potential of Multiresolution Matrix Factorization for graph learning. By moving beyond low-rank assumptions and leveraging localized, sparse wavelet bases, WNNs provide a robust and efficient alternative for modeling complex hierarchical data. Future work may focus on tighter integration of the MMF learning process to further reduce the computational overhead of the RL-based index selection.

Summary updated

Abstract

Multiresolution Matrix Factorization (MMF) is unusual amongst fast matrix factorization algorithms in that it does not make a low rank assumption. This makes MMF especially well suited to modeling certain types of graphs with complex multiscale or hierarchical structure. While MMF promises to yield a useful wavelet basis, finding the factorization itself is hard, and existing greedy methods tend to be brittle. In this paper, we propose a "learnable" version of MMF that carefully optimizes the factorization with a combination of reinforcement learning and Stiefel manifold optimization through backpropagating errors. We show that the resulting wavelet basis far outperforms prior MMF algorithms and provides the first version of this type of factorization that can be robustly deployed on standard learning tasks. Furthermore, we construct the wavelet neural networks (WNNs) learning graphs on the spectral domain with the wavelet basis produced by our MMF learning algorithm. Our wavelet networks are competitive against other state-of-the-art methods in molecular graphs classification and node classification on citation graphs. Our complete paper with the Appendix and more experiments is publicly available at https://arxiv.org/pdf/2111.01940.pdf. We release our implementation at https://github.com/risilab/Learnable_MMF/.
BibTeX
@inproceedings{hy2022multiresolution,
  author = {Truong Son Hy and Risi Kondor},
  title = {{Multiresolution Matrix Factorization and Wavelet Networks on Graphs}},
  booktitle = {TAG-ML},
  year = {2022},
  url = {https://openreview.net/forum?id=PiAJZrXwXa},
}
Figure