Интерактивное обнаружение аномалий в атрибутированных сетях

Обнаружение аномалий в атрибутированных сетях направлено на выявление узлов, модели или поведение которых существенно отклоняются от большинства эталонных узлов. Успешное применение этого подхода продемонстрировано во многих реальных задачах, включая обнаружение вторжений в сети, выявление спама в сообщениях, выражающих мнение, и диагностику отказов систем. Несмотря на эмпирическую эффективность существующих методов, подавляющее большинство исследований проводится в безучительном режиме из-за высокой стоимости разметки истинных аномалий. В действительности во многих сценариях небольшие объемы предварительных знаний эксперта о данных можно получить без значительных затрат, а их включение в процесс обучения оказывается эффективным для решения многих важных задач машинного обучения. Кроме того, поскольку новые типы аномалий, особенно в условиях противодействия, могут постоянно возникать с течением времени, интересы эксперта относительно обнаруживаемых типов аномалий также могут соответственно изменяться. Это создает дополнительные трудности для традиционных алгоритмов обнаружения аномалий, которые часто применяются в пакетном режиме и не способны взаимодействовать с окружающей средой. Для решения этих проблем в статье исследуется обнаружение аномалий в атрибутированных сетях в интерактивном режиме, при котором система может проактивно взаимодействовать с экспертом, выполняя ограниченное число запросов о наличии истинных аномалий. Цель состоит в том, чтобы после исчерпания заданного бюджета запросов предъявить эксперту максимально возможное число истинных аномалий. В рамках этого подхода задача формулируется в соответствии с принципиальной структурой многорукого бандита, а также разрабатывается новый алгоритм контекстного бандита с совместным обучением под названием GraphUCB. В частности, разработанный алгоритм (1) явно и согласованно моделирует атрибуты узлов и зависимости между узлами в единой структуре и (2) разрешает дилемму исследования и эксплуатации при запросе аномалий различных типов. Обширные эксперименты на реальных наборах данных показывают, что ...