AF: Small: Fast and Memory-Efficient Dimensionality Reduction for Massive Networks

AF：小：大规模网络的快速且节省内存的降维

• 批准号: 1117055
• 负责人: Inderjit Dhillon
• 金额: $ 36万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1117055&HistoricalAwards=false
• 关键词: AF; Small; Fast; Memory; Efficient

Many systems take the form of massive networks, i.e., a set of nodes joined together in pairs by links. Examples include social, communication and biological networks. Research on such complex networks has attracted broad scientific disciplines. While many sophisticated mathematical tools for network analysis have been developed, many such tools are not directly applicable due to the sheer size of modern-day networks. In addition, these networks may be dynamically evolving and may have extra node information and/or auxiliary links between the same group of nodes obtained from heterogeneous data sources. Our proposed research aims to develop mathematical ideas novel to the analysis of massive networks. In particular, we plan to develop a novel dimensionality reduction method that proceeds by conducting a very fast clustering of the graph, extracting local latent subspaces of the graph, and then "gluing" together these subspaces to get a dimensionality reduction scheme for the entire network. Building on our new method, we plan to develop methods for handling time-evolving networks, multiple sources of information, supervised dimensionality reduction of networks and hierarchical schemes for dimensionality reduction as well as prediction. Our methods are eminently suitable for parallel computation, and we propose to further address the scalability problem by developing parallel versions of our methods on modern multi-core architectures.The proposed research will enable important inference tasks, such as link prediction, collaborative filtering and semi-supervised classification to be efficiently carried out on massive networks. We expect the resulting algorithms to have the following properties: (1) computationally faster than current state-of-the-art methods for dimensionality reduction; (2) much more memory-efficient than the globally and rank-wise optimal SVD method; (3) scalable to extremely large data sets, such as online social networks, e.g., MySpace and Facebook, communication networks and virtual networks; (4) flexible enough to integrate auxiliary information of various types and different levels of uncertainty; and (5) effective enough to discover the task-oriented low-dimensional structure of the network. The proposed project will have broad impact on research in a variety of disciplines, including applied mathematics, computer science and social sciences. We plan to share the software developed under the project with the scientific community via a public web site, as well as the data and results that arise from our studies. The project will make a conscious effort to involve students in inter-disciplinary research.

许多系统采用大规模网络的形式，即一组通过链路成对连接在一起的节点。例子包括社交、通信和生物网络。对这种复杂网络的研究吸引了广泛的科学学科。虽然已经开发了许多用于网络分析的复杂的数学工具，但由于现代网络的巨大规模，许多这样的工具并不直接适用。此外，这些网络可以是动态发展的，并且可以在从异类数据源获得的同一组节点之间具有额外的节点信息和/或辅助链路。我们提出的研究旨在发展新的数学思想来分析海量网络。特别是，我们计划开发一种新的降维方法，通过对图进行非常快速的聚类，提取图的局部潜在子空间，然后将这些子空间粘合在一起，得到整个网络的降维方案。在我们新方法的基础上，我们计划开发处理时间演化网络、多信息源、网络的监督降维以及降维和预测的分层方案的方法。我们的方法非常适合于并行计算，我们建议通过在现代多核体系结构上开发我们的方法的并行版本来进一步解决可伸缩性问题，所提出的研究将使重要的推理任务，如链接预测、协同过滤和半监督分类能够在大规模网络上高效地执行。我们期望所得到的算法具有以下特性：(1)比当前最先进的降维方法在计算上更快；(2)比全局和按等级的最优SVD方法更有效地存储；(3)可扩展到极大的数据集，例如在线社交网络，例如MySpace和Facebook、通信网络和虚拟网络；(4)足够灵活地集成各种类型和不同级别的不确定性的辅助信息；以及(5)足够有效地发现网络的面向任务的低维结构。拟议的项目将对各种学科的研究产生广泛影响，包括应用数学、计算机科学和社会科学。我们计划通过一个公共网站与科学界分享在该项目下开发的软件，以及我们研究产生的数据和结果。该项目将有意识地努力让学生参与跨学科研究。