L2G2G: a Scalable Local-to-Global Network Embedding with Graph Autoencoders
This addresses scalability issues in graph representation learning for real-world network analysis, offering an incremental improvement over existing Local2Global methods.
The paper tackles the scalability problem of graph autoencoders (GAEs) for network analysis by proposing L2G2G, a Local2Global method that dynamically synchronizes latent node representations during training, achieving higher accuracy than standard Local2Global approaches and even outperforming slower GAEs on large, dense networks while maintaining scalability.
For analysing real-world networks, graph representation learning is a popular tool. These methods, such as a graph autoencoder (GAE), typically rely on low-dimensional representations, also called embeddings, which are obtained through minimising a loss function; these embeddings are used with a decoder for downstream tasks such as node classification and edge prediction. While GAEs tend to be fairly accurate, they suffer from scalability issues. For improved speed, a Local2Global approach, which combines graph patch embeddings based on eigenvector synchronisation, was shown to be fast and achieve good accuracy. Here we propose L2G2G, a Local2Global method which improves GAE accuracy without sacrificing scalability. This improvement is achieved by dynamically synchronising the latent node representations, while training the GAEs. It also benefits from the decoder computing an only local patch loss. Hence, aligning the local embeddings in each epoch utilises more information from the graph than a single post-training alignment does, while maintaining scalability. We illustrate on synthetic benchmarks, as well as real-world examples, that L2G2G achieves higher accuracy than the standard Local2Global approach and scales efficiently on the larger data sets. We find that for large and dense networks, it even outperforms the slow, but assumed more accurate, GAEs.