GReTo: Remedying dynamic graph topology-task discordance via target homophily
Authors: Zhengyang Zhou
Qihe Huang
Gengyu Lin
Kuo Yang
LEI BAI
Yang Wang
Venue: ICLR 2023 poster (2023)
Keywords: Dynamic graph
graph homophily theory
Graph Neural Network
topology-task discordance

Abstract: Dynamic graphs are ubiquitous across disciplines where observations usually change over time. Regressions on dynamic graphs often contribute to diverse critical tasks, such as climate early-warning and traffic controlling. Existing homophily Graph Neural Networks (GNNs) adopt physical connections or feature similarity as adjacent matrix to perform node-level aggregations. However, on dynamic graphs with diverse node-wise relations, exploiting a pre-defined fixed topology for message passing inevitably leads to the aggregations of target-deviated neighbors. We designate such phenomenon as the topology-task discordance, which naturally challenges the homophily assumption. In this work, we revisit node-wise relationships and explore novel homophily measurements on dynamic graphs with both signs and distances, capturing multiple node-level spatial relations and temporal evolutions. We discover that advancing homophily aggregations to signed target-oriented message passing can effectively resolve the discordance and promote aggregation capacity. Therefore, a GReTo is proposed, which performs signed message passing in immediate neighborhood, and exploits both local environments and target awareness to realize high-order message propagation. Empirically, our solution achieves significant improvements against best baselines, notably improving 24.79% on KnowAir and 3.60% on Metr-LA. 

Published as a conference paper at ICLR 2023
GRETo: REMEDYING DYNAMIC GRAPH TOPOLOGY- TASK DISCORDANCE VIA TARGET HOMOPHILY
Zhengyang Zhou?, Qihe Huang", Gengyu Lin?, Kuo Yang", Lei Bai*, Yang Wang -2.3+
Keey Laboratory of Precision and Intelligent Chemistry, University of Science and Technology of China (USTC), Hefei, China
Schooo of Software Engineering, USTC. Schooo of Computer Science and Technology, USTC.
"Shanghai AI Laboratory, Shanghai, China
{zzy0929, hgh, 1 lingengyu, vangkuo)@me @mmal 1, ustc. edu cn, ba maisanshin @mmai i 1. com, angyan@ustc. edu.cn"
ABSTRACT
Dynamic graphs are ubiquitous across disciplines where observations usually change over time. Regressions on dynamic graphs often contribute to diverse critical tasks, such as climate early-warning and traffic controlling. Existing ho- mophily Graph Neural Networks (GNNs) adopt physical connections or fea- ture similarity as adjacent matrix to perform node-level aggregations. However, on dynamic graphs with diverse node-wise relations, exploiting a pre-defined fixed topology for message passing inevitably leads to the aggregations of target- deviated neighbors. We designate such phenomenon as the topology-tase discor- dance, which naturally challenges the homophily assumption. In this work, we revisit node-wise relationships and explore novel homophily measurements on dynamic graphs with both signs and distances, capturing multiple node-level spa- tial relations and temporal evolutions. We discover that advancing homophily ag- gregations to signed target-oriented message passing can effectively resolve the discordance and promote aggregation capacity. Therefore, a GReTo is proposed, which performs signed message passing immediate neighborhood, and exploits both local environments and target awareness to realize high-order message prop- agation. Empirically, our solution achieves significant improvements against best baselines, notably improving 24.79 79% on KnrwAir and 3.60% on Metr-LA.
INTRODUCTION
Graph-structured data mining has become a popular technique in numerous disciplines, such as social networks You et al. 2022), road networks (Chen et al., 2020). and molecule analysis (Abu- EI-Haija et al. 2019). However, existing solutions to graph mining usually make the assumption of homophily on graphs where connected nodes tend to share similar features or have the same labels (targets). Actually, in real-world graphs, the homophily assumption does not always hold on (Zhu ct al. 2020). Thus, Graph Neural Networks (GNNs) considering heterophily proposed to break the homophily assumption, which disentangle the complex neighborhood components (Ma et al,
2019 Du al. 2022) and model the edge diversity (Zhu et al.] 2021a] Wang al. 2022a) by separately aggregating similar and dissimilar signals (Bo et al. 2021 Yan et al. 2021 Despite achievements, heterophily GNNs are mostly investigated on classification tasks over static graphs while less explored on node-level regressions over dynamic graphs Therefore, it provides an oppor- tunity to dissect how edge-type disentanglement boosts regression capacity on dynamic graphs
Regression tasks are more challenging than classification as the latter only considers discrete labels with much tolerance (Wang et al.) (2022b). Actually, nodes in dynamic graphs are more prone suf- fer complex neighborhood distributions (Ma et al. (022) due to the existence of time-varying values and different edge types, incurring misleading message passing when aggregating terget-deviated neighbors. The misleading message passing is formally designated as the topology-task discordance in our work (see Fig. aa)). We take traffic volumes of road networks as an intuitive example of edge
Prof. Yang Wang is the corresponding author.

---

Published as a conference paper at ICLR 2023
diversity in Fig. (c)- The neighboring intersections sharing -arrrearmdd connectiv- ity can be positively correlated, while interactions locating parallelly on the same Origin- Destin tran- sition tend to be negatively correlated with contended relationship. These two-type edges respec- tively account for homophily and heterophily components and these correlations will also change over time with tidal patterns. Consequently, uniform aggregations these two-type neighbors will involve interfered noise and deteriorate the performances of GNNs, as not all of them have consis- tent evolution direction towards targets. Empirically, in four real-world dynamic graphs. both low homophily ratios within intra-grapy frames and across temporal adjacent frames (Fig. (d) imply that physically-connecee
nodes are not necessarily with close observations or with same varia- tion directions. This not only supports the argument of topology-task discordance, also manifests the universality of such phenomenon across different dynamic graphs Furthermore, due to the heterogeneous local structures and neighborhood distributions, the topology-task discordance can be propagated to high-order neighborhoods. In other words, the optimal receptive fields should be adaptively and efficiently constructed to realize controllable neighborhood aggregation, thus avoid- ing noise involvement. Therefore, for dynamic graphs, remedying topology-taie ttak discordance in both immediate and high-order neighborhoods is urgently desired.
Based on the apatial-temporis property within node-wise relationships, adapting existing ho- mophily theory to address such topology-task discor- dance is still challenging. The key obstacles can be summarized as 1) how to determine which pairs of nodes belong to homophily components without cat- egorical labels, 2) how to involve targets to reconstruct node-wie wise correlations, thus materializing remedied and powerful target-oriented aggregations, 3) how to exploit the dynamic local neighborhood environments to achieve personalized high-order propagations.
Challenges.
Devershaar
Postively
correlated
(a) Tegrsbag tonk Niigher
(bi Hamsphib iiighloeboo
upripttis the
Negalively corralated
(n) Eletoraphit neightorhood
(4) Awwraget lonnepiity THET Catzees
Figure 1: Illustration of edge-type diversity and statistical graph homophily.
Present work. Our work empirically and theoretically elucidates the existence of topology-task discordance and explains the failure of homophily GNNs on dynamic graphs. To get rid of such dilemma, we propose a novel GNN to Remedy Topology-tan discordance via Target-homophil, (GReTTo). Firstly, we extend the node-wise relations to triple tuple based on signed-distance proximity, and construct two measures including intra- and inter-graph homophily capture diverse spatial-temporal rela- tions and overcome lacking categorical labels. Secondly, by introducing the target awareness with a transition homophily predictor, we incorporate two signed homophily measures to facilitate target- oriented message passing, renewing the activeness of GNNs. Finally, instead of imposing nested or bi-le inefficient optimization (Xiao et al., 2021), , we devise an adaptive layer- wise importance measurement to promote the immediate neighborhood aggregation towards high-order propagations, by identifying the informativeness of each propagation step relative to the expected targets. We evaluate our solution on four dynamic graphs and successfully achieve 3.20% to 24.79% improve- ments against baselines on MAPE, where Air (t 24.79% with higher intra-graph negative heterophily ratios (Tab. 4 especially benefits from flexible signed message passing.
Contributions. (1) We formalize a dynamic graph homophily theory, jointly characterizing multi- type node-wise relations considering spatial-temporal property. (2) On dynamic graphs, we analyze the topology-task discordance and corresponding solution from its existence to the solution to per- sonalized high-order propagation. (3) We propose GReTo, consisting of a signed target-oriented message passing and layer-importance based high-order propagation, to refine the topology adapt- ing downstream regression tasks.
2 RELATED WORK
GNNs have become an admirable tool of diverse graph-structured data mining (Song et al. 2022 Kipf & Welling 2016 Abu-El-Haija et al. 2019). To boost the representation capacity of traditional
'Observations refer to the observed node features the graph.
Following graph construction on existing literature (Yu et al. 2018 Guo al. 2019 Li et al. 2018), we
establish the edges between nodes by selecting top-5% geographical proximal nodes neighbors.
2

---

Published as a conference paper at ICLR 2023
GCNs, GAT (Veličković al. 2018) modifies the conventional GNNs by allowing flexible node- level attention, while Directional GNN (Beaini et al. 202I) exploits directional derivatives to en- dow GNNs with the anisotropic property and overcome the oversmoothing issue. Recently, multiple
node-level relations motivate the research trend of homophily theory that measures the consistency between the original topology and node-wise features (or labels) (Zhu al. 2021b [o al.. (021). ) These techniques respectively design bi-kernel aggregations (Du et al. 2022] Yan et al.) 2021) and high-order neighborhood modeling (Ma al. 2022; Zhu et al., 20200) to advance the standard GNNs towards more powerful aggregation in addressing heterophily. Besides, researchers carefully devise various high-order propagations by a bi-level learn-to-stop optimization (Xiao al.
[22T]] or layer-
shared weighted aggregation (Chien et al.) 2020). Even flourishing, graph theories mostly focus on classification over static graphs, thus resulting in the opportunity of adapting emerging theories to dynamic graphs. Dynamic graph learning usually adopts RNN backbones (Ruiz et al. 2020 You
ct al. 2022 Bai et al., 2020) in a spatial-temporal manner, where they construct various adj matrices via similarity (Zhou et al., 2020), or learnable embedding product (Wu et al. (0220b. And
two pioneering works D2STGNN (Shao et al., 2022) and TAMP-S2GCNET (Chen et al. (021c), respectively motivated by the dynamic composition separation and time-conditionee topology data, are proposed to capture the spatiotemporal dynamics. Among them, all these works generate the non-negative adjacencies and neglect the influence of evolution trend on topology. However, due to the topology-task discordance induced by node dynamics and edge diversity, these works thus fail to realize the target-oriented aggregations. In contrast, our work investigates the homophily theory in dynamic graphs to capture 'good' neighbors by explicitly modeling the target-related temporal evolution influences. Detailed related works can be found in A.2
3 PRELIMINARIES
Let T = (1, T} be a temporal step set and denote the dynamic graphs as G = (Gi, G2...., Ge,..,, Given step L, G. = (V, X,, Ar} represents the valid observation of graph G. Specifically. the node set V {ui, U2 uN } is with the cardinality of N, and the matrix A, .R-N describes the static weighted adjacency relationship of G.. Let F be the number of fea- ture dimensions of each node 3l then X; = {zं. zz..... .... #n} NxF serves as the feature matrix. The goal of our dynamic graph regression is derive an optimized graph learning function F to
predict the observations across the whole graph for the next step. i.e., XT+1 Fj X, Aglt 2, T,, θ). We name At)lt = 2.., T} and XT+1 respectively as the historical and targeted observations, while O refers to all learnable parameters.
3.1 DYNAMIC GRAPH HOMOPHILY THEORY
We first introduce the conventional graph homophily ratio in classification (Zhu et al. 2020; Ma et al. 2021), which is defined as the fractions of nodes in their neighborhoods that with the same label y, as Ug i.e., ho; ZiyeW(or) T(H wy;)
Here, N(;;;) refers to the neighboring node set of e;- In contrast, we propose our dynamic graph homophily theory to adapt the continuous data space. Our dynamic graph homophily theory includes descriptors of homophily measurements and local neighborhood environments, which are two factors of node-level and neighborhood-leww statistics that inherently affect the information propagation. Concretely, we first exploit signed distances to extend the binary relations to a triple tuple, compensating for non-explicit class boundaries. For dynamic graphs, we formulate an intra-graph spatial homophily capture node correlations in same graph frames and an inter-graph transition homophily to extract temporal evolution between adjacent temporal frames. Second, to numerically depict the neighborhood on both structures and neighbor compositions, we integrate the topological feature (node degree de) with homophily distribution as local neighborhood environments.
[N(
Definition (Intra-graph spatial homophily and Inter-graph transition homophily) Both intra- and inter-graph homophily can be categorized into three classes according the feature distances by a proximity threshold e, with the signs indicating the direction of proximity. Given a serial graphs G, temporal step and node Us the intra-gruph homophily (*īt)) and inter-graph homophily (mtt))
We set F=1 but is orthogonal to our theory can he easily extended to tensor formats.
3

---

Published as a conference paper at ICLR 2023
respectively defined by symmetric formation (see Fig.
(a) as,
1-
1|
|zi1l
<
-
(mig)s
6,
-
E
(mi))=
1|
11
S
(v, (Nu)))
(I)
1.
|=|||
>
In particular, the signed direction indicates how will the node value change when it aggregates a specific neighbor in Tig. while the direction demonstrates how the node is expected to change to reach the target TT.
Definition (Local neighborhood environments (LNE)) LNE consists of local structure descrip- tions and neighborhood distributions. Given node vs, we let the node degree d; describe the local structure and further partition the nodes of its neighborhood (vx) into three groups based on node-wise feature distances. In detail, the neighboring components those are proximal, positively deviated, and negatively deviated away the central node vi are respectively considered as spatial homophily (N(v)) positive heterophily (N(v:)) op and negatively heterophily (N (N(v)) gu We can transfer the neighborhood components into numerical Neighborhood Distributions vector Tey
Σ U = c) Σ Eim = 1) Σ 1mm = -1)
The, (Par 9p:4n))
[V(ee]] 3
(u, N(u))
W(v.)]
[V(w))
where (Pe: 9p. 9n)
{p(mii E). p(Tj( 1), =- 11]] Then the local neighborhood envi- ronment can be denoted LNE., (di, Pá Aps 9m.).
4 DISCORDANCE BETWEEN TOPOLOGY AND TASKS
In this section, we show the discordance between the topology and task, when adopting traditional homophily GNNs. Given serial graphs G and node v, (I) the ratio intra-graph spatial homophily Te, (p.) is simplified to Ps, while the ratio of other node-level relations is denoted qi 1 Ps. (2) the target coefficient % quantifies the relationship between the targeted step + and a given step & by z T++ yaz Our analysis only considers aggregations from T T + 1, and let x 2 na? We ignore the temporal superscript for simplification in following analysis. Actually, given target coefficient "/i a successful aggregation can be equivalent to finding a valid d, to construct an appropriate neighborhood for achieving targets. Therefore, we establish the relationship between % and degree d, to find what conditions will the comophily-assumee graph aggregation fail.
Theorem 1 (Proof in Appendix B.I)
Consider impoxe a homophily GNN Fg X for node-level regres- sions, the relationship between the expected degree and target coefficient T3 is.
(-00 1300-11;- 1), 74 < <s 80, 7i P:
d,
0. +00), P: 11
(1,0),, >>
Theorem [ demonstrates that homophily aggregations cannot find the optimal neighborhoods to achieve the targeted results when 7/2 P; and % 1. In other words, the homophily GNNs will fail when the gap between historical observations and targeted prediction value is large.
5 REMEDY TOPOLOGY-TASK DISCORDANCE ON DYNAMIC GRAPHS
In this section, we propose our solution, GReTo, to remedy the topology-task discordance dy- namic graph regressions, where it consists of Signed target-oriented message passing, and Person- alized high-order layer propagation. The framework overview is illustrated in Fig.
5.1 SIGNED TARGET-ORIENTED MESSAGE PASSING
Overview. We first provide theoretical analysis the potential of aggregation capacity improve- ment by exploiting homophily theory. Then we propose to design a signed target-oriented message passing, which captures the task-oriente evolution direction remedy the dynamic graph topology.
4

---

Published as a conference paper at ICLR 2023
Theorem 2 (Proof in Appendix B.2) Given central node vs, and target coefficient Ti pt or 74 > L, the aggregation capability can be improved by a sign-preserved directional message passing that separately aggregates positive and negative heterophily compositions. Under such message passing, we denote 8p > and by < the signed kernels, then the aggregation algorithm can conditionally converge to x² where di satisfies the following two conditions.
Ii + d.p:(1 + E)=; + 8p
E Wpds + Bq
Σ (vc)
ETh'1 d, E E
2; +1
(E))
T: d: + 1)
d +1
dj
(4)
where the expectation of neighbors with intra-graph homophity denotes dip:(1 + E) (+x) and N- N-(wx) denote the positively and negatively heterophily neighborhoods, and wp: We are learnable weights. Detailed conditions for obtaining targets are demonstruted Appendix B.2 With these derived conditions, we can estimate whether the GNN can successfully aggregate the neighbors towards targets when the dataset is given.
Therefore, the key to our target-oriented message pass- ing becomes investigating both intra- and inter-graph homophily to discover the target-beneficial neighbor- hoods, and devising meaningful directional aggrega- tion. The technical stages are three-fold, 1) discover the target-oriented homophily neighborhoods, 2) pre- dict node-wise inter-graph transition homophily to en- able target awareness, and 3) disentangle different types of neighborhoods for target-aware aggregations.
cakulged
homaphiy prodicer
Insarriance mheastree
Torgeh-arentes homophlly disertinlenent
Tarpet homoppiy agg soyregation
hale vgrily aggrugatonn
Propagater
Signed to reel-aneetto message passing
Persaralied righ-arder order layer Propagatton
Target-homophhe neighborhood discovery. To ex- plicitly distinguish target-oriented neighboring nodes, resort our dynamic homophily theory with both signed direction and proximity. Considering that the signs in these two homophily measurements indicate the directional consistency, we couple the spatial one and transition one to derive con- sistency between the intra-graph connections and the targeted graph. The signed target-oriented neighborhood disentanglement matrix M can be achieved by an element-wise division Ø, i.e.,
Figure 2: Framework overview of GReTTo.
Mij = Tmī, where . is the estimated transition homophily that will be predicted in the next subsection. This design of division enables each Myj E formative edge descriptions, i.e., each edge value can not only discriminate the target-oriented nodes (with positive signs) as good neighbors, but also measure the degree of node-wise proximity where larger values imply more target- anreet-oriente consistency and contribution. By splitting M based on the edge signs, we can achieve the target-oriented homophily and heterophily neighbors by,
- in M to possess in-
M = [M] + [M]
(5)
In Eq 5 [M] is the disentangled aggregation matrix with positive elements interpreting the target- homophily adjacent connections, while [M] composes negative values explaining the target- heterophily relationship. Noted that although the original triple relations are shrunk into the signed matrix for efficient implementations, the directional proximity indicating the informativeness for aggregation towards targets is carefully preserved by diverse values in M.
Inter-graph transition homophily predictor. Since the transition homophily is not available during inference stages, we formulate a sequence classification task to predict which type of relation that the transition homophily belongs to. However, computations among node-level transition homophily are inefficient, we thus reduce the transition homophily to self-transition homophily between adjacent steps Sig = (m 1 1-117 which can be available from historical observations. Then, we leverage the nice property of periodicity and continuity in time-series to construct the sequence learning. This time-series learner concatenates two parallel LSTMs and one Conv ID to capture the evolution and trend dependence by taking step-wise historical node observations and self-transition homophily [X;; Sig'](t = 1, 2.,, T) as inputs. Thus, we obtain the estimated next-step representation by.
Sig R
ConvID(LSTM(XX, Xz,.., Xr):LSTM(Siig Sig?,.., Sig"))
(6)
5

---

Published as a conference paper at ICLR 2023
T+1
We then utilize the time-series representation Sig n for a three-category classification where the class probability estimated with an MLP parameterized by W., i.e.
T+1 p. qo |+ MLP((Sign W&))
7+1
The estimated p. 9p. On refer to probabilities of three homophily categories that Sig g. belongs
to, and then we can obtain the final Sig T+1
based on these probabilities.
Disentangled signed directional message passing. With modified transition homophily Sig T
the disentangled target-oriented matrix can be altered as My = Sig, (TiT)) ). To accommodate separate aggregations over different types of node-wise connections, we take advantage of the pos- itive target- homophily matrix [M] and negative target-heterophe matrix [M]x to respectively
filter the adjacence A; where we impose self-loop on the adjacence A A + I. Thus, the two aggregation kernels can be realized as,
(fz): ([M)[) O A., (fx). ([M)N) o.
(8)
where @ an dementtwwiee Hadamard Product for kernel filtering. Considering the relational prop- crty of node-wise signals over graphs, fr, and fn are respectively interpreted as low-pass filter and a high-pass filter in graph convolutions (Bo et al. 202T). Then the disentangled signed directional message passing can be formulated as,
AGGR((: = Σ (ft)eszuu,+ + (1- JEN2(())
Σ (fu)azzun
(9)
(ENN(())
where (vg) and (u;) denote the target-homophily and target-heterophily neighbor set re- garding ui and a adjusts the proportion between two compositions. In addition, Wp Wp and Wn E W are two learnable parameters for feature transformation. In Eq. 9 the negative kernels can make sense when the aggregated neighbors exactly negatively correlated with targets, which potentially closes the gap between historical node observations and targeted ones. Thus, our strategy can explicitly model multi-type edges and boost our aggregation power.
5.2 PERSONALIZED HIGH-ORDER LAYER PROPAGATION
Overview, Since the propagation step is a discrete value, it is intractable to directly optimize such discrete values. In this subsection, exploit the local neighborhood environments to quantify the informativeness of node representations at each propagation step, which determines when to stop the propagation in a soft manner. Concretely, our high-order propagation with two components, an adaptive layer importance measure and high-order propagation blocks.
Relationship between local neighborhood environments and propagation steps. Given node vy (1) the optimized propagation step is determined by the proportion of target-homophily neighbor- hoods p; (rather than intra-graph homophily P:) and the substructure description d,. (2) the smaller values of d; and p; are, the larger propagation step K is expected. By denoting INFO(M) ) as the target-oriented information encapsulated in the representation of the k-th propagation step in mes- sage passing, Theorem 3 demonstrates the quantitative relationship between the informativeness of each propagation layer and the local neighborhood environments, to verify our qualitative analysis.
Theorem 3 (Proof in Appendix B.3) Consider a series of dynamic graphs G that conform to the neigh- borhood distribution ((x)) ~ (P. 9p. qu) where enforce 4u 19p, + qp + 1/4 = 1. Consider x. T+1 = qh. > of with 7/s > 1, the quantitative relationship among the layer-specific target-oriented infor- mation (hF) substructure di, and the target-homophily P. as follows. Under this case, the expected target-homoppe homephilm compositions of neighborhoods p. becomes quo and difference between the probability of hitting beneficial nodes in the second layer and the first layer AP(N4)) is (-1 - 2n)4 + 9p. We have,
INFOO?)) INFO(H!), 0< < 1+27
INFO(RE) Z INFO 4p 1+27
(10)
The symmetric results be achieved when we have small 7/ satisfying 7/

---

Published as a conference paper at ICLR 2023
Theorem Bl verifies that in dynamic graphs with complex neighborhood distributions, lower node- level activeness and target-oriented homophily must result in larger receptive fields and vice versa. Therefore, are expected to pick the high-order neighbors that are turget-homopilly.
Adaptive layer importance measurement. To pick the high-order target- hrogethhomophily neighbors, we transfer this challenge to measuring the consistency between high-order neighborhood distributions and transition homophily distribution of targets. First, we exploit the edge composition Th, to con- struct neighborhood distribution matrix ND, Neightf (X) (Ty) Tegi... [ Toy] where Neightf (X () is a neighborhood disentanglement function on graph-wide features X. Then ND in the k-th propagation step is ND Neigh ( (A* X). Second, since dynamic graphs ex- perience continuous temporal evolution, the variations of consecutive steps can imply fine-grained fluctuations that progressively approach targets. Therefore, for each t, we exploit the estimated tran- sition probability distribution on three categories predicted by Eq. [5 construct the step-wise tran- sition distribution matrix, i.e., (NDr)) = [P. Tp: FnJ" E RRNS As result, (NDr)f naturally encapsulates the target information. Then, can measure the consistency between the expected k-th order neighborhood and the target-oriented transition homophily probability by imposing a
RR-xx
Hadamard Product to (,D)); and (NDr)), Then MAX operation applied in each to pre- serve the maximal result and suppress the non-target-oriented noise. Besides, a smaller degree tends encourage aggregating nodes of farther horizons while larger propagation layer should be less weighted. Thus, the layer importance measurement of for node i, at layer & can be computed by,
of LiM((ND"),, (NDr).. d: MAX ((ND). @ (NDr).)
(11)
where dlt denotes the averaged degree of nodes in v. k-th order neighborhood.
d (AX((NDD), @ (NDT).)
(12)
k
Personalized high-order propagation block. The core technique of high-order layer propagation is learning a of interpretable node-specific soft weights for aggregating multi-order neighbors. To achieve such well nollanommal aggregation weights, we impose Softmax on the estimated layer importance of associated with an MLP parameterized by W Km to enable it learnable, i.e., of Wim
(LP(LMM((NDD))) (NDT).) Wim).. Given maximal propagation step K, we can obtain the soft weights over layer-wise aggregations &b E NX by sb Softmax "..,,..... - where th is the i-th in vb. So far, we can build our high-order propagation blocks. As target-heterophily compositions are less important during aggregations, we only consider the high-order propagation over target-homophily neighborhoods while imposing one-layer aggregation target-heterophily components. Then the K-th layer representation H (K) can be achieved by,
K
((R) á
Σ th D (1 a.)
(13)
There are two distinctions of our designs. First, instead of tuning parameters, we instantiate an & R as a learnable gate to reduce the fine-tuning burden, i.e., ã = (ML Wmip)) and adjust the compositions between target-homophily and target- hureet-hetrrophll... Wmip E R are learnable parameters. Second, rather than complicated routing mechanism, we exploit a learnable but interpretable matrix to reweight the importance of each layer specific to nodes, contributing to efficient high-order message passing. We plug our layer propagation into every temporal step.
5.3 TEMPORAL INCEPTION LAYER AND OPTIMIZATION
Temporal inception layer. To efficiently capture the temporal evolution, we adopt a fully- convolution based sandwich structure the temporal inception layer, which is inherited from STGCN (Yu et al. 2018). We can formulate the temporal inception layer as (K) F+, (F) (X))
(X)
and denote the final outputs as E Y. Details can be found in Appendix A.1.4
Training objective. The optimization objective of GReTo composes of two parts, the transition homophily estimation implemented by a cross-entropp--bsee multi-class classification, and the dy-
7

---

Published as a conference paper at ICLR 2023
Table I: Performance comparisons on various baselines.
Men-LAA
PcMis-Bay
KoowAir
Tongeranre
MAPE
RMSE
MAFE
RM45
MAPE
RMSE
MAFE
RMSE
019755
K.3098
16.5635
0.3221
GAT
0.628
5.8018
0.0176
1.6610
0.2435
13.3114
0.3393
1,4855
0.0665
5,7550
0.0167
1.6173
0.2449
13. 1931
0.1966
1,0233
SuperGAT
0.6223
5,7886
0.0175
1,6906
0.2535
13.3671
0.3224
1.3439
BGCvn
0.689
5,7554
0.1875
HoGCN
0.6088
5.7292
0.0168
1.6999
0.2371
1207
0.1906
0.9971
STGUN
0.0554
3,8655
0,0199
1,5850
0.2457
12 3681
0.1734
1,1190
GWN
0.0288
3.8434
0.160
MITGNN
0.0226
3,8133
0.0170
1.5759
0.2271
12,9091
0.1683
0.9034
DCRNN
0.0532
3,8798
0.0161
1.5222
0.2392
13 0399
0.1551
0.9715
ASTGNN
0.0530
5.5313
0,0189
1,6299
0.2485
13:2274
0.2975
0,9330
GReTo (Chrrs
0.0500
36652
0.1341
0.8784
namic graph regression based on MSE. The final objective can be written as,
Loss ( =
Σ
(p log - (1 -p)) - -p)))3 +
(14)
7e Epp 9p:2m
6 EXPERIMENT
6.1 IMPLEMENTATION DETAILS
Dataset description. We collect four cross-domain dynamic graph datasets. All of them possess the mixed property of homophily and heterophily. Traffic: (1) Metr-LA: Highway traffic status
consisting of 207 loop detectors of Los Angeles (Li et al. 2018). (2) PeMS-Bay: Traffic statuses
collected by California Transportation Agency, including 325 sensors in Bay Area (Li et al. 2018)) Climate: (3) KnowAir: PM2.5 Concentrations, covering 184 main cities in China (Wang et al.
2020 (4) Temperature: Urban Temperatures of the same 184 cities as KnowAir (Wang et al.
2020 We construct the graphs based on geographical distances where the node values and virtual
topology can be varied across temporal steps. The 8% is set as 5% across all datasets to control the proportion of node connections. Dataset details are elaborated in Table and andd?
Protocols. We evaluate GReTo on the dynamic graph regression tasks and compare it with state- of-the-art graph architectures. Training. We alternately train our model, i.e., train the transition ho- mophily predictor by freezing other weights while utilizing the well-learned transition homophily predictor to continue training the remaining architecture, where Adam SGD (Kingma 2014) is the optimization strategy. We initialize the learning rate of 1e-3 with weight decay 0.99. Evaluations. We employ classic GNNs, topology-refined GNNs, heterophily GNN and spatiotemporal net- works for comparisons, and adopt MAPE/RMSE to jointly evaluate the regression performances. Parameters, The homophily criteria are set as 0,08, 00 0.10 and 0. while the maximal propa- gation steps K are set 6, 6, 4 on MetrLA, PeMS-Bay, Know Air and Temperature, according to empirical evaluations. The size of TCN kernels is set to 1 3 on all datasets. For fairness, for each compared GNN, the number of hidden layers is set and the hidden dimension for each GCN is set to 64. For GAT, the number of heads is set to 8 according to the default setting in their papers.
GHNN
0.3
0.15
6.13
6.00
012
0.31
9.11
A.1
Areeaarg--Ma Mair MAPP
0.29
0.009
8MM
808
0.00
em0
007
0.00
606
811 06 01 15 L1 L6 LE 20
22
0.00
8.
LA 13 22
600g
Thuast exdiickul y MoaLA
Targe caciiiieel on Know
Pridiced harbae on MariAA
Phadiiia herbon en Pr3 (1) Prediction on MetrA A and PsMS with 12-leg selling
66) Predictionon MetelA and KnowAir diffenele
Figure 3: Detailed evaluations on different 7 and multi-step prediction.
Baseline. We compare solutions with respective four types of baselines. [1] Classic GNN mod- els: (1) GCN (Kipf & Welling 2016)) (2) GAT /Veliković et al. 2018). (3) GraphSAGE (Hamilton
et al. 2017 [2] Topology refined models: (4) SuperGiT (Kim & Oh 2020 (5) EGConv (Taloor
8

---

Published as a conference paper at ICLR 2023
et al.
2021). [3] Heterophily GNN: HgGCN (Zuu al.
2020 [4] Spatiotemporal graph learn-
ing: STGGN (Yu al.. 2018). (2) MTGNN (Wu et al.
2020b). (3) Graph (GWN) (Wu
et al.
2019). (4) DCRNN (Lietal. 2018). (5) ASTGNN (Guo et al. 2019).
Accuracy of transition homophily prediction. We present the Classification Accuracy between the estimated ones and groundtruth, i.e., 0.78/0. (.78//.60/0...8 86/0.68/ respectively four datasets (1)-(4). As observed, the higher intra-graph homophily tends to lead the higher prediction accuracy and we can also obtain a barely satisfactory result on PeMS and Temperature, which probably benefits from the data property of proximity and continuity. These promising accuracy can imply the feasibility of our transition homophily predictor and ensure the rationality of following implementations.
Performance comparison. Comparison results are figured in Table ! The best result is in bold and the second best is underlined. Our solution almost beats all SOTA baselines, achieving promising performances on four datasets with both 2 metrics. Promisingly. GRe'To improves MAPE by 24.79% and 3.61 % respectively on KnowAir and MetrLA, where KnowAir with high negative heterophily On benefits from flexible signed message passing instead of only aimilarity-based aggregation. In detail, classic GNNs fail to involve the transition-orrentted temporal information approaching real targets, reasonably resulting in large performance margins between theirs and our GRe'To, also infe- rior to other spatiotemporal networks. Generally, EGConv and H2GCN obtain better results and we can observe that the higher heterophily of the graphs is, the more superior performances of GReTo, EGGonv and H2GCN reveal. The underlying distinctions lie in the spatially-varying adaptive filters of EGConv and heterophily tolerance of H2GCN, supporting idea of target-homophily topology refinement in dynamic graphs. Extensive comparisons illustrate that our work advances the interpre- tation and designs of graph-based theory forward spatiotemporal learning and benefits learning on graphs that are with dynamic topology and heterophily compositions.
Ablation study. (1) Ablate the target-oriented neighborhood calibration, reducing to traditional GCN (V-TO). (2) Replace the high-order layer propagation with layer-wise weighted fusion, re- ducing to Mixhop (V-Mix). (3) Reduce the high- order layer propagation to uniform multi-layer fusion with the same weight (V-ULW). We report
Table 2: Performance comparisons (MAPE)
on ablative variants
Datasets
Men-LAA
PcMS-Ray
KnowAir
Tenpenture
0.0805
0,0450
0.2691
0
V-Lxs
0,0516
0.0176
0,1799
0.2523
VULLW
0,0519
0.0180
0.1800
0.2434
GROTO
0,0500
0.0166
0.1708
0.1341
MAPE four datasets in Table 2 Overall, promising results confirm the effectiveness of the two well-designed modules. In particular, target-oriented designs play sigmificant roles across all datasets with the improvement ranging from 37% to 61%, while the personalized high-order prop- agation reveals prominent improvements on Temperature. Regarding the fusion strategy, the layer- wise weighted fusion and uniform aggregation share similar performances while our node-specific personalized propagation shows a remarkable promotion. Noted that these ablation results also show that two modules are with diverse sensitivity datasets with different properties such as graph sizes or graph homophily, but our GRe'To is a general solution revealing promotions across four datasets.
Generalization on different y and multi-step prediction. We respectively select two datasets for a detailed study. First, we derive the statistical MAPE at different ry ranging from 0.5 to 2. Results are shown in Figure aa.. The performances reveal a 'V' shape with y increasing, indicating bet- ter results when y approaches 1 while inferior performances as it deviates away from 1. Similarly but promisingly, our solution exhibits lower errors and more robustness, which can be attributed to signed target-oriented message passing. Second, we present our multi-step performances against several representative baselines by modifying our framework to a 12-step forecasting with a se- quential output where results are in Figure (b). We observe that longer horizons enforce the target- oriented design to gradually lose ground as our GReTo does not tailor for multi-horizon settings. Even so, our solution still achieves comparable performances with best baselines, which verifies the generalization and potential of GRe'T in modeling longer horizons.
7 CONCLUSION
In this paper, we propose dynamic homophily theory by revisiting node-wise relationships from spatial-tempora perspectives and show the opportunity to renew aggregation capacity of conven- tional GNNs. Technically, novel GNN, i..,, GReTo is proposed, which integrates the signed target- oriented message passing and the layer importance based propagation, to refine the topology in both immediate and high-order neighborhoods. Empirical experiments have validated the superiority of

---

Published as a conference paper at ICLR 2023
GReTo four dynamic graphs. We will continue work on how homophily theory improves generalized dynamic graph learning, e.g., edge-type prediction and multi-step series predictions. Our code is available at http://gghhbb.ommm/e///222111111
10

---

Published as a conference paper at ICLR 2023
8 ACKNOWLEDGEMENT
This work is partially supported by the National Natural Science Foundation of China (No.6201) N2.62207247,, No. No.12227901) the Project of Stable Support for Youth Team in Basic Research Field, CAS (No. YSBR-005), Academic Leaders Cultivation Program, USTC.
REFERENCES
Sami Abu-El-Haile 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 international conference machine learn- ing. pp. 21-29. PMLR, 2019.
Lei Bai, Lina Yao, Can Li, Xianzhi Wang, and Can Wang. Adaptive graph convolutional recurrent network for traffic forecasting, NIPS, 33, 2020.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference Machine Learning, pp. 748- 758. PMLR, 2021.
Vidmantas Bentkus. On hoeffding's inequalities. The Annals of Probability, 32(2):1650-1673, 2004.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 35, pp. 3950-3957, 2021.
Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li. Jie Zhou, and Xu Sun. Hopology-imbalanty learning for semi-supervised node classification. Advances in Neural In- formation Processing Systems, 17298885228977 2021a.
Weiqi Chen, Ling Chen, Yu Xie, Wei Cao, Yusong Gao, and Xiaojic Feng. Multi-range attentive bicomponent graph convolutional network for traffic forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 3529-3536, 2020.
Yuzhou Chen, Ignacio Segovia, and Yulia R Gel. Z-genets: time zigzags at graph convolutional networks for time series forecasting. International Conference on Machine Learning, pp- 1684-1694, PMLR, 2021b.
Yuzhou Chen, Ignacio Segovia-Done Dominguez, Baris Coskumuzer, and Yulia Gel. Tamp s2genets:: pling time-aware multipersistence knowledge representation with spatio-supra graph convolu- tional networks for time-series forecasting. In International Conference on Learning Representa- tions, 2021c.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Songgaojun Deng, Huzefa Rangwala, and Yue Ning. Dynamic knowledge graph based multi-event forecasting. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1585-1595, 2020.
Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk- gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pp. 1550-1558, 2022.
Christina Göpfert, Yinlam Chow, Chih-wei Hsu, Ivan Vendrov, Tyler Lu, Deepak Ramachandran, and Craig Boutilier. Discovering personalized semantics for soft attributes in recommender sys- tems using concept activation vectors. Proceedings of the ACM Web Conference 2022, pp- 2411-2421, 2022.
11

---

Published as a conference paper at ICLR 2023
Shengnan Guo, Youfang Lin, Ning Feng, Chao Song, and Huaiyu Wan. Attention based spatial- temporal graph convolutional networks for traffic flow forecasting. In AAAI, volume 33, pp. 922-929, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. Rawlsgen: Towards rawlsian difference principle on graph convolutional network. In Proceedings of the ACM Web Conference 2022, pp. 1214-1225. 1225, 2022.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. In International Conference Learning Representations, 2020.
Kingma, D.P.; Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 160.002009 2016.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. International Conference on Learning Representations, 2018.
Weixuan Lin, Di Wu, and Benoit Boulet. Spatial-temporal residential short-term load forecasting via graph neural networks. IEEE Transactions on Smart Grid, 12(6):5373-5384, 2021.
Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph convolutional networks. In International conference on machine learning, pp. 4212-4221, PMLR, 2019.
Xiaojun Ma, Qin Chen, Yuanyi Ren, Guojie Song, and Liang Wang. Meta-weight graph neural network: Push the limits beyond global homophily. In Proceedings of the ACM Web Conference 2022, pp. 1270-1280, 2022.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural net- works? In International Conference Learning Representations, 2021.
Hao Miao, Jiaxing Shen, Jiannong Cao, Jiangnan Xia, and Senzhang Wang. Mba-stnet: Bayes- enhanced discriminative multi-task learning for flow prediction. IEEE Transactions on Knowl- edge and Data Engineering. 2022.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov, Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023. PMLR, 2016.
Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems, 33:12559-12571, 2020.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Gated graph recurrent neural networks. IEEE Transactions Signal Processing, 68:6303-6313 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pp. 593-607. Springer, 2018.
Zezhi Shao, Zhao Zhang, Wei Wei, Fei Wang, Yongjun Xu, Xin Cao, and Christian S Jensen. De- coupled dynamic spatial-temporal graph neural network for traffic forecasting. Proceedings of the VLDB Endowment, 15(1 (5(11):2733-277 2022.
Jacyun Song, Joonhyung Park, and Eunho Yang. Tam: Topology- aware margin loss for class- imbalanced node classification. In International Conference on Machine Learning, pp. 20369- 20383. PMLR, 2022.
12

---

Published as a conference paper at ICLR 2023
Shyam A Tailor, Felix Opolka, Pietro Lio, and Nicholas Donald Lane. Do need anisotropic graph neural networks? In International Conference on Learning Representations. 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Shuo Wang, Yanran Li, Jiang Zhang, Qingye Meng, Lingwei Meng, and Fei Gao. Pm2. 5-gnn: A domain knowledge enhanced graph neural network for pm2. 5 forecasting. In Proceedings of the 28th International Conference on Advances in Geographic Information Systems, pp. 163-166, 2020.
Yuling Wang, Hao Xu, Yanhua Yu, Mengdi Zhang, Zhenhao Li, Yuji Yang, and Wei Wu. Ensemble multi-relational graph neural networks. arXiv preprint arXiv:2205. 12076, 2022a.
Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learn- ing of representations via graph neural networks. Nature Machine Intelligence, 4(3):279-287, 2022b.
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts graphs: An invariance perspective. International Conference on Learning Representations, 2021.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. Advances in Neural Information Processing Systems, 33:20437-20448, 2020a.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chengqi Zhang. Graph wavenet for deep spatial-temporal graph modeling. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 1907-1913, 2019.
Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, Xiaojun Chang, and Chengqi Zhang. Connect- ing the dots: Multivariate time series forecasting with graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp- 753-763, 2020b.
Lianghao Xia, Chao Huang. Yong Xu, Jiashu Zhao, Dawei Yin, and Jimmy Huang. Hypergraph con- trastive collaborative filtering. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 70-79, 2022.
Teng Xiao, Zhengyu Chen, Donglin Wang, and Suhang Wang. Learning how to propagate messages in graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1894-1903, 2021.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. In International Conference on Learning Representations, 2018.
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 202::2/022006622. 2021.
Jiaxuan You, Tianyu Du, and Jure Leskovec. Roland: Graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2358-2366 2022.
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting. In Proceedings of the 27th International Joint Confer- ence on Artificial Intelligence, pp. (634-3640, 2018.
Chuxu Zhang. Dongjin Song. Chao Huang. Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery data mining, pp. 793-803, 2019.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Counterfactual graph learning for link prediction. arXiv preprint arXiv:2106.02172 2021.
13

---

Published as a conference paper at ICLR 2023
Zhengyang Zhou, Yang Wang. Xike Xie, Lianliang Chen, and Hengchang Liu. Riskoracle: A minute-level citywide traffic accident forecasting framework. In Proceedings of the AAAI Con- ference Artificial Intelligence, volume 34, pp. 1258-1266 2020.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7800 2020.
Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. On the relationship between heterophily and robustness of graph neural networks. arXiv preprint arXiv:2106.07767, 2021a.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 11 11168-11176, 2021b.
14

---

Published as a conference paper at ICLR 2023
A APPENDIX
A.1 MORE DETAILS ABOUT PROPOSED GRETO
A.1.1 MOTIVATION OF GRETO
In general, we discover that some topologically connected neighbors sometimes tend to dissimi- lar with targets and the aggregation of these target-deviated neighbors will introduce noise and harm the performance. In dynamic graphs, the node values will change over time thus the node- wise re- lationship, i.e., homophily intuition of this work is that not all neighbors are beneficial to aggregate for achieving targets, es- pecially in dynamic graph regression tasks, where designate such phenomenon topology-tar -tak discordance. Actually, only target-oriented neighbors are beneficial and encouraged to aggre- gated. Therefore, inspired by the homophily theory in static graphs, extend the graph homphily theory to dynamic graph scenarios and highlight the beneficial nodes based on fine-grained analysis of neighborhood compositions remedy the topology-task discordance. We further design layer- wise importance measures to propagate over high-order neighborhoods, generalizing the topology remediation to high-order message passing.
graphs, will also accordingly tend to be time-varying. To this end, the
A.1.2 FRAMEWORK OVERVIEW
We propose novel GNN architecture Remedy Topology via Target-oriented homophily (GReToo,, which simultancously performs adaptive immediate neighborhood aggregation and high-order layer propagation, from the perspective of target-oriented homophily disentanglement. Specifically, the proposed two homophily measurements respectively capture node-level intra-graph spatial proxim- ity and inter-graph connections between adjacent steps. Therefore, take advantage of both two homophily measurements to find target-oriented neighbors, thus calibrating the original topology. Since GNNs have two major processes, i.e., node-wise aggregations and layer-wise propagation, our GReTTo on topology-tase remediation correspondingly consists of two stages, Singed target- oriented message passing, and Personalized high-order layer propagation, illustrated Figure We also detailedly demonstrate the spatial and transition homophily well as the step-wise topol- ogy refinement in Figure 5
GReTo: Graph learning to Remedy Topology-task discordance
Local environments
(d,p. 9n)
S Spatial homophily
Transition hamophily
Multi-layer propagation
Temporal convolution
harpet-homophil aggregation
Temporal convolution
Target
Noighborhood disentanglement
Target-heterophly aggregation
Personalized high-order
igned target-orienttnn message passing
layer propagation
Figure Framework overview of GReTo on remedying topology-task discordance
A.1.3 TECHNICAL DETAILS OF TRANSITION HOMOPHILY PREDICTOR
Motivations. Although we have derived the formation of target-homophily neigh- borhood, the transition homophily from step T' to T'+1 cannot be available. How- ever, realizing a predictor to estimate the node-wise transition homophily tractable due to following two challenges. I) the unavailability of x T+I and 2) com- puting transition homophily between node pairs is computationally inefficient.
in-
15

---

Published as a conference paper at ICLR 2023
+1
Ty (xyy) )
Singed distance
3
E
between and
Temporal inception
Pair-wise signed aggregation kernel
Personalized
Homophily
Aggregaton
Positively
heterophily
Temporal
t
tH
Negatively
inception
Intra-graph spatial homophily
Inter-graph transition homophily
heterophily
Output
Schematic demonstration dynamic graph homophily
(b) Data flows step-wise dynamic graph learning in G ReTo
Figure 5: Homophily illustration and step-wise dynamic graph learning
To this end, we make one simplification and convert the homophily estimation into an efficient sequence classification task address above issues. First, we reduce the transition homophily to self-transition ho- mophily Sig Our Sig; (Tt)) --- 1-st measures the degree of node-level self variations between adjacent steps, which can be available from historical observations and encourages efficient computations. Second, to complement the unavailable 2f++ we find the serial inter-graph transition homophily obeys the favorable property of time-series, i.e., the periodicity and continuity. Therefore, we for- mulate time-series classification task.
STM
Stgl
Consolttion
Figure 6: Transition homophily predictor
Techniques. Concretely, the time-series learner concatenates two parallel LSTMs and one ID- convolution (Conv ID) to capture the evolution and trend dependence by taking all available his- torical observations of both node values and self-transition homophily [X,; Sig 1,2, 2,,, T) as inputs. Thus, we obtain the estimated next-step representation by,
SigR R
ConvID(LSTM(X,, X2,..., Xr); LSTM Sig².... ........ ))
(15)
We then exploit the learned time-series representation Sig T+1 where the class probability is estimated with an MLP parameterized by W. i.e.
for a three-category classification
D co. @n) ] MLP(SigR T+1 W..) The estimated p, Zop To refer to three probabilities that SigR T+1
(16)
belongs to corresponding cate-
gories, and then we can obtain the final Sig --++1 based on these probabilities.
A.1.4 TECHNICAL DETAILS ON TEMPORAL INCEPTION LAYER
Instead of highly computational recurrent learning Bai et al. 2020 Li et al. 2018), we adopt an efficient fully-convolution based sandwich structure for temporal inception, following the learning order of pampporrl-ppatial--empooo
(Yu et al., 22118). Specifically, the temporal convolution kernel implemented gate by taking self observations the feature inputs control the message passing. By involving both upper and bottom temporal blocks with our GReTT, the whole learning process can be written as,
= X
@x(X); (K)
(X)
(17)
16

---

Published as a conference paper at ICLR 2023
-TTxH = H(K) o (H((K))
(18)
Then the convolution is implemented by the element-wise Hadamard product @ between self- observation and the gate, and x is the length of convolution kemel for temporal aggregation fol- lowing the setting of (Yu et al. 2018 With this well-designed structure, our solution can not only sufficiently learn the temporal dependence, but also avoid the insufficiency of RNN-based methods.
A.2 RELATED WORK
In this section, we revisit series of related works on Graph Neural Networks (GNNs), homophily theory in GNNs as well as dynamic graph learning.
A.2.1 GRAPH NEURAL NETWORKS (GNNS)
Graph-structured data has received significant interest to energize substantial domains including molecular modeling (Rong et al. 2020; Beaini et al., 202I). social networks (Zhao et al.] [021] and smart grids (Lin et al., (021)) Early GNNs, which categorized to spectral methods, extend the convolution from grid data to irregular graph data by imposing Fourier transformations on graphs and extract informative structures (Defferrard et al., 2016, Xu al.] 2018). After that, researchers find that spectral GNNs suffer the issues of high computational costs and non-alignment to vertex domain. Therefore, spatial methods are proposed relax the equal number neighbors flexible neighborhood constructions by directly defining the kernel functions (Hamilton et al. 2017 Kipf & Welling 2016 Niepert al., 2016). To enable global node-wise correlation learning, attention methods of Graph Attention Networks (Veličković et al.) 2018) and ASTGNN (Guo et al. 2019) are subsequently proposed. However, graph-structune
data real scenarios are more complex than assumptions in most existing research. For example, multi-type edges and multi-type nodes in graphs are pervasive in many areas such as chemical bonds in molecules and heterogeneous relationships in social networks or citation networks (Wang et al. 2022a). Also, with the increasing layers of deep graph neural networks, node representations tend to go towards similar by iterative aggregations. To address these challenges. heterogencous GNN (Zhang et al. (019). adaptive relational graph learning (Wang et al., 2022a Schlichtkrull et al. 2018), and heterophily GNNs (Yan et al.) 2021 Ma et al., (221) have raised. Even so, adapting the GNN architecture more complex scenarios still remains as emerging research topic and less explored.
A.2.2 HOMOPHILY AND HETEROPHILY IN GNNS
The hemophily-hettrophiit theory aims to quantify local neighborhood distributions, i.e., the pro- portions of different types of neighbors that approaching and deviating from targets. Given the 'op- posites attract' phenomenon in real-world graphs, emerging GNNs are proposed to tackle the het- erophily issue. (Bo et al. 2021) first explain multi-type node-wise correlations with low and high frequency components and design frequency adaptation GCN to allow both high and low frequency message passing. After that, Yan et, al. propose signed message passing and degree-correction (Yan) al. 2021). to enable actively identifying different components graphs by extracting signs of node-level pair-wise similarity, and re- re-weighting layer-wise information by degree corrections. At the same time, Zhu et, al. design compatibility matrix to model the node heterophily (Zhu et al.) 2021b) and investigate three principles considering neighboring aggregation and high-order propa- gations, adapt heterophily scenarios (Zhu et al. (020). Actually, the homophily ratios of different substructures can experience large variances (Du et al. 2022). In this way, GPR-GNN (Chien et al.) 2020) and MixHop HAbu-El-Haija et al.] (209) enable learnable weights over different layers to achieve high-order propagation. Unfortunately, these high-order propagations cannot specify the weights over node-level, and all above solutions are tailored for classification.
A.2.3 LEARNING ON DYNAMIC GRAPHS
Majority of dynamic graph learning can be elassified into link prediction and node-level regressions.
Tasks of link predictions unversally exist in recommendation system (Xia et al. 2022] Göpfert et al., 2022), social networks YYou et al. (022) and heterogeneous academic networks (Kang et al. 2022)
where these studies exploit the dynamics of user preference and interests to achieve time-varying
"The size for temporal convolution kernels set across four datasets.
17

---

Published as a conference paper at ICLR 2023
Table 3: Dataset statistics
Node
Time
Time
Interval
Intra-graph homophily
Dataset
step #
span
length
03/01/2012-
Metr-LA
207
34,272
Smin
0.2273
06/30/2012
01/01/2017-
PeMS-Bay
325
52,116
5min
0.1073
05/31/2017
01/01/2015-
KnowAir
184
11,688
3h
0.2481
12/31/2018
01/01/2015-
Temperature
184
11,688
3h
0.1 0.1156
12/31/2018
Table 4: Neighborhood distributions on real-world datasets
Intra-graph homophily т..
Inter-graph homophily Te,
On
Pa
Metr-LA
0.2273
0.4732
0.2995
0.3325
0,4920
0.1755
PeMS-Bay
0.1073
0.5912
0.3015
0.2399
0.6863
0.0738
KnowAir 0,2481
0,3945
0.3574
0,3190
0,4030
0.2780
Temperature
0.1156
0.6980
0.1864
0.1418
0.5538
0.3044
embedding. This research line pays more attention to individual embedding rather than the holistic graph. Node-level regressions such as traffic forecasting YYu et al., 2018, Guo et al. 2019 Miao et al. (202) and smart grid predictions (Lin et al., 2021 Chen et al. (021b)), aim to aggregate rel- evant nodes for approaching future observations. To capture the dynamic topology, recent works devise various adaptive topology learning strategies, including dynamic similarity (Yan et al. 2021 Zhou al. 2020; Bai al. 2020) and attention mechanism (Guo al. 2019), quantity weights of different nodes. Actually, dynamic graph learning tends to be more challenging than static graphs, as these node values are often time-varying and naturally induce the edge diversity over time (Chen ee al. 2020, Yan et al. 2021). In addition, the imbalanced local structures over nodes (Chen et al.) 2021a Wu al., (022) further pose challenges high-order propagation and topology refinement. Although there are studies respectively focus dynamic relation embedding (Deng et al.) 2020), and personalized receptive field construction (Xiao et al.) 2021), there are two issues have been significantly neglected. 1) None of them take the temporal evolution into account to capture their influences on their potential dynamic topology and 2) Considering the potential topology task dis- cordance discussed above, none of them investigate the node-level multi-relations over graphs to facilitate regression tasks.
A.3 ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
A.3.1 STATISTICS OF DATASETS
As this work studies the node-wise proximity over dynamic graphs and investigates how the prox- imity of both homophily and heterophily enhances dynamic graph regressions. We thus present the statistics of node numbers, total temporal steps and intra-graph homophily of each real-world dy- namic graph in Table 3 Also, the numerical neighborhood distributions of each node are averaged into Ps. 9p and q,, regarding both two types of homophily, i.c.. intra- and inter-graph homophily in Table 4 Noted that the reported numerical homophily is derived with the well-set homophily crite- ria E, Le., 0.08, 0.1, 0.1 and 0.12 corresponding to four dynamic graph datasets. Due to the inheret dynamics in these graphs, we can observe that these graphs suffer serious heterophily issue and the inter-graph homophily tends to be higher than that of intra-graph. We especially observe that datasets of KnowAir and Temperature are with higher negative heterophily q.. and experimental results in Table I also demonstrate more significant improvement KnowAir and Temperature. These statistics can verify the intuition that modeling homophily and heterophily can disentangle the target-oriented homophily and boost both aggregation and representation capacity in GNNs.
18

---

Published as a conference paper at ICLR 2023
A.3.2 DETAILS OF COMPARED BASELINE MODELS
Classic GNNs: (1) GCN: The classical graph convolution neural network Kipff Welling 2016). (2) GAT: An attention-baset graph method capturing global dependence on the whole graph (Veličković et al.) 2018). (3) GraphSAGE: A representative spatial method of GNNs to re- alize graph-based inductive learning (Hamilton al., 2017). Topology-refined models: (4) Su- perGAT: A self-supervised GAT designed for noisy graphs, which learns expressive attention in distinguishing mislinked neighbors (Kim & Ohl 22220) (5) EGConv: It is lightweight GCN that designs spatially-varying adaptive filters (Tallrr et al. 2021). Heterophily GNN: (6) HCGCN; It is a framework for node-level classification on graph with homophily and heterophily components by three effective designs (Zhu et al. 2020). Spatiotemporal Networks: (1) STGCN: A graph-based spatiotemporal framework with sandwich structure of temporal-spatial -patial--paaaallattpra learning archi- tecture (Yu et al. 2018)) (2) MTGNN: Multivariate time-series forecasting model which is capable of adaptively learning uni-directed relations among variables with a graph learning module (Wu et al. 2020b). (3) Graph (GWN): A state-of-the-art graph-based traffic prediction model that integrates TCNs and GCNs (Wu et al. 2019). (4) DCRNN: A diffusion convolutional recur- rent neural network, which combines diffusiin graph convolutions with RNNs (Li et al. 2018). (5)
ASTGNN: An attention- spatiotemporal network for capturing dynamic ST correlations (Guo
al. 2019
Error metric: MAPE
MetrLA (Right Y-Axis) WIZH
KnowAir (Right Y-Axis)
0.0510
0.051
0.176
0.8505
0.185
8.048
0.185
8,050
0,3500
0.180
BJ06
0.180
0.049
U.172
0.044
0.175
0,048
0.05
1,08
0.170
0.0490
0.170
Edge connection Fatio
Homophily criteria
propagation stepe
PeMS (RightY-AxE
/// Temperature (Right Y-Axis)
0.0170
BJ017
0.145
B.0EG5
0.145
0.141
RUE7
0.169
0.0160
0.140
0.139
0.016
0.0155
8J155
0,83
0.64
0.05
8.06
0.07
0.138
0.02
0.45
0.88
8.1
0.12
0.130
0.0150
Edge connection ratio
Homophily criteria
Maximal propagation steps
Figure 7: Parameter sensitivity analysis
A.3.3 ADDITIONAL DETAILED COMPARISON RESULTS
In this subsection, we perform series of experiments to test the model performance stability with different initializations, model robustness on temporal resolutions and the high temporal node de- grees.
Stability comparisons of different models. To explore the performance stability of different mod- els, we train our models with different initialization random seeds, and select three matching baselines, MTGNN, GraphWaveNet (GWN) and DCRNN as the compared baselines. We record the standard deviation of RMSE and MAPE for these models on four datasets and report them in Ta- ble 5 Among the four models, our GReToo reveals comparable and identical stability almost all datasets with other baselines, verifying there is no stability issues in our solution.
Robustness temporal resolutions. Our solution is independent the length of time intervals as the evolution trend should be captured regardless of the interval length. To confirm this intuition, perform case experiment by aggregating the time intervals from 5 min into 30 min Metrl.
19

---

Published as a conference paper at ICLR 2023
Table 5: Performances with standard deviations
63
PaMiS-Ba (5-min)
KnowAir
Tempeniiu
MAPE
RMSE
MAPE
RMSE
MAPE
RMSE
MAPE
RMSB
MIGNNN
38155500168
0.759100:010
0.6622000051
GWN
08434 0000
0,01630000002
1.348240 0087
228810.000 0027
12.8495100123
06077
099112000097
DERNN
3.8792200119 0,032200006
0.0161:0.0003
1622940.002
0224220000244
13.0899000317
0.1251200057
0,9715500003
GReTo
0A50080.004
3,652200356
0,016240,0006
1.981360,025
0.170840.0025
11,03999.0670
0.13410.003
0.5704:0.0031
Table 6: Performances on aggregated 30-min intervals of two datasets
Metr-LA (30-min)
PcMS Bay (30-min)
Models
MAPE
RMSE
MAPE
RMSE
MTGNN
0.0950#0.0011
40.6671#0.622/
0.028740.0002
18.076740.0785
GWN
0.0952+0.0002
40.7782+0.51300
0.0281
17.717740.0832
DCRNN
0.0989=000010
41.5420=:0.5994
0.0292+0.0000
17.8241#0.0861
GReTo
0.09362000004
39.201440.3306
0.0273+0.0002
17.5980=0.0619
and PeMS-Bay. The results illustrated in Table 6 show that our solution can also have 1.6% and 2.8% improvement on these two well-studied datasets when compared with best baseline, where the performance gains are comparable 5-min setting. Thus, we exactly demonstrate the independence of our solution on temporal resolutions. Noted that the greater magnitude of errors and larger vari- ations of 30-min datasets is probably attributed to the larger magnitude of node observation values on aggregated datasets.
Robustness on graphs with higher temporal node degrees. The graphs with higher temporal node degrees are corresponding to the scenarios that nodes in adjacent/different graphs possess more inter- connections, i.e., graphs with higher inter-graph homophily. As illustrated Table 4 this scenario occurs two datasets, Metr-LA and KnowAir, as both datasets reveal higher inter-graph homophily ie., larger ps (0.3325 on Metr-LA and 0.3190 on Kir. On their performances, the reduced errors away from best baselines both datasets, from 0.0526 0.0507 Metr-LA and from 0.2271 to 0. 708 on KnowAir, can imply the robustness of our GRe'To on higher temporal degree nodes.
A.3.4 INTERPRETABLE INTERMEDIATE RESULTS
To present an intuitive understanding on aggregation process of our GReTo, Figure demonstrates study of our GReTo Metr-LA. Some important central nodes associated with their neigh- borhoods and the intermediate results of layer-wise importance are visualized. It is observed that nodes in graph usually reveal distributed centers and different centers also tend to be connected. For layer-wise importance, it shows that nodes with lower degrees (e.g., Node 7 and 107) tend to propagate farther than nodes with higher degrees (e-g.. Node 28 and 78) where the learnable results can verify the intuition of our layer propagation principle and the effectiveness of our GReTTo for high-order propagations.
A.3.5 PARAMETER SENSITIVITY ANALYSIS
We investigate the three hyperparameters in GReTo to test the model parameter sensitivity. We illus- trate the optimal parameter searching process on all four datasets in Figure We have the following three observations. First, we must strike a balance on the edge connections between the lower graph connectivity and reduced graph topology, corresponding to lower and higher connectivity 8 and s. Second, it can observed that the larger-scale of graphs tend to require a larger propagation order K, indicating more neurons can accommodate better fitting capacity towards to adapt more intensive data. Third, although different graphs have their intrinsic property and corrspond to their optimal pa- rameters, we can still find our solution can be stable across different parameters and discover some regularity parameter tuning.
20

---

Published as a conference paper at ICLR 2023
0.6
0.5
0.3
0.2
1st
2nd
3rd
Layers
Hierarchical node distributions
importance over Sverr-oordee propagations
Figure 8: Case study of GRe'To on Metr-LA
Table 7: Model training time for each epoch (unit: seconds)
Datasets
Metr-LA
PeMS-Bay
KnowAir
Temperature
GreTo
58
122
16
16
GCN
35
87
11
11
A.3.6 COMPLEXITY ANALYSIS
Complexity GReTo. model complexity plays an important role in both training and inference stages, we here analyze the additional computation existing GNNs of our GReTo. For one step t E [T]. the major computation costs lie two aspects, (1) in the data-preparation stage, spatial homophily and transition homophily should be pre-caleulated, which leads to O(N N), (2) in the training and inference stages, real-time spatial homophily computation, a binary judgement for ma- trix sign disentanglement additional K K-times computation for high-order neighborhood distribution as well as matrix product, finally the MLP for LiM, which lead to O K + + O(2K + 2) times atomic operation (element-wise matrix product addition). Since the aata-preparation stage does not occupy training resources and can be computed only once while the computation during training and inference is linearly increasing with maximal layer number K, the additional compu- tation is tolerable for the whole architecture. Besides, we also investigate the training complexity and parameter volumes of the proposed model empirically. The comparison of model training time compared with vanilla GCN is illustrated in Table 7 while the parameter volume comparisons with other comparable dynamic graph learning models are shown Table S where both of them can support the acceptable computations.
Complexity of GReTo on large-scale graphs. More specifically, readers may concern about the efficiency issue when the graphs become larger. Here present the efficiency analysis over very large graphs. In this case, we can force the spatial proximity only to be computed on spatially neighboring nodes. Assuming there averagely N, neighbors of each node (N, N), the total computation on large graph is N N,. By adding the computations of temporal evolution, the whole graph homophily calculation only requires totally N (N, + times of computation that is linearly increasing with node numbers, while LIM in the neural network still needs (2K + 1) computation. Further, we can also construct the matrix describing the ego-net neighbors allow the
Table 8: Parameter volumes on different models (unit: million (M))
Models
GReToo
MTGNN
GWN
DCRNN
Metr-LA
0.38M
0.41M
0.28M
0.37M
PeMS-Bay
0.38M
0.57M
0.37M
0.28M
21

---

Published as a conference paper at ICLR 2023
computation to rum parallelly. Therefore, with these slight modifications, our solution can be easily generalized to large-scale graphs.
A.3.7 FURTHER DISCUSSIONS ON EMPIRICAL RESULTS
Influences of dataset property on module performances. The ablation studies have illustrated how the model performances vary when each component individually removed. We find that the improvements induced by designed modules are sensitive to the property of datasets. Since tradi- tional GNNs only aggregate homophily compositions in the current graph for smoothness while our larget-oriented message passing explicitly considers the target influences topology to perform ag- gregations, the datasets with higher intra-graph heterophily (large In of antra-graph) or inter graph heterophily (large qn of inter-graph) are more prone to receive more benefits. In fact, more significant performance improvements on KiowAir and Temperature can correspondingly verify our intuition. Therefore, when the property of datasets varies, the performances will change accordingly. Besides, the interactions between two modules may bring in additional bonus where the topology remedi- ation can work cooperatively with the personalized high-order propagation. Concretely, the topol- ogy remediation will be meaningless in the high-order neighborhood aggregations if the layer-wise importance measure module is removed, and the ablations on V-ULW (aggregation with uniform layer-wise weight rather than personalized aggregations) exactly confirm this argument.
Model scalability on different scenarios. The theoretical analysis and experimental results can ver- ify that our solution is easily generalized to different scenarios. Here, we will analyze the scalability issue on three aspects, i.e., temporal resolution, homophily property and large-scale graph adapta- tion. First, we argue that our solution is actually independent on the length of time intervals as it only requires to calculate the current graph homophily and captures the potential evolution trend in data-driven manner. The additional empirical results (Sec. A.3.2) reveal similar improvements on both 5-min and 30-min intervals also demonstrate the independence on the interval length. And for multi-step prediction, as shown in Figure (b), the 6-step prediction results are comparable to other baselines that tailored for multi-step time series predictions (i.e., MTGNN) but with a smaller improvement margin than single step prediction does. This can inspire us explore an extended version of GReTo-M that is tailored for multi-step prediction. A new GReTo-M can concentrate on how to guide the learning of trends by considering the homophily, context-factors to generalize to a high-quality multi-step prediction. These interesting works will be left as our future work. Therefore, our solution is generally robust to different temporal resolutions. Second, for homophily property, we have illustrated the statistics of neighborhood distribution in Table We find that datasets with different inter-graph homophily and intra-graph homophily exactly reveal various prediction perfor- mances. Specifically, our solution explicitly considers the target evolution direction to capture the turget-homophily nodes that can potentially involve both heterophily and homophily in one graph. Therefore, our solution can adapt to the high intra- hntra-heterophily scenarios such Temperature, and high inter-graph heterophily scenario such as Know Actually, the performances on these two datasets have large margin than baselines that validates our intuitions. Finally, our GRe'To can also be easily generalized to large-scale graphs as we are only required to calculate the intra-graph homophily within spatial neighborhoods and inter-graph homophily within node itself. The sim- plified operations will lead to a linearly increasing computation with node number N that can be satisfactory for model deployment (demonstrated in Sec. AA.3.6). To conclude, our newly developed GReTo model is with good scalability on various scenarios probably with slight modifications, and we believe our work can be an advance in both spatiotemporal learning and graph learning theory.
B PROOF OF THEOREMS
B. PROOF OF THEOREM II
Proof. To prove Theorem we first provide several notations on graph G and node e; to facilitate the
analysis. (1) d, serves as the degree of node v while the feature value x; is bounded by B, (2) p( (W) denotes the largest singular value in learnable parameters W, (3) the ratio of intra-graph spatial homophily mi is fixed to p;. while the ratio of other node-level relations is qi where qi = 1 1- Pi.
(4) assume target coefficient to quantifies the relationship between the targeted step T + 1 and current step i. by x! T+1
yart We omit the non-linear activation layer for simplification, it will
22

---

Published as a conference paper at ICLR 2023
not intervene this theoretical analysis. Based on above assumptions, introduce the following Lemma to demonstrate the representation h2 will finally converge to its expectation.
Lemma 1 Acorrding to Hoeffding's Inequality (Bentkus 2004), the aggregated representation h; will converge to its expectation Elh,] with their differences bounded by,
d
P(Ih;; - Elhlll2 2 t) S e1exp( (p)
(19)
Lemma I has been exactly proved in literature (Ma ct al. 2021 classification tasks. Considering GNNs share the same process neighborhood aggregation and node representation updates on both classification and regression tasks, Lemma 1 can be extended regression tasks.
After then, we can derive the expectation Æ of hy to complete following analysis. For simplifica- tion, we only consider the evolution from the one step T to the targeted step 7 i.e., x!. - - - where we assume x! " If only the nodes of intra-graph homophily can be aggregated, each aggregated neighbor b/ E (wx)) satisfies 2, (1 + E)x; Let 2, (1 + E)x,, where satisfy E g < 1. Therefore, can calculate the expectation E[h after once convolution, i.c..
I; + d.p; (1 + 2)
E
(20)
d: 1
where dep; interprets the expectation number of the spatial homophily nodes in the whole graph.
Given the target coefficient %r a successful aggregation can be equivalent to finding a valid d; to construct appropriate neighborhood field for achieving targets. Therefore, we continue to derive the relationship between di, and p;.
The difference between E and the targeted value x; T+1 = -.., can be written as,
[Thh] x +|=++===1/- 1 d,pa( + ē) (d +1 xall
(21)
d, +
Consider that the differences will converge to 0 as the optimized points are obtained, we can derive the closed solution of d;,
1 - Pi
d, P: 3)
-1 +
Pr 76
71
Pi
7/3 P
By analyzing the above inverse proportional function in Figure 9 achieve the conditional relationship among the substructure d, the target coefficient 7 and intra-graph homophily Pi.
4.
-000-1), 7/2 < P: 00, 7 = Pi
d;
10. +00), P: < 1
(v.00)
(-1,0), 74 >
Based on above analysis, we have theoretically demonstrated that cannot obtain the optimized d, when < and > 1, corresponding to the discor- dance between topology and tasks.
Figure 9: Relationship between the target coefficient 7/ and substructure degree dç-
B.2 PROOF THEOREM 2
Proof. To faciliate the analysis on more complex mes- sage passing, we introduce the following notations and settings. Given node t. the spatial homophily still keeps as p; while heterophily ratio keeps as q., d,q, is the expectation number of heterophily neighbors to v; and a adjusts the aggregation proportions between homophily and heterophily.
23

---

Published as a conference paper at ICLR 2023
We consider the expectation values of positive and negative heterophily neighbors respectively as Et. and Azæ; where (A1. A2) satisfying < A1 X2 < 1 are the scalar factors. By formulating a Ar
seperated aggregation strategy, we can derive the difference between the expectation of current- graph representation and target as,
11=11 Di + d.p:( E) + d:gi x, Sp + (1 - a 228
|
d; +
(22)
Y:.r (d: + +1)
|1
dj +1
with
d: E
<< <1
0 7 <1
Let the difference be 0, we have the following equation,
+ d.p.(1 + deg. x - - -1)) + 1) = 0
(23)
Ignoring the relatively small e, we can arrive the optimzed closed form of d;
%
d
Pt + 2o A1 (1 c2)22) 7
To find an optimized d, E N the parameter tuple (pi, 9s a. No, A2, A2) must conform to the fol-
lowing inequality by simplifying 8p 1, 8q = 1,
0 < p: t -11 aa)))) - <
(24)
Without loss of generality, we denote T" can simplify Equation into,
a - (1 - aa) and substitute qi with 1 - -pi then we Xs
N P. (1 p:)T" 2% -
(25)
Then we can derive the condition that 7" must satisfy as,
Y P P
2% Ps
(26)
ps
Since the node-wise aggregation process are parameterized by both signed kernels and learnable pa- rameters, it can be viewed encapsulating learnable W into our pre-defined parameters (A1, A2 a) and hence we can always find the optimal T" to satisfy above inequality. We will further present detailed analysis of above inequality for verifying the existence of such solution.
Let -==t- x we have,
24 Pi
2%/ Ps
(27)
p:
1- Pb
Then we can resolve the inequality and derive the exact t by,
P4
+
27 2mc-(p=+1) I-P:
27-- )z
+
<t<
1-p:
(28)
Ultimately, set of possible solution (A1, to the directional message passing should satisfy the following inequality.
2 T-m:
+
24 (pctt) + ( 2 +
a
1 P.
(29)
a2
2
Given that A₁ and A respectively imply the neighborhood of intra-graph positively heterophily and negative heterophily, in the following section, will continue to analyze what conditions will satisfy when 7 tends to approach respectively or +oo. This will provide insights into the evaluations of predictability and GNN success the given datasets.
24

---

Published as a conference paper at ICLR 2023
1) when 3/- + 0, we have,
7-1
lim dç = 7- pi + 9i( - (1 ax)2))22)))))) (042)-1
(30)
To ensure the valid d, with 1 s d, I +00, we derive,
2 - < p. + qil a \1
(1 (1- (1-a))2) <7
(31)
We can obtain the constraints of X2.
A1 + pi -
(32)
A1 a)
(1-a)q
Thus, for 7. + O, the successful aggregation can be achieved when compositions of negatively het- erophily neighbors dominate the neighborhoods, i.e., we have a large \ but small X2 satisfying Eq. 31
2) when 7/- + +o0, we have,
Y --1
7. lim di
(33)
Pt + 26 - -a))2) - %
To ensure the S d; $ +00, we derive,
0 S p: + qel A1
- -1 a)- - 7/ S
(34)
As the assumption of 7/2 + too but 0 < a, d2, q < 1, we can directly neglect the components of both p. and (1 - A2g; We then have,
2% 2 λ1 & 71 Pp +1
(35)
(T-a)A1
Thus, for 7 + +00, the successful aggregation can be achieved when compositions of positively heterophily neighbors dominate the neighborhoods, i.e., we have a small λ₁ but large X2 satisfying Eq. 34
Therefore, we conclude that extending the aggregation to signed message passing with separately aggregating different types of neighborhoods can exactly enhance the aggregation capacity.
Remark. In Theorem we demonstrate the required conditions of expected neighbors that poten- tially lead to successful aggregations under signed message passing. With these derived conditions, we can roughly estimate whether the GNN can success or not to aggregate the neighborhoods for achieving targets if the dataset is given. Based on Theorem 2 we can remedy the task-topology discordance by disentangling the neighborhood relationships and performing signed bi-directional message passing.
B.3 PROOF OF THEOREM 3
Intuitive demonstration. As illustrated in Figure 10 we can observe that non-identical neighbor- hood environments can directly result in different optimized aggregation steps (orders) each neighboring direction. In other words, the neighborhood topology and the target-heterophily nodes determine the stopping step of aggregation along each route. We demonstrate the detailed proof regarding their quantitative relationship as below.
Proof. Due to the mixed compositions of intra-graph homophily and heterophily in one graph, there must be target-heterophily edges. Intuitively, the target-oriented neighboring nodes, i.e., target- homophily are more beneficial to the aggregation process leading to targets. With the notations and basic setting in Theorem 3 we can analyze the expected number of total target-homophily neighbors. To simplify the proof, we leverage local dependence assumption in Graph Information Bottleneck (GIB) theory (Wu al. 2020a) in analysis, which assumes nodes in same k-order EgoNet share the same neighborhood distributions and environments. Also, herein we only consider a two- layer propagation (k=2) and let the two-order neighborhood share the same local neighborhood
25

---

Published as a conference paper at ICLR 2023
environments (di, P. 1p:99.9hh qn) specified by a central node (we will not impose the node index sub- script to (p, 9p: 9n) as we make the local dependence assumption in the local fields).
We first consider the scenairo of a large % in a consecutive transition x- na. > x (%+ > 1), and there are two cases that nodes are beneficial aggregate. The beneficial nodes are distributed hierarchically and carefully depicted in Figure a), i.e. (1) in the first-order propagation, the pos- itively intra-graple heterophily neighbors central node (circle colored in green). (2) the second- order propagation, the positively intra-graph heterophily compositions neighboring to first-order homophily neighbors (left ellipse colored in blue), and the intra-graph homophily and positive het- erophily compositions neighboring to first-order neighbors that are positively heterophily composi- tions to v; (right ellipse colored in blue). Let N++)) be the expected number of target-homophily neighbors of es can derive the following equation,
N4 (14) = qpd; + pap + (pqp + oz)d{
(36)
dz tp + d;)
Denoting the expected feature values of first-order target-oriented neighborhood as Tol and fea- ture observations of the second-order neighborhood as Toz, the expected aggregation observations normalized by the degree d, can be derived as,
1 E| = di
ppdz x vol + (2M, + d2)
(37)
= Fo + (2pqp + (f))
Therefore, we consider the information aggregated from target-oriented nodes as the probability that beneficial nodes are exactly selected for aggregation. In this way, the difference of such probability between the second layer and the first layer AP(N+))1- is computed by.
AP(N)) P(N+) P(N4),
2pqp 99 9p
(38)
= =2(1 - 9g On 1p + 1p Up
--11 1-2n)) + 4p
We consider the quadratic function of qp. where the function describes the compositions of target- homophily.
1) If0 < %- < 14 we have AP > O. It refers to that when it is with small target- hoophhlymmpphll,, the second-layer can gain more information than the first- layer does, i.e., we have (12) > INFO Similar conclusion can be extended to (NFO (NFO(h)) for 3-rd and 4-th layer propagation, and further higher-order propagations if they share simi- lar neighborhood environments. This numerical result can support the intuitive understanding that the smaller target-homophily is, the larger layer propagation steps are required to gain more informative target-related messages.
B
16
Propegation Á
Propagation B
T+1
16
2) If 9p > 1+20 we have AP(N+) < O. This inter- prets that a large target hngehlly can encourage the first-layer gain more information than the second one, i.e., we have INFO(h)) > (NF) and sim- ilarly (1))
Figure 10: Illustration of node-specific per- sonalized receptive field
INP)(h!) achieves. An intuitive understanding can be achieved that the larger target-homophily, the fewer propagation steps demanded to balance the propagation efficiency and information gains.
For the scenario of small y, the negatively intra-graph heterophily compositions are encouraged to aggregate, as illustrated Figure [T Now the proportion of target-orienter composition becomes qn in the first-order propagation. Let N_ (xx) be the expected number of target-homophily neighbors of v;, we have,
N_ (vz) qud + of + (g gn)d)
(39)
26

---

Published as a conference paper at ICLR 2023
Similar to above analysis, the probability difference of aggregating the nodes that are target-orienter autra-graph negatively heterophily) between the second and first layers can be derived as,
PP(N-))1-2 (-1 22n) + On
(40)
Eq. 39 is highly analogous to Eq. 37
hence the symmetric results be achieved when have
small satisfying <
Orders
Central Node
Central Node P1
neighborhoods
Homo
letero
Hatero+
Hetero-
Ist-order
Ap
Un
9p
2nd-order
4p
4n
P
4p
4n
4p
4n
4p
4n
9p
N. (v:) 9p d + pap d² + (qp d (p 9p)d)
(-(P2) = 9n d pda df (9n d (p + 9n Rd)
(a) large
(b) is small
Figure 11: Example of target-homophil node selection process. The highlighted circles in green represent the target-oriented neighborhood in first propagation order while the circles in blue indicate the target-oriented neighborhood in the second order. Homo, Hetero+ and Hetero- respectively refer to target-homophily, postively target-heterophily and negatively target-heterophily.
We can finally complete the proof of the quantitative relationship between the informativeness of layer-wise node representation and the target-oriented homophily ratio.
B.4 BROADER IMPACTS AND ETHICS ISSUE
Scalability and broader impacts. general, this paper proposes a novel GNN architecture, GReTT, for dynamic graph regressions via remedying the topology -takk discordance. Our work provides a new perspective that exploits both original topology and targets to investigate topology refine- ment and reconstruction, i.e., the topology in structured data must be informative knowledge for message passing while the aggregations may not involve all connected nodes but only the target- beneficial neighborhoods. This research delves into how fine-grained analysis of neighborhood com- positions facilitates dynamic graph regressions and can promisingly inspire better modeling and analysis on various graph-structured data with complex explicit or implicit correlations. In detail, it not only can be good baseline for multivariate series prediction such as smart grid prediction, numerical weather forecasting, and economic growths, but can also be generalized to resolve var- ious classification tasks on dynamic graphs including link predictions in social networks, citation networks, and recommendation systems.
Limitations and future works. The limitation of work can be summarized as 1) limited di- rection expressivity for multi-step predictions, 2) lacking individual-level node analysis and inter- pretability on controllable message passing, i.e., dissecting how each composition of neighborhood affect the representation, deviating or approaching targets? Therefore, for future works, we are go- ing comprehensively study 1) how exploit homophily theory improve more general dynamic graph learning tasks such as link predictions or edge-type predictions, 2) how the node-level rela- tions and neighborhood compositions affect the node representations, which potentially can control the message passing in robust and anti-noise manner.
Fairness and ethic issues. Our work performs extensive analysis and experiments on datasets in- cluding traffics on two cities and climate datasets concerning air quality and temperature, without any personal identity and privacy issues. Therefore, our work with no ethics and privacy issues. In addition, all baselines and methods are compared with fairness.
27


Reviews:
[{"review_id": "hvS8pWtUWCz", "reviewer": "Reviewer_mrA2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "", "summary_of_the_paper": "This work studies regression task on dynamic graph. It points out that some edges could be harmful when using GNN for the target task, which the authors called topology-task discordance. To address this, the authors extend the notion of homophily to dynamic graph and design GReTo, which adaptively perform selective message passing on dynamic graph. The extensive experiments showed the effectiveness of the proposed GReTo, which outperforms baselines by a large margin.", "summary_of_the_review": "I think this is a technically solid, modest-to-high impact paper in a subarea of graph machine learning, so I tend to accept.", "strength_and_weaknesses": "Strength: 1. The motivation of this paper is good. Topology-task discordance issue does exist in dynamic graph yet has been overlooked. 2. The derived theory and proposed method are sound. 3. Experiments are coherent with the motivation, which clearly demonstrates the effectiveness of the proposed method.\n\nWeakness: This paper is a little bit hard to follow due to a lot of concepts and the complexity of the method. I think the authors could motivate each of the proposed module a little before detailed description. To be specific, it would be better to add summary at the beginning of subsection 5.1 and 5.2.\n\nMinor comments:\n\nThe authors should carefully check their citing format- \\citet{} and \\citep{} are different and should be used accordingly.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ckhypQbez93", "reviewer": "Reviewer_dBq6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "Aiming at the problems of the aggregations of target deviated neighbors on dynamic graphs (the authors call it topology-task discordance), this paper revisits node-wise relationships based on a dynamic homophily theory from the spatial-temporal perspectives, and proposes a model GReTo consisting of two stages, signed target-oriented message passing and personalized high-order layer propagation, corresponding to the two major processes of GNN.", "summary_of_the_review": "Please refer to the weaknesses and questions for the details. I look forward to your answers to the above questions.", "strength_and_weaknesses": "Strength:\n1. This paper is well-written and easy to follow, and the motivation is clear.\n2. This paper proposes a dynamic graph homophily theory from the spatial-temporal perspective.\n\nWeakness:\n1. In the community, there are many GNN-based models for dynamic graphs, but in the Related Work part of this paper, the authors lack some representative methods (e.g., TAMP-S2GCNets[1], D2STGNN[2]). They should clearly discuss the differences between those models.\n2. There lack of efficiency analysis in the experimental part.\n3. The proposed model GReTo can only make one-step predictions while multi-step predictions are widely used in the community.\n\n[1] TAMP-S2GCNets: \nYuzhou Chen, Ignacio Segovia-Dominguez, Baris Coskunuzer, Yulia R. Gel: TAMP-S2GCNets: Coupling Time-Aware Multipersistence Knowledge Representation with Spatio-Supra Graph Convolutional Networks for Time-Series Forecasting. ICLR 2022\n[2] D2STGNN：\nZezhi Shao, Zhao Zhang, Wei Wei, Fei Wang, Yongjun Xu, Xin Cao, Christian S. Jensen: Decoupled Dynamic Spatial-Temporal Graph Neural Network for Traffic Forecasting. Proc. VLDB Endow. 15(11): 2733-2746 (2022)\n[3] AGCRN:\nLei Bai, Lina Yao, Can Li, Xianzhi Wang, Can Wang: Adaptive Graph Convolutional Recurrent Network for Traffic Forecasting. NeurIPS 2020", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Qca7pLfW7eT", "reviewer": "Reviewer_XKsq", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper introduces a dynamic graph neural network model that handles the dynamics in graph homophily wrt specific prediction tasks. Specific modules are designed to model the topology-task discordance along time with theoretical analysis. Experiments are done on real-world traffic and climate datasets.", "summary_of_the_review": "In general a good paper with a novel angle, solid technical developments, and promising results. Some rearrangements between the main content and appendix may help the presentation.", "strength_and_weaknesses": "S1: Novel angle of task-topology discordance for modeling dynamic networks.\nS2: Organized presentations with rich theoretical analysis for the proposed techniques.\nS3: Promising experimental results on real-world datasets of dynamic networks.\n\nW1: A good motivating example of dynamic task-topology discordance is missing-- we know the concepts of homophily and heterophily in static networks already and it seems natural to consider them in dynamic networks. But in what cases do the homophily and heterophily change?\nW2: A schematic figure is missing to clearly visualize different components and their relations in the proposed framework (saw some in the appendix but it may be better to put one in the main paper).\nW3: Some case studies to qualitatively understand the behaviors of the models are missing (again saw some in the appendix but it may be better to put some out-- more technical details can be put into appendix to trade for space).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JtGhooxL6KZ", "reviewer": "Reviewer_1rTB", "summary": "", "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": "", "summary_of_the_paper": "This manuscript presents a novel GNN, namely GReTo, to remedy topology-task discordance on dynamic graphs via target-homophily. They first formalize a dynamic graph homophily theory with both signs and distances, and accordingly refine the topology by designing the signed target oriented message passing and the layer importance based propagation. Experimental results on four dynamic graphs verify the superiority of proposed GReTo.", "summary_of_the_review": "The authors propose a novel GNN to remedy the topology-task discordance on dynamic graphs by integrating the signed message and layer-importance, which is reasonable and solid. The paper is well written, and easy to follow. However, more experimental details and analysis are recommended to be considered and provided. \n", "strength_and_weaknesses": "Strength:\n\n1.The paper is well organized and clearly written.\n\n2.The theoretical analysis is solid. \n\n3.The framework of GReTo is intuitively, where the two parts are well designed and well described.\n\nWeaknesses:\n\n1.Although dynamic graph regression shows positive results, there should be more insightful analysis to show where the improvements come from. In addition, mean and standard deviation for each method are recommended to make the experimental results more convincing.\n\n2.The ablation result analysis is not very convincing. Except the Temperature dataset, the variant V-Mix is always close to the full variant version, which means that not always all the components are needed.\n\n3.It is necessary to discuss whether the proposed GReTo can learn on dynamic graphs with large average time intervals and higher temporal node degrees.\n\n4.Some minor mistakes, Figures 2 and 7 are repeated.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7pj2nUyHi5R", "reviewer": "Reviewer_bmba", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "This paper presents a novel GNN model for dynamic graphs which considers spatial (intra graph: in the same timeframe) and transition (inter-graph: between different timeframes) homophiles by adaptive neighbourhood aggregations and high-order layer propagations. Averaging both gives the target oriented neighbours. The proposed method is called GReTo which empirically gives superior performance in graph regression. ", "summary_of_the_review": "This paper provides a GNN for dynamic graphs which performs well on graph regression. As is, it is hard to follow and understand. ", "strength_and_weaknesses": "The graphs studied are small and the model requires and n^2 step which makes it not scalable to large graphs. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster