Collaborative Research: III: Medium: Graph Neural Networks for Heterophilous Data: Advancing the Theory, Models, and Applications

合作研究：III：媒介：异质数据的图神经网络：推进理论、模型和应用

• 批准号: 2212143
• 负责人: Danai Koutra
• 金额: $ 50万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-10-01 至 2026-09-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2212143&HistoricalAwards=false
• 关键词: Collaborative; Research; III; Medium; Graph

Graph neural networks (GNNs), which translate the success of deep learning to graph-structured data, have numerous applications spanning from recommendation systems and fraud detection to medicine to finance. In such applications, the extent to which similar entities connect with each other---known as homophily---is unknown and cannot be computed empirically due to limited labeled data. Though homophily is common, it is not universal; there are important real-world settings where "opposites attract", leading to heterophily (low homophily). By moving beyond a reliance on graph homophily and introducing new GNN models, this project will generalize GNNs to work effectively in a wider range of domains. It will also help rectify some negative consequences of GNNs that are tailored to homophilous graphs, including biased, unfair, or erroneous predictions when applied to heterophilous data. Focusing on robustness, fairness, and explainability will help support accountable algorithmic decision-making in the domains where GNN models are employed. In addition to research, this project will support the training of a diverse cohort of undergraduate and graduate students at the University of Michigan, the New Jersey Institute of Technology, and Michigan State University via integration of this research in advanced courses, capstone projects, and other opportunities to directly contribute to this research program.The inability of GNNs to generalize their strong performance on homophilous or assortative graphs to many heterophilous graphs has attracted significant attention, and has led to empirical demonstration of the existence of "good heterophily", where GNNs can perform well. However, there is still limited understanding about the types of heterophily that are easy or difficult to handle with GNNs, especially beyond the limited, typically-studied settings (i.e., node classification on small homogeneous graphs). This project will advance the theoretical underpinnings of the interplay between different types of heterophily and GNNs, considering properties beyond just accuracy, which are necessary for deployment. Specifically, it will contribute: (a) New Theory: It will formally characterize the heterophily-related challenges of GNNs to provide a deeper understanding into "good" and "bad" heterophily, and enhance our understanding of "good" types of heterophily, which some architectures can model effectively, but have been vastly ignored until now. (b) New Models: Based on the new theory, it will introduce new GNN designs and architectures that not only have strong performance across different levels and types of heterophily, but are also robust, fair, and transparent, which are crucial for algorithmic decision-making. (c) New Applications: The project will also go beyond the traditional tasks and heterophilous network types investigated in the literature, and will include exploration of high-impact applications along with collaborators in academia and industry.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.

图神经网络（GNN）将深度学习的成功转化为图结构数据，具有从推荐系统和欺诈检测到医学到金融的众多应用。在这样的应用中，相似实体彼此连接的程度-被称为同质性-是未知的，并且由于有限的标记数据而不能凭经验计算。虽然同质性很常见，但它并不普遍;有一些重要的现实世界设置，“异性相吸”，导致异质性（低同质性）。通过超越对图同构的依赖并引入新的GNN模型，该项目将推广GNN，使其在更广泛的领域中有效工作。它还将有助于纠正为同质图定制的GNN的一些负面后果，包括在应用于异质数据时有偏见，不公平或错误的预测。专注于鲁棒性，公平性和可解释性将有助于在使用GNN模型的领域中支持负责任的算法决策。除了研究之外，该项目还将支持密歇根大学、新泽西理工学院和密歇根州立大学通过将本研究整合到高级课程、顶点项目、和其他机会，以直接促进这一研究计划。GNN无法概括其强大的性能对同性恋或非同性恋图到许多异质图的映射已经引起了极大的关注，并且已经导致了“良好异质性”的存在的经验证明，其中GNN可以表现良好。然而，对GNN容易或难以处理的异质性类型的理解仍然有限，特别是在有限的、典型研究的环境之外（即，小的均匀图上的节点分类）。该项目将推进不同类型的异质性和GNN之间相互作用的理论基础，考虑部署所必需的准确性之外的属性。具体来说，它将有助于：（a）新理论：它将正式描述GNN的异质性相关挑战，以提供对“好”和“坏”异质性的更深入理解，并增强我们对“好”类型异质性的理解，一些架构可以有效地建模，但到目前为止一直被忽视。(b)新型号：基于新的理论，它将引入新的GNN设计和架构，不仅在不同层次和类型的异质性上具有强大的性能，而且还具有鲁棒性，公平性和透明性，这对于算法决策至关重要。(c)新应用：该项目也将超越传统的任务和heterophilous网络类型的文献调查，并将包括高影响力的应用沿着与学术界和工业界的合作者的探索。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响力审查标准进行评估的支持。

项目成果

Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks

• DOI: 10.1109/icdm54844.2022.00169
• 发表时间: 2021-02
• 期刊: 2022 IEEE International Conference on Data Mining (ICDM)
• 作者: Yujun Yan;Milad Hashemi;Kevin Swersky;Yaoqing Yang;Danai Koutra

On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks

• DOI: 10.48550/arxiv.2306.05557
• 发表时间: 2023-06
• 期刊: ArXiv
• 作者: Donald Loveland;Jiong Zhu;Mark Heimann;Benjamin Fish;Michael T. Shaub;Danai Koutra

Heterophily and Graph Neural Networks: Past, Present and Future

• 发表时间: 2023
• 期刊: IEEE Data Eng. Bull.
• 作者: Jiong Zhu;Yujun Yan;Mark Heimann;Lingxiao Zhao;L. Akoglu;Danai Koutra

Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices

• DOI: 10.1145/3616855.3635786
• 发表时间: 2023-06
• 期刊: Proceedings of the 17th ACM International Conference on Web Search and Data Mining
• 作者: Jing Zhu;Yuhang Zhou;V. Ioannidis;Sheng Qian;Wei Ai;Xiang Song;Danai Koutra

How does Heterophily Impact the Robustness of Graph Neural Networks?: Theoretical Connections and Practical Implications

• DOI: 10.1145/3534678.3539418
• 发表时间: 2021-06
• 期刊: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
• 作者: Jiong Zhu;Junchen Jin;Donald Loveland;Michael T. Schaub;Danai Koutra