Graph neural networks on heterophilous graphs: performance analysis and new architectures

Presenter: Andrea Cavallo
Monday, December 5th, 2022 17:00
Location: SmartData@Covivio

Graph Neural Networks (GNNs) achieve state-of-the-art performance on several tasks on graph-structured data. Their success is related to their capability to generate embeddings that model the entire neighborhood of a node, instead of just the node itself. This approach is very effective on homophilous graphs, i.e. graphs where same-type nodes tend to connect, but it leads to less consistent performance on heterophilous graphs, where different-type nodes are likely connected and, therefore, neighborhood information might be less representative or even misleading.

In this talk, we first observe that GNNs do not perform poorly on all heterophilous graphs, and we identify a new graph structural property that is more correlated to GNN performance than homophily. To measure this property, we introduce a new metric, called 2-hop Class Neighbor Similarity (2NCS).

Then, we introduce two novel GNN models, GCNH and GATH, which extend existing architectures and improve classification accuracy on heterophilous graphs, achieving comparable performance with the state-of-the-art.

Biography: Andrea Cavallo obtained his Master’s Degree in Computer Engineering from Politecnico di Torino in 2022 and he is currently working in the SmartData@PoliTo research center. His research interests include Graph Machine Learning and Deep Learning with application to network traffic analysis.

Download flyer