Two Layer Walk: A Community-Aware Graph Embedding

He Yu, Jing Liu · 2024

Read Two Layer Walk: A Community-Aware Graph Embedding by He Yu, Jing Liu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-12933.txt.

Introduction

He Yu and Jing Liu tackle a blind spot in 2024 in how computers map networks into numbers. Mapping methods learn a spot for each node by mimicking random walks, which captures local ties well. What they miss is community structure, the clusters that tie the local view to the whole. Older fixes for that gap cost too much compute for big networks.

Their method, TLWalk, walks with community awareness built in, balancing steps inside a cluster against steps between clusters, with no extra settings to tune. Theory shows it cuts a known local bias, they report. On standard test networks it beat leading methods, gaining up to 3.2 percent on link guessing. Dense local ties and sparse global ones both survive the mapping, which suits very large graphs.

Catalog record

CREATORHe Yu, Jing Liu
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-12933

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Two Layer Walk: A Community-Aware Graph Embedding He Yu, Jing Liu Abstract Community structures play a pivotal role in understanding the mesoscopic organization of networks, bridging local and global patterns. While methods like DeepWalk and node2vec effectively capture node positional and local structural information through random walks, they fail to incorporate critical community information. Other approaches, such as modularized nonnegative matrix factorization and evolutionary algorithm-based methods, preserve community structures but suffer from high computational complexity, making them unsuitable for large-scale networks. To address these limitations, we propose Two Layer Walk (TLWalk), a novel graph embedding algorithm that explicitly incorporates hierarchical community structures. By balancing intra- and inter-community relationships through a community-aware random walk mechanism automatically without using any parameters, TLWalk achieves robust and scalable representation learning that can fully extract local and global topologies, which is proved theoretically by showing TLWalk can overcome locality bias in the walk. We also theoretically prove the relationship between TLWalk and matrix factorization. Extensive experiments on benchmark datasets demonstrate TLWalk’s superior performance, with significant accuracy gains—up to 3.2%—over existing methods for the link prediction task. TLWalk’s ability to encode both dense local and sparse global structures ensures its adaptability across diverse network types, offering a powerful and efficient solution for network analysis. Introduction Graphs are ubiquitous in representing complex systems across diverse domains, from social networks [ 1 ] and biological systems [ 2 ] to transportation [ 3 ] and recommendation systems [ 4 ] . These structures, consisting of nodes and edges, capture relationships and interactions within the system. Analyzing these graphs is crucial for tasks like link prediction, node classification, and uncovering hidden structures. Graph embedding provides a powerful solution by mapping graphs into low-dimensional vector spaces while preserving their essential properties [ 5 , 6 , 7 , 8 , 9 ] . These embeddings encode positional relationships, structural roles, and patterns, facilitating efficient downstream tasks. Positional information reflects how nodes are situated, while structural roles highlight patterns and topological features. A wide range of embedding methods has been developed, broadly categorized into shallow and deep learning-based approaches. Shallow methods, such as DeepWalk [ 5 ] , node2vec [ 6 ] , and matrix factorization [ 10 ] , efficiently capture local and global patterns through strategies like random walks or linear decomposition. Deep learning approaches, such as Graph Neural Networks (GNNs) [ 11 ] and Graph Attention Networks (GATs) [ 12 ] , address non-linear dependencies but face challenges like over-smoothing, high computational demands, and sensitivity to hyperparameters. Communities, residing at the mesoscopic level, bridge microscopic node-level and macroscopic graph-level structures [ 13 , 14 , 15 , 16 , 17 ] . By identifying densely connected groups of nodes, communities provide a unique lens for understanding intermediate network organization. Incorporating community information into embeddings enhances their capacity to encode local and global patterns, making them vital for nuanced network analysis. Despite these advancements, effectively incorporating community structure into graph embeddings remains a critical challenge. Early community-preserving embedding methods, such as modularized nonnegative matrix factorization (M-NMF) [ 18 ] and evolutionary algorithm (EA)-based approaches [ 19 , 20 ] , have demonstrated the value of integrating community information. However, M-NMF suffers from high computational complexity due to iterative matrix decomposition and lacks support for incremental learning, making it unsuitable for large-scale or dynamic networks. Similarly, EA-based methods, such as EA-NECommunity [ 19 ] , while capable of preserving both local proximity and community structures, are computationally intensive. These limitations highlight the need for scalable, dynamic, and community-aware embedding methods that strike a balance between computational efficiency and representational richness. The random walk mechanism used in DeepWalk and node2vec is simple yet powerful for extracting local structural and positional information in graphs. Their inherent flexibility allows for incremental updates and scalability to large graphs. Traditional methods often mix local and global walks, resulting in a loss of critical mesoscopic information and an inability to fully leverage community structures. In contrast, we propose Two Layer Walk (TLWalk), a novel graph embedding algorithm designed to overcome the limitations of existing approaches in capturing community structures. TLWalk introduces a hierarchical two-layer design that separates the network into an intra-community layer and an inter-community layer. By independently conducting walks within each layer, TLWalk effectively extracts dense local structures from communities while capturing sparse global relationships across communities. This design allows TLWalk to preserve the nuanced interplay between local and global structures while ensuring communication between layers through “bridging” nodes—key connectors that link communities. This separation and targeted exploration enable TLWalk to achieve a more precise and comprehensive embedding of network structures, addressing gaps left by existing methods. Figure 1 illustrates this hierarchical organization using the Zachary’s Karate Club network [ 21 ] . This study rigorously evaluates TLWalk through experiments on benchmark datasets spanning social, biological, and ecological domains. The results consistently demonstrate TLWalk’s superior performance in tasks such as link prediction, node classification, and clustering, outperforming state-of-the-art methods while maintaining computational efficiency. Our key contributions are as follows: 1. We propose a graph embedding algorithm that explicitly incorporates community structures into random walk-based methods without using any parameters, effectively bridging local and global perspectives in network analysis. 2. We theoretically prove the proposed TKWalk can overcome locality bias, thus, can fully extract both local and global topologies. We also theoretically prove the relationship between TLWalk and matrix factorization. 3. We validate the versatility of TLWalk, demonstrating significant performance improvements across key tasks, including link prediction, node classification, and clustering. By addressing critical challenges in graph embedding, this study not only enhances predictive performance but also advances the theoretical and practical development of community-aware embedding algorithms. Leveraging random walk-based methods to effectively extract community structures, TLWalk strikes a balance between computational efficiency and representational richness, establishing itself as a powerful tool for diverse real-world network analysis tasks. Figure 1: Illustration of the hierarchical organization in the Zachary’s Karate Club network. The intra-community level (colored groups) captures dense connections within communities, while the inter-community level (pink edges) highlights sparser connections linking different communities. This structure forms the basis for TLWalk’s two-layer embedding approach. Methods Preliminaries A graph is represented as G=(V,E) , where V is the set of nodes, and E is the set of edges connecting pairs of nodes. For an undirected graph, (u,v)\in E implies (v,u)\in E . The adjacency matrix of G is denoted by A\in\{0,1\}^{|V|\times|V|} , where A[u,v]=1 if (u,v)\in E , and A[u,v]=0 otherwise. The degree of a node v , denoted by d(v) , is the number of edges incident to v : d(v)=\sum_{u\in V}A[v,u]. (1) A community in a graph refers to a subset of nodes that are densely connected internally but sparsely connected to nodes outside the subset. A community partition of G is denoted by \mathcal{C}=\{C_{1},C_{2},\ldots,C_{k}\} , where C_{i}\subseteq V , i=1,2,...,k and \bigcup_{i=1}^{k}C_{i}=V . The quality of a community partition can be evaluated using modularity Q [ 13 ] , which is defined as: Q=\frac{1}{2|E|}\sum_{u,v\in V}\left[A[u,v]-\frac{d(u)d(v)}{2|E|}\right]\delta(C_{u},C_{v}), (2) where \delta(C_{u},C_{v}) is 1 if nodes u and v belong to the same community and 0 otherwise. Word2Vec [ 22 ] is a widely used model for learning vector representations of words based on their contextual relationships. In

Read the complete text