Я бы подумал об использовании SQL Server Compact (внутрипроцессная база данных от Microsoft), а не о сериализации большого графа объектов.
У меня был опыт сериализации большого графика на диск с использованием BinaryFormatter.Были проблемы, связанные с контролем версий.Сериализованные объекты сложно поддерживать и работать с ними тоже.И работа с такими объектами обычно требует десериализации в память.Это ресурсоемкий способ работы с большим графом.
А Sql Server CE довольно легкий, его сборка составляет около 1 Мб.Он также решает некоторые проблемы с многопоточностью.
Если вам нужно сериализовать только для отправки по сети или что-то еще, я полагаю, что 60 МБ - это довольно большой массив, могут возникнуть проблемы с его передачей.
Обновление
Если вы хотите использовать BinaryFormatter, я предполагаю, что вы можете сериализовать свой график не как один корневой объект, а как набор более мелких объектов.Возможно, будет медленнее сериализовать все объекты, но это позволит вам сериализовать только некоторую часть объектов.Если у вас есть гетерогенный массив (то есть последовательность объектов разных типов), я могу предположить, что чем сложнее объект и чем глубже его иерархия, тем больше времени требуется для его сериализации.Вы можете измерить время сериализации для коллекции объектов одного типа.Вы также можете использовать некоторые профилировщики для сериализации всего графа, большинство профилировщиков показывают, какой метод занимает больше времени.