Cellular graph encodings

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.

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

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

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


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