Revisiting Graph Homophily Measures
Homophily is a graph property describing the tendency of edges to connect similar nodes. There are several measures used for assessing homophily but all are known to have certain drawbacks: in particular, they cannot be reliably used for comparing datasets with varying numbers of classes and class size balance. To show this, previous works on graph homophily suggested several properties desirable for a good homophily measure, also noting that no existing homophily measure has all these properties. Our paper addresses this issue by introducing a new homophily measure - unbiased homophily - that has all the desirable properties and thus can be reliably used across datasets with different label distributions. The proposed measure is suitable for undirected (and possibly weighted) graphs. We show both theoretically and via empirical examples that the existing homophily measures have serious drawbacks while unbiased homophily has a desirable behavior for the considered scenarios. Finally, when it comes to directed graphs, we prove that some desirable properties contradict each other and thus a measure satisfying all of them cannot exist.
Code (0)
등록된 구현이 없습니다.
Tasks
AllSimilar Papers 제목 키워드 기반
Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond
Homophily is a graph property describing the tendency of edges to connect similar nodes; the opposite is called heterophily. It is often believed that heterophilous graphs are challenging for standard message-passing gra…
InformativenessNode ClassificationGoing beyond accuracy: estimating homophily in social networks using predictions
In online social networks, it is common to use predictions of node categories to estimate measures of homophily and other relational properties. However, online social network data often lacks basic demographic informati…
General ClassificationNew Benchmarks for Learning on Non-Homophilous Graphs
Much data with graph structures satisfy the principle of homophily, meaning that connected nodes tend to be similar with respect to a specific attribute. As such, ubiquitous datasets for graph machine learning tasks have…
AttributeFraud DetectionGraph Representation LearningInductive Bias+3Structural Bias Beyond Homophily: A Study of Fairness in Link Prediction
Graph link prediction (LP) plays a critical role in socially impactful applications such as job recommendation and friendship formation, making fairness a critical concern in this task. While many fairness-aware methods …
Graph GenerationLink PredictionGraph LearningRevisiting Heterophily For Graph Neural Networks
Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by using graph structures based on the relational inductive bias (homophily assumption). While GNNs have been commonly believed to outperform NNs in real-wo…
Inductive BiasNode ClassificationNode Classification on Non-Homophilic (Heterophilic) Graphs