There are many ways a graph can be sampled, e.g., by sampling nodes, edges, paths, or other substructures [1]}, [2]}.
Depending on our measurement goal, the elements with different properties may have different importance and should be sampled with a different probability. For example, Fig. REF (a) depicts the world's population, with residents of China (1.3B people) represented by blue nodes, of the Vatican (800 people) by black nodes, and all other nationalities represented by white nodes. Assume that we want to compare the median income in China and Vatican.
Taking a uniform sample of size 100 from the entire world's population is ineffective, because most of the samples will come from countries other than China and Vatican.
Even restricting our sample to the union of China and Vatican will not help much, as our sample is unlikely to include any Vatican resident. In contrast, uniformly sampling 50 Chinese and 50 Vaticanese residents
would be much more accurate with the same sampling budget.
