Most early breakthroughs in graph representation learning followed a simple intuition: nodes that are close to each other in a network should have similar vector representations. By using local random walks or immediate neighborhood aggregations, models like DeepWalk or GCNs successfully captured the "microscopic" structure of graphs. However, as Marinka Zitnik and Jure Leskovec point out in To Embed or Not: Network Embedding as a Paradigm in Computational Biology, this local focus often comes at the cost of the "big picture."
When we only look at immediate neighbors, we lose the global topological features—the community structures, long-range dependencies, and overarching density—that define a network's true character.
The Locality Bias Problem
Traditional embedding methods rely on local proximity. If node A is connected to node B, their embeddings are pushed together. While effective for link prediction, this approach struggles with global consistency. For example, two nodes might play identical roles in two different communities but never appear in the same random walk. A purely local model would fail to recognize their structural similarity.
Furthermore, Fan-Yun Sun and Jian Tang argue in vGraph: A Generative Model for Joint Community Detection and Node Representation Learning that local edges are often noisy or sparse. Without a global structural context, models overfit to these local irregularities, failing to capture the broader organizational patterns of the graph.
Bridging the Gap with Community Embeddings
One way to inject global context is to treat communities not just as outputs of a model, but as fundamental components of the embedding process. Instead of just embedding nodes, researchers like Vincent W. Zheng have proposed embedding entire communities as distributions.
In the ComE framework (From Node Embedding To Community Embedding), node embeddings, community detection, and community embeddings are optimized in a closed loop. This ensures that a node's representation is informed by the "global" cluster it belongs to, rather than just its immediate neighbors. Similarly, Wei Shi introduced ComVAE (Network Embedding via Community Based Variational Autoencoder), which uses Variational Autoencoders to ensure that node representations reflect the broader organizational clusters of the network.
Global Prototypes and Mutual Information
Another powerful intuition for capturing global structure is the use of global prototypes. In Bipartite Graph Embedding via Mutual Information Maximization, Xixun Lin and Shu Guo describe a method called BiGI.
The core idea is to maximize the mutual information between a local subgraph and a global prototype of the entire graph. By forcing the local representation to "know" something about the global state, the model preserves long-range dependencies and community-level distributions that traditional local-reconstruction methods miss.
Spectral and Functional Perspectives
To truly capture the "shape" of a graph, some researchers move away from discrete adjacency entirely. Giannis Nikolentzos and Michalis Vazirgiannis suggest representing graphs as "bags-of-vectors" derived from spectral embeddings. In Matching Node Embeddings for Graph Similarity, they use the Earth Mover's Distance to compare these global signatures, allowing for graph comparison based on global topology rather than just shared local substructures like cycles or paths.
Taking this a step further, Hongteng Xu and Dixin Luo introduced the Graphon Autoencoder (GNAE) (Learning Graphon Autoencoders for Generative Graph Modeling). By representing graphs as continuous functions (graphons) in a shared functional space, they can capture the overarching topology of a network regardless of its size, enabling models to transfer knowledge from one social network to another.
Hierarchical and Mesoscopic Structures
Finally, the transition from local to global isn't always binary. There is a "mesoscopic" middle ground—the community level. He Yu and Jing Liu address this in Two Layer Walk: A Community-Aware Graph Embedding. By separating random walks into intra-community and inter-community layers, their TLWalk algorithm explicitly models the hierarchical relationship between a node's local neighborhood and its broader functional group.
This hierarchical approach is echoed in the work of Lunwen Wang, who uses the HARP framework (Link Prediction Algorithms for Social Networks Based on Machine Learning and HARP) to recursively coalesce nodes into super-nodes. This creates a "topological skeleton" of the graph, allowing the model to learn long-range dependencies before refining the embeddings at the local level.
Summary
The shift in graph representation learning is clear: while local connectivity provides the building blocks, global context provides the blueprint. Whether through community distributions, mutual information with global prototypes, or spectral functional representations, the goal is to ensure that every node "knows" its place within the entire network's architecture.