DeepWalk: online learning of social representations

DeepWalk shows significantly increased classification performance in the presence of label sparsity, with improvements 5%-10% of Micro F1 on the sparsest problems considered.

“We show significantly increased classification performance in the presence of label sparsity, getting improvements 5%-10% of Micro F 1 , on the sparsest problems we consider.”

DeepWalk outperforms challenging baselines that are allowed a global view of the network, especially in the presence of missing information.

“Our results show that DeepWalk outperforms challenging baselines which are allowed a global view of the network, especially in the presence of missing information.”

DeepWalk outperforms other latent representation methods for creating social dimensions, especially when labeled nodes are scarce.

“DeepWalk outperforms other latent representation methods for creating social dimensions [39, 41], especially when labeled nodes are scarce.”

• cites [39] [39] L. Tang and H. Liu. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , KDD '09, pages 817-826, New York, NY, USA, 2009. ACM. - sourceNot checked yet

  Not checked in the free run.

• cites [41] [41] L. Tang and H. Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery , 23(3):447-478, 2011. - sourceNot checked yet

  Not checked in the free run.

Word frequency in natural language follows a power-law distribution similar to vertex frequency in random walks.

“Word frequency in natural language follows a similar distribution, and techniques from language modeling account for this distributional behavior.”

• Also stated in: § 3.2 Connection: Power laws · p. 3 · plain

  “The first comes from a series of short random walks on a scale-free graph, and the second comes from the text of 100,000 articles from the English Wikipedia.”

Linearly separable portions of the 2D embedding correspond to clusters found through modularity maximization in the input graph.

“Beyond the striking similarity, we note that linearly separable portions of (1b) correspond to clusters found through modularity maximization in the input graph (1a) (shown as vertex colors).”

The frequency with which vertices appear in short random walks on a scale-free graph follows a power-law distribution.

“If the degree distribution of a connected graph follows a power law (is scale-free ), we observe that the frequency which vertices appear in the short random walks will also follow a power-law distribution.”

• AssumptionRests on an assumption: The social networks to which DeepWalk is applied have degree distributions that follow a power law (are scale-free).

Parallelizing DeepWalk shows no loss of predictive performance relative to running DeepWalk serially.

“It also shows that there is no loss of predictive performance relative to the running DeepWalk serially (Figure 4b).”

DeepWalk demonstrates scalability by building representations of web-scale graphs (such as YouTube) using a parallel implementation.

“We demonstrate the scalability of our algorithm by building representations of web-scale graphs, (such as YouTube) using a parallel implementation.”

The learned representation encodes community structure so it can be easily exploited by standard classification methods.

“The learned representation encodes community structure so it can be easily exploited by standard classification methods.”

• Also stated in: § DeepWalk: Online Learning of Social Representations · p. 1 · plain

  “Note the correspondence between community structure in the input graph and the embedding.”

DeepWalk's representations can provide F1 scores up to 10% higher than competing methods when labeled data is sparse.

“DeepWalk 's representations can provide F 1 scores up to 10% higher than competing methods when labeled data is sparse.”

Parallelizing DeepWalk shows consistent speedup in processing BlogCatalog and Flickr networks as workers increase to 8.

“It shows the speed up in processing BlogCatalog and Flickr networks is consistent as we increase the number of workers to 8 (Figure 4a).”

In some experiments, DeepWalk's representations outperform all baseline methods while using 60% less training data.

“In some experiments, DeepWalk 's representations are able to outperform all baseline methods while using 60% less training data.”

• Also stated in: § 1. INTRODUCTION · p. 2 · plain

  “In some cases, DeepWalk 's representations can outperform its competitors even when given 60% less training data.”

Strong performance with DeepWalk's representations is possible with very simple linear classifiers (e.g., logistic regression).

“Strong performance with our representations is possible with very simple linear classifiers (e.g. logistic regression).”

On YouTube, the lead of DeepWalk over EdgeCluster narrows as the training data increases.

“This lead narrows as the training data increases”

On BlogCatalog, DeepWalk outperforms SpectralClustering on MicroF1 when the training ratio is at most 60%.

“DeepWalk still outperforms when labeled data is sparse on both MacroF 1 ( T R ≤ 20%) and MicroF 1 ( T R ≤ 60%).”

On YouTube, DeepWalk ends with a 5% improvement in MacroF1 over EdgeCluster.

“an impressive 5% improvement in MacroF 1”

The relative performance between different dimensions is relatively stable across different values of γ.

“The relative performance between dimensions is relatively stable across different values of γ .”

On YouTube, DeepWalk ends with a 3% lead in MicroF1 over EdgeCluster.

“DeepWalk ends with a 3% lead in MicroF 1”

On Flickr, DeepWalk's MicroF1 performance when only 3% of the graph is labeled beats all other methods even when they have been given 10% of the data.

“Additionally, its MicroF 1 performance when only 3% of the graph is labeled beats all other methods even when they have been given 10% of the data.”

The relative difference between different values of γ is quite consistent between Flickr and BlogCatalog.

“The second is that the relative difference between different values of γ is quite consistent between the two graphs.”

The performance of the DeepWalk model depends on the number of random walks it has seen.

“They also show that the performance of the model depends on the number of random walks it has seen, and the appropriate dimensionality of the model depends on the training examples available.”

On BlogCatalog, when trained with only 20% of the nodes labeled, DeepWalk performs better than EdgeCluster, Modularity, and wvRN when they are given 90% of the data.

“In fact, when trained with only 20% of the nodes labeled, DeepWalk performs better than these approaches when they are given 90% of the data.”

On Flickr, DeepWalk outperforms all baselines by at least 3% with respect to MicroF1.

“DeepWalk outperforms all baselines by at least 3% with respect to MicroF 1 .”

Most of the benefit is accomplished by starting γ = 30 walks per node in both Flickr and BlogCatalog.

“The first is that there is most of the benefit is accomplished by starting γ = 30 walks per node in both graphs.”

On BlogCatalog, DeepWalk outperforms SpectralClustering on MacroF1 when the training ratio is at most 20%.

“DeepWalk still outperforms when labeled data is sparse on both MacroF 1 ( T R ≤ 20%) and MicroF 1 ( T R ≤ 60%).”

On YouTube, DeepWalk's MacroF1 shows a corresponding 10% increase over EdgeCluster.

“The MacroF 1 shows a corresponding 10% increase.”

On BlogCatalog, DeepWalk performs consistently better than EdgeCluster, Modularity, and wvRN.

“DeepWalk performs consistently better than EdgeCluster, Modularity, and wvRN.”

On YouTube, DeepWalk significantly outperforms the scalable baseline EdgeCluster.

“They show that DeepWalk significantly outperforms the scalable baseline for creating graph representations, EdgeCluster.”

The optimal dimensionality for a DeepWalk model depends on the number of training examples available.

“The performance is quite consistent between both Flickr and BlogCatalog and show that the optimal dimensionality for a model is dependent on the number of training examples.”

On YouTube, when 1% of the labeled nodes are used for test, DeepWalk's MicroF1 improves by 14% over EdgeCluster.

“When 1% of the labeled nodes are used for test, the MicroF 1 improves by 14%.”

DeepWalk learns latent representations of vertices in a network by modeling a stream of short random walks.

“We develop an algorithm ( DeepWalk ) that learns social representations of a graph's vertices, by modeling a stream of short random walks.”

• Also stated in: § ABSTRACT · p. 1 · plain

  “DeepWalk uses local information obtained from truncated random walks to learn latent representations by treating walks as the equivalent of sentences.”

Techniques used to model natural language can be re-purposed to model community structure in networks.

“A core contribution of our work is the idea that techniques which have been used to model natural language (where the symbol frequency follows a power law distribution (or Zipf's law )) can be re-purposed to model community structure in networks.”

DeepWalk generalizes neural language models to process a special language composed of randomly-generated walks.

“DeepWalk generalizes neural language models to process a special language composed of a set of randomly-generated walks.”

• Also stated in: § ABSTRACT · p. 1 · plain

  “DeepWalk generalizes recent advancements in language modeling and unsupervised feature learning (or deep learning ) from sequences of words to graphs.”

DeepWalk introduces deep learning as a tool to analyze graphs for the first time.

“In this paper we introduce deep learning (unsupervised feature learning) [2] techniques, which have proven successful in natural language processing, into network analysis for the first time.”

• cites [2] [2] Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. 2013. - sourceNot checked yet

  Not checked in the free run.

The same representation can be used for multiple classification problems concerning that network.

“Moreover, the same representation can be used for multiple classification problems concerning that network.”

The separation between structural representation and labeling task avoids cascading errors that can occur in iterative methods.

“This separation between the structural representation and the labeling task avoids cascading errors, which can occur in iterative methods [33].”

• cites [33] [33] J. Neville and D. Jensen. A bias/variance decomposition for models using collective inference. Machine Learning , 73(1):87-106, 2008. - sourceNot checked yet

  Not checked in the free run.

Hierarchical Softmax reduces the computational complexity of calculating Pr(u_k | Φ(v_j)) from O(|V|) to O(log |V|).

“This reduces the computational complexity of calculating Pr( u k | Φ( v j )) from O ( | V | ) to O (log | V | ).”

The latent representations encode social relations in a continuous vector space with a relatively small number of dimensions.

“These latent representations encode social relations in a continuous vector space with a relatively small number of dimensions.”

• Also stated in: § ABSTRACT · p. 1 · plain

  “These latent representations encode social relations in a continuous vector space, which is easily exploited by statistical models.”

DeepWalk learns structural regularities present within short random walks.

“DeepWalk learns structural regularities present within short random walks.”

The algorithm does not require knowing the vocabulary or frequency distribution of vertices ahead of training.

“While it is beneficial to know the V and the frequency distribution of vertices in the random walks ahead of the training, it is not necessary for the algorithm to work as we will show in 4.2.2.”

ASGD achieves an optimal rate of convergence when updates are sparse and no lock is acquired for shared model parameters.

“Given that our updates are sparse and we do not acquire a lock to access the model shared parameters, ASGD will achieve an optimal rate of convergence [36].”

• cites [36] [36] B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in Neural Information Processing Systems 24 , pages 693-701. 2011. -Not checked yet

  Not checked in the free run.

DeepWalk can make useful models of various sizes.

“These experiments show that our method can make useful models of various sizes.”

DeepWalk can outperform the baselines on Flickr with 60% less training data.

“In other words, DeepWalk can outperform the baselines with 60% less training data.”

DeepWalk is able to learn meaningful latent representations for vertices after only a small number of random walks.

“These results demonstrate that we are able to learn meaningful latent representations for vertices after only a small number of random walks.”

DeepWalk performs exceedingly well in a sparsely labeled environment.

“DeepWalk , can scale to large graphs, and performs exceedingly well in such a sparsely labeled environment.”

The YouTube experiment showcases performance benefits that can occur from using social representation learning for multilabel classification.

“This experiment showcases the performance benefits that can occur from using social representation learning for multilabel classification.”

DeepWalk learns latent social representations instead of computing statistics related to centrality or partitioning.

“We learn our latent social representations, instead of computing statistics related to centrality [12] or partitioning [41].”

• cites [12] [12] B. Gallagher and T. Eliassi-Rad. Leveraging label-independent features for classification in sparsely labeled networks: An empirical study. In Advances in Social Network Mining and Analysis , pages 1-19. Springer, 2010. -Not matched

  Couldn’t be matched to a paper in Crossref, so it can’t be checked.

• cites [41] [41] L. Tang and H. Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery , 23(3):447-478, 2011. - sourceNot checked yet

  Not checked in the free run.

As an online algorithm, DeepWalk is scalable.

“As an online algorithm, DeepWalk is also scalable.”

Experiments on a variety of different graphs illustrate the effectiveness of DeepWalk on challenging multi-label classification tasks.

“Experiments on a variety of different graphs illustrate the effectiveness of our approach on challenging multi-label classification tasks.”

DeepWalk applies unsupervised representation learning to graphs.

“Weapply unsupervised representation learning to graphs.”

DeepWalk can scale to large graphs.

“DeepWalk , can scale to large graphs, and performs exceedingly well in such a sparsely labeled environment.”

The strong performance of DeepWalk when only small fractions of the graph are labeled is a core strength of the approach.

“This strong performance when only small fractions of the graph are labeled is a core strength of our approach.”

DeepWalk is a novel approach for learning latent social representations of vertices.

“We propose DeepWalk , a novel approach for learning latent social representations of vertices.”

On large graphs, DeepWalk significantly outperforms other methods designed to operate for sparsity.

“On such large graphs, our method significantly outperforms other methods designed to operate for sparsity.”

DeepWalk can create meaningful representations for graphs too large to run spectral methods on.

“Our results show that we can create meaningful representations for graphs too large to run spectral methods on.”

Using local information from truncated random walks as input, DeepWalk learns a representation which encodes structural regularities.

“Using local information from truncated random walks as input, our method learns a representation which encodes structural regularities.”