1. Использование PowerShell для прямого доступа к гранулированной информации о процессах;
2. Построение и визуализация иерархии процессов первый важный шаг в поиске угроз;
3. Использование метаданных Sysmon для формирования важных метрик, полезных при углублённом расследовании угроз, таких как подсчёт частоты, с которой запускаются конкретные процессы.

Использование Get-Sysmonlogs

$events = Get-WinEvent  -LogName "Microsoft-Windows-Sysmon/Operational" | where { $_.id -eq 1 } foreach ($event in $events)  {    $ev = $event.Message -split "`r`n"    $jsons="{ "    foreach ($line in $ev) {        $line=$line -replace "\\","\\" `               -replace "\{"," " `               -replace "\}"," " `               -replace '"','\"' `               -replace "`n"," "         $line=$line -replace '(\s*[\w\s]+):\s*(.*)', '"$1":"$2",'        $jsons = $jsons + $line }         $jsons =$jsons + '"blah" : "blah" }'         ConvertFrom-Json -InputObject $jsons     }}

Азы структур данных: списки и графы

Охота на угрозы с помощью направленных графов

#Let's graph it!!!$gv = New-Graph -Type BiDirectionalGraph # PSQuickGraphforeach ($e in $g.getAllEdges() )  { $g from Doug Fink's functions    $vs= $e.startvertex   $ve= $e.endvertex    PSQuickGraph\Add-Edge -From $vs.value.Key -To $ve.value.Key -Graph $gv |Out-Null}Show-GraphLayout -Graph $gv

О чем эта статья

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

Есть ли смысл в спорах

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

Думаю, что многие это проходили. Когда количество споров на одну и ту же тему с разными людьми переваливает за десяток, спорить становится уже неинтересно. Вы понимаете, что знаете и предсказываете их логические цепочки, аргументы и контраргументы. Конечно, иногда встречаются новые ходы, но все же "основные логические магистрали" остаются приблизительно теми же, и их количество вполне ограничено. И это в принципе можно рассматривать как приобретение. Фактически таким образом разрабатывается некая карта логических связей. Правда, эта карта разбита на многие осколки, которые хранятся лишь в умах большого количества людей, не формализованная, не выраженная, с ложными или тупиковыми тропками

В какой-то момент для некоторых тем мне захотелось запротоколировать и проанализировать эту карту. Работая над этим, я получил то, что я назвал волновым анализом и несколько, на мой взгляд, интересных выводов, которыми и хочу поделиться.

Волновой анализ

Связи между утверждениями

Рассмотрим два утверждения: A и B. Будем считать, что каждое из этих утверждений может быть или истинным или ложным. Тогда возможны следующие зависимости утверждения A от B:

• Независимость (А не зависит от В). Истинность или ложность утверждения A никак не зависит от истинности или ложности утверждения B.

• Прямое опровержение. Если утверждение B истинно, то утверждение A ложно. Будем обозначать такую связь, как A --п-> B. Суть в том, что стрелка --п-> фактически заменяет выражение "ложно потому, что", то есть A --п-> B это краткая запись выражения "A ложно потому, что B (истинно)". На графе эту связь мы будем обозначать сплошной линией со стрелкой от А к B:

  
  
  

  Замечание
  
  При этом, если утверждение B ложно, то это может ничего или почти ничего не значить для А.
  
  Пример
  
  Утверждение А: "Вчера в 7 часов вечера Алиса была дома".
  Утверждение B: "Вчера в 7 часов вечера Алиса была в театре".
  A --п->B: "Вчера в семь часов вечера Алиса не была дома, потому что она была в театре."

  
  
• Дополнение (логическое отрицание). Если утверждение B истинно, то утверждение A ложно, и если утверждение B ложно, то утверждение A истинно. Будем обозначать это как А <-> B. Легко показать, что если А <-> B, то B <-> A. На графе эту связь мы будем обозначать сплошной линией с двунаправленной стрелкой:
  
  

  Пример
  
  Утверждение А: "Вчера в 7 часов вечера Алиса была дома".
  Утверждение B: "Вчера в 7 часов вечера Алисы НЕ было дома".
  

• Прямое подтверждение. Если утверждение B истинно, то утверждение А тоже истинно. Будем называть это прямым подтверждением. Легко показать, что такая зависимость составляется из предыдущих зависимостей: A<->C--п-> B. В этом случае если B истинно, то C ложно, а значит A истинно. На графе это может быть представлено в виде
  
  

  Пример
  
  Утверждение А: "Вчера в 7 часов вечера Алиса была дома".
  Утверждение B: "Вчера в 7 часов вечера Боб был в гостях у Алисы, и видел её дома".
  A <->C--п->B: "Вчера в семь часов вечера Алиса была дома, потому что Боб в это время был у нее в гостях и видел её там."
  Дословно же эту запись можно представить, как "Вчера в семь часов вечера Алиса не была вне дома, потому что Боб был у нее в гостях и видел её дома".
  

• Косвенное опровержение. Если утверждение B истинно, то вероятность того, что утверждение А ложно увеличивается. Будем называть это косвенным опровержением и обозначать как A --к-> B. На графе будем обозначать это пунктирной линией со стрелкой от A к B:

  
  
  

  Замечание
  
  При этом, если утверждение B ложно, то это может ничего не значить для А.
  Отличие от прямого опровержения в силе связи. Если В истинно, то это еще не значит, что А ложно, но говорит нам о том, что вероятность того, что А ложно увеличивается.
  
  Пример
  
  Утверждение А: Вчера в 7 часов вечера Алиса была дома".
  Утверждение B: "Вчера в 7 вечера к Алисе приходил Боб, звонил в дверь, но никто не открыл".
  A --п->B: "Вчера в семь часов вечера Алисы скорее всего не было дома, потому что в это время приходил Боб и звонил в дверь, но никто не открыл". Но в действительности Алиса могла быть дома, но по каким-либо причинам не могла или не хотела открывать.

  
  
• Косвенное подтверждение. Если утверждение B истинно, то вероятность того, что утверждение А тоже истинно увеличивается. Будем называть это косвенным подтверждением. Легко показать, что такая зависимость составляется из предыдущих зависимостей: A<->C--к-> B. В этом случае, если B истинно, то вероятность того, что C ложно увеличивается, а значит вероятность того, что A истинно тоже увеличивается. Отличие от прямого подтверждения опять-таки в силе связи (как и для косвенного опровержения). На графе это может быть представлено как
  
  

  Пример
  
  Утверждение А: "Вчера в 7 часов вечера Алиса была дома".
  Утверждение B: "Вчера в 7 часов вечера соседи слышали звуки пианино из квартиры Алисы".
  A <-> C --к->B: "Вчера в семь часов вечера Алиса скорее всего была дома, потому что соседи слышали звуки пианино из ее квартиры". Но, в действительности, это ведь могла быть просто запись.
  

Таким образом мы ввели 3 основных вида зависимости утверждения A от утверждения B:

• прямое опровержение
• косвенное опровержение
• дополнение (логическое отрицание)

Все остальные необходимые для анализа комбинации можно получить из этих 3х.

• в случае нескольких опровержений одного утверждения, они объединяются логическим "или". На данном графе показано, что N ложно потому что M1 или M2 или Mk (истинно)

  
  
  

  Замечание
  
  Возможна комбинация прямых и косвенных опровержений.

  
  

• если мы хотим показать аргументы, поддерживающие наше утверждение, то, как уже было замечено выше, это можно сделать через опровержение дополнения. Так, например, если мы имеем утверждение N1 и аргументы M1, M2, .., Mk, где M1 косвенное подтверждение, а M2 и Mk прямые, то это будет выглядеть следующим образом

  
  

Граф, построенный по этим правилам мы будем называть волновым графом.

Волновой граф

Предположим, что происходит обсуждение истинности/ложности утверждения A. Утверждение А должно быть сформулировано таким образом, что возможен один и только один вариант А истинно или А ложно.

Построим волновые логические цепочки в виде графа по следующему принципу:

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

  Замечание
  
  В данной статье мы будем использовать положительные числа, если утверждение является подтверждающим наше корневое утверждение, и отрицательные числа если опровергает, но это, конечно, необязательно (обязательным является однозначность нумерации). При этом номером +0 будет обозначена корневая вершина, а -0 её дополнение. Конечно, это всего лишь обозначение, поэтому тот факт, что +0 = -0 ничему не мешает.
  

• ребра графа отражают перечисленные виды зависимости и, соответственно, у нас всего лишь 3 вида ребер

Волновой логической цепочкой (волной) мы будем называть движение от вершины к вершине по стрелкам ребер. Очевидно, что в такой цепочке мы всегда будем иметь последовательность аргументов за и против, что лично мне напоминает волну. Приблизительно это мы наблюдаем и в "правильном" споре (что, к сожалению, бывает далеко не всегда).

Пример волнового графа. Отелло

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

• корнем этого графа является утверждение "Дездемона изменила Отелло"
• далее вниз мы можем наблюдать волновые логические цепочки (волны). Цвет ближе к голубому (мы будем называть его голубым) является подтверждением того, что "Дездемона НЕ изменяла Отелло", а цвет ближе к желтому (мы будем называть его желтым), является подтверждением противоположного, а именно, что "Дездемона изменила Отелло". Мы видим чередование голубых и желтых вершин
• мы знаем, что истинными являются все голубые утверждения, Отелло же на момент убийства был уверен в том, что истинными являются все "желтые утверждения"
• рассмотрим примеры всех возможных зависимостей:
  
  • прямое опровержение
    +0 --п-> -2: утверждение, что "Дездемона изменила Отелло" ложно потому, что "Дездемона говорит, что она не изменяла". Если то, что говорит Дездемона правда, то, конечно же, это прямое опровержение того, что Дездемона изменила
  • косвенное опровержение
    +0 --к-> -3: утверждение, что "Дездемона изменяла Отелло" ложно потому, что "Дездемона любит Отелло". Действительно, если она действительно любит Отелло, то это еще не значит, что она ему не изменяла, но этот факт увеличивает вероятность того, что Дездемона верна Отелло
  • дополнение
    +0 <-> -0: "Дездемона изменила Отелло" и "Дездемона не изменяла Отелло".
  • прямое подтверждение
    +0 <-> -0 --п-> +3: "Дездемона изменила Отелло" потому, что "Кассио сам рассказал об этом". Очевидно, что, если Кассио рассказал правду, то это прямое подтверждение
  • косвенное подтверждение.
    +0 <-> -0 --к-> +5: "Дездемона изменила Отелло" потому, что "Кассио говорил о связи с Дездемоной во сне". Понятно, что даже если это и правда, и Кассио говорил об этом во сне, то это еще не значит, что Дездемона изменила. Однако, это все же увеличивает вероятность этого
• мы можем рассмотреть отдельные волновые логические цепочки (волны). Для этого нужно просто следовать стрелкам. Помним, что каждая однонаправленная стрелка от вершины N к вершине M значит, что "N ложно потому, что M (истинно)". Так же у нас может быть конструкция с подтверждением (описана выше). Например, рассмотрим логическую цепочку +0 <->-0 п-> +3 п-> -6 п-> +13 п-> -14 к-> +20 п-> -15 <-> + 21 --к-> -19 <->+25:
  
  • +0 <->-0 п-> +3: Дездемона изменила Отелло, и доказательством является то, что Отелло слышал разговор Кассио с Яго, где Кассио говорил о связи с Дездемоной
  • +3 п-> -6: но это не так, потому что Отелло слышал только часть разговора и неправильно интерпретировал его
  • -6 п-> +13: интерпретация верна, Яго подтвердил верность интерпретации
  • +13 п-> -14: Яго лжёт
  • -14 к-> +20: У Яго нет мотива обманывать Отелло
  • +20 п-> -15: Нет, у Яго есть мотив. Он обижен на то, что Отелло назначил не его заместителем, а Кассио
  • -15 <-> + 21 --к->-19: Яго обижен на Отелло и держит на него зло потому, что он злой и порочный человек
  • -19 <->+25: Это не так, потому что Яго хороший и честный человек
    Зачем мы закончили --19 <-> + 25? Потому, что мы не можем точно знать (Отелло не может), каким человеком является Яго, злым или хорошим. У нас нет аргументов. Такая же ситуация бывает и в споре, когда оппоненты просто упираются в "да нет" без какой-либо аргументации. Это и есть одна из опорных точек.
    

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

Анализ волнового графа

Сходимость графа

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

Будем называть вершину N тупиковой, если из нее не выходит ни одной стрелки, в том числе и двунаправленной (дополнение), то есть она не опровергается ни одним утверждением (в идеале ни прямым, ни косвенным, но существенными для анализа являются только прямые опровержения).

Тогда утверждение M, для которого M --п-> N будем называть утверждением, опровергнутым N.

Ниже приведен алгоритм разрешения волнового графа.

• найдем (если есть) тупиковую вершину N
• найдем все утверждения, опровергнутые N. Пометим эти вершины и тупиковую вершину N как "удаленные". Все стрелки, ведущие к ним и от них, также пометим как "удаленные". Мы не учитываем их в дальнейшем анализе
• все вершины, которые не входят в волновые логические цепочки с началом в корне (потеряна логическая связь с корневым утверждением) помечаем как "удаленные". Все стрелки, ведущие к ним и от них, также пометим как "удаленные". Мы не учитываем их в дальнейшем анализе.
• если для двух вершин N и M таких что N<->M вершина M помечена как удаленная, то вершина N становится тупиковой (доказанной), и все стрелки ведущие из нее (все опровержения) помечаются как удаленные
• повторяем этот процесс до тех пор, пока не кончатся тупиковые вершины
• когда тупиковые вершины закончатся у нас возможны 3 варианта:
  
  • корневое утверждение будет помечено как "удаленное". Тогда данный граф считается решенным. Наше корневое утверждение оказалось ложным
  • осталось только корневое утверждение. В этом случает данный граф считается решенным. Наше корневое утверждение оказалось истинным
  • все остальные варианты. В этом случае мы можем утверждать, что существует скрытая информация, которая не позволяет нам определить, является утверждение ложным или истинным
    

    Замечание
    
    Теоретически, в зависимости от последовательности взятия тупиковых вершин, мы можем получить разный результат. Это говорит или об ошибке в логике, или о ложной информации, принятой за истину. Если наш алгоритм в зависимости от последовательности действий приводит к разным результатам, то мы должны сначала исправить ложную информацию или ошибку в логике.
    

Вернемся к примеру с Отелло.

Пример сходимости. Дездемона невинна

Итак, Отелло убил Дездемону в полной уверенности в ее порочности. Но сразу после ее смерти его видение ситуации развернулось на противоположное. Что же произошло, и как это объясняет волновой анализ?

Вспомним последний акт. Эмилия, под впечатлением от смерти Дездемоны разоблачает своего мужа Яго, объясняя мавру историю с платком. Таким образом Отелло получил опровержение того, что Яго говорит правду. Отелло верит служанке, и это сразу же приводит к разрешению графа, но уже с противоположным результатом. Давайте посмотрим почему.

Теперь к нашему графу мы можем добавить вершины -20, +24, -21, -17, -18 (здесь представлена только правая часть графа):

При этом -20<->+24 --п->-17 и -20<->+24 --п->-18 мы можем отнести к прямым доказательствам:

• -20<->+24 --п->-17: "Эмилия рассказала правду про платок, что показывает, что Яго лгал", и это правда потому, что "Яго так напуган словами Эмилии, что убивает её"
• -20<->+24 --п->-18: "Эмилия рассказала правду про платок, что показывает, что Яго лгал", и это правда потому, что "Эмилия находится под сильным впечатление от смерти Дездемоны и не способна лгать"

В действительности это не выглядит такими уж сильными аргументами, и "волну" можно продолжить и дальше. Например, возможно, Яго убивает Эмилию не потому, что она говорит правду, а по другой причине, или Эмилия лишь притворяется, что находится под сильным впечатлением. И при холодном анализе все это должно быть учтено. Но в данном случае интересно отношение Отелло, интересно то, как именно он все это воспринимает, а мавр поверил Эмилии.

Проанализируем наш граф теперь.

• вершины -17 и -18 на нашем графе тупиковые. Значит, эти вершины, а также вершины +24 и +25 и все их связи мы помечаем как удаленные. Также мы удаляем вершину -21 вместе со связями, т.к. она потеряла связь с корнем графа
• теперь вершины -19 и -20 становятся тупиковыми. Значит, эти вершины, а также вершины +6, +23 и +20 и все их связи можно удалить. Также удаляем и вершины, не имеющие пути к корню, то есть -16, -15, +21, -8, +15, + 22
• теперь тупиковые вершины -14, -7. Удаляем их и вершины, которые они прямо опровергли: +13, +5

Получаем граф (только правое крыло):

Даже после признания того, что Яго лжец, граф формально не сходится. Действительно, теперь Отелло знает, что Яго лжец, что история с платком была подстроена. Нет никаких доказательств того, что Дездемона изменила (также нет и никаких опровержений). Но Отелло лично слышал то, как Кассио рассказывал про свою связь с Дездемоной. При этом Отелло не знает, говорил ли Кассио правду, а также не знает, правильно ли он интерпретировал диалог, который услышал. Но у Отелло уже произошло "переключение" восприятие, поэтому он считает, что, так как все было подстроено, то и диалог был понят неверно. Поэтому вершина +23 удаляется, и вершина -6 становится тупиковой.

На следующем шаге это приводит к тому, что вершина +3 и с ней вершины -4 и +4 со всеми связями также удаляются, и вершина -0 остается без прямых и косвенных опровержений. Это значит, что все аргументы, как прямые, так и косвенные, подтверждающие, что Дездемона изменила были опровергнуты.

Что мы имеем в данной точке нашего анализа?

• у нас не осталось ни одного аргумента, подтверждающего прямо или косвенно измену
• у нас есть аргументы, опровергающие измену (недоказанные и неопровергнутые)
  Можно ли считать в данной точке граф разрешенным? Пока нет, потому что далее мы должны произвести анализ всех аргументов опровергающих измену, и может получиться следующая ситуация:
  

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

Почему же граф сошелся для Отелло? Для этого давайте взглянем на его левую часть. Теперь все просто, вершины -13 ("Эмилия говорит правду") и -12 ( "Дездемона говорит правду") становятся тупиковыми (доказанными) в восприятии Отелло, и после этого граф легко разрешается.

Итак, что же произошло? Теперь, когда Отелло перестал верить Яго, он автоматически стал верить Дездемоне и Эмилии (что, в принципе, иррационально), и это привело к тому, что граф сошелся, но уже с противоположным результатом. Фаза восприятия мавра сдвинулась на 180 градусов.

Иррациональные элементы и опорные точки

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

Потом, когда Отелло поверил Эмилии и соответственно осознал, что Дездемона говорила правду, а Яго лгал, фаза восприятия Отелло скачком сдвигается на 180 градусов, и для Отелло становятся истинными утверждения всех голубых вершин (отрицательная нумерация, голубой цвет).

Что же произошло? Отелло получил от Эмилии некоторую дополнительную информацию, но он даже не проверил, правдива ли она, а ведь Эмилия могла тоже обманывать, и холодный анализ требует построения "волны" доказательств/опровержений и для фактов, предоставленных Эмилией. Но мавр опять поверил. Да, в соответствии с той реальностью, которую предоставил нам Шекспир, в этот раз он не ошибся. Но, в жизни могло быть все не так, и на самом деле именно Яго мог бы быть истинным положительным героем, преданным и честным, попавшем в паутину интриги.

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

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

Например, как мы видели в случае Отелло, было несколько опорных утверждений, связанных с доверием Яго, доверием Дездемоне и доверием служанке Эмилии. Согласованность заключалась в том, что, чтобы граф сошелся недостаточно было верить Яго, нужно было также не верить Дездемоне и Эмилии и, наоборот.

Пример 1

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

Замечание

Мы никак не обсуждаем вопрос истинности или ложности этих концепций здесь.

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

Пример 2

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

Аксиома волнового анализа

Введем понятия полного и абсолютно полного волновых графов.

Абсолютно полный волновой граф это граф, на котором учтены все возможные волны.

Это значит, что волны этого графа опускаются в том числе и до фундаментальных вопросов, связанных с мирозданием, нашим восприятием, вопросам бытия Например, простое утверждение "Я вижу стол" порождает волны о реальности/иллюзорности нашего мира, объективности/субъективности восприятия, о моем психическом состоянии, ...

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

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

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

Замечание

Возникает вопрос, где же проходит эта граница контекста беседы? На каком уровне глубины анализа разумно остановиться? Что мы готовы принять за аксиомы (и, следовательно, на веру) в нашем анализе?

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

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

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

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

Следствие:

• если произошло разрешение волнового графа, то это говорит о наличии иррационального элемента, ошибке логики или о неполноте волнового графа

Это не математическое утверждение, скорее психологическое.
Идея данной аксиомы заключается в том, что у нас всегда есть волны, которые "доходят" до скрытой информации. Не всегда уместно их исследовать, но всегда можно найти тот уровень, где появятся скрытые данные. Зачем это делать? А зачем формулировать вопрос, с которым все согласны? Темы поднимаются лишь тогда, когда требуется анализ, что предполагает искать точки сомнения, и такие точки в принципе всегда есть.

Говорит ли введенная аксиома о том, что нельзя докопаться до истины?

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

Просто к логике, к знанию, к информации, нужно добавить что-то еще.

Я бы назвал это что-то адекватностью. О сложности и неоднозначности этого понятия мы уже подробно говорили в этой статье, но в любом случае важным компонентом адекватности является также эмоциональная зрелость и развитое чувство гармонии. Можно прекрасно владеть информацией, данными, логическим мышлением и быть при этом безумцем с искаженным восприятием.

Замечание

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

Тот факт, что мы пришли к выводу и особенно то, что мы уверены в своей правоте говорит о том, что мы во что-то поверили. Тоже самое и с нашими оппонентами, но их "вера" другая. Мы имеем разную веру по поводу опорных точек нашего графа.

Типичные ошибки при ведении дискуссии

Волновой анализ также позволяет увидеть причины, почему спорить по старинке не эффективно.

Приведем список типичных ошибок ведения споров:

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

Применение волнового анализа на практике

Пример с Отелло содержит около 50 вершин и это довольно простой анализ. Когда я пытался применить данный подход к реальной ситуации, я имел сотни вершин со множеством связей. Я пользовался и пользуюсь yEd для этого, но все-же это не удобно. Надо также понимать, что каждая вершина это не просто утверждение, это может быть небольшой статьей с описанием фактов и доказательной базой.

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

Так что же может дать нам волновой анализ на практике?

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

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

  
  

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

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

Принципы волнового анализа

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

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

Поэтому в основе анализа несомненно должна лежать свобода в создании любых логических цепочек и смелость, не только потому, что все мы боимся быть неверно истолкованными и потерять хорошие отношения (или даже приобрести врагов), но и потому, что в принципе никто не застрахован от того, что, подвергнув свои убеждения глубокому и честному анализу вы останетесь тем же человеком!

Networkx.

!pip install networkximport networkx as nx

from matplotlib import pyplot as plt%matplotlib inlineplt.rcParams.update({    'figure.figsize': (7.5, 7.5),    'axes.spines.right': False,    'axes.spines.left': False,    'axes.spines.top': False,    'axes.spines.bottom': False})

from pathlib import Pathdata_dir = Path('.') / 'data'# Read edge listG = nx.read_edgelist('example.edgelist')# Draw network#pos = nx.spring_layout(G)pos = nx.spectral_layout(G)#pos = nx.planar_layout(G)nx.draw_networkx(G, pos)plt.gca().margins(0.15, 0.15)

from pathlib import Pathdata_dir = Path('.') / 'data'

G = nx.read_edgelist('example.edgelist')

# source targetИванов КИК1Иванов КИК2КИК1 КИК2КИК1 Ромашка_ОООКИК2 Ведро_АО

pos = nx.spectral_layout(G)

nx.draw_networkx(G, pos)plt.gca().margins(0.15, 0.15)

plt.savefig('plot.png')

Как нарисовать сегмент в networkx.

#подграфикH = G.subgraph(['Иванов', 'КИК1', 'Ромашка_ООО'])plt.subplot(212) print("Подграфик:") nx.draw_networkx(H)

Направленный график в networkx (Directed edge list).

# Read edge listG = nx.read_edgelist(    str('example.edgelist'),    create_using=nx.DiGraph)pos = nx.spectral_layout(G)# Draw networknx.draw_networkx(G, pos, arrowsize=20)plt.gca().margins(0.15, 0.15)

# source targetИванов КИК1 100Иванов КИК2 100КИК1 КИК2 50КИК1 Ромашка_ООО 100КИК2 Ведро_АО 100

# Read edge listG = nx.read_weighted_edgelist(    str('example2.edgelist'))# Extract weightsweights = [d['weight'] for s, t, d in G.edges(data=True)]nx.draw_networkx(G,pos)labels = nx.get_edge_attributes(G,'weight')nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)plt.gca().margins(0.15, 0.15)

Кто кем и как владеет, networkx.

list(nx.all_simple_paths(G,'Иванов', 'Ведро_АО'))

[['Иванов', 'КИК1', 'КИК2', 'Ведро_АО'], ['Иванов', 'КИК2', 'Ведро_АО']]

x=0b=0c=[]for i in list(nx.all_simple_paths(G,'Иванов', 'Ведро_АО')):        for a in i:                if x>len(i)-2:            pass                                else:                        b=int(nx.bidirectional_dijkstra(G, i[x],i[x+1])[0])#доля владения                                   x+=1            c.append(b/100)              print(c)import numpy as npprint(np.prod(c))

x=0b=0c=[]for i in list(nx.all_shortest_paths(G,'Иванов', 'Ведро_АО')):    for a in i:                if x>len(i)-2:            pass                              else:                        b=int(nx.bidirectional_dijkstra(G, i[x],i[x+1])[0])#доля владения                                   x+=1            c.append(b/100)              print(c)import numpy as npprint(np.prod(c))

Netwulf

import netwulf as nwplt.figure(figsize=(200,200))G = nx.read_weighted_edgelist(str('example2.edgelist'),create_using=nx.DiGraph)pos = nx.spring_layout(G)nw.visualize(G)

Webweb.

from webweb import Webweb = Web(title='kitchen_sink')web.display.networkName = 'tree'web.display.networkLayer = 2web.display.colorBy = 'ring'web.display.sizeBy = 'degree'web.display.gravity = .3web.display.charge = 30web.display.linkLength = 15web.display.colorPalette = 'Greens'web.display.scaleLinkOpacity = Falseweb.display.scaleLinkWidth = Truefrom pathlib import Pathdata_dir = Path('.') / 'data'# Read edge listG = nx.read_edgelist('example.edgelist',create_using=nx.DiGraph)plt.figure(figsize=(200,200))# Draw networkpos = nx.spring_layout(G)Web(list(G.edges)).show()

Подножка от Минфина, перекрестное и кольцевое владение.

# source targetD B 45B A 40A B 55E A 60

TLDR: крохотные модельки обошли модные графовые нейронки в предсказании свойств молекул.
Код: здесь. Берегите Природу.

^{ФОТО: Андерс Хеллберг для Wikimedia Commons, модель Грета Тунберг}

Необученная графовая свёрточная нейронная сеть [1] (uGCN) со случайной инициализацией весов уже пару лет занимает первое место в моём списке алгоритмов для задач машинного обучения на графах из-за копеечной стоимости, простоты реализации, да вполне очевидной элегантности решения. В то же время, насколько мне известно, никто ещё не не проводил соревнований между этой простой моделью и её старшей сестрой полноценно обученной графовой свёрточной нейронной сетью (GCN) в режиме обучения с учителем. Вот я сделал.

Мотивация: показать, что uGCN выдаёт качественные представления, которые можно использовать в последующих задачах машинного обучения в индуктивном режиме, когда модели обобщаются к не виденным ранее данным (вдохновлено недавним отчётом [2] о производительности простых моделей в трансдуктивном случае).

Полученные результаты занимательны. В худшем случае простые модели (uGCN + degree kernel + random forest) показали счёт 54:90 против полноценно обученных GCN, в то время как реалистичный сценарий закончился разгромным реваншем 93:51, указывающим на то, что мы можем позволить себе почти бесплатные эмбеддинги, которые превосходят или показывают результаты на уровне полноценно обученных GCN в задаче предсказания свойств графа (например эффекта медикаментов: яд или лекарство) за долю стоимости. Простые модели обучались ~10 минут в то время как весь эксперимент продлился ~4 часа. Перейдём же к деталям и разберёмся с тем, что произошло!

Основные понятия

Многие из важных наборов данных об окружающем нас мире имеют связный характер: социальные сети, графы знаний, взаимодействия белков, всемирная паутина WWW и т.д. (просто несколько примеров) [1].

Граф, обыкновенно записываемый как G=(V, E) это математическая модель, множество множеств, состоящее из набора вершин V и множества рёбер E попарных связей e(i, j) между вершинами i и j. Расширением Графа является модель Граф со Свойствами (Labeled Property Graph), позволяющий задать вектор признаков xi для вершины i (мы также можем определять свойства для рёбер, однако это выходит за рамки сегодняшнего эксперимента). Графовая нейронная сеть [3] (GNN) это модель машинного обучения (параметрическая функция, которая подбирает, другими словами выучивает, параметры из данных), расширяющая возможности хорошо известного семейства алгоритмов, вдохновлённых биологией, до работы с неструктурированными данными в виде графов. На мой взгляд, передача сообщений это самая простая интуиция для понимания механики работы GNN и вполне оправдано обратиться к мнемоническому правилу 'скажи мне, кто твой друг и я скажу тебе кто ты'. Графовые свёрточные нейронные сети (GCN) очень подробно описал их изобретатель здесь (https://tkipf.github.io/graph-convolutional-networks/) и мне, право, непросто что-то ещё добавить к этой замечательной истории.

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

Многослойная GCN с фильтрами первого порядка.

Данные

Проведём серию экспериментов на общедоступных данных. Мы обратимся к (i) коллекции TUDatasets [4] и (ii) ограничим наше упражнение задачей бинарной классификации (предсказанием свойств) небольших молекул. Ещё одним условием нашего мероприятия будет (iii) использование графов с признаками вершин.

Заданные ограничения оставляют нам несколько наборов данных, широко используемых для сравнения современных алгоритмов. Вот наш итоговый список: AIDS, BZR, COX2, DHFR, MUTAG и PROTEINS. Все обозначенные наборы данных доступны как часть Pytorch Geometric [5] (библиотека для глубокого обучения на графах) в двух версиях: оригинальной и очищенной от дубликатов [6]. Итого у нас будет 12 датасетов.

AIDS Antiviral Screen Data [7]

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

Benzodiazepine receptor (BZR) ligands [8]

Оригинальный набор содержит 405 молекул, очищенная версия 276, по 35 признаков на вершину.

Cyclooxygenase-2 (COX-2) inhibitors [8]

Оригинальный набор содержит 467 молекул, очищенная версия 237, по 35 признаков на вершину.

Dihydrofolate reductase (DHFR) inhibitors [8]

Оригинальный набор содержит 756 молекул, очищенная версия 578, 35 признаков на вершину.

MUTAG [9]

В наборе содержится 188 химических соединений, разделённых на два класса согласно их мутагенному воздействию на бактерии. В очищенной версии 135 молекул, 7 признаков на вершину.

PROTEINS [10]

Энзимы и не-энзимы. В оригинальном наборе содержится 1113 молекул, по 3 признака на вершину. Очищенная версия 975 структур.

Дизайн Эксперимента

Мы устроим турнир!

Для каждого набора данных проведём 12 раундов обучения и тестирования.

В каждом раунде:

(1) псевдослучайным образом разделим данные в пропорции 80/20 в Pytorch Geometric (начиная со стартового параметра генератора random seed = 42 и увеличивая его на единицу в каждом последующем раунде), таким образом 80% точек данных (графов) будут использованы в качестве обучающей выборки, а оставшиеся 20% будут тестовой выборкой;

(2) обучим модели и оценим долю верных ответов (accuracy) на тесте.

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

Для GCN мы проводим 200 эпох обучения и тестирования со скоростью обучения learning rate = 0.01 и принимаем во внимание:
(А) среднее значение доли верных ответов для 10 финальных эпох обучения реалистичный сценарий;
(В) наибольшее значение доли верных ответов, достигнутое в процессе обучения (как если бы мы сохраняли промежуточное состояние для того, чтобы выбрать наилучшую модель впоследствии) наилучший сценарий для GCN (и наихудший для простых моделей);

(3) лучшей модели присуждается 1 балл;

(4) в случае ничьей балл присуждается лёгкой модели.

Всего будет распределено 288 баллов: 12 датасетов 12 раундов 2 сценария.

Модели

Degree kernel (DK) или степенное ядро гистограмма степеней вершин (количество рёбер, соединённых с вершиной), нормированная к числу вершин в графе (таким образом вектор признаков для каждого графа состоит из размеров долей вершин с количеством связей, равным индексу признака, от всего множества вершин в сумме они дают единицу).

import networkx as nximport numpy as np from scipy.sparse import csgraph# g - граф формате популярной библиотеки NetworkXnumNodes = len(g.nodes)degreeHist = nx.degree_histogram(g)# нормализуемdegreeHist = [x/numNodes for x in degreeHist]

Необученная графовая свёрточная нейронная сеть (uGCN) со случайной инициализацией весов 3 слоя с промежуточной нелинейной активацией (ReLU, т.е. f(x) = max(x, 0)). Аггрегация усреднением полученных после прямого прохода 64-разрядных векторов (эмбеддинги вершин) позволяет получить компактное представление графа. Это на самом деле очень просто.

A = nx.convert_matrix.to_scipy_sparse_matrix(g)

Воспользуемся вариантом реализации одного слоя свёртки в три строки, который пару лет назад предложил iggisv9t :

# A - матрица связности графа# X - матрица признаков вершин (np.array)D = sparse.csgraph.laplacian(A, normed=True)shape1 = X.shape[1]X = np.hstack((X, (D @ X[:, -shape1:])))

(код здесь приводится чтобы подчеркнуть очаровательный минимализм реализации метода)

Разберём его на части и пересоберём заново.

Использованная реализация uGCN выглядит так:

# A - матрица связности графа# X - матрица признаков вершин (np.array)# W0, W1, W2 - случайным образом инициализированные весаD = sparse.csgraph.laplacian(A, normed=True)# слой 0Xc = D @ X @ W0# ReLUXc = Xc * (Xc>0)# конкатенация признаков вершин с аггрегированной информацией соседейXn = np.hstack((X, Xc))# слой 1Xc = D @ Xn @ W1# ReLUXc = Xc * (Xc>0)Xn = np.hstack((Xn, Xc))# слой 2 - эмбеддинги вершинXc = D @ Xn @ W2# аггрегация усреднением - эмбеддинг графаembedding = Xc.sum(axis=0) / Xc.shape[0]

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

mix = degreeHist + list(embedding)

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

Графовая свёрточная нейронная сеть (GCN) полноценно обученный классификатор, состоящий из 3 свёрточных слоёв размерностью 64 с промежуточной нелинейной активацией (ReLU), агрегацией усреднением (до этого момента архитектура GCN очень похожа на uGCN), за которой следует слой регуляризации дропаутом (произвольным обнулением разрядов с вероятностью 50%) и линейный классификатор. Мы будем обозначать результаты модели, отобранные в наилучшем для GCN сценарии (B) как GCN-B, а модели в реалистичном сценарии (А) как GCN-A.

Результаты

После 144 раундов (12 датасетов * 12 раундов) сравнения качества предсказаний на отложенной выборке между простыми моделями и полноценно обученными графовыми свёрточными сетями 288 баллов распределились как:

147:141

Доля верных ответов на тестовых выборках варьировалась между раундами и частенько случались ситуации, в которых простые модели доминировали над более сложными противниками.

Наборы данных, в которых простые модели побеждают: AIDS, DHFR(A) и MUTAG.

Например, DK собрала все 48 баллов для набора данных AIDS, демонстрируя отрыв более чем на 10% (абсолютное значение) от доли верных ответов полноценно обученной GCN.

Здесь побеждают GCN: BZR, COX2 и PROTEINS.

Индивидуальный зачёт:
90 GCN-B;
71 DK;
55 Mix (uGCN + DK);
51 GCN-A;
21 uGCN.

Достаточно подробный протокол соревнований приведён в блокнотике с кодом, таблица с результатами раундов здесь.

В целом, результаты стабильно варьировались между очищенными и оригинальными наборами данных. Это ещё раз напоминает о важности качества данных для проведения адекватных сравнений между моделями. Хорошая новость в том, что в исследовательском сообществе уже есть движение в данном направлении и значительные усилия лучших умов в области уже направлены на организацию честных турниров.

Выводы

Как видим, проведенный эксперимент подтверждает предположение о том, что в задаче предсказания свойств молекул мы можем позволить себе использовать почти бесплатные эмбеддинги, которые превосходят или показывают результаты на уровне полноценно обученных нейронных сетей. Наблюдения согласуются с вдохновляющими этот эксперимент результатами [2] в том, что концептуально метод Label Propagation очень похож на передачу сообщений в графовой свёрточной нейронной сети. Объяснение эффективности скорее всего следует искать в том, что на самом деле мощнее подбирать параметры фильтров для того, чтобы внутренние представления, выученные сетью стали линейно разделимыми, либо же просто использовать классификатор помощнее, как это сделано в рассмотренном примере.

Дисперсия результатов между раундами соревнования напоминает о том, что всякое сравнение дело непростое. Здесь стоит упомянуть Free Lunch Theorem и напомнить о том, что использовать сразу несколько моделей в построении решения скорее хороший тон. Также важно отметить влияние разбиения на выборки в ходе сравнения на одном и том же наборе данных одна и та же модель может показывать очень разное качество. Поэтому сравнивая модели, убедитесь, что обучаете и тестируете их на идентичных выборках. К слову, фиксация параметров генератора псевдослучайных чисел не панацея

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

Послесловие

В лекции открытого курса по графам знаний GCN названа Королевской Лазейкой Через Пространство Фурье, этот ярлык приклеился с тех пор, когда впервые выступил на публике с рассказом о силе графов и провёл первые эксперименты с классификацией картинок (как графов) для того, чтобы продемонстрировать мощь спектральных фильтров одной юной леди, запускавшей стартап в милой моему сердцу аэрокосмической области. Данная заметка появилась в результате того, что пару недель назад в реальной задаче на закрытых данных uGCN, вместе с простенькими моделями показали результат, который полноценно обученные GCN смогли превзойти всего на 2% (96 против 98) и мне вздумалось проверить вопрос о том, кто кого заборет ещё на каких-нибудь данных.

В наши дни машинное обучение на графах превратилось в знаменитость, всё больше исследователей обращают внимание на эту область и новые архитектуры графовых нейронных сетей появляются каждую неделю. Однако на самом деле мы ещё не очень хорошо понимаем почему GNN так успешны и нужны ли они для хорошего качества решения [2].

Перед тем, как ступать на очаровательный путь машинного обучения на графах, пожалуйста ознакомьтесь с основами этого дела. Значительные усилия прилагаются к тому, чтобы сделать новейшие достижения (да и классические методы тоже) доступными широкой аудитории совершенно бесплатно. Упомяну лишь несколько из таких инициатив: материалы и лекции стенфордского cs224w, площадку для тестирования качества алгоритмов Open Graph Benchmark [14] и недавнюю работу об основах геометрического глубокого обучения [15] методологию разработки новых архитектур нейронных сетей. Напоследок, ещё раз напомню о том, что начинать проекты машинного обучения стоит с простых методов, вроде ядер и необученных графовых свёрточных сетей достаточно часто эти модельки показывают неприлично хороший уровень.

Берегите Природу, используйте алгоритмы эффективно. Порою неученье сила.

Литература

[1] Kipf & Welling, Semi-Supervised Classification with Graph Convolutional Networks (2017), International Conference on Learning Representations;
[2] Huang et al., Combining Label Propagation and Simple Models out-performs Graph Neural Networks (2021), International Conference on Learning Representations;
[3] Scarselli et al., The Graph Neural Network Model (2009), IEEE Transactions on Neural Networks ( Volume: 20, Issue: 1, Jan. 2009);
[4] Morris et al.,TUDataset: A collection of benchmark datasets for learning with graphs (2020), ICML 2020 Workshop on Graph Representation Learning and Beyond;
[5] Fey & Lenssen, Fast Graph Representation Learning with PyTorch Geometric (2019), ICLR Workshop on Representation Learning on Graphs and Manifolds;
[6] Ivanov, Sviridov & Burnaev, Understanding isomorphism bias in graph data sets (2019), arXiv preprint arXiv:1910.12091;
[7] Riesen & Bunke, IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning (2008), In: da Vitora Lobo, N. et al. (Eds.), SSPR&SPR 2008, LNCS, vol. 5342, pp. 287-297;
[8] Sutherland et al., Spline-fitting with a genetic algorithm: a method for developing classification structure-activity relationships (2003), J. Chem. Inf. Comput. Sci., 43, 1906-1915;
[9] Debnath et al., Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds (1991), J. Med. Chem. 34(2):786-797;
[10] Dobson & Doig, Distinguishing enzyme structures from non-enzymes without alignments (2003), J. Mol. Biol., 330(4):771783;
[11] Pedregosa et al., Scikit-learn: Machine Learning in Python (2011), JMLR 12, pp. 2825-2830;
[12] Waskom, seaborn: statistical data visualization (2021), Journal of Open Source Software, 6(60), 3021;
[13] Hunter, Matplotlib: A 2D Graphics Environment (2007), Computing in Science & Engineering, vol. 9, no. 3, pp. 90-95;
[14] Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020), arXiv preprint arXiv:2005.00687;
[15] Bronstein et al., Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges (2021), arXiv preprint arXiv:2104.13478.

Переведя гипотезу Келлера на понятный компьютерам язык поиска в графах, исследователи, наконец, решили задачу покрытия пространств плиткой

Загадочное седьмое измерение

Соединяем точки

Масштабирование

Язык логики

Скрытые эффективности

Давид Конлон и Асаф Фербер подняли нижнюю границу для значений многоцветных чисел Рамсея. Эти числа говорят о том, насколько можно увеличивать граф, пока в нём не начнут появляться неизбежные закономерности

Цветные связи

Изучая случайность

Включение порядка

1. Для каждой вершины графа находим все смежные вершины и начинаем формировать цикл движением в сторону каждой смежной вершины поочередно.
2. Если число смежных вершин (исключая ту, с которой вошли) =0, то идём обратно, формируя цикл ---> п.5
3. Если число смежных вершин (исключая ту, с которой вошли) равно 1, то идём по ней, формируя цикл ---> п.5
4. Если число смежных вершин (исключая ту, с которой вошли) >=2, то ищем самое правое ответвление (путем нормализации векторов и их перемножения), и идём по нему, формируя цикл ---> п.5
5. Анализируем вернулись в начальную точку? Если нет, то ---> п.2
6. Если да, то завершаем формирование цикла и осуществляем проверки.
7. Ищем в цикле повторяющиеся вершины, если такие есть, то удаляем все вершины между ними, оставляя только одну повторяющуюся.
8. Ищем в числе уже сформированных циклов совпадающие с данным циклом, и если есть, то прерываем формирование цикла и переходим на ---> п.1 (проверять надо с учетом всех сдвигов и направлений)
9. Ещё раз проходим по циклу и смотрим на левые ответвления от него. Найдя такие ответвления, для каждого организуем поиск в ширину (или в глубину, неважно). Если при этом мы попадаем в конце концов на вершину сформированного цикла (кроме текущего), то прерываем формирование цикла и переходим на ---> п.1
10. Записываем цикл, и переходим на поиск нового ---> п.1

Постановка задачи

Пространства и подпространства графов (*)

Матрицы и тензоры

Формула преобразования

Величина результирующих связей между элементами множества равна сумме исходных и наведенных связей

Пример расчета

Введение

• Они недостаточно быстры
• Они требуют визуальной обратной связи

Определяемся с жестами

Кодирование жестов

Привязка жестов к действиям

Практика

Наблюдения

• Хотя процесс Python, в котором запущена эта система ввода, обычно потреблял не больше 10% ресурсов процессора, если бы он должен был постоянно выполняться в фоновом режиме, то я бы реализовал его заново и оптимизировал на языке более низкого уровня, чтобы процессор мог заниматься более затратными задачаи.
• После покупки геймпада DualShock4 я понял, то довольно точно могу выполнять диагональный ввод. Интеграция диагонального ввода уменьшит количество более сложных вариантов ввода, а значит, увеличит скорость.
• После недели практики я могу печатать на геймпаде всего в два раза медленнее, чем на клавиатуре. Учитывая мою безумную скорость печати на клавиатуре, это совсем неплохо. Для дополнительной выгоды я использую оставшиеся варианты ввода, привязав их к специальным действиям, например, к горячим клавишам или операциям конкретных программ.
• Похоже, сильнее всего напрягают большие пальцы круговые движения. Вероятно, стоит заменить их более долгими, но более прямыми вариантами ввода.
• Напряжение больших пальцев снижается после практики. Однако в начале стоит практиковаться всего по несколько минут за раз.

Заключание

Входные данные

Выходные данные

• Список подчиненных сотрудников для данного
• Список начальников для данного сотрудника
• Является ли сотрудник подчиненным для данного
• Список подчиненных сотрудников для данного(путь от начальника к сотруднику)

Реализация, используя PL/pgSQL

Хранение графа в виде таблицы ребер

CREATE TABLE graph(    vertex integer NOT NULL ,         --id записи в целевой таблице  edge integer NOT NULL ,           --id ребра  vertex_order integer NOT NULL --порядок вершины ( 0 предок, 1 потомок));

CREATE SEQUENCE enge_seq OWNED BY graph.edge; 

Заполнение таблицы ребер

--Генерация нового id ребраnew_id = nextval('enge_seq');

--Вставка предкаINSERT INTO  graph (vertex  , edge , vertex_order  ) VALUES ( id0 , new_id , 0  );

--Вставка потомкаINSERT INTO  graph (vertex  , edge , vertex_order  ) VALUES ( id1 , new_id , 1  );

Получение списка подчиненных сотрудников для данного current_id

SELECT   id FROM   graphWHERE   vertex_order  = 1 AND   edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 0  );

Получение списка начальников для данного current_id

SELECT   id FROM   graphWHERE   vertex_order  = 0 AND   edge IN (SELECT edge FROM graph WHERE vertex  = current_id AND vertex_order = 1  );

Генерация матрицы доступности (алгоритм Дейкстры) из заданной вершины start_id

CREATE TEMPORARY TABLE tmp_matrixAS(  SELECT     DISTINCT vertex  ,     FALSE AS label ,    999999 AS distance ,    FALSE AS is_finish   FROM    graph);

UPDATE tmp_matrix SET label = TRUE , distance = 0 WHERE vertex = current_id ; current_id = start_id ;SELECT   distanceINTO   current_distanceFROM   tmp_matrixWHERE   vertex = current_id;SELECT   EXISTS (SELECT 1 FROM tmp_matrix WHERE label = FALSE )INTO  not_visit;

WHILE not_visit LOOP  FOR v_rec IN    SELECT       *   FROM      tmp_matrix  WHERE     NOT label AND     --Вершина достижима за один шаг     vertex IN ( SELECT                        id                      FROM                       graph                    WHERE                       vertex_order  = 1 AND                       edge IN (SELECT                                      edge                                     FROM                                       graph                                     WHERE                                       vertex  = current_id AND vertex_order = 0  ))  LOOP        --Найдена достижимая вершина    IF v_rec.distance > (current_distance +1)    THEN       UPDATE tmp_matrix SET distance = (current_distance +1) WHERE vertex = v_rec.vertex;    END IF ;       --если закончен обход   IF SELECT         NOT EXISTS         (          SELECT 1 FROM graph WHERE vertex = v_rec.vertex AND vertex_order = 0         )   THEN     UPDATE tmp_matrix SET label = TRUE , is_finish = TRUE WHERE vertex = v_rec.vertex;   END IF ;     END LOOP;    UPDATE tmp_matrix SET label = TRUE WHERE vertex = current_id ;  --Следующая итерация  SELECT     vertex  INTO    current_id   FROM     tmp_matrix   WHERE     NOT label AND    distance < 999999 ;  SELECT     distance  INTO     current_distance  FROM     tmp_matrix   WHERE      vertex = current_id ;  SELECT     EXISTS (SELECT 1 FROM tmp_matrix  WHERE label = FALSE )  INTO   not_visit ;  IF current_id IS NULL   THEN     not_visit = FALSE ;   END IF;END LOOP;

SELECT   vertex ,   label ,    distance ,   is_finishFROM   tmp_matrix WHERE   distance != 999999 ;

Является ли сотрудник с check_id подчиненным для данного start_id

IF EXISTS   ( SELECT distance FROM tmp_matrix WHERE vertex = check_id  )THEN    RETURN TRUE;ELSE   RETURN FALSE;END IF;

Список подчиненных сотрудников для данного(путь от начальника start_id к сотруднику finish_id)

current_id = finish_id ;result[1] = finish_id ; WHILE current_id != start_id LOOP  SELECT     par.id   FROM    ( SELECT        id      FROM       graph    WHERE       vertex_order  = 0 AND       edge IN (SELECT                      edge                     FROM                       graph                     WHERE                       vertex  = current_id AND vertex_order = 1  )) par  JOIN  tmp_matrix m ON ( par.id = m.vertex  )  INTO     parent_id  LIMIT 1 ;  SELECT     array_append( result , parent_id )  INTO     result ; --Следующая итерацияcurrent_id = parent_id ;   END LOOP;