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

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

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.