Diverse Message Passing for Attribute with Heterophily
Authors: Liang Yang
Mengzhe Li
Liyang Liu
Bingxin Niu
Chuan Wang
Xiaochun Cao
Yuanfang Guo
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
over-smoothing issue
networks with heterophily

Abstract: Most of the existing GNNs can be modeled via the Uniform Message Passing framework. This framework considers all the attributes of each node in its entirety, shares the uniform propagation weights along each edge,  and focuses on the uniform weight learning. The design of this framework possesses two prerequisites, the simplification of homophily and heterophily to the node-level property and the ignorance of attribute differences. Unfortunately, different attributes possess diverse characteristics. In this paper, the network homophily rate defined with  respect to the node labels is extended to attribute homophily rate by taking the attributes as weak labels. Based on this attribute homophily rate, we propose a Diverse Message Passing (DMP) framework, which specifies every attribute propagation weight on each edge. Besides, we propose two specific strategies to significantly reduce the computational complexity of DMP to prevent the overfitting issue.  By investigating the spectral characteristics, existing spectral GNNs are actually equivalent to a degenerated version of DMP.  From the perspective of numerical optimization, we provide a theoretical analysis to demonstrate DMP's powerful representation ability and the ability of alleviating the over-smoothing issue.  Evaluations on various  real networks demonstrate the superiority of our DMP on  handling the networks with heterophily  and alleviating the over-smoothing issue, compared to the existing state-of-the-arts.

Diverse Message Passing for Attribute with Heterophily
Liang Yang 1,2.*, Mengzhe Li 1.*, Liyynng Liu 1.-
Bingxin Niu Chhan Wang Xiaochun Cao 3, Yuanfang Guo School of Artificial Intelligence, Hebei University of Technology. Tianjin, China State Key Laboratory of Information Security, IIE, CAS, Beijing, China School of Cyber Science and Technology, Sun Yat-sen University, Shenzhen, China State Key Laboratory of Software Development Environment, Beihang University, China yangliangovip qq. com, limengzhefreed oxmail. com, liyang_ com niubingzin6660163. com, [vangchuan, caoxi (ochun) @iie. ac. cn, andyguo@buaa edu cn
Abstract
Most of the existing GNNs can be modeled via the Uniform Message Passing framework. This framework considers all the attributes of each node in its entirety, shares the uniform propagation weights along each edge, and focuses on the uniform weight learning. The design of this framework possesses two prerequisites, the simplification homophily and heterophily to the node-level property and the ignorance of attribute differences. Unfortunately, different attributes possess diverse characteristics. In this paper, the network homophily rate defined with respect to the node labels is extended to attribute homophily rate by taking the attributes as weak labels. Based on this attribute homophily rate, we propose a Diverse Message Passing (DMP) framework, which specifies every attribute propagation weight on each edge. Besides, we propose two specific strategies to significantly reduce the computational complexity of DMP to prevent the overfitting issue. By investigating the spectral characteristics. existing spectral GNNs are actually equivalent to degenerated version of DMP. From the perspective of numerical optimization, we provide a theoretical analysis to demonstrate DMP's powerful representation ability and the ability of alleviating the over-smoothing issue. Evaluations on various real networks demonstrate the superiority of our DMP handling the networks with heterophily and alleviating the over-smoothing issue, compared to the existing state-of- -ftte----se--sss.
Introduction
Originated from the spectral graph theory. Graph Neural Networks (GNNs) 2 have demonstrated superior performances on modeling ubiquitous irregular data in many tasks, such as computer vision, natural language processing, information retrieval, etc. By reducing the computational complexity of graph Fourier transformation via approximation, most the GNNs, especially Graph Convolutional Networks (GCN) [3] and its variants (such as SGC 4),, actually perform Laplacian smoothing [5] and low- low-passing filtering [4] Although this intuitive strategy achieves state-of-the-art performances on networks with homophily, such as Cora, CiteSeer and Pubmed, possesses fatal drawbacks. Firstly. it only performs well on shallow networks, while induces serious smoothng issue when more layers are stacked
Secondly, shows obvious ineffectiveness in handling the networks
"Equal contribution. Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

with heterophily, where its performance is even worse than the simple multiple layer perceptron (MLP) [
There are many attempts to overcome the above two drawbacks. The common philosophy behind these attempts is weakening the smoothing effect. One type of methods directly modifies the smoothed node representations based on local information. For example, APPNP [2] and GCNII [T average the smoothed node representations with the corresponding original node attributes. JKNet [77 and PPNP M combine multi-scale information by summation, while Mix M.. truncated block Krylov network [12] and H2GCN N combine multi-scale information by concatenation. Other methods modifies the network topology, which indirectly reduces the over-smoothing issue. For instance, DropEdge [33 and GRAND [4] randomly remove edges and nodes, respectively, while FAGCN [15] and GPRGNN relax the edges with positive values, which tends to induce the smoothing effect, to possess real values (which can be either positive or negative). A recent research 17 has tried to bridge and unify over-smoothing issue and networks with heterophily.
Most of the GNNs, which can be designed for networks with either homophily or heterophily, can be unified by a message passing framework. These GNNs usually consider all the attributes of one node in its entirety, and propagate them via the same (positive or negative) propagation weight along each edge. Intuitively, most of the Graph Neural Networks (GNNs) are restricted in the uniform message passing framework and focus on uniform weight learning, such as GCN B. GAT [8 and to
FAGCN [TS This phenomenon is induced by simplifying the network nomophily/heterophhi node-level property [1)] In Geom-GCN 20 and H2GCN [. which are designed handle the networks with heterophily, the network homophily rate is defined by only utilizing network topology
and node labels.
Actually, different attributes possess diverse characteristics. To explicitly model the diversity, the concept of network homophily rate defined in (20 is extended attribute level. Specifically, attribute homophily rate for each attribute is defined by replacing the real label of each node with the corresponding attributes to form weak labels. Statistics in Figure FigureMreveal that the attribute homophily rates of the networks with either homophily and heterophily all tend to vary in large range. Then, GNNs are desired to explicitly consider the diversity of attribute homophily rates. To achieve this objective. we propose a Diverse Message Passing (DMP) framework, which specifies every attribute propagation weight on each edge, to adaptively handle the diverse attribute homophily, Besides, we further propose two strategies to significantly reduce the model complexity of DMP to alleviate the overfitting issue. By investigating the spectral characteristics, existing spectral GNNs are actually equivalent to degenerated version of our DMP. From the perspective of numerical optimization, we provide a theoretical analysis to demonstrate DMP's powerful representation ability and the ability of alleviating the over-smoothing issue. Specifically, different from Uniform Message Passing, which directly generates a graph partition, our DMP generates multiple groups of graph partition candidates, and then the classifier in semi-supervised task will determine the specific combining approach to form the final partition. This mechanism actually enables our DMP to possess more representation ability, which can also alleviate the over-smoothing issue, compared to classic Uniform Message Passing.
2 Notations and Preliminaries
Let G = (V,E) denote graph with set of nodes V = {U1, U2....,, and a set of edges E, where N is the number of nodes. The topology of graph 9 can be represented by its adjacency matrix A [aty] (0, 1xN,, where daj 1 if and only if there exists an edge eij = (vi, 1t) between nodes V/ and vi. The degree matrix D is a diagonal matrix with each diagonal element d; = ΣN aij being the degree of node U/- .V(,,) {uy (1), 02) E E} stands for the neighbourhoods of node 2/- X E R. NxF and H E R NXF' respectively denote the collection of node attributes and representation of the th row, i.e., x; E R. and h, IR F", which both correspond to node U,. Note that F and F" stand for the dimensions of node attributes and representations.
Most of the Graph Neural Networks (GNNs) follow an aggregation-combinatio strategy (1]. where each node representation is iteratively updated by aggregating node representations in the local neighbourhoods and combining the aggregated representations with the node representation itself as
h AGGREGATE* ((h k- lu (()))) h COMBINATE (h)-) kt)
(I)
2

---

3.006-02 tosss (0.06)
wetcconsss (0.16)
1.8
chameleon (0.25)
comel [0.11]
actor (0 24)
chesoer (0.71)
pubmed (0.79)
1.2
2,00E-02
1.50E-02
0.8
1.006-02
0.2
0.00E+00
600
1030 1500
2000 2500
Figure 1: Attribute homophily rates networks with different homophily. Each number, which corresponds to network name, denotes network homophily rate computed via the method in 20). (a) Distributions of attribute homophily rates, i.e., {3f) on different networks. Each column represents one network. (b) Attribute homophily rate, i.e., {By)f-1. on different networks. Each curve denotes one network. For better visualization, attribute homophily rates sorted in ascending order.
where h stands for the aggregated representation from local neighbourhoods. Besides of the concatenation based implementation, such as GraphSAGE [2) and H2GCN S averaging (or summation) has been widely adopted to implement COMBINATE"S (..-), such as GCN [ GAT | GIN 23 etc. Except for the MAX and LSTM implementations GraphSAGE 2
most of the GNNs utilize averaging function to implement AGGREGATE" Therefore, they can be unified as
h = of (( h k
Σ (EN())
ck h W
where W represents the learnable parameters and (-) denotes the nonlinear mapping function. Note that the scalar Cup is the averaging weight. For example, GCN [ sets cuu 1/(1 + 1)(d, + 1),
GIN 23 sets ot = 1 for * and ct = 1 + ct, and GAT | learns non-negative ct based on the attention mechanism. Recently, to handle the network with heterophily via high-passing filtering, GPRGNN [16] sets c = > >>//(Vdd, + ()d, 1) with 7 being a learnable real value,
while FAGCN 1S directly relaxes the learnable Cau in GAT real value.
3 Diverse Message Passing
In this section, the motivation of Diverse Message Passing is firstly provided. Then, the diverse aggregation framework is given, followed by implementations to reduce model complexity.
3.1 Motivations
The unified formulation Eq. 2 can be regarded as the uniform message passing framework, where all the attributes which propagated from node v node i.e., all the elements of h share the common weight ct... Then, all the attributes can be aggregated with the same weight assignment scheme in the local neighbourhood A(()) {v}. Since aggregation can be interpreted from the perspectives of both Laplacian smoothing [5] and low now-passing filtering 4 the same weight assignment scheme indicates that all the attributes tend to share similar distributions over the entire graph.
To investigate the distributions of attributes and measure their similarities, the attribute homophily rate is proposed. The network homophily rates, including both the node version 20 and edge version R quantify similarity between connected nodes. The node similarity network homophily rate measured according to the node labels. Here, the attribute homophily rate is defined by measuring

---

the node similarity according to each attribute. Specifically, the attribute homophily rate of attribute is formulated as
EueN(uu) Buf Fof
81 EvEr Rof DEV
Bus ΣVEN Ros
(3)
dg
DEV
where EmeN(ca Ruf is the rate of neighbourhoods with attribute f, Pus = 2ef de dy
EmeNto) Ruf
is the rate of neighbourhoods which share the same attribute f as node v, and the attribute homophily rate of attribute f. i.e., B3.. is the average of Bef over all the nodes possessing attribute f.
Figure I shows the distribution of {,5) networks with different homophily, computed via the method in [20]. For better visualization, both the macroscopic and microscopic perspectives are provided. Figure gives the distribution of attribute homophily (in macroscopic perspective) on each network (each column). Figure[I] describes the attribute homophily of different attributes, i.e., {3y]f=1 from the microscopic perspective.
It can be observed that networks with higher homophily also possess higher averaged attribute homophily, and vice versa. However, attribute homophily { distributes a large range, with little correlations to the degree of attribute homophily of network. It shows that different attributes possess remarkably different attribute homophily, which reveals that the distributions of attributes over the entire graph are diverse, instead of uniform ones. Therefore, diverse aggregation scheme, i.., averaging scheme, should be designed to fully explore the diverse distributions of attributes over the entire graph for effective node representation learning.
3.2 Diverse Aggregation Framework
To achieve diverse aggregation, the Uniform Message Passing in Eq. is revised to make different
attributes possess different propagation weights. Then, the scaler Gyg in Eq. ( is augmented to vector ct.. which has the same length the node representation h Each element in ot stands for the weight of the corresponding attribute in h propagated from node to node v. Thus, Eq.
@ is modified to
((oc) 1
h =
Σ cxv ④ h- W
(4)
uEN((o)
where @ denotes the element-wise product of vectors. Then, the remaining issue is the learning strategy of e 's. If all c are set free parameters be directly learned, the model complexity, i.., the number of parameters, of directly learning ct 's is ((E)F), which may induce overfitting. In the following paragraphs, two strategies are designed to reduce the number of learnable parameters.
The first strategy constrains all the parameters ch,, 's to be determined by learnable function. Since c can be regarded as the averaging weight between nodes v and the attention scheme can be adopted as
(5) where [h: thg-"1[bb- represents the concatenation of representations h and h 1, Note that the learnable mapping function W E FxF is shared across all the edges, where F is the dimension of h and c Then, the model complexity significantly reduced to ( Different from the attention mechanism employed in GAT
ch tanh
[ which constrains the learned propagation weights c to be non-negative via softmax nonlinear function, the learned weight vectors ctt 's are relaxed to exp(()=exp(-o)
1, whose output is zero-centered and ranged in (-1, 1). Intuitively, the positive weights are equivalent to low-passing filtering, while the negative weights actually facilitate the filtering beyond low- low-frequency.
real values by adopting a tanh nonlinear function tanh(a:) = exp(=) +ex(=)) = sigmoid(2n)
The second strategy simplifies Eq. 4 by assuming that all the neighbourhoods employs identical propagation vector, i.e., ck cli for every u E (o). This simplification, which has also been adopted in GraphSAGE [22], H2GCN K and GIN GIN assumes that the neighbourhoods of fixed-hop equally contribute to the node representations, Accordingly, Eq. can be simplified to
h = = ((
k-
Σ
k-1
W
(6)
BEA(

---

6 can be considered as the weighted averaging of the node representation h and the neigh- bourhood representation h EmeN(r) h where both c and e can be regarded as the element- wise averaging weights. Thus, the learning of ct and cf can be determined by node and neighbourhood representations. Similar to Eq. b the attention mechanism is adopted to learn them as
c = tanh ( (b1-"11R"-
(7)
Compared to E..5). the learning process of ct similar, yet with a different parameter W This strategy possesses Identical model complexity to the first strategy.
3.3 Interpretation from the Spectral Perspective
In previous subsections, Diverse Message Passing is motivated and proposed from the spatial perspective of GNNs. Actually, GNNs originate from spectral graph theory, where ChebNet (24) and GCN 3 representative methods. ChebNet utilizes the Chebyshev polynomials of Laplacian matrix define the graph convolution as H Σ To T XL,,, where L denotes the scaled Laplacian matrix and (z) represents the Chebyshev polynomials. GCN simplifies ChebNet by
constraining it to a 1-order model, i.e., R = as
k- WT + h = h
<E NEN(())
Σ
h 1 w
(8)
GCN force the two terms in Eq. to share the same mapping function, i.e., W - W W It can be observed that if all the nodes share the same c and et as ch and cx the second strategy in Eq. degrades to 1 l-order ChebNet in Eq. (8) with W (1.c*) c*) W and W (1-c*) W where 1 stands for the vector of ones and it possesses the same length as c* and ch. Therefore, the mapping function W in both ChebNet and GCN contain the attribute-win wise propagation weights, c and c², which are shared by all the edges. Therefore, most of the spectral GNNs tend to fail in the Uniform Message Passing framework, which has also been explained in (25
In fact, the attribute wise weights ey in Eq. and cf in Eq. (6) cannot be integrated into the mapping parameter W because these weights tend to be different, on different edges in Eq. 4 and different nodes in Eq. to model the attribute heterophily. Hence, Diverse Message Passing may break the performance ceiling of spectral GNNs.
3.4 Theoretical Analysis
Recently, some efforts have been paid to interpreted GNNs from the perspective of numerical
Each graph convolutional layer GCN can be regarded as a gradient descent algorithm to minimize the graph Laplacian regularization Ir (HTLH)
optimization 26 27 28
Σ., h - h, where tr(-) stands for the trace of the matrix, starting from the node attribute X. However, most of the existing literatures only unify and interpret GNNs based on the fixed propagation weight in Eq.
such as APPNP 9 JKNet i and DAGNN
2
In this subsection, the theoretical difference between the Uniform Message Passing in Eq. and Diverse Message Passing in Eq. should be learnable to facilitate the Diverse Message Passing, the previous numerical optimization framework for GNNs with fixed propagations is desired to be relaxed. Specifically, the propagation weights c in Eq. 2 and ct in Eq. (4) are both assumed to be learnable. Since this analysis focuses on the underlying philosophy of learning propagation weights from the bdge-wiss/chhanel-wiss perspective, the specific learning function is neglected.
analyzed. Since the propagation weights on all the attributes
Uniform Message Passing Eq. 2 with learnable weights ch can regarded as the combination of two steps: 1) learning the propagation weights to form a new graph topology; 2) propagating attributes on the new graph. Then, the following theorem holds.
Theorem 1.
The Uniform Message Passing in Eq. 2 with learnable weights Can the gradient descent algorithm of the following objective function with node attribute X. being the initialization of
5

---

H.
min Σ C.H
(buoCur + tcge)) + 2tr (H LcH),
HH),,
(9)
s.t. Vu Σ Guv 11 Cuv 1 H HER
(10)
where buv = (auus (x, xj)) denotes the similarity berween nodes and v, according both the topology auv and the distance between attributes dis(x,, x,). A = (awel is the adjacency matrix of G. C represents the collection of Cuv, i.e., the adjacency matrix of the learned graph. Le stands for the Laplacian matrix of the adjacency matrix C.
Theorem can be easily proved. The sketch of the proof is that the minimization of Eq. 2 can be performed by alternately updating Cue and H, which correspond to the two step of Uniform Message Passing. The detailed proof is provided in Appendix.
To further understand the insight of the objective function of Uniform Message Passing, two important theorems are provided. They bridge the graph Laplacian regularization, eigenvalue of the Laplacian matrix and the number of connected components in the graph.
Theorem 2. [Ky Fan's Theorem 30 There exists
min tr HERN LH' f=1
-oy(Le))
(11)
where o (Lc) denotes the 8th smallest eigenvalue of the Laplacian matrix Lc-
Theorem 3. /137 32 |
The multiplicity F of the eigenvalue 0 of the Laplacian matrix Le equals to the number of connected components in the graph, whose similarity matrix is C.
Theorem reveals that the graph can be partitioned into F connected components, if rank N - F. Then, as shown in the following theorem, Uniform Message Passing actually performs graph partitions based on the similarity between nodes, which is calculated with respect both the topology and attribute distances.
Theorem 4. The Uniform Message Pussing in Eq. 2 actually partitions gruph into F connected components based the similarity buv 9 (awes dis xx,,,)) via
min Σ M,0'
(bue + ycuu)
(12)
S.L. Vu Σ Cuu =1, OS Cav S 1, rank(Lc) = N
(13)
Diverse Message Passing in Eq. with learnable weights et extends Uniform Message Passing by propagating different attributes with different weights. By following the derivation of Theorem we can obtain the following theorem for Diverse Message Passing.
Theorem 5. The Diverse Message Passing Eq. components (F groups) based on each similarity
actually partitions graph into connected
(i = g (auvs dis(F:f, Rz5)) via
min Σ C(
(Dff (f) 200 Cuv
{(c(f))2) , 1,.... F.
(14)
s.t. Vu
1, 0 (f) $ 1, ronk(L 22
(15)
Different from Uniform Message Passing, which directly generates F-components partition, Diverse Message Passing generates F groups of 2-components partitions as candidates. Then the classifier in semi-supervised task determines how to combine them to form the final F F-components partition. This shows that Diverse Message Passing possesses a superior representation ability, compared to classic Uniform Message Passing.
3.4.1 Alleviating the Oversmoothing Issue
The powerful representation ability of Diverse Message Passing also indicates that DMP can alleviate the over-smoothing issue. According Theorem in [5), the over-smoothing issue will force all the

---

node embeddings to converge to few vectors, which are fully determined by the indication vectors of the connected components and thus make the nodes indistigguishable In the following example, we will demonstrate that the number of converged vectors from our Diverse Message Passing is much larger than that from Uniform Message Passing, which reveals that our DMP can effectively alleviate the over-smoothing issue.
Given graph G with & connected components {C+) the indication vector for the i-th component is denoted by ( {0, 13k. This vector indicates the relationship between a vertex and the component C. i...
1. 1, EC -
(16)
0, $ C..
According to Theorem 4 the Uniform Message Passing actually partitions the graph G into F connected components. Then, the embeddings in Uniform Message Passing will converge to one- hot vector 10) E {0. 1}*, where only one element is and the other elements are 0, for i 1,...,F. F, i.e, the smor-smg issue appears.
On the contrary. Theorem 5 reveals that our Diverse Message Passing generates F' groups of 2-components partitions, which is equivalent to generating 2 candidate components. If the components partition of the j-th group for node i is represented by scalar 1/ {0. 1}. the F groups of 2-components partitions for node i can be represented by (9) {0, 1] Note that different from 1 (+) e {0, 13 in Uniform Message Passing, where only one element
and the other elements are each element in (0) = {0, 13 can be either 1 0. Then, (6) {0, 13. to which the embeddings in our Diverse Message Passing tend to converge, may possess 2n different values.
The number of different values in (f)) = {0, 1) 2", which is apparently much larger than that in (+) E {0, 11*h i.e., F. Therefore, the number of converged values from our Diverse Message Passing is much larger than that from Uniform Message Passing, which proves that our Diverse Message Passing can effectively alleviate the over-smoothing issue.
For intuitive illustration, toy example with F = 3 is provided here. The embeddings generated from Uniform Message Passing will converge (1, 0, 0). (0, 1, 0) and (0, 1). which makes the nodes less distinguishable. Meanwhile, the embeddings generated from our Diverse Message Passing will converge to (1, O, 0), 1,,1,)), (1, 1, 1), 1,, 0), (0, 1, 1), ) (0, 0, 1) and (1, O, 1), which gives more diverse results. When F increases, the advantage of our Diverse Message Passing becomes more significant.
4 Evaluations
In this section, the proposed Diverse Message Passing (DMP) is evaluated on real data from two perspectives: 1) handling networks with heterophily; 2) alleviating the over-smoothing issue.
4.1 Datasets
Our DMP is validated on 9 networks, which are shown in Table [ These 9 networks can be categorized into 4 types of datasets. Citation networks: Cora, Citeseer, and Pubmed, which are
widely used to evaluate GNNs, are the standard citation network benchmark datasets [33] 34]. In these networks, nodes and edges represent papers and citations among them, respectively. Words in the paper are employed to represent the node features in the bag-of-word form. The academic topic of each paper is taken the label of node. WebKB webpage networks: Cornell, Texas, and Wisconsin are the webpage networks which are captured from the computer science departments of these universities. respectively. In these network, nodes and edges respectively represent the webpages and hyperlinks among them. Similar to the Citations networks, words in the webpage are employed to represent the node features in the bag-of form. The webpages are manually classified into five categories, student, project, course, staff and faculty. Co-oceurrence network: Actor network contains the co-occurrences of actors films, which are extracted from the heterogeneous information networks. It describes the complex relationships among films, directors, actors and writers (35). In this network, nodes and edges stand for actors and their co-occurrences in films, respectively. The actor's 's Wikipedia page is exploited to extract features and node labels. Wikipedia networks:
[
7

---

Table 1: Datasets
Dataset
Cora
Citeseer
Pubmed
Cham.
Squirel
Actor
Cornell
Texas
Wisconsin
# Nodes
2,708
3,327
19,717
2,277
5,201
7,600
183
183
251
# Edges
5,429
4.732
44,338
36,101
217.073
33,544
295
309
499
# Features
1,433
3,703
500
2,325
2,089
931
1,703
1,703
1,703
# Classes
7
Homphily
0.83
0.71
0.79
0.25
0.22
0.24
0.11
0.06
0.16
Chameleon and Squirrel are the webpages extracted from different topics in Wikipedia 33.. Similar to WebKB, nodes and edges respectively denote the webpages and hyperlinks among them, and informative nouns in the webpages are employed to construct the node features in the bag-of-word form. Webpages are classified in term of the averaged number of the monthly traffic. In Table [ the network homophily rates, as computed [20]. are provided. It shows that the citation networks often possess high homphily rate, while others only possess low homophily rate, i.e., they are the networks with heterophily.
Besides, three heterogenous information networks (HINs), i.e., DBLP, ACM and IMDB, are also employed [37] Different from the homogeneous networks shown Table | HINs possess multiple types of nodes or edges, and multiple meta-paths can be utilized. DBLP contains 14.328 papers, 4,057 authors, 20 conferences and 8,789 terms. The authors are classified into four fields. ACM consists of 3,025 papers, 5,835 authors and 56 subjects. Papers are categorized into three fields (Database, Wireless Communication and Data Mining). IMDB contains 4,780 movies, 5,841 actors and 2,269 directors. The movies are classified into three classes (Action, Comedy and Drama) according to their genres. Note that the node features are the bag-of-word form by extracting words from papers/plots.
4.2 Baselines
To demonstrate the superiority of DMP, 12 state-of-the-art methods are adopted as the baselines. Three of them, i.e., GCN 3 GAT [8]] and GraphSAGE [22 are the standard GNNs, which achieve decent performances on networks with high homophily. ChebNet [4 is a classic spectral GNN. GCN, ChebNet and GraphS with JKNet, which combines the multi-scale information via residual connections. MixHop I combines multi-scale information by concatenation. H2GCN [S] shows that concatenation is the key to process the networks with heterophily. Geom-GCN 20 attempts to leverage network embeddings in GNNs for processing the networks with homophily/heterophill.
4.3 Implementation Details
For all the datasets, nodes in each class are randomly split into three groups, 48% for training. 32% for validation, and 20% for testing, as mentioned in S The performances of all the models are obtained by computing the averaged results over 10 random splits. The hyper-parameters, including weight decay, dropout, initial learning rate and patience for learning rate decay, are tuned by searching on the validation set. Adam BE is adopted as the optimizer for all the models. For fair comparisons to GCN and GAT, standard DMP utilizes a two-layered model.
There exists many different implementations of our DMP. The two strategies introduced in Section
3.2 are named as D (Eqs. and 5 and DMP-2 (Eqs. (6) and 77, respectively. DMP-Deg stands for the degenerated DMP introduced in Eq. (8] in Section 3.3 Besides, two implementations,
which consider the combining approach of first-order and second-order topology information, is also realized, i.e., Concatenation in H2GCN [ and GraphSage (2 (denoted "-Con"), and Summation in GCN K and GAT [8] (denoted as "-Sum"). To demonstrate the effectiveness of negative propagation weights in the above DMP implementations, positive weight learning, which replaces tanh(-) in Eq. with so fomam(()) (-), is denoted as "-Posi".
4.4 Supervised Node Classification
The results of supervised node classification are shown Table 2 general, DMP achieves comparable performances networks with high homophily, such Cora, CiteSeer and Pubmed,

---

Table 2: Mean Classification Accuracy (Bold indicates the best, italics indicates the second best).
Methods
Texas
Wisconsin
Actor
Squirrel
Cham.
Coreell
Citeseer
Pubmed
Cora
GraphSAGE
82.43
81.18
34.23
41.61
58.73
75.95
76.04
88.45
86.90
GCN
64.86
56.86
31.12
32.28
53.51
54.05
75.53
84.71
85.51
GAT
58.38
55.29
26.28
30.62
54.69
58.92
75,46
84.68
82.68
SAGE+JK
83.78
81.96
34.28
40.85
58.11
75.68
76.05
88.34
85.96
ChebNet+JJ
78.38
82.55
35.14
45.03
63.79
74.59
74.98
89.07
85,49
GCN+JK
66.49
74.31
34.18
40.45
63.42
64.59
74.51
88.41
85.79
GCN-ChebNet
77.30
79.41
34.11
43.86
55.24
74.32
75.82
88.72
86.76
MixHop
77.84
75.88
32.22
43.80
60.50
73.51
76.26
85.31
87.61
GEOM-GCN
67.57
64.12
31.63
38.14
60,90
60.81
77.99
90.05
85.27
H2GCN
84.86
86.67
35,86
36.42
57.11
82.16
77.04
89.40
86.92
GPRGNN
90.49
85.33
34.17
32.44
51,63
91.14
74.07
88.27
88.14
DMP-Deg
78.38
80.39
33.09
32.46
54,38
83.78
76.87
88.
86.31
DMP-2-Sum
78.37
84.31
34.93
32.18
55.92
83.78
76.27
88.15
85.31
DMP-2-Con
83.78
84.31
34.67
44.28
60.53
83.78
75.97
85.31
85.31
DMP-1-Posi 86.48
84.31
35.72
34.96
51.53
70.27
75.67
88.
86.11
DMP-1-Sum 86.48
86.27
34.21
43.42
50.21
70.27
76.13
88.13
82.28
DMP-1-Con 89.19
92.16
35.06
47.26
62.28
89.19
76.43
89.27
86.52
compared to all the state-of-the-an basclines. Meanwhile DMP significantly outperforms the baselines, especially the methods designed for processing the network with heterophily (such as H2GCN and Geom-GCN), on networks with heterophily (such as Texas, Wisconsin and Squirrel). Specifically, compared to H2GCN, which is the SOTA for processing the networks with heterophily, the obvious improvements on Texas, Wisconsin and Squirrel are 5.10%, 6.33% and 39%76% respectively. This demonstrates the superiority of DMP in handling the networks with heterophily.
Representation Ability: 1) As elaborated in Section 3.2 DMP-2 the simplification of DMP-1, and DMP-Deg is the degenerated version of DMP-1. 1. Then, the ideal representation abilities are monotonically decreasing for DMP-1, DMP-2 and DMP-Deg. The results Table hhave verified the representation abilities of these methods. The performances of DMP-1 1 are higher than that -M and both of them give much higher performances than DMP-Deg. The performance gaps are more remarkable networks with heterophily, since these networks require GNNs to possess powerful representation ability to exploit the informative attributes. 2) GraphS MixHop and H2GCN have shown that the concatenation strategy possesses high representation ability than the summation strategy employed in GCN and GAT. This strategy is also employed in the implementation of DMP. In Table 2 the accuracies of "-Con"'s negative propagation weights is also validated by the improvements of DMP-1-Con over DMP-1-Pos. especially the networks with heterophily. Therefore, DMP-1-Con exploited the final DMP implementation, which will be used in the following experiments.
higher than those of "-Sum" 3) The superiority of allowing
4.5
Semi-supervised Classification on Heterogenous Information Networks
Since only type of nodes labelled in HINs, the
Table 3: Accuracy on HINs in terms of Macro-F1 Score.
effectiveness of DMP is verified on the nodes with given labels. For the semi-supervised node classification task, 20% of the nodes in each class are utilized for training.
Methods
DBLP
ACM
IMDB
To demonstrate the universality. DMP ignores the node types and meta-paths used in HAN (37 and treats the networks homogenous networks. Two implementa- tions of DMP, i.e., DMP-1 1-Cnn and DMP-1-Sum, are compared GAT 18 and HAN 337. The classifica- tion accuracies in terms of Macro-FI Score are reported in Table S As can be observed, HAN outperforms GAT by manually selecting the semantic meta-paths and combining the results from multiple peta-paths. Although the proposed DMP ignores the semantic meta-path, can still achieve comparable or better performances compared HAN. The main reason of this surprising results is that DMP can explore more semantic information and learns the meta-paths instead of manually
GAT HAN
90.97
86.23
49.44
92.83
90.96
56.77
DPM-1 1--um
84.56
92.62
58,58
DPM-1-Con
92.49
92.64
57.73

---

Actor
Cora
Citesser
Pulomed
0.34
0.7
Accuracy
7-
0.30
0.20
0.4
6
0.4
DPP
0.3
Number of Layers
Number Layers
Number Layers
Number of Layers
Figure 2: Classification accuracy results with various model depths.
Cora
Citeseer
Texas
Cornell
AcCurDc
Scone Dimansion
Scores Dimension
Figure 3: Distributions of the learned weights of sampled attribute dimensions.
selecting. Specifically, since HINs consist of multiple nodes or edges, the mutual impacts between different kinds of nodes tend to be different. These differences can not only be manually utilized by selection semantic meta-paths as HAN, but also be automatically exploited DMP, which allows diverse attribute propagations. Apparently, the results demonstrate the superior representation ability of DMP.
4.6 Alleviating the Over-smoothing Issue
the potential on alleviating the over-smoothing issue is theoretically analyzed. In this section, this potential is experimentally verified on networks with homophily. The performance comparisons between DMP and GCN with various model depths are shown Figure 2 As can be observed, when the number of layers increases, the performances of GCN tend to significantly degrade, while the performances of DMP remain stable. This trend verifies that DMP can effectively alleviate the over-smoothing issue.
In Section 3.4
4.7 Visualization of Learned Weights
To provide an intuitive understanding, this section provides the visualization of the distributions of learned weights of each attribute dimension. Due all networks possess high attribute dimension, only 8 attribute dimensions are sampled for each network. For each attribute dimension, different edges obtain different propagation weights via learning scheme. Figure 3 visualizes the distributions of learned weights of sampled attribute dimensions. Most learned weights in networks with homophily, such as Cora and CiteSeer, are positive, while those networks with heterophily, such as Texas and Squirrel, are positive. This also meets the definitions of networks with homophily and heterophily.
Conclusions
This paper investigates the attribute homophily rate and its impacts on the design of GNNs. Most of the existing GNNs perform uniform message passing by ignoring this factor. However, statistics on networks have revealed that attributes usually possess diverse homophily. To better exploit this observation, Diverse Message Passing (DMP) framework, which specifies each attribute propagation weight along every edge, proposed, and two specific strategies are proposed reduce computational complexity. A theoretical analysis is provided to show that Diverse Message Passing may break the ceiling of representation ability of the spectral GNNs, as well as alleviate the common over-smoothing issue. Evaluations on real networks have verified the superiority of Diverse Message Passing on handling the networks with heterophily and alleviating the over-smoothing issue, compared the ofthe-ff methods.
10

---

Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China under Grant 61972442, Grant 61802391, Grant 62 1022411, Grant U2001202, Grant U1936208 and Grant 61802282, in part by the Key Research and Development Project of Hebei Province of China under Grant 20350802D and 18020D,,, in part by the Natural Science Foundation of Hebei Province of China under Grant F2020202040, in part by the Natural Science Foundation of Tianjin of China under Grant 20/CYBJ000600, in part by the Science and Technology Specialists Project from Science and Technology Program of Tianjin under Grant 20YDTPJC00670, and in part by State Key Laboratory of Software Development Environment under Grant SKLSDDE20000Z-11
References
[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24, 2021.
[2] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. AI Open, 1:57-81, 2020.
[3] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. 2017.
[4] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Wein- berger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 6861-6871, 2019.
[5] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3538-3545, 2018.
[6] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[7] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stock- holmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 5449-5458, 2018.
[8] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Ad- vances in Neural Information Processing Systems 33; Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020.
[9] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[10] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 1725-1735, 2020.
[11] Sami Abu-El Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, pages 21-29, 2019.

---

[12] Sitao Luan, Mingde Zhao, Xiao Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 10943-10953, 2019.
[13] Yu Rong, Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Abubu, Ethiopia, April 26-30, 2020, 2020.
[14] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang. Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi- supervsee learning on graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-1 2020, virtual, 2020.
[15] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond wwwfrrquency information in graph convolutional networks. In Thirty-Fifthh AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 3950-33 9950-3957, 2021.
[16] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
[17] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.004462 2021.
[18] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations ICLR 2018, Vancouver, BC, Canada, April 30 May 2018, Conference Track Proceedings, 2018.
[19] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001.
[20] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
[21] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML. 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 12331122,,0011
[22] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages (024-1034, 2017.
[23] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[24] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29; Annual Conference Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3837-3845, 2016.
[25] Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. In International Conference on Learning Representations, 2021.
[26) Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks graph signal denoising. arXiv preprint arXiv:2010.01777, 2020.
12

---

[27] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In WWW '21: The Web Conference 2021, Virtual Event / jubbljnn,, Slovenia, April 19-23, 2021, pages 1215-1226, 2021.
[28] Liang Yang, Chuan Wang, Junhua Gu, Xiaochun Cao, and Bingxin Niu. Why do attributes propagate in graph convolutional neural networks? In Thirty-Fifhe Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Virtual Event, February 2-9, 2021, pages 4590-4598, 2021.
[29] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In KDD 20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pages 338-348, 2020.
[30] Ky Fan. On a theorem of weyl concerning eigenvalues of linear transformations Proceedings of the National Academy of Sciences, 35(1 1) 1):662 655, 1949.
[31] Bojan Mohar, Y Alavi, G Chartrand, and OR Oellermann. The laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 11871-89)):1,, 1991.
[32] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[33] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
[34] Galileo Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In International Workshop on Mining and Learning with Graphs, 2012.
[35] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 807-816. ACM, 2009.
[36] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv:1909.13021 2019.
[37] Xiao Wang, Houye Ji, Chuan Shi, Bai Wang. Yanfang Ye, Peng Cui, and Philip S. Yu. Het- erogeneous graph attention network. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 2022-2032, 2019.
[38] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
13


Reviews:
[{"review_id": "mrnNSQuOWTf", "reviewer": "Reviewer_wnNV", "summary": "This paper focused on improving graph neural networks from homophily and over-smoothing issues by introducing a diverse message passing (DMP) framework. Experiments on 9 public datasets with a variety of homophily scores were provided to validate the effectiveness of the proposed method. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n-\tFollowing previous works [8], the motivation of this work is clearly presented.  How the proposed method connects to existing GNN methods has been elaborated in both spatial and spectral domains. \n-\tWhile the proposed implementation is simple and straightforward, some theoretical analyses (Theorem 4 and 5, though with some key typos) have been provided to demonstrate the benefits of DMP over the uniform message passing. \n-\tExtensive experimental results have been provided in terms of different homophily graphs and model components. Plus, experiments on heterogenous graphs and deep GNNs have also been conducted. \n\nCons:\n-\tThe technical contribution of this work is limited since the proposed method mainly follows the framework provided in [8] and adopts a similar implementation way to compute “attentions” over attributes as in [18,22,23]. \n-\tSome claims are over-emphasized as the proposed method is clearly built on top of several theoretical frameworks [6-8, 28]. To name a few, “existing spectral GNNs are just equivalent to a degeneration of diverse message passing”, “diverse message passing may break the ceiling of spectral GNNs”, etc.\n-\tThe proposed method might be ad hoc to the datasets with low homophily rates. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Suffice.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "heixjKp8ZAO", "reviewer": "Reviewer_brCz", "summary": "This paper extends the node-level network homophily based on the node label to attribute-level one by considering each attribute as a weak label. Then, it observes that different attributes have diverse attribute homophily rates. To alleviate the issue of existing uniform message passing on capturing this diverse attribute homophily rates, this paper proposes diverse message passing, where different attributes are assigned different propagation weights, and two implementations. Finally, it theoretically investigates the ability of diverse message passing on overcoming over-smoothing by analyzing the roles of the uniform and diverse propagation weights. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The extension from network homophily rate to attribute homophily rate makes sense since node attributes can be seen as the weak label to represent the node compared to the node label. It is interesting to separately consider the homophily rate of each attribute and propose diverse propagation weights for different attributes. By comparing the proposed two implementation strategies and the interpretation from the spectral perspective, the two strategies can be regarded as a compromise between the expressive power and the overfitting issue. Thus, I think the proposed diverse message passing is effective in capturing the diverse homophily rate of different attributes. Therefore, this paper is technically sound.\n\nBesides, the theoretical contribution of this paper is significant. Different from previous works, which often consider the over smoothing issue is caused by the over propagation, this paper shows that the over smoothing issue is actually induced by the uniform propagation. The theorems show an interesting finding that the propagation weight learning is equivalent to graph partition, and connect the graph partition and over smoothing issue. Thus, the theoretical analysis provides a new perspective to understand the over smoothing issue. \n\nThe experimental evaluation is sufficient. It demonstrates the superior performance on networks with heterophily and heterogeneous information networks and the ability on preventing the over-smoothing issues.  \n\nAlthough I think this paper is interesting and novel, there are also some concerns. \n1.\tWhy the performance improvements on networks with heterophily are more significant than those on networks with homophily?\n2.\tThe explanation of why multiple graph partition just below theorem 5 is hard to understand. It is better to reorganize this paragraph.\n3.\tThe description of the data in Figure 1 is not very clear in the appendix.\nThe performance of the proposed DMP can’t outperform some SOTA methods designed for heterogeneous such as MAGNN.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "OQyOGmex1Y9", "reviewer": "Reviewer_RdEt", "summary": "The authors extend network homophily rate to attribute homophily rate by taking attribute as weak label and design diverse message passing (DMP) framework to specifiy each attribute propagation weight along each edge. The authors show that DMP can prevent  over-smoothing and handle network with heterophily.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. Although DMP looks like a simple extension of GAT, I think to form uniform and diverse message passing into an optimization problem is interesting.\n2. The visualization looks good.\n\nWeakness&Advice:\n\n1. Line 74, “ddimensions” —> “dimensions”\n\n2. In equation (3), is it possible to get a zero denominator? Do you assume all elements $x_{vf}$ are positive?\n\n3. In equation (4)(6), DMP looks like a channel-wise GAT with attention values in (-1,1). The contribution and novelty in section 3.2 are limited.\n\n4. In theorem 5, should add $f=1.\\dots, F$\n\n5. Line 213-216, “different form Uniform Message Passing, which directly generates a F-components partition, Diverse Message Passing generates F groups 2-components partitions as candidates and then the  classifier in semi-supervised task determines how to combine them to form the final F-components partition.” For shallow GNNs, why generating  F groups of 2-components partitions is better than generating one F-components partition on semi-supervised learning. Need more explanation.\n\n6. The dimension of $X$ is $N\\times F$ and F is number of partitions you use in section 3.4. What is the relation between the two $F$ or do I miss something? $F$ is an assumption or a restriction for theorem 4?\n\n7. Making correction of theorem 5 in supplementary material seems not to be allowed.\n\n8. Should add a comparison with GPRGNN, which is a new model to solve heterophily problem.\n\n9. Standard deviation should be provided in table 2&3.\n\n10. There are two strategies proposed to reduce the number of learnable parameters. So what is the running speed of the current models and how they compare with the existing methods?\n\n11. How well does DMP on solving over-smoothing compared to the existing models.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "2hSLnqQZdG", "reviewer": "Reviewer_x1nw", "summary": "This paper proposes a diverse message passing framework (DMP) to generalize a classic uniform message passing framework and also suggests strategies preventing over-smoothing issues.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "================================================================= \n\n[Main Strengths] \n\nThis paper's main strength is that the motivations of the work are well described (as shown in SEction 3.1) and evaluations across various homophily rate datasets (see Table1) are well designed. \n\n================================================================= \n\n[Main Weaknesses] \n\nThe paper's main weakness is the somewhat limited merits of the theoretical analysis shown in Section 3.4. In particular, the potential benefits of the contribution of Theorem 5 toward preventing an over-smoothing issue are not clear to me.\n\n================================================================= ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not provide the “limitations and social impact” of this work in the paper.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5 hour"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a message passing scheme for graph neural networks(GNNs) derived from homophily.  The problem is clearly motivated. The distinctness of the work is brought vis-a-vis GNN models has been elaborated in both spatial and spectral domains. One of the reviewers appreciated the theoretical insights which help in understand the shortcomings of existing literature. However the main concern seems to be that comparisons of the State of the art need to be improved.

Decision: Accept (Poster)