ATD: Sparse and Localized Graph Convolutional Networks for Anomaly Detection and Active Learning

许多应用程序产生大量数据，其中复杂的关系和相互依赖性自然地被建模为图形，例如道路网络、移动网络和公共卫生监测网络。尽管人们对图卷积网络（GCNs）非常关注，但现有的绝大多数工作仅限于平衡节点分类，因此无法准确检测异常节点。这个项目的目标是一个稀疏的、局部化的GCN，用于检测异常模式。此外，还将开发一种新的主动学习框架，该框架将学习最优查询策略以减少训练标签的数量。将进行理论调查来解释异常模式，试图与领域专家的直觉和澄清保持一致。所开发的计算工具将特别适用于遥感和地理空间信息领域。此外，研究人员将把研究成果纳入开发新的跨学科课程，注重理论和应用。这些课程将作为学生招募的跳板，例如有兴趣将此研究作为博士论文主题的研究生和有兴趣暑期研究项目的本科生。对真实数据集的初步研究已经强烈地证明了在图上使用稀疏卷积滤波器的偏好。为了提高计算效率和结构特征提取，还需要在顶点和图的频域都有节点定位。通过将稀疏性和本地化相结合，该项目旨在建立一个稀疏和本地化的GCN范式，以有效地检测异常节点。特别是，本项目将解决以下问题：(1)如何设计图形卷积来有效地执行稀疏和局部模式的异常检测；(2)如何优化网络架构和算法设计；(3)如何通过主动学习来减少用户在标记数据收集中的负担，即通过一系列动态查询来标记少量最有效的异常检测节点。总体而言，本项目将推进gnn和异常检测的算法和理论基础。该研究将有助于时频分析、谐波分析、不确定度量化和非凸优化等领域的研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many applications produce massive quantities of data in which complex relationships and interdependency are naturally modeled as graphs, such as road networks, mobile networks, and public health surveillance networks. Despite considerable attention on graph convolution networks (GCNs), the vast majority of the existing works are limited to balanced-node classification, thus ineffective at detecting anomalous nodes accurately. This project aims at a sparse and localized GCN for detecting anomalous patterns. In addition, a novel active learning framework will be developed that learns the optimal query strategy to reduce the number of training labels. Theoretical investigations will be performed to interpret the anomalous patterns in an attempt to align with intuitions and clarifications from domain experts. The computational tools developed will be applicable, specifically in the fields of remote sensing and geospatial information. Furthermore, the investigators will incorporate the research results into developing new interdisciplinary courses with a focus on both theory and application. These courses will serve as a springboard for student recruitment, such as graduate students interested in using this research as the subject of a Ph.D. thesis and undergraduates interested in a summer research project. Preliminary studies on real datasets have strongly demonstrated a preference for sparse convolution filters on the graph. It is also desirable to have joint localization in both the vertex and graph frequency domains for computational efficiency and structural feature extraction. By combining sparsity and localization, the project aims at a sparse and localized GCN paradigm that efficiently detects anomalous nodes. In particular, this project will address the following questions: (1) how to design graph convolutions to effectively enforce sparse and localized patterns for anomaly detection; (2) how to optimize the network architecture and algorithm design; and (3) how to reduce the user’s burden in the collection of labeled data by active learning, which involves a sequence of dynamical query for labeling a small number of nodes that are most effective in anomaly detection. Overall, this project will advance the algorithmic and theoretical foundations of GNNs and anomaly detection. The research will contribute to the areas of time-frequency analysis, harmonic analysis, uncertainty quantification, and nonconvex optimization.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.