A Survey on Network Embedding

Challenges of Traditional Representation

• Large networks represented as graphs face high computational complexity because many analysis algorithms require iterative or combinatorial operations over explicit edges.Shortest-path computation may require enumerating many possible paths between nodes.Source: §1 · p. 1
• Explicit edge coupling makes traditional network representations difficult to parallelize and distribute, increasing communication costs across servers.The achievable speed-up depends on the topological characteristics of the underlying graphs.Source: §1 · p. 1
• Traditional network representations are poorly suited to standard machine-learning methods because nodes are dependent rather than independent vectors, while adjacency rows are extremely high-dimensional.This high dimensionality makes subsequent network processing and analysis difficult in large graphs.Source: §1 · pp. 1–2

Network Embedding

• Network embedding learns low-dimensional vectors that encode topological and structural characteristics while replacing explicit relationships with distances in vector space.The karate club network illustrates this transformation through a two-dimensional embedding.Source: §1 · p. 2, Figure 1 · p. 2

Goals of Network Embedding

• Network embedding aims both to reconstruct the original network and to support inference tasks such as link prediction, important-node identification, and node-label inference.Reconstruction alone can overfit observed links and fail to infer unseen links, as illustrated by SVD-based embeddings.Source: §1 · p. 2

Survey Scope

• The survey reviews state-of-the-art network embedding methods, organizes their preserved information, evaluates application scenarios, and identifies future research directions.Its coverage includes structure and property preservation, side information, advanced information preservation, datasets, and codes.Source: §1 · p. 2

Categorization

• Network embedding methods are categorized into structure and property preserving methods, methods using side information, and advanced information preserving methods.The categorization is based on the types of information preserved in the embedding.Source: §2 · p. 3
• Traditional graph embedding mainly emphasizes network reconstruction, whereas this survey focuses on recent network embedding methods designed to support network inference.The categorization structure is presented as an overview of the related works.Source: The Categorization of Network… · p. 3

Information Preserved

• Network structures and properties provide foundational information for inference, while side information and advanced task information can further characterize relationships and target applications.Examples of side information include node content, labels, attributes, and node types.Source: The Categorization of Network… · p. 3, Advanced Information Preserving… · p. 4

Advanced Information Preserving Network Embedding

• Advanced information preserving methods use supervised or pseudo-supervised signals to optimize representations toward particular target problems, including node classification with labels.An end-to-end design can use network structure as input, labels as supervision, and embeddings as a latent layer.Source: Advanced Information Preserving… · p. 4

Common Models

• Matrix factorization, random walks, and deep neural networks are common model families, and their combinations can produce new network embedding solutions.Matrix factorization learns low-rank spaces, random walks identify neighborhoods through co-occurrence, and neural models provide nonlinear mappings.Source: Commonly Used Models in Network… · p. 4, Matrix Factorization · p. 4, Random Walk · pp. 4–5
• Random-walk methods borrow the Word2Vector analogy by treating nodes as words, paths as sentences, and co-occurring nodes as neighborhoods.DeepWalk and Node2Vec are representative methods in this family.Source: Random Walk · pp. 4–5

• Graph embedding maps a graph into a low-dimensional vector space and has a substantial classical literature.Source: §3 · p. 5

Classical graph embedding methods

• Isomap constructs a neighborhood graph, computes graph shortest-path distances, and applies multidimensional scaling to obtain representations that approximately preserve geodesic distances.Its key limitation is the high complexity of computing pairwise shortest paths.Source: Representative Graph Embedding Methods · p. 5
• LLE reconstructs each entry from its neighbors and optimizes a low-dimensional mapping that preserves neighborhood structure.Source: Representative Graph Embedding Methods · p. 5
• Laplacian eigenmaps construct a neighborhood graph, weight its edges with a heat kernel, and obtain node representations by minimizing a Laplacian objective under a nontriviality constraint.The reviewed graph embedding literature extends these methods by considering different characteristics of constructed graphs.Source: Representative Graph Embedding Methods · p. 5

Network embedding versus graph embedding

• Unlike graph embedding, network embedding targets both network reconstruction and network inference, generally operates on naturally formed networks, and defines node proximity according to the analytic task.The survey therefore focuses mainly on network embedding methods designed to support network inference.Source: Major Differences · p. 6

Network structures

• Network structures include neighborhood structure, high-order node proximity, and community structure.Source: Structure Preserving Network Embedding · p. 6

Neighborhood Structures and High-order Node Proximity

• DeepWalk preserves neighbor structures through short random walks and Skip-Gram representations.Source: Neighborhood Structures and High-order… · p. 6
• Node2vec uses second-order random walks to interpolate between breadth-first and depth-first neighborhood sampling.Source: Neighborhood Structures and High-order… · p. 6
• LINE preserves first- and second-order proximities, while GraRep additionally captures k-step proximities for global node representations.Source: Neighborhood Structures and High-order… · p. 7

Deep and property-preserving methods

• SDNE combines a deep autoencoder with first- and second-order proximity objectives, emphasizing reconstruction errors on observed edges.Source: Network Communities · p. 7

Summary

• Most methods preserve high-order structure, whereas property-preserving methods remain lightly studied because embedding and network spaces differ heterogeneously at the property level.Source: Property Preserving Network Embedding · p. 8, Summary · p. 9

Overview

• Side information comprises node content and node or edge types, complementing network structure in embedding.Source: §5 · p. 9, Network Embedding with Node Content · p. 9

Node content and labels

• MMDW incorporates node labels into DeepWalk-derived matrix factorization while jointly optimizing an SVM max-margin classifier.Source: Network Embedding with Node Content · p. 9
• Document-network models jointly represent network structure and topic-space information associated with document nodes.Source: Network Embedding with Node Content · p. 9
• TADW incorporates text through matrix factorization, but its high computational cost and unordered attribute features lose semantic information.Source: Network Embedding with Node Content · pp. 9–10
• Some models jointly enhance representations with network structure, node content, and node labels, while LANE combines their affinity matrices spectrally.Source: Network Embedding with Node Content · p. 10

Heterogeneous networks

• Heterogeneous-network methods map different node types into common spaces or preserve typed relations using classification, smoothness, deep embedding, or meta-path proximity.Source: Heterogeneous Information Network… · pp. 10–11

Overview

• Advanced information is supervised or pseudo-supervised information tied to a specific analytic task.Source: §6 · p. 11

Information diffusion

• Diffusion-prediction embeddings model observed cascades as heat diffusion and learn latent positions whose kernels explain infection timing.Source: Information Diffusion · p. 12

Cascade prediction

• DeepCas predicts cascade-size increments end to end by sampling paths from cascade graphs instead of using hand-crafted cascade and network features.Source: Information Diffusion · p. 12

Anomaly detection

• Anomaly-detection embeddings encode node-community correlations and identify nodes connecting to diverse communities through learned anomalousness measures.Source: Anomaly Detection · p. 12

Network alignment

• Network-alignment methods densify paired networks, preserve their structures, and learn linear or nonlinear mappings consistent with observed anchor links.Source: Network Alignment · pp. 12–13

Summary

• These methods generally preserve network structure while connecting node representations to target tasks through domain-specific information.Source: Summary · p. 13

Real-world network datasets

• Network embedding evaluations commonly use social, citation, language, and biological networks.The survey organizes real-world datasets into four groups according to network nature.Source: Real World Data Sets · p. 14

Social networks

• BlogCatalog, Flickr, YouTube, and Twitter provide examples of social-network datasets based on online user relationships or contacts.The listed datasets represent blogger relationships, photo-sharing contacts, video-sharing users, and Twitter users.Source: Social Networks · p. 14

Citation networks

• DBLP, Cora, and Citeseer provide citation-network datasets involving authors, papers, or scientific publications.Cora additionally associates publications with word-presence vectors.Source: Citation Networks · p. 14

Language and collaboration networks

• ArXiv is described as a collaboration network, while Wikipedia is described as a word-cooccurrence network.These datasets represent language or information derived from online sources.Source: Citation Networks · p. 14, Language Networks · p. 14

Biological networks

• PPI represents pairwise physical interactions between proteins in yeast.It is presented as a biological-network dataset.Source: Biological Networks · p. 14

Node Classification

• Node classification classifies unlabeled nodes using a network embedding learned from the network and known node labels.The described procedure first embeds the network, then uses labeled nodes to classify the remaining nodes.Source: Node Classification · p. 14

Evaluation metrics

• Micro-F1 and Macro-F1 are commonly used metrics for evaluating multi-label node classification.Macro-F1 is defined from per-label F1 values, while Micro-F1 aggregates true positives, false positives, and false negatives across labels.Source: Node Classification · p. 14

Evaluation settings

• Multi-label classification has been tested on social, citation, language, and biological datasets.Examples include BlogCatalog, Flickr, YouTube, DBLP, Cora, Citeseer, Wikipedia, and PPI.Source: Node Classification · pp. 14–15
• DeepWalk, GraRep, SDNE, node2vec, and LANE evaluate node classification on social-network datasets including BlogCatalog and Flickr.The cited studies use these embedding methods to assess classification performance on social networks.Source: Node Classification · p. 15

Conclusion

• Network embedding methods have been widely applied across networks and demonstrated effectiveness for node classification.This is the survey’s summary conclusion for the task.Source: Node Classification · p. 15

Link Prediction

• Link prediction estimates the likelihood of an edge between two nodes from observed network structure.It is presented as a fundamental network-analysis problem.Source: Link Prediction · p. 15

Embedding-based scoring

• Node embeddings support link prediction by enabling node similarity estimates through inner products or cosine similarity.Higher similarity indicates a higher propensity for the two nodes to be linked.Source: Link Prediction · p. 15

Evaluation metrics

• Precision@k and Mean Average Precision are commonly used to evaluate link prediction performance.The accompanying notation defines ranked nodes and observed edges for precision@k.Source: Link Prediction · p. 15

Evaluation settings

• Link prediction evaluations use citation, social, and biological networks, including ArXiv, DBLP, Twitter, Facebook, Epinions, Slashdot, and PPI.The cited studies apply different embedding methods across these network categories.Source: Link Prediction · pp. 15–16

Conclusion

• Extensive experiments demonstrate that network embedding can tackle link prediction effectively across various networks.The survey attributes this suitability to embedding methods’ ability to capture inherent network structures.Source: Link Prediction · p. 16

Node Clustering

• Node clustering groups nodes so that nodes within a cluster are more similar than nodes in different clusters.Network embeddings provide low-dimensional representations on which methods such as Kmeans can operate directly.Source: Node Clustering · p. 16

Evaluation metrics

• Accuracy and normalized mutual information are frequently used to evaluate clustering performance on graphs and networks.Accuracy measures the percentage of correctly assigned labels, while NMI uses mutual information between clusterings.Source: Node Clustering · p. 16

Evaluation settings

• Node clustering evaluations use social, citation, and document networks, including Facebook, YELP, DBLP, and 20-NewsGroup.The survey also describes a social-blogging network constructed from TF-IDF features and following behaviors.Source: Node Clustering · p. 16

Conclusion

• Network embedding has become an effective method for solving node clustering problems across different network types.The conclusion follows the survey’s reported testing of embedding-based clustering on multiple networks.Source: Node Clustering · p. 16

• Network embedding generates meaningful two-dimensional layouts that make sophisticated network structure easier to inspect.Applying visualization tools such as t-SNE to learned node representations helps users see a network's overall structure.Source: Network Visualization · p. 16
• In SDNE visualizations, documents appear as points whose colors encode their labels.Source: Network Visualization · p. 16
• Similar nodes are positioned closer than dissimilar nodes, preserving intrinsic network structure in the low-dimensional visualization.Source: Network Visualization · p. 17

• Table 2 collects links to source code for various network embedding methods.Source: Open Source Software · p. 17

Conclusions and framework

• Structure- and property-preserving embedding is foundational because information loss in the embedding space can harm subsequent analytic tasks.The framework then supports machine learning, side-information integration, and incorporation of advanced domain knowledge.Source: §8 · p. 17

More Structures and Properties

• Existing methods do not fully account for some real-world structures, including network motifs, complex local structures, and hyperedges.The survey specifically identifies hypernetwork embedding as important for some real applications.Source: More Structures and Properties · p. 17
• How power-law degree distributions affect embedding performance and how to improve representations for minority nodes remain largely unexplored.Source: More Structures and Properties · p. 17

The Effect of Side Information

• The assumption that network structure and side information agree may not hold in real applications, while the two information sources may be complementary.Low correlation between them may degrade embedding performance.Source: The Effect of Side Information · p. 17

More Advanced Information and Tasks

• Meta structures offer a higher-order constraint beyond meta paths and suggest a direction for heterogeneous information network embedding.Source: The Effect of Side Information · p. 17
• Future work should design embeddings for specific applications by integrating their distinctive domain knowledge as advanced information.The survey mentions rumor detection and social-tie inference as example targets.Source: More Advanced Information and Tasks · p. 18

Dynamic Network Embedding

• Most existing methods target static networks, so evolving networks require approaches that avoid repeatedly rerunning embeddings at each timestamp.Repeated execution is time-consuming and may not meet real-time processing demands.Source: Dynamic Network Embedding · p. 18

More Embedding Spaces

• Exploring non-Euclidean target spaces, including hyperbolic space, is another research direction for network embedding.Hyperbolic assumptions can naturally reflect heterogeneous degree distributions and strong clustering.Source: More embedding spaces · p. 18