Подход 3, комбинированный. Цель - учесть как и локальные фичи, так и положение в графе. Во-первых, заставим нейросетку из предыдущего подхода принимать на вход не только графовые эмбеддинги вершин "контекста", но и их "обычные" фичи из подхода 0. Во-вторых, заставим её на выходе предсказывать не только порядковый номер целевой вершины, но и её собственные локальные фичи. Ну а эмбеддинг, как и раньше, будем брать откуда-то из середины этой нейросети. Тут можно смело применять предобработку из NLP - например, фичи некоторых из вершин заменять на случайно выбранные или на специальную вершину [MASK], чтобы их эмбеддинги не могли смотреть сами на себя, и вынуждены были опираться на контекст. Собственно, и архитектуру сети можно взять из NLP, обучая transformer на небольших окрестностях, надёрганных из графа, и ограничивая attention всех или некоторых из его голов в соответствии с наличием рёбер или каких-то путей между парами вершин.

Все эти подходы я породил преимущественно из собственного воображения и из довольно беглого знакомства с материалами в сети. Но вообще-то графовые эмбеддинги - это тема обширная, едва ли не безграничная. Если хочется залезть поглубже, рекомендую почитать обзоры графовых эмбеддингов, например, этот: https://arxiv.org/abs/2012.08019. А ещё есть чудесный пост про связь между трансформерами и графовыми нейросетками: https://towardsdatascience.com/bca9f75412aa (картинку я стырил как раз оттуда).