Network representation learning based on social similarities

Ziwei Mo, Zhenzhen Xie, Xilian Zhang, Qi Luo, Yanwei Zheng, Dongxiao YuFrontiers in Environmental Science 2022 · DOI

Abstract

Analysis of large-scale networks generally requires mapping high-dimensional network data to a low-dimensional space. We investigate a novel social similarity-based method, Truss2vec, for learning network representations. By introducing neighborhood structural features based on higher-order $k$-truss parameters and employing similarity-biased random walks, our model maintains both structural and domain similarity. Extensive experiments demonstrate that Truss2vec outperforms state-of-the-art solutions like Node2vec and DeepWalk.

Introduction

In network analysis, representation learning aims to transform complex, high-dimensional graphs into low-dimensional vectors (embeddings) suitable for machine learning tasks. A significant challenge in existing methods is balancing two distinct types of similarity: community proximity (nodes physically close in the graph) and structural similarity (nodes performing similar functional roles, regardless of distance). Traditional metrics, such as node degree, often fail to capture the nuanced "social strength" of connections. Truss2vec addresses this by leveraging higher-order structural features to define node identities more accurately.

Methodology: The Truss2vec Framework

Truss2vec operates through a multi-stage process designed to bridge the gap between proximity and role-based similarity.

1. Structural Identity Extraction

The core of the approach lies in the use of the $k$-truss. A $k$-truss is defined as a subgraph where every edge is part of at least $k-2$ triangles. This metric serves as a proxy for the cohesiveness and social strength of a connection.

Example of a k-truss subgraph, illustrating the structural cohesiveness required for higher-order connectivity.

Each node is assigned a structural vector based on the distribution of truss numbers within its $h$-hop neighborhood. An attenuation factor ($\delta$) is applied to prioritize immediate connections, ensuring the local structural context is preserved.

2. Similarity-Biased Random Walks

Unlike standard random walks (DeepWalk) or those balancing local and global search (Node2vec), Truss2vec employs a similarity-biased random walk. The transition probability between nodes is proportional to the Euclidean distance of their structural vectors. This bias ensures that the walk stays within regions of similar structural roles.

3. Optimization

The generated walks are processed using a Skip-gram model to produce final node embeddings, effectively mapping structural similarities into the vector space.

Experimental Evaluation

The model was evaluated on several real-world datasets, including flight networks (Brazil, Europe, USA) and Wikipedia communication networks.

Key Results

Truss2vec was compared against baseline models including LINE, DeepWalk, and Node2vec using Macro-F1 and Micro-F1 scores.

  • Performance: Truss2vec consistently outperformed baselines across most datasets. It showed particular strength in sparse networks, such as flight datasets, where structural roles are more informative than raw connectivity.
  • Clustering Clarity: Visualization using t-SNE confirmed that Truss2vec produces distinct clusters corresponding to node labels.
t-SNE visualization of node embeddings for the USA flight network, demonstrating the model's ability to form clear, label-consistent clusters.

Sensitivity analysis revealed that an attenuation factor ($\delta$) between 0.5 and 0.6 is optimal, indicating that while neighborhood structure defines identity, the influence of distant nodes diminishes rapidly.

Conclusion and Future Work

Truss2vec provides a robust framework for network representation by integrating higher-order structural features. While the model excels in static network analysis, future work is required to address the computational complexity of $k$-truss decomposition on billion-edge graphs and to extend the framework to dynamic, time-varying networks. Exploration of other cohesive subgraph indicators may further refine the accuracy of node identity representation.

Summary updated

Abstract

Analysis of large-scale networks generally requires mapping high-dimensional network data to a low-dimensional space. We thus need to represent the node and connections accurate and effectively, and representation learning could be a promising method. In this paper, we investigate a novel social similarity-based method for learning network representations. We first introduce neighborhood structural features for representing node identities based on higher-order structural parameters. Then the node representations are learned by a random walk approach that based on the structural features. Our proposed truss2vec is able to maintain both structural similarity of nodes and domain similarity. Extensive experiments have shown that our model outperforms the state-of-the-art solutions.
BibTeX
@inproceedings{mo2022network,
  author = {Ziwei Mo and Zhenzhen Xie and Xilian Zhang and Qi Luo and Yanwei Zheng and Dongxiao Yu},
  title = {{Network representation learning based on social similarities}},
  booktitle = {Frontiers in Environmental Science},
  year = {2022},
  doi = {10.3389/fenvs.2022.974246},
}
Figure