# Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 80 references that are in the map.
- First posted on arXiv 3 Aug 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size](https://mlsanity.com/paper/1602.07360/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [TimeChat: A Time-sensitive Multimodal Large Language Model for Long Video Understanding](https://mlsanity.com/paper/2312.02051/) (2023)
- [Video Summarization with Long Short-term Memory](https://mlsanity.com/paper/1605.08110/) (2016)
- [Video Summarization Using Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.06072/) (2021)
- [Summarizing Videos with Attention](https://mlsanity.com/paper/1812.01969/) (2018)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [Supervised Video Summarization via Multiple Feature Sets with Parallel Attention](https://mlsanity.com/paper/2104.11530/) (2021)
- [CSTA: CNN-based Spatiotemporal Attention for Video Summarization](https://mlsanity.com/paper/2405.11905/) (2024)
- [Video Summarization through Reinforcement Learning with a 3D Spatio-Temporal U-Net](https://mlsanity.com/paper/2106.10528/) (2021)
- [Dissimilarity-based Sparse Subset Selection](https://mlsanity.com/paper/1407.6810/) (2014)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2006.08816/) (2020)
- [Convolutional Hierarchical Attention Network for Query-Focused Video Summarization](https://mlsanity.com/paper/2002.03740/) (2020)
- [Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images](https://mlsanity.com/paper/1607.01895/) (2016)
- [A General Framework for Edited Video and Raw Video Summarization](https://mlsanity.com/paper/1904.10669/) (2019)
- [Shorts vs. Regular Videos on YouTube: A Comparative Analysis of User Engagement and Content Creation Trends](https://mlsanity.com/paper/2403.00454/) (2024)
- [Eigendecomposition-Free Sampling Set Selection for Graph Signals](https://mlsanity.com/paper/1809.01827/) (2018)
- [Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment](https://mlsanity.com/paper/1907.06179/) (2019)
- [Video Summarization Overview](https://mlsanity.com/paper/2210.11707/) (2022)
- [Structured sampling and fast reconstruction of smooth graph signals](https://mlsanity.com/paper/1705.02202/) (2017)
- [A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series](https://mlsanity.com/paper/1803.03353/) (2018)
- [Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment](https://mlsanity.com/paper/2110.11420/) (2021)

## Abstract (arXiv)

User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several keyframes in linear-time via fast graph sampling based on Gershgorin disc alignment (GDA). Specifically, we first model a sequence of N frames in a UGV as an M-hop path graph cGo for M ll N, where the similarity between two frames within M time instants is encoded as a positive edge based on feature similarity. Towards efficient sampling, we then ``unfold'' cGo to a 1-hop path graph cG, specified by a generalized graph Laplacian matrix cL, via one of two graph unfolding procedures with provable performance bounds. We show that maximizing the smallest eigenvalue λmin(B) of a coefficient matrix B = diagh + μ cL, where h is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We maximize instead the Gershgorin circle theorem (GCT) lower bound λ^-min(B) by choosing h via a new fast graph sampling algorithm that iteratively aligns left-ends of Gershgorin discs for all graph nodes (frames). Experiments on multiple short video datasets show that our algorithm achieves comparable or better keyframe selection performance compared to state-of-the-art methods, at a substantially reduced complexity.