# Multiscale Graph Construction Using Non-local Cluster Features

arXiv: https://arxiv.org/abs/2411.08371 · HTML: https://mlsanity.com/paper/2411.08371/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 13 Nov 2024.

## Builds on (most cited first, 12 of 12)

- [Fully Convolutional Networks for Semantic Segmentation](https://mlsanity.com/paper/1411.4038/) (2014)
- [PointNet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space](https://mlsanity.com/paper/1706.02413/) (2017)
- [SegNet: A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation](https://mlsanity.com/paper/1511.00561/) (2015)
- [Semantic Understanding of Scenes through the ADE20K Dataset](https://mlsanity.com/paper/1608.05442/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Joint 2D-3D-Semantic Data for Indoor Scene Understanding](https://mlsanity.com/paper/1702.01105/) (2017)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [SLIC: Self-Supervised Learning with Iterative Clustering for Human Action Videos](https://mlsanity.com/paper/2206.12534/) (2022)
- [Graph analysis of functional brain networks: practical issues in translational neuroscience](https://mlsanity.com/paper/1406.7391/) (2014)
- [Subgraph-based filterbanks for graph signals](https://mlsanity.com/paper/1509.05642/) (2015)
- [Image Segmentation Based on Multiscale Fast Spectral Clustering](https://mlsanity.com/paper/1812.04816/) (2018)
- [Optimizing k in kNN Graphs with Graph Learning Perspective](https://mlsanity.com/paper/2401.08245/) (2024)

## Abstract (arXiv)

This paper presents a multiscale graph construction method using both graph and signal features. Multiscale graph is a hierarchical representation of the graph, where a node at each level indicates a cluster in a finer resolution. To obtain the hierarchical clusters, existing methods often use graph clustering; however, they may ignore signal variations. As a result, these methods could fail to detect the clusters having similar features on nodes. In this paper, we consider graph and node-wise features simultaneously for multiscale clustering of a graph. With given clusters of the graph, the clusters are merged hierarchically in three steps: 1) Feature vectors in the clusters are extracted. 2) Similarities among cluster features are calculated using optimal transport. 3) A variable k-nearest neighbor graph (VkNNG) is constructed and graph spectral clustering is applied to the VkNNG to obtain clusters at a coarser scale. Additionally, the multiscale graph in this paper has textitnon-local characteristics: Nodes with similar features are merged even if they are spatially separated. In experiments on multiscale image and point cloud segmentation, we demonstrate the effectiveness of the proposed method.