Node classification in the heterophilic regime via diffusion-jump GNNs.

Area of Science:

• Graph Neural Networks (GNNs)
• Network Science
• Machine Learning

Background:

• Vanilla GNNs assume homophily, where connected nodes share labels, leading to harmonic node properties.
• Heterophily, where connected nodes have different labels, is treated as a loss of harmonicity in standard GNNs.
• Existing High-Order (HO) GNNs like MixHop use hops, which may not effectively capture complex network structures.

Purpose of the Study:

• To define and quantify "structural heterophily" as a measure of network harmonicity.
• To develop a novel GNN model, Diffusion-Jump GNN, that overcomes limitations imposed by structural heterophily.
• To improve GNN performance on both homophilic and heterophilic graph datasets.

Main Methods:

• Defined structural heterophily using the ratio of Laplacian Dirichlet energy to ground energy.
• Introduced Diffusion-Jump GNN, which utilizes diffusion distances for network traversal instead of simple hops.
• Developed a method to learn diffusion distances and structural filters, approximating Laplacian eigenvectors through a combination of Dirichlet and prediction losses.

Main Results:

• The Diffusion-Jump GNN model demonstrates competitive performance against State-Of-the-Art (SOTA) methods.
• The model achieves strong results on both homophilic and heterophilic graph datasets.
• Effectiveness was shown even on large-scale graphs, indicating scalability.

Conclusions:

• Structural heterophily provides a valuable new perspective for understanding and modeling graph data.
• Diffusion-Jump GNN offers a robust and effective approach for graph representation learning, adaptable to diverse network structures.
• The proposed method advances GNN capabilities in handling complex, real-world graph data.