On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications

Abstract

Structural roles define sets of structurally similar nodes that are more similar to nodes inside the set than outside, whereas communities define sets of nodes with more connections inside the set than outside. Roles based on structural similarity and communities based on proximity are fundamentally different but important complementary notions. Recently, the notion of structural roles has become increasingly important and has gained a lot of attention due to the proliferation of work on learning representations (node/edge embeddings) from graphs that preserve the notion of roles. Unfortunately, recent work has sometimes confused the notion of structural roles and communities (based on proximity) leading to misleading or incorrect claims about the capabilities of network embedding methods. As such, this paper seeks to clarify the misconceptions and key differences between structural roles and communities, and formalize the general mechanisms (e.g., random walks, feature diffusion) that give rise to community or role-based structural embeddings. We theoretically prove that embedding methods based on these mechanisms result in either community or role-based structural embeddings. These mechanisms are typically easy to identify and can help researchers quickly determine whether a method preserves community or role-based embeddings. Furthermore, they also serve as a basis for developing new and improved methods for community or role-based structural embeddings. Finally, we analyze and discuss applications and data characteristics where community or role-based embeddings are most appropriate.

References in corpus (36)

• Finding and evaluating community structure in networks
• Community detection in graphs
• A Comprehensive Survey on Graph Neural Networks
• DeepWalk: Online Learning of Social Representations
• Fast algorithm for detecting community structure in networks
• LINE: Large-scale Information Network Embedding
• Near linear time algorithm to detect community structures in large-scale networks
• Graph Embedding Techniques, Applications, and Performance: A Survey
• Biological network comparison using graphlet degree distribution
• Hierarchical Graph Representation Learning with Differentiable Pooling
• Mixed membership stochastic blockmodels
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• GNNExplainer: Generating Explanations for Graph Neural Networks
• graph2vec: Learning Distributed Representations of Graphs
• Temporal motifs in time-dependent networks
• Graph Metrics for Temporal Networks
• Hyperbolic Graph Convolutional Neural Networks
• REGAL: Representation Learning-based Graph Alignment
• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale
• Role Discovery in Networks
• subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs
• Supervised Community Detection with Line Graph Neural Networks
• Graph-based Anomaly Detection and Description: A Survey
• Graph Summarization Methods and Applications: A Survey
• Learning Role-based Graph Embeddings
• Network Sampling: From Static to Streaming Graphs
• Network Representation Learning: A Survey
• Higher-order Graph Convolutional Networks
• G2SAT: Learning to Generate SAT Formulas
• Predicting Social Links for New Users across Aligned Heterogeneous Social Networks
• A Framework for Generalizing Graph-based Representation Learning Methods
• HONE: Higher-Order Network Embeddings
• Carina: Interactive Million-Node Graph Visualization using Web Browser Technologies
• Locally computable approximations for spectral clustering and absorption times of random walks
• Feature Propagation on Graph: A New Perspective to Graph Representation Learning
• Latent Network Summarization: Bridging Network Embedding and Summarization

Cited by in corpus (6)

• Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent
• Local, global and scale-dependent node roles
• A Hidden Challenge of Link Prediction: Which Pairs to Check?
• An Efficient Quadratic Penalty Method for a Class of Graph Clustering Problems
• Blind Extraction of Equitable Partitions from Graph Signals
• Temporal Motif Participation Profiles for Analyzing Node Similarity in Temporal Networks