  A powerful framework for studying graphs is to consider them as geometric
graphs: nodes are randomly sampled from an underlying metric space, and any
pair of nodes is connected if their distance is less than a specified
neighborhood radius. Currently, the literature mostly focuses on uniform
sampling and constant neighborhood radius. However, real-world graphs are
likely to be better represented by a model in which the sampling density and
the neighborhood radius can both vary over the latent space. For instance, in a
social network communities can be modeled as densely sampled areas, and hubs as
nodes with larger neighborhood radius. In this work, we first perform a
rigorous mathematical analysis of this (more general) class of models,
including derivations of the resulting graph shift operators. The key insight
is that graph shift operators should be corrected in order to avoid potential
distortions introduced by the non-uniform sampling. Then, we develop methods to
estimate the unknown sampling density in a self-supervised fashion. Finally, we
present exemplary applications in which the learnt density is used to 1)
correct the graph shift operator and improve performance on a variety of tasks,
2) improve pooling, and 3) extract knowledge from networks. Our experimental
findings support our theory and provide strong evidence for our model.
