Graph Neural Networks on heterophilous graphs: performance analysis and new architectures

Graph heterophily, also called disassortativity, is a property of networks that models the likelihood of nodes with different characteristics being connected. Several real-world graphs present high levels of heterophily, such as computer networks, where clients usually connect to servers, and dating applications, where users tend to connect with users of the opposite gender. Despite the relevant contexts in which heterophilous graphs are observed, current approaches fail to map nodes to meaningful low-dimensional embeddings. Indeed, Graph Neural Networks (GNNs), currently the state-of-the-art models for machine learning on graph-structured data, implicitly assume homophily, leading to worse performances on disassortative networks. Notwithstanding several works defining novel GNN architectures for heterophilous settings, there is still insufficient understanding of the relation between GNN performances and graph disassortativity. In this context, this thesis focuses on two main objectives. First of all, the impact of heterophily on GNN performances is discussed. In particular, it is shown that GNNs can still achieve good performances under heterophily if other conditions are met. Previous works already identify other graph properties beyond heterophily that affect GNN performances, but they rely on the assumption of node features being very informative for node labels, which is not always observed in real scenarios. Therefore, in this thesis, the classification capabilities of a Graph Convolutional Network (GCN), chosen as example given its popular and simple design, are modeled in a context without node features, where only graph structural properties are considered. In this setting, it is shown that a target node is likely to be correctly classified if the majority of its 1-hop neighbors have neighbors that, for the most part, share the same label as the target node. To numerically quantify this property, a new metric is introduced: 2NCS (2-hop Neighborhood Class Similarity), defined as the average over neighbors of the percentages of their neighbors with the same label as the target node. Through extensive experiments on real and synthetic graphs, it is shown that nodes with high 2NCS values are usually correctly classified by a GCN, also in some scenarios where features are present. Therefore, 2NCS appears to be an informative metric to estimate GCN performances. Secondly, two new GNN models for node classification on heterophilous graphs are proposed: GATH (GAT for Heterophily) and GCNH (GCN for Heterophily). GATH leverages an extended attention mechanism to learn a weight between any pair of nodes in the graph. This weight defines the importance of the message coming from that node. Additionally, GATH separately computes an embedding for the target node and its neighborhood, merging them only at the latest stage through a learnable coefficient. Moreover, messages for a target node are aggregated also from nodes that are not directly connected but might still be informative in heterophilous settings. In conclusion, structural information, namely the node degrees and the distance between the nodes, is added to the feature embeddings as input to the attention weight computation. GCNH is a simpler model that extends GCN by separately learning embeddings for the target node and the neighbors. Experiments on real and synthetic graphs show that GATH and GCNH can achieve competitive performances compared to state-of-the-art methods on heterophilous graphs.