Таблица умножения как граф

С чего обычно начинают про графы

В 1736 году Леонард Эйлер решил задачу о кёнигсбергских мостах — и попутно изобрёл целый раздел математики. Фокус был в отказе: Эйлер выбросил из задачи всё, кроме факта «что с чем соединено» — берега стали точками, мосты — линиями, и оказалось, что ответ зависит только от соединений, а не от расстояний, форм и названий. Так появился граф: математический объект, который помнит исключительно связи. Любая сеть — маршруты, зависимости в коде, друзья друзей, ссылки в вики — при ближайшем рассмотрении оказывается графом, а не схемой и не таблицей.

Возьмём десять вершин — числа от 1 до 10. Соединим каждую пару и напишем на ребре произведение концов: между 3 и 7 вес 21, между 9 и 10 — 90. Петель не разрешаем. Получился полный граф K₁₀: десять вершин, сорок пять рёбер, веса от 2 до 90.

А теперь выпишем матрицу смежности — таблицу, где на пересечении строки i и столбца j стоит вес ребра. Она равна i·j. Но это же дословно таблица умножения, та самая, из детства, — только с выколотыми клетками диагонали. Любимая арифметика начальной школы оказалась паспортом графа. И обратная задача работает: покажи мне эту таблицу — и я нарисую граф, не спросив ни слова.

Слева — матрица смежности (она же таблица Пифагора, диагональ пуста). Справа — тот же объект глазами графа: вес ребра задан толщиной и цветом

Таблица без диагонали хитрее таблицы с диагональю. Если петли вернуть (единица на месте (1,1), четвёрка на (2,2)…), матрица ранга 1: все строки пропорциональны, один неттовый собственный вектор (1, 2, …, 10). Выколов диагональ, мы добавили −diag(1,4,9,…,100) — и матрица раздулась в полный ранг 10: собственное число-гигант 321,4 и хвост отрицательных вплоть до −92,3. Одна вытертая диагональ превратила «почти ничего» в «полноценно всё».

Взвешенная степень — парабола. Сумма весов всех рёбер вершины i равна i·(1+2+…+10 без самого i) = i·(55−i). Это не прямая, а перевёрнутая парабола: вершина 1 тянет на себя 54, вершина 5 — 250, вершина 10 — уже 450, но прирост от 9 к 10 меньше, чем от 4 к 5. «Важность» вершины растёт с номером, но с замедлением — классическая форма насыщения, та же, что в законе Вебера-Фехнера про ощущения.

d(i) = i·(55−i): веер вершины толстеет с номером, но с замедлением — на этом отрезке парабола ещё не дошла до своего максимума при 27,5

Вес ребра — это число способов. Ребро 36 одно (4·9=6·6, но 6·6 — петля), а вот 12 встречается дважды (2·6 и 3·4): у графа есть «созвучия» — разные пары дают одинаковый вес. Всего в таблице 10×10 без петель ровно 36 разных весов на 45 рёбрах.

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

Как у графа появляется «звучание»

У любого графа есть матрица смежности — а у матрицы, стало быть, собственные числа. Их совокупность математики называют спектром — и это не метафора: спектр ведёт себя как звук. Протяни струну-граф «в ноту λ» — и она отзовётся: λ₁ говорит, насколько граф слит в единый гул, следующие ноты — сколько в нём общин, слоёв, оболочек. Тот факт, что «музыку графа можно послушать», — один из самых красивых сюрпризов дискретной математики.

Наш пифагоров граф звучит поучительно. С петлями (верни мы диагональ) — это чистый тон: единственная нота λ₁ = 385, ровно сумма квадратов 1²+2²+…+10², остальные девять нулевые. Граф-таблица умножения с диагональю — это один аккорд, один вектор-гул (1, 2, …, 10). Без петель тон расщепляется в гребень: главный тон 321,4, а под ним лесенка отрицательных — −1,1; −4,5; −10… вплоть до −92,3. Вытирание диагонали сработало как демпфер: тот же самый гул, но с привкусом всех «несостоявшихся петель».

Слева — граф с петлями: одна нота 385. Справа — без петель: главный тон и гребень обертонов до −92,3

Из спектра растёт и понятие важности вершины. Ведущий собственный вектор нашей матрицы (с точностью до знака) — это (1, 2, …, 10) как есть: центральность вершины пропорциональна её номеру. В более привычном «PageRank» (тот же мотив, только нормированный по весам соседей) десятки тоже забирают почти всё внимание сети. Здесь полезно вспомнить про гиперссылки: PageRank — это буквально «рейтинг страницы по весу ссылок на неё», то есть центральность вершины в графе интернета. Google построил корпорацию на одной идее: важность — это свойство связей, а не содержимого. А мы получили её учебным примером из таблицы умножения.

Зачем графы языковым моделям

Казалось бы, нейросеть — сплошные векторы, где там граф? А везде — и вот три независимых сюжета.

Первый: само знание — граф. Текст — цепочка, но знание — сеть: «столица», «находится в», «больше чем» — это рёбра. Отсюда графы знаний (в духе ресурсно-целевого управления): база фактов, связанных так, что по ним можно идти. Модель, дополненная таким графом (приём называют GraphRAG), отвечает на вопросы «через связи»: не «что похоже по смыслу», а «что следует по цепочке». Поиск по смыслу хорош для «найди похожее»; за «что с чем связано и актуально ли» отвечают именованные рёбра.

Второй: внимание — это граф на каждое слово. Внутри трансформера каждый токен смотрит на другие токены через механизм внимания — и это взвешенный ориентированный граф между словами, перестраиваемый на каждом слое. Весь «контекст» модели есть не что иное, как разреженный граф «кто на кого посмотрел и с каким весом». Поэтому модели так естественно перенимают графовую оптику: она у них в анатомии.

Третий: агент без графа слеп к структуре. Когда агент должен понять большой код, большую вики или большую базу, он работает не со «всем текстом», а с графом вызовов/ссылок/внешних ключей — ходит по рёбрам, как мы сегодня ходили бы по оглавлению. Практический вывод для оператора ИИ: приводя знание, приносите связи — паспорт, карту, индекс. Голая пачка документов для модели — как город без карт: всё на месте, а не добраться. Модель запоминает слова; граф запоминает, что к чему относится — и это ровно та часть понимания, которая у чистой модели самая хрупкая.

Круг замыкается красиво: мы начали с детской таблицы, увидели в ней паспорт графа, послушали его звучание, вывели из него PageRank — а на выходе получили объяснение, как устроена память машины. Математика умеет прятать целые вселенные в самых скромных таблицах — надо только научиться смотреть на таблицы как на графы.

Идеи и расчёты — автора (@Tottop10, pro100.D); иллюстрации и текст — его ИИ-агент. CC BY 4.0.