  The concept of dimension is essential to grasp the complexity of data. A
naive approach to determine the dimension of a dataset is based on the number
of attributes. More sophisticated methods derive a notion of intrinsic
dimension (ID) that employs more complex feature functions, e.g., distances
between data points. Yet, many of these approaches are based on empirical
observations, cannot cope with the geometric character of contemporary
datasets, and do lack an axiomatic foundation. A different approach was
proposed by V. Pestov, who links the intrinsic dimension axiomatically to the
mathematical concentration of measure phenomenon. First methods to compute this
and related notions for ID were computationally intractable for large-scale
real-world datasets. In the present work, we derive a computationally feasible
method for determining said axiomatic ID functions. Moreover, we demonstrate
how the geometric properties of complex data are accounted for in our modeling.
In particular, we propose a principle way to incorporate neighborhood
information, as in graph data, into the ID. This allows for new insights into
common graph learning procedures, which we illustrate by experiments on the
Open Graph Benchmark.
