Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond
Authors: Oleg Platonov
Denis Kuznedelev
Artem Babenko
Liudmila Prokhorenkova
Venue: NeurIPS 2023 poster (2023)
Keywords: graph characteristics
homophily
heterophily
label informativeness
constant baseline
GNN
TL;DR: We propose a theoretical framework for the analysis of graph characteristics. Based on this framework, we suggest using adjusted homophily and label informativeness to characterize graph datasets.

Abstract: 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 graph neural networks (GNNs), and much effort has been put into developing efficient methods for this setting. However, there is no universally agreed-upon measure of homophily in the literature. In this work, we show that commonly used homophily measures have critical drawbacks preventing the comparison of homophily levels across different datasets. For this, we formalize desirable properties for a proper homophily measure and verify which measures satisfy which properties. In particular, we show that a measure that we call adjusted homophily satisfies more desirable properties than other popular homophily measures while being rarely used in graph machine learning literature. Then, we go beyond the homophily-heterophily dichotomy and propose a new characteristic that allows one to further distinguish different sorts of heterophily. The proposed label informativeness (LI) characterizes how much information a neighbor's label provides about a node's label. We prove that this measure satisfies important desirable properties. We also observe empirically that LI better agrees with GNN performance compared to homophily measures, which confirms that it is a useful characteristic of the graph structure.

Characterizing Graph Datasets for Node Classification: Homophily-Heterophi. Dichotomy and Beyond
Oleg Platonov* HSE University
Denis Kuznedelev
Yandex Research
Yandex Research
Skoltech
alepplatooordyaneee-teaa...
dkuzzedeelevyyadee--tee
Artem Babenko
Liudmila Prokhorenkova"1
Yandex Research
Yandex Research
artem www..bbbboo@@pyystcch..ed
ostrounova--a@yyadee--
Abstract
Homophily is a graph property describing the tendency of edges to connect similar nodes; the opposite is called heterophily. It is often believed that het- erophilous graphs are challenging for standard message-passing graph neural net- works (GNNs), and much effort has been put into developing efficient methods for this setting. However, there is no universally agreed-upon measure of homophily the literature. In this work, we show that commonly used homophily measures have critical drawbacks preventing the comparison of homophily levels across different datasets. For this, we formalize desirable properties for a proper homophily mea- sure and verify which measures satisfy which properties. In particular, we show that measure that we call adjusted homophily satisfies more desirable properties than other popular homophily measures while being rarely used in graph machine learning literature. Then, we go beyond the homophily homophily-heterophily heterophily dichotomy and propose a new characteristic that allows one to further distinguish different sorts heterophily. The proposed label informativeness (LI) characterizes how much information neighbor's 's label provides about node's label. We prove that this measure satisfies important desirable properties. We also observe empirically that LI better agrees with GNN performance compared to homophily measures, which confirms that a useful characteristic the graph structure.
1 Introduction
Graphs are natural way represent data from various domains such social networks, citation networks, molecules, transportation networks, text, code, and others. Machine learning on graph- structured data has experienced significant growth in recent years, with Graph Neural Networks (GNNs) showing particularly strong results. Many variants GNNs have been proposed [16] IO most of them can be unified by general Message Passing Neural Networks (MPNNs) framework 77.. MPNNs combine node features (attributes) with graph topology to learn complex dependencies between the nodes. For this, MPNNs iteratively update the representation of each node by aggregating information from the previous-layer representations of the node itself and its neighbors.
43 45
'Equal contribution Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In many real-world networks, edges tend to connect similar nodes: users in social networks tend to connect to users with similar interests, and papers in citation networks mostly cite works from the same research area. This property is usually called homophily. The opposite of homophily is heterophily: for instance, in social networks, fraudsters rarely connect to other fraudsters, while in dating networks, edges often connect the opposite genders. Early works on GNNs mainly focus on homophilous graphs. However, it was later discovered that classic GNNs typically do not perform well on heterophilous graphs, and new GNN architectures have been developed for this 49].
setting
To measure the level of homophily, several homophily measures are used in the literature [ 20
32 [88. but these measures may significantly disagree with each other. In this work, we start by addressing the problem of how to properly measure the homophily level of graph. For this, we
formalize some desirable properties of reasonable homophily measure and check which measures satisfy which properties. One essential property is called constant baseline and, informally speaking, it requires measure to be not biased towards particular numbers of classes or their size balance. Our analysis reveals that commonly used homophily measures do not satisfy this property and thus cannot be compared across different datasets. contrast, a measure that we call adjusted homophily (a.k.a. assortativity coefficient) satisfies most of the desirable properties while being rarely used in graph ML literature. Based on our theoretical analysis, we advise using adjusted homophily as a better alternative to the commonly used measures.
Then, we note that heterophilous datasets may have various connectivity patterns, and some of them are easier for GNNs than others. Motivated by that, we propose new graph property called label informativeness (LII) that allows one to further distinguish different sorts of heterophily. LI characterizes how much information the neighbor's 's label provides about the node's label. We analyze this measure via the same theoretical framework and show that it satisfies the constant baseline property and thus is comparable across datasets. We also observe empirically that LI better agrees with GNN performance than homophily measures. Thus, while being very simple to compute, LI intuitively illustrates why GNNs can sometimes perform well on heterophilous datasets phenomenon recently observed in the literature. While LI is not a measure of homophily, naturally complements adjusted homophily by distinguishing different heterophily patterns.
In summary, we propose a theoretical framework that allows for an informed choice of suitable characteristics describing graph connectivity patterns in node classification tasks. Based on this framework, we suggest using adjusted homophily to measure whether similar nodes tend to be connected. To further characterize the datasets and distinguish different sorts of heterophily, we propose a new measure called label informativeness.
2 Homophily measures
Assume that we are given graph G = (V, E) with nodes V, |V| = n. and edges E. Throughout the paper, we assume that the graph is simple (without self-loops and multiple edges) and undirected RRM and class label yo E (l...., C}. Let n& denote
Each node v E V has feature vector the size of k-th class, i.e., A4 = [ : yo = k}H By N(v) we denote the neighbors of o in and by d(v)= [N)) the degree of Also, let D2 := w d(v). Let p(-) denote the empirical distribution of class labels, i.e., pkk) na Then, we also define degree- distribution as
E. ya d(e)
p(k))
2|
2|
2.1 Popular homophily measures
Many GNN models implicitly make so-called homophily assumption: that similar nodes are connected. Similarity can be considered in terms of node features or node labels. Usually, label homophily analyzed, and we also focus on this aspect, leaving feature homophily for further studies. There are several commonly used homophily measures in the literature. Edge homophily [I 48) is the fraction of edges that connect nodes of the same class:
Hfu, v) E E ya = yoH
hedge
(1)
E
We further denote (unordered) edges by {u, f} and ordered pairs of nodes by (u, v).

---

Node homophily [32] computes the fraction of neighbors that have the same class for all nodes and then averages these values across the nodes:
Eu)NNO ya yoH
Ryode
d(v)
NEV
These two measures intuitive but have the downside of being sensitive the number of classes and their balance, which makes them hard to interpret and incomparable across different datasets [20]. For example, suppose that each node in graph is connected to one node of each class. Then, both edge homophily and node homophily for this graph will be equal to C. Thus, these metrics will produce widely different values for graphs with different numbers of classes, despite these graphs being similar in exhibiting no homophily. To fix these issues, Lim et al. (20) propose another homophily measure sometimes referred to as class homophity [22]. Class homophily measures excess homophily compared to a null model where edges are independent of the labels. More formally,
1
Enyo Kuu E N(v) ya - yo3l Evg.= d(u)
Tik
helass =
C-1 k=1
where [x]+ = max(x; 0}. The factor C-I
1 scales helase to the interval [o, 1]; larger values indicate more homophilous graphs and non-homophilous ones are expected to have close to zero values.
However, there are still some issues with class homophily. First, when correcting the fraction of intra-class edges by its expected value, class homophily does not consider the variation of node degrees. Indeed, if nodes of class & have, on average, larger degrees than 2|E|/n, then the probability that a random edge goes that class can be significantly larger than n2 n Second, only positive deviations from n / contribute to class homophily, while classes with heterophilous connectivity patterns are neglected. Let us illustrate these drawbacks of class homophily with simple example.
Example Let us construct non-homophilous graphs for which class ho- mophily is significantly larger than zero. First, we take elique of size with all nodes belonging to the red class; then, for each node in the clique, connect to
leaves, all of which belong to the blue class (example for r = 4 is shown on the right). Note that all blue nodes are strictly heterophilous (i.e., only connect to nodes of the opposite class), while all red nodes are glass-agnostic (i.e., have the same number of neighbors of both classes). Such graphs are clearly non-homophilous, and a meaningful homophily measure should not produce value significantly greater than zero for them. However, class homophily for such graphs is positive and can become as large as 2: helass =
I.
as -> co.
2.2 Desirable properties for homophily measures
Above, we discussed some disadvantages of existing homophily measures. In this section, we formalize and extend this discussion: we propose a list of properties desirable for a good homophily measure. Our analysis is motivated by recent studies of clustering and classification performance measures 88 I. but not all their properties can be transferred to homophily measures. For instance, we do not require symmetry- - a property that a measure does not change when we swap the compared objects since homophily compares entities of different nature (a graph and a labeling). For the same reason, the distance property (requiring a measure to be linearly transformed to a metric distance) cannot be defined. On the other hand, some of our properties are novel.
Maximal agreement This property requires that perfectly homophilous graphs achieve a constant upper bound of the measure. Formally, we say that a homophily measure h satisfies maximal agreement if for any graph G in which yu = yo for all (u, v) E we have i(()) = Ciaxx- For all other graphs G. we require hGG < Cmax-
Minimal agreement We say that homophily measure satisfies minimal agreement if M(G) = Gmin for any graph G in which yo # yv for all (u, w) E E. For all other graphs G. we require (G) > Cmin. In other words, if all edges connect nodes of different classes, we expect to observe a constant minimal value.
3

---

Constant baseline This property ensures that homophily is not biased towards particular class size distributions. Intuitively, if the graph structure independent of labels, we would expect low homophily value. Moreover, if we want a measure to be comparable across datasets, we expect to observe the same low value in all such cases. There are several ways to formalize the concept of independence, and we suggest the one based on the so-called configuration model.
Definition Configuration model is defined as follows: take n nodes, assign each node v degree d(v), and then randomly pair edge endpoints to obtain a graph [
Assuming that we are given labeled nodes and the graph is constructed according to the configuration model (independently from the labels), we expect to observe a fixed (small) homophily independently of the number of classes and class size balance. We formalize this property as follows and refer to Appendix B.2 for other possible definitions.
Definition A homophily measure h has asymptotic constant baseline for G generated according to the configuration model and for any & > 0 with probability 1 1 o(1) we have [/(G) Cbase < for some constant Chase as n 0c.
In combination with maximal agreement, asymptotic constant baseline makes the values of a ho- mophily measure comparable across different datasets: the maximal agreement guarantees that perfectly homophilous graphs have the same value, while constant baseline aligns the uninformative cases with neither strong homophily nor strong heterophily.
Empty class tolerance Since homophily measures are used to compare different graph datasets, they have to be comparable across datasets with varying numbers of classes, For this, the following property is required.
Definition 3. A measure is tolerant empty classes if it is defined and it does not change when introduce an additional dummy label that is not present the data.
For instance, edge homophily and node homophily empty class tolerant, while class homophily is not. Empty class tolerance a new property that was not discussed in 8 9 since classification and clustering evaluation measures are used within one given dataset, see Appendix B.3 for more details.
Monotonicity As we discuss in Appendix B.3 it can be non-trivial to define monotonicity for the follow-
homophily measures and there can be different possible options. In this paper, ing definition that aligns especially well with edge-wise homophily measures discussed below in Section 2.5
Definition 4. A homophily measure is monotone if is empty class tolerant, increases when we add an edge between two nodes of the same class (except for perfectly homophilous graphs) and decreases when we add an edge between two nodes of different classes (except for perfectly heterophilous graphs).
In contrast Gösgens al. 9 our notion of monotonicity requires the property hold across graphs with different numbers of classes. This is caused by the empty class tolerance property.
2.3 Properties of popular homophily measures
Below we briefly discuss the properties of popular homophily measures. In most cases, the proofs straightforward or follow from Section 2.5 below. Table summarizes the results.
Edge homophily satisfies maximal and minimal agreement and is empty class tolerant and monotone. However, does not satisfy asymptotic constant baseline, which is a critical drawback: one can get misleading results in settings with imbalanced classes.
Node homophily satisfies maximal and minimal agreement. It is empty class tolerant, but not monotone: adding an edge between two perfectly homophilous nodes of the same class does not change node homophily. Similarly edge homophily, node homophily does not satisfy the asymptotic constant baseline and thus is incomparable across different datasets.
"See Appendix for additional discussions about the model.

---

Table Properties of homophily measures: maximal agreement (Max), minimal agreement (Min),
asymptotic constant baseline (ACB), empty class tolerance (ECT), monotonicity (Mon). x denotes
that the property not satisfied in general, but holds for large Madj (see Theorem
Measure
Max
Min
ACB
ECT
Mon
Edge homophily
X
V
Node homophily
X
V
X
Class homophily
X
X
X
X
Adjusted homophily
V
X*
Class homophily satisfies maximal agreement with helass = 1, but minimal agreement is not satisfied: not only perfectly heterophilous graphs may have hetass O. Class homophily is not empty class tolerant and thus is not monotone. Additionally, it does not have the asymptotic constant baseline. See Appendix B.1 for the proofs and discussions. Interestingly, removing the [+]+ operation from the definition of class homophily solves the problem with the asymptotic constant baseline, but minimal agreement, empty class tolerance, and monotonicity are still violated.
2.4 Adjusted homophily
Let us discuss a much less known homophily measure that by construction satisfies two important properties maximal agreement and constant baseline. To derive this measure, start with edge homophily and first enforce the constant baseline property by subtracting the expected value of the measure. Under the configuration model, the probability that given edge endpoint will be connected
Evige d(e) 2
to node with class k is (up to negligible term)
Thus, the adjusted value becomes
D2 hedge Eb 7|E
Now, to enforce maximal agreement, we normalize the measure as follows:
Redge > A= p(k)²
badj 1 kk=1 Ø(k)2
where we use the notation p(k) 2| This measure is known in graph analysis literature as assor- tativity coefficient [28). While assortativity is a general concept that is often applied to node degrees, it reduces to ( when applied to categorical node attributes undirected graphs. Unfortunately, this measure is rarely used in graph MI. literature (Suresh et al. [41 is the only work we are aware that uses it for measuring homophily), while our theoretical analysis shows that it satisfies many desirable properties. Indeed, the following theorem holds (see Appendix B.4 for the proof).
Theorem 1. Adjusted homophily satisfies maximal agreement, asymptotic constant baseline, and empty class tolerance. The minimal agreement is not satisfied. Moreover, this measure monotone if E0) hadi Σ. 90 and note that the bound L. p(1)²
#0741 is always smaller than 0.5. When hestj is
small, counterexamples to monotonicity exist.
While adjusted homophily violates some properties, it still dominates all other measures and is comparable across different datasets with varying numbers of classes and class size balance. Thus, we recommend using it as measure of homophily in further works.
2.5 Edge-wise homophily vs classification evaluation measures
We conclude the analysis of homophily measures by establishing connection between them and classification evaluation measures 8 For this, let us first define edge-wise homophily measures. We say that a homophily measure edge-wise it is function of the class adjacency matrix that we now define. Since we consider undirected graphs, each edge {u, v} E gives two ordered pairs of nodes (u, v) and (v, u). We can define class adjacency matrix C as follows: each matrix element Gj denotes the number of edges (u, v) such that y,, and y, j. Since the graph is undirected, the matrix symmetric. Note that monotonicity can be naturally put in terms of the class adjacency matrix: adding an edge between two nodes of the same class i corresponds to incrementing the
5

---

(a) Informative neighbors
(b) Less informative neighbors
Figure I: Non-homophilous graphs with different connection patterns
diagonal element ou by two, and adding an edge between two nodes of different classes and corresponds to incrementing Ciy and cys by one.
Now, for each edge (u, v), let say that Yu is true label (for some object) and yo is predicted label. Then, any classification evaluation measure (e.g., accuracy) applied to this dataset is measure of homophily. Based on that, get the following correspondence.
Clearly, accuracy corresponds to edge homophily hedge-
Interestingly, both Cohen's 's Kappa and Matthews correlation coefficient correspond to adjusted homophily. As argued in 8]. the Matthews coefficient one of the best classification evaluation measures in terms of its theoretical properties. Our extended analysis confirms this conclusion for the corresponding homophily measure: we prove a stronger version of asymptotic constant baseline and also establish stronger variant of monotonicity in the interval of large values of hadj. The latter result essential since in X was only claimed that monotonicity is violated when C 2.
Another measure advised by { is symmetric balanced accuracy. Since in our case the class adjacency matrix is symmetric, it gives the same expression as balanced accuracy: heat The obtained measure satisfies the maximal and minimal agreement prop- erties. However, it is not empty class tolerant and thus is not monotone. The asymptotic constant baseline is also not satisfied: the value Chase I/C depends on the number of classes. Thus, despite this measure being suitable for classification evaluation, it cannot used as a homophily measure. This difference is caused by the fact that homophily measures have to be comparable across datasets with different numbers of classes, while for classification evaluation it is not required.
δ E
[[w.o);,. y.. =.
Dr
Finally, note that similarly to our derivations in Section 2.4, the value Aba can be adjusted to have both maximal agreement and constant baseline. Interestingly, this would lead to a slighlty modified class homophily with []+ operation removed. As discussed in Section 2.3 the obtained measure satisfies only the maximal agreement and constant baseline.
To conclude, there a correspondence between edge-wise homophily measures and classification evaluation measures. Adjusted homophily corresponds to both Cohen's Kappa and Matthews coeffi- cient. In terms of the satisfied properties, adjusted homophily dominates all other measures derived from this correspondence.
Finally, we also note that homophily measures can be directly related to community detection evaluation measures including the well-established characteristic in graph community detection literature called modularity (30]. See Appendix B.5 for a detailed discussion.
Label informativeness
In the previous section, we discussed in detail how to properly measure the homophily level of a graph. While homophily indicates whether similar nodes connected, heterophily is defined the negation of homophily. Thus, heterophilous graphs may have very different connectivity patterns. In this section, characterize such patterns.
To give an example, among strictly heterophilous graphs in which nodes never connect to nodes of the same class, there can be those where edges are drawn between particular pairs of classes (Figure la and those where the class of node cannot be derived from class of its neighbor (Figure [b). While adjusted homophily correctly captures the absence of homophily in these graphs, it is not designed to identify which type they belong to. However, distinguishing such graphs is practically important: informative neighbors can be very useful for models accounting for the graph structure.

---

We define a characteristic measuring the informativeness of neighbor's 's label for node's 's label. For example, in Figure Ta the neighbor's label uniquely defines the node's label. Thus, the node classification task is simple on this dataset, and we want our informativeness to be maximal for such graphs. Let us formalize this idea. Assume that we sample an edge (S. 7) E E (from some distribution). The class labels of nodes Ç and 1 are then random variables yE and Vn: We want to measure the amount of knowledge the label Yn gives for predicting Ve. The entropy H (yE) measures the 'hardness' of predicting the label of without knowing Y/. Given y/, this value is reduced to the conditional entropy H (yee (8)). In other words, My reveals [y Mn) = H (we) - H (b,) information about the label. To make the obtained quantity comparable across different datasets, say that label informativeness is the normalized mutual information of yg and Byy
LI := 1 (ye: Un)) (He))
(3)
We have LI E [0, 1]. If the label yo allows for unique reconstruction of ye, then LI 1. y and Un are independent, LI O.
Depending the distribution used for sampling an edge (5. 77), one obtain several variants of L.I.
For instance, if the edges are sampled uniformly at random (which is natural approach), the mutual
distribution (VE, Myy) for a randomly sampled edge is p(c), 02) E(,,)EE
1 =o. Then,
2
the marginal distribution of yę (and yr) the degree-weighted distribution p(c). Thus,
3 becomes:
Eer.ez p(1,, 02) log plei (ple)) 2 Een,e p(c1, 02) log (2) E. p(c)
plenee)
Lledge
D() logp(c)
For brevity, we further denote LLedge by LI and focus on this version of the measure. However, note that another natural approach to edge sampling is to first sample random node and then sample random edge incident this node. For a discussion of this approach, we refer to Appendix C.2
To claim that LI is a suitable graph characteristic, we need to show that it is comparable across different datasets. For this, we need to verify two properties: maximal agreement and asymptotic constant baseline. Recall that LI is upper bounded by one and equals one if and only if the neighbor's class uniquely reveals the node's class. This property can be considered as a direct analog of the maximal agreement defined in Section [.22 The following theorem shows that LI satisfies the
asymptotic constant baseline; see Appendix C.I for the proof.
Theorem 2. Assume that FF|
> Do and that the entropy of p(.) is bounded from below by some constant. Let Pmin ming p(k) and assume that pmin >> C/V [E] as n + 00. Then, for
the random configuration model, we have LI = o(1) with high probability.
In summary, is a simple graph characteristic suitable for comparing different datasets. We note that LI is not a measure of homophily. LI naturally complements homophily measures by distinguishing different types of heterophilous graphs.
Empirical illustrations
In this section, we first characterize some existing graph datasets in terms of homophily and LI see which structural patterns are currently covered. Then, we show that LI, despite being very simple graph characteristic, much better agrees with GNN performance than homophily
4.1 Characterizing real graph datasets
We first look at the values of homophily and label informativeness for existing graph datasets. For this analysis, we choose several node classification datasets of different sizes and properties. Statistics of these datasets and values of all the measures discussed in this paper provided in Table 5 in Appendix E while Table Shshows selected results.
Recall that both node and edge homophily are sensitive to the number of classes and class size balance. Indeed, they may indicate high homophily levels for some heterophilous datasets. An
'Implementations of all the graph measures discussed in the paper and examples of their usage are provided this Colab notebook
7

---

extreme example is questions: hedge = 0.84, while more reliable adjusted homophily shows that the dataset heterophilous: hady 0.02. In fact, all binary classification datasets in [able be considered homophilous if one chooses hedge or hadee as the measure of homophily. In contrast, hadj satisfies the constant baseline property and shows that most of the considered binary classification datasets are heterophilous.
It is expected that datasets with high homophily badj also have high LI since homophily implies informative neighbor classes, For medium-level homophily, LI can behave differently: for in- stance,
Characteristics of some real graph Table 2:
datasets, see Table for the full results
Dataset
hedge
bodj
LI
and twitter- hate have similar homophily levels, while the neighbors in ogbn-arxiv are significantly more informative. For heterophilous datasets, IJ can potentially be very different, as we demonstrate in Section on synthetic and semi-synthetic data. How- ever, most existing heterophilous datasets have LI ~ O. This issue is partially addressed by new heterophilous datasets recently proposed [3]. For the proposed roman- empire dataset, LI = 0.11 and hadj = -0055. Thus, while being het- erophilous, this dataset has non-zero label informativeness. meaning that neighboring classes somewhat informative. We believe that datasets with more interesting connectivity patterns will be collected in the future.
lastfm-asia cora
18
0.87
0.86
0.74
7
0.81
0.77
0.59
ogbn-arxiv twitter-hate wiki wwich--aamers
40
0.65
0.59
0.45
2
0.78
0.55
0.23
5
0.38
0.15
0.06
2
0.55
0.09
0.01
actor
5
0.22
0.00
0.00
questions
2
0.84
0.02
0.00
Noman-empinn
18
0.05
-0.05
0.11
4.2 Correlation of LI with GNN performance
Recently, it has been shown that standard GNNs can sometimes perform well on non- non-hooophisous datasets [22 24 We hypothesize that GNNs can learn more complex relationships between nodes than just homophily, and they will perform well as long as the node's neighbors provide some information about this node. Thus, we expect LJ to better correlate with the performance of GNNs than homophily. To illustrate this, we use carefully designed synthetic and semi-synthetic data. First, it allows to cover all combinations of homophily levels and label informativeness. Second, we can control that only a connection pattern changes while other factors affecting the performance are fixed.
Synthetic data based on SBM model To start with the most simple and controllable setting, we generate synthetic graphs via variant of the stochastic block model (SBM) 13. In this model, the nodes are divided into C clusters, and for each pair of nodes j, draw edge between them with probability Pe()).e(5) independently of all other edges. Here c(i) is a cluster assignment for a node which in case corresponds to the node label yt-
We set the number of classes to C and the class size to = n/4. We define the probabilities as follows: Pt.j Po K if i = j. Pt.j P1 K jj 5, and pt.j P2 K otherwise. Here K > 0 and Note that the expected degree of any node (up to negligibly small term) K7 + pı Kl + 2p² Kl= = Kl.
we require Pa + P1 + 2p
This model allows us to explore various combinations of dataset characteristics. Indeed, po directly controls the homophily level, while the relation between P1 and enables us to vary LI. To see this, we note that the condition + j
gives two pairs of classes: (1, 4) and (2, Thus, p2 and P1 > 0, knowing the label of any neighbor from another class, we can uniquely restore the node's label. In contrast, for given Po, the case P1 P2 gives the smallest amount of additional information. The following proposition characterizes the covered combinations of LI and homophily; the proof follows from the construction procedure.
Proposition 1. As + x., the datasel characteristics of the proposed model converge to the following values (with high probability): hadj Po =l H(po.P1.P.PP where H(x)
log
Σ, Ir log(2.).
Thus, hadj ranges from -1/3 to and LT can be between 0 and If = 0, then we always have hadl 0; if hadi 1, then LI = 1. However, if LI = then either hadj - 1/3 hadi = 1.
8

---

-036
0145
Iabol informaivennnss
Iabre
002
0.73
631
0.
02
3.6
08
0.
0.0
0.1
0.7
0.3
0.1
05
0.
adjucted homaphily
adjusted homoonily
(a) Synthetic SBM graphs
(b) Semi-synthetic cora graphs from
Figure 2: Accuracy of GraphSAGE synthetic and semi-synthetic graphs
We generated graphs according to the procedure described above with the expected node degree of 10 and various combinations of Po- P1. Pg. Given the class labels, the features are taken from the four
largest classes in the cora dataset [38, 27 46 25]. We use the obtained graphs to train four popular
GNN models: GCN [16]. GraphSAGE [0]. GAT 43] and Graph Transformer (GT) [4].. In
total, we run more than 20000 experiments synthetic datasets for each of the four models. A detailed description of data generation, training setup, and hyperparameters used is provided in Appendix F.T
Figure 2a shows the results for GraphSAGE. can be seen that the performance is much more correlated with LI than with homophily. particular, when LI is high, GraphSAGE achieves good performance even strongly heterophilous graphs with negative homophily. We refer Appendix for additional visualizations.
Table 3: Spearman correlation be- tween model accuracy and charac- teristics of synthetic SBM datasets
Model
hadj
LIedge
The Spearman correlation coefficient between accuracy and I.I equal to 0.93, while between accuracy and adjusted ho- mophily equals 0.05. For other considered models, the differ- ence in correlation is also significant; see Table Note that due the balanced classes and degrees, all homophily measures give the same correlation, so we report only hadj.
GCN
0.19
0.76
GraphSAGE
0.05
0.93
GAT
0.17
0.77
GT
0.17
0.77
124 also argue that standard GNNs can perform well on certain heterophilous graphs. They construct semi-synthetic graphs by adding inter-class edges following different patterns to several real-world graphs, thus obtaining several sets of graphs with varying levels of homophily. Ma et al. [24] run experiments on these graphs and note that a standard GNN achieves strong performance on some heterophilous graphs.
Semi-synthetic data from (24
Ma et
We train GCN, GraphSAGE, GAT, and GT on the and citeseer graphs used in 24 and find that the models achieve strong perfor- mance when the graphs have high label informativeness. Training setup and hy- perparameters used in these experiments the same above and described Appendix F.1 The performance of Graph- SAGE on cora shown in Figure (b) In Appendix F3 we also show the perfor- mance GraphSAGE on the citeseer dataset. Table 4 shows the Spearman cor- relation coefficients between accuracy and various homophily measures LI for all
Table 4: Spearman correlation between model accuracy and characteristics of semi-synther datasets from [24
modifications of the
Model
hedge
Anadee
hatnas
hadj
L
cora
GCN GraphSAGE
-0.31
-0.31
-0.31
-0.31
0.72
-0.24
-0.24
-0.24
-0,24
0.78
GAT
-0.24
-0.25
-0.24
-0.24
0.77
GT
-0.23
-0.24
-0.23
-0.23
0.79
citeseer
GCN
-0.24
-0.24
-0.24
-0.24
0.76
GraphSAGE
-0.53
-0.53
-0.54
-0.54
0.51
GAT
-0.27
-0.27
-0.27
-0.27
0.75
GT
-0.19
-0.19
-0.19
-0.19
0.80

---

models and both datasets. The correlation coefficients for homophily measures are all negative, while for LI they are positive and sufficiently large. This again confirms that LI indicates whether graph structure is helpful for GNNs.
Additionally, conduct experiments with other datasets: Appendix F.4 describes the results for the LFR benchmark [17] and Appendix presents
presents an experiment on synthetic data from [22].
5 Conclusion
In this paper, we discuss how to characterize graph node classification datasets. First, we revisit the concept of homophily and show that commonly used homophily measures have significant drawbacks preventing the comparison of homophily levels between different datasets. For this, formalize properties desirable for a good homophily measure and prove which measures satisfy which properties. Based on our analysis, we conclude that adjusted homophily is better measure of homophily than the ones commonly used in the literature. We believe that being able to properly estimate the homophily level of graph is essential for the future development of heterophily-suiter GNNs: we need a characteristic that reliably differentiates homophilous and heterophilous graphs.
Then, we argue that heterophilous graphs may have very different structural patterns and propose new property called label informativeness (I.I) that allows one distinguish them. I.I characterizes how much information a neighbor's is label provides about node's label. Similarly to adjusted homophily, this measure satisfies important properties and thus can be used to compare datasets with different numbers of classes and class size balance. Through series of experiments, we show that LI correlates well with the performance of GNNs.
To conclude, we believe that adjusted homophily and label informativeness will be helpful for researchers and practitioners as they allow one to easily characterize the connectivity patterns of graph datasets. We also hope that new realistic datasets will be collected to cover currently unexplored combinations of hadj and LII Finally, our theoretical framework can be helpful for the further development of reliable graph characteristics.
Limitations We advise using adjusted homophily as reliable homophily measure since it the only existing measure having constant baseline and thus it dominates other known alternatives in terms of desirable properties. However, still violates minimal agreement, and monotonicity is guaranteed only for sufficiently large values of hadj- It is currently an open question whether there exist measures dominating adjusted homophily in terms of the satisfied properties.
Regarding LI, we do not claim that this measure is a universal predictor of GNN performance. We designed this measure to be both informative and simple compute and interpret. For instance, LI considers all edges individually and does not account for the node's neighborhood as a whole. As a result, LI can be insensitive some complex dependencies. Such dependencies can be important for some tasks, but taking them into account is tricky and would significantly complicate the measure. However, we clearly see that despite its simplicity, LI correlates with GNN performance much better than homophily.
Let us also note that our analysis of both homophily and LI is limited graph-label interactions. In future work, would be important to also analyze node features. Indeed, node features may have non-trivial relations with both graph and labels. For example, a graph can be heterophilous in terms of labels but homophilous in terms of node features or vice versa. These interactions may allow one understand the properties and performance of GNNs even better. However, analyzing feature-based homophily or informativeness can be much more difficult since the features can differ in nature, scale, and type.
Acknowledgements
We thank Yao Ma for sharing the semi-synthetic datasets from Ma et al. 22 that we used in Section 4.2 We also thank Andrey Ploskonosov for thoughtful discussions.
10

---

References
[1] Abu-EI-Haija B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan. G. Ver Steeg, and A. Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pages 21-29. PMLR, 2019.
[2] Ba, J. R. Kiros, and G. E. Hinton. Layer normalization, arXiv preprint arXiv: 1607.06400 2016.
[3] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics. Physics Reports, 424(4-5) 2006.
[4] E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2021.
[5] Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125-145, 2002.
[6] C. L. Giles, K. D. Bollacker, and S. Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM Conference on Digital Libraries, pages 89-98, 1998.
[7] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272. PMLR, 2017.
[8] M. Gösgens, A. Zhiyanov, A. Tikhonov, and L.. Prokhorenkova, Good classification measures and how to find them. Advances in Neural Information Processing Systems, 34:17136-17147, 2021.
[9] M. M. Gösgens, Tikhonov, and Prokhorenkova. Systematic analysis of cluster similarity indices: How to validate validation measures. In International Conference Machine Learning. pages 1799-3808. PMLR, 2021.
[10] W. L.. Hamilton, R. Ying, J.d Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 1025-1035, 2017.
(11) K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[12] D. Hendrycks and K. Gimpel. Gaussian error linear units (GELUs). arXiv preprint arXiv: 066666606041111 2016.
[13] P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109- 137, 1983.
[14] W. Hu, M. Fey, M. Zitikk, Y. Dong, H. Ren, B. Liu, M. Catasta, and Leskovee. Open graph benchmark: Datasets for machine learning graphs. Advances in Neural Information Processing Systems, 33:22118 18-12133, 2020.
[15] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
[16] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[17] A. Lancichinetti, S. Fortunato, and F. Radicchi. Benchmark graphs for testing community detection algorithms. Physical review E, 78(4):046110, 10, 2008
[18] J. Leskovee, J. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. Proceedings of the eleventh ACM SIGKDD International Conference Knowledge Discovery in Data Mining, pages 177-187, 2005.
11

---

[19] D. Lim and A. R. Benson. Expertise and dynamics within crowdsourced musical knowledge curation: A case study of the genius platform. In Proceedings of the International AAAI Conference Web and Social Media, volume 15, pages 373-384, 2021.
[20] D. Lim, F. Hohne, X. Li, S. L. Huang, V. Gupta, O. Bhalerao, and S. N. Lim. Large scale learning on non homooooopsiouus graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.
[21] R. Liu, S. Cantürk, F. Wenkel, S. McGuire, X. Wang, A. Little, L. O'Bray, M. Perlmutter, B. Rieck, M. Hirn, et al. Taxonomy of benchmarks in graph representation learning, In The First Learning on Graphs Conference, 2022.
[22] S. Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X.-W. Chang, and D. Precup. Revisiting heterophily for graph neural networks. In Advances in Neural Information Processing Systems, 2022.
[23] S. Luan, C. Hua, M. Xu, Q. Lu, J. Zhu, X.WW Chang, J. Fu, J. Leskovec, and D. Precup. When do graph neural networks help with node classification: Investigating the homophily principle on node distinguishability. arXiv preprint arXiv:2304. 14274, 2023.
[24] Y. Ma, X. Liu, N. Shah, and J. Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022.
[25] A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2):127-163, 2000.
[26] M. Molloy and B. Reed. A critical point for random graphs with given degree sequence. Random Structures & Algorithms, 6(2-3):161-180, 1995.
[27] G. Namata, B. London, L. Getoor, B. Huang, and U. EDU. Query-driven active surveying for collective classification.. 10th International Workshop on Mining and Learning with Graphs, volume 8, page 1, 2012.
[28] M. E. Newman. Mixing patterns in networks. Physical Review (7))), 2003.
[29] M. E. Newman. Equivalence between modularity optimization and maximum likelihood methods for community detection. Physical Review E, 94(5), 2016.
[30] M. E. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, 69(2), 2004.
[31] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, perf-peeformance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
[32] H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. International Conference on Learning Representations, 2020.
[33] O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova. A critical look the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, 2023.
[34] L. Prokhorenkova and A. Tikhonov. Community detection through likelihood optimization: in search of a sound model. In The World Wide Web Conference, pages 1498 1508, 2019.
[35] B. Rozemberezki and R. Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors parametric models. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1325-13344 2020.
[36] B. Rozemberezki and R. Sarkar. Twitch gamers: dataset for evaluating proximity preserving and structural role- node embeddings. arXiv preprint arXiv:2101.03091 2021.
[37] B. Rozemberczki, C. Allen, and R. Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021.
12

---

[38] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher. and T. Ehassi-Rad. Collective classifica- tion in network data. Al Magazine, 29(3):93-99 93, 2008.
[39] O. Shchur, M. Mumme, A. Bojchevski, and Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, 2018.
[40] Y. Shi, Z. Huang, S. Feng, H. Zhong, W. Wang, and Y. Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509 2020.
[41] Suresh, V. Budde, J. Neville, P. Li, and J. Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
[42] Tang, Sun, C. Wang, and Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 807-816, 2009.
[43] Veličković, G. Cucurull, A. Casanova, A. Romero, Liö, and Y. Bengio. Graph Attention Networks. International Conference on Learning Representations. 2018.
[44] M. Wang, D. Zheng, Z. Ye, Q. Gan, M. Li, X. Song. J. Zhou, C. Ma, L. Yu, Y. Gai, al. Deep graph library: A graph-centric, highly-perfrrmat package for graph neural networks. arXiv preprint arXiv: 1909.01315, 2019.
[45] K. Xu, W. Hu, J. Leskovec, and Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[46] Z. Yang, W. Cohen, and R. Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pages 40-48. PMLR, 2016.
[47] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna. GraphSAINT: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020.
[48] J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
[49] J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra, Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 35, pages 11 1168-11176, 2021.
13

---

A Random configuration model
Numerous random graph models have been proposed reflect and predict important quantitative and topological aspects of real-world networks [3]. The simplest model is the Erdós- Rényi random graph, iee. we assume that G is sampled uniformly at random from the set of all graphs with n nodes and [E] edges. However, this model is known to be not good descriptor of real-world networks since its Poisson degree distribution significantly differs from heavy-tailed degree distributions observed in real-world networks. A standard solution is to consider random graph with given degree sequence [26]: a graph is sampled uniformly from the set of all graphs with a given degree sequence.
A configuration model, which we assume throughout the paper, is defined as follows. To generate a graph, we form set containing d(()) distinet copies of each node and then choose a random matching of the elements of A. In this case, self-loops and multiple edges may appear. Under some conditions, the obtained graph is simple (i.e., does not contain self-loops and multiple edges) with probability 1 o(1) (26].
Let also note that there is another model that is similar the one discussed above but can be easier to analyze. To obtain graph with given expected degree sequence [5], we take the degree sequence from the observed graph and say that the number of edges between and j follows a Poisson distribution with the mean d(t)d()) if 7 and the expected number self-loops for a node is d(s) ATT This model does not preserve the exact degree sequence but has it in expectation. Note that usually d(i)d(j) < E]. so multiple edges rarely appear. Asymptotically, this model is similar to the configuration model, but graph with given expected degree sequence is easier analyze theoretically. In our analysis, we assume the configuration model, so we have to track the error terms carefully.
2|
B
Analysis of homophily
B.1
Class homophily
Recall that class homophily is defined as 20]
Σ
Hu E N(v): : Yu = yuHl
Relass
Viga
72g
C
Evy. d(u)
1
Here the first term inside the brackets is the fraction of edges that go from a particular class to itself. The second term ng/n p(k) is the null expected fraction. We note that p(k) is the expected fraction we assume the Brdōs-Rény' model. Indeed, for this model, all edges have equal probability, and thus the expected fraction of neighbors of class k is proportional the size of this class, However, as mentioned above, the Erdös-Rényi null model has certain disadvantages since it does not take into account node degrees. This may lead incorrect estimates of null probabilities for degree-imbalance imbalanced classes, as shown in the example below
Proposition 2. Assume that we have two classes of size n1/2. Further, assume that the expected degrees of nodes in the first class are equal to d, while nodes in the second class have expected degrees ld for some 1 >> 1. Then, if edges are added independently of the classes, the expected value of heless
1 1+1
Ehilass
2 Thus, for randomly connected nodes we get Ehtlass + 1/2 as 1 DC.
Proof. We need to compute the expected number of intra-class edges for each class. For the first class, multiply the number of nodes by the degree of each node and by the probability of particular
'For simplicity, in these statements, we use the random graph model with a given expected degree sequence as it allows for simpler illustrations. For the configuration model, the error terms can be tracked similarly to the proofs in Sections B.4 C.I
14

---

edge to go to the same class: d. nd nd n(i+1)d 2(+1))
Normalizing by the sum of the degrees, we get (411) Similarly, for the second class, the normalized number of the intra-class edges is (=1] Hence,
Ehelass
1+1 2 + [+1 2
1+1 2
This proposition shows that class homophily does not satisfy the constant baseline property.
As discussed in Section 2.3 we remove the [-]+ operation from the definition of class homophily, obtain measure that does satisfy the asymptotic constant baseline. Following Section 2.5 call this measure balanced adjusted homophily as it adjusts balance homophily for chance:
Σ Huu E (()): : yo = yoHl
Nhol C-1
L
Vi
72k n
Chhat -1
Evy. d(v)
C-1
Proposition 3. Assuming that there are C classes and the graph is generated according to the model with given expected degrees, we have El
Proof. Let us denote the sizes of the classes by f.,..... TC.. Recall that we use the notation D3- E Evy.=t d(v). easy to see that
1
1 1-1 Dj Σ, =C-
D:
Ehbat
B.2
Constant baseline
There are several possible ways to formalize the constant baseline property. In the literature g 9] this property is often formalized as follows: assuming some randomized model, the expected value of a measure should be equal to some constant. For homophily measures, this corresponds to the following definition.
Definition 5. A homophily measure h has constant baseline if for G generated according to the configuration model we have (G) = Chase for some constant Chase-
This property is very strict minor variations in the definition of the model (e.g., different alternatives of the configuration model discussed Appendix A may lead to negligibly small error terms preventing us from getting exactly the same constant Cbase- Thus, in the main text, use the alternative Definition 2 This definition weaker the sense that we allow asymptotically negligible deviations from the constant Cbase- On the other hand, our definition is somewhat stronger since also require the concentration of the value around its expectation. In that sense, our definition is stronger than the asymptotic constant baseline defined in (8]
B.3 Monotonicity property
In this section, we discuss how one can define monotonicity for homophily measures.
First, 1et us revisit how monotonicity is defined for measures used in other areas. In general, the monotonicity property is defined follows: an object 3' definitely more similar an object A than B, then the similarity between B' and A should be larger than between B and A. The only problem is to define what means be "definitely more similar". D. the monotonicity property was introduced for cluster similarity measures. Such measures evaluate how close two partitions of same set of items are. To formally define the concept of more similar partitions, Gösgens et al. 9 use the concept of perfect splits and perfect merges such transformations of partition B that make more similar to Later, monotonicity was defined for classification evaluation measures that compare the predicted labels for set of items with the reference ones [8] Here it is casier to
15

---

formalize what it means that a labeling B' is definitely more similar to the reference labeling than B. Indeed, if we consider a labeling B and change one incorrect label to the correct one, then it becomes closer to the reference labeling.
Now, let return homophily measures. Such measures evaluate the agreement between a graph and a labeling of its nodes. To define monotonicity, we need such transformations that make graph and labeling definitely more similar. Since the problem not symmetric, we can either rewire edges or relabel nodes. Regarding relabeling of nodes, we may say that taking perfectly heterophilous node (that not connected to any node of its class) and relabeling in such a way that it becomes perfectly homophilous (which is only possible when all its neighbors belong to one class) should make the graph and labeling more similar to each other. Regarding the edges, we may say that taking an edge that connects two nodes of different classes and rewiring it to connect two nodes of the same class should increase the measure. However, rewiring edges may also affect the graph structure in a non-trivial way (degree distribution, diameter, etc.).
In this paper, we follow the edge rewiring approach, and thus our definition aligns well with edge- wise homophily measures and with previous works on classification and clustering performance measures
If we consider edge-wise wise measures (that can be defined in terms of the class adjacency matrix) and directly follow the definition of monotonicity in [8 9.. definition would be as follows: homophily measure is monotone if it increases when we decrement Cıy and Cys by one and increment either Ga Cjj by two for * j- This condition corresponds to taking an edge with yu * yo and changing Yu. to Yo or vice versa.
However, an important property that has to be taken into account when discussing monotonicity for homophily measures is the fact that such measures are used to compare different graph datasets, in contrast classification evaluation measures that compare the agreement between predicted labelings with a fixed given reference labeling. This means that for classification measures, monotonicity and constant baseline are critical for fixed numbers of classes and elements. In contrast, homophily measures have to be comparable across datasets with different sizes and numbers of classes. For instance, balanced accuracy has constant baseline with the expected value of C which is sufficient for classification evaluation but is a drawback for measuring homophily. Because of this, we do not consider the standard definition of monotonicity as it is restricted to a fixed number of classes only. Instead, we introduce tolerance to empty classes, and based on that, we introduce a stronger version of monotonicity where allow separate edge additions deletions. In fact, our definition of monotonicity (Definition 4 is similar to strong monotonicity in 8 9] but also requires empty class tolerance since comparing measures across different numbers of classes is crucial.
B.4 Proof of Theorem 1
The fact that adjusted homophily is empty class tolerant directly follows from its definition: an empty class does not contribute to the numerator or denominator of hadh.
Maximal agreement also straightforward: we have hadge - Ee (2 S
Ee Ek=1 (2)(2)))) with equality if and only if all edges are homophilous.
Minimal agreement is not satisfied since the value -I D2/(211)2
I- DE/[2/ can be different for different
datasets. Thus, perfectly heterophilous datasets may get different values, which also causes some monotonicity violations for small values of hadj.
Asymptotic constant baseline of adjusted homophily Now, let formulate and prove the constant baseline property.
Proposition 4. Let G be graph generated according to the configuration model. Assume that the degree-weighted distribution of classes is not very unbalanced, ie., that 1 - E p(k)² > 1/VE. Then, [haaj] S & with probability 1 - o(1) for some & = ((( + 0 as [P| - Dc.
Proof. Let us first analyze the numerator of hadj which we denote by kmod (since it corresponds to the network's s modularity see Appendix B.5
16

---

Let & denote the number of intra-clas cltra-class edges in graph constructed according to the configuration model. We may write:
D ΣΣ
1
where 1i, indicates that an endpoint of some node with class k is connected to another endpoint of class k. Note that the probability of this event is -18-11 Thus, have
C
D
C
DD 1)
DJ. 4
1 E
Emood
E
E
2
=
(4)
Now, let us estimate the variance of the number of intra-class edges. We may write:
C
D2
Var(2() E((2))² (E((2))
Σ
1ike
-(E2E)²
(Dk)
1
D2
Dx -
= E + Σ
2.
2
2
E
2 E - 3
k=1
C
DE -
Dt -1
Σ
2D&Di
(E22))
2
2 -3
k=11=k41
C
D O
= =F((g) + Σ
E
2D + O(D,D, + D2D?)
C
D +((k) 2
2
k=1
(
C
O + D&
E(EE)
ΣΣ Σ
E
E
k=11=k+1
E(E)) +0))) = O(
Let = ((EE) be any function such that - 00 as E
- co. Using the Chebyshev's 's inequality
and 4). we get:
P
[mmodd
40
=P
-P
-P((nood
Edinod
+0
E
E
[
Var(E) E
=0
o(1).
|ER
Recall that hadj 1-56 p(k)2 Since we have p(K)2 > 1/VE and [mmod
< with VE
probability 1 - o(1,, choose such slowly growing tp that hadj VB(1- B(N)2) with probability 1 - o(1).
o(1)
Monotonicity of adjusted homophily mophily and finish the proof of Theorem
Finally, let us analyze the monotonicity of adjusted ho-
Recall that homophily measure is monotone if it is empty class tolerant, and it increases when increment a diagonal element by 2 (except for perfectly homophilous graphs) and decreases when we increase Cij and Cjs by one for j (except for perfectly heterophilous graphs).
Empty class tolerance is clearly satisfied for adjusted homophily, so us now analyze what happens when we increment a diagonal element or two (symmetric) off-diagonal elements.
17

---

Let us denote N := 2) 04 == E, Cij. Then, we have p(t) N
Thus, we have to prove that the
Σ af
measure is monotone when Radj > (E, (Eaa+tn))
Using the notation with class adjacency matrix, adjusted homophily can be written as follows:
N NE CH Σ,
a
hadj
N E.
To check whether the measure increases when we increment diagonal elements, let us compute the derivative w.r.t. Cl-k for some k:
abadj (E, Ga + N 20x) (N²-
- _E, (2N - 2ax) (N E, Ci Σ. at)
Ockk Let us simplify the numerator:
(N2 Σ; n??
(N2 Σ, at)
Σ Ci N -2ax ( N2 (N-- Σ d
N N ci - - a3
(2N 20x)
N3 - 2N
Σ 4o Σ of N
Σ Go + N Σ Cui + N E ag.
For monotonicity, we need the derivative to be positive, i.e.,
N3 + 2a N Σ N N a > 2N2ax as + Σ Σ
2 d + +N2 Σ
Ci.
8
Let us denote by D the sum of all off-diagonal elements, i.c., D = N Σ; Cz.. Then, we can rewrite the above condition as follows:
N2 D + D Σ at > 2NaxD,
2 Σ 0 2No
The latter equality holds since
N Σ 2 > N + o 2 2Na..
Thus, hadj increases when we increment a diagonal element.
To whether the measure decreases when increment the off-diagonde elements, let us compute the derivative of the measure w.r.t. Oki (which is equal to qK)) for k + 1:
ahadi Ocgt
(2 cu 2ax 2aj) (N² E.a?)
(4N 2a 2as)) (N Σ, Cu - -.a?)
(N2 - 2, a))
-N x²)²
The numerator is:
Σ Ca 2ak
201 -2ar)
N22 12- Σ a {A² -(4N -2x -201) N N
Cii Σ at
2(xx + +a))N² - 2 - Ca Σ a7 2N Σ Gia + 2(ax +a)N Σ Cit + 4N Σ
03
For monotonicity, we need the following inequality:
(ax + Nz
Σ C4s
Σo² of+ N2
Ecs > (ax a)N Σ Cis + 2N
Σ
of
(5)
This inequality is not always satisfied. Indeed, both on + at and E, Ca can be small. Let us note, however, that the inequality is satisfied if hadj is large enough. Indeed, the sufficient condition for (5)
Σ ca Σ at +N2
2N Σ a
18

---

This is equivalent to the following inequality for hady:
N,, C4 - -,, N N [. "f + N2 2i
N2)
hadj
N Ej of
N E, ag
[Ex at)²
E, C az +N2)
(N² Σ, a (E of +
[ E, Note that have E, (E (E,
Thus, bady is monotone if its values are least
0.5,
so when hadj > 0.5 always monotone.
However, non-monotone behavior may occur when the numerator of hadi is small. This undesirable behavior is somewhat expected: due to the normalization, hadj satisfies constant baseline and maximal agreement but violates minimal agreement. Since minimal agreement does not hold, one can expect monotonicity be violated for small values of hod).
For instance, we can construct the following counter-eas counter-example to monotonicity. Assume that we have four classes (0, 1, 2, 3) and non-zero entries of the class adjacency matrix are 623 C32 M, C33 = 2. Then, the adjusted homophily is:
2(2 2) M (M + 2)
-2
-
badh (2M 2) - M - (M + 2) 2M + 4M
M +
Now, we increment the entries Co1 and C10 by 1. The new adjusted homophily is:
2(2M + 4) - M - (M + 2)² - 2
-2M² +
1- M
Kadj (2M 4)2 M (M + 2) 2
2M 12M + 10 M +
We disprove monotonicity if we have Mads > hadj. i.e..
1 - M - -M
M + 5 M +
M M > -M² 5M,
2> 4M,
which holds for all M 2 1.
B.5 How homophily and modularity are related
Modularity Modularity is arguably the most well-known measure of goodness of a partition for graph. first introduced in [30) and is widely used in community detection literature: modularity is directly optimized by some algorithms, used as a stopping criterion in iterative methods, or used metric to compare different algorithms when ground truth partition is available. The basic idea is to consider the fraction of intra-community edges among all edges of G and penalize it for avoiding trivial partitions like those consisting of only one community of size n. In its general form and using the notation adopted in this paper, modularity is
E (1((u,)) F Vn yo -FFF)
where is a random number of intra-class edges in a graph constructed according to some underlying random graph model; y is the resolution parameter which allows for varying the number of communi- ties obtained after maximizing modularity. The standard choice is 7 = 1, which also guarantees that the expected value of modularity is 0 if graph is generated independently of class labels according to the underlying model.
Usually, modularity assumes the configuration model. In this case, we have E Σg Dx(Ex-1) R
2(2
En DE. giving the following expression:
TE
Hlu v) E E : yu = NoHl
D.
Bmood
E
4
We refer Newman 29. Prokhorenkova and Tikhonov and its usage in community detection literature.
for more details regarding modularity
19

---

Relation to homophily While modularity measures how well a partition fits given graph, ho- mophily measures how well graph edges agree with the partition (class labels). Thus, they essentially measure the same thing, and modularity can be used as homophily measure. Indeed, it is easy to see that modularity coincides with the numerator of adjusted homophily, see 2 Hence, adjusted homophily can be viewed as normalized version of modularity. Note that for modularity, normal- ization is not crucial as modularity usually used to compare several partitions of the same graph. In contrast, homophily is typically used to compare different graphs, which is why normalization is essential.
C Analysis of label informativeness
C.1 Proof of Theorem 2
In this section, we prove Theorem 2 Let us give a formal statement of this theorem.
Theorem 2. Assume that [E] - oo as + oc. Assume that the entropy of p(.) is bounded from
below by some constant. Let Puain ming p(k). Assume that Punn >> C/ /IE as + Do. Let
& E(n) be any function such that > pmon VlEl and o(1) as - oc. Then, with probability
C
1 - o(), we have [TJ] S Ke = o(1) for some constant K > O.
Proof. Recall that
LI Ee p(C1, 62) log p(c).c)) p(cr)p((s))
F(c log
Thus, for each pair 4, we need to estimated
p(k: 1). Let us denote:
E(k,() = Σ
1 1[ v) E,yu k 1}.
u=1 v=1
so we have p(k:,) 1) ((k.)) F
As before, we use the notation D3 = Evmy= d(v). First, consider the case * Let us compute the expectation of E(k; l):
Dr for k +
EE(k,t) 2 - DD(D, 1) 2 -1
EE(k
Now, we estimate the variance. Below, 1i,j indicates that two endpoints are connected.
VarE(k,1) = E
10
(EE(K,
E)(k,1) + DeDi(Ds - 1)( (E)(K,
(2 - 1) 33
= =E((k,)+ (D. + +Di) (D.
DE
=0
E
E
Similarly,
D
D3
Var = E
1ig
(EE(K, EE(K, A:) + O
0
E
E
From Chebyshev's inequality, we get:
P ((E(K, 1) - EE(k, 0)l > sEE(k, 1)) = = Dre = =0
P
E
=
20

---

Thus, with probability 1 o(1), P (()E(k,1) EE(k, 1)1 < <EE(k, ()) for all pairs of classes. In this case,
kx, p(k, log(1 11 + O(e))
LI
O
log p(k
C.2
Alternative definition
Recall that in Section 3 we define the label informativeness in the following general form: LI == [ye, // (yg). Then, define LLedge. say that & and 1) are two endpoints of edge sampled uniformly at random. Another possible variant is when we first sample a random node and then sample its random neighbor. The probability of edge becomes
1 (1e = c1, Ur =02
c2)
Σ
nd(u)
(u,))E
In this case, H (yE) is the entropy of the distribution p(c), H (yn) is the entropy of p(c). Thus, obtain:
Enyoo p(c,, log p())e))
LInode
p(cr)p(e))
Pcc)log(((
In this paper, we mainly focus on Lleage and refer to it as LI for brevity. First, this measure is conceptually similar to adjusted homophily discussed above: they both give equal weights to all edges. Second, in our analysis of real datasets, we do not notice substantial difference between LLedge and LInode in most the cases, see Table However, these measures can potentially be different, especially for graphs with very unbalanced degree distributions (in LInode averaging is over the nodes, so all nodes are weighted equally, while in LTedge- averaging is over the edges, so more weight is given to high-degree nodes). The choice between Leedge and LI may depend particular application.
D Additional related work
In the aspect of characterizing graph datasets, our work is conceptually similar recent paper by Liu et al. (21] In this paper, the authors empirically analyze what aspects of graph dataset (e.g.. node features or graph structure) influence the GNN performance. Liu et [21] follow data-driven approach and measure the performance change caused by several data perturbations. In contrast, we follow a theoretical approach choosing graph characteristics based only on the label-structure relation. Additionally, general-purpovt graph analysis (beyond graph ML). Similarly to (1I) we believe that the proposed characteristics can help in the selection and development of diverse future graph benchmarks.
characteristics are very simple, model agnostic, and can be used for
Similarly our work, several papers note that homophily does not always reflect the simplicity of dataset for GNNs, and standard GNNs can work well on some heterophilous graphs. To address this problem, Luan al. (22) propose metric called aggregation homophily that takes into account both graph structure and input features. We note that the aggregation homophily is based on proposed LT is a simple and
particular aggregation scheme of the GCN model. In contrast, intuitive model-agnostic measure. An additional advantage of LI is that it is provably unbiased and can be compared across datasets with different numbers classes and class size balance. Another feature-based metric was very recently proposed by Luan al. [23] It is called Kernel Performance Metric (KPM) and reflects how beneficial is a graph structure for prediction. Ma et al. (24] also observe that some heterophilous graphs are easy for GNNs. To analyze this problem, they propose measure named cross-class neighborhood similarity defined for pairs of classes. While this measure an informative tool to analyze particular dataset, it does not give single number to easily compare different datasets.
Finally, let us note that Suresh et al. 41 use 2 as measure of graph assortativity (homophily). The authors show that the homophily level varies over the graph, and the prediction performance of GNNs correlates with the local homophily. They use these insights to transform the input graph and
21

---

get an enhanced level of homophily. In future work, it would be interesting to see whether additional benefits can be obtained using label informativeness instead of homophily.
E
Characterizing real graph datasets
E.1
Datasets
Cora, citeseer, and pubmed 26 27 46 are three classic paper citation network benchmarks.
For cora and citeseer labels correspond to paper topics, while for pubmed labels specify the type of diabetes addressed in the paper. Coauthor-cs and paauthor-physiiee
[39] are co-authorship networks. Nodes represent authors, and two nodes are connected by edge if the authors co-authored a paper. Node labels correspond to fields of study. Amazon- computers and amazon- amazon-photo [39] co-purchasing networks. Nodes represent products, and edge means that two products are frequently bought together. Labels correspond to product categories. Lastfm-asie faeffiaaaiaaaaa is a social network of music streaming site LastEM users who live in Asia 35 Edges represent follower relationships, and labels correspond to user's nationality. In the facebook (37] graph nodes corre- spond to official Facebook pages, and links indicate mutual likes. Labels represent site categories. In the gi tituub [37] graph, nodes represent GitHub users and edges represent follower relationships. A binary label indicates that user is either web or machine learning developer. Ogbn- Ogbn-arxiv and Ogbn-products [14] are two datasets from the recently proposed Open Graph Benchmark. Ogbn-arxiv is citation network graph with labels corresponding subject areas. ogbn-products is co-purchasing network with labels corresponding to product categories. Actor [42 32] is a popular dataset for node classificatiion in heterophilous graphs. The nodes correspond to actors and edges represent co-occurrence on the same Wikipedia page. The labels are based on words from an actor's Wikipedia page. Flickr 47 a graph of images with labels corresponding to image types. Deezer-europe 35 is user network of the music streaming service Deezer with labels representing a user's gender. twitch-de and twitch-pt (77 are social network graphs of gamers from the streaming service Twitch The labels indicate if streamer uses explicit language. Genius [19) twitch swittch-gamers gamers (36), arxiv-year [14, snap- maap-patents [18), and wiki (20] are re- cently proposed large-scale heterophiious datasets. For the wiki dataset we remove all isolated nodes.
Roman Roman-empire, amazon -ratinnrrannns...... minesweeper, workers, and questions ionss (3 are recently pro- posed mid-scale heterophilous datasets. We additionally construct one more binary classification graph switter-hate This graph is based on data from Hateful Users on Twitter dataset on Kaggle [
The labels indicate if user posts hateful messages not. We remove all the unlabeled nodes from the graph and use the largest connected component of the resulting graph.
We transform all the considered graphs to simple undirected graphs and remove self-loops.
E.2 Dataset characteristies
Dataset characteristics are shown in Table This table extends Table the main text. It can be seen that the typically used homophily measures - hedge and Anode - often overestimate homophily levels, since they do not take into account the number of classes and class size balance. This is particularly noticeable for datasets with two classes. fact, according to these measures all binary classification datasets in our table are homophilous. In contrast, hadj corrects for the expected number of edges between classes and shows that most of the considered binary classification datasets are actually heterophilous (github and twitter- hate being the exceptions).
As for label informativeness, can be seen that on real heterophilous datasets is typically very low (with the exception of coman-empiin dataset). This is in contrast to synthetic datasets used for experiments in 22 24, which sometimes exhibit a combination of low homophily and high label informativeness. High label informativeness of these datasets leads to strong GNN performance on them despite low homophily levels.
Let us note that edge and node label informativeness differ in how they weight high/low-degre nodes. For node label informativeness, averaging is over the nodes, so all nodes are weighted equally. For
7 Twi t de and twitch- ppt are subgraphs of larger dataset twitch-gamers. We report characteristics for all them since they have different sizes, edge density, and may have different structural propertics. https: / /wwww kaggle. htt.c///ttttttt/mmmaeroereaa/aaa
users- on-twitter
22

---

Table 5: Dataset characteristics, more homophilous datasets above the line
Dataset
[6]]
C
Redge
Anode
Relass
hadi
Lledge
LInode
cora
2708
5278
7
0.81
0.83
0.77
0.77
0.59
0.61
citeseer
3327
4552
0.74
0.72
0.63
0.67
0,45
0.45
pubmed
19717
44324
0.80
0.79
0.66
0.69
0.41
0.40
coauthor-cs
18333
81894
0.81
0.83
0.75
0.78
0.65
0.68
coauthor-physics
34493
247962
5
0.93
0.92
0.85
0.87
0.72
0.76
amazon-conpuleer
13752
245861
10
0.78
0.80
0.70
0.68
0.53
0.62
amazon-photo
7650
119081
0.83
0.85
0.77
0.79
0.67
0.72
lastfin-asia
7624
27806
0.87
0.83
0.77
0.74
0.68
faccbook
22470
170823
0.89
0.88
0.82
0.82
0.62
0.74
github
37700
289003
0.85
0.80
0.38
0.38
0.13
0.15
twiteerhatee
2700
11934
0.78
0.67
0.50
0.55
0.23
0.51
ogbn-arxiv
169343
1157799
40
0.65
0.64
0.42
0.59
0.45
0.53
ogbn-products
2449029
61859012
0.81
0.83
0.46
0.79
0.68
0.72
actor
7600
26659
0.22
0.22
0.01
0.00
0.00
0.00
flickr
89250
449878
0.32
0.32
0.07
0.09
0.01
0.01
deczer-europe
28281
92752
0.53
0.53
0.03
0,03
0.00
0.00
twitch-de
9498
153138
0.63
0.60
0.14
0.14
0.02
0.03
twitch-pt
1912
31299
0.57
0.59
0.12
0.11
0.01
0.02
twitch-gamers
168114
6797557
0.55
0.56
0.09
0.09
0.01
0.02
genius
421961
922868
0.59
0.51
0.02
-0.05
0.00
0.17
arxiv-year
169343
1157799
0.22
0.29
0.07
0,01
0.04
0.12
snap-patents
2923922
13972547
0.22
0.21
0.04
0.00
0.02
0.00
wiki
1770981
242605360
0.38
0.28
0.17
0.15
0.06
0.04
roman-cmpire
22662
32927
18
0.05
0.05
0.02
-0.05
0.11
0.11
amazon-ratings
24492
93050
5
0.38
0.38
0.13
0.14
0.04
0.04
minesweeper
10000
39402
2
0.68
0.68
0.01
0.01
0.00
0.00
workers
11758
519000
0.59
0.63
0.18
0.09
0.01
0.02
questions
48921
153540
0.84
0.90
0.08
0.02
0.00
0.01
1:64
0.94
accurocy
6.75
0.72
adjusbad hamaphily
informativvness
Figure 3: Dependence of GraphSAGE accuracy on homophily and label informativeness for synthetic
SBM graphs
edge label informativeness, averaging is over the edges, which implies that high-degree nodes make larger contribution the final measure. is natural expect that for high high-degree nodes the amount of information from each individual neighbor is lower than for low-degree nodes since neighbors of high-degree nodes are expected to more diverse and closer the "average" distribution. Thus, is natural to expect edge label informativeness to often be smaller than node label informativeness, which agrees with Table Note that for most of the real datasets, the values of these two measures rather close, with twitter hate, genius, and arxiv-year being the exceptions.
23

---

F Correlation of LI with GNN performance
F11 Experimental setup
For our experiments on synthetic data, we select 208 combinations of homophily and LI. For each combination, we generate 10 random graphs with the corresponding homophily and LI values using the SBM-based model described in Section 4.2 Each graph has 1000 nodes (250 nodes for each class) and the expected node degree of 10. Node features are taken from the four largest classes in the cora dataset (each of these four classes is mapped to one class in the synthetic data, and node features are sampled randomly from the corresponding class). For each synthetic graph, we create 10 random 0016/55%/555 rrain/aliiattoontess splits. Thus, for each model, we make 10 runs per graph or 100 runs per homophily/LL combination, totaling 20800 runs.
We use GCN 16. GraphSAGE [TO) GAT 43 and Graph Transformer (GT) as repre- sentative GNN architectures for our experiments. For GraphSAGE, we use the version with the mean aggregation function and do not use the node sampling technique used in the original paper. For all models, we add two-layer MLP after every graph neighborhood aggregation layer and further augment all models with skip connections [1]] layer normalization (2), and GELU activation functions [12. For all models, we use two graph neighborhood aggregation layers and hidden dimension of 512. We use Adam [I5] optimizer with a learning rate of 3 10-5 and train for 1000 steps, selecting the best step based on the validation set performance. We use a dropout probability of 0.2 during training. Our models are implemented using PyTorch [3 and DGL
F.2 Synthetic data based on SBM model
In Figure 2a of the main text, we show the results for GraphSAGE. In Figure 3 we additionally plot the dependence of GraphSAGE accuracy homophily and label informativeness. It can be seen that the model's accuracy is much more correlated with label informativeness than with homophily. The results for GCN, GAT, and GT presented in Figures 4 performance of all models generally follows the same pattern, and LI is a better predictor of model performance than homophily. In particular, when LI is high, all models achieve high accuracy homophily is negative. Recall that we provide Spearman correlation coefficients between model accuracy and adjusted homophily or LI in Table 3
3 and 6 respectively. As be seen, the
F.3 Semi-synthetic data from
24
We use the same experimental setting described above for training GCN, GraphSAGE, GAT, and GT on modifications of the cora and citeseer graphs from [24). The results for GraphSAGE and cora provided in Figure 2h of the main text. The results for GraphSAGE and citeseer are shown in Figure 7
F.4 Synthetic data based on LFR model
We also experiment with the LFR random graph model, which well-known benchmark for community detection (we treat communities as node labels). We generated 39 LFR graphs with the mixing parameter values evenly spaced between 0.025 and 0.975. Each graph has 1000 nodes and 5 communities. The maximum community size 350, and the minimum community size is 100. The average node degree is 10, and the maximum node degree 50. Note that homophily monotonically changes with the mixing parameter, while LI is U-shaped. Similarly to our experiments with SBM, we measure the Spearman corre- lation coefficient between accuracy and LI/ / hadj, see Table 6 We see that LI is a better predictor of GNN performance than homophily.
Table 6: Spearman correlation be- tween model accuracy and charac- teristics of LFR graphs
Model
hadj
L Leege
GCN
0.79
0.96
GraphSAGE
0.68
0.99
GAT
0.77
0.97
GT
0.77
0.97
24

---

2.00
label infommtreees
Jabre
2.3
-032
631
01 52
25
08
00
1.0
62
61
00
01
03
04
05 56
07
05
09
adjucted homaphily
adjucted homophily
Figure 4: Accuracy of GCN synthetic SBM graphs
Figure 5: Accuracy of GAT on synthetic SBM graphs
L9992 Informetreett
23
186
44
lebeel
0.55
-0.2 -01
26
08
09
10
0.0
0.1
6:5
adjusted homophiyy
adjusted homophily
Figure 6: Accuracy of GT synthetic SBM graphs
Figure 7: Accuracy of GraphSAGB: on semi-
synthetic citeseer graphs from 24
F55 Synthetic data from 22
Luan al. (22 have shown that GNNs achieve strong performance certain heterophilous graphs. Again, this phenomenon can be explained by the high label informativeness the het- erophilous graphs used for these experiments.
The authors investigate how different levels of homophily affect GNN performance. They find that the curve showing the dependence GNN performance on edge homophily (as well on node homophily) is U'-shape:: GNNs show strong results not only when edge homophily high, but also when edge homophily is very low. Our label infor- mativeness explains this behavior. We use the same data generating process in 22 and find that the curve of la- bel informativeness depending on edge homophily is also U-shaped (see Figure B). Thus, the datasets from (22). GNNs perform well exactly when label informativeness high regardless of edge homophily. The U-shape of the label informativeness curve is not surprising: when edge homophily is very low, knowing that node has neighbor of a certain class provides us with information that this node probably does not belong to this class.
label Informatienesss
0.10
0.08
0.06
0.04
0.0
0.1
0.2
0.4
edge homopily
Figure Label informativeness depend- ing edge homophily on synthetic graphs from 22
25

---

0.5 Spearman Correlation: 0.85
Spearman Correlation: 0.78
1.0
Test ROC AUC
Test Test ROC AUC
0.8
0.6
2.0
61
02
0.3
0.4
05
0.5
0.7
0.0
01
0.4
0.3
0.4
0.5
Label informativeness
Label informativeness
(a) GAT
GraphSAGE
Figure 9: Performance of GAT and GraphSAGE on real graphs vs LLedge
Table 7: Spearman correlation coefficients between ROC AUC score and characteristics of real- world
datasets from Table 5
Model
hedge
Nnode
helass
hadj
LIedge
LI
GraphSAGE
0.64
0.62
0.67
0.61
0.78
0.82
GAT
0.69
0.65
0.74
0.69
0.85
0.84
F.6 Correlation of GNN performance with homophily and LI on real datasets
Analyzing which measures better agree with GNN performance real data is non-trivial. Indeed, we consider diverse node classification problems, there are many factors affecting the GNN performance: the size of the datasets and fraction of training examples, the edge density, the number of features and their informativeness, the number classes and their balance, and so on. However, as analyze how well different homophily measures and LI correlate with
requested by the reviewers, GNN performance on the datasets in Table In this experiment, we measure the ROC AUC score suitable performance
since some of the datasets highly unbalanced, and thus accuracy measure. For the datasets with more than two classes, we report the macro-averaged ROC AUC score. The relation between ROC AUC and LI for GAT and GraphSAGE is shown in Figure 9 The Spearman correlation for all the measures is reported in Table 7 We see that the largest correlation is achieved by LLedge and LInode Let us note that this table does not aim compare homophily measures with each other since a good homophily measure is expected to properly capture the tendency of edges to connect similar nodes. Thus, we compare homophily measures using the proposed theoretical framework in Section 2
26


Reviews:
[{"review_id": "l8hn9zkYCo", "reviewer": "Reviewer_QJti", "summary": "The paper proposes new measures to characterize homophily and heterophily in graph datasets. First, some desirable properties are asserted for a good measure of homophily. It is discussed whether various prior measures of homophily satisfy these properties, then a new measure called *adjusted homophily* is proposed; this is a modification of the established measure of *edge homophily* using information about (degree-adjusted) class distributions of nodes. After this, to capture the fact that a node's class label can be, depending on the dataset, either informative or uninformative about its neighbor's class label, a measure called *label informativeness* (LI) is also proposed. When randomly sampling an edge $(u,v)$, this is the fraction of the information content of a $u$'s class label that is given by knowing $v$'s class label. After establishing these measures, the paper lists them for several real-world datasets. In experiments on synthetic SBM graphs and semi-synthetic modifications of the Cora graph, the authors show that LI is better correlated with GNN performance than homophily.", "questions": "My questions correspond to points from the prior section:\n- Assuming that LI is indeed a new measure, do you see some variant of it that could work for more than 1 hop across the graph? Or otherwise, do you think such measures are unlikely to be informative?\n- Do you expect there to be a general trend (even if it is a weak trend) that, across the usual benchmark graph datasets, higher LI corresponds to higher node classification performance? Or do you at least expect a higher correlation than with (adjusted) homophily? I think it would be interesting to see plots like the ones for the synthetic datasets, except for (some fraction of) the graphs in Table 4.", "limitations": "Limitations are adequately addressed in a designated section of the conclusion.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- The homophily/heterophily topic has seen a lot of interest in the past few years, so this work is likely to get much attention.\n- The paper is very well-written. It is logically organized and easy to read.\n- The paper makes a compelling case that both the adjusted homophily and LI measures are the most sensible such measures.", "weaknesses": "- While LI seems like a very sensible measure, it is rather straightforward, so I am left thinking: First, has it really not been proposed by some prior work, especially given that the general concept of normalized information measures is well-established (e.g., [this](https://en.wikipedia.org/wiki/Mutual_information#Normalized_variants))? I don't see this as a weakness on it's own, since I am not aware of such prior work. However, I do feel that some more graph-specific theoretical work addressing the first limitation listed in the paper (i.e., variants of homophily/LI that consider multiple hops in the graph) would significantly increase the contribution. The paper seems to state that this is beyond the scope of the work, but I feel the amount of contribution is a bit borderline as it is.\n- The experiments positing that LI is well correlated with GNN performance are on synthetic or semi-synthetic datasets only. Ideally, some trend could be shown across a variety of real-world datasets, though it is understandable that such a trend may not exist given various factors besides LI.\n\n\n### Typos\n- Figure 8: \"edge homopily\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback and useful comments! We address your concerns below.\n\n> While LI seems like a very sensible measure, it is rather straightforward, so I am left thinking: First, has it really not been proposed by some prior work, especially given that the general concept of normalized information measures is well-established\n\nWe indeed use the normalized mutual information as a well-known concept when defining the LI measure. Our suggestion here is to apply this concept to graphs by defining random variables to which it should be applied. We are not aware of prior work using normalized mutual information for graphs in a similar manner to characterize edge-label relations.\n\n> Assuming that LI is indeed a new measure, do you see some variant of it that could work for more than 1 hop across the graph? Or otherwise, do you think such measures are unlikely to be informative?\n\nThis is a very reasonable suggestion. At earlier stages of our research, we indeed defined and measured “two-hop homophily” and “two-hop LI”. These are similar measures to those discussed in the paper but defined via pairs of nodes at distance two (or larger distances can be considered). However, we have not observed any interesting patterns for these measures: non-trivial connection patterns become harder to detect as we increase distances between nodes. Thus, we decided to make our work more focused and to advise simple but efficient one-hop measures.\n\n> Do you expect there to be a general trend (even if it is a weak trend) that, across the usual benchmark graph datasets, higher LI corresponds to higher node classification performance? Or do you at least expect a higher correlation than with (adjusted) homophily? I think it would be interesting to see plots like the ones for the synthetic datasets, except for (some fraction of) the graphs in Table 4.\n\nYou are absolutely right that various factors besides LI may affect the performance - and it is the reason why we initially experimented only on synthetic and semi-synthetic datasets. However, to address this question, we also conducted the experiment you suggest and measured the correlation on the datasets in Table 4. We report the results in our [general response](https://openreview.net/forum?id=m7PIJWOdlY&noteId=hxPviGCfUx). Here we show that despite other factors potentially affecting the results, LI better agrees with GNN performance than homophily measures.\n\nWe hope that we addressed your concerns and will be happy to answer any additional questions!\n"}, {"review_id": "NWlGatQnC5", "reviewer": "Reviewer_eRJB", "summary": "This paper focuses on developing techniques to characterize graph node classification datasets. First, this paper has proposed a theoretical framework to develop measures of graph’s characteristics. Then two measures called “adjusted homophily” and “label informativeness” are proposed to easily characterize the connectivity patterns of graph datasets. And experimental results show the stronger correlation of proposed measures with GNNs’ performance.", "questions": "1.\tMore details about how to get the adjusted value in lines 183 and 184.\n2.\tEdge label informativeness seems to be smaller than node label informativeness in most cases, any explanation about this?\n", "limitations": "Authors have adequately addressed the limitations in this paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper has analysis the drawbacks of existing measures, like node homophily and edge homophily.\n2.\tThis paper has proposed a generic framework with theoretical analysis to develop techniques for characterizing graph node classification datasets, which will help to design more suitable models on certain datasets. And proposed minimal agreement, maximal agreement, and monotonicity is very useful.\n3.\tThe proposed adjusted homophily get rid of the number of class and class size on different datasets and is of broader applicability.\n4.\tThe proposed label informativeness have a strong correlation with the GNN’s performance, which is interesting and novel. Moreover, this can help to design more powerful development of heterophily-suited GNNs.\n", "weaknesses": "1.\tOnly Cora and Citeseer that be considered as homophilic graphs are used for showing the correlation between GNNs’ performance and LI, more heterophilic graphs should be tested.\n2.\tAssortativity coefficient is mentioned in section 2.4, but there is not comparison with proposed measures.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and for acknowledging the usefulness of our theoretical framework! We address your questions and concerns below.\n\n> Only Cora and Citeseer that be considered as homophilic graphs are used for showing the correlation between GNNs’ performance and LI, more heterophilic graphs should be tested.\n\nIn our experiments we mostly focus on synthetic datasets where connectivity patterns can be easily controlled. Here we consider both SBM and LFR random graph models with varying parameter combinations allowing us to get non-trivial patterns. We also use semi-synthetic data from [17], where datasets are generated based on Cora and Citeseer. Originally, we have not experimented with real datasets since various factors besides edge-label relation may affect the performance. However, as asked by several reviewers, we also measured the correlation between performance and different measures on real datasets from Table 4, please see our [general response](https://openreview.net/forum?id=m7PIJWOdlY&noteId=hxPviGCfUx). Here we show that even on real datasets LI better agrees with GNN performance than homophily measures. We hope these additional experiments address your concern. \n\n> Assortativity coefficient is mentioned in section 2.4, but there is not comparison with proposed measures.\n\nAs written in Section 2.4, the assortativity coefficient reduces to (2) when applied to discrete node attributes on undirected graphs. Thus, it produces the same values in our setting. We call this measure _adjusted homophily_ in our paper for the following reasons:\n- To avoid ambiguity with other usages of assortativity, e.g., assortativity coefficient often refers to degree-degree correlations in graphs without node labels\n- To emphasize that adjusted homophily is a standard adjustment for chance applied to edge homophily (i.e., adjusted homophily relates to edge homophily as, e.g., adjusted Rand index relates to Rand index)\n- To emphasize that this measure indicates the level of homophily since this coefficient is rarely used in graph ML literature for this purpose\n\n> More details about how to get the adjusted value in lines 183 and 184.\n\nAccording to the configuration model, the probability that a given edge goes to a node of degree $d$ equals $\\frac{d}{2|E|}$, where the denominator equals the sum of all node degrees. Then, to get the probability of connection to a node from class $k$, we need to sum these values over all nodes from class $k$. Thus, we obtain $\\frac{D_k}{2|E|}$ since $D_k$ is the sum of all degrees for nodes from class $k$. Multiplying this by $D_k$, we get twice the expected number of edges going from class $k$ to class $k$. Dividing this by $2|E|$ gives that $\\frac{D_k^2}{4|E|^2}$ is the expected fraction of edges going from class $k$ to class $k$. Then, if we sum over all the classes, we get the expected number of homophilous edges. We subtract this value from $h_{edge}$ to get an unbiased measure. There are some negligible error terms in this reasoning, so we refer to section B.4 where all error terms are carefully tracked.\n\n> Edge label informativeness seems to be smaller than node label informativeness in most cases, any explanation about this?\n\nEdge and node label informativeness differ in how they weight high/low-degree nodes. For node label informativeness, averaging is over the nodes, so all nodes are weighted equally. For edge label informativeness, averaging is over the edges, which implies that high-degree nodes make a larger contribution to the final measure. It is natural to expect that for high-degree nodes the amount of information from each individual neighbor is lower than for low-degree nodes since neighbors of high-degree nodes are expected to be more diverse and closer to the “average” distribution. Thus, edge LI is expected to be smaller. Thank you very much for this observation, we will add this discussion to the text!\n\nWe hope that we addressed your concerns and will be happy to answer any additional questions!\n"}, {"review_id": "lobyWkw6mQ", "reviewer": "Reviewer_kh3x", "summary": "This paper analyzes homophily measures and proposes a new characteristic highly correlated with performance. Specifically, the authors suggest desirable properties for the metric and show that current homophily measures do not satisfy some important properties, so suggest a new homophily measure to satisfy them. Furthermore, beyond homophily arguments, the authors suggest a new characteristic that is more highly correlated with performance from the perspective of the usefulness of neighbor labels to predict the label of the corresponding center node. They demonstrate that the correlation between the values of proposed measures and performance is significantly higher than current homophily measures on various architectures and datasets.", "questions": "Could you provide the results when calculating the correlation only based on the values of metrics and performance in Appendix Table 4, without manipulating the original graphs?", "limitations": "As the authors mentioned, LI only considers node label interaction in graphs.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors suggest the desirable properties for the metrics and show that current homophily measures do not satisfy important traits such as asymptotic constant baseline.\n- They suggest adjusted homophily to satisfy most of the important properties including the asymptotic constant baseline.\n- They propose a new characteristic describing the effectiveness of graph structure for performance.\n- The proposed characteristic exhibits a significantly higher correlation with performance compared to homophily measures.", "weaknesses": "Although the authors provide the correlations between performance and a given metric on Cora and Citeseer by modifying graphs synthetically, it seems not enough to show the general applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and positive feedback! In our experiments we indeed mostly focus on synthetic datasets where connectivity patterns can be easily controlled and on semi-synthetic data previously used in the literature for the analysis of homophily measures. Originally, we have not experimented with real datasets since various factors besides edge-label relations may affect the performance. Moreover, we did not want to move the focus of our work from theoretical analysis to only experimental results - LI is a very simple measure that cannot pretend to capture all complex situations that can arise in practice.  However, as asked by several reviewers, we also measured the correlation between performance and different measures on real datasets from Table 4, please see our [general response](https://openreview.net/forum?id=m7PIJWOdlY&noteId=hxPviGCfUx). Here we show that even on real datasets LI better agrees with GNN performance than homophily measures. We hope these additional experiments address your concern and will be happy to answer any additional questions!"}, {"review_id": "XBoFEfVlUI", "reviewer": "Reviewer_oQPA", "summary": "The main contribution of this paper is a new measure called label informativeness that characterizes how much information a neighbor’s label provides about a node’s label. The paper also discusses the expected properties of homophily. The experimental results are based on the relation between the performance of GNN and the proposed metric. ", "questions": "1. Regarding the analysis of the value. Does LI have a linear scale of the values? Does a value of 0.5 mean 50% of reconstruction? \n\n2. Is the LI general enough to obtain similar correlations with other classification models (I think so)?\n\n3. Could you explain the main difference between LI (the metric, not the way that is used) and https://www.jstor.org/stable/2775440?\n\n4. Could you explain the difference between LI with respect to the LI metric used in the published paper [16]?", "limitations": "Yes, the authors clearly state the limitations of their work. However, there are some limitations that were omitted.\n\nAs a suggestion, if the main contribution is the use of the JSTOR paper in graphs. Please state it this way, rather than saying that this is a new measure.\n", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The quality of the theoretical demonstrations. Most of the demonstrations seem correct, even though I did not go exhaustively through the details, as they are in the supplementary material.\n\n2. Good discussion about homophily. The paper covers several aspects of homophily, mentioning the desired properties of this measure.\n\n3. The clarity of the proposition. It is clearly stated the main contribution of the paper.\n\n4. Readability. The paper is well-written, being very simple to read.\n", "weaknesses": "1. The novelty of the work could be questionable. The measure is not novel, please refer to \"On the Estimation of Relationships Involving Qualitative Variables\", available at https://www.jstor.org/stable/2775440. The submitted paper presents an uncertainty coefficient that is closely related to the work proposed in this paper. Even though, that paper does not focus on graphs, the proposed measure seems to be the application of this measure over a particular distribution, rather than the proposition of a new measure. Second, the same formulas and equations are already published in [16]. Moreover, in [16], it is mentioned that LI was previously introduced. \n\n2. The conclusion mentions \"LI characterizes how much information a neighbor’s label provides about a node’s label\". Unfortunately, this is not explained in the paper, except by the phrase \"$LI \\in [0, 1]$ If the label y_n allows for unique reconstruction of y_\\epsilon , then LI = 1. If y_\\epsilon and y_n are independent, LI = 0\". \n\n3. The paper mentions that \"Through a series of experiments, we show that LI correlates well with the performance of GNNs.\". Based on https://www.jstor.org/stable/2775440, I believe that this is related because the measure is based on the classification performance, rather than GNN. \n\n4. The limitations mention \"this measure to be both informative and simple to compute and interpret.\". However, no interpretations are given besides the values of 0 and 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and comments! In this response, we address your questions and concerns.\n\n**Contribution of our work**\n\nIn our discussion below we argue why we think that LI is a novel graph characteristic and how it relates to known concepts in information theory. However, in this discussion, we do not want to narrow the scope of our paper to only one formula (3), thus let us briefly state the main contributions of our work. We think that our main contributions are the proposed theoretical framework and theoretical analysis of different measures within this framework. We believe that the important takeaway from our work is that one has to be careful when choosing graph characteristics to describe and compare graph datasets. In particular, it is important to verify the unbiasedness of the measures. We advise using adjusted homophily and LI since both these measures are unbiased and have other important desirable properties.\n\n**The novelty of LI and its relation to concepts from information theory**\n\nIn our work, we use normalized mutual information (equation (3)) as a well-known and widely used concept and therefore do not cite any works here. Thanks for pointing out that we do not explicitly call this measure “normalized mutual information” (or “coefficients of constraint”, “uncertainty coefficient”, or “proficiency” which are other terms used in the literature) -- this happened because we tried to explain the intuition and interpretation of this measure while introducing it step-by-step. This will be fixed - we will explicitly write that the concept is well-known.\nHowever, the main novelty of LI is applying this known notion of mutual information to graph datasets. For this, we need to define graph-based random variables to which this concept can be applied. Note that such random variables are not predetermined and there are several options, some of which we discuss in the paper. We are not aware of prior work applying the concept of mutual information to graphs in a similar manner to characterize edge-label relations.\nWe address other questions and concerns below.\n\n> Could you explain the main difference between LI (the metric, not the way that is used) and https://www.jstor.org/stable/2775440?\n\nAs described above, we use the uncertainty coefficient as a known concept in information theory (and will explicitly state it in the paper to avoid any possible misunderstanding). However, to properly address the questions on the relation to Theil (1970), we would like to kindly ask if you can point us to a particular equation or definition in Theil (1970) to which we should compare our notion of LI.\n\nAlso, we cannot agree with the distinction between the metric and the way that it is used, since in our case defining the random variables is a part of the metric definition. Drawing parallels with other known graph characteristics, one could say that the assortativity coefficient is the application of Pearson correlation to graphs, edge homophily is the application of the operation “average” to graphs, PageRank is the application of eigenvectors to graphs, and so on. In all these cases, the characteristics are defined by the application of a known concept to a graph domain.\n\n> The conclusion mentions \"LI characterizes how much information a neighbor’s label provides about a node’s label\". Unfortunately, this is not explained in the paper\n\nThe cited sentence refers to the concept of information from the information theory, i.e., this is just a rephrasing of the definition of LI: by definition, LI describes the (relative) amount of information revealed by the label of a single neighbor. We provide more intuition in our answer to the next question.\n\n> Regarding the analysis of the value. Does LI have a linear scale of the values? Does a value of 0.5 mean 50% of reconstruction?\n\nThe value of LI can be related to the cross-entropy loss. Indeed, assume that no information about the neighbors’ labels is available. Then, the best classifier in terms of the cross-entropy assigns probability $p(k)$ to each class $k$. For this classifier, the cross-entropy loss is the entropy of $p(\\cdot)$. If we know the label of one neighbor, the cross-entropy loss of the best possible classifier is reduced to the conditional entropy. Thus, we can say that LI describes the relative reduction of the expected cross-entropy loss of the best possible classifier. So, the value of 0.5 means that this loss becomes two times smaller. We hope that this explanation addresses the concern about the interpretability of the measure.\n\nThis simple intuition, however, does not account for the fact that in graphs each node has several neighbors which may have various distribution of labels. Thus, the reasoning above cannot be directly applied, so we additionally verify the usefulness of LI as a graph characteristic via experiments.\n\n> Is the LI general enough to obtain similar correlations with other classification models (I think so)?\n\nWe hope that our reply to the previous question addresses this concern. But if no, could you please clarify which classification models we need to consider?\n\n> Could you explain the difference between LI with respect to the LI metric used in the published paper [16]?\n\nSince explaining the current paper's relationship to LI used in [16] involves a potential double-blind issue, we have checked it with the AC, and the AC confirms that the LI in [16] does not negate the novelty of the LI in the current work.\n\nWe hope that our response addresses your concerns. We are happy to answer any additional questions during the discussion period if needed.\n"}]

Author rebuttal:
We would like to thank all the reviewers for their comments and suggestions! In this general response, we address the comment raised by several reviewers about conducting additional experiments on real datasets.

Analyzing which measures better agree with GNN performance on real data is non-trivial. Indeed, if we consider diverse node classification problems, there are many factors affecting the GNN performance: the size of the datasets and fraction of training examples, the edge density, the number of features and their informativeness, the number of classes and their balance, and so on. 

However, for the completeness of the study, we analyze how well different homophily measures and LI correlate with GNN performance on real datasets from Table 4. In this experiment, we measure the ROC AUC score since some of the datasets are highly unbalanced, and thus accuracy is not a suitable performance measure. For the datasets with more than two classes, we report the macro-averaged ROC AUC score. 

The relation between ROC AUC and LI (for GAT and GraphSAGE) is shown in Figures 1 and 2 in the attached pdf. Table 1 reports the Spearman correlation of ROC AUC with all the measures. We see that the largest correlation is achieved by LI (node and edge variants). 

Let us note that this experiment does not aim to compare homophily measures with each other since a good homophily measure is expected to properly capture the tendency of edges to connect similar nodes and is not expected to correlate with GNN performance. That is why we compare homophily measures using the proposed theoretical framework in our paper.

We hope that these experiments address the concerns of the reviewers and we are open to further discussions.


Meta-review: The paper makes a number of novel contributions:
* Discuss desirable properties for homophily measures, and show that existing homophily measures fail to satisfy some of these
* Studies the "adjusted homophily" measure and show the properties it satisfies
* Propose the label informativeness (LI) measure, which aims to go beyond the homophily-heterophily dichotomy by measuring how informative a node's labels are about its neighbor's labels; show that it satisfies some of the properties
* Empirically show the correlation between LI and GNN performance

Overall, most reviewers are on the positive side, with 1 on the negative side mainly due to concerns with novelty. Specifically, there is the concern due to similarity to "On the Estimation of Relationships Involving Qualitative Variables" (https://www.jstor.org/stable/2775440). This paper is about information theoretic measures in a general (non-graph) context. Use of information theoretic measures is indeed classical and standard, and the contributions of the current work should be considered in light of that, but my view is the specific paper https://www.jstor.org/stable/2775440 does not significantly affect the consideration beyond this. In my view, it is a good thing that LI is designed in a simple way based on standard information theoretic measures, since it is better for metrics to have a clear and easily understood interpretation, rather than being complex, and the novelty is more in the points listed above rather than the specific design choices of the LI metric.

The paper [16] is also noted by the reviewer, but discussion (between AC / SAC) confirmed that the LI in [16] does not negate the novelty of the LI in the current work.

Moreover, the author response adds results showing that LI correlates better with GNN performance on real datasets (rather than just synthetic datasets) compared to existing homophily measures, which is interesting. Overall, the paper provides detailed empirical and theoretical analysis on the important topic of heterophily, which provides some insights which are not well known in the GNN literature. Hence, I recommend acceptance. 

Authors are requested to note improvements / action items arising from discussion with the reviewers, such as adding the new empirical results to the manuscript, clarifications to the paper arising from reviewer discussion (e.g. line 183-184), etc.
Decision: Accept (poster)