Marc: Multi-Granular Representation Learning for Networks Based on the 3-Clique

Zhenghua Xin, Jie Chen, Guolong Chen, Shu ZhaoIEEE Access 2019 · OpenReview

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."

A detailed view of 3-clique coarsening: the triangle formed by nodes 1, 2, and 3 is collapsed into a single supernode, preserving the connections to external nodes 4 and 5.

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.

The recursive 3-clique coarsening process, where triangles are iteratively collapsed into supernodes to create a hierarchy of graphs.

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

Abstract

Network embedding is of paramount importance in many real applications, such as node classification, network visualization, and link prediction. Existing methods can effectively encode different structural properties into representations. Most of them are single-granular representation learning methods that do not enable the network to be easily analyzed at various scales. There are many kinds of hierarchical structures in reality. In this paper, we propose a novel algorithm multi-granular representation learning for networks based on the 3-clique named Marc. It makes the representations of the current network be formed by both considering the structure of this granular network and inheriting the coarser network representation results. Firstly, we propose the 3-clique coarsening strategy. A 3-clique is coarsened to be a supernode in the coarser network. These coarsened networks with different granularities, preserve the original network's main structure. Secondly, we use the single-granular optimization objective function to obtain the nodes' representations of each granular network. Finally, the refinement model learns the nodes' representations, starting from the coarsest network. The learned representations of supernodes serve as good initializations for embedding the corresponding coarsened nodes from the finer network. This process is repeated until we obtain an embedding for each node in the original network which preserves the relationship among multi-granular networks. The experimental results on five public datasets, Wiki, BlogCatalog, Cora, CiteSeer, and DBLP, demonstrate that Marc has a better Macro F1 value for classification tasks than the baseline methods.
BibTeX
@inproceedings{xin2019marc,
  author = {Zhenghua Xin and Jie Chen and Guolong Chen and Shu Zhao},
  title = {{Marc: Multi-Granular Representation Learning for Networks Based on the 3-Clique}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=BIUpKrDMuV},
}
Figure