2024/12/12 by Maksim Mironov, Mironov, Mikhail, Liudmila Prokhorenkova +1 · 3 citations
Computer Science · #Topological and Geometric Data Analysis #Advanced Graph Theory Research #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2412.09663
Homophily is a graph property describing the tendency of edges to connect\nsimilar nodes. There are several measures used for assessing homophily but all\nare known to have certain drawbacks: in particular, they cannot be reliably\nused for comparing datasets with varying numbers of classes and class size\nbalance. To show this, previous works on graph homophily suggested several\nproperties desirable for a good homophily measure, also noting that no existing\nhomophily measure has all these properties. Our paper addresses this issue by\nintroducing a new homophily measure - unbiased homophily - that has all the\ndesirable properties and thus can be reliably used across datasets with\ndifferent label distributions. The proposed measure is suitable for undirected\n(and possibly weighted) graphs. We show both theoretically and via empirical\nexamples that the existing homophily measures have serious drawbacks while\nunbiased homophily has a desirable behavior for the considered scenarios.\nFinally, when it comes to directed graphs, we prove that some desirable\nproperties contradict each other and thus a measure satisfying all of them\ncannot exist.\n