TAGDN: type-aligning graph diffusion network for capturing long-range dependencies in heterogeneous graphs without over-squashing and over-smoothing

Abstract Graph neural networks (GNNs) have seen significant growth in analyzing heterogeneous graphs, which contain different types of nodes and connections. Recent studies have attempted to analyze heterogeneous graphs without relying on manually selected metapaths. However, existing methods often struggle to learn long-range dependencies between distant nodes because of over-squashing and over-smoothing. This paper presents a new approach, type-aligning graph diffusion network (TAGDN), that effectively addresses these challenges. Our main idea is to boost the power of graph diffusion techniques in heterogeneous graphs with a type-adaptive alignment scheme. This approach allows us to exploit long-range dependencies between nodes in heterogeneous graphs without suffering over-squashing and over-smoothing. Through extensive experiments, we show that TAGDN outperforms state-of-the-art heterogeneous GNNs on diverse graph analysis tasks. Ablation studies show that our alignment scheme enhances the capacity of graph diffusion networks in heterogeneous graph analysis, yielding an average improvement of 5.02% in node classification and 25.43% in node clustering. Our implementation is available at https://anonymous.4open.science/r/TAGDN-6FC3/ .