BIGDATA: F: DeepWalking Graphs for Feature Extraction

大型网络的稀疏性使得机器学习算法很难有效地提取特征。最近关于网络嵌入（DeepWalk）的工作揭示了神经语言建模如何应用于数据挖掘和信息检索中非常一般的一类图分析问题。 该项目将改进大规模网络的训练算法和数据表示，为加权和属性网络创建更好，更强大的图嵌入。 它还将使网络连接功能与更面向文本的功能的相对性能进行有意义的比较。链接中可能有比可读内容本身更多的可用信息。这个项目将在几个新的方向上开发这些方法，包括扩展到新的图形类和速度/规模增强。 最初的DeepWalk只从未加权、无向和连通图中诱导潜在表示。但是，将其应用于数据分析中产生的更一般的图形，有相当大的兴趣。在二分图和不连通图这样的自然网络上做正确的事情，提出了具有理论和实际意义的令人惊讶的微妙问题。 该项目还将探索几种提高网络嵌入训练性能的想法，包括更有效的梯度更新和改进的图采样方法，特别是自避免随机游走对其他稀有节点进行过采样的能力。 该项目旨在将DeepWalk的有效范围扩展几个数量级，从我们今天常规处理的1000万个顶点图到数十亿个节点上的网络规模网络。 这项工作的更广泛的影响是深远的数据挖掘和信息检索，包括用户分析/人口统计推断，在线广告和欺诈检测。 在这个研究项目下开发的软件和数据资源将作为开源发布。它们将直接适用于生物医学和社会科学，并作为教育和学术资源。 欲了解更多信息，请访问项目网站http://www.cs.stonybrook.edu/~skiena/deepwalking。

The sparsity of large networks makes it difficult to efficiently extract features for machine learning algorithms. Recent work on network embeddings (DeepWalk) has revealed how neural language modeling can be applied to a very general class of graph analysis problems in data mining and information retrieval. This project will improve training algorithms and data representation for large-scale networks, creating better, more powerful graph embeddings for weighted and attributed networks. It will also enable meaningful comparison of the relative performance of network connectivity features vs. more text-oriented features. It is possible that there might be more usable information in links than in the readable content itself.This project will develop these methods in several new directions, including extensions to new graph classes and speed/scale enhancements. The original DeepWalk induced latent representations only from unweighted, undirected, and connected graphs. But there is considerable interest in applying it to more general graphs arising in data analysis. Doing the right thing on such natural networks as bipartite and disconnected graphs presents surprisingly subtle issues of theoretical and practical significance. This project will also explore several ideas to increase training performance of network embeddings, including more efficient gradient updates and improved graph sampling methods and particularly the power of self-avoiding random walks to oversample otherwise rare nodes. This project seeks to extend the effective range of DeepWalk by several orders of magnitude, from the 10 million vertex graphs we routinely handle today to web-scale networks on billions of nodes. The broader impacts of this work are far reaching across data mining and information retrieval, including user profiling/demographic inference, online advertising, and fraud detection. The software and data resources developed under this research project will be released as open source. They will be directly applicable to the biomedical and social sciences, and serve as both an educational and scholarly resource. For further information, see the project website at http://www.cs.stonybrook.edu/~skiena/deepwalking.