Спектральный графовый алгоритм балансировки загрузки также использует рекурсивное деление пополам графа. Данный алгоритм производит хорошие разделения для широкого класса графов, но имеет высокую вычислительную сложность, поскольку требует вычисления собственного вектора матрицы Лапласа, соответствующей исходному графу.
Положим, что вычислительные сложности всех процессов одинаковы и величина четна. Рассмотрим задачу разделения графа на два подграфа таким образом, чтобы
(*) их суммарные вычислительные сложности были равны (т.е. были равны количества процессов в каждом из подграфов) и
(**) количество разрезанных ребер было минимально.
Как мы уже отмечали выше, последнее условие позволяет с высокой точностью сбалансировать коммуникационную загрузку процессоров в случае, когда объемы данных, передаваемых между процессорами невелики. Положим, что граф замкнут (т.е. не содержит узлов, которые "висят" на одной ветви или вообще «в воздухе»).
Определим матрицу смежности графа такую, что =1, если вершины , связаны между собой ребром, и =0 - в противном случае. Матрицу смежности графа легко получить из матрицы (если , то ; если , то ). Определим также (*) диагональную матрицу степеней вершин графа : , , где величина равна степени вершины (числу ребер, инцидентных этой вершине). Кроме того, введем в рассмотрение матрицу Лапласа для графа

Введенные обозначения иллюстрирует рис. 1 (в матрицах ,, для простоты записи не показаны нулевые элементы).
Рис. 1.  Пример построения матриц A,B,L и оптимальной бисекции графа.
Определим нормализованные собственные векторы матрицы , а также соответствующие собственные значения этой матрицы.
Утверждение 1. Искомая оптимальная бисекция графа может быть найдена следующим образом:
•находим взвешенное среднее компонентов вектора =;
•если <, то относим вершину графа к первому подграфу, в противном случае – ко второму подграфу;
•если несколько величин имеют значение , то распределяем соответствующие вершины между подграфами равномерно.
В рассмотренном виде спектральный алгоритм бисекции может приводить к получению несвязанного подграфа. Поэтому в практической реализации на каждом шаге рекурсивного деления пополам следует контролировать связность полученных подграфов и в случае ее нарушения вводить (а затем удалять) виртуальные дуги.
Заметим, что для вычисления собственных векторов матрицы Лапласа обычно используют итерационный алгоритм Ланцоша.
Продолжим рассмотрение примера, приведенного на рис. 1. Собственные значения матрицы Лапласа для графа, приведенного на этом рисунке, равны (-0.0000, 0.4384, 3.0000, 3.0000, 3.0000, 4.5616), а соответствующие нормализованные собственные векторы - есть столбцы матрицы
Приведенные результаты получены с помощью следующей MATLAB-программы:
L=[2 0 -1 0 -1 0;0 2 0 -1 0 -1;-1 0 3 -1 -1 0;0 -1 -1 3 0 -1;-1 0 -1 0 2 0;0 -1 0 -1 0 2]
[U,lambda]=eig(L)
Таким образом, вектор =(0.4647 -0.4647 0.2610 -0.2610 0.4647 -0.4647)T, как и следовало ожидать, к первому подграфу относятся вершины ,,, а ко второму подграфу – вершины ,, (см. рис. 1).
Приведем краткое обоснование спектрального алгоритма бисекции графа.
Введем в рассмотрение -мерный отображающий вектор =(,,...,)T, компоненты которого могут принимать только значения 1 и . Будем полагать, что ситуация означает, что вершина должна быть включена в первый подграф, а ситуация - вершина должна быть включена во второй подграф. Заметим, что условие формализует условие ().
Легко видеть, что значение функции
 (1)

при заданном отображающем векторе равно количеству разрезанных ребер (количеству ребер, соединяющих первый и второй подграфы между собой). Действительно, величина ничего не вносит в сумму (1), если , имеют один знак (принадлежат одному подграфу). С другой стороны, величина вносит 4 в сумму (1), если имеют разные знаки (принадлежат разным подграфам).
Поскольку а , функция (1) может быть записана в виде

 (2)

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

 (3)

где -мерный единичный вектор. Заметим, что это условие эквивалентно условию .
Нам понадобятся далее некоторые свойства матрицы Лапласа . Пусть - нормализованные собственные векторы матрицы , а - соответствующие собственные значения этой матрицы. Тогда имеет место следующая теорема.
Теорема 1. Матрица Лапласа обладает следующими свойствами: (I) матрица симметрична и вещественна, (II) собственные векторы матрицы попарно ортогональны, (III) первое собственное значение матрицы равно нулю - , а ее первый собственный вектор равен , (IV) все собственные значения матрицы , кроме первого, отличны от нуля
Заметим, что свойство (II) следует из свойства (I).
По свойству (II) матрицы Лапласа вектор X может быть представлен в виде
 (4)

где - некоторые вещественные константы такие, что . Подставляя выражение (4) в формулу (2), получим
 (5)

Обратим внимание на то, что, воспользовавшись разложением (4), мы отказались от требования дискретности компонент вектора .
Поскольку собственные значения матрицы Лапласа упорядочены по убыванию, из (5) следует, что

Отсюда вытекает, что достичь значения ()= можно, положив . Важно, что так найденный вектор удовлетворяет ограничению . Действительно, поскольку (см. свойство (III)), ==0 (по свойству II).
Таким образом, решение удовлетворяет ограничению и минимизирует функцию (), т.е. является непрерывным решением задачи (2), (4).
Теперь остается только перейти к дискретному решению задачи (2), (4) – см. Утверждение 1.