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