Abstract
Homophily is a graph property describing the tendency of edges to connectsimilar nodes. There are several measures used for assessing homophily but allare known to have certain drawbacks: in particular, they cannot be reliablyused for comparing datasets with varying numbers of classes and class sizebalance. To show this, previous works on graph homophily suggested severalproperties desirable for a good homophily measure, also noting that no existinghomophily measure has all these properties. Our paper addresses this issue byintroducing a new homophily measure - unbiased homophily - that has all thedesirable properties and thus can be reliably used across datasets withdifferent label distributions. The proposed measure is suitable for undirected(and possibly weighted) graphs. We show both theoretically and via empiricalexamples that the existing homophily measures have serious drawbacks whileunbiased homophily has a desirable behavior for the considered scenarios.Finally, when it comes to directed graphs, we prove that some desirableproperties contradict each other and thus a measure satisfying all of themcannot exist.