HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity

Graph neural networks (GNNs) have substantially advanced machine learning applications to graph-structured data by effectively propagating node attributes end-to-end. Typically, GNNs rely on the assumption of homophily, where nodes with similar labels are more likely to be connected [39, 36]. The homophily assumption holds true in contexts such as social networks and citation graphs, where models like GCN [14], GIN [37], and GraphSAGE [11] excel at tasks like node classification and graph prediction. However, this is not the case in heterophilous datasets, such as web page and transaction networks, where edges often link nodes with differing labels. Models such as GAT [35] and various graph transformers [38, 9] show improved performance on these datasets. With their attention mechanisms that learns edge importances, they reduce the dependency on the homophily. In this setting, our work specifically addresses unsupervised attributed node clustering tasks, which require models to function without any label information during training.