https://arxiv.org/abs/1904.02963
Learning Erdős-Rényi Graphs under Partial Observations: Concentration or Sparsity?
Vincenzo Matta, Augusto Santos, Ali H. Sayed
(Submitted on 5 Apr 2019)
This work examines the problem of graph learning over a diffusion network when data can be collected from a limited portion of the network (partial observability). While most works in the literature rely on a degree of sparsity to provide guarantees of consistent graph recovery, our analysis moves away from this condition and includes the demanding setting of dense connectivity. We ascertain that suitable estimators of the combination matrix (i.e., the matrix that quantifies the pairwise interaction between nodes) possess an identifiability gap that enables the discrimination between connected and disconnected nodes. Fundamental conditions are established under which the subgraph of monitored nodes can be recovered, with high probability as the network size increases, through universal clustering algorithms. This claim is proved for three matrix estimators: i) the Granger estimator that adapts to the partial observability setting the solution that is optimal under full observability ; ii) the one-lag correlation matrix; and iii) the residual estimator based on the difference between two consecutive time samples. Comparison among the estimators is performed through illustrative examples that reveal how estimators that are not optimal in the full observability regime can outperform the Granger estimator in the partial observability regime. The analysis reveals that the fundamental property enabling consistent graph learning is the statistical concentration of node degrees, rather than the sparsity of connections.

---

интересно.
вообще есть такая мета-задача: пускай у вас есть очень большой граф (больше интернета, интернет слишком маленький) и вам нужно оценить его размер. например, найти диаметр.
в римановой геометрии есть теорема Майерса,
которая говорит, что если у вас кривизна Риччи ограничена снизу положительной константой k, то диаметр
многообразия не превосходит pi*sqr(n-1)/sqr(k), где n-размерность.
нам нужно обобщение понятия ограниченности кривизны ричи для графов. именно риччи, потому что для ограниченной секционной кривизны это, конечно, тоже работает, такие пространства называются пространствами Александрова -- но графы Александрова не очень интересны -- они необходимо являются многообразиями , то есть это циклический граф или граф изометричный прямой или отрезку.
правильные определения ограниченной кривизный Риччи есть (Лотт-Вилани, Яу с соавторами, Оливье), то есть такие, при которых теорема Маерса верна. Все эти определения довольно муторные (и естественны только для графов с дополнительными структурами - с мерой или размерностью).
то есть метрическая часть более-менее решена (единственная проблема, что оценка есть при положительной отделенной от нуля кривизне, что вообще говоря, условие редкое, не исключено что для практических задач пустое -- но возможно, что в каких-то задачах математики или народного хозяйства есть какая-то естественная положительность, которая как раз дает такие графы; вопрос: можно ли сказать что-то о кривизне графа, если его матрица тотально позитивна).

вторая часть значительно более сложная, как раз статистическая. мы не имеем весь граф в своем распоряжении, естественно, а знаем только его какие-то статистические свойства. нужно понять какие распределения нам нужно знать, чтобы достоверно восстанавливать диаметр.

определения ограниченной кривизны локально (определение Яу точно -- там вообще нужно знать только точку, ее соседей и расстояния между соседями, определение Лотта-Вилани-Оливье тоже, но я не уверен на 100%) и
самый наивный способ был бы просто случайным образом накидывать точки на граф и мерить кривизну X_i в них,
и подбирать функцию F_i(X_i) которая бы сходилась к диаметру, минимизируя какое-нибудь апостериорное отклонение.
но подозреваю, что сходиться будет очень медленно и точки нужно будет накидывать более хитро как раз с учетом кривизны, в области где складок может быть много нужно накидывать больше точек. вот в статье по ссылке кажется есть какие-то общие результаты о статистическом изучении графа (и внушает некоторую надежду, так как в практических задачах, которые мне встречались, контроль на степенью вершин как раз есть -- он и требуется в определении кривизны тоже).