Graph Framelets for Graph Deep Learning: Homophily and Heterophily

Description

Graph theory originated from Euler's work on the "Seven Bridges of Königsberg" as a powerful tool for modeling abstract relationships and solving combinatorial problems. Over the past 285 years, graph theory has been extensively developed and applied across various disciplines, including computer science, physics, chemistry, and social science. In recent decades, the power of deep learning has been showcased by many of its applications, e.g., in large language models (LLMs) and artificial intelligence generated content (AIGC). Deep learning has enriched graph theory, leading to a recent active research area: graph deep learning. It is also known as learning on graphs (LoG), which focuses on machine/deep learning on large-scale, real-world graph-structured data. One of the key developments in graph deep learning is the introduction of graph neural networks (GNNs), which have demonstrated remarkable performance in various tasks such as node classification, link prediction, and graph classification. GNNs leverage the inherent structure of graphs to capture complex dependencies and make predictions. They have been proven to be effective in handling graph-structured data and opened up new avenues for uncovering insights in biology, chemistry, physics, and social science. Homophily and heterophily are typical phenomenons in graph-structured data, which refer to the tendency of connected nodes to share common characteristics or belong to the same class. Traditional GNN models, which assume homophily, may struggle to perform well on graph-structured data exhibiting heterophily. Thus, graph learning on heterophilous graphs brings challenges that require the development of new GNN models capable of extracting meaningful information despite the lack of homophily between neighboring nodes. Graph framelets are multiscale representation systems that generalize classical wavelets and framelets to graph domains. They inherit desirable properties like multiscale analysis, sparse representation, graph filter banks, and fast graph framelet transforms. In this project, we shall focus on the development of graph framelets for graph deep learning. We aim to build graph framelets for encoding geometric priors and sparse prior on graph-structured data. Graph framelets allow for domain-specific design while ensuring computational efficiency. By incorporating spatial and spectral adaptivity, graph framelets enable the sparse representation of graph-structured data exhibiting either homophily or heterophily. We shall consider the integration of deep learning techniques in the development of graph framelet neural networks and beyond, which provide a powerful mathematical tool for learning on graphs with homophily and heterophily.