- Быстрая онлайн-маркировка узлов для очень больших графиков (arXiv)
Автор: Баоцзянь Чжоу, Ифань Сунь, Реза Бабанежад.
Аннотация: В этой статье исследуется проблема онлайн-классификации узлов в условиях трансдуктивного обучения. Текущие методы либо инвертируют матрицу ядра графа со временем выполнения O (n3) и пространственной сложностью O (n2), либо производят выборку большого объема случайных остовных деревьев, поэтому их трудно масштабировать до больших графов. В этой работе мы предлагаем усовершенствование, основанное на методе \textit{онлайн-релаксации}, представленном в серии работ (Рахлин и др., 2012; Рахлин и Шридхаран, 2015; 2017). Сначала мы доказываем эффективное сожаление O(n1+γ----√) при выборе подходящих параметризованных ядер графа, а затем предлагаем приближенный алгоритм FastONL с сожалением O(kn1+γ----√) на основе этого ослабления. Ключом FastONL является метод \textit{обобщенный локальный толчок}, который эффективно аппроксимирует столбцы обратной матрицы и применяется к ряду популярных ядер. Кроме того, стоимость прогноза составляет O(vol(S)log1/ε), локально зависящая от графа с линейной стоимостью памяти. Эксперименты показывают, что наш масштабируемый метод обеспечивает лучший компромисс между локальной и глобальной согласованностью.
2. Вычисление метрик на основе расстояния на очень больших графиках (arXiv)
Автор: Джамбаттиста Амати, Антонио Кручиани, Симоне Анджелини, Даниэле Пасквини, Паола Вокка.
Аннотация: Мы предлагаем PROPAGATE, систему быстрой аппроксимации для оценки метрик на основе расстояния на очень больших графиках, таких как (эффективный) диаметр, (эффективный) радиус или среднее расстояние с небольшой ошибкой. Фреймворк присваивает начальные значения узлам и распространяет их в стиле BFS, вычисляя набор соседей до тех пор, пока мы не получим либо весь набор вершин (диаметр), либо заданный процент (эффективный диаметр). На каждой итерации мы получаем сжатые булевы представления обнаруженных до сих пор множеств соседства. Фреймворк PROPAGATE предлагает два алгоритма: PROPAGATE-P, который распространяет все начальные числа s параллельно, и PROPAGATE-s, который распространяет начальные числа последовательно. Для каждого узла сжатое представление алгоритма PROPAGATE-P требует s бит, а алгоритма PROPAGATE-S — только 1 бит. Оба алгоритма вычисляют среднее расстояние, эффективный диаметр, диаметр и скорость связности с небольшой ошибкой с высокой вероятностью: для любого ε>0 и с использованием s=Θ(lognε2) выборочных узлов ошибка для среднего расстояния ограничена по ξ=εΔα, ошибка для эффективного диаметра и диаметра ограничены ξ=εα, а ошибка для скорости связности ограничена ε, где Δ — диаметр, а α — мера связности графа. Временная сложность равна O(m∆lognε2), где m — количество ребер графа. Экспериментальные результаты показывают, что структура PROPAGATE улучшает текущее состояние дел как по точности, так и по скорости. Кроме того, мы экспериментально показываем, что PROPAGATE-S также очень эффективен для решения проблемы кратчайшего пути для всех пар в очень больших графах.
