Cellular graph encodings

[donRumata03]

Tracking issue for this research direction.

На данный момент на графах с количеством вершин $> 40$ сходимость GOLEM деградирует: #69. Методы поиска графов с доступам к градиенту целевой функции, например NOTEARS, работают с заметно большими графами.
Один из вариантов преодоления этой проблемы — использовать непрямые кодировки в эволюции: особи представляются не как графы непосредственно, а как что-то, раскодирующееся в них. Статья, упомянутая в #100, утверждает, что такие кодировки стоит искать среди expressive encodings. При специализации задачи для графов возникает несколько вариантов. По сравнению с прямыми кодировками им свойственны:

• модуляризуемость. Переиспользование блоков внутри графа, то есть поиск в пространстве графов с низкой Колмогоровской сложностью: при больших графах точное (aka оптимальное) решение обычно искать смысла не имеет и зачастую оно не модуляризуемо, но в реальных задачах очень часто существует достаточно хорошее модуляризуемое решение.
• полигены — на одну и ту же часть фенотипа влияют разные части генома → нейтральность (позволяет безнаказанно накапливать мутации, которые не проявляются, но могут оказаться полезными при смене среды — эффект «canalization»),
• плейотропия — один и тот же ген влияет на многие части фенотипа → модулярность (позволяет компактно и реюзабельно кодировать фенотип).

L-systems

https://en.wikipedia.org/wiki/L-system

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

Можно парсить дерево из строки, а можно генерировать матрицу смежности графа, как в «Designing neural networks using genetic algorithms with graph generation system».

Простой подход, но очень много проблем.

Гиперграфовые грамматики

На каждом шаге вывода имеется гиперграф с рёбрами, помеченными метками-нетерминалами, которые заменяются на гиперграфы с входными и выходными узлами. При этом сопоставление узлов вставляемого графа и вершин, инцидентных ребру, при эволюции осмысленно производить на основе soft matching по эволюционирующим меткам (см. статью):

Graph Design by Graph Grammar Evolution, 2007
↑↑↑ здесь отдельно поддерживается пулл правил, отдельно грамматики — его подмножества.

Коэволюция компонентов и методов их комбинации

Популяции:

• Блоки (в случае NAS — несколько слоёв)
• Глобальная структура с ссылками на блоки

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

Evolving Deep Neural Networks, Risto Miikkulainen, 2023

Клеточные кодировки

Граф представляется деревом программы особого вида, которое «исполняется» клетками в процессе эмбриогенеза. Когда программа клетки завершается, она превращается в вершину графа. К этому дереву уже применяются «простые» мутации.

Обладают привлекательными теоретическими свойствами:

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

В частности, для многих классов графов можно подобрать набор разрешённых операций в клетках, чтобы выполнялась полнота и замкнутость для конкретной задачи. Соответственно, можно автоматически генерировать кодировку для произвольного объекта GraphRequirements и каких-то graph verifier-ов, а значит мутации не будут выводить из искомого класса графов.

Кажется, можно доказать, что клеточные кодировки являются expressive encodings в смысле статьи из #100.

На данный момент фокус направлен на них.

• Статья, где впервые ввели клеточные кодировки:
  Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm, Gruau, 1994

• XC-NAS: A New Cellular Encoding Approach for Neural Architecture Search of Multi-path Convolutional Neural Networks, 2023
  Ищут макро-архитектуру из существующих building-блоков (convolution, resNet и Inception). Процесс эволюции занимает один GPU-day.

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

  Мутация: классическая для GP: смена поддерева какой-то ноды на случайное какого-то размера.
  Кроссовер: аналогично — смена случайных поддеревьев, получая 2 отпрыска.
  Селекция: турнирная с тюныящимся размером турнира.

GANы

TODO

Эволюция в пространстве embedding-ов?
Эволюция весов части GAN?!

Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art: https://arxiv.org/pdf/2008.12646.pdf

Бенчмарки, процесс разработки

На данный момент — ведутся эксперименты, после чего, в случае успеха — буде внедрять в GOLEM.

Реализовано MVP, проверена замкнутость и полнота в разных подпространствах DAGов: с 1 или многими истоками и стоками, получен прирост скорость сходимости по правнению с обычным DEAP.

Текущие задачи:

• Доказать или опровергнуть утверждение, что клеточная кодировка — expressive (в зависимости от подмножества операторов).
  (TODO: улучшить асимптотику?)
  [x] Получить теоретический результат о лучшей скорости сходимости клеточных кодировок по сравнению с прямыми на некотором классе задач.
  • Двухуровневые (то есть вложенность раскрытия правил — 2) Гиперграфовые грамматики
  • Большее количество уровней вложенности и разнообразие блоков
• Подобрать для разных классов графов оптимальное подмножество операторов (tree-DAG; DAG, разделяемый на слои, где связи только если $|\mathrm{layer}_i - \mathrm{layer}_j| \leq d$, прочих часто встречающихся классов).
• Добавить поддержку параметров, ассоциированных с вершинами и рёбрами.
• Представлять операторы в вершинах как векторы того, какие операции производятся и над чем. Это позволит решить задачу поиска подмножества операторов эволюцией, а также структурировать код.

В процессе разработка идей:

• Поддержать набор операций и правил применения для обеспечения полноты и замкнутости в DAGах, ограниченных прозвольными GraphRequirements и GraphAdvisor.
• За счёт регистров, soft матчинга или рандома попробовать выделять какую-то часть связей ноды (сид рандома/метки тогда, вероятно, будут храниться в геноме).

При генерации дерева кодировки и мутациях вершины устанавливаются в случайную инструкцию клеточной кодировки, изменяющую окрестность клетки-вершины: она может обрезать связи, может добавлять вершину (по-разному связанную с этой и наследующую/отбирающую связи материнской клетки). Всего таких инструкций ≈20 штук.

Также планируется тестирование на NAS Bench.