# Preserving Minority Structures in Graph Sampling

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2020.

## Built on by (most cited first, 5 of 5)

- [Foundation Models Meet Visualizations: Challenges and Opportunities](https://mlsanity.com/paper/2310.05771/) (2023)
- [ZOOMER: Boosting Retrieval on Web-scale Graphs by Regions of Interest](https://mlsanity.com/paper/2203.12596/) (2022)
- [Structural-Entropy-Based Sample Selection for Efficient and Effective Learning](https://mlsanity.com/paper/2410.02268/) (2024)
- [HeteroSample: Meta-path Guided Sampling for Heterogeneous Graph Representation Learning](https://mlsanity.com/paper/2411.07022/) (2024)
- [Learning to Compress Graphs via Dual Agents for Consistent Topological Robustness Evaluation](https://mlsanity.com/paper/2511.18958/) (2025)

## Abstract (arXiv)

Sampling is a widely used graph reduction technique to accelerate graph computations and simplify graph visualizations. By comprehensively analyzing the literature on graph sampling, we assume that existing algorithms cannot effectively preserve minority structures that are rare and small in a graph but are very important in graph analysis. In this work, we initially conduct a pilot user study to investigate representative minority structures that are most appealing to human viewers. We then perform an experimental study to evaluate the performance of existing graph sampling algorithms regarding minority structure preservation. Results confirm our assumption and suggest key points for designing a new graph sampling approach named mino-centric graph sampling (MCGS). In this approach, a triangle-based algorithm and a cut-point-based algorithm are proposed to efficiently identify minority structures. A set of importance assessment criteria are designed to guide the preservation of important minority structures. Three optimization objectives are introduced into a greedy strategy to balance the preservation between minority and majority structures and suppress the generation of new minority structures. A series of experiments and case studies are conducted to evaluate the effectiveness of the proposed MCGS.