Обучение и масштабирование сетей на основе вложения графа
Обучение и масштабирование сетей на основе вложения графа
Авторы
Аннотация
Надежное оценивание алгоритмов интеллектуального анализа сетей предполагает тестирование их статистической значимости и масштабируемости. Обычно это достигается путем подбора нескольких графов разного размера из разных доменов. Однако свойства графов и, таким образом, результаты оценки могут сильно различаться от одного домена к другому. Отсюда вытекает необходимость агрегирования результатов по множеству графов из каждого домена.
В статье представлен метод автоматического извлечения свойств ориентированного графа из произвольного домена и метод генерации похожих графов с возможностью масштабирования на вещественный коэффициент. Генерация нескольких графов близкого размера позволяет проводить тестирование значимости, в то время как возможность масштабирования размера графа позволяет оценивать масштабируемость алгоритмов. Предлагаемый метод основан на вложении исходного графа в пространство малой размерности, что позволяет закодировать свойства графа в наборе векторов-вершин. Веса ребер и сообщества вершин также могут быть сымитированы дополнительно.
Мы показываем, что подход на основе вложения обеспечивает вариативность синтетических графов, сохраняя при этом распределение степеней вершин и распределение подграфов близкими к исходным. Таким образом, этот метод может повысить достоверность тестов значимости и масштабируемости сетевых алгоритмов без необходимости поиска дополнительных данных. Мы также показываем, что подход на основе вложения позволяет воспроизводить многие свойства в генерируемых графах, что не может быть достигнуто другими генераторами, имитирующими данный граф.
Работа получила приз "Лучшая студенческая статья" (Best Stdent Paper Award) на конференции ECML-PKDD 2017
Ключевые слова
Издание
Proceedings of ECML PKDD 2017
Научная группа
Все публикации за 2017 год
Все публикации