Чому авторегресивні моделі погано генерують цикли графів?

Проблема серіалізації

Граф — це множина вузлів і ребер. Перетворення його на послідовність токенів означає вибір порядку для вузлів. Серіалізація в ширину обходить сусідів перед віддаленими вузлами. Ребра, що з'єднують вузол із чимсь далеким у цьому порядку, потрапляють за межі поточного вікна генерації. Модель не бачить їх за один прохід. Цикли зникають.

Стаття каже це прямо: авторегресивні генератори за один прохід систематично недостворюють цикли. Єдина глобальна умова також не здатна розрізняти кандидатські ребра. Обидві перешкоди виходять з одного кореня: умова занадто груба.

Як GraphVQ токенізує контексти вузлів

GraphVQ спочатку будує токенізатор. Кожен вузол отримує контекст: його ознаки плюс локальна маска ребер, отримана з багаторядкової серіалізації в ширину. Ці контексти потрапляють у VQ-VAE зі спільним словником. Декодер використовує каліброване BCE бернуллівське декодування ребер.

Токенізатор відновлює ознаки вузлів з точністю 0.86–0.99. Він декодує локальні ребра з AUROC ≥ 0.89 та ECE ≤ 0.007. Квантування відбувається один раз. Словник стає основою для другого етапу.

Чому потрібні парні ознаки

Структурно-чутливий декодер приймає послідовність токенів. Він видає глобальну матрицю суміжності, обумовлену парними ознаками від токенів. Стаття формалізує, чому будь-яка глобальна умовна сума не працює: результат про неможливість у певній області доводить необхідність парних ознак. Контекст рівня пар перетворює квантований словник на використану вісь ємності. Генерація, вірна розподілу, стає можливою. Майбутнє попереднє навчання на рівні токенів отримує опору.

Результати на чотирьох наборах даних

За одного протоколу на чотирьох наборах парне умовлення покращує orbit MMD з 0.248 до 0.174 на PROTEINS і в 3.4 рази на стрес-тесті кільця. Приріст зникає на контрольі з випадковими мітками. Це зникнення — підпис зв'язку атрибутів і топології. Покращення зафіксовано саме там, де атрибути несуть сигнал, релевантний до ребер.

На PROTEINS GraphVQ посідає перше місце серед навчених генераторів. На SYN-COMM ділить першу позицію. Orbit MMD покращується в 2.7–17 разів порівняно з одноетапною генерацією на трьох наборах. Бутстреп-інтервали на рівні сідів підтверджують: рейтинг не є шумом сід.

У MUTAG ціль неважених ребер недостворюється, про що звітується. Стаття не каже, скільки графів залишається у розгортанні.