Контакты: drobyshevsky@ispras.ru

Образование: ФУПМ МФТИ — бакалавриат (2013), магистратура (2015), аспирантура (2019); к.ф.-м.н. (2019)

Научные интересы:

• Искуственный интеллект — доверенный ИИ (trusted AI), объяснимый ИИ (XAI)
• Машинное обучение — графовые нейронные сети (Graph neural networks)
• Сложные сети (complex networks) — алгоритмы сбора (crawling), модели случайных графов (random graphs), вложение графов (graph embedding)
• Биоинформатика — задачи, связанные с анализом графов

Публикации:

профиль на GoogleScholar

 НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ

Основное направление на ближайшие 1-2 года — повышение интерпретируемости алгоритмов машинного обучения, в частности графовых нейросетей.

Сейчас в сфере ИИ все более активно обсуждаются проблемы доверия к алгоритмам машинного обучения. Как понять, почему сложный алгоритм выдает тот или иной результат? Что если ИИ ставит неверный диагноз пациенту, принимает плохое финансовое решение или выносит неверный приговор? Как определить, почему алгоритм ошибся, если это нейросеть с сотнями миллионов параметров? Для решения этих вопросов развиваются методы повышения интерпретируемости алгоримтов машинного обучения: изобретаются способы объяснения и методы встраивания интерпретируемости в модели. Однако, зачастую хорошо интерпретируемые методы (дерево решений, метод ближайших соседей) показывают качество ниже, чем state-of-the-art модели (нейросети), и на практике необходимо искать компромисс между понятностью и качеством.

Последние годы модели графовых нейронных сетей показывают лучшие результаты в различных прикладных областях: анализ социальных сетей, поиск лекарств, рекомендательные системы, а также в биологии, химии, финансах и др. Число параметров у графовой нейросети существенно меньше чем у традиционной нейросети, но вся сложность интерпретации кроется в нерегулярной структуре самих графов и такие методы объяснения только начинают появляться.

Актуальным является вопрос доверия к ИИ с точки зрения уязвимости к атакам. В интернете можно найти различные видео, на котором человек надевает футболку со специальным изображением и становится «невидим» для камеры с распознаванием лиц. Существует множество типов атак и уязвимостей, в том числе еще никем не обнаруженных. В связи с этим свойство интерпретируемости моделей приобретает еще большее значение.

Примерные темы работ

• Исследование и разработка методов повышения интерпретируемости графовых нейронных сете.
• Исследование и разработка методов построения объяснимых графовых нейронных сетей.
• Анализ атак отравления и уклонения на графовые нейронные сети и исследование методов защиты от них.

ТЕМЫ ПРОШЛЫХ ЛЕТ

10. Исследование и разработка Q-learning алгоритмов для поиска целевых вершин в  социальных графах [Шайхелисламов Д.С. 2020-21-22, 5-6 курс МФТИ]

Из текста диплома Шайхелисламова Д.С.:

«Социальная сеть обеспечивает основу для поддержки социальных отношений, поиска пользователей со схожими интересами, формирования сообществ. В прикладных задачах возникает потребность сбора целевых пользователей, например, лидеров мнений или пользователей, объединенных по интересам. Однако из-за большого объема данных и ограничений на автоматизированный сбор информации поиск таких пользователей в сети отличается от обычной технологии обхода графа. Социальная сеть легко абстрагируется в социальный граф, где вершины — это пользователи, а ребра — социальные взаимоотношения. Серьезной проблемой при поиске целевых вершин в реальных социальных графах является отсутствие знания обо всем графа. В реальных приложениях возникает задача сбора максимального числа целевых вершин при ограничениях на число запросов в неизвестном графе.

…

В работе выдвинута гипотеза о том, что свойство неизвестной вершины можно предсказывать по окрестности. В этой работе изложен подход исследования социального графа с обучением по вознаграждениям. Разработаны три новых алгоритма обхода: FocusedCrawler, DQNCrawler, DDPGCrawler — которые принимают решение на основе Q–функции на каждом шаге алгоритма.»

9. Использование многоруких бандитов для поиска целевых вершин в графе [Лукьянов К.С. 2020-21, 4 курс МФТИ]

Из текста диплома Лукьянова К.С.:

«За последние годы количество социальных сетей, а также их пользователей по­ стоянно увеличивается. С этим повышается и интерес к их изучению. Но на практике нельзя получить доступ к всей сети. Почти вся информация про размер, топологию и узлы исходной сети скрыта либо известна малая часть информации. Для многих целей возникает необходимость найти как можно больше пользователей социальной сети с некоторыми свойствами/интересами.

В работе предполагается, что граф изначально полностью скрыт. Целью работы является разработка эффективного алгоритма сбора вершин с заданными свойства­ми.

Реализованы три различные модификации алгоритма KNN-UCB для задачи сбо­ра хабов, которые показывают стабильно высокие результаты в сравнении с жадны­ми и другими популярными алгоритмами сбора вершин. В работе предложен подход: использование графовых нейросетей для предсказания атрибутов вершин при крау­линге. Разработан метод, который позволяет предсказывать атрибуты вершин при краулинге. Предложены три алгоритма для работы с множествами вершин с задан­ными атрибутами, которые пока не показывают значимо высоких результатов, но имеют потенциал при доработке.»

8. Исследование алгоритма сбора влиятельных вершин в социальных графах [Айвазов Д.А. 2019-20, 4 курс МФТИ]

Из текста диплома Айвазова Д.А.:

«Социальные сети получили очень широкое распространение и объединяют мил­лиарды пользователей. Но с усложнением сети растёт и интерес к её исследованию и разнообразие информации, которую можно из неё извлечь. По сети друзей чело­века можно описать законы поведения и различные социальные явления, изучить влияние лидеров мнений, оценить скорость распространения информации, увидеть динамику изменения и развития дружеских связей и многое другое [1]. Для изуче­ния социальной сети удобно представлять её в виде графа — множества из вершин (аккаунтов пользователей сети) и рёбер, их соединяющих. Рёбра в данном случае отражают связи: дружба, подписка и т.д. Такую модель удобно исследовать, изучая свойства отдельных вершин, их распределение и метрики самого графа. Это позволя­ет создавать математическую модель, с похожими свойствами, с помощью которой можно изучать реальный граф и предсказывать его развитие [2]. Самые популярные социальные сети: Facebook, Instagram, Twitter и другие до­стигают размеров в миллионы, и даже миллиарды аккаунтов, и их скачивание и полный анализ довольно трудоёмкий процесс. Но кроме размера социальной сети на пути исследователей встаёт ещё одна проблема: искусственное ограничение на число запросов к серверам через API — Application Programming Interface, которое устанав­ливает каждая социальная сеть на своё усмотрение, чтобы не нагружать хранилища и не дать собрать всё целиком [3]. В сборе социальных сетей (social network crawling) вычислительная сложность алгоритмов не является ограничением и главной пробле­мой остаётся число запросов к серверу. С помощью специальных сборщиков данных — краулеров (crawler), становится возможно за ограниченный бюджет запросов собрать выборку меньшего размера и исследовать уже её, потому что из всего графа прежде всего интересны вершины с наилучшими показателями каких-то метрик центральности — влиятельные пользова­тели [4]. Они влияют на скорость распространения информации, на других пользо­вателей, соединяют слабо связанные части графа и т.д. Целью данной дипломной работы является сравнение алгоритмов краулинга вер­шин с наибольшими значениями важных мер центральности в социальных графах. В процессе работы была написана и опубликована статья [5] со сравнением основных решений в этой области, а данная дипломная работа является её расширением.»

Литература:

1. Catanese S. A., De Meo P., Ferrara E. et al. Crawling facebook for social network analysis purposes // Proceedings of the international conference on web intelligence, mining and semantics. 2011. P. 1-8.
2. Newman M. E. The structure and function of complex networks // SIAM review. 2003. Vol. 45, no. 2. P. 167-256.
3. Ye S., Lang J., Wu F. Crawling online social graphs // 2010 12th International Asia­-Pacific Web Conference / IEEE. 2010. P. 236-242.
4. Freeman L. C. Centrality in social networks conceptual clarification // Social net­works. 1978. Vol. 1, no. 3. P. 215-239.
5. Drobyshevskiy M., Aivazov D., Turdakov D. et al. Collecting Inѕuencers: A Compar­ative Study of Online Network Crawlers // 2019 Ivannikov Ispras Open Conference(ISPRAS) / IEEE. 2019. P. 42-48

7. Разработка эффективного алгоритма поиска влиятельных пользователей в социальном графе [Шайхелисламов Д.С. 2019-20, 4 курс МФТИ]

Из текста диплома Шайхелисламова Д.С.:

«Стремительный рост популярности социальных сетей, таких как Twitter, Facebook, привлекает внимание исследователей из самых разных областей. Благодаря изуче­нию этих сетей становится возможным получить глубокое представление о челове­ческом поведении в масштабах общества, например, понять, как формируются соци­альные группы, распространяется информация или болезнь, возникают или исчезают дружеские связи.
В любом анализе сети, как правило, доминируют постоянные пользователи, т.к. остальные не отличаются высокой активностью или высоким уровнем связности совсей сетью – имеют мало подписчиков или «твитят» всего несколько раз в месяц. Следовательно, для проведения анализа нет необходимости в сборе всего графа, до­статочно лишь его репрезентативной выборки [1].
Известно, что, по сравнению с обычными пользователями, пользователи влия­тельные [2] в социальных графах играют более важную роль с точки зрения связ­ности, влияния и распространения информации. В связи с этим анализ структуры связности и информационного обмена внутри только лишь «влиятельной» части се­ти, содержащей всех влиятельных пользователей и их попарные отношения, обеща­ет ряд интересных возможностей. Во-первых, такие пользователи обычно являются широко известными личностями (знаменитости, политики) или представляют собой целые организации (информационные агентства, технологические компании) с опре­деленными социальными, культурными или географическими атрибутами, которые могут быть использованы для анализа шаблонов отношений между элитными пользо­вателями. Во-вторых, поскольку влиятельные пользователи в совокупности, как пра­вило, связаны со значительным числом постоянных пользователей социальной сети, анализ таких взаимоотношений может дать ценную информацию об общей структуре всей сети.
Основываясь на этих наблюдениях, репрезентативную выборку можно сформи­ровать из множества влиятельных узлов. Влиятельность узла может быть опреде­лена как мера его центральности в графе. В данной работе влиятельными будем считать узлы с большой степенью. Можно предположить, что люди с большим чис­лом подписчиков или друзей в социальной сети – это лидеры мнений.
Стоит отметить, что сбор данных может быть сложной задачей, поскольку неко­торые сети, особенно социальные, скрыты в целях сохранения конфиденциальной информации. Впрочем, они предоставляют удобный и доступный канал сбора – API. Стоит также учитывать, что при обработке запросов по API пользователь может столкнуться с такими проблемами, как ограниченность по времени или по количе­ству запросов; потребность в огромном количестве ресурсов для хранения и анализа больших реальных графов.
Предполагается, что сети имеют ограниченный доступ к сетевым данным, од­нако поддерживают алгоритмы обхода. В начале обхода возможен доступ к произ­вольному узлу или конечному множеству узлов в сети. Алгоритм посещает вершину, выполняя запрос по API или веб-скрапинг. Для простоты положим, что каждый узел имеет унитарную стоимость, т.е. один шаг работы алгоритма равен одному запросу. В свою очередь на запрос возвращается полный список соседей вершины. По мере продвижения по графу, наблюдаемая часть сети расширяется, а видимые вершины могут быть сгруппированы на две категории (рис. 1): посещенные (скрауленные) и наблюдаемые. Хороший алгоритм сбора, (далее – краулер), должен максимизировать долю влиятельных узлов среди всех собранных при ограниченном числе запросов.»

Литература:

1. Ahmed N. K., Neville J., Kompella R. Network sampling: From static to streaming graphs // ACM Transactions on Knowledge Discovery from Data (TKDD). 2013.Vol. 8, no.
   2. P. 1–56.
2. Al-Garadi M. A., Varathan K. D., Ravana S. D. et al. Analysis of online social network connections for identification of influential users: Survey and open research issues // ACM Computing Surveys (CSUR). 2018. Vol. 51, no. 1. P. 1–37.

6. Оптимизация процесса генерации ребер графа в модели ERGG (Embedding-based Random Graph Generator) [Портной А.М. 2019-20, 6 курс ВМК МГУ]

Аннотация: «В данной работе исследуется генератор графов, похожих на данный, ERGG (Embedding-based Random Graph Generator) и предлагается модификация процесса генерации ребер в данном генераторе для более быстрой его работы. Проводится экспериментальное сравнение предложенной модификации на графах различного размера из различных доменов. Предложенная модификация позволяет существенно сократить время генерации ребер в генераторе ERGG.»

5. Исследование свойств динамических графов [Портной А.М. 2018-19, 5 курс ВМК МГУ]

Некоторые графы реального мира со временем увеличиваются в размерах (социальные сети, графы цитирований и т.п.), при этом динамика изменения их характеристик мало изучена. Известно, например, что кол-во ребер от кол-ва вершин зависит по степенному закону [1], а начиная с какого-то момента роста графа (gelling point), его диаметр начинает уменьшаться [2]. На практике возникают вопросы прогнозирования будущей структуры графа, например: насколько хорошо будет работать Интернет-протокол через пять лет? какие свойства будет иметь граф Facebook когда кол-во пользователей вырастет?

Выяснив динамику различных метрик в реальных данных, нужно проверить существующие модели случайных графов на способность воспроизведения такого поведения в сгенерированных графах. Например, распределение подграфов размера 3 позволяет классифицировать графы по доменам [3,4], и есть предположение, что этот признак меняется слабо с ростом графа. Интересно разработать модель, автоматически выявляющую закономерности по серии снэпшотов графа увеличивающегося размера, и способную таким образом предсказать будущее состояние данного графа.

Задачи:

• экспериментально исследовать динамику различных метрик в растущих графах из разных доменов
• проверить гипотезу о сохранении распределение подграфов размера 3 с ростом графа
• протестировать существующие модели динамических графов на предмет воспроизведения метрик
• (дополнительно) разработать модель, способную обучаться на серии снэпшотов графа разного размера

Литература:

1. J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graph evolution: Densification and shrinking diameters,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 1, no. 1, p. 2, 2007.
2. M. McGlohon, L. Akoglu, and C. Faloutsos, “Weighted graphs and disconnected components: patterns and a generator,” in Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008, pp. 524–532.
3. Comparing predictive powers of Network Motif Distribution and structure of Overlapping Communities
4. Mining Large Networks with Subgraph Counting (section 4.2)

4. Вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами [Зимнюков М. 2018-19]

Один из способов оценить качество работы метода поиска сообществ в графе, не имея правильного ответа (ground truth) — измерение модулярности [1]. Основная проблема в том, что существующие алогритмы имеют сложность квадратичную и более от размера графа, что делает их почти неприменимыми для графов с более 100К вершин. Специфику задаче придают следующие аспекты: направленные ребра, веса на ребрах, пересекающиеся сообщества. Формула для модулярности, учитывающая все три аспекта, была предложена в [2]. Предлагается расширение работы [2], а именно:

• реализовать быструю версию алгоритма расчета модулярности (например на C++)
• провести больше экспериментов на графах из различных доменов
• (дополнительно) адаптировать алгоритм поиска сообществ как оптимизацию модулярности, подобно [3]
• (дополнительно) опубликовать статью по результатам

Литература:

1. https://en.wikipedia.org/wiki/Modularity_(networks)
2. Параллельное вычисление модулярности для направленных взвешенных графов с пересекающимися сообществами
3. Fast unfolding of communities in large networks

3. Сравнение методов генерации графов, похожих на данный [Бардуков А. 2018-19, 5 курс ВШЭ]

Задача сгенерировать граф, похожий на данный, возникает, например, когда необходимо опубликовать граф, не раскрывая конфиденциальную информацию. Например, для анализа социальной сети Вконтакте исследователям нужна структура всего графа, однако связи между конкретными пользователями не должны быть раскрыты. Наивный метод анонимизации путем замены id всех пользователей на случайные не гарантирует защиты [1]. Существуют различные виды атак, использующие встраивание искусственных узлов-пользователей в граф с заранее известной конфигурацией связей для «узнавания» ее после анонимизации и прочие [2]. Поэтому цель — генерация графа, похожего на данный в смысле графовых метрик, но при этом достаточно отличающийся от него, чтобы скрыть конфиденциальную информацию (обзор методов в [3]).

Другая область применения — создание искусственных датасетов для тестирования алгоритмов на графах. Часто в наличии есть граф в одном экземпляре или только его часть (сэмпл сети Вконтакте), а работу нового алгоритма (например, приближенный подсчет диаметра) необходимо проверить на разных графах. Для этого генерируется выборка похожих случайных графов с некоторым разбросом в основных характеристиках и на ней тестируется статистическая значимость результатов вычисления, времени работы алгоритма, его масштабируемости и т.д. См. Обучение и масштабирование сетей на основе вложения графа.

Отталкиваясь от результатов статьи Reproducing Network Structure: A Comparative Study of Random Graph Generators, предлагается исследовать существующие модели-генераторы случайных графов в контескте описанных приложений.

Литература:

1. L. Backstrom, C. Dwork, and J. Kleinberg, “Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography,” in Proceedings of the 16th international conference on World Wide Web. ACM, 2007, pp. 181–190.
2. A. Narayanan and V. Shmatikov, “De-anonymizing social networks,” in Security and Privacy, 2009 30th IEEE Symposium on. IEEE, 2009, pp. 173–187.
3. S. Ji, W. Li, P. Mittal, X. Hu, and R. A. Beyah, “Secgraph: A uniform and open-source evaluation system for graph data anonymization and de-anonymization.” in USENIX Security Symposium, 2015, pp. 303–318.

2. Исследование и разработка методов вычисления распределения подграфов в графе — Methods for Subgraph Distribution Computing in a Graph [Портной А.М. 2017-18, 4 курс ВМК МГУ]

Традиционно для описания свойств таких графов используют множество статистик: распределение степеней вершин, коэффициент кластеризации, собственные значения матрицы смежности и многие другие. Одной из интересных характеристик графа является распределение подграфов малого размера. Например, распределение подграфов размера 3 и 4 в графе [1] позволяет классифицировать графы из различных доменов (социальные сети, биоинформатика, графы цитирования и т.д.) с большей точностью, чем это позволяют сделать другие признаки [2,3]. Вычисление распределения подграфов в ориентированном графе довольно сложно даже для подграфов размера 3. Для этого было разработано несколько инструментов, в том числе использующих приближенные алгоритмы.

В работе предлагается:

• провести обзор существующих инструментов
• выяснить, необходимо ли разработать новый (распределенный, более точный/быстрый и т.п.) алгоритм подсчета подграфов
• реализовать придуманный алгоритм

Быстрые алгоритмы:

• gtrie (the fastest, but consumes a lot of memory)
• Arabesque (needs hadoop, undirected graphs only).

Приближенные алгоритмы:

• mfinder (very slow, dislike duplicate edges and loops)
• FANMOD (only GUI, slow)
• FaSE analogue to gtrie (fast, but fails on > 1M graphs)
• FASCIA very cool but undirected only

Другие инструменты:

• Motif-Discovery plugin for cytoscape (not for command line; can draw interactive pictures)
• snap (2 orders slower than gtrie, but memory-saving; only 3 and 4 subgraphs)

Литература:

1. Random Graphs with Motifs
2. Comparing predictive powers of Network Motif Distribution and structure of Overlapping Communities
3. Mining Large Networks with Subgraph Counting (section 4.2)
4. Learning multifractal structure in large networks (section 6.2)
5. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs

Результат: диплом

1. Использование распределения подграфов в графе для определения демографических атрибутов пользователей сети Интернет [Ефремова М.А. 2017-18, 4 курс МФТИ]

Среди предложенных тем для студентов есть задача Определения демографических атрибутов пользователей сети Интернет по текстам их сообщений [1]. В качестве признаков для предсказания используются тексты публичных сообщений пользователей и другие открытые данные. Предлагается рассмотреть как новый признак распределение подграфов размера 3 в графовой окрестности пользователя в социальном графе: т.е. графе, состоящем из его друзей (1-я окрестность) или друзей всех друзей (2-я окрестность).

Задачи:

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

Литература:

1. см. страницу Гомзина Андрея

Результат: диплом