ça dépend du graphe. C'est souvent des matrices creuses mais avec les transformers ou les CNN on s'en sort. Il y a des librairies qui parallélisent ces algorithmes sur des GPU (comme torch geometric par exemple). La quantité de données dépend de la taille du graphe, et de la tâche à accomplir.