Node classification in the heterophilic regime via diffusion-jump GNNs

Abstract

In the ideal (homophilic) regime of vanilla GNNs, nodes belonging to the same community have the same label: most of the nodes are harmonic (their unknown labels result from averaging those of their neighbors given some labeled nodes). In other words, heterophily (when neighboring nodes have different labels) can be seen as a “loss of harmonicity”. In this paper, we define “structural heterophily” in terms of the ratio between the harmonicity of the network (Laplacian Dirichlet energy) and the harmonicity of its homophilic version (the so-called “ground” energy). This new measure inspires a novel GNN model (Diffusion-Jump GNN) that bypasses structural heterophily by “jumping” through the network in order to relate distant homologs. However, instead of using hops as standard High-Order (HO) GNNs (MixHop) do, our jumps are rooted in a structural well-known metric: the diffusion distance. Computing the “diffusion matrix” (DM) is the core of this method. Our main contribution is that we learn both the diffusion distances and the “structural filters” derived from them. Since diffusion distances have a spectral interpretation, we learn orthogonal approximations of the Laplacian eigenvectors while the prediction loss is minimized. This leads to an interplay between a Dirichlet loss, which captures low-frequency content, and a prediction loss which refines that content leading to empirical eigenfunctions. Finally, our experimental results show that we are very competitive with the State-Of-the-Art (SOTA) both in homophilic and heterophilic datasets, even in large graphs. • Structural Heterophily . We define heterophily in graphs as the loss of harmonicity of the labeling. • Diffusion-Jump GNNs . High-Order GNNs where the distances between the nodes rely on diffusion distances (leading to “jumps”) instead of hops. • Learnable Structural Filters . Jumps result from slicing the matrix of diffusion distances (diffusion matrix DM). Such slicing is fully learnable. • Empirical Eigenfunctions . Instead of computing the eigenvectors, we learn them in order to provide a spectral approximation of diffusion distances.

Topics & Concepts