TL;DR
Marc is a hierarchical network embedding framework that leverages 3-clique (triangle) structures to coarsen graphs into multiple scales. By learning representations from the coarsest level and refining them down to the original network, it captures global topology and avoids the local minima common in traditional single-scale embedding methods.
Introduction: The Challenge of Scale in Network Embedding
Network embedding—mapping nodes into low-dimensional vectors—is a cornerstone of modern graph analysis, enabling tasks like node classification, visualization, and link prediction. However, most established algorithms, such as DeepWalk or LINE, are "single-granular." They focus primarily on local neighborhoods, often failing to capture the hierarchical or global structures inherent in complex real-world networks.
Furthermore, these methods are prone to getting stuck in poor local optima because they typically start with random initializations on high-dimensional, non-linear search spaces. While hierarchical methods like HARP exist, they often rely on simple edge or "star" collapsing, which can merge unrelated nodes and distort the network's global topology.
The Marc Framework
To address these limitations, the authors introduce Marc, a multi-granular framework that operates in three distinct phases: coarsening, embedding, and refinement.
1. 3-Clique Coarsening
The core innovation of Marc is its coarsening strategy based on the 3-clique (triangle). In real-world networks, the 3-clique is a fundamental unit of cohesion. Based on the principle of homophily—where connected nodes are likely to be similar—Marc identifies these triangles and merges them into single "supernodes."
This process is repeated to create a series of increasingly smaller, coarser versions of the original graph. This geometric reduction preserves the "solid triangle patterns" that define communities, ensuring the global structure remains intact even at high levels of compression.
2. Coarsest Level Embedding
The algorithm begins by embedding the smallest, most compressed version of the network. Because the graph is small and the "noise" of local edges is reduced, standard optimization functions can more easily capture the global structure without being distracted by local fluctuations.
3. Recursive Refinement
The embeddings from the coarse level serve as the initial state for the next finer level. This "warm start" initialization propagates high-quality structural information down the hierarchy. This process continues until every node in the original network has a representation that reflects both its local neighborhood and its place in the global hierarchy. Crucially, Marc is algorithm-agnostic; it can be used to enhance various existing embedding techniques, such as DeepWalk, LINE, or Node2vec.
Experimental Evaluation
The authors evaluated Marc on five diverse benchmark datasets: Wiki (word co-occurrence), BlogCatalog (social network), Cora and CiteSeer (citation networks), and DBLP (co-author network).
Key Results
Marc consistently outperformed both baseline methods (DeepWalk, LINE, Node2vec) and the previous state-of-the-art hierarchical method (HARP) across all datasets:
- Classification Accuracy: Marc achieved significantly higher Macro $F_1$ scores. For example, on the Wiki dataset, Marc improved the Macro $F_1$ of DeepWalk from approximately 13% to over 27%.
- Significant Gains: The authors reported improvements as large as 15.03% over existing methods in multi-label classification tasks.
- Robustness: Performance gains remained consistent even with very small portions of labeled training data (as low as 1%), suggesting that Marc learns more meaningful and robust structural features.
Conclusion and Future Directions
By solving the "big picture" first on a coarse graph, Marc provides a superior starting point for fine-grained learning, effectively breaking away from local minima. While Marc shows strong performance on homogeneous networks, future work could extend this logic to heterogeneous networks with multiple node and edge types. Additionally, integrating Marc with deep learning architectures like Graph Convolutional Networks (GCN) could further enhance its representational power.
Summary updated