Graph Neural Networks Designed for Different Graph Types: A Survey
Authors: Josephine Thomas
Alice Moallemy-Oureh
Silvia Beddar-Wiesing
Clara Holzhüter
Venue: Accepted by TMLR ()

Abstract: Graphs are ubiquitous in nature and can therefore serve as models for many practical but also
theoretical problems. For this purpose, they can be defined as many different types which
suitably reflect the individual contexts of the represented problem. To address cutting-edge
problems based on graph data, the research field of Graph Neural Networks (GNNs) has
emerged. Despite the field’s youth and the speed at which new models are developed, many
recent surveys have been published to keep track of them. Nevertheless, it has not yet
been gathered which GNN can process what kind of graph types. In this survey, we give a
detailed overview of already existing GNNs and, unlike previous surveys, categorize them
according to their ability to handle different graph types and properties. We consider GNNs
operating on static and dynamic graphs of different structural constitutions, with or without
node or edge attributes. Moreover, we distinguish between GNN models for discrete-time or
continuous-time dynamic graphs and group the models according to their architecture. We
find that there are still graph types that are not or only rarely covered by existing GNN
models. We point out where models are missing and give potential reasons for their absence.

Published in Transactions on Machine Learning Research (03/2023)
Graph Neural Networks Designed for Different Graph Types: A Survey
Josephine M. Thomas'
jthmmasSuni-kssel..e
GATN Grophs in Artificial Intelligence and Machine Learning Intelligent Embedded Systems
University of Kassel, Germany
Alice Moallemy-Ourde
amoolleengg&uuii-kssss....
GAIN Grophs in Artificial Intelligence and Machine Learning Intelligent Embedded Systems
University of Kassel, Germany
Silvia Beddar- Wiesing"
s.
GAIN Craphs in Artificial Intelligence and Machine Learning Intelligent Embedded Systems
University of Kossel, Germany
Clara Holzhüter'
GATN Graphs in Artificial Intelligence and Machine Learning Fraunhofer Institute for Energy Economics and Energy System Technology (TEE) Kassel, Germany
Reviewed on OpenReview: https: // openreview. net/ formm? id- h4BYt279uy
Abstract
Graphs are ubiquitous in nature and can therefore serve as models for many practical but also theoretical problems. For this purpose, they can be defined as many different types which suitably reflect the individual contexts of the represented problem. To address cutting-edge problems based graph data, the research field of Graph Neural Networks (GNNs) has emerged. Despite the field's youth and the speed at which new models developed, many recent surveys have been published to keep track of them. Nevertheless, it has not yet been gathered which GNN can process what kind of graph types. In this survey, we give detailed overview of already existing GNNs and, unlike previous surveys, categorize them according to their ability to handle different graph lypes and properties. We consider GNNs operating on static and dynamic graphs of different structural constitutions, with or without node edge attributes. Moreover, we distinguish between GNN models for discrete-time or continuous-time dynamic graphs and group the models according to their architecture. We find that there are still graph types that are not or only rarely covered by existing GNN models. We point out where models are missing and give potential reasons for their absence.
1 Introduction
Over the last decades, neural networks (NNs) have become increasingly important. Their development dates back to the early 1940s (Anderson & Rosenfeld 1988 With increasing computational power
and the possibility of utilizing Deep Learning (DL), their applications have reached most parts of society,
from detecting cancer [McKinncy et al. 2020 to playing computer games [Tbar et al. 2018 Silver et al.
All authors contributed equally.
Anderson & Rosenfeld 1988) provides historical overview up end 1980s.

---

Published in Transactions on Machine Learning Research (03/2023)
2018
Nevertheless, classical NNs are limited to Euclidean data. Given the rising amount of non-Euclidean data [Bronseein et al. 2017] and the fact that graphs are a suitable mathematical representation for many theoretical and practical problems, several authors started investigating NNs on particular graph problems
Cimikowski & Shope 1996: Lai ct al. 1994) or so-called "structuros" " (Sperduti 1997 Sperdutí & Staritaa
p997p in the 90s. With an ever-increasing amount of graph data available (see, e.g., repositories Rossi &
Ahmed (2015). or OGB Hu et al.
(0200) in many applications (e.g. traffic (Ma ct al.
2020 Rossi & &Ahmed
2015), citation (Feng et al. 2019
loannidis et al. 2019; [en al. 2020 Tran & Tran 2020), biological or
medical La Gatta et al 2020: Wang al. 2020 Yadati et al.) 2019 Zitnik et al. 2018). social Pareea et al.
2020 Rossi et al. 2020 Trivedi et al.
2019 recommendation (ankar et al. 2020 Wang et al.
2021 Yang
et al. 2020)), so-called Graph Neural Networks (GNNs) have become a thriving research field.
Therefore, many surveys have recently conducted intensive research on GNN models, e.g., Barros et al.
[2021]: |: Kazemi et al. (2020); (Skarding et al.] (2021) : Zhouu et al.] (2020). However, most GNN models are
either limited to a specific graph type or developed to address particular problems. E.g., Hier-GNN Chen eet al. (2022) is developed especially for hierarchical graphs, MXMNet. Zhann et al. (2020a) for multiplex graphs and EpiGNN La Gatta et al. (2020) focuses on learning the evolution of an epidemic. On the other hand, real-world graphs are diverse. In many cases, they contain heterogencous nodes or edges and evolve dynamically. One example of a heterogeneous graph is a power grid representation in which the nodes could have different types, such as "solar power plants", "wind parks", or "nuclear power plants". An example of a dynamic graph is a social network with cimenihanging nodes and the connections among them. However, no comprehensive overview is available that investigates which graph types are addressed by existing GNN models. Since the graph type plays vital role in choosing model to solve graph problem, it is essential to provide an overview of the latest collection of GNNs.
This survey aims to fill this gap by providing an outline of GNNs for all graph types and pointing out the absent GNN models for static and dynamic graphs. As comprehensive overview of the different graph types is missing, the first contribution of this survey consists of the definition and overview of these. It covers basic structural graph lypes (e.g., directed, multi-, heterogeneous, or hypergraphis) for static and dynamic graphs in discrete and continuous-time and the so-called semantic graph types (e.g., cyelic, regular, and bipartite graphs). This categorization approach is advantageous because some GNN models are restricted to specific graph properties. The second contribution is an analysis of which graph types can be handled by currently available GNN models. As third contribution, we group the investigated GNN models by their architecture in the main part. The final contribution consists in analyzing what graph types cannot be handled by current GNN models, including explanations for these gaps.
Due to the vast amount of publications the field, this survey camnot cover all existing models. Therefore, this survey aims to cover the most important models and list only one or two models for each graph type or property to illustrate the existence of at least one model. The following criteria determine the importance of the models for the choice: 1) Up-to-dateness of the model, 2) relevance of the model concerning the mumber of citations and its use as a baseline in other publications, 3) the generality of the model (c.g., that it is not only applicable to a particular domain), 4) explicitness in addressing the listed graph properties, and 5) simplicity of the model (e.g., if two models fulfill the same task, priority is given to the simpler one). The individual reason for the choice of each model can be found in the appendix in Tab
This paper is structured as follows. Sec. 2 contains related work. In Sec. 3 the considered graphs and their properties are defined in 3.1 while preliminary definitions concerning GNNs are given in 3.2 Sections 4 to 7 constitute the central part of the paper and deal with GNN models focusing on structural graph properties (Sec. D. dynamic graph properties (Sec. 5)) semantic graph properties (Sec. () and combined or other GNN models (Sec. 7). Here, each section contains a table showing which graph types and properties are addressed by existing GNN models, a description of the applied GNN techniques, and an evaluation of why current models might not cover specific properties. Note that many models have the same acronym in the respective publication. Therefore we altered some of them to distinguish the models and improve readability. Finally, Sec. M concludes the work and points out future challenges. The mathematical notation used throughout this work can be found in Sec. g Tab. 7
2

---

Published in Transactions on Machine Learning Research (03/2023)
2
Related Work
Several surveys that review GNNss concerning different aspects have been proposed over the last few years. Multiple surveys provide a more detailed overview of specific types of methods, such as convolutional GNNs
Gama et al. 2020;
Zhang et al.
2018 2019b), GNNs using attention mechanisms (Lee et al. 2019), or
Baysian GNNs (Shi et al. (021). ) Furthermore, many existing surveys focus on specific application arcas
2020 Wu al., 2022), such as natural language processing (Wu al.) (Jang & Luo 2022 Shlomi et al.,
2021), combinatorial optimization Peng al.) 2021 power systems (Liao et al. 2021]. Other publications
reviewing GNN models concentrate on specific aspects such as explainability (Yuan et al. 2021), or the
expressive power of GNNs (Sato 2020). Unlike these publications, we provide a more general survey, which is neither limited to particular lypes of methods or aspects nor explicit application fields.
Cai et al. (2018) provide a broad survey of graph embedding techniques, including methods apart from deep learning, such as matrix factorization or graph kernels, similar to (Cui al.) 20188 Goyal & Ferrara 2018: Hamilton et. al. 2017). In Bronstein et. al. (2017), an overview of deep learning methods applicable to Mon-Euulidiaa data is provided. The survey does not only focus graphs but aims to cover methods of geometric deep learning in general, including its applications, challenges, and future directions. Concerning GNNs, it primarily surveys convolutional methods. However, the aforementioned surveys do not cover methods for dynamic graphs. In contrast, (Wu et al.] 2020 covers spatial-temporal GNNs, convolutional methods, recurrent GNNs, and graph autoencoders. The investigated methods are grouped according to these categories. Similarly, (Zhang et al., 2020b) review models by the type of GNN they apply. However, these categories differ from thosse in Wu et al. (2020) such that instead of -patial-tempora GNNs, graph reinforcement learning and adversarial methods are discussed. Both methods only partially cover dynamic graph models.
Further publications such as Barros et al. (0021] Kazemi et al. (2020); Skarding et al. (021)) explicitly focus on models for dynamic graphs. [Skarding ct al. 2021 further group the reviewed models concerning the encoded lype of dynamics (e.g., node dynamie, edge-growing) and the applied methods. While Barros el. al. (2021) and [Skarding et al. (2021) survey models for dynamic graphs only, Kazemi et al. (2020) also reviews several static methods. However, the corresponding chapter of this survey aims to understand better the basic concepts for static graphs, which can be extended to dynamic graphs, rather than reviewing methods for static graphs. None of the abovementioned surveys categorizes the reviewed methods for different graph types and their semantic properties. The only survey that explicitly investigates GNN models concerning the graph types is Zhou et al. (2020). However, it does not consider all graph types covered in this survey since we provide a more fine- gre-grained distinction of different graph properties. Moreover, in Zhou et al. (2020) the authors focus on the pipeline of designing a GNN, including identifying the graph type and additional network modules such as pooling or sampling. Accordingly, it takes a different point of view and reviews GNN models amongst other modules, which can be integrated into a deep learning pipeline.
Our contribution is detailed overview of existing GNNs and their categorization into cortain types of methods, but more importantly, the types of graphs they can process. Unlike many existing surveys, we consider static and dynamic graphs. Moreover, we group the corresponding dynamic GNNs into discrete-time and contimuuus-time dynamic models while considering the node and edge attributes and the graph's structure.
3 Foundations
The application of graphs takes place many different fields. This is because of the high degree of freedom in designing a graph and, thus, in representing information. Therefore, many different graph types have been developed and extended over time. This section defines graph types and properties in detail to give the reader a comprehensive insight into all graph types and associated GNNs in detail and presents them in order. Readers familiar with the different graph types and properties may omit this section and go on to the following section, Sec. for an overview of existing GNN models and architectures.
For the remainder of this soction, the reader assumed to have basic knowledge of analysis and linear algebra (see, for example, Abbott (2001): |trrng (993]). ). A table containing the most frequently used notation can
be found in Sec. 9
3

---

Published in Transactions on Machine Learning Research (03/2023)
3.1 Graphs And Their Properties
At first, the considered graph properties and graph lypes have to be defined to survey for which graph types and properties GNN models exist. These definitions are given here, as well as some graph-related terms which are nceded throughout the paper.
We distinguish between structural and semantic graph properties. The graph structure is defined only by the mathematical objects that make up the graph, i.e, node, edge, and attribute sets. The so-called structural properties can be deduced from these sets, e.g., whether the graph is directed or attributed. Semantic properties, in contrast, do not affect the mathematical representation. They result from interpreting the graph, e.g., whether it is cyclic or tree. Some GNNs specialize in such properties since they frequently occur in real-world applications. All definitions concerning structural properties are taken from Thomas et al. (2021 and given here for the reader's comfort.
In the following, elementary graph types are defined. They form the basis for all graphs to which neural networks have already been applied or might be applied in the future.
Definition 3.1 (Static Graphs: Elementary)
1. A directed (simple) graph is a tuple G = (V,E) containing a set of nodes V c N and a set of directed edges given as tuples & E V.
2. (generalized) directed hypergraph is a tuple -=(E)) with nodes V c N and hyperedges
& that include a mumbering map fi for the i-th edge (x. f), which indicates the order of the nodes in the (generalized) directed hyperedge. W.l.o.g. it can be assumed that the numbering is gap-free, so if there exists node eE with f(u) k > then there will also exist a node s.t. f(v)= k k-
f: f::x No}
These graphs are called elementary because every other graph is a composition of them. In this sense, a directed hypergraph is a directed simple graph that simultaneously a hypergraph. Since one can not only combine clementary graphs but also extend them with additional properties, in what follows, different types of graph properties are introduced. Namely the static structural, dynamic struetural, and semantic properties.
Definition 3.2 (Static Structural Graph Properties)
An elementary graph G = (V,E) is called
undirected if the edge directions are irrelevant, i.c., for directed graphs: if (u, v) e E whenever (v,u) e for V. Then, the edges can be denoted as set of sets instead of a set of tuples, namely
E ((u, 1,, V, u off Jue V
for directed hypergraphs: if x (0) for all (x, T Abbreviated by & (x x V). 2. multigraph if it is a multi-edge graph, i.e., the edges E are defined as a multise c multi-node graph, ie., the node set V is a multiset, or both. heterogencous
the nodes or edges can have different types (node or odge-heteroggnncous) Mathematically, the lype is appended to the nodes and edges. Lee, the node set is determined by V c S with node type set S and thus, node (v,s) V is given by the node v itself and its type The edges can be extended by a set R that describes their types, to (e,r) Ve E of edge type R. 4. attributed if the nodes V or edges & are equipped with node or edge attributes. These attributes are formally given by a node attribute function and an edge attribute function, respectively, iee a: a V + A and w: + W, where A and W are arbitrary attribute sets. In case there are only node attributes the graph callod nodc-attributed (or node labelod /node features), in case of just odge attributes it called edge-attributed and if we have W R is called weighted.
/
the second set contains the sct of sclf-loops
3 fx(x) encodes that is undirected hyperedge
4A multiset. set that can have entries which occur multiple times.
4

---

Published in Transactions on Machine Learning Research (03/2023)
Fig. 1
shows examples for each graph type up to this point.
V
V3
directed graph
undirected graph
multigraph
a = 'Ozzy'
a a==(-2,4)
a,=7
a5
a+=
directed hypergraph
heterogeneous graph
attributed graph
Figure 1: Visualization of different elementary static graph lypes.
The term static in these structural properties stands for the absence of temporal dependence. This means, in particular, that once the graph is given, it never changes with time. In contrast, the so-called (temporal) dynamic structural graph properties are listed in the following.
Definition 3.3 (Dynamic Structural Graph Properties) A graph called
dynamic if the graph structure the graph properties time dependent. In the following, the notation G; = EV) f; E ' is used, where 7 is a set of (not necessarily equidistant) timestamps to emphasize the time-dependence and therefore the dynamics. growing is dynamic and the node or edge sets evolve w.r.t. addition of new nodes and edges respectively. Le., for all t; e T it holds
V Vi+1 or & E
shrinking if it dynamic and we just allow node edge set evolution w.r.t. deletions of nodes and edges respectively. Le.. for all t; é T, it is
2 V4n
E, E
4. strictly growing/ /hriining if consider only real inclusions in definition 2 and 3 above.
5. structure-dmnamic if it is growing, shrinking both simultaneously, i.e., in particular, the nodes
V or edges & evolve over time due to additions or deletions of nodes or edges 55
6. attribute-dynamic if the node or edge attribute function is time-dependent. Thus, we extend our
notions of the attribute functions to a; V + A and wi : E + W, for all 6; 6 T.
type-dynamic if the graph type evolves over time. E.g,, an undirected graph becomes directed from one to another time step.
Structurally, these dynamics describe different temporal behaviors of graphs. When processing dynamic graphs, they are typically defined either as discrete-time or continuous- representations.
Kazemi al. 2020 also mentions splits and merges nodes and edges. Obviously, these sequences of additions
and deletions.
5

---

Published in Transactions on Machine Learning Research (03/2023)
Definition 3.4 (Dynamic Graph Representation)
1. A dynamic graph in discreto-time reprosentation is given by set 9= (....... 963 of graph snapshots I at time steps i = 1....,k. Here, gi &V;, are static graphs with nodes V and edges &, E {(u,v) e VJJ.
2. A dynamic graph in continuous-time representation is defined by a set G G E)) containing an initial static graph at time stamp tu é T and a set E = te of events encoding a structural or attribute change at time stamp 1 >> lg E T.
Not all combined graphs are equally important in the literature and especially for GNNs. The following introduces some combined graph types of specific interest with proper names. Definition 3.5 (Combined Static Graphs)
1. Knowledge graphs are defined in several ways. In Wang et al. (2021), they are defined as heterogeneous directed graphs, while in Yu et al. (2020) knowledge graphs are the same as edge- heterogeneous graphs. But there are also definitions that do not see a knowledge graph as a graph combined from the aforementioned types, see for example Ehrlinger & wo6l (2016) for an overview.
2. multi-rclational graph (Hamilton 2020) is an cdge-heterogeencoss but honogeoooos graph.
3. content-assoociated heterogeneous graph is a heterogeneous graph with node attributes that correspond to heterogeneous data like, e-g., attributes, text or images (Zhang et al. 2019a)
4. A multiplex graph/ (eapph/munt mmulti-channel graph corresponds to an hige-heeeroogeeeuus graph with self-loops (Hamilton 2020). Here, we have k layers, where each layer consists of the same node set V, but different edge sets g(A) Additionally, inter-layer edges & exist between the same nodes across different layers.
spatio-temporal graph is a multiplex graph where edges per each layer are interpreted as spatial edges and the inter-layer edges indicate temporal steps between a layer time step and t+ They are called temporal edges (Kapoor et al. 2020
Remark. All the combined properties mentioned in Def. 3.5 can occur in dynamic graphs as well.
Besides the structural properties, a graph can have semantic properties that do not explicitly change its structure but result from applying or interpreting the graph information. Some GNNs are limited or specialized to these properties defined the following.
Definition 3.6 (Semantic Graph Properties)
An elementary graph G = EV,E) is called
complete if all pairwise different nodes are connected through an edge, i.e., E ((, E Vx VxV/u+ u+ 2. r-regular if each node E V has r N neighbors, i.e.,
[[ = Hu (1, v) E
3. bipartite if there exists a disjoint node decomposition into two sets V 1 U W,, such that the edges are of the form E x W.
4. connected if the graph undirected and for all node pairs v, w V there is a path from to w in G. An clementary graph is called weakly connected if the underlying undirected graph is connected and it is strongly connected if for all node pairs v, E V there is a directed path from to w in G. Otherwise it is unconnected.
5. cyclic if it contains a cycle of length k E N, ie., there exists a subgraph G. V e Vi, such that the series of nodes and edges
H = (fu (eI....,, (f.........)............... 01, 01 v2...... Mk. Ck, 01 is closed (directed) path called (directed) cycle of length k with 2 + ny Vi,j. Otherwise, is called acyelic or a forest.
6. tree if it is a connected forest. In case each node in the tree has at most two neighbors, it is called binary tree (Gessel & Stanley 1995). A polytree is directed graph whose underlying undirected graph is tree (Dasgupta) 1999).
7. level-(I+1) (1]+ 1) hierarchical w.r.t. a level-/ base graph H (V, if one can find a complete partitioning of H into & 2 non-empty, connected sets of nodes VI..., Dr.. Such that each set of nodes Vi V induces a subgraph sub; = (V,, s E) with &, = ((1),,)) U2) e E U1 02 e V,). Each of these subgraphs, in turn, corresponds a node in the hicrarchical graph G. Edges in G correspond to edges in H between nodes u; 12y of two different subgraphs sub;(H), sub,, (Stoffel et al. 2008).
6

---

Published in Transactions on Machine Learning Research (03/2023)
8. scale-free, if its node degree distribution P(d) follows power law P(d) dt,, where y typically lies within the range 2 < < 3.
A (generalized) (directed) hypergraph G (V,8) ) is called
recursive, if an edge can not only exist between nodes, but also between edges and a recursive way. E.g. two edges ej and 62 make up edge 612; odges 63 and 64 make up edge 634 and edge es consists of edges e12 and 634- See definition 4 of ubergraph in Joslyn & Nowak (2017) and figure 1a in Yadati 20200 for visualization.
Fig. 2 shows examples for each semantic graph property by applying to undirected graphs.
complete
cyclic
bipartite
tree
2-regular
acyclic
unconnected
binary tree
Figure 2: Semantic graph properties illustrated for undirected graphs.
In the following chapter, introduce the basic architectures for GNNs that make up all the GNNs in this survey. In order to be able to describe these appropriatcly, we list some frequently occurring graph-rclated terms beforehand.
Definition 3.7 (Graph related terms)
Let G = (V,E) be a graph.
The degree of node v is given by 5(v) [(e E | e)l. For directed graphs, the out- or in-degree of is the number of edges starting v or ending in v, respectively. The degree of an edge e determined by Jel, i.e, by the number of nodes in the edge.
2. The graph Laplacian or Laplacian matrix L is defined by L D A, where D is the degree matrix and A the adjacency matrix. In Graph Convolutional Neural Networks, it is mostly used in a normalized version, e.g., the symmetric and normalized graph Laplacian Lnorm = AD- where Ā is the adjacency mairix with self connections and D the degree matrix with self-loops.
3. An entry Vi,j of the incidence matrix e (0, 1)111111 of a graph G= G=(V, is 1, if the node i is incident to odge j, and 0 otherwise. For non-hypergraphs, the incidence matrix has exactly 2 entries per row that are non-zero. Let V V be set of nodes. Then, the induced subgraph of 1> is defined by graph G(V) (V,E) with edges E (e ee V x V} between the nodes of V.
4. A path from E V to V, denoted by p(u, v) el,...,ek E E is a sequence of edges, for which there is a sequence of nodes (z1..., 2k+1) such that (z,, 2++1) for i 2..... k and = (u,z) and Cs-1 = (y, v) for some yyyeS E V.
The path length of a path p( (, Ei,...eg, denotes the sequence length, i.e., len(p(u, u)) = k. random walk of length i is path of length & whose odges are selected itcratively and randomly.
3.2 GNN Preliminaries
GNNs define the adaptation of Iraditional NNs to graph data and aim to learn high-level representations of graphs in an end-to-end fashion by applying several network layers. They can be applied to all classical machine learning problems, such as classífication, regression, or clustering, for entire graphs and subgraphs node or edge level. Each layer computes new representation of the graph its components. A typical procedure is to update the representation for the nodes in each layer by propagating information through
7

---

Published in Transactions on Machine Learning Research (03/2023)
the graph. A task-specific prediction then be made using the learned representation and suitable decoder function. For node classification, e-g,, a typical choice for the decoder is standard MLP with a softmax activation as the output function. It maps the learned representation to a vector indicating the class probabilities for all nodes. At the edge level, frequently considered task is link prediction which aims to predict the probability of the existence of an edge. The corresponding decoder oflen implemented as a logistic regression classifier since the existence of an edge can be expressed as a two-class problem.
Different types of GNNs specify the computation of the node representation in the GNN layers. According to Bronstein et al 2021 the following relation of GNN approaches applies:
message-passingg attention convolution
Therefore, these are introduced one after the other, from the most general case to special ones. visualization of the three GNN layer types shown figure 3 The Recurrent Neural Networks coexist with the message- passing and will be introduced afterward. Combined with GNNs, is particularly relevant for dynamic graph learning problems due its ability to model temporal data.
11
X
att
Mau
Cul
Cuu
att
u1
m
XU
Cu3
X3
Xu
att
X3
xu
Mua
X3
Cuz
att
mg2
X2
X2
X2
convolutional
attentional
message-passing
Figure 3: Visualization of the information propagation process in the different types of GNN layers for node u and its neighbors. The idea for the figure is taken from Bronstein et al. (2021 Fig. 17). Left: In convolutional layers, the node features 2, of the neighbors É ( of node are multiplied with constant Cu,e to form the message. Middle: In attention layers, this multiplier is computed via an attention mechanism att = (I.,,,.,,)) x.) between the source and the target nodes u,v. Right: In message-passingg layers, the messages maz are computed explicitly from the source and larget node representations i.e., Mas v T.p.
3.2.1 Message- Passeng
determines which and how much information is forwarded between two nodes, e.g., via their connecting edges. The resulting representation h, node u is computed from the node representations
æ Vo
h ① Bus
+ ve)(
(WW, (2)
(1)
where is a learnable message function that assigns an information vector to the pair u,v. Typically, t is defined as multiplication with learnable weight matrix, and its output is denoted aggregation depicts the mossago-passingg process on the graph, which in most cases is implemented as a non-parametric operation such as sum, mean, or maximum. (N) denotes a neighborhood of node u and ø is an activation function (Bronstein et al. 2021
message. The
3.2.2 (Multi-head) Graph Attention
Graph attention is a special case of message- message-passing (Bronstein et al. 2021). Here, the message computed by applying learnable function to each neighboring node weighted by so-called attention factor. Typically,
8

---

Published in Transactions on Machine Learning Research (03/2023)
the function & is shared across all neighbors, whereas the attention is computed individually for each node pair. The attention mechanism specifies the message-passing rule in the aggregation function as follows:
ha Φ
Du. VEN (u)
att T.) (z) (1
where the attention function att is learnable and determines the effect of the message from neighbor v with representation (xx) to the hidden representation ha of node u. Additionally, the attention coefficients are normalized across all neighbors the target node. Note that att,, therefore, depends not only on 2u and 2a sum, the aggregation is a linear combination
but also on all other neighbors of node ze-- Furthermore, considering feature-specific weights for the neighbors.
Multi-heas attention extends the attention mechanism to K different attention functions (Velickovic et al. 2018 and is determined by
Dus attæ x. x.) M((.))
h
3))
ke[K] (eN(
where denoles the concatenation operation. The K different attention functions also called allention heads are computed independently. In Velickovie et al. (2018), implementation of an attention mechanism is proposed. The according self-attention function att : [dim(h) (gdim()) - R outputs attention weight.
Wiy WW,, Wh;)
for an edge (i,j) given the incident node embeddings h; h2 to indicate the importance of the features of node j node for all node pairs i.j V. Considering the neighborhoods given in the graph, the attention mechanism can be defined by
oz.j == softmax, (Wi.s) = EkeN(()) exp
expwh,j
3.2.3 Spatial and Spectral Graph Convolutions
Compared to the attention approach, the graph convolution aggregates the neighbored nodes directly using fixed weights (Bronstein et al. 2021 by
Cu, Cu (xx)) neN(u)
h2 = Φ Ta.
+
(4)
where Cu,v is a factor indicating the impact of neighbor on the hidden representation of node Note that Cu,e is a pre-defined constant instead of a node-specific function, as is the case for attention layers. For spatial convolution, Cu,r is usually given by the (weighted) adjacency matrix and thus includes structural information. For spectral convolution, spectral filters dependent on the graph Laplacian (c.f. 3.7 3.7 determine the weights of all nodes in the graph integrating structural information implicitly.
If the aggregation is sum, the layer can be interpreted as linear diffusion or position-dependent linear filtering An example of spatial convolution in layer 1 - 1 is given in, e.g., Morris et al. (2019
M (W,,, W₂ Σ n()) vEN(u)
(5)
W1 and W2 are learnable weight matrices and is activation function such ReLU(.) max(0,-)
An implementation of standard spectral convolution is given in, e.g. Kipf & Welling 2017) The layer-wise propagation rule in layer I is determined by
H (++) = o D 1 AD ! w()),
(6)
Inorm

---

Published in Transactions on Machine Learning Research (03/2023)
where A= = A+ E is the adjacency matrix with added self connections, E is the identity matrix, D is the degree matrix of the graph with self-loops, and Lorr is the normalized graph Laplacian. is activation function, and W is a learnable weight matrix functioning as a filter. The idea of spectral graph convolutions comes from signal processing. Vividly, one can imaginc it as global message passing on a graph, weighted with a filter.
3.2.4 Recurrent Neural Networks
For each time step t, the Recurrent Neural Network (RNN) calculates hidden representation using historical information logether with the current input ( Bronstein et al. 2021 First, the inpul is transformed by an encoder function f to a representation vector x = f(X())) Then, x(() is aggregated together with the previous information by an update function R R R R that additionally considers the hidden representation from the time step before. Altogether, a basic RNN is formalized by
(h =((= R(="),,(()))) ((-))))
In the context of graph learning, the node feature matrix is commonly used as initial input X ( Furthermore, in various GNNs for dynamic graphs, GCN layers are combined with RNNs by, e.g., modeling the GCN weight evolution with an RNN or propagating the learned structural information from one timestamp to the next timestamp.
4 Models Focusing on Structural Graph Properties
Learning on simple graphs is most prevalent in the research of GNNs. The clementary graph structure can already model relations the data, and the mathematical foundations go back to the 17th century. After the most prominent introduction of Graph Neural Networks by [Scarsllii et al.) (2009) for learning on static node-altributed graphs, many different. extensions have been proposed. An overview of GNN models for simple static graphs is discussed in Sec. 4.1 Their approaches often build on the graph information processing scheme of Scarselli et al. and adapt it to new applications and several structural graph properties.
One of the extensions includes the higher-order representation of relational data with the aid of elementary hypergraphs. Hypergraph theory is still a young field and has been essentially developed by Claude Berge Berge 1973) in the 1970s. Learning on hypergraphs has also emerged as part of research in recent years and has much potential for applications on differently structured hypergraphs, as illustrated in Table 2
4.1 GNNs for Simple Graphs
The number GNNs for simple graphs has increased immensely in the past years, so Table D does not list all of them but gives an overview of several GNNs for simple graphs with structural properties defined Def. 3.2 This demonstrates which graph types have already been considered in GNN research. The models are selected according their up-to-dateness, relevance, general applicability, explicit addressing of specific graph type, and simplicity, as discussed in the introduction. Note that in the case of processing tttributed graphs, the attributes have to be encoded in d-dimensional vectors. To apply the corresponding models to arbitrary attributed graphs, preprocessing steps have to be utilized as in Zhang et al. (2019a).
The most common type of GNNs for simple graphs concerning structural properties are convolutional models, which compute new node representations in each layer. common graph convolution as, for example, defined in GNN* (Scarselli et al. 2009), or WL (Morris et al. 2019), typically assumes attributed nodes and allows for directed and undirected edges without being explicitly designed for either property. Models designed for other graph types typically extend common spectral or spatial convolution to adapt to the specific structural property they focus on.
To consider directed edges, for example, in GenRecN (Sperduti & Starita 1997). a standard spectral convolution is applied only on the out-neighbors of a target node, i.c., on those neighbors connected via a directed edge originating from it. A more recent model, MagNet (Zhang et al. 2021), applics spectral convolution using complex-valued Hermitian matrix, called magnetic Laplacian, instead of symmetric and
10

---

Published in Transactions on Machine Learning Research (03/2023)
real-valued Laplacian which cannot be computed due to the asymmetric adjacency matrix of a directed graph. The magnitude of the complex Laplacian indicates the presence of an edge but not its direction, while the phase of the complex Laplacian indicates the direction of an edge. The lack of models designed for graphs with edge attributes probably results from considering edge attributes only in addition to node attributes since edge attribules are lypically not relevant in isolation. In terms of heterogeneity, similar observation can be made. Corresponding graphs are either heterogencous in their nodes and edges or node homogeneous, i.e. the, node set remains of one type. Edge heterogeneity is more common than node heterogeneity since it inchudes widely-used multi-relational graphs. These be handled by, e.g., extension of standard convolution applied separately for each relation (GRNN (Toannidis et al. 2019
Another common procedure is extending & convolutional model using an attention mechanism, e.g., as described Sec. [.2.2] Attention mechanisms are suitable for node attributed graphs since they allow the computation of node-specific attention scores that express the importance of one node another. These attention scores can serve as weights in computing node features to focus on specific nodes. Spectral (CapsGNN (Xinyi & Chen 2018)), well as spatial convolutions (GAT (Velickovic al. 2018)), can be equipped with attention mechanisms. They also be adapted to attributed edges to process entirely attributed graphs (EGNN (Gong & Cheng, 2019h). Also, attention-based models are suitable approach for heterogeneous graphs since multi-head attention can be used to model different relation types, as in AA-HGNN (Ren et al. 2020). particular case attention convolution is HAN (Wang et al. 2019), which utilizes selected set of meta paths for neighborhood aggregation.
Table 1: GNN's developed for learning on simple graphs of different structures. Such models are most prevalent the research of GNNs.
Graph Type
Models
Problem
Data Category
GenRecN
graph classification
logic terms
Sperduti & Starita 19977
directed
MagNet
link prediction, node classification
linking of websites, synthetic
Zhang et al. (2021)
subgraph matching, graph classification, web page ranking
GNN
synthetic, mutagenesis (molecules)
undirected
Scarselli et al.
2009
GAT
citation networks, protein interaction
Velickovic et al.
2018
node and graph classification
graph
node-attributed
CapsGNN
biological-, social networks biological-, social networks, molecules
Xinyi & Chen
2018
WL
graph classification, attribute prediction
Morris et al.
2019
odgo-attributed
EGNN
graph classification, node and edge attribute prediction
Gong & Cheng PG-GNN
2019
citation networks, protein structure
attributed
Xia & Ku (0021)
node-hedeerogeneous
GRNN
odge-heterogencous
citation networks
Ioannidis et al. (0019)
AA-HGNN
node classification
Ren et al. 20200)
news articles & citation networks
heterogeneous
HAN
Wang et al.
2019
multi
11

---

Published in Transactions on Machine Learning Research (03/2023)
4.2 GNNs for Hypergraphs
Learning on hypergraphs as in Def. 3.1 has been rarely explored. Most approaches involve convolutions adapted to hypergraphs, i..., the property that an edge can be incident to an arbitrary number of nodes. Table 2 lists GNNs that mainly address node classification on citation networks represenled as hypergraphs, which shows that the application of hypergraphs not yet widespread; hence, the available datasets are currently limited. During the rescarch for hypergraph GNNs, it turned out that, so far, only few GNNS have been applied to hypergraphs. When it comes to additional structural propertics defined in Def. 3.2 sometimes only one or two models for the specific hypergraphs have been developed. Table 2 indicates that. the data is still very homogeneous and that the heterogeneity in graphs is only addressed to limited extent.
One option to handle hypergraphs is to transform them into simple graphs and apply standard GNNs afterward. This preprocessing can be done by selecting two representative nodes for each hyperedge, as in HyperGCN (Yadati et al. 2019). Based on the assumption that nodes in hyperedge are similar, the representative nodes typically have the most significant difference between their attributes. Another approach presented in LHCN (Bandyopadhyay et al. 2020) represents hypergraph as line graph In this process, each hyperedge of the original graph serves as simple node in the line graph. The corresponding node attributes are computed by the average across the attributes of all hypernodes in that hyperedge. Both variants allow for processing attributed and undirected hypergraphs using GNN models for simple graphs.
Table GNNS learning on hypergraphs with different additional properties. The selection of GNNs is still limited, which illustrates gaps and the potential of the young research field.
Graph Type
Models
Problem
Data Category
NDHGNN
directed
node classification
citation networks
Tran & Tran 2020
densest k-subbyyergraphh problem, node classification
combinatorial optimization, citation networks
HyperGCN
undirected
Yadati et al. 2019
by Soverrerrae
HyperConvAle Bai et al. 2021
node classification
citation networks
LHCN
node-attributed
node classification
citation networks
Bandyopadhyay et al. 2020
HGNN
node classification, object classification
edge-attributed
citation networks
Feng
2019
AHGAE
citation networks,
attributed
graph clustering
Hu et al. 2021
3D models
node-heterogeneous
cdge-heterogeneous
HWNN
heterogeneous
node classification
citation networks
Sun et al. (021b
G-MPNN (multiple edges)
knowledge (hyper-) graphs
multi
link prediction
Yadati
2020
There are also models which are specifically designed for hyporgraphs, most of them based on spectral convolutions. The graph's incidence matrix can be used to adapt spectral convolutions attributed
TThe nodes of line graph w.r.t. an original graph determined the edges of the original graph, while the edges inserted between two edges of the original graph that share an incident. node.
12

---

Published in Transactions on Machine Learning Research (03/2023)
hypergraphs and the node and edge degree matrix in the neighborhood aggregation (HGNN (Feng et al. 2019), AHGAE (Hu et al. 2) Such convolution can be additionally equipped with an attention mechanism (HyperConvAtt (Bai et al., 2021)). NDHGNN (TTaan & Tran 2020) uses separate incidence matrices for the source and target nodes to model the graph's Laplacian in the spectral hypergraph convolution to process directed hypergraphs. Such convolutions can also be used for heterogeneous graphs by using edge homogenization, e.g., by working on subgraphs that include hyperodges of only one specific type. In HWNN (Sun a 2021b), the spectral convolution is applied on subgraphs, which include hyperedges of only one specific type. Finally, to enable learning multi-hyyperrapphs, a message- message-passing GNN is extended to include multiple relations and node or edge duplicates (Yadati. 2020).
Both approaches, i.e., transforming hypergraphs into simple graphs or directly working on them, have advantages and disadvantages. The first case enables the application of well-established GNN architectures, which have typically been investigated more thoroughly. However, the transformation often related information loss, affocting performance. In HyperGCN (Yadati et al.) 2019). the information from nodes in hyperedges that do not serve as representative nodes disappear. Models that directly operate on hypergraphs, such HGNN (Feng et al. 2019 can use the complete information to learn.
5 Models Respecting Dynamic Graph Properties
Many applications include data that changes with time. In the application of graphs, it often appears, e.g., that graphs are growing structurally changing or that node and edge altributes are evolving, as defined in Def. 3.3 Therefore, the research on GNNs for dynamic graphs has expanded immensely. There are two common approaches in graph learning for representing a graph's dynamical behavior: discrete-time and nontiuuoustimme representation (cf. Def. 3.4). The first approach has been widely used since the snapshots simplify the processing of structures processing time graphs are listed in the next section. The continuous-tima approach is much more compact in its reprosentation since it stores only events instead of the entire graph for each time step. However, local evaluation of the graph is required, i.e. the area in the graph affected by an event has to be identified and retrieved to process the event using GNN. Hence, the application of this representation is more complex, which is also reflected in the less frequent use of it in GNN models, which can be seen in Sec. 5.2
the graph. Corresponding proposed GNNs in the literature for
5.1
GNNs for Discrete- Time Graphs
Although dynamic graphs are much more challenging to handle than static graphs due to the additional temporal dependencies, existing dynamic GNN models already cover many structural graph properties. GNN models operating on discrete-time graphs are typically extensions of static GNNs since the discrete-time representation corresponds to a series of static graphs. Therefore, similar gaps appear, i.e., only node- heterogeneous graphs and multi-graphs are not yet covered. The structural component of dynamic graphs can be learned by applying standard GNN models to the graph snapshots.
Those models are often combined with RNN-based models to encode the dynamics, which capture the temporal features. Such an approach is pursued in, e.g., GCRN (Seo et al.) 2018). The model processes attribute dynamic graphs using a spectral GCN combined with an LSTM. First, the node attributes are preprocessed by a spectral convolution, and the resulting representation is passed to the LSTM, which captures the data distribution. A similar approach is taken in WD/CD-GCN (Manessi et al., 2020), which applies a GCN to transform the input graph sequence into a sequence of node representations, which are then processed by modified LSTM. EpiGNN (La Gatta et al.) 2020) also combines GCNs and LSTMs to predict the parameters of a generic epidemiological model based on historical movement data. The model embeds the graph nodes for each time step, representing locations using a standard GCN, It learns the desired parameters by embedding the current graph and information from previous time steps stored in the LSTM.
13

---

Published in Transactions on Machine Learning Research (03/2023)
Table 3: GNN's learning discrete-time dynamic graphs. Many of these models are extensions of the static case since the discrete-time representation corresponds to series of static graphs. Therefore also the gaps appear similar to the static case. The O sign means, that the graph handled by the model can have attributes, but the attributes are static. Thus, they appear or disappear together with their respective nodes or edges but do not change over time.
Data Category
Graph Type
Models
Nodes
Edges
Attr.
Problem
add
del
add
del
node
odge
EpiGNN
node label
directed
La
Gatta
covid-19
prediction
al. (2020)
DySAT
communication, rating networks
Sankar et al.
x
x
link prediction
undirected
(2020)
(WD/ (WD/CD)- CD)- GCN
research community
x
X
node classífication
Manessi
eet al. 2020
GCRN
video prediction graph sequence prediction
node- attributed
Seo ct al.
x
videos, text
(0018)
graph reconstruction, link prediction, anomaly detection
synthetic, collaboration, communication networks
DynGEM Goyal et al.
edge-
x
attributed
(0118
synthetic, social networks,
DTR
EvolveGCN Pareja et al. 2020
link prediction, edge and node classification
attributed
v
bitcoin, community network
node-
heterogeneous
Re-Net
edge-
extrapolation link prediction
knowledge graphs
Jin et al.
x
x
X
X
heterogeneous
(2019)
DyHAN
e-commerce, online- community
heterogeneous
Yang et al.
x
x
link prediction
(020
multi
TOnly static edge attributes considered.
8Tehe model uses the moving written digits datasat (moving-MNIST dataset) generated by Shi et al.
Shi all (2015)
" "Only considers the previous time step, patterus of short duration (length for link prediction and restricted weights.
10 Edges weighted generally attributed.
14

---

Published in Transactions on Machine Learning Research (03/2023)
DHAT
directed
Luo
al.
x
v
x
feature prediction
traffic data
2021
undirected
STHAN-SR
node-
Sawhney
X
X
x
V
node ranking
stock prediction
attributed
et al. (2021)
by hypergrapi
HGC-RNN
Yi & Park
x
feature prediction
traffic flows
(0200)
Hyper- GNN
action
attributed
Hao
al.
recognition graph classification
human motion
2021
node-, edge
heterogeneous
MGH
graph classification
heterogeneous
Yan el al.
v
videos
2020
multi
Further approaches combining RNNs and GCNs are, c.g., RE-Not (Jin al.) 2019) and EvolveGCN (Pareja et al. 2020). RE-Net computes local representations for all nodes by applying RNN to its temporal neighborhood, ie., the neighbors at different time steps. The model is designed for heteroentoossneouus graphs and aggregates the edges of different types using GCN before the neighborhood aggregation. To obtain global node representation, the local node representations over time are processed by another RNN. In contrast to the models mentioned above, EvolveGCN uses the RNN to model the GCN weights, which embeds the graph nodes. More specifically,, the weights of each GCN layer are generated by an RNN, which takes the weights of the preceding GCN layer and, optionally, the node embeddings as input. This way, the model adapts the GCN weights along the temporal dimension to tackle the problem of changing node attributes.
Another way to handle temporal features in GNNs is temporal attention. DySat (Sankar et al. 2020 C.g., generalizes the GAT approach (Velickovic et al. 2018) described in Sec. [ to dynamic graphs. On the one hand, the model extends the structural attention mechanism. On the other hand, it incorporates an additional temporal attention mechanism that enforees an auto-rogressive behavior. Similarly, DyHAN (Yang et al.) 2020) generates node embeddings using node-level attention and updates them via neighborhood aggregation and edge-level attention. Finally, the node embeddings are aggregated over time using a temporal attention mechanism. Heterogeneity is accounted for by applying node-level attention at each time step subgraphs of only edge type. During edge-level attention, the importance of cach edge type is learned through one-layer MLP. DynGEM (Goyal et al.] 2018) takes entirely different approach and is a dynamically extendable autoencoder for growing graphs. The imput and output dimensions are extended respectively for each new incoming node.
Since handling hypergraphs is challenging, especially the dynamic case, few models have been proposed yet. One model that combines RNNs and GCNs is the HGC-RNN (Yi & Park 2020). It integrates the temporal evolution of higher-ordered structures with two different hypergraph convolutions to encode structural and temporal information, global states, and subsequent recurrent unit. All other hypergraph models in Tab. involve attention mechanisms. Typically, they combine hypergraph convolution with a temporal attention mechanism, as in DHAT (Luo et al. 2021). and MGH (Yan et al. 2020). For graph learning on video data, MGH extracts features from classical CNNs of different, granularity to define hypergraphs of different types beforehand. The heterogeneity the edges is then integrated into the model using corresponding attention.
A very similar model is Hyper-GNN (Hao et al. 2021). It applies hypergraph convolution similar HGNN (Feng al. 2019 from Sec. 4.2 and a corresponding attention mechanism adapted to neighborhoods
15

---

Published in Transactions on Machine Learning Research (03/2023)
hypergraphs. The overall architecture consists of three parallel networks of the same structure, each processing different input features. STHAN-SR (Sawhney et al. 2021) also applies an attention convolution, which has been designed for static graphs. It applies a HyperGCN model (Yadati et al. 2019) from Sec. 4.2 to process node features that have been generated utilizing an LSTM and a temporal attention mechanism.
When considering the types of dynamics the different models can handle, it becomes apparent that most of them focus on specific dynamics, such as dynamic node attributes only (EpiGNN (La Gatta et al., 2020), GCRN (Seo et al., 2018), STHAN-SR (Sawhney et al. 2021), HGC-RNN (Yi & Park 2020), DHAT (Luo et al. 2021 or evolving edges (RE-Net (Jin et al., 2019), Hyper-GNN (Hao et al. 2021), WD/CD-GCN (Manessi et al. 2020)). In particular, to the best of our knowledge, MGH (Yan et al. 2020) is the only model capable of processing graphs with changing node and edge sets and node and edge attributes over time.
Among all the dynamics, deleting nodes and changing edge attributes have emerged as the least considered and probably most challenging ones. In the case of decreasing node sets, difficulties arise from the changing data structures leading to data gaps, the handling of obsolete data, and in particular, the lack of data and applications in this area. At the same time, the lack of models for changing edge altributes is consequence of the fact that there are hardly any data and applications for this case.
5.2 GNNs for Graphs in Continuous Time
Regarding dynamic graphs in continuous-time representation, fewer models use the advantages of this compressed representation, although the amount is growing quickly. Especially dynamic hypergraphs in this form are currently rarely investigated. Using the continuous-lime representation allows the usage of explicit timestamps and an explicit specification of the change in the graph instead of processing a graph snapshot in every time step. Therefore, it drastically reduces the storage requirements. Nevertheless, utilizing this representation is challenging due to the absence of direct encoding of the graph structure at a particular time and the model's requirement to be updateable in case of occurring events.
Stochastic processes are frequently used to model dynamic graphs represented as sequence of events. Typically, such processes model the probability of an event occurring at specific time. These events encode the graph's dynamies, such as a node's appearance or an attribute's change, and an intensity function describes the distribution of the events over time. The occurrence of an event is modeled based on the most recent events involving the nodes or edges of interest.
Examples of approaches utilizing stochastic processes are Know-Evolve (Trieedi et al. 2017 and its extension, DyREP (Trivodi et al.) 2019). Know-Evolve considers events of appcaring edges of different types. Here, separate embeddings for source and target nodes are computed to take directed edges into account. Furthermore, a learnable function is applied to the difference between a specific node's current and the last event to capture the temporal evolution. Morcover, previous embeddings of the nodes and edges involved in the current event are processed by an RNN-based model to encode the effect of the recurrent participation of each entity in events. The node embedding is further processed by a learnable function, which captures the compatibility of nodes in previous edges. Based on the learned node embeddings, a temporal point process is used to model the probability of an edge occurring between two existing nodes at the next timestamp. Evolve'solve's extension DyREP iddillynally uses structural information of the graph for two different edge types that represent different ways of communication between nodes.
A different approach is proposed in DyGNN (Ma et al., 2020). It utilizes LSTMs in two kinds of units, one for the source and the other for target nodes connected through an edge. Tn the case of link prediction, node pairs are ranked respecting the cosine similarity of their node representations, and in the case of node classification, the softmax function is utilized. Similarly, TGN (Rossi et al.) 2020) enables the usage of memory module, which can be updated using an RNN such as LSTM GRU. The obtained node embedding can be used together with learnable function to perform, e.g., temporal attention, summation, or projection. Afterward, an MLP processes the node embeddings of node pairs to generate a probability for the edge at the next. limestamp to perform future link prediction.
[Souza et al. ) proved a deficit in the exprossivity of TGN and proposed the Positional- Injective Temporal Graph Net (PINT) to overcome this deficit. A node embedding at a certain timestamp is determined by an injective temporal aggregation of the neighborhood, where the attributes of the neighbors are calculated
16

---

Published in Transactions on Machine Learning Research (03/2023)
with an MLP over the neighboring node attribute concatenated with the corresponding edge attribute. Further, the performance is improved by concatenating the relative positional features that incorporate information from the temporal walk structures with the node features.
Jin et al. 2022) propose a model that uses a recurrent unit combined with temporal walks. Such walks are defined as node sequences which subsequent nodes have previously been involved in an event together. While sampling temporal walks for target node, nodes that have been involved in an event with the target node more recently sampled with higher probability. By anonymizing these walks into relative and node- undeciispecific encodings, so-called motifs created. An autoregressive gated recurrent unit processes these to compute the node embeddings. Since the nodes are sampled irregularly for the temporal walks, the motifs are integrated over multiple interaction time intervals.
Table 4: GNN's learning on continuous-time dynamic graphs. Due to the difficulties arising from the lack of a direct encoding of the graph structure each time point, there are only certain graph types covered by models models utilizing graphs in this representation.
Data Category
Graph Type
Models
Nodes
Edges
Attr.
Problem
add
del
add
del
node
edge
Know-Evolve
link/time
socio-political interactions
Trivedi et al.
X
X
directed
prediction
2017)
DyGNN
link prediction, node classification
communication/ trust networks
Ma
al.
x
2020
undirected
DyRep
link/event time prediction
social networks, github
rivedi et al.
x
x
X
node-
2019
attributed
edge-
attributed
social networks, interaction networks
Neur T'Ws Jin
dynamic link prediction
attributed
et al. 2022
x
x
x
x
X
node-
graph
heterogeneous
Know-Evolve
link/time prediction
socio-political interactions
Trivedi al. 2017)
x
edge-
heterogeneous
DyRep
link/even time prediction
social networks, github
CTR
Trivedi et al.
x
x
x
2019
heterogeneous
PINT
Souza
al.
2022).
node classification, edge prediction
multi
TGN
social networks
Rossi
al.
2020
11e baseline models used in the experiments made continuous time dynamic GNNs. All models used either made for static graphs (e-g., GCN, GraphSAGE) discrete-time dynamics (e.g., DynGEM, DANE, Dynamic Triad).
17

---

Published in Transactions on Machine Learning Research (03/2023)
directed
Q&A platform, political interactions, patient medication
HIT
edge, pattern- time prediction
undirected
Liu
et
x
x
x
2021
(node, edge) attributed, (node, edge) heterogeneous, multi
To the best of our knowledge, the only GNN developed for hypergraphs in contintous- representation is HIT (Liu et al. (021). To encode structural and temporal information, it uses temporal random walks defined as a randomly selected set of hyperedges backward in time. Aflerward an aggregation mechanism pools the obtained representation into the final node embedding.
6 Models Utilizing Semantic Graph Properties
Besides the structural graph properties, it is also possible to consider semantic properties in designing GNN. Although semantic graph properties typically do not explicitly affect the graph's structure (R-5), it can be advantageous to leverage them in GNNs since the graph topology could change or specialized architectures might better preserve the original properties in the learned representation. The necessity for this comes from the data's nature and theoretical considerations to learn structures more efficiently or to explicitly model certain constraints or properties of the data structure. The semantic properties listed in Def. 3.2 are a selection from data-motivated characteristies (c.g., bipartite nodes for user-item modcling, complete graphs for relation prediction) and graph theory (e-g-, regular or disconnected graphs, trees). Accordingly, GNNs that integrate some of these properties presented in Tab. 5
Some characteristics are considered more often in graph learning than others. These include, e.g., complete, acyclic, and bipartite graphs since they reflect frequently occurring characteristies of graph applications. contrast, recursive graphs or (poly-)trees are considered explicitly only occasionally. To the best of our knowledge, regular graphs do not play significant role in graph learning.
Complete graphs represent the existence of connection bet each node pair. Standard Message-Passingg GNNs or Convolutional GNNs theoretically capable of handling complete graphs. However, especially in the case of GCNs, the neighborhood of all nodes is considered equally, and thus, the information flow in the graph is inexpressive. Some GNNs have been developed for complete graphs to overcome this problem.
MGCN [Lu et al. 2019), e.g., is specifically designed to predict propertics of molccules represented as a complete graph. The network is a standard Message-Passing Neural Network (MPNN), utilizing node and edge attributes. The erucial innovation is how nodes and edges are embedded. The idea to model quantum interactions between atoms since these influence the overall properties of the molecule. Initially, the atoms of molecule define nodes of complete graph, respecting the number of protons in their nuclei. Then, the edge attributes are const using radial basis function (RBF) layer and processed in hierarchical GCN to weight nodes in the message-passing and hicrarchically aggregating the neighborhood of incrcasing depth. The learned node and edge embeddings are summed across the graph to infer the prediction of molecule properties. Since molecule datasets typically comprise labels only for small fraction of the data and only for smaller molecules, the authors mainly focused on generalizability and transferability between different molecule sizes.
A final node embedding is obtained by executing several convolutions
As can be observed from the table, there are models focusing on bipartite graphs, i.e., graphs that can be divided into two disjoint node sets such that every edge connects node of one set to a node from the other
12 Nodes only appear together with new hyperedges.
18

---

Published in Transactions on Machine Learning Research (03/2023)
set. One example is BGNN (He et al. 2019 which focuses generating suitable representation for such graphs. For this purpose, information across and within the graph's 's two partitions (domains) is aggregated to enable inter-domain message passing, The model is trained in a so-called cascade way, iee, the training of a layer begins after the precoding layer has been fully trained. Thereby, the loss function for the domains is defined layer-wise. Together with global loss, the quality of the resulting node representation measured.
BipGNN (Wang et al. 2020), in contrast, restricts the convolution the propagation between the disjoint node sets. The network encoder produces pairwise embeddings for nodes from the two disjoint sets, and the decoder maps these embeddings to association matrix to perform link prediction between disjoint sets.
In the case of unconnected graphs, the underlying concept of information flow in GNNs may reach its limits. In standard GNNs, subgraphs without a connection to the rest of the graph are processed isolatedly. Thus, small isolated subgraphs may not provide enough structural information to prevent over-smoothing Li et al. (2018) of the GNN. To tackle this problem, the generative graph transformer network (GTN) Yun al. 2019). e-g., aims to identify valuable connections between unconnected nodes the rest of the graph. It enables learning multiple subgraph structures in heterogeneous graph by concatenating graph convolutions on different meta-paths.
Table 5: GNNs using semantic graph properties. The specific semantic properties have been selected due to their rather common appearance in graph data. Since some graph characteristics are considered in more applications or in more popular applications, there exist more GNN models, e.g. bipartite graphs are considered often.
Graph Type
Models
Problem
Data Category
MGCN
complete
graph attribute prediction
quantum chemistry
Lu et al.
2019
r-regular
BipGNN
link-rank prediction
drug repurposing
bipartite
Wang et al.
2020
BGNN
node representation learning
social-/citation networks
He et al.
2019
GTN
graph generation, meta-path generation, node classification
unconnected 13
citation networks, movie genres
Yun et al.
2019
DAGNN
node prediction, longest path prediction
source code, neural architectures, Bayesian networks
acyclic
Thost
& Chen
2021
GenRecN
troes
Sperduti & Starita
graph classification
logic terms
1997)
CTNN
3d surfaces in context of hydrological applications
polytrees
node classification
He et al. 2021
MPNN-R
recursive
node classification
documents in academic networks
Yadati 2020
Hier-GND
hierarchical
image classification
images
Chen al.
2022
Acyelic graphs occur across various domains, such as source code, neural architectures, or logic terms.
DAGNN (Tost & Chen 2021 learns a representation for directed acyclic graphs driven by the partial order
18gince, to the best of knowledge, most of the models do not specify the connectedness, is assumed here that they can handle both connected and uncounected graphs.
14eThe majority GNN models in this survey can handle cycles because they are very common graphs.
19

---

Published in Transactions on Machine Learning Research (03/2023)
over the graph nodes. It is RNN-based saassago-psssing network utilizing attention module to obtain the messages, which are then forwarded through a GRU. A graph representation is obtained by first concatenating the source and target node representations separately, then max-pooling them and concatenating the results.
Particular cases of acyelic graphs are trees, i.a., examined in GenReeN (Sperduti & Starita, 1997) This early work, as mentioned in Sec. 4.1 applies a spatial neighborhood convolution on the out-neighbors of a node. Polytrees also serve as suitable representations for some types of data, such as surface contours of 3D data. As shown in CTNN (He et al. 2021), polytrees can be used to model the evolution of the surface contours at different elevation levels. The model uses a U-Net (Ronneberger et al. 2015 architecture with ChebyNet (Defferrard et al. 2016) and diffusion Graph Convolution (Li et al. 2017 Layers, using graph pooling and unpooling methods for the characteristic unit architecture.
Another model using a U-Net [Ronneberger et al. 2015) architecture is Hier-GNN (Chen et al. 2022), which explores hicrarchical correlations between nodes. For this purpose, specialized pooling and unpooling mothods are explieitly defined to encode hierarchical information. Graph convolutions are then applied among layer in the hierarchy.
Finally, MPNN-R Yadati 2020 has been developed to encode recursive graphs. It is based on G-MPNN Yadati 2020 mentioned in Sec. 4.2 and adapts the message-passinnn passing function for recursive multi-relational
ordered multi-hyyergraphs..
7 Models for Combined Graphs
Arbitrary combinations of graph types can be used to model real-world problems and thus be considered for graph learning purposes. To conclude this work, we give a selected list of graph-type combinat ions used several research fields where GNNs are already established. Therefore, this list is not necessarily complete but gives an insight into further research on GNNs considering combined graph types.
The architectures listed in Tab. G are GNN models specialized for particular combination of graph properties. Some of them use a selected non-Euclidcan space that is assumed to provide better fit for the specific data. GCN (Kipl& & Welling 2017), e.g,, defines a standard spectral graph convolution for simple graphs allowing for one-dimensional edge weights, whereas Hyperbolic GNN (Liu et al. 2019) defines its extension to hyperbolic space. Hyperbolic GNN operates on Riemannian manifolds
16 and independent of the underlying
space. Since every point of a differentiable Riemannian manifold can be approximated by Euclidean space, all functions with trainable parameters are executed in Fuclidean Space. HVGNN (Sun al. 2021a) uses hyperbolic model as well. More precisely, it consists of temporal graph neural network based convolution and attention modules and variational graph auto-encoder in hyperbolic space. A map from time to a hyperbolic space encodes time information to handle time in the convolution process. This way, the aggregation of the features is done in a time-aware neighborhood.
The combined graph structures that make up knowledge graphs represent a common application for GNNs. They can represent all types of attributes, together with heterogeneity and dynamics. Therefore, many different models have been developed. KGIN (Wang al., 2021), e.g., uses an attention mechanism that combines different relations into so-called intents to model the user-item relations. These are subsequently used for user and item embeddings modeled via another attention layer to predict the probability of user adopting an item. A similar use case is approached in SBGNN (Huang et al., 2021), where the two node types of users and items are represented as a bipartite graph connected through signed relations. The model uses message- passsingg scheme, including an atlention mechanism to encode positive and negative links in recommender, voting, and review systems. HetG (Zhang et al., 2019a) processes a similar graph type. The model is designed to embed heterogencous graphs with node and edge attributes of any kind. It generates heterogeneous neighborhood using Random Walk with Restart and applies Bi-LSTM for heterogeneous content embedding. Different types of nodes are then combined via an attention mechanism.
A Riemannian manifold is real and smooth manifold equipped with an inner product each point, of the manifold Lin
et al. 2019).
20

---

Published in Transactions on Machine Learning Research (03/2023)
A particular type of graph that can be useful for several applications is the multiplex graph. It consists of different layers, each with the same set of nodes but different sets of edges within these layers. Inter-layer edges connect the same nodes across different layers. In MXMNet (Zhang et al. 2020a), a two-layer multiplex graph is utilized such that the so-called local layer is generated with the aid of molecular expert knowledge, and the global layer depends on the neighborhood of the local layer. MXMNet applies a message message-passing procodure to each layer scparately and enables communication between these layers by defining an additional cross-layer mapping function.
Multiplex graphs can also be used to model temporal features without explicitly using dynamic graph reprosentation in STGNN (Kapoor et al. 2020). This model is specifically designed to predict the daily new cases of COVID-19 in a particular region based on mobility data. Each layer of the multiplex graph corresponds to a specific period, i.e., day. Nodes represent regions, and relations within these layers describe human mobility between different regions. Edges between the layers are temporal and define node's attribute through time. STGNN processes such graphs using spectral graph convolutions.
Table 6: GNN's for combined graph types. The graph type combinations were selected to cover combinations in fields where the usage of GNNs is already established.
Graph Type
Models
Problem
Data Category
GCN
citation networks, knowledge graphs
Kipl & Welling (011))
node classification
undirected
node-attributed
Hyperbolic GNN
graph classification, node regression
synthetic, molecular, blockchain
Liu et al. 2019)
KGIN
knowledge graph
link prediction
recommender systems
Wang et al. 2021
link prediction, recommendation (inductive) node classification, node clustering
content-associated
HetG
review networks
heterogeneous
Zhang et al.
2019a
MXMNet
multiplex
graph feature prediction
molecules
Zhang al.
2020a
STGNN
spatio-temporal
node attribute prediction
discase sprcading
Kapoor et al.
2020
multi-rclational
SBGNN
recommender, voting, review systems
link sign prediction
bipartite
Huang et al.
2021
bipartite edge-growing in contimuous-time
future uscr-item
JODIE
social media, wiki, music, student actions
interaction prediction, user state change prediction 16
Kumar et al.
2019
undirected
HVGNN
link prediction, node classification
nodo-attributed
social, citation, knowledge
Sun et al.
2021a
edge-dynamic
JODIE Kumar et al. 2019h also processes temporal information, but it directly encodes the dynamics using RNN. It can be considered a particular case of the TGN-Model (Rossi et al. 2020). For node embeddings, it also uses a memory module that can be updated using an RNN. The message- passing function is set to the identity and applicd together with a learnable time projection function. The model is evaluated, c.g., on link prediction between users and items inferred from the distance between the embeddings of a pair of nodes.
16 task is predict interaction will lead state change user, particularly in use cases: predicting will be banned and predicting student will drop-out course.
21

---

Published in Transactions on Machine Learning Research (03/2023)
8 Conclusion and Future Work
This survey provides a fine-grained overview of Graph Neural Networks for graph types of different structural constitutions. To the best of our knowledge, this is the first work to survey which graph types are addressed by published GNNs. We overviewed and defined the most common graph types and properties and the respective GNN models. Moreover, we identified GNN models specialized for specific graph properties and investigated how they handle these. This way, we could relate formal graph properties to the corresponding practical GNN models. Furthermore, we analyzed the architecture of the considered models and grouped them according to the modules they apply, i.e., the type of layer, such as convolutional or recurrent layers. Additionally, we analyzed GNN models concerning dynamics and grouped the models according to the types of dynamics they can process.
Our work allows several conclusions to be drawn and identifies gaps concerning the graph types, propertics, and dynamics that GNN models can handle. First, existing GNN models can, in principle, handle the most common structural graph properties (e.g., attributed, directed, node-heeteroeeneity) for static graphs and hypergraphs. The lack of models for few properties results from the existence of more general models, e.g., there is no GNN model for node- mederoeterogeneous graphs in discrete time, but there is one for fully heterogeneous graphs. Another reason could be a lack of standard graph data sets for such lypes. Furthermore, there are many GNN models which consider graphs in discrete-ting representation. These models cover the most common graph types and properties except for the multiplicity of nodes or edges. A difficulty in handling multiplicity results from the inability of a standard graph's 's adjacency matrix to encode duplicate nodes.
When it comes to the models for graphs in continuous time, it is evident that there are substantial gaps in research on GNNs for most of the graph types compared to the discrete case. In particular, only one model for hypergraphs has been found. Generally, developing GNNs for continuous-time graphs is still a young field of GNN research. Another reason for the small number of graph types covered by models for contimuuustimme graphs could be that such models typically use stochastic point processes to model the dynamic behavior of the graphs. The number of different events increases with the number of dynamic graph properties considered. Since a point process models each event, the model becomes more complex. From the results from Tab. f it can be observed that most events model discrete outputs in continuous time, such as whether there is a new edge. When including attribute dynamics for real-valued attributes, the model must deal with continuous values in continuous time, making the model more computationally intensive.
Most dynamic graphs addressed by GNN models exhibit only specific dynamics, such as strictly growing graphs or dynamic node attributes. GNN models for graphs with dynamics in the edge attribules and the deletion of nodes are scarce. To the best of our knowledge, only one model, MGH[Yan et al., 2020), has been developed to process graphs with all dynamics considered in this work, i.e,, changing node and edge sets as well as changing node and edge attributes. Reasons for this may be the popularity of problems where graphs are growing over time and node deletions are believed not to play a crucial role (as, e.g., in citation networks, recommender systems, data networks) and the difficulties that arise when combining known GNN techniques for dynamic graphs. Considering the time representation of graphs, e.g., GNN techniques for static graphs are usually applied to every graph snapshot and combined with an RNN to capture the dynamics, leading to computationally expensive models.
Finally, existing GNN models have been developed to cover many semantic graph properties or for particular combined graph types dependent on the given data structure, which shows that multiple graph properties can be learned simultancously by GNN models.
To sum up, the research on GNNs for particular graph types has become a hot area in recent years. However, this extensive survey could reveal gaps in graph types, properties, and dynamics that are not yet considered sufficiently in the GNN community.
22

---

Published in Transactions on Machine Learning Research (03/2023)
9
Notation
Table 7: Notation used throughout this work.
natural numbers
No
natural numbers starting 0
real numbers
R
R vector space of dimension k
|a|
absolute value of a real
norm on IR
M
number of elements of a set M
Ø
emply set. set
(
0-D
multiset, i.c., set allowing multiple appearances of entries union of two (multi)sets
disjoint union of two (multi)sets
sub(multi)sct.
x
factor set two sets learnable message function activation function
Φ
sigmoid activation function aggregation
11
concatenation
A
adjacency matrix
Ā
adjacency matrix with self-loops
B
edge degree matrix node degree matrix node degree matrix with self-loops
D
D
E
identity matrix
I
incidence matrix
Laplacian matrix edge weight matrix
W
Author Contributions
All authors contributed equally.
Acknowledgments
The GAIN project is funded by the Ministry of Education and Research Germany (BMBF), under the funding code 01IS20047A, according to the 'Policy for the funding of female junior researchers in Artificial Intelligence'
The authors would like thank Mohamed Hassouna, and Jan Schneegans for the fruitful discussion and corrections of the manuscript.
References
Stephen Abbott. Understanding Analysis, volume Springer, 2001.
23

---

Published in Transactions on Machine Learning Research (03/2023)
James A. Anderson and Edward Rosenfeld. Neurocomputing: Foundations of Research. MIT Press, Cambridge, MA, USA, 1988. ISBN 0262010976.
Song Bai, Feihu Zhang, and Philip HS Torr. Hypergraph convolution and hypergraph attention. Pattern Recognition, 110:107637, 2021.
Sambaran Bandyopadhyay, Kishalay Das, and M Narasimha Murty. Line hypergraph convolution network: Applying graph convolution for hypergraphs. arXiv preprint arXiv:2002.03392, 2020.
Claudio DT Barros, Matheus RF Mendonça, Alex B Vieira, and Artur Ziviani. A survey on embedding dynamic graphs. ACM Computing Surveys (CSUR), 55(1):1-37, 2021. Publisher: ACM New York, NY.
Claude Berge. Graphs and Hypergraphs. 1973.
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. TEEE Signal Processing Magazine, 34(4):18 42, 2017. doi 10.1100.1195SS 22..2.26179.111 MLL.109//MSP2221.2283111
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021. URL https://arxiv: http://www..rg/aab///.....1..
Hongyun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang A comprehensive survey of graph
embedding: Problems, techniques and applications. arXiv:1709.07604 [cs], February 2018. URL http: Maaxiv.org/abs. 1709. 07604 arXiv: 1709.07604.
Cen Chen, Kenli Li, Wei Wei, Joey Tianyi Zhou, and Zeng Zeng. Hierarchical graph neural IEEE Trans. Circuits Syst. Video Technol, ::200 252, 2022. URL
networks for few-shot learning.
doi 10t.0.01//TSSTTT..22. 2021..252222.0009
2021.
Robert J. Cimikowski and Paul Shope. A neural-network algorithm for graph layout problem. IEEE Trans. Neural Networks, 7(2):341-34) 1996. doi 10.1109/72.485670 URL fottp://ddo.org/11 1109/72
485670
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding. IEEE transactions on knowledge and data engineering, 31(5):833 852, 2018. Publisher: IEEE.
Sanjoy Dasgupta. Learning polytrees. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, UAT999, pp. 134-141, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606149.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
Lisa Ehrlinger and Wolfram WöB. Towards a definition of knowledge graphs. SEMANTiCS (Posters, Demos, SuCCESS), 48(1-4):2, 2016.
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In The Thirty-Third AAAT Conference on Artificial Intelligence, AAAT 2019, The Thirty-First. Innovative Applications of Artificial Intelligence Conference, LAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, Jamuary 27 February 1, 2019. pp. 3558 3565. AA Press, 2019. 10.16001609 aaai. v33101 1033301113013333 .33013558 aaai. v33101 33013558
URL ntttps://doi. http:///oioogg/...11 1609/
Fernando Gama, Elvin Tsufi, Geert Teus, and Alejandro Ribeiro. Graphs, convolutions, and neural networks: From graph filters to graph neural networks. IEEE Signal Processing Magazine, 37(6):128-13) 1388 November
2020. ISSN 1558-0792. 10. 00..109//MSP.022.331166 2020.3011133
Ira. M. Gessel and Richard P. Stanley. Algebraic enumeration. Handbook of combinatorics, 2:1021-1061, 1995.
24

---

Published in Transactions on Machine Learning Research (03/2023)
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Procoedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9211-9219) 2019.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: survey. Knowledge-Basee Systems, 151:78 94, 2018. Publisher: Elsevier.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs, 11273
2018. URL http://aaxxiv...abbb./aa////
William L. Hamilton. Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovee. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40(3):52 74, 2017. URL http::/sites.commttt// computter.or//debull. org/debull/ A17sept/p52.1 pdf
Xiaoke Hao, Jie Li, Yingehun Guo, Tao Jiang, and Ming Yu. Hypergraph neural network for skeleton-based based action recognition. IEEE Transactions on Image Processing, 30:2263 2275, 2021. doi 10.11099 TT00//IIP.2222220 2011.3054
Chaoyang Hc, Tian Xie, Yu Rong, Wenbing Huang, Yanfang Li, Junzhou Huang, Xiang Ren, and Cyrus Shahabi. Bipartite graph neural networks for efficient node representation learning. arXiv e-prints, pp. arXiv-1906, 2019.
Wenchong He, Arpan Man Sainju, Zhe Jiang, and Da Yan. Deep neural network for 3d surface segmentation based on contour tree hierarchy. In Carlotta Demeniconi and lan Davidson (eds.), Proceedings of the 2021 SIAM International Conference on Data Mining, SDM 2021, Virtual Event, April 29 - May 1, 2021, pp. 253 261. STAM, 2021. 111001137/1177111177770000
URT httpss://dii org/ 10. 977711.978111117667000
29
Waihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. CoRR, abs/2005.00687, 2020. URL https://arxiv www.arwwiw...raaaao.ooo aaaaabbs/2000 00687
Youpeng Hu, Xunkai Li, Yujie Wang, Yixuan Wu, Yining Zhao, Chenggang Yan, Jian Yin, and Yue Gao. Adaptive hypergraph auto-encoder for relational data clustering. IEEE Transactions on Knowledge and Data Engincering, 2021.
Junjie Huang, Huawei Shen, Qi Cao, Shuchang Tao, and Xueqi Cheng. Signed bipartite graph neural networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 740 749, 2021.
Borja Tbarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. In NewrIPS, 2018.
Vassilis N loannidis, Autonio G Marques, and Georgios B Giannakis. recurrent graph neural network for multi-rclational data. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Specch and Signal Processing (ICASSP), pp. 8157 8161. IEEE, 2019.
Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey. arXiv:2101.1117 [cs]. arXiv: 2101.11174.
February 2022. URL
Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning on continuous-ting dynamic graphs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (cds.), Advances in Neural Information Processing Systems, 2022. URL https:://pperreveer /tteeeeerrieeeeeeeeeeeeee forum NorpaPPAd-N
Woojeong Jin, Meng Qu, Xisen Jin, and Xiang Ren. Recurrent event network: Autoregressive structure inference over temporal knowledge graphs. arXiv preprint arXiv:1904.05530 2019.
25

---

Published in Transactions on Machine Learning Research (03/2023)
Cliff A. Joslyn and Kathleen Nowak. Ubergraphs: A definition of a recursive hypergraph structure. CoRR. abs/1704.05544 2017. URL. http://arxiv http:///aax....orrr//////444. wrtp//a///0...00000000
Amol Kapoor, Xue Ben, Luyang Liu, Bryan Perozzi, Malt Barnes, Martin Blais, and Shawn O'Banion. Examining covid-19 forecasting using spatio-temporal graph neural networks. arXiv preprint arXiv:2007.03113, 2020.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation Learning for Dynamic Graphs: A Survey, Journal of Machine Learning Research, 21(70):1-73, 2020. URL
http:///rrr/rppppp////////111111 html
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. Open net, 2017. URL https: wttp:pparrrrree.ooooooorrreeeee net///rum/ttd SJU4ayYg1
Srijan Kumar, Xikun Zhang, and Jure Leskovee. Prodicting dynamic embodding trajectory temporal interaction networks. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis (eds.), Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1269-1278. ACM, 2019. doi 001444//222500033666
URL https://doi. wwt..o////....///....
Valerio La Gatta, Vincenzo Moscato, Marco Postiglione, and Giancarlo Sperli. An cpidemiological neural network exploiting dynamic graph structured data applied to the covid-19 outbreak. IEEE Transactions on Big Data, 7(1):45-55) 55, 2020.
Jenn-Shiang Lai, Sy- Yen Kuo, and Ing-Y Yi Chen. Neural networks for optimization problems in graph theory. In 1994 IEEE International Symposium on Circuits and Systems, ISCAS 1994, London, England, UK. May 30- June 2, 1994, pp. 269-272. IEEE, 1994. 10/100110///BAAA1144.00000 //doi.org/10 10. 1109/ISCAS. 1994.409570
URL https
John Boaz Lec, Ryan A Rossi, Sungchul Kim, Nesreen K Ahmed, and Eunyce Koh. Attention models in graphs: A survey. ACM Transactions on Knowledge Discovery from Data (TKDD), 13(6): 25, 2019. Publisher: ACM New York, NY, USA.
Qimai Li, Zhichao Han, and Xiao-ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018. doi 10.1099 waai..32i...1100.. URL nattpa://oja aaai http://wwwpppp////aaaatttt/c////
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv:1707.01926, 2017.
Wenlong Liao, Birgitte Bak-Jensen, Jayakrishman Radhakrishna Pillai, Yuelong Wang, and Yusen Wang. A review of graph neural networks and their applications in power systems. Journal of Modern Power Systems and Clean Energy, pp. 1-16, 2021. ISSN 2196-5420. doi 10.3588//P/333332222 Name: Journal of Modern Power Systems and Clean Energy.
Conference
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bun E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL htttps://proceedingss ittp:/eeeediinnnnnuuuiirr..eeeee www.iee..ucpppaeeeeee .
Yunyu Liu, Jianzhu Ma, and Pan Li. Neural higher-order pattern (motif) prediction in temporal networks. arXiv preprint arXiv:2106.06039, 2021.
Chengqiang Lu, Qi Liu, Chao Wang, Zhenya Huang, Peize Lin, and Lixin He. Molecular property prediction: A multilevel quantum interactions modeling perspective. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, TAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence.
26

---

Published in Transactions on Machine Learning Research (03/2023)
EAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pp. 1052-1060) AAAI Press, 2019. doi 10. 1609/ (609//aai.vv aaai.v3330) .3001 1052. URL https://ddi...... org/10. 1609//aa..00
Xiaoyi Luo, Jiaheng Peng, and Jun Liang. Directed hypergraph attention network for traffic forecasting. IET Intelligent Transport Systems, n/a(n/a), 2021. 1ttp://0...044//1222212333
URL https:
//ietresearch.
wiley. wwwpo/////aa//////t//oooooooaaet
Yao Ma, Ziyi Guo, Zhaochun Ren, Eric Zhao, Jiliang Tang, and Dawei Yin. Streaming graph neural networks. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR' 20, pp. 719-728, 2020.
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. Pattern Recognit., 97, 2020. (oi100.016/ 1070000000000 107000 URL https::/abi. 1016// patcog..00000 2019
107000.
Scott McKinncy, Marcin Sicnick, Varun Godbole, Jonathan Godwin, Natasha Antropova, Hutan Ashrafian, Trevor Back, Mary Chesus, Greg Corrado, Ara Darzi, Mozziyar Etemadi, Florencia Garcia-Viene Vicente, Fiona Gilbert, Mark Balling-Browa. Demis Hassabis, Sunny Jansen, Alan Karthikesalingam,, Christopher Kelly, Dominic King, Joseph Ledsam, David Melnick, Hormuz Mostofi, Lily Peng, Joshua Reicher, Bernardino Nomera-Paredes, Richard Sidebottom, Mustafa Suleyman, Daniel Tse, Kenneth Young, Jeffrey De Fauw, and Shravya Shetty. International evaluation of an ai system for breast cancer screening. Nature, 577: 89 94, 12/2020 2020. ISSN 1476-4687. doi
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gauray Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiscrson. Evolvegen: Evolving graph convolutional networks for dynamic graphs. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAII 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, LA 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAT 2020, New York, NY, USA, February 7-12, 2020, pp. 5363-5370. AAAI Press, 2020. URL https: httpp:::/aaat.oo////////nieteoi
haap/AlA//article/vieee
Yun Peng, Byron Choi, and Jianliang Xu. Graph learning for combinatorial oplimization: A survey of state-of-the-art. Data Science and Engineering, 6(2):119- 141, 2021. Publisher: Springer.
Yuxiang Ren, Bo Wang, Jiawei Zhang, and Yi Chang. Adversarial active learning based heterogeneous graph neural network for fake news detection. In 2020 IEEE International Conference Data Mining (ICDM), pp. 452-461, 2020. doi 10. 11110/CCDM50000 2020000000
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pp. 234 241. Springer, 2015.
Emanucle Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Foderico Monti, and Michael M. Bronstein. Temporal graph networks for deep learning on dynamic graphs, 2020. URL https://arxiv.. abs/ 2006.10631
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL http:://ittorrrreppsiorr..
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural eppresentation learning on dynamic graphs via self-attention networks. In James Caverlee, Xia (Ben) Hu, Mounia Lalmas, and Wei Wang (ods.), WSDM '20: The Thirtcenth ACM International Conference on Web Search and Data Mining, Houston, TX, USA, February 3-7, 2020, pp. 519-527. ACM, 2020. 11111.14//333611...0 URL http:://aaii.or//....oooo wttp://////....1//...1.00000
27

---

Published in Transactions on Machine Learning Research (03/2023)
Ryoma Sato. A survey the expressive power of graph neural networks. arXiv:2003.04078 [cs, stat], October 2020. URT. http://arxiv..rr/// wwwgg//gg//..././//o/o 20tpb///000000088..) arXiv: 2003.04078.
Ramit Sawhney, Shivam Agarwal, Arnav Wadhwa, Tyler Derr, and Rajiv Ratn Shah. Stock selection via spatiotemporal hypergraph attention network: A learning to rank approach. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 497-504, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20:61 80, 2009. ISSN 1941-0093.
doi
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolut ional recurrent networks. In Long Cheng, Andrew Chi-Sing Leung, and Seicchi Ozawa (eds.), Neural Information Processing 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13-16, 2018, Procoodings, Part I, volume 11301 of Lecture Notes in Computer Science, pp. 362 373. Springer, 2018. doi 11778-3-030-01167--0
33. CRL https: http://doo.or//////
Hong Shi, Xiaomene Zhang, Shizhong Sun, Lin Liu, and Lin Tang. A survey on bayesian graph neural networks. In 2021 13th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC); pp. 158 161, August 2021. 11111001109/1MMS55211111
Xingjian Shi, Zhourong Chen, Hao Wang, Yan Yeung, Wii-Kin Wong, and Wang-chun Woo. Convolutional Istm network: A machine learning approach for precipitation nowcasting. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (ods.), Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 802 810, 2015. URL httpp::/procceednggs wew.eeeddiinnnn.niis..... neurips cc/ paper/2015/
www.sSbbeeeeea8444 e33a84333 a4dd0445444 Abstract.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 222)002100, 2020. Publisher: IOP Publishing.
David Silver, Thomas Hubert, Julian Schrittwieser, Joannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Gracpel, Timothy Lillicrap, Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 342199)::1 1144, 2018, doi 10.1126 http://iinnecarr.0000 org/ htt///di/ab////// 1121 science. aar6404
URL https: //tp::://www... wwww.science. science
Joakim Skarding, Bogdan Gabrys, and Katarzyna. Musial. Foundations and modelling of dynamic
networks using dynamic graph neural networks: A survey. IEEE Access, 9, 2021. ISSN 2169-3536. arXiv: 2005.07496.
10.11..109/ACCEE... AAL.109//ACCEES22233332222 URL http://arxii. httaaariiv...ogaaaa. aa////bs//00000 07496
Amauri H Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph
networks. In NeurIPS 2022 Workshop: New Frontiers in Graph Learning, 2022. URL htthtttst///oereiiiee
her/fforumiid=22neeknngee
Alessandro Sperduti. Neural networks for processing data structures. In C. Lee Giles and Marco Gori (eds.), ), Adaptive Processing of Sequences and Data Structures, International Summer School on Noural Networks, "E.R. Caianiello', Vietri sul Mare, Salerno, Italy, September 6-13, 1997, Tutorial Lectures, volume 1387 of Lecture Notes in Computer Science, pp. 121-144. Springer, 1997. doi 10.1000/PBP00000330 URL
A Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Trans. Neural Networks, 8(3):714-735, 1997. doi 10.110019772.555210 URL https:://ai.org::
1109/72.572108
Edgar-Philipp Stoffel, Korbinian Schoder, and Hans Jürgen Ohlbach. Applying hicrarchical graphs pedestrian indoor navigation. In Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, pp. 1 1-4, 2008.
28

---

Published in Transactions on Machine Learning Research (03/2023)
Gilbert Strang. Introduction to Linear Algebra, volume 3. Wellesley-Cambridge Press Wellesley, MA, 1993.
Li Sun, Zhongbao Zhang, Jiawei Zhang, Feiyang Wang, Hao Peng, Sen Su, and Philip S Yu. Hyperbolic Variational Graph Neural Network for Modeling Dynamic Graphs. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 35, pp. 4375 4383, 2021a.
Xiangguo Sun, Hongzhi Yin, Bo Liu, Hongxu Chen, Jiuxin Cao, Yingxia Shao, and Nguyen Quoe Viet Hung. Heterogeneous hypergraph embedding for graph classification. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp. 725-733 2021b.
Josephine M. Thomas, Silvia Beddar- Siidar- Alice Moallemy-Ourchh and Rüdiger Nather. Graph type org/abs/2109
expressivity and transformations. CoRR, abx/2210.10078,, 2021. URL 10708
Veronika Thost and Jie Chen. Directed acyclic graph neural networks. In International Conference on Learning Representatious, 2021. URL http://pwrrrrreeeeeeeeooorrrra/a
Loe Hoang Tran and Linh Hoang Tran. Directed hypergraph neural network. CoRR, htss/2008.03622 2020.
URL attps://arxiv. wttp//vvvooooooooooo.ooo hts//bb//20000 03666
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th Internal ional Conference on Machine Learning, ICML, 2017, Sydney. NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 3462 3471. PMLR, 2017. URL http::/prrocedings.no proos/v70//zrived1.....
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In 7th International Conference on Learning Representations, ICLR 2019, New Orlcans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:///oparrereew.ntttooooo
HyePrhR5KX
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https://openrevier wwt./fnrummmm... JXMpikcZ
Xiang Wang, Tinglin Huang, Dingxian Wang, Yancheng Yuan, Zhenguang Liu, Xiangnan Hc, and Tat-Seng Chua. Learning intents behind interactions with knowledge graph for recommendation. In Proceedings of the Web Conference 2021, pp. 878 887, 2021.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip Yu. Heterogeneous graph attention network. In The World Wide Web Conference, pp. 2022 2032, 2019.
Zichen Wang, Mu Zhou, and Corey Arnold. Toward heterogeneous information fusion: Bipartite graph convolutional networks for in silico drug repurposing. Bioinformatics,
1):1525-1533, 2020.
Lingfei Wu, Yu Chen, Kai Shen, Xiaojic Guo, Hanning Gao, Shucheng Li, Jian Pei, and Bo Long. Graph neural networks for natural language processing: A survey. arXiv preprint arXiv:2106.06090 2021.
Shiwen WU, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: A survey. MrXiv:2011.02/10 [os], February 2022. URL. httpp://aaxii..o//abbb//////
arXiv: 2011.02260.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S. Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Tian Xia and Wei-Shinn Ku. Goometric graph representation learning on protein structure prediction. In
Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1873- 1883, 2021.
29

---

Published in Transactions on Machine Learning Research (03/2023)
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In International Conference Learning Representations, 2018.
Naganand Yadati. Neural message passing for multi-relational ordered and recursive hypergraphs. Advances in Neural Information Processing Systems, 33, 2020.
Naganand Yadati, Madhav Nimishakavi, Prateck Yadav, Vikram Nitin, Anand Louis, and Partha P. Talukdar. Hypergen: A new method for training graph convolutional networks on hypergraphs. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché- Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 1520-1520, 2019.
Yichao Yan, Jie Qin, Jiaxin Chen, Li Liu, Fan Zhu, Ying Tai, and Ling Shao. Learning multi-granular hypergraphs for ardeo-based person re-identification. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Luwei Yang, Zhibo Xiao, Wen Jiang, Yi Wei, Yi Hu, and Hao Wang. Dynamic heterogencous graph embodding using hierarchical attentions. Advances in Information Retrieval, 12036:425, 2020.
Jaehyuk Yi and Jinkyoo Park. Hypergraph convolutional recurrent neural network. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 3366-3366 -376, 2020.
Donghan Yu, Chenguang Zhu, Yiming Yang, and Michael Zeng. Jaket: Joint pre-training of knowledge graph and language understanding. arXiv preprint arXiv:2010.00700 2020.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic
survey, arXiv:2012.15445 15445
[cs], March 2021. URL http://aaxxiv.org/abb/
15445 arxiv: 2012.15445.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo Kim. Graph transformer networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buce E. Fox, and R. Garnett (eds.),
Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https http:/pppprr//////aa/a// //proceedings.nenie www. httpap/a.........aaaaaaaaaaaaaaa
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V. Chawla. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 793-803, 2019a.
Shuo Zhang, Yang Liu, and Lei Xie. Molecular mechanics-driven graph neural network with multiplex graph for molecular structures, 2020a. URL httpp://arrav.oog//b////1..../00
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: Algorithms, applications and open challenges. In International Conference Computational Social Networks, pp. 79-91. Springer, 2018
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Macicjewski. Graph convolutional networks: a comprehensive review. Computational Social Networks, 6(1): December 2019b. ISSN 2197- 4314. do:100.188//10010-010000006 com/ him/articles/100 1111/1000-000111-00000------- 019-0
URL httpe:///onpuutttooooooooolltlte sprrikkrrppiinneerpeenn
Number: Publisher: SpringerOpen.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew J. Hirn. Magnet: A neural network for directed graphs. Advances in neural information processing systems, 34:27003 27015, 2021.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 2020b.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li. and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57-81, 2020.
30

---

Published in Transactions on Machine Learning Research (03/2023)
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, (4(13):457-466 2018.
10
Appendix
10.1 Reasons for Selection of the Models per Graph Type
To clarify why each model was chosen for certain graph type, the reasons are listed in Tab Additionally, the critcrion of generality, ic. the applicability of the model not only for a certain domain, is fulfilled by most of the models.
Table 8: Reasons for Selection of the Models per Graph Type. The number of citations taken from google scholar the beginning March 2023.
Model
Reason(s) for Sclection
Models from Tab.
GenRecN (Sperduti Starita,
1997
cited often (783 times), historical importance
MagNet Zhang et al.
(0021)
explicit addressing of graph property
GNN* Scarselli et al.
2009
cited very often (5433 times)
GAT Velickovic el al.
(2018)
cited very often (5705 times), commonly used as basline
CapGNN Xinyi & Chen
20118
cited often (172 times)
WL Morris et al. (2019)
cited often (914 times)
EGNN Gong & Cheng
2019
cited often (195 times)
GRNN Toannidis et al.
2019)
explicit addressing of graph properly
AA-HGNN Ren et al.
2020)
explicit addressing of graph property
HAN Wang et al. (0119)
explicit addressing of graph property
Models from Tab.
NDHGNN Tran & Tran
2020
only model found for graph property
HyPerGCN Yadati et al.
2019
cited often (202 times)
HyperConve Att Bai et al.
(2021
cited often (239 times)
LHCN Bandyopadhyay
al.
(2020)
more straight forward than other models (simplicity)
HGNN Feng et al.
(0019)
cited often (566 times), commonly used baseline only model found for graph property
AHGAE Hu et al.
(2021
HWNN Sun al.
(2021b)
explicit addressing of graph property
G-MPNN Yadati (2020)
explicit addressing of graph property
Models from Tab.
EpiGNN La Gatta et al. (2020)
more straight forward than other models (simplicity) cited often (254 times), commonly used as bascline
DySAT Sankar et al. (2020)
(WD/CD)-GCN Manessi et al. 2020
cited often (229 times), can handle node attributes unlike DySat
GCRN Seo et al. (2018)
cited often (537 times)
DynGEM Goyal et al. (2018)
cited often (322 times)
EvolveGCN Pareja
(2020)
cited often (532 times)
RE-Net Jin et al. (2019)
only model found for graph property
DyHAN Yang et al. (2020)
only model found for graph property
DHAT Luo al. 2021
only model found for graph property
31

---

Published in Transactions on Machine Learning Research (03/2023)
STHAN-SR Sawhney al.
2021
can handle edge attributes unlike HGC-RNN
HGC-RNN Yi & Park
2020
more straight forward than other models (simplicity)
cited often (33 times since 2021), more straight forward than other models (simplicity)
Hyper-GNN Hao et al.
2021
only model found for graph property that handle all dynamics in DTR
MGH Yan et al.
2020
Models from Tob. 4
Know-Evolve Trivedi al
2017
cited often (337 times), commonly used baseline cited often (121 times), more recent and better performing than predessesor Know-Evolve
DyGNN Ma et al.
(2020)
DyRep Trivedi
(201
cited often (301 times), commonly used as baseline recent model
Neur Jin et al
2022
PINT
Souza et al.
(022)
recent model, better performace than TGN
TGN Rossi
2020
cited often (246 times), commonly used baseline only model found for graph property
HIT
Liu et al.
(2021)
Models from Tab.
MGCN Lu et al. (2019)
explicit addressing of graph property explicit addressing of graph property explicit addressing of graph property
BipGNN Wang ct al.
2020)
BGNN He et al.
2019
GTN Yun et al.
2019)
explicit addressing of graph property, cited often times)
explicit addressing of graph property, cited often (51 times since 2021)
DAGNN Thost & Chen 2021
CTNN He et al. (2021)
explicit addressing of graph property explicit addressing of graph property explicit addressing of graph property
MPNN-R Yadati (2020)
Hier-GNN Chen et al.
2022)
Models from Tab.
GCN Kipf & Welling 2017
cited very often (21945 times)
Hyperbolic GNN Liu et al.
2019
cited often (220 times), explicit addressing of graph property cited most (120 times) among models for this graph type, explicit addressing of graph properly
KGIN Wang et al.
(2021)
HetG Zhang et al.
(011aa)
cited often (775 times)
cited most (29 times) among among models for this graph type, explicit addressing of graph property
eXMNet
Zhang et al.
(2020a)
STGNN Kapoor et al.
(020)
often cited (148 times), explicit addressing of graph property explicit addressing of graph property
SBGNN
Huang al.
2021
JODIE
Kumar et al.
2019
often cited (342 times), explicit addressing of graph property explicit addressing of graph property
HVGNN Sun et al.
2021a
32


Reviews:
[{"review_id": "rhLlZ6KkNr", "reviewer": "Reviewer_BMQA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The motivation of the paper is great since it tries to summarize the current research on GNNs from the data perspective. Essentially, various graphs of types and attributes might need a customized GNN design. The survey provides a more comprehensive view compared with existing survey papers.\n\n2. The paper tries to provide a high-level categorization of all kinds of graphs and summarizes representative GNN models for each category. Some model designs are discussed and analyzed.\n\nWeaknesses:\n\n1. The writing of the paper needs significant improvement in terms of language, grammar, and logic. \n\n2. The taxonomy of graphs in Section 2 is a bit unclear and confusing. Although it is mentioned that all basic definitions concerning graph types and their structural properties are taken from Thomas et al. (2021), there is a lack of discussion on why this taxonomy is reasonable and suitable for the discussion of GNNs. For instance, what are the intrinsic differences between \"Structural graphs\" and \"Semantic graphs\"? \n\n3. While the paper mentions that the cited models are selected according to their up-to-dateness, relevance, general applicability, explicit addressing of a specific graph type, and simplicity. It is unclear how these cafeterias are actually carried out. A significant portion of references is from arXiv or some less-known venues while only a small portion of papers is from well-known Machine Learning or Data Mining venues. For instance, to the best of my knowledge, there are many more representative models for directed graphs not being cited while the cited works are less known. \n\n4. The paper summarizes many existing works, but there is a lack of deeper discussion on their advantages, disadvantages, connections, potential, and empirical performance. \n\n5. It would be better to provide a summary of implementations of cited works, i.e., adding links to the table.\n\nOther minor comments:\n1. From what is described in section 3.2.3, the differences between spatial and spectral convolution are unclear. \n\n2. It is suggested to adjust the wording to avoid lines with one a few words. This can make the space compact and save more space for deeper discussions.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a survey of Graph Neural Networks (GNNs) with a focus on different graph types and properties and the GNNs designed for the corresponding categories. In particular, Section 2 and Section 3 introduce the basic knowledge of graphs and GNNs. The following sections (4, 5, 6, and 7) summarize existing GNN research on structural graphs, dynamic graphs, semantic graphs, and combined graphs. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the comments in weakness.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CI0mZOEQhw", "reviewer": "Reviewer_wySu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. Few survey papers focused on the graph topology (semantic) and classified GNNs according to which topology they can handle (Section 6)\n2. The paper not only listed GNNs that support each graph type but also discussed how much and why GNN research for the type was active or not.\n3. The paper is well-organized and clearly written.\n\n**Weaknesses**\n1. There is room for improvement in the description of graph-type definitions.\n2. Contributions 1 and 3 above could be stronger in terms of novelty.\n\n\n**Soundness**\n\n[S-1] I think the above contributions are well-supported.\n\n[S-2] Contribution 1 is discussed in Section 3. Specifically, graph types such as elementary properties (simple graph/hypergraph), temporal properties (static/discrete-time dynamic/continuous-time dynamic graph), and semantic properties (e.g., bipartite/complete.) This paper considered graph types for each property, such as undirected/directed, node-/edge- attributed, and node-/edge- heterogeneous. In addition, special examples of their combinations were discussed, such as knowledge graphs, multi-relational graphs, and multiplex graphs. These definitions are reasonable, although there are some minor suggestions (see Requested Changes).\n\n\n[S-3] Contribution 2 is discussed in Sections 4--7: Section 4 for simple graphs and hypergraphs, Section 5 for static and dynamic graphs, Section 6 for graphs with semantic properties, and Section 7 for combined graphs. I am afraid I have yet to be able to check all GNN models this paper referred to. However, as far as I know, there were no major errors in the paper's classification of GNNs.\n\n[S-4] Contribution 3 is discussed in Section 3.2, although it is not explicitly stated in the text. Since the contents mostly relied on Bronstein et al. (2021), this part is not the contribution of this paper.\n\n[S-5] Contribution 4 is discussed in Section 8. I agree that for node-heterogeneous static graphs, graphs with duplicated nodes/edges, and continuous-time dynamic graphs, few GNNs support these graph types. Also, the reasons for this phenomenon were reasonable.\n\n**Novelty and significance**\n\n[N-1] For Contribution 1, giving mathematical definitions of the graph types was preferred because the definitions of these graph types often vary from paper to paper. It certainly increased the readability of the paper. On the other hand, the graph types were not new in themselves. Also, this unification of terminology was mainly for the preparation of the following sections (especially, Contribution 2). Therefore, novelty is limited on its own. Nevertheless, this classification of the graph types serves as a foundation on which subsequent studies will be developed.\n\n[N-2] For Contribution 2, I agree with the authors' claim that although there were many GNN surveys for individual graph types (or some of them), few studies comprehensively classified them based on graph types. In addition, surveys of GNNs focusing on semantics are rare. From these points, I think we can recognize the novelty in this respect.\n\n[N-3] For Contribution 3, since the discussion follows that of Bronstein et al. (2021), I do not think this part is novel.\n\n[N-4] For Contribution 4, the discussion is novel. To the best of my knowledge, little literature has analyzed the relationship between graph types and the amount of GNNs models that supported them. However, I have several questions regarding the discussion on continuous dynamic graphs (see Requested Changes).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is a survey that categorized existing GNNs according to what graph types they could handle. First, they gave mathematical definitions of various graph types and basic GNN architectures. Then, for each graph type, they gave representative GNNs that could handle it. Based on these classifications, the paper identified graph types that many GNNs supported and ones that few GNNs supported and discussed the reasons for the differences.\n\nAccording to the authors, the contributions of this paper are as follows (P2, Section 1):\n1. gave a comprehensive definition of the various graph types\n2. classified existing GNNs by graph types they can handle\n3. related GNNs to each other based on their architectures\n4. identified graph types that current GNN research is missing", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "[R-1] P1, Section 1: ,,structure'' -> I do not think using such quotations in English papers is common. \"structure\" or $\\textit{structure}$ are more suitable.\n\n[R-2] P3, Section 3.1:\n\n>In this sense, a directed hypergraph is a directed graph that simultaneously is a hypergraph\n\nIn Definition 3.1, hypergraphs are described as elementary. However, this sentence described them as a composition of elementary objects. Therefore, they need to look more consistent.\n\n[R-3] P4, Figure 1: I would like to confirm the source of the dog image.\n\n[R-4] P5, Definition 3.3: In the definition of growing, $\\mathcal{E}\\_i \\subseteq \\mathcal{E}\\_{i+1}$ implicitly assumed $\\mathcal{V}\\_i \\subseteq \\mathcal{V}\\_{i+1}$. Therefore, it is weird that these conditions were connected by the \"or\" expression. The same is true for the definition of shrinking.\n\n[R-5] P6, Definition 3.6: I would like to clarify how the paper used the following terms: structure, topology, and semantics. It looks strange to call graph properties such as complete, regular, bipartite, and so on \"semantic .\" Also, I could not understand the following sentence in P18:\n> Although semantic graph properties typically do not explicitly affect the graph's topology, [...]\n\nI want to know what the authors intended to mean by a graph's topology -- I think that the properties such as complete are something that I imagine the topology of the graph:\n\n[R-6] P6, Definition 3.6: 7. recursive and 10. hyperbolic were not well defined. Therefore, it is difficult to understand these concepts from these descriptions alone. I suggest the authors guide the readers to the reference therein.\n\n[R-7] P6, Definition 3.6, 8: Edges in $H$ correspond to ... -> $G$\n\n[R-8] P7, Definition 3.7, 4: The notations $v\\in e$ in 1 and $e\\subseteq \\mathcal{V}$ implied that the graph is interpreted as a hypergraph. It is better to state this explicitly.\n\n[R-9] P7, Definition 3.7, 7: random -> randomly\n\n[R-10] P7, Definition 3.7, 8: It would be difficult for someone unfamiliar with the concept of metapaths to understand its meaning from this definition alone. It is preferable to provide appropriate definitions or references.\n\n[R-11] P7, Definition 3.7, 1: indegree -> in-degree\n\n[R-12] P8, Eq. (2): Strictly speaking, GAT cannot be formulated in the form Eq. (2). $\\mathrm{att}$ corresponds to $a_{ij}$ of an equation in P.9. However this function depends not only on $x_u$ and $x_v$ but also on all $x_i$'s for $i\\in \\mathcal{N}(v)$. Nevertheless, it would be too complicated to describe this in a rigorous mathematical manner. Therefore, I think it is sufficient to explain it as a supplement to Eq. (2).\n\n[R-13] P9, Section 3.2.4: I think it is better to use a more special character to denote the set of real numbers (e.g., $\\mathbb{R}$) \n\n[R-14] P9, Section 3.2.4: $\\boldsymbol{X}$ -> $\\boldsymbol{X}^{(0)}$\n\n[R-15] P10, Section 4.1:\n> The number of GNNs for simple graphs [...], so the following table does not list all of them [...] \n \nI think it is better to write explicitly which table this sentence refers to (Table 1?). The same applies to Table 2 in Section 4.2.\n\n[R-16] P10, Section 4.1: The authors referred to GenRecN as an example of GNN for directed edges. Certainly, this paper has 723 citations (google scholar, 2023/1/14) and is a very important study. However, this paper was published in 1997 and is not positioned in the GNN studies starting from the late 2000s. Since one of the criteria for selecting GNN models in this paper is that they are relatively new, I would recommend mentioning other models, such as DimeNet [1]?\n\n[R-17] P10, Section 4.1: Add reference to HAN.\n\n[R-18] P13, Section 5: [...], Def. 3.4 The first [...] -> [...] Def. 3.4 The first [...] -> [...]\n\n[R-19] P13, Section 5 and P16, Section 5.2: This paper explained that continuous-time graphs/GNNs were more compact than discrete-time graphs/GNNs. However, I think this is not a matter of discreteness or continuity of dynamic graphs. Rather, it is a matter of representation of graphs. There are two ways to represent a dynamic graph: taking a snapshot of graphs at each time step or saving the changes of graphs. The latter is expected to be more compact representations. While discrete-time graphs can take both approaches, continuous-time graphs can only take the latter approach. Therefore, a compact representation is not an advantage of the continuous-time graph but rather an advantage of the representation method.\n\n[R-20] P18, Section 6: Over-smoothing is a technical term with special meaning in the context of GNNs, so a reference should be provided, e.g., [2].\n\n[R-21] P21, Section 8: Moreover, [...] how they handle these. -> them.\n\n[1] https://openreview.net/forum?id=B1eWbxStPH\n\n[2] https://ojs.aaai.org/index.php/AAAI/article/view/11604", "broader_impact_concerns": "I have no major concerns about broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4BOxffK7yJ", "reviewer": "Reviewer_4uat", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths \n\noverall, I believe this survey can benefit the graph representation learning community through its systematic analysis of graph types and models. Overall, I would recommend acceptance with some edits required as listed in the weakness and request change section. I will first list the strengths below: \n\n1. This survey systematically organizes different graph types and pointed out related GNN models to each type\n\n2. The selection criteria for the inclusion of a given model is clearly discussed and the presentation of the survey overall is quite clear\n\n3. the discussion around which areas lack GNN models are beneficial for the community and can be a guide for further future research\n\n* Weaknesses\n\nThere are a few weaknesses and suggestions that the authors should improve upon:\n\n1.  One important consideration of applying ML models on a given data type is scalability. Recently there is an increasing amount of work on scalable GNNs[1]. To improve the usefulness of the survey, clearly listing the time complexity for each model in the tables would help readers understand the scalability aspect. This can also facilitate future research especially if existing models are expensive in complexity.\n\n2. The performance of a given model on a graph type should also be a selection criteria for model inclusion as it will point readers to the state-of-the-art model (as of the writing of the paper). \n\n3. There is a large amount of recent work designing GNNs for continuous time dynamic graphs. The statement such as \"the small number of models for continuous-time graphs\" on page 22 should be reconsidered. I also hope the authors would include some of these recent papers and update the section on continuous-time dynamic graphs.  Some recent work include [2],[3],[4],[5]. In particular, [3] is one of the first work to design methods for signed continuous time dynamic graphs and should be included in the survey. \n\n\nReferences:\n\n[1]. Ding et al., Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity, NeurIPS 2022\n\n[2]. Luo et al., Neighborhood-aware Scalable Temporal Network Representation Learning, LOG 2022 Conference\n\n[3]. Raghavendra et al., Signed Link Representation in Continuous-Time Dynamic Signed Networks\n\n[4]. Jin et al., Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs, NeurIPS 2022\n\n[5]. Souza et al., Provably expressive temporal graph networks, NeurIPS 2022\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "With the increased popularity of GNN based approaches on data from different domains, the range of GNN models have grown significantly. This survey aims to examine different graph types and point out corresponding GNN models designed for such types. In addition, this work also points out graph types where there is a lack of GNN models. This survey provides a roadmap for novel and existing researchers working with specific types of graph data to identify relevant GNN models in the literature. \n\nThe authors also clearly listed the criterias for including specific work in this survey. These criterias are 1). Up-to-dateness of the model, 2). relevance of the model, 3). the generality of the model, 4). explicitness in addressing a given graph property and 5). simplicity of the model and the priority of selection is in the same order. The criterias help reader understand the significance of the selected model. \n\nLastly, I believe this survey can act as a guide for the GNN community to develop more models in areas which lacks GNN models and facilitate future research. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* suggestions and adjustments\n\n1. following weakness 1, I believe adding the discussion on time complexity for each included model would strengthen the work but wouldn't be critical for my acceptance recommendation\n\n2. following weakness 2, I think a discussion on the performance of the models selected would be useful but again it would mostly strengthen the work\n\n3. following weakness 3, **I would request the authors to update the section on continuous-time dynamic graphs** with the references I included in mind. This is important towards my recommendation of acceptance as it will improve the Up-to-dateness of the survey on this section. \n\n* minor suggestions and edits \n\nPlease update the write-up based on these minor suggestions, it wouldn't change my recommendation but it is very important for the clarity of the paper. \n\n1. in introduction page 1 \"or so-called \"structures\"  and on last line page 1  \"solar power plants\". Most quotation marks are formatted incorrectly in the paper, please check and update all quotation marks\n\n2. \"Remark. All combined static graphs can also be dynamic\" on page 6. Does it mean that all types of static graph can also be dynamic? if so, this sentence was not clear on it.\n\n3. \"However, the continuous-time approach is much more compact in its representation but requires a local evaluation of the graph.\"  It is unclear what \"a local evaluation\" means.\n", "broader_impact_concerns": "There is no concern of ethical implications of the work to my knowledge as it is a survey paper examining existing work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two of the reviewers recommended to accept the paper and agreed that the manuscript was technically correct and relevant to the 
TMLR community, especially to researchers working on graph machine learning. This survey offers an overview of different graph types and  models to tackle ML tasks involving such graphs. 

The 3rd reviewer was leaning toward rejection mainly for two reasons: (i) they questioned the choice of references by the authors and asked to select more high-quality and representative references (ii) lack of discussion on their connections, advantages, disadvantages, potential, limitations, and future development. 

The authors uploaded a last revision appending a table to the paper explaining the choice of each of the models they chose to refer to in the survey. They also argued that "*We do not aim to provide an extensive analysis of all available models for each graph type. Instead, we focus on identifying which graph types are currently covered by existing models. Therefore, we think that discussing multiple models for each graph type is beyond the scope of this paper.* " 

I believe that the addition of the table addresses concern (i) and I think it is reasonable that fully addressing (ii) goes beyond the scope and objective of the paper.

I thus decided to accept the manuscript, I think this will be a useful reference for the graph learning community. 

Here are a couple of minor points to address in the last revision: 

- Unless I missed it, I think Table 7 is not referenced anywhere in the main paper. 

- Def 3.2: 

1) the notation f_i : x \to 0 seems ambiguous to me, maybe consider an alternative notation, e.g. f_i : x \to \{0\} would be technically correct, or f_i(x) = \{0\}.

2) "All multigraphs are written as the set Gm": I recommend using the alternative phrasing " The set of all multigraphs  is denoted as Gm" (as it was done in 4))

4) remove the "-" after "node"

- Def 3.3: 1) "notion" should be "notation"

- Def 3.7: 
1) remove "(R11)"
2) where \tilde{A} **is** the adjacency


Decision: Accept (poster)