CAREER: New Frontiers in Graph Generation

图是不同实体之间许多不同类型的连接、关系或网络的模型。它可以用来表示微观层面的对象，比如分子被记录为连接原子的键，也可以用来表示宏观层面的网络，比如由用户之间的连接组成的社交网络。图结构通常包含丰富的信息，而且规模很大。一个重要的任务是合成与现有图相似但又不同的新图。例如，药物设计任务可能需要一个模型来生成用于筛选的新分子图；而一个社交网络的数据共享任务可能需要一个模型来合成和共享一个类似于原始网络的图，而不释放敏感的链接信息。这个项目结合了神经网络和概率方法来开发工具，为广泛的任务生成新的图形。这些工具还具有坚实的统计基础，有助于加深对图形数据的理解。本项目将倡导基于离散顺序过程的图生成模型开发的新方向——生成模型从随机或平凡图出发，分多个步骤裁剪生成随机图。这个项目的研究工作有三个技术目标。首先，该项目将开发一个概率框架，用于使用神经网络构建图形生成模型。其次，该项目将克服模型训练和模型预测的效率问题。第三，将新开发的模型与传统的随机图模型进行比较，加深对网络数据的理解。通过比较，还将开发新的方法来保护网络数据共享中的私有信息。该项目开发的模型将具有坚实的统计基础，并与传统的随机图模型相连接。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A graph is a model of many different types of connections, relationships, or networks between different entities. It can be used to represent micro-level objects, like molecules being recorded as bonds connecting atoms, and macro-level networks, like social networks consisting of connections between users. Graph structures often contain rich information and are large in scale. An important task is to synthesize new graphs that are similar to but different from existing ones. For example, a drug design task may require a model to generate new molecule graphs for screening; and a data-sharing task for a social network may need a model to synthesize and share a graph similar to the original network, without releasing sensitive link information. This project combines neural networks and probabilistic methods to develop tools for generating new graphs for a wide range of tasks. These tools also have a solid statistical foundation and help to deepen the understanding of graph data.This project will advocate a new direction of developing graph generative models based on discrete sequential processes—the generative model starts from a random or trivial graph and tailors it in multiple steps to generate a random graph. The research effort in this project has three technical aims. First, the project will develop a probabilistic framework for building graph generative models with neural networks. Second, the project will overcome efficiency issues in model training and model predictions. Third, the project will compare newly developed models with traditional random graph models to deepen the understanding of network data. From the comparison, new methods will also be developed to preserve private information in the sharing of network data. Models to be developed from this project will have a solid statistical foundation and be connected to traditional random graph models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.