Preserving Minority Structures in Graph Sampling

Ying Zhao, Haojin Jiang, Qi'an Chen, Yaqi Qin, Huixuan Xie, Yitao Wu, Shixia Liu, Zhiguang Zhou, Jiazhi Xia, Fangfang Zhou

TL;DR

Existing graph sampling algorithms are great at preserving the "big picture" (majority structures like large communities), but they often accidentally delete or distort rare, small, yet critically important "minority structures" like bridges and high-degree outliers. This paper introduces Mino-Centric Graph Sampling (MCGS), a new framework that specifically identifies, ranks, and protects these vital structural needles in the haystack while maintaining the overall representativeness of the graph.

What Problem Does This Paper Address?

Graph sampling is essential for making massive networks (like social webs or protein interactions) small enough to visualize and compute. However, most current algorithms aim to preserve global statistical properties, such as the power-law degree distribution.

The authors argue that this "majority-rules" approach overlooks minority structures: rare configurations that occupy very few nodes but carry immense analytical weight (e.g., a single "bridge" node connecting two massive clusters). Through a pilot user study, they found that human analysts are actually more interested in these anomalies than in the average nodes. Furthermore, standard sampling doesn't just lose these structures; it often creates "fake" ones—for example, by deleting enough edges from a normal cluster that it accidentally looks like a rare "star" structure in the sample.

Methods

The authors propose MCGS (Mino-Centric Graph Sampling), which operates in four main stages:

  1. Identification: Using two novel, fast algorithms to find minority structures.
  2. A triangle-based algorithm identifies "Super Pivots" (hubs with interconnected neighbors) and "Huge Stars" (hubs with isolated neighbors).
  3. A cut-point-based algorithm identifies "Rims" (marginal appendages) and "Ties" (bridges between communities).
  4. Ranking: Minority structures are ranked by importance based on visual and structural criteria (like degree or chain length).
  5. Minority Sampling: The most important structures and a proportion of their neighbors are "locked" into the sample to ensure they remain recognizable.
  6. Majority Sampling: A greedy optimization strategy fills the remaining sample budget. It selects nodes that minimize a "loss function" based on three objectives: degree distribution similarity, connectivity preservation, and structural similarity (Jaccard Index).

Datasets

The researchers used a diverse array of real-world networks for their experiments:

  • Pilot Study: 34 real-world datasets (including social, web, and communication networks).
  • Experimental Evaluation: 12 representative datasets, including Facebook1912, Facebook107, AS-733 (autonomous systems), and PGP (Pretty Good Privacy network).
  • Case Studies: Specifically highlighted AS-733, Cpan (Perl developer network), and Facebook1684.

Key Insights and Ideas

  • Human Interest vs. Statistical Metrics: The user study revealed a major gap: what algorithms think is "representative" (the average) is often what humans find "boring." Analysts naturally gravitate toward outliers like super-hubs and bridges.
  • The Danger of Degeneration: Sampling isn't just about losing data; it's about corruption. The authors quantified "New Minority Structure Generation," showing that standard algorithms frequently create "phantom" structures that weren't in the original data, leading to false conclusions.
  • The "Induction" Secret: The authors found that algorithms using a "graph induction" step (re-adding edges between sampled nodes) are significantly better at suppressing the generation of fake minority structures.

Key Results

  • Superior Preservation: In significance tests against 20 reference algorithms, MCGS won 12 out of 12 categories for minority structure preservation.
  • Quantitative Wins: MCGS achieved a Minority Structure Preservation Rate (MSPR) of nearly 1.0 for super pivots and huge stars, meaning it kept almost all of them even at low sampling rates.
  • Suppressing "Fakes": MCGS showed the lowest New Minority Structure Generation Rate (MSGR), effectively preventing the creation of phantom hubs or bridges.
  • Visual Fidelity: In subjective assessments, participants rated MCGS higher than popular methods like Forest Fire (FF) or Random Walk (RW) for preserving the "overall shape" and "margin structures" of the graphs.

Limitations and Future Work

  • Graph Types: The current work focuses primarily on simple, undirected, scale-free graphs. The authors note that definitions of "minority structures" might need to change for directed or bipartite graphs.
  • Visual Clutter: While MCGS preserves structures in the data space, very large graphs still suffer from visual "hairball" effects when rendered. The authors suggest exploring sampling directly in the "visual space" (pixel-based) as a next step.
  • Scalability: While the identification algorithms are fast ($O(n+m)$), the greedy optimization step for majority structures is more computationally intensive than simple random sampling, though still acceptable for medium-to-large graphs.

Summary updated

Abstract

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.
BibTeX
@article{zhao2021preserving,
  author = {Ying Zhao and Haojin Jiang and Qi'an Chen and Yaqi Qin and Huixuan Xie and Yitao Wu and Shixia Liu and Zhiguang Zhou and Jiazhi Xia and Fangfang Zhou},
  title = {{Preserving Minority Structures in Graph Sampling}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2021},
  url = {https://openreview.net/forum?id=nJDZGK3Z97},
}
Figure