Использование методов анализа графов для поиска аномалий

Несмотря на то, что описание данных с помощью графов практикуется еще с позапрошлого столетия, использование их в решении повседневных задач по анализу данных лишь набирает обороты. Хотя основное внимание уделяется, как водится, графовым эмбеддингам и сверточным сетям, маленькие шаги предпринимаются и в алгоритмах по поиску аномалий или антифроде. Основная обзорная статья, на которую ссылается большинство специалистов в своих в докладах и публикациях, — Graph based anomaly detection and description: a survey от авторов Leman Akoglu, Hanghang Tong, Danai Koutra (Akoglu, 2015). Мы в CleverDATA решили рассказать Хабру об этом практически единственном материале по теме и предлагаем вашему вниманию его саммари.

Первый граф Российского царства Борис Петрович Шереметев. Аномалий не обнаружено.

Во вступлении авторы отвечают на вопрос: «В чем же преимущества поиска аномалий с использованием теории графов?»:

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

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

Таким образом, перспективность использования теории графов для поиска аномалий обоснована. Перейдем к описанию самих методов.

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

Поиск аномалий в графах без свойств, приписанных вершинам и/или ребрам

Для простых графов выделяют три направления структурных подходов: поиск аномалий на основе признаков узлов, диад узлов, триад, эгонетов (egonet), на основе сообществ и на основе метрик близости (proximity): pagerank, personalized pagerank, simrank. При этом предлагается для решения задачи поиска аномалий на графе использовать обычные алгоритмы (например, Isolation Forest, или если есть разметка, то стандартные классификаторы), но на основе графовых признаков.

Пример Эгонета

Отдельно описывается подход с признаками эгонетов — подграфов, включающих целевой узел, и его ближайших соседей. Авторы, ссылаясь на статью 2010 года (Akoglu, 2010) (в статье будет очень много таких ссылок, гиперссылки на некоторые я дал в тексте, но более подробные ссылки, например, с указанием страниц, вы найдёте в списке литературы в конце этой статьи), предлагают искать характерные для графа паттерны эгонетов с выраженной зависимостью между характеристиками, а эгонеты, не соответствующие этим паттернам, считать аномальными, и, таким образом, считать аномальными их центральные узлы. Поскольку всевозможных показателей на основе эгонетов может быть много, авторы в этой же статье обосновывают свой выбор подгруппы таких показателей, наилучшим образом отражающие свойства графа (например, число треугольников, общий вес ребер). Расстояние между паттернами и между эгонетом и паттерном предлагается измерять, как отклонение характеристики этого эгонета от характерной зависимости, соответствующей паттерну. 

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

Также авторы описывают и другие подходы:

• кластеризация узлов на основании сходства их ближайшего окружения; предлагается реорганизация матрицы смежности для получения более плотных и менее плотных блоков (Chakrabarti 2004; Rissanen, 1999); 
• матричная факторизация; предлагается аналог Non-negative matrix factorization (NMF) (Tong and Lin 2011).

Поиск аномалий в графах с узлами и/или ребрами, обладающими свойствами

Основная идея таких подходов заключается в последовательном решении  двух задач: поиск аномальных подграфов с точки зрения структуры и поиск в рамках этого подмножества аномальных подграфов с точки зрения свойств узлов и/или ребер. Решение этой задачи авторы рассматривают как поиск редких элементов в множестве, сводя ее таким образом к задаче обратной по отношению к поиску элементов, которые чаще всего встречаются в графе, и, таким образом, являются для него наиболее характерными (лучше всего «сжимают» граф). 

Также рассматривается проблема наличия у узлов множества характеристик  различных модальностей. Предлагается всем условно нормальным значениям ставить в соответствие единственное значение категориальной переменной, а для выбросов ставить в соответствие значение единственного показателя аномальности, например, на основании метрических методов обнаружения аномалий: kNN, LOF.

Также перечисляются и другие возможности:  SAX (Symbolic Aggregate approXimation) (Lin et al., 2003), MDL-binning (Minimum description length) (Kontkanen and Myllymki, 2007) и дискретизация по минимуму энтропии (Fayyad and Irani, 1993). Авторы этой статьи (Eberlie and Holder, 2007) иначе подходят к определению аномалии в графовых данных, считая аномальными те подграфы, которые похожи по отношению к условно нормальному графу в определенных пределах. Такой подход авторы обосновывают тем, что самые успешные мошенники будут стараться максимально подражать реальности. Они также предлагают учитывать стоимость модификации показателя и формулируют показатели аномальности с учетом этой стоимости (чем меньше стоимость, тем более аномальным является показатель).

Поиск аномалий для графов с атрибутированными узлами рассматривается и в основанный на поиске сообществ парадигме. Предлагается подразделять графы на сообщества. Далее, в рамках каждого сообщества, искать аномалии по атрибутам. Например, курильщик в команде по бейcболу. Курильщик не является аномалией для общества в целом, но в своем сообществе является. Другой подход (Müller, 2013) основывается на выборе пользователем (аналитиком) набора узлов, для которых далее определяется подпространство показателей, схожих для них. А аномалиями в таком подходе являются узлы, которые структурно принадлежат к кластеру этих узлов, но в выбранном подпространстве показателей находятся далеко от них. 

Отдельно рассматриваются методы semi-supervised, в предположении, что какая-то часть узлов размечена как нормальные и аномальные, а остальные узлы можно классифицировать, используя соответствующие методики, а в самом простом случае им можно присваивать метки соседних с ними узлов. Перечисляются основные подходы: iterative classification algorithm, gibbs sampling (подробнее про эти подходы пишут здесь), loopy belief propagation, weighted-vote relational network classifier. 

Поиск аномалий в динамическом графе

Для динамического графа, который представляет собой упорядоченную во времени последовательность статических графов, основной подход осуществляется следующим образом: 

1. выделяется некоторое сжатие или интегральная характеристика каждого статического графа;
2. вычисляется расстояние последовательно идущих графов;
3. аномальными принимаются те графы, для которых расстояние выше порога.

В качестве мер расстояния предлагаются:

• maximum common subgraph (MCS) distance;
• error correcting graph matching distance, то есть расстояние, измеряющее, сколько шагов нужно сделать, чтобы из одного графа сделать другой;
• graph edit distance (GED), то же, что и предыдущее, но возможны лишь топологические изменения;
• расстояния между матрицами смежности (например, Хэмминга);
• различные расстояния на основе весов ребер;
• расстояния между спектральным представлением графов (распределениями собственных векторов);
• описывается также и более экзотическая мера: эвклидово расстояние между перроновскими собственными векторами графа. 

В статье от Bunke et al. (2006) авторы предлагают считать расстояние не только между последовательно идущими графами, но вообще между всеми графами в последовательности, и потом применять многомерное шкалирование, переводя графы в двумерное пространство. Далее выбросы ищутся в этом двумерном пространстве. 

Описан также следующий способ работы с динамическими графами (Box and Jenkins, 1990): графу ставится в соответствие некое число (расчетный показатель) и далее применяются стандартные методы поиска аномалий во временных рядах. Например, расхождения с моделью ARIMA. 

В статье Akoglu and Faloutsos (2010) авторы осуществляют следующую последовательность операций: 

1. выделяют для каждого узла графа для каждого момента времени F-признаков;
2. для каждого признака с временным окном W считают корреляционные матрицы между узлами;
3. выделяют собственные векторы и далее рассматривают лишь первый собственный вектор;
4. параллельно выделяют «типичное» поведение собственных векторов корреляционной матрицы (для этого делается еще одно SVD-разложение над матрицей изменения всех собственных векторов корреляционной матрицы во времени);
5. сравнивают (через косинусное произведение) с реальным поведением этого вектора, получая таким образом показатель аномальности рассматриваемого временного окна.

Матричное разложение используется также и в статье Rossi (2013): 

1. аналогично предыдущему подходу выделяется по F-признаков на узел на каждый временной промежуток; 
2. для каждого временного промежутка производится NMF-разложение, при котором каждому узлу ставится в соответствие роль;
3. далее мониторится изменение ролей каждого узла.

Матричное разложение для интерпретации результатов

Отдельно хочется отметить приведенные авторами методы аппроксимации матриц — альтернативные по отношению к давно известным SVD, PCA, NMF: CUR (Drineas et al., 2006), CMD (Sun et al. 2007b) и Colibri (Tong et al. 2008). Основным преимуществом этих методов является интерпретируемость, поскольку в отличии от SVD, переводящего точки в другое пространство, эти методы оставляют пространство нетронутым, лишь сэмплируя точки из него. Наиболее простым из них является CUR, у которого авторы отмечают два недостатка: в нем точки выбираются из матрицы с повторением. В CMD удается убрать этот недостаток, однако как и в CUR, этому методу присуща линейная избыточность, которую удается избежать авторам алгоритма Colibri. Хотя методы были изобретены именно для решения задач поиска аномалий в графах методами матричной аппроксимации, их использование может быть перспективным и для других задач.

В задачах, обсуждаемых в этом обзоре, эти подходы применяются по следующему принципу: производится аппроксимация и оценивается, насколько различные столбцы/строки отличаются у аппроксимированной матрицы от изначальной.  Также авторы отмечают метод NrMF (Tong and Lin 2011), модификация NMF, в котором ограничение на неотрицательность накладывается на матрицу остатков R, поскольку именно в ней сосредоточена основная информация по отличию апроксимации от изначальной матрицы, а отрицательные значения в таком случае было бы сложно интерпретировать. Тем не менее, до конца не ясно, почему нельзя аналогичным образом использовать SVD для декомпозиции, последующей реконструкции и последующим расчетом отличия от изначальной матрицы.

Определение узлов, связывающих аномальные

При анализе результатов может возникнуть задача определить узлы, связанные с аномальными. Так, например, как аномальный может быть определен узел, который подвергся  DDoS-атаке, в то время как атакующие узлы не определены. Или как аномальные могут быть определены члены какой-то группировки, в то время как люди, руководящие ими, не определены как аномальные. Для решения этой задачи авторы предлагают несколько подходов, основной идеей которых является выделение подграфа из полного графа, который содержит аномальные узлы и узлы, лучше всего их связывающие.

1. Определение связного подграфа (connection subgraph)  (Faloutsos et al., 2004). Проблему предлагается решать в терминах электротехники, присваивая одному узлу положительный потенциал, а другим узлам — нулевой, и смотреть, как будет «течь ток» между ними, если присвоить ребрам некое сопротивление.
2. Center-Piece Subgraphs (CePS) (Tong and Faloutsos, 2006). В отличие от предыдущего метода предпринимается попытка выделить лишь k-узлов из всех аномальных, поскольку совершенно не обязательно все узлы заданы. При этом k необходимо задавать.
3. Dot2Dot (Akoglu et al., 2013b; Chau et al., 2012). В этом подходе авторы решают задачу группировки выбранных узлов и уже далее выделяют узлы, их связывающие.

Примеры поиска аномалий в различных сферах

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

Телекоммуникации. Целью являются люди, пользующиеся услугами бесплатно. Cortes et al. (2002) искали подграфы, тесно связанные с ключевым узлом по параметрам числа и продолжительности звонков. Наблюдения, которые авторы обнаружили: фродовые аккаунты оказались связаны, то есть нарушители или сами звонили друг другу, или звонили на одни и те же телефоны. Второе наблюдение — нарушителей можно обнаружить по схожести их подграфов, определенных предложенным образом.

Онлайн-аукцион. Нарушители создают себе фейковые аккаунты и накручивают им рейтинги. Их не получается отследить по обычным агрегатным показателям, но возможно увидеть по  графу. Аккаунты нарушителей более связаны с фейковыми аккаунтами, чем с хорошими аккаунтами. Фейки связаны примерно в равной степени с аккаунтами нарушителей и с хорошими. Последние в основном связаны с подобными себе аккаунтами. Pandit et al. (2007) решают эту задачу через приведение к реляционным марковским сетям (relational markov networks) и далее классифицируют узлы через Loopy Belief Propagation (метки класса итеративно распространяются по графу).

Транзакции. McGlohon et al. (2009) решают эту задачу через реляционную (relational) классификацию в предположении, что нарушители будут близко расположены друг к другу. То есть аналогично подходу из предыдущего примера.

Брокеры, которые жульничают с ценными бумагами. Здесь Neville et al. (2005) анализируют мультимодальный граф, выделяя подграфы, включающие человека под подозрением, его коллег, фирмы, с которыми он связан и т. п. Они рассчитывают агрегированные атрибуты и приписывают их центральному узлу. Далее используют реляционные вероятностные деревья (relational probability trees (Neville et al. 2003)) для реляционной классификации.

Поиск фейковых постов на форумах, дающих заведомо ложную информацию. Авторы описывают несколько подходов, с использованием признакового описания, анализа текста и графовых методов. Графовые методы, использованные Wang et al. (2011a), применялись для ситуации, когда в задаче присутствуют обзоры какого-то товара. В предложенном ими алгоритме предлагалось присваивать рецензентам показатели «степени доверия им», их обзорам «достоверности» и товарам — показатели «надежности». Все эти показатели взаимосвязаны. Так, насколько можно доверять рецензенту, зависит от того, насколько у него достоверные обзоры.  Надежность товаров зависит от степени доверия рецензентам, которые его описывают, а достоверность обзоров зависит от надежности товара, по которым они пишутся, и от доверия их авторам. Предлагаемый алгоритм сначала их случайно инициализирует, а затем итеративно улучшает оценку.

Трейдинг. Мошенники сначала совершают большое число транзакций друг с другом по какому-то типу акций, увеличивая их привлекательность, а затем, когда акции повышаются в цене, распродают их другим трейдерам. Оба этих последовательных инцидента можно отследить по графовым данным. В первом случае будет выделяться подграф, где нет никаких внешних транзакций (именуется «черная дыра»), а через временной промежуток этот же подграф преобразуется к подграфу, в котором сильно преобладают транзакции из подграфа в другую часть графа (именуется «вулкан»). Авторы ссылаются на работу Li et al. (2010).

Веб-ресурсы. Одним из первых подходов для борьбы с «плохими» веб-сайтами предлагалось распространение показателей «надежности» и «ненадежности» ресурсов. Если есть ссылка с одной страницы на другую, то для последней это увеличивает ее статус надежной. Если страница указывает на другую страницу, для которой известно, что она спам, то это снижает надежность изначальной страницы. Упоминается алгоритм TrustRank (Gyöngyi et al., 2004) — модификация PageRank для борьбы с веб-спамом. Для него требуется, чтобы изначально эксперты разметили часть сайтов, как надежные. Эти показатели далее распространяются по графу, постепенно затухая. Anti-TrustRank (Krishnan and Raj, 2006) следует этому же принципу, но с распространением показателей ненадежности от размеченных заведомо ненадежных сайтов. У обоих методов есть недостаток, что надежность делится по числу дочерних узлов. Benczúr et al. (2005) предлагают совершенно иной подход: анализировать PageRank узла и соседних с ним. Распределение PageRank таких подграфов должно подчиняться некому степенному закону. Для тех же узлов, для которых распределение PageRank их соседей выбивается из этого закона, присваивается штраф. В работе (Castillo et al., 2007) предлагается сначала обучать классификатор на известных надежных и ненадежных страницах, а затем «размывать» результат скоринга остальных веб-сайтов по графу.

Социальные сети. Для обнаружения постов мошенников в социальных сетях (для увеличения числа лайков, для перенаправления на вредоносную страницу или на анкетирование) описываются подходы на основе обычных классификаторов, но с учетом графовых признаков: длина распространения «плохого» поста по графу, число лайков и комментов других пользователей по посту, схожесть сообщений, распространяющих пост пользователей, степень узла пользователя, написавшего пост.

Атаки в компьютерных сетях. Sun et al. (2008) успешно применяют для решения этой задачи матричное разложение (CMD).  Ding et al. (2012) используют подход основанный на поиске сообществ, выделяя в качестве подозрительных узлы-мосты между сообществами.

Заключение

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

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

Если вас интересует тема, то, чтобы получить больше информации, обязательно нужно идти в слак ODS (OpenDataScience), в каналы #network_analysis и #class_cs224w, смотреть курс Стэнфорда cs224w.

Еще недавно был прочитан курс по Knowledge Graphs. Ну и, конечно, нужно прочитать саму статью Graph based anomaly detection and description: a survey от авторов Leman Akoglu, Hanghang Tong, Danai Koutra (Akoglu, 2015), о которой идет речь в этом посте. Я перевел ее не всю, а только те фрагменты, которые счел важными, и понял в какой-то степени. Большинство авторов ссылаются именно на эту статью, потому что больше обзоров такого уровня и широты по теме нет. По крайней мере, я не нашел таких. 


Да, наша команда CleverDATA не только пишет и переводит статьи. Большую часть времени мы посвящаем решению интересных и разнообразных практических задач, для чего используем не только теорию графов, но и множество методов машинного и глубокого обучения.