Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings
Authors: Nurudin Alvarez-Gonzalez
Andreas Kaltenbrunner
Vicenç Gómez
Venue: Accepted by TMLR ()

Abstract: We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features or extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP-GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match or improve previous baselines on expressivity, graph classification, graph regression, and proximity tasks---while reducing memory usage by 18.1x in certain real-world settings.

Published in Transactions on Machine Learning Research (04/2024)
Improving Subgraph-GNNS via Edge-Level Ego-Network Encodings
Nurudin Gonzaz-Gonzaaez Universitat Pompeu Fabro
nuralgon&gmail.commm com com
Andreas Kaltenbrunner
gnttenbrrunnerr@@mail.comm
Universitat Oberta de Catalunya ISI Poundation Turin
Vicenç Gómez
vicen.gomezZuugf.co
Universilat Pompeu Fabro
Reviewed on OpenReview: https: //ppr/////eervveee.. net/ forum? id= NOScOKYOAH
Abstract
We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP- GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match or improve previous basclines on expressivity, graph classification, graph regression, and proximily tasks while reducing memory usage by 18.1 certain real-world settings.
1 Introduction
Neural graph architectures the current standard for learning from graph data. Those methods automat- ically learn representations of nodes, edges, graphs in data-driven and end-to-end way. Message Passing Graph Neural Networks (MP-GNNs) are the most common model for learning on graphs. MP-GNNs process the input graph (data) with a computational graph (model) to learn useful representations through message passing between direct neighbors in the input graph. This framework facilitates the theoretical analysis of MP-GNNs (e.g., in terms of their expressive power (Xu et al.) 2019). or characterizing issues such as over-squashing (Alon & Yahav 2021) or over-smoothing (Oono & Suzuki 2022
The idea of decoupling the imput graph from the computational graph is the basis of leading- learning approaches, such as Sub-graph GNNs (Zhao et al. 2022
Abboud et al. 2022 Frasca et al. 2022 Mitton & 2022), or Graph Transform-
Murthy-Smith 2023). perturbation methods (Papp et al. 2021 Dwivedi et al.
ers Yun et al. 2019 Ying et al. 2021 Rampášck et al. 2022 Kim et al. 2022
These methods extend the
message-passinng mechanism more general structures induced by the graph, beyond direct neighbors for example between the nearest neighbours of a node at given depth (cgo-networks)) This fiexibility extends the expressive power of MP-GNNs, at the cost of increased compulational footprint and departure of the inductive bias contained in the input graph, which must be learned again.
In this work, we present an alternative to previous pure learning approaches. Rather than learning on sub- graphs, we introduce a systematic ic procedure to generate a pool of structural features (an encoding) which can subsequently be integrated into MP-GNNs. Similar approaches have been proposed recently (Bourissas ct al. 2023 Alvarez-Gonzalez et al. 2022). Crucially, our proposed features capture information at the edge- level, including signals contained in the two ego-networks of adjacent nodes in the input graph. We call this encoding ELENE, for Edge-Level Ego-Network Encodings. The benefits of such representation diverse:

---

Published in Transactions on Machine Learning Research (04/2024)
The encodings interpretable and amenable for theoretical analysis, they efficiently computable pre-processing step, and finally, they reach comparable performance with state-of-the-ari learning methods.
As an illustrative example, consider Strongly Regular Graphs (SRGs). They are known to be indistinguishable
by node- based sub-graph GNNs (Balcilar et al. 2021 Morris et al. 2023 Papp & Wattenhofer 2022 Zhao
Rook and Shrikhande graphs in ig. We theoretically show that ELENE is expressive node-only sub- sub-graph GNNs, and expressive
et 2022 Frasca et al., 2022), as exemplified by the non-isomorphic
enough to differentiate certain classes of SRGs like those in Fig.
(a) Rook Graph.
(b) Shrikhande Graph.
Figure 1: Expressive power is typically analyzed in terms of the families of non-isomorphic graphs that models fail to distinguish: 4 x Rook (a) and Shrikhande (b) graphs are indistinguishable by node-only sub-graph GNNs (Frasca et al. 2022
Another example of challenging benchmark is the h-Proximity task (shown in Fig. which requires the ability to capture graph propertics that depend both the graph structure (shortest path distances) and node attributes (colors) (Abboud et al. 2022). In this case, enriched (learnable) MP-GNN with ELENE features called ELENE-L outperforms current baselines. In real-world benchmarks, ELENE-L matches the performance state-of-tho-art learning methods at significantly lower momory costs, as we show experimen- tally
The paper is organized as follows. S3 defines and motivates ÉLENE. $4 introduces ELENE-L, describes
related work and [6 analyzes expressivity. Finally, 37 evaluates our methods in four benchmarks and summarizes results.
(a) Positive graph.
(b) Negative graph.
Figure 2: h-Proximity binary classification task-A pair positive (a) and negative (b) 1-Proximity graph examples. An h-P Prooiiiiiyy graph is positive if all red nodes have at most 2 blue neighbors up to distance h. and negative otherwise.
2

---

Published in Transactions on Machine Learning Research (04/2024)
2 Notation and Definitions
In this work, G = (V, denotes a graph with n = [V] and m = [E]. (a(u, v) is the shortest path length between u, v. E in G. de(v) is the degree of e in G and we use daxx for the maximum degree over all nodes in G. Double brackets {[-B denote multi-sets while U and N. respectively, indicate set and multi-set union and intersection. We use short-hand x' notation signify æ is contained times, where y = fx B reads "I appears times in y".
We use Sth = (V+ E+) S G' for the k-depth induced ego-network sub-graph of G centered on (abbreviated S in equations). We denote the maximum degree over all nodes in S by df Likewise, we use (u.e) = (V* a nV+ e N to denote the intersection of ego-networks across edge (u, v). Feature vectors are shown in bold, as X2 for node v, ((a,)) for edge (u, v),, we denote vector concatenation by I, and the Hadamard product by o. Finally, we represent a learnable embedding of discrete input, e.g., degree or distance signals Emb(-), and learnable weight matrix as W.
3 Defining ELENE
In this section, we first present the proposed edge-level encodings and then illustrate their expressive power.
3.1
Constructing an Edge-Level Ego-Network Encoding
The main idea behind ELENE encodings is to capture higher-order interactions that go beyond the node- centric perspective used by MP-GNNs. We look at the structure resulting not only from the ego-network of every node, but also from the combination of two ego-networks of adjacent nodes in the input graph, and design pool of features based on that structure.
Consider the k-depth (k: 1) ego-network S surrounding node v. We may ask: how many edges of neighbor of reach nodes that are 1-hop closer to c, al the same distance u, or 1-hop farther from v The proposed ELENE encodings elaborate on this idea to capture interactions between nodes and edges in ego-network sub-graphs.
More formally, consider a node u contained in St and let ds(ulv) count the edges from u to nodes at a distance (s) + p of n, p E (-1,0,+1}:
dg (ulv) (u,w) w) Ek, Vw V w) (s( v) +pp
The degree of node decomposes the sum of these relative degrees corresponding to these three different subsets of neighbors of u:
ds(u) (d) (wlo) + d (ulv) + d5 (ulo).
(left) shows example graph, with all nodes labeled with their degrec and colored according to the distance to the root node of the ego network, in this case, the node in green. The plot on the right shows a degree triplet for each node, which counts the relative degrees, or edges closer and further to the root (1st and 3rd components), together with the individual degree (2ud component).
Fig. 3
Leveraging relative degrees yields ELENE, an ego-network encoding as a multi-set of quadruplets counting all instances of distance and degree triplets in sub-graph S:
= ((s(u v), oe (ulp), de (u/v)) Vuev D.
We can construct an Edge (ED) Centric encoding analogous to the Node (ND) Centric encoding of Eq. 1 by also encoding edge-wise sub-graph intersections for edge (u, u) as eQu.v and counting quadruplets across sk..., (n.n) with distances to both u and v. Using ED or ND encodings leads to different expressive power, as we show formally in 3 In both cases, App. C shows that ELENE encodings are permutation invariant the node level and equivariant at the graph level.
3

---

Published in Transactions on Machine Learning Research (04/2024)
3
2
1, 3, 2
2, 2,
4
2
3,
1, 2
2,
3
3
3,
2, 3,
Node Degrees
Degree Triplets
Figure 3: Example graph (right) and corresponding (left) degree triplets for nodes the 2-hop ego-network rooted on the green node. The dashed blue node has one edge to the 0-hop root (d = 1), degree of 4, and two edges 2-hops from the root (d = 2, red), so its degree triplet (1, 4, 2).
3.2 Illustrating ELENE
To illustrate ELENE, we focus on Strongly Regular graphs. An n-vertex graph d-regular if all n nodes have degree d, ie., u V,dg(v) d. An n-vertex d-regular graph said be Strongly Regular if there cxists A, μ N such that every two adjacent nodes have À neighbors in common, and every two non- adjacent nodes have neighbors in common. We denote Strongly Regular Graphs as SRG(n, d, A,) Strongly Regular graphs with equal parameters are indistinguishable by the 1-WL (Weisfeiler & Leman 1968) test a
classic graph algorithm known to distinguish graphs that are not isomorphic with high probability (Babai & Kucera 1 -nnd its more powerful = 3-WL variant (Arvind et al. 2020: Balcilar et al. 2021 whose ability distinguish graphs has been shown be the expressivily upper-bound for node-only Sub-graph
GNNs [Bevilaquua et al. [2022] Frasca al.] [022 Zhao al. 2022 A natural question follows: what structural information is sufficient to distinguish SRGs!
6
5
13
13
16
16
16
8
13
13
16
(a) x Rook Graph.
(b) Shrikhande Graph.
Figure The Rook (a) and Shrikhande (b) graphs are indistinguishable by 3-WL as SRGs with
parameters SRC(16, 2, {Arvind et al.) 2020: Frasca et. al.] 2022. ELENE (ND, top sub-graphs) is also unable to distinguish the graphs, while ELENE ED, bottom sub-graphs) counts different numbers of edges.

---

Published in Transactions on Machine Learning Research (04/2024)
we show the 1-depth ego-networks S for the purple vertices labeled with '1' with its 1-hop neighbors colored in red (top smaller sub-graphs We represent both graphs in terms of = 16 equal sub-graphs (one per node), analyzing whether the sub-graph pairs can be distinguished. Both sub-graphs have the same number of nodes (7), edges (12), and matching degree multisets ft3.. 6 Furthermore, by coloring the edges as connected to the ego-net rool (in green) or connecting adjacent neighbors of the root (in orange), the count of edge colors also matches. The Node-Centric (ND) ELENE encoding, as shown in Eg. I corresponds such coloring and is thus unable to distinguish the pair of graphs. In [SG we formally prove this upper bound for ELENE (ND), which coincides with the expressive power of node-based Sub-graph GNNs.
In Fig. 4
In contrast, if we consider the 1-hop common neighbors (in blue) of adjacent nodes labeled 'I' and '2', the intersecting sub-graphs are distinguishable (bottom smaller sub-graphs). Indeed, the mumber of edges differs between the x 4 Rook graph (6 edges) and the Shrikhande's graph (5 edges). This corresponds to Edgo-Centric ELENE (ED), and illustrates it has more expressive power than the Nodo-Centin (ND) one.
3.3 Computational Complexity
The ELENE encoding for a single node e requires traversing all the edges in the ego-network &.. This can be computed via Breadth-First Search (BFS) bounded by depth k, which has worst-case complexity (d If k is greater than the diameter in the graph, ELENE must traverse all m edges for the ego-networks with each node as the root. Encoding the entire graph thus has time complexity O(n minfm, d=ax)) }). Note that the more expressive edge-centric implementation requires executing the BFS from both nodes alongside an edge, with asymptotically no additional cost.
ELENE is best suited for sparse graphs, where dasx < n. For fully connected graphs, m - -E = n (n 1)/2 which results in time complexity O(n²), matching the computational worst-case complexity of GNN- AK Zhao et al. (2022). NGNNs Zhang & Li (2021). SUN Frasca et al. (2022), ESAN Bevilacqua et al. (2022), or SPEN Mitton & Murray-Smith (023)..
In terms of memory, ELENE encodings require sparse 3 (A + 1) (daex + 1) component vector for each node e E V to represent the multi-sct of quadruplets in Eq. 1 Accordingly, each entry holds the count of observed relative degrees at each distance from v. In App. A. we describe a BFS implementation that produces a mapping of each ELENE encoding quadruplet to its frequency, and can be parallelized over p processors yiclding On min (m, dh 3/p) time complexity.
4 Learning with ELENE: ELENE-L
We now introduce two approaches for leveraging ELENE encodings in practical learning settings a simple concatenation of ELENE over network attributes, and fully learnable variant called ELENE-L that updates node and edge representations during the learning process. The first approach represents ELENE multi-as sparse vectors containing frequencics of cach quadruple q q-which can be attributes concatenated to x, X(u,u) if processing et or e "(,,,)'
ELENE - Ko =e(o)(())=)
(2)
where f(q) is an indexing function mapping each unique quadruplet to an index in the sparse vector.
The concatenation approach is the most memory efficient, using only as much memory as the encodings themselves, and can be computed once and reused during training or inference. Furthermore, this approach is directly applicable to any downstream learning model e.g., an MP-GNN, without changing its architecture.
Certain tasks, however, require structural information within the sub-graph to be combined with node edge allvibules during learning. One example are h- i-Proximily lasks, which require joint representations that integrate the ELENE encodings with attributes and structure.
Note that for these two graphs, any node will have matching ego-networks regardless of their label see proof for Theo.
5

---

Published in Transactions on Machine Learning Research (04/2024)
ELENE-L addresses the limitations of concatenating ELENE with node and edge attributes by learning over both structures and aldribules at once. ELENE-T, learns non-linear functions (Ø; e.g. Dense Neural Network DNN) to represent nodes, edges, and Node or Sedge-Centric sub-graphs by representing u in S via a learnable function n
(u/v)))) = Pna Xx x Emb(ulu))),
(3)
where xf, and x are features of u and v at timo-step (i.c. after layers, such that 0 are 'input' features), and Emb(u/v) is learnable embedding of ELENE encodings which we describe in $4.1 As with ELENE, we produce learnable representation of an edge (u, w) in St via learnable Dea:
(u, w/v) Ded (
|
C x Emb(u, (u, w/v))
The representation of the Node Centric net-nkk root at time is learnable 4xD applied over the aggregation every node and edge in the sub-graph given a pooling function (E)
v
( PuD
x
Σ
D'
(ul(())))
Σ
(d w(w)
(4)
Similarly, the Edge- Centric representation for edge (u, v) at time is a learnable PeD consuming the aggre- gation over ego-networks containing the edge, as shown in Fig. 5
Vi (uie)
1% (u, v) PED
Σ
T (u, olue)
Node and edge representations update via learnable parameter y gating the flow of ELENE updates:
x ++1 = x + nmo (v))
(6)
We follow the same update-rule at the edge level:
1+1 (u,0)
= X (1,w)) + YEo D (u, w).
(7)
We may use x and x directly in the downstream task, or as inputs into an MP-GNN layer during learning boosting its expressivity. We follow the latter approach in this work.
W3
u
u
WA
W1
u
W
Figure 5: k-depth ego-network intersoction following Eq. for the green edge. The ego-networks of u and v (yellow (left) and purple (center) respectively), intersect on five nodes around (u, e) (dotted, right). We show Dズ= {u, v, Wi, W2, W3, W4, ws} (right), indicating nodes reachable in 0 or 1-hops, exactly 1-hop or or 2-hops from and v.
(a,0)
2e compress notation using the output of 4 at step

---

Published in Transactions on Machine Learning Research (04/2024)
4.1 Defining ELENE-L Embeddings
The representations in Eq. and Eq. leverage attributes and ELENE encodings through Emb(ulv) and Emb(u, w/o). To define ELENE-L, embeddings, three hyper-parameters determine the shapes of embedding matrices: w, the length of the embedding vectors; the max. degree to be encoded (by default, daax); and k the maximum distance to be encoded (i.e., the ego-network depth). For the quadruplet. of we abbreviate:
Qu = (lu, dua Lu. d - (ls(u, v), d (ulv), ds(u), dg (ulo))
defined in Eq. and jointly embed distance and relative degrees. The embedding Emb(u/c) of u in S is given by:
Lus du de. d') (wlad (H.
w W (Lu
Emb
(h..d))
(8)
where Wind W2nd and W E RSww are three node embedding matrices with == (p+1) (k + 1) entries-ont for each distance and relative degree pair. A visual representation of the attributes and ELENE encodings of u is shown in Fig.
To embed edge (u, w) in St we use the quadruplets of and w, 9u and Tws and increase the granularity of distances to capture the relative direction of the edge, following Fig. 4
8wn lu Lw + 1E {0, 1,2).
We embed (u, w) in a permutation-invariant manner, summing embeddings bidirectionally so Emb(u, w/u) = Emb(w; u/v):
Emb(u (u, w/v) (wledd (bo
2dd (u.bumedd d2)
W33,d (
( led (1s dl
2 2,ed (bu RR
3,ed Curbba
(9)
Wl.ad W2.ed and Wid.ed E Rxx are edge-level embedding matrices with 3x more entries to represent the three possible values of 8mw-
2
1, 1, 2
2, 2, 0
2
0,
2
1, 0
1,
2, 3,
(+) Sk
Node Features xu, Xx
Distance, ss (u, v)
Rel. Degree, d
(u, v)
t nd (ulv) = Ind (x
x
Emb
2
1, 2, 0
Figure 6: ELENE-L encoding of in the & 2 ego-network of The representation contains the feature vectors of both nodes (x, and xu, left), the distance information of to (2, center) and the relative degree information (11,2, 0), right).

---

Published in Transactions on Machine Learning Research (04/2024)
5 Related Work
In this section, we connect related work with ELENE encodings and the practical applications of ELENE and ELENE-L in [4 Per [1 the expressivity of MP-GNNs is often studied through the 1-WL test and its
more powerful k- WL variants. Despite great successes in many domains (Duvenaud et al. 2015 Battaglia
et al. 2016; Gilmer et al. 2017 Ying et al. 2018), the GIN architecture (Xu et al., 2019) showed that
one-hop MP-GNNs are at most as expressive as 1-WL. This increased interest in expressive power within the community in the formal study of MP-GNNs (Papp & Wattenholer 2022), and to boost message- passing
with spectral (Balcilar et al.) 2021), positional (You et al. 2019 Li et al. 2020 Abboud et al.) 2022)
path-level (Eliasof ct al. 2022 Michel ct al. 2023), sub-graph (Nikolentzos et al. 2020; Zhang & Li 2021
Bevilacqua et al.] 2022 Frasca et al.) 2022 Mitton & MMMuray-Smiii Smith 2023), structural signals (Morris et al.
2019 Bodnar et al. 2021). ), or their combination (Ying et al.) 2021 Zhao et al. 2022 Dwivedi et al. 2022
Rampásek et al. 2022). We now discuss the theoretical ability of models to express certain computations
expressivity in the abstract-ant empirical performance and architectures of graph learning methods.
Exxresssvvty. The most common framework to study expressivity are the k-Wl, tests and its vari- ants (Morris al., 2019). Recent research has also focused on other perspectives, such as matrix lan- guages (Balcilar et al. 2021 or the GD-WL test (Zhang et al. 2023 which reframes expressivity in terms of graph biconnectivity, capturing the ability to identify cut nodes and edges. Shortest Path Neural Networks 2022) introduced model aggregating across shortest-path distances, but not edges or messages across neighbors whose expressivity differs from 1-WL and addresses the over-squashing prob- 2021). Finally, another approach has been through 2-variable counting logics (Barceló studying what Boolcan statements MP-GNNs can express.
(SPNNs) (Abboud et al.
lem [Alon & Yahav
ct al.
2020
Grohe
2021
ELENE builds on previous expressivity analyses by presenting features that can distinguish challenging 3- WL equivalent graphs Sraphs-SRGss. In S6 we will show that ELENE can fully identify between SRGs with different parameters, and prove that an ELENE-L model can emulate SPNNs. Furthermore, in $7 we empirically evaluate our models on the h-Proximity tasks and explore whether structural (k- WL) expressivity is all we need. We find ELENE-L outperforms previous strong baselines of SPNNs and Graphormers (Ying et al. 2021 Abboud et al. 2022) while simply concatenating ELENE encodings underperforms, showing that expressivity without aftributes is insufficient for certain tasks.
Boosting Graph Neural Models. Besides studying flavors of expressivity, researchers have also focused improving performance for MP-GNNs and Graph Transformers. We summarize the most relevant families of novel network archilectures in connection with ELENE and ELENE-L:
Sub-graph MP-GNNs. ELENE is most related to equivariant, sub-graph methods including k- 2020). Structural MP-GNNs (SMP) (Vignac et al. 2020). NestedGNNs
hop GNNs (Nikolentzos et al.
(NGNNs) (Zhang & Li 2021).
Identity-GNNs (ID-GNN) You el al. (021). Equivariant Subgraph
Aggregation Networks (ESAN)
(Bevilacqua et al.) 2002). Ordered Subgraph Aggregation Networks
2022), Shortest Path Neural Net- Frasca et al. 2022), and Subgraph Permutation Equivariant Networks (SPEN) (Mitton & Murray-Smith 2023). By encoding structural at- tributes of the ego-network sub-graph, ÉLENE captures similar signals as GNN-AK's centroid encodings. However, ELENE-L extends node and edge representations within sub-graphs first, and then feeds sub-graph aware data into a GNN rather than applying a GNN on the sub-graph and aggregating its outputs as in NGNNs and GNN-AK. During learning, ELENE-L resembles SPEN and ESAN with the EGD+ policy with node marking, as the root of the ego-network implicitly marked by the relative degree and distance pairs.
(OSAN) Qian et al., 2022). GNN-As-Kennn (GNN-AK) (Zhao et al.
works (SPNN) (Abboud et al. 2022). Subgraph Union Networks (SUN)
These sub-graph GNNs involve processing the sub- sub-graphs during training and inference, which is avoided by approaches like IGEL (Alvarez-Gonzalez et al. 2022p, GSNs (Bouritsas et al., 2023) or ESC-GNN (Yan et al. 2023), and also ELENE as they add sub-structure information without executing a GNN in the sub- graph. Theo. I shows ELENE encodings are a superset of sparse IGEL vectors. ELENE requires no choice of substructure to count. In contrast, GSNs require counting k-node structures which has an exponential cost in k. Finally, ESC-GNNs also use structural degree and distance signals directly as inputs. However, ELENE-L learns additional embeddings from the structural encodings rather than using them as static features.
8

---

Published in Transactions on Machine Learning Research (04/2024)
Other approaches instead tackle the representation task by learning to select sub-graphs, such as MAG- GNN (Kong et al. 2023) Policy-Learn (Bevilacqua et al. 2023) for which ELENE signals could act as additional features. Finally, ELENE-L can be understood as a graph rewiring approach as recently excmplified by Dynamic Graph Rewiring (DRew) (Gutteridge et al. 2023). since each ELENE-L layer can be independently parameterized to connect nodes via ego-sel and edge-level sub-graphs addinng virtual edges between vertices that are k-hops away, and also passing signals across adjacent nodes (i.c. edges) whose k-depth ego-networks intersect. In this work, we only explore the impact of static edge-level rewiring through relative degrees and Node or Edge-Centiog sub-graphs.
The key difference with the aforementioned methods is that ELENE-L captures edge-level information both in the encoding and during learning, as per Fig. 4 66. shows edge-level signals boost expressivity and cor- roborates results from SUN that node-only sub-graph models are apper-bounded by the 3-WL test (Frasca
ct al. p022). In $7.2 we experimentally validate that ELENE-L, (ED) but not (ND) reaches 100% accuracy
on SR25, challenging SRG dataset only solved before without graph perturbations by O(n²) PPGN- AK (Maron et. al., 2019: Zhao et al. 2022), and partially by SPEN (Mitton & Murray-Smith 2023 whicch distinguished 97% of non-isomorphic pairs.
Perturbation methods. Beyond sub-graph methods, random perturbations of the graph structure like DropGNN (Papp et al.] 2021), Random Node Initializations (Abboud et al.] (021), or paths from random walks EEiasoo et al.] [022) have also shown surprising performance in expressivity tasks. Furthermore, random-walks based methods have been shown to be effective at capturing structural information, including positional information (RWPE) (Dwivedi et al., 2022p. Although ELENE in its current definition does not consider graph perturbations or stochastic features, the underlying quadruplets can be easily adapted to ignore dropped-out nodes or edges, and can be seamlessly combined with random node initializations global positional encodings.
Graph Transformers. Similarly, the extension of Transformer models to graph tasks has led to increased research interest, notably with the introduction of Graphormer (Ying et al. 2021) which included positional and degree encoding similar to ELENE, but using only absolute in/out. degrees. More recently, Pure Graph Transformers (Kim al. 2022] removed graph-specific architecture choices, directly encoding nodes and edges as tokens processod through self-attention and global read-out.
Finally, a series of works have yielded high-performance recipes for graph transformers such as GPS Ram- pášek et al. 2022) combining strong inductive biases from MP-GNNs, as well as global and local encoding to build high-performance Graph Transformers. Transformers on graphs can be understood as Fully-connecto graph processors, and it has been shown that Graphormers can be emulated through an SPNN (Abboud ct al. 2022). In 36.3 we show that ELENE-L can, in turn, emulate an SPNN- and transitively a Graphormer. We consider the analysis of edge-level ELENE signals in Graph Transformers as future work, focusing our study on MP-GNN architectures.
6 Expressive Power
We now analyze the expressive power of is sufficient to distinguish SRGs. We extend recent results ICEL, a sparse vector encoding similar to ELENE (Alvarez-Govzalez et al. 2022) and show that Edge-Centric and Node-Centric ELENE are strictly more expressive than previous methods relying on degrees and distances by comparing their expressivity on SRGs. We then show that ELENE-L is at least as expressive as ELENE, and prove that ELENE-L (ED) is more expressive than ELENE-L (ND) and ELENE (ND). Finally, we connect our framework with SPNNs (Abboud et al. 2022), showing that the latter can be expressed by an instance of node-centric ELENE-L without edge- degree information motivating our analysis on attributed tasks in $
formally answering our question on which information
6.1 Expressive Power of ELENE
Previous work has shown that incoding-basod and sub-graph MP-GNN methods are limited in their ability to distinguish 3- WL equivalent SRGs (Arvind et al. 2020 Balcilar al. 2021 Alvarez-Gonzalez Gonzalez et al., 2022;
Frasca et al. 2022). Recently, Gonaaaez et al. 2022) presented IGEL. simple, sparse node feature
9

---

Published in Transactions on Machine Learning Research (04/2024)
vector containing counts of distance and degree tuples in ego-network, showingg it is strictly more expressive which than the 1-WL, lest. Following Eq. 2 ELENE multi-sets may also be represented as sparse vectors wictorrswhichh can then be used as feature vectors, but also to distinguish ego-network sub-graphs.
We build on top of the results from Alvarez-Gonzale et al., 2022) and show ELENE is at least as expressive as IGEL. We then find an upper-bound of expressivity for IGEL, which at most. able to distinguish ween n, d or À parameters of SRGs, but not μ,, and show Node-Centric and Edge-Centric ELENE is strictly more expressive than IGEL on SRGs it can explicitly encode all SRG parameters by counting edges:
Theorem 1. Node- Centric ELENE is at least expressive IGEL Slbarez-Gonzade et al. 2022 and Iransilinely more expressive than 1-WL.
Proof. The IGEL encoding in Alazale et al. (2022] is simpler version of Eq. 2 that only considers distance (In) and absolute degree (d:)
{ ((.
IGEL & (w);
E (3)
where fl( d()) is bijective function that does not consider relative degrees, in contrast with ELENE'S Thus, for any ego-network, ELENE includes all information required to construct IGEL vectors, it is least as expressive as IGEL.
Theorem 2. ELENE (ND) encodes and distinguishes SRGs with different parameters of n, d, X and p.
Proof. Consider SRG(n, d, 1, E). The maximum diameter of an SRG is 2 (Brouwer & Van Maldeghem 2022 so we focus on the case where = 2. The ELENE (ND) encoding of v E V according to Eq. is:
eae ==(000a)((110)==)))) ud
n-d-1
By definition, any Mode-Centrie net-rk in an SRG has single root with d neighbors, d neighbors with one edge with the root and d - edges to the next layer, and the remaining n - --11 non-adjacent nodes to the root each have d- edges with the d neighbors the root. Consider SRC' (n', d', X. any of the parameters between SRG and SRC' differ, so will og from eq, This is not the case for IGEL, which can at most capture n, d, and A:
k') ) = (V', E'). If
I = (1..)))
ICEL (0.0)) (1, (2. a-d-1
Thus, ELENE (ND) can encode and distinguish all parameters of SRGs outperforming IGEL. However, ELENE (ND) cannot distinguish nomiisomopphic SRGs when nt, d d', x= X, and μ j².
Corollary 1. ELENE (ND) is more expressive than IGEL and 1- 1-WL, per Theo. Ø Theo.
Corollary 2. ELENE (ND) signals at the node-level are not capable of distinguishing between non-isomorphic SRGs with equal parameters e.g. the grophs in Fig. 4.
Proposition 1. ELENE (ED, leveraging both ex Ve E V and e V(u, v) E E) is striclly more expressive than ELENE (ND), as it can distinguish the pair of graphs in Fig.
6.2 Expressive Power of ELENE-L
Theorem 3. ELENE-L with the sum as the pooling operator is at least as expressive as ELENE.
Proof. We first show ELENE-L (ND) at least as expressive as ELENE (ND). We then show that the ED variants are at least as expressive as ND variants (Prop. 20, and show through Fig. 4 that ELENE-L (ED) is more powerful than Node-Centric ELENE-L. (ND).
10

---

Published in Transactions on Machine Learning Research (04/2024)
On ELENE-L (ND). Yu V, the ELENE-L(xt) representation of v is given by (/D(v) per Eq. 4 D (v) is the result of applying PuD to the concatenation of x and the combined representations of every u E V and (u, w) E E. Let Pout and Pna be the identity function, we exclude edge~level information by discarding the output of tea. We now expand (v), which (n with the changes to the learnable 4:
V
$ (1))
x
x x
EnD((l)))
We discard repeated x terms, and rewrite the reprosentation of distributing the sum over the concatenated vector:
(D)
x
Emb((l())
Let W and W W.3add E RSS used by Emb be identity matrices every relative degree and distance pair out of S = duax (k+ + 1) has a single position in W. By using the sum as the pooling function, we obtain the frequency each relative degrec and distance pair, matching ELENE in Eq. Thus, & Biure (v) contains the information contained in the ELENE multi-set, reaching at least the same expressivity.
Proposition 2. ELENE-L (ED) variants with the sum as the pooling operator are least expressive as ELENE.
On ELENE-L. (ED). We had discarded ted, showing ED variants are at least as expressive as ND variants, since the concatenation of edge-level information can only match or boost expressivity. Thus, (ND) and (ED) variants of ELENE-L are as expressive as ELENE.
Theorem 4. ELENE-L (ED) more expressive than ELENE-L L (ND) and ELENE (ND).
Proof. There least a pair of non-isomorphic SRGs that ELENE-L EED) can distinguish. In $3.2 we
show that the Shrikhando and 4 Rook graphs (Arvind et al. 2020 Balcilar al. 2021 (parametrizod as SRG(16, 2, 2)) can be distinguished by Edge-Centric counts that ELENE-L (ED) captures despite being undistinguishable by 3-WL (by implementing Eq. 1at the edge level). Following from Theo. and Theo. both graphs are indistinguisaable by ELENE (ND) or ELENE-L (ND), as well as sub-graph GNNs like GNN-AK or SUN.
Intuitively, SRGs are indistinguishable with node-centric ego-network sub-graph encodings when k E {1, 2} since all nodes produce identical representations, as shown Theo. 2 However, the graphs can be distin- guished by odge-level information as per Eq. 7 as the interscction of k-depth ego-networks for (vi, U2) differ in edge counts between both SRGs as observed in S3
We see the 4 x Rook Graph has 6 edges (i.e. 1 (2)) ) 6) while the Shrikhande graph has | (e 5, hence the graphs are distinguishable by ELENE-L (ED), but not ELENE-L (ND) or ELENE (ND). ]
6.3 Linking ELENE and Shortest Path Neural Networks.
Remark A Graphormer with mar. shorlest path length M and global readoul. is an instance Shorlest Poth Neural Networks (SPNNs) with = depth (Abboud et al. 2022).
Theorem 5. ELENE-L (ND) is as expressive as Shorlest Path Neural Networks (SPNNs), and transilively, Graphormers.
Proof. Let (v) (ulu E V VV Alo,,, w) = k) be the nodes in G exactly at distance i of v. In Abboud et al. (2022), k-depth SPNN updates the hidden state of node an aggregation over the 1, I,.., & exact-distance neighbourhoods:
* x
xt1 = -opp ((1+()
Σ
as (E)
Σ
x
(10)
11

---

Published in Transactions on Machine Learning Research (04/2024)
We show that ELENE-L (ND) can implement SPNNs. First, let Yod
in Eq. 6
such that:
x ++1 = (v) = PDD
x
Σ
Lh (ull))
Σ
Dea (u, w|u)
(u,w)
We drop T (u, wlo) as SPNNs ignore edgo-level signals where:
Let xD be composed of two functions (pp()())
12
v
(x
Σ D (ua(ul)))
x
Σ
Pa (ulpr))
We replace PND by Pap and g(-), and expand @ (2/e))
Vk
x = Ppp (1 +c) x + Σ Dnd x x Emb(ulu))
We then instantiate (-) as:
nna = Σ a: ifli = (s(u, X
if[l] can be implemented through the distance and degree signals in Emb, such we check if the node distance matches specific value Substituting in xt+1 above yields:
VE
x = Pop (1 c) -x.
X
ar ifli = ls(u, x
which is equivalent to Eq. 10 and shows FLENE-L (ND) can learn like SPNNs and, transitively
through Rem. that Graphormers can be emulated by ELENE-L (ND).
7 Experimental Results
We now study the effect of introducing ELENE and ELENE-L in variety of graph-level settings, evaluating where purely structural ELENE encodings underperform ELENE-L, and the practical impact of ELENE variants in terms of model performance, training time, and memory costs. We describe our experimental protocol in $7.1 and provide reproducible code, hyper-parameter,, and analysis scripts through Githut 5 for four experimental benchmarks:
A) Expressivity. Evaluates whether models distinguish non-isomorphic graphs (on 1-W1. EXP (Ab- boud et al., 2021) and 3-WL SR25 (Balcilar et al., 2021 equiv. datasets), count sub-graphs (in Ran- domGraph (Che et al. 2020 ) and evaluate graph-level properties (Corso et al. 2020).
B) Proximity. Measures whether models learn long-distance attributed node relationships in h- t-Proximity datasets (Abboud et al. 2022).
C) Real World Graphs. Evaluates performance on five large-scale graph classification/rereesste datasets from Benchmarking GNNs (ZINC, CIFARIO, PATTERN) (Dwivedi et al. 2020), and the Open Graph Benchmark (MolHIV, MolPCBA) (Hu et al. 2020a)
D) Memory Scalability. Evaluates the memory consumption of ELENN-T, on d-regular graphs, varying n and drex to validate the aiic complexity analysis in $3. and comparing with the memory consumption of GIN-AK, GIN-AK+ and SPEN (Mitton & Murray-Sma Smith 2023).
Incclding edge-level signals may bring ELENE-L (ED) to parity with Pure Graph Transformers Kim et al. 2022 not explore this connection.
We do
*g(:) is linear combination over concatenated imput vectors, learnable by first layer of Pout without activations. Thiis is not necessary during learning: onc-hot 'decoder' can be implemented using two-layer perceptron with ReLU activations.
hnttps://githin cww/nur- ag/EEEE
12

---

Published in Transactions on Machine Learning Research (04/2024)
7.1 Experimental Protocol
Reporting. When reported in the original studies, we show stddevs for experiments with more than two runs following (Zhao et al. 2022), and highlight best-performing models per task in underlined bold. ELENE denotes Eq. 2 as additional features, while ELENE-L denotes the reprosentations of of 6 and [Eq. 7 (ED) denotes ELENE-L L with Edge-Centric signals, while (ND) denotes a Node-Centric variant that ignores edge information for ablation studies. 't indicates results from the literature.
Environment. Experiments ran on a shared server with a 48GB Quadro RTX 8000 GPU, 40 CPU cores and 502GB RAM. Each individual job has limit of 96GB RAM and 8 CPU cores. To measure memory and time costs without sharing resources, we also reproduced our experiments on real-world graphs on SLURM cluster with nodes equipped with 22GB Quadro GPUs. Finally, scalability experiments ran on Tesla T4 GPUs with 15.11GB of VRAM to validate our approach on consumer hardware.
Experimental Setup. We explore sub-sets of ELENE hyper-parameters via grid search with & e {0, (,,1,2,3,5) parameter ranges for ELENE and ELENE-L, and test the ED/ND variants for ELENE-L with em- bedding params. E (16,32, 64), p == dmax; using masked-mean pooling for stability. For I-Proximity (Ab- (iaeinerrrrriinnaaaaan compare against SPNNs (Abboud et al. 2021) I and Graphormer Ying et al. 2021) originally reported. For Exprcssivity and Real World Graphs, we reuse hyper-parameters and splits from (2022) without archilecture search, comparing against strong MP-GNN baselines from literature where GNN-AK* underperforms: CIN (Bodnar et al. 2021) for ZINC and SUN (Frasca et al. 2022 for sub-graph counting. We choose GINE (Hu et al. 2020b), an edge-aware variant of GIN (Xu et al.
boud et al. 2022)
GIN-AK+ + in Zhao et al.
2019), , as our base MP-GNN given that GIN-AK" outperforms its uplifted counterparts for GCN-AK+ and & Welling 2017 Corso et al.
2022 without running into out-of-memory issues like PPGN (Maron et al.) 2019) in the PPGN-AL instantiation. Finally, for scalability we compare
(Kipf PNA-AK+
2020 Zhao et al.
with GNN-AK on benchmark datasets Zhao et al. (2022) and SPEN Mitton & Murray-Smith (2023)
Experimental Objectives. We connect expressivity and its relation to graph alfributes, comparing against methods that do not perturb graph structure, c.g. DropGNN (Papp et al.
2021 | levorage random walks,
e.g. RWPE (Dwivedi el al., 2022); or require costly pre-processing e.g. O(n)) spectral eigendecompositioon
such as GNNML3, LWPE, or GraphGPS (Balcilar al.) 2021; Dwivedi et al., 2022 Rampášek et al., 2022)
Per $6.3
ELENE relates to Graphormers via SPNNs, focus sub-graph GNNs and SPNNs.
7.2
Expressivity
We test ELENE on four MP-GNN expressivity datasets, with results captured Tab. 1
Introducing ELENE signals improves the performance of GINs, and our single-run results EXP and SR25 are consistent with our formal analysis on g namely, ELENE and ELENE-L L (ND) and (ED) all reach 100% accuracy on the 1-WL equivalent EXP task, as expected from Theo. 1 Furthermore, ELENE-L (ED) can distinguish all 3-WL
equivalent SRGs in the challenging SR25 dataset providing empirical evidence for Theo. 4
On Graph Properties and Counting Substructures (2 runs averaged, as in Zhao et al. 2022 ), a GIN + ELENE-L (ND) model consistently outperforms GIN-AK without context encoding. In Counting, both ELENE variants and GIN-AK+ are outperformed by SUN, but GIN+ELENE matches or outperforms GIN on every task, showing that ELENE features are informative and can boost performance by themselves.
On both tasks, find that GIN+ELENE-L (ED) performs poorly outperforming GIN+ELENE but not our baselines. This might be caused by model parametraatiiii,onn,, as six node and edge-level embedding matrices are learned for 3 and layers on Counting Substructures and Graph Properties respectively! Fi- nally, on the Graph Properties tasks of IsConnected and Diameter, a GIN-AK+ with ELENE-L outperforms state-of-the-art results and interestingly a GIN with ELENE-L (ND) outperforms all existing baselines on the IsConnected task. This can be further improved by using GIN-AK+ with ELENE-L (ND).
Weight sharing may help peeemparametiiitionn by learning a single structural representation, trading off expressivity.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Table 1: Expressivity benchmark results. EXP and SR25, introducing ELENE-L yields the best perfor- mance per task, shown in underlined bold. We highlight the best-pe rist-performéng configurations from ELENE variants on GIN in italics, which we consistently observe in the for isomorphism tasks.
(ND) configuration except
Count. Substr.
Graph Prop. (0 (MAE))
EXP
SR25 (Acc.)
Model
(MAE)
(Ace.)
Tri.
Tail Tri.
Star
4-Cycle
IsCon.
Diam.
Radius
GIN
50%
6.67%
0.357
0.253
0.023
0.231
-1.914
-3.356
-4.823
SUNT. Frasea ol.
2022
0.008
0.008
0.006
0.011
-2.065
-3.674
-5.636
GIN-AK ZZhao
2022
100%
6.67%
0,093
0.075
0.017
0.073
-1.993
-3.757
-5.010
GIN-AK
100%
6.67%
0.011
0.010
0.016
0.011
-2.122
-3.917
-5.260
GIN+ ELENE
100%
6.67%
0.024
0.023
0.020
0.041
-2.218
-3.656
-5,024
CIN+ELENE-L (ND)
100%
6.67%
0. 0.012
0.015
0.014
0.016
-2.620
-3.815
-5.117
+IN+ELENE-L (ED)
100%
100%
0.023
0.023
0.017
0.023
-2.497
-3.541
-4.755
Best (GIN) / GIN-AK) + (ELENE ELENE-L)
100%
100%
0.010
0.010
0.014
0.011
-2.715
-4.072
-5.267
7.3
h- I--Prxximity
We evaluate ELENE-L on f--Proximity (Abboud et al., 2022) tasks (10-fold averaged)- where nodes are assigned colors including red and blue, and models classify whether all red nodes have at most two blue nodes within h hops (positive) otherwise (negative), in Fig. 2 Models must learn which colors are relevant for the larget and capture long-ranging dependencies during learning. Edge information is irrelevant, and pre-computed encodings like ELENE cannot capture interactions of distances and node attributes.
In Abboud et al. (2022): the authors reported that MP-GNNs perform well on = 1-Proximity, so we focus on the h E {3,5,8 5, 8, 10) variants. Tab. shows our results, where ELENE-L, (ND) outperforms strong baselines from SPNNs and Graphormer (Abboud al. 2021).. As expected, GIN + ELENE did not meaningfully improve over GIN. Our numerical results provide empirical validation for Theo.
Table 2: P-Proximyty binary classification results (accuracy). ELENE-L L (ND) without degree information
outperforms baselines strong SPNNs and Graphormer baselines from
Abboud et al. 2021
3-Prox.
5-Prox.
8-Prox.
10-Prox.
GCNí
50.0
50.0 0.0
50.1 0.0
49.9
GAT
50.4 1.0
49.9 + 0.0
50.0 + 0.0
50.0 + 0.0
SPNN (k 1)' 50.5 + 0.7
50.2 1.0
50.0 0.9
49.8 + 0.8
SPNN (k: 5)t
95.5
96.8 + 0.7
96.8 = 0.6
96.8 = 0.6
Graphormer' 94.7
9..1
97.3 1.4
96.8 = 2.1
GIN+ELENE 52.0 2.0
518 1.2
52.4 - 2.6
514 1.1
GIN+ELENE-L (ND) 98.3 0.5
98.6 1 0.5
99.0 1.00:00
99.2 1 0.3
7.4 Real World Graphs
We also evaluate ELENE and ELENE-L five real-world, large-scale graph classification and regression tasks. We test ELENE and ELENE-L ZINC, MolHIV, PATTERN, CIFAR10, and MolPCBA and report our results in Tab. 3 Given increased memory and computation costs and the weaker performance of ELENE-L (ED) in $7.2 we only evaluate ELENE-L (ND).
On ZINC, GIN + ELENE-L (3 averaged runs) achieves comparable results to existing baselines, including SUN Frasca al. 2022). Furthermore, by introducing ELENE-L on GIN-AK+ the model matches the previous strong bascline achieved by CIN (Bodnar et al. 2021). On PATTERN (3 averaged runs), GIN + ELENE-L achieves comparable results to GIN-AK+, but does not meet. the best reported performance of
14

---

Published in Transactions on Machine Learning Research (04/2024)
Table 3: Results on real world benchmark datasets. We compare with published results and reproduce the experiments of Zhao al. (2022). Adding ELENE variants GIN and GIN-AK* yield state-of sate-of-thhe-rr results on ZINC and MolPCBA, and match the performance of existing methods in PATTERN and MolHIV.
ZINC
PATTERN
MolHIV (ROC)
CIFARIO
MolPCBA (AP)
(MAE)
(Acc.)
(Acc.)
GSN
0.115 0.012
77.99 + 1.00
NGNN
78.34 + 1.86
28.32 + 0.41
CIN
0.079 + 0.006
80.94 0.57
SUN
0.083 + 0.003
80.55 + 0.55
GCN-AK+1
0.127 + 0.004
86.887 0.009
79.28 + 1.01
72.70 0.29
0.285 0.000
GIN-AK
0.094 + 0.005
86.803 + 0.044
78.29 + 1.21
67.51 + 0.21
0.274 + 0.000
GIN-AK+
0.082 + 0.003
86.868
0.028
77.37 + 0.31
72.39 0.38
0.293 + 0.004
(Lit, results!)
10.080 + 0.001
186.850 0.057
179.61 +: 1.19
172.19 +: 0.13
10.293 1 0.004
GIN
0.155 + 0.005
85.692 0.042
78.72 + 0.54
59.55 + 0.54
0.271 + 0.003
(Lit. results!)
16.163 1 0.004
185.732 1. 0.023
178.81 1: 1.01
159.82 1: 0.33
10.268 1 0.001
GIN+IGEL
0.103 + 0.004
86.762 +: 0.029
78.92 +: 0.92
GIN+ELENE
0.092 + 0.001
86.783 + 0.044
78.92 + 0.35
56.34 - 0.06
0.277 + 0.002
+ELENEL (ND)
0.083 1 0.004
86.828 0.002
78.26 1 0.93
68.95 1 0.25
0.294 1 0.001
Best Result
0.079 + 0.003
86.828 0.002
79.15 + 1.45
68.95 0.25
0.294 + 0.001
(ELENE ELENE-L)
GCN-AK+ by 0.07% delta. We do not achieve to independently reproduce GIN-AK results (Zhao et al, 2022 MolHTV (5 averaged runs) runs)-fidding that GIN with FLENE or ELENE-L, do not have statistically significant (p < 0.01) differences with GIN, while the performance of GIN-AK is statistically inferior.
Tab. 4 shows time and memory costs of ELENE compared to trate-of-the-ar methods. Despite not tuning hyperparameters, a G model outperforms GIN-AK CIFAR and a strong GIN-AK+ baseline in MolPCBA. Purthermore, our setup of GIN layers combined with ELENE always outperforms GNN-AK+ in terms of memory consumption. In ZINC, GIN+ELENE- (ND) requires 0.99GB compared to the 1.68GB of GIN-AK+ while reaching comparable performance +.083 vs 0.082 0.003, respectively). In MolHIV, GIN+ELENS model requires only 70MB during training while outperforming the ROC of our reproduced run of GIN-AK+, which required 790MB an 11.3-fold reduction in memory usage. On PATTERN, we find that GLE+ELENE- (ND) achieves 99.95% the performance GIN-AK+ while consuming only 7.8GB of memory during training, compared to the 26.52GB reported by /Zhao et al. 2022 3.4-fold reduction.
In summary, ELENE and ELENE-L (ND) achieve comparable results to the baselines with favorable time / memory efficiency. ELENE encodings used mode-features (GIN+ -LLENE) add minor overhead over GIN and match outperform GIN+IGEL in all tested settings, and GIN-AK in four over five. ELENE-L (ND) also shows favorable memory performance versus GIN-AK and GIN-AK in all setups. Finally, we observe additional memory costs for ELENE-L (ED) due to using node and edge embeddiins..
Table 4: Memory and time performance on benchmark datasets, controlling for shared resource
per $7.1 We report average epoch duration in seconds (s) and maximum memory consumption in gigabytes GB) respectively. Dashed entries indicate executions that terminated due to running out of memory.
ZINC
PATTERN
MolHIV
CIFAR10
MolPCBA
GIN
6.02s
0.12GB
118.62s
1.42GB
14.88s
0.07GB
98.37s 283.93s
0.90GB 18.80GB
223.13s
0.44GB
GIN-AK
9.76s
1.1GB
19.30s
0.64GB
534.78s
3.80GB
GIN-AK +
13.63s
L68CB
25.47s
0.79GB
607.89e
3.83GB
GINNEE
6.14s
0.13GB
90.15s
1.47GB
14.94s
0.07GR
120.21s
0.91GR
278.29s
0.46GB
ELENE-L (ND)
10.23s
0.99GB
146.15s
7.80GB
42.53s
0.54GB
224.43s
10.72GB
451.12s
2.39GB
ELENE-L (ED)
22.61a
2.85GB
32.28s
1.40GB
1025.58s
7.10GB
15

---

Published in Transactions on Machine Learning Research (04/2024)
7.5 Memory Scalability
Finally, we evaluate the scalability of ELENE-L. in a learning setting. We analyze the memory consumption function of the graph size and how it compares with other methods. For that, we follow similar setting as Mitton & Murray-Smith (2023) for SPEN: we design and implement learning task on large d-regular graph, and use it to explore memory consumption under different values of degree d and nodes n. With this setup, we train the model for 25 epochs to predict a constant variable so that both input tensors and gradient computations are kept in memory.
We evaluate both ELENE-L (ND) and (ED), together with a GIN model without any ELENE-L features, GIN-AK and GIN-AK+ baselines. For all ELENE-L variants, execute the benchmark with different values of & E 21,
Max. Memory Consumption (MB)
d max 12 Merrory
8192MB
4096MB
k 1:
2048MB
GINAA
CIN-ACI
1024MB
ELTNE (ND]
CLTNE (60)
512MB
2:
256MB
Iek GINAK
GIR-AC
128MB
ELTNE (ND)
CLINE
64MB
32MB
16MB
102
10225
102.
10275
103
10325
103.
103.5
10a
10425
10
Graph Size (Nr. of Nodes)
Figure 7: Memory scalability analysis of ELENE when dpez 12. We include GIN (dotted line) and maximum GPU memory (dash-and-dotter linc) as indicative lower and upper memory bounds. ELENE-L (ND, full lines) outperforms both GIN-AK, GIN-AK+ (dotted lines) and ELENE-L (ED, dashed lines). Additionally, ELENE-L (ND) can encode all d-regular graphs the benchmark when k = 1. As expected, memory consumption increases lincarly with the number of nodes dnax kept fixed.
Fig. 7 shows our results when dasx 12. As expected, the memory cost grows exponentially as function n. We observe that ELENE-L (ND) with k can scale up to graphs with 10, 000 nodes with ego-network sub-graphs. Since all nodes have the same degree daxx 12, at 2 hops we are guaranteed to find the root node, its 12 neighbors, and at least one additional neighbor at 2 hops or 14 total nodes. In practice, as the graphs are randomly generated, we find that each of the 2-depth subgraphs contains an average of 144.13 nodes with the expected maximum 145.
Additionally, our experiments show that ELENE-L (ND) with k can scale up to graphs with 104.5 31, 623 nodes with up to daax = 18. Furthermore, despite requiring additional memory, the more expressive ELENE-L (ED) can nevertheless be used for & = 1 for graphs with up to 104.5 nodes well. Scaling graphs with more than 105 nodes is possible by increasing the cpu-memory (our limit is 96GB) or alternatively changing the implementation. The latter can be done for example by computing the encodings through parallel BFS, which would result in a slower algorithm (but the same order complexity). We provide additional results for daax and d 18, as well as different graph density patterns, in SB.2
Recent methods like SPEN outperform global perruuationn-qquiariann methods like PPGN. However, SPEN still struggles to process significantly smaller graphs, with & 1, 000 nodes and k 1 depth ego-networks that contain 9 nodes, even with higher GPU memory as reported by Mitton & Murray-Smith (2023). Compared with the complexity of SPEN, which O(n O ELENE-L can encode ego-networks with 16 times more nodes with comparable memory usage-wiind while outperforming sub-graph GNN baselines like GIN-AK and GIN-AK+.
16

---

Published in Transactions on Machine Learning Research (04/2024)
7.6 Experiments Summary
ELENE and ELENE-L consistently boost GNN performance on the three experimental benchmarks, and are shown to be scalable in Tab. and Fig.
On Expressivity, $7.2 gives empirical support for Theo. 4 i.c. that ELENE-L (ED) can distinguish SRGs, achieving 100% accuracy the challenging SR25 (Balcilar et al. 2021 dataset. Although SUN (Frasca ct al. 2022 outperforms other models on Counting Substructures, ELENE and ELENE-L. still improve baseline performance and match previous GIN-AK and GIN-AK+ baselines respectively. On Graph Properties, +IENELENE- matches existing baselines, and a GIN-AK* model with ELENE-L outperforms previous state-of-the-art results on the IsCon. and Diam. tasks with -2.715 and -4.072 (og(()ME)) each.
On h- Proxxiiity, $7.3 validates Theo. 5] ie., that ELENE-L (ND) is at least expressive as SPNNs (Abboud 2022 as ELENE-L (ND) outperforms SPNNs and Graphormers at capturing attributed structures et al.
that sparse ELENE vectors alone cannot capture.
On Real World Graphs from $7 ELENE and ELENE-L reach state-of-the-art results. On ZINC, GIN-AK+ with ELENE-L. achieves 0.079 + 0.003 MAF, matching CIN (Bodnar et al. 2021). A GIN+ELENE-L. matches 99.95% of the performance of baselines on PATTERN while consuming 3.4x less memory, and +IN+ELENE reaches 0.1% less accuracy than GIN-AK+ but does so using 1.47GB, compared to the 26.54GB reported for GIN-AK+ 18. 1x memory reduction. Finally, a +IN+ELENE-L matches stale-of-the- resulls MolPCBA 20.294 0.001 0.293 + 0.003 of GIN-AK+ (Zhao et al. 2022 without reper-paramete tuning and while consuming 37. 67.6%% less memory (2.39GB us 3.83GB).
On Memory Scalability, $7.5 shows that ELENE-L can be used on d-regular graphs with more than 1 nodes where dmax E {6, 12, 18}, validating the expected memory costs from $3.3 and outperforming the memory consumption strong GIN-AK and GIN-AK+ baselines and recent methods like SPEN (Mitton Murray-Smite 2023
8 Conclusions
We presented ELENE, a principled edge-level ego-network encoding capturing the structural signals sufficient. to distinguish WL equivalent SRGs. We proposed two variants ELENEE and ELENE-L- and showed that Node-Centris and Edge-Centric representations exhibit different expressive power. To position our find- ings, we formally drew connections between ELENE and recent Sub-Graph GNNs, Graph Transformers, and Shortest Path Neural Networks.
Empirically, we evaluated our methods on 10 different tasks, where the sparse ELENE vectors improve performance on structural expressivity tasks. Our learnable Edge- Centric ELENE-L variant boosts MP-GNN expressivity to reach 100% accuracy on the challenging SR25 dataset, while its Node-Centric counterpart improves over a strong baseline on the h-Proximity task and matches state-of-the-art results in several real- world graphs. Finally, we found our methods provide trade-off between memory usage and structural expressivity, improving memory usage with up 18.1x lower memory costs compared to sub-graph GNN basclines.
Broader Impact Statement
Our main contributions are (a) a novel family of edge-aware features that can be used alone or during learning in MP-GNNs, with (b) a formal analysis of their expressivity that shows they can distinguish challenging SRGs, and (c) experimental results matching state-of-the-art learning models with favorable memory costs.
We do not foresee ethical implications of our theoretical findings. Our experimental results are competitive with state-of the--rtt methods lower memory footprint, which may help solve tasks with limited memory budgets.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Acknowledgements
This work is part of the action CNS2022-136178 financed MCIN//AL//00..8/////000000 and by the EU Next Generation EU/PRTR. This work has been co-funded by MCIN/ ACCT///5//0013300/55001 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-N)
References
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, IJCAT-21, pp. 2112 2118, 8 2021.
Ralph Abboud, Radoslav Dimitrov, and ismail ilkan Ceylan. Shortest path networks for graph property prediction. In Proceedings of the First Learning on Graphs Conference (LoG), 2022.
Uri Alon and Fran Yahav. On the bottleneck of graph neural networks and its practical implications. Tn International Conference on Learning Representations, 2021.
Nurudin Alvarez-Gonzalez, Andreas Kaltenbrunner, and Viceng Gómez. Beyond 1-WL with local ego- network encodings. In The Pirst Learning on Graphs Conference, 2022.
V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky, On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Compuler and System Sciences, 113:42-55 59, 2020.
Laszlo Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium on Foundations of Computer Science (sfes 1979), pp. 39 46-4 1979. doi: 10.1109/SFCS.1999
Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Albert-László Barabási and Réka. Albert. Emergence of scaling in random networks Science, 286(5439): 509 509-512, 1999. doi:
Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems, volume 29, 2016.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Bal- amurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. Tn International Conference on Learning Representations, 2022.
Beatrice Bevilacqua, Moshe Eliasof, Eli Mcirom, Bruno Ribciro, and Haggai Maron. Efficient subgraph gnns by learning effective selection policies. arXiv preprinl ar 2r1:::2310.2088. 2023.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido F Montufar, and Michael Bronstein. Weisfeiler and Lehman go cellular: CW networks. In Advances in Neural Information Processing Systems, volume 34, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657 668, 2023.
Andries E. Brouwer and Hendrik Van Maldeghem. Strongly regular graphs, volume 182. Cambridge University Press, 2022. ISBN 9781316512036.
18

---

Published in Transactions on Machine Learning Research (04/2024)
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information. Processing Systems, volume 33, pp. 13883-00955, 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liö, and Petar Velickovic. Principal neighbourhood aggregation for graph nets. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. ISBN 9781713829546.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru- Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, volume 28, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Bench- marking graph neural networks. Xiv preprint orXi::2003.0088, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference Learning Represenlations, 2022.
Moshe Fliasof, Fldad Haber, and Eran Treister. pathGCN: Learning general graph spatial operators from paths. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volune 162 of Proceedings of Machine Learning Research, pp. 5878-5891. PMLR, 17-23 Jul 2022.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetrics. In Advances in Neural Information Processing Systems, 2022.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 94th International Conference on Machine Learning (ICML), volume 70, 2017.
Martin Grohe. The logic of graph neural networks. In Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '21, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781665448956, doi: 10.1109/ LL0CS522222.2221199222
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. DRew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp. 12252-12261 PMLR, 2023.
Weihua Hu, Matthias Foy, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:205500068) 2020a.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovee. Strategies for pre-training graph neural networks. In International Conference on Learning Representa- tions, 2020b.
Jinwoo Kim, Dat Tien Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. In Advances in Neural Information Processing Systems, 2022.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR, 2017.
Locheng Kong, Jiarui Feng, Hao Liu, Dacheng Tao, Yixin Chen, and Muhan Zhang. MAG-GNN: Rein- forcement learning boosted graph neural network. In seeenhh Conference on Neural Information Processing Systems, 2023.
19

---

Published in Transactions on Machine Learning Research (04/2024)
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Advances in Neural Information. Processing Systems, volume 33, pp. 4465 4478, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Gaspard Michel, Giannis Nikolentzos, Johannes Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph ncural networks. In Proceedings of the 40th International Conference on Machine Learning (ICML), 2023.
Joshua Mitton and Roderick Murray-Smithh Subgraph permutation equivariant networks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Christopher Morris, Martin Ritzert, Matthias Fcy, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAT Conference Artificial Intelligence, 33(01):4602 (6001):6022460000 4469,, Jul. 2019.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning; the story so far. J. Mach. Learn. Res., 24(1), mar 2023. ISSN 1532-4435.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130:195 205, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. In International Conference on Learning Representations, 2022.
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. In Kamalika Chaudhuri, Stefanic Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Leurning, volume 162 of Proceedings of Machine Learning Research, pp. 17323 17345. PMLR, 17- 17-23 Jul 2022.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. DropGNN: random dropouts increase the expressiveness of graph neural networks. In 35th Conference on Neural Information Processing Systems, 2021.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. In Alice Н. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, 2020.
B Weisfeiler and A Leman. The reduction of a graph to canonical form and the algebra which appears therein. Nauchno- Technicheskaya Informatsia, 2(9):12-16, 16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Tn International Conference on Learning Representations, 2019.
Zuoyu Yan, Junru Zhou, Liangeai Gao, Zhi Tang, and Muhan Zhang. Efficiently counting substructures by subgraph gnns without running gnn subgraphs. arxi preprint arXi::2303.000 10576, 2023.
20

---

Published in Transactions on Machine Learning Research (04/2024)
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tic- Yan Liu. Do transformers really perform badly for graph representation? In 35th Conference Neural Information Processing Systems, 2021.
Rex Ying, Ruining He, Kaifeng Chen, Pong Fksombatchai, William I. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM Inter- national Conference on Knowledge Discovery & Dala Mining, pp. 974 983, 2018.
Jiaxuan You, Rex Ying, and Jure Leskovee. Position-aware graph neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7134-7143, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural net- works. In 35th AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim. Graph transformer networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di Hc. Rethinking the exprossive power of GNNs via graph biconnectivily. In International Conference on Learning Represenlations, 2023.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances Neural Information Processing Systems, 34, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations, 2022.
21

---

Published in Transactions on Machine Learning Research (04/2024)
A ELENE through BFS
This appendix showcases BFS implementation of the ELENE Encoding that spans edges until reaching the maximum encoding depth & given a node u in V. As noted in $3.3 this implementation can be trivially parallelized over processors as the encoding of each is independent of other nodes.
Algorithm ELENE Node Encoding using BFS.
Input: G = (V, R), v E V, :
1: distances = (v: 0
Mapping of nodes to their distance to n, i.e. la(u, v). (P) (ulv).
Mapping of nodes to their relative degrees, i.e. 3: for (src, dst) in C.bfs_edgeesi max_max__deeeee max_mepthh k) do
r_degrees == {v (0,0,0)
4: if src & distances then
D Invariant: only one node can be unknown / not in distances.
5: dst, := src, dst
end if
if dst & distances then distances(dst] distances(arc] end if
b dst is unknown, so distance is onc-hop after src's.
10:
dist_ dest_delta- == distances[dst] distances/src|
Compute the distance delta in f-1, 0, 1}.
11:
12:
& Access the relative degree counts each node.
13:
src_ erc_deg- = r_ degrees degrees.get(src, [0, 0])
14:
det_ __ deg.eeeeesss. seeeesgee(dst,,, (0, 0,))
15:
16:
Increment degree counts for each node in their respective 'direction'
17:
arc deg_ddist_ddeeteeeee deltalllaaaa.... + 1]++ & The indexing maps {-1, 0, 1} deltas into {0, 1, 2) vector indexes.
18:
jst__dg[[ dist_ +est__delaa+++++
19:
20:
Update the relative degrees of erc and dst.
21:
r degrrees |rc| := src_deg
22: r_ degrees dst] == dst_deg
23: end for
24:
25: b For each u E Vk compute Eq. quadruplets, count their frequencies and return the mapping.
26: mapping: := !
27: for u E 1 do
28: quadruplet: := (distances(u) r__ganceeeeulr.deeeeeeeeeeeeee [u][0]]] r_ degrees (..mm()) [egrressuu]] [u][)
29: quadrugluaadrullet)+++
30: end for
Output: mapping
B Benchmark Details
In this appendix, we provide an overview of the benchmark we execute when evaluating ELENE, including the variants of models we test, and descriptions of our code and compute environment. We also summarize the datasets use in SB.1
Benchmark Configuration. We build on top of the implementation from Zhao et al. 2022 explicit ego-network attributes on their evaluation framework for consistency.
introducing
All ELENE results are reported by extending the node and edge attributes as input into a GIN Xu et al. (2019) extended support edge-level features when available Hu al. (2020b). In all experiments, we evaluate ELENE-L. on top of GINs with edge extensions Hu al. (002bb).
22

---

Published in Transactions on Machine Learning Research (04/2024)
For all explicit ego-network attribute methods, summarize the available hyper-parameters in Tab. 5 the implementation of FLEENE-L, we observed unstable training when using the sum pooling function during early stages of development. We found that training was stable using masked Mean pooling where the a node messages (or m for edge messages) in the ego-network sub-graph are averaged considering a binary mask for neighbors of the root. node al distance or less. All our results are reported using Mean pooling, including our results on SR25, suggesting that this decision does not adversely impact the model expressivity expected from S6
For
The resulting implementation of Eq. 4 is:
Ra (u(e) (ize
(u, w(v) size(E!)
(
(v) = 4 Pout
x Σ
Σ
(u,w))
We use an analogous implementation for Eq. 7 implement ELENE-L (ND) without the Ded term so that it more closely follows the node-centric ELENE encodings of Eq. reducing memory costs. We describe the hyper-parameters implemented to control our models in Tab.
Additionally, in our experimental benchmark we choose to
Table 5: Hyper- parammeersettrrs controlling the behaviour of explicit ego-network attribute encodings. ELENE only relies on k while ELENE-L has 5 additional configurable settings.
Parameter
Elene
Elene-L
Depth of Ego-Net (k)
{0, 1, 2]
{0. 1, 2, 33
Embedding Type
Sparse
Dense, learned
Representation
Node-only
Node-centric (ND), Edge-centric (ED)
Set to doax
Set to dear
Max. Encoded Degree
from the training datasel or 0 (ignore degree info).
from the training dalaset.
Set to k. Can be modified to control the sub-graph norm. factor.
Max. Encoded Distance
Equal to k
Tested Models. On the Expressivity tasks, ZINC and MolHTV, we evaluate all learnable variants (ND and ED), while on the remaining classification rregreesiionnreeeeisiooooooo benchmarks only consider (ND) models due to reduced memory costs and limited computational bandwidth. Furthermore, in all ELENE-L setups we only test reduced number of syper-parameted due to computational constraints, unless specified otherwise, only evaluating different values the maximum sub-graph distance to embod. We describe the hyper-paramoters and modeling choices in detail in SB.2
B.1 Dataset Details
We summarize the key aspects of the datasets we use evaluate our proposed methods in $7 Tab. contains an overview of each benchmark and dataset, the objective being addressed, and high-level dataset statisties-nameyy namely number of graphs, average number of nodes (n) and edges (m) per graph.
B.2 Detailed Experimental Summary
In this section, we summarize our experimental setup and training procedure, describing the hyper- parameters that we consider in each setting. For all the experiments described, we evaluate the ELENE encodings by concatenating them with the node feature vectors and as part the edge features when available, using the element-wise product following the same approach as IGEL
Expressivity. See expressivityDaaasees.ee sh for details.
23

---

Published in Transactions on Machine Learning Research (04/2024)
Table Dataset statistics.
Nr. of Graphs
Benchmark
Dataset
Objective
Tasks
(Train
Valid
Test)
Avg. n
Avg. m
EXP
Distinguish 1-WL Equiv. graphı Distinguish 3-WL Equiv, graphs
2
1200
44.4
110.2
Expressivity
SR25
25
300
SountingSub.
Count graph substructures
1500 / 1000
2500
18.8
62.6
GraphProp.
Regress graph properties
3
5120 / 640 / 1280
19.5
101.1
ZINC-12K
Molecular prop. regression
1
10000 / 1000 / 1000
28.1
49.8
Real World
CIFARIO
Multi-class class.
50000
110000
Graphs
PATTERN
Rerognize subgraphs
2
10000
2000
2000
118.9
6079.8
MolHIV
Binary class,
32901
/ 4113 / 4113
25.5
54.1
MolPCBA
Multi-label binary class.
128
350313
43793 / 13793
25.6
53.4
Proximity
h-Proximity
Binary classification
9000
117.14
1484.82
EXP and SR25. We evaluate ELENE on GIN and GIN-AK for both data sets with & E {0, 1,2). For ELENE-L, we evaluate all model variants for & E (0, 1.2) with 8-dim embeddings for EXP and 32-dim embeddings for SR25. All models use L = 4 for EXP and L. 2 for SR25.
-Counting Sub. and Graph Prop. We evaluate ELENE GIN and GIN-AK for both data sets with k E 1,, For ELENE-L, evaluate all model variants for k {0,1,2] with 16-dim embeddings. On the GraphProp dataset, we additionally try k 3 after noticing expected positive results during carly evaluation as larger values of enable the model to capture long-range dependencies. All models use
L = 3 for Counting Sub. and L = 6 for Graph Prop.
Real World Graphs. See benchmarkDatasets.. sh for details.
- -IICC and MolHIV. We evaluate ELENE on GIN and GIN-AK for both data sets with k E {0, 1, 1, For ELENE-L, we evaluate all model variants for k E (0, 1,,3) with 32-dim embeddings. All models use L = 6 for ZINC and L 2 for MolHTV.
PATTERN. We evaluate ELENE on GIN with (0, 1,2) and on GIN-AK+ k (0,1). For ELENE-L, we evaluate all model variants for (0, 1, with 64-dim embeddings. Suspecting that degree information may not play salient role in the sub-graph patterns, also evaluate the setting without degree information but found this slightly degrades performance compared to models that encode degree attributes. All models use L = 6.
CIFAR1O and MolPCBA. We evaluate node-centric ELENE-L (ND) with E (1, Due to computa- tional constraints, we prioritize training with = 3 given promising results in other lasks. On CIFAR, we discard uninformative degree information as graphs are information. We do not modify the architecture or hyper-parameters of the best-performing GNN-AK+ model reported in Zhao al. (2022). Our results report average and standard deviations of the evaluation metric Accuracy for CIFAR10, Average Precision (AP) for MolPCBA collected from 3 independent runs.
nearest neighbor graphs containing super-pixel
i-Prrximity. See proximityResulls... sh for details.
We evaluate node-centrie ELENE-L without degree information, which matches the configuration of SPNNs. We do not tune any parpemearaeetes, evaluating ELENE-L with & {3,5) fixing L 3 and using 32- dim. embeddings. The first layer in the network embeds the color information, for which the model needs to appropriately learn to ignore irrelevant colors. Due to constrained computational resources, we only evaluate two maximum distances for ELENE-L, 3 and 5, sharing embedding weights and introducing ego-nelwork signals before each of the GIN layers. We share ELENE-L embedding matrices across all layers and set the maximum encoded degree d = to only encode distance information. We report the mean and standard deviation of the binary classification accuracy computed across 10-folds over the dataset, following Abboud
et al. 2022
24

---

Published in Transactions on Machine Learning Research (04/2024)
Memory Scalability.
We provide additional results from the memory scalability experiments in S7 reporting memory consump
tion performance when dnax = 6 and dnax 18 in
Fig. 8 and
Fig.
Max. Memory Consumption (MB)
mmx
8192MB
Max.
4096MB
Jhase
2048MB
GA-AK
1024MB
(ND)
512MB
256MB
128MB
64MB
k= 3:
32MB
GIAAK
Gh-AA+
16MB
SLONE IND]
ELENE (60)
102
10225
102.5
102.55
103
10325
103.5
103.75
104
10425
104.5
Graph Size of Nodes)
Figure 8: Memory scalability analysis of ELENE with daaz = 6, produced as Fig. 7 line) and maximum GPU memory (dash-and-dotted line) as indicative lower and upper memory bounds. ELENE-L (ND, full lines) outperforms both GIN-AK, GIN-AK+ (dotted lines) and ELENE-L (ED, dashed lines). Additionally, ELENE-L (ND) can encode all d-regular graphs in the benchmark when 1. As expected, memory consumption increases linearly with the number of nodes daex is kept fixed.
We include GIN (dotted
Max. Memory Consumption (MB)
d max 18
8192MB
Max. aru Memooy jaase
4096MB
K 1:
2048MB
1024MB
CLINE (ND)
SLINE (ED)
512MB
k 2:
256MB
GIN-AK
GEN ACC
128MB
CLINE IND)
SLINE (D0)
64MB
32MB
100 GRRAK
GIR-ECT
16MB
102
20
20
102.55
103
3022
103.5
103.75
10a
10425
104.5
Graph Size (Nr. of Nodes)
Figure 9: Memory scalability analysis of ELENE with daax 18. See caption of Figure for details.
Graph Density and Scalability.
We also provide extended memory scalability results by studying the impact of the density of the graph. We ran additional experiments graphs where N = 1000, and evaluated the memory consumption as density increases as function of the degree of nodes in the graph. We perform the same experiment in two settings: one where the degree distribution is regular (i.e. the graphs are d-regular, studying different values of d), and one where the distribution of degrees is irregular. In the irregular case, we study the case in which all nodes have at least degree d, but may have higher connectivity following the Barabási-Albe preferential attachment model (Barabási & Albert 1999).
25

---

Published in Transactions on Machine Learning Research (04/2024)
Memory Consumption Regular Density Graphs. In Fig. 10 compare GIN, GIN-AK, GIN-AK and
ELENE variants at depths (1, Note that we could not include SPEN, as described in 97 due to reaching the maximum memory thresholds at dmax = 8.
Max. Memory Consumption (MB)
1000
8192MB
Hsase
4096MB
2048MB
GIN-AK
GIR-ACT
1024MB
ELTNE (ND)
CLINE
512MB
256MB
128MB
64MB
k 3:
32MB
S1:NE IND)
16MB
SLENE (80)
24
30
36
dmax (Max. Degree)
Figure 10: Memory scalability analysis of ELENE with N = 1000 in function of increasing values of dmax- See caption of Figure for details.
Memory Consumption on Irregular Density Graphs. In Fig. 11 we repeat the analysis from Fig. 10 on graphs generated following the preferential attachment model where each node has at least. m edges. We find that ELENE-L L (ND, full lines) outperforms both GIN-AK, GIN-AK+ (dotted lines) and ELENE-L (ED, dashod lines), matching $7.5 and results on regular connectivity patterns shown in Fig. 10
Max. Memory Consumption (MB)
1000 Max.
8192MB
GMN 15ase Inc)
4096MB
2048MB
1024MB
512MB
256MB
128MB
64MB
k 3:
32MB
GIN-AK
GIN AC1
16MB
SLINE (ND)
SLINE (00)
1
6
10
12
14
16
18
20
m (Edges per Node)
Figure 11: Memory scalability analysis of ELENE with N = 1000 in function of increasing values of dmii on random Barabási- Albert graphs. See caption Figure for details.
B.3 Best Syper-parameter.
In this section, we provide an overview of the best hyperparameters find for ELENE and ELENE-L. For simplicity, we only report the best performing model, i.e., not distinguishing belween enhancing a GIN or a GIN-AK+ model. We group together seper-parametes set at the dataset level (e.g. for the Counting Substructures or h-Proximity datascts), and report the hyper-parameters corresponding the best models reported in S7 In our summary, include the dest-performing ego-network feature with (a) the ego-network depth-
(b) the number of layers L,, and (c) the embedding layer size for ELENE-L.
26

---

Published in Transactions on Machine Learning Research (04/2024)
Table 7: Best typee--paameters for the for the top performing models after introducing explicit ego-network attributes as shown in S7 We report the syper-paramcters corresponding the best-performing model by looking the objective performance metric on each dataset, and resolve ties by selecting the model with the lowest memory footprint.
Emb. Size (ELENE-L)
Benchmark
Dataset
Task
Ego-Net Feature
A-hops
L-Layers
Ego-Net Features
EXP
Reach 100% Accuracy
4
32
SR25
GIN +ELENE-L (ED)
2
32
Triangle
GIN-AK +ELENE
Expr.
Counting Sub.
Tailed Tri.
GIN-AK ELENE
2
3
16
Star
GIN +ELENE-L (ND)
4- Cycle
GIN-AKT +ELENE
IsConn
GIN-AK +ELENE-L (ND)
Graph
Prop.
Diameter
GIN-AK GIN-AK++ELENEE +ELENE-L (ND)
3
16
Radius
GIN-AK +ELENE-L (ND)
ZINC-12K
GIN+ELENE-L (ND)
32
Real World
CIFARIO
GIN+ELENE-L (ND)
2
4
61
Graphs
PATTERN
GIN (ND)
64
MolHIV
GIN EELENE
2
N/A
MolPCBA
+IN+ELENE-L (ND)
5
64
h 3
3
Proximity
h-Proximity
GIN + ELENE-L (ND)
3
32
h 8
We summarise our findings in Tab. 7 For datasets and tasks where multiple models achieve comparable performance (i.e. same performance metric with the reported significant digits), we break ties by reporting the model with the lowest memory footprint across the tie.
C ELENE is Permutation Equivariant and Invariant
We show that ELENE is permutation equivariant at the graph level, and permutation invariant at the node level. As all operations that ELENE roquires are permutation oquivariant at the graph level, and permutation invariant at the node level, the same holds for ELENE representations.
Lemma 1. Given any v V for G EV, and given permuled graph G' (V', FV", of produced by permutation of node labels V V such that Vu E V + x(v) E V', V(u,v) E + (π(L), (()) E'.
All ELENE representations are permutation equivariant at the graph level:
2 &e B) (e ( B. b)
Furthermore, FLENE representations are permutation invariont at the node level:
c = & (0))) Yu V.T(v)
Proof. Note that et in Eq. can be exprossed in terms of de (ule) and (u, Both lo(;;) and del (+)-) are permutation invariant functions at the node level and equivariant at the graph level, they rely the dis- tance between nodes, which will not change when permutation x(-) is applied. Thus, ELENE representations are permutation equivariant at the graph level, and permutation invariant at the node level.
27


Reviews:
[{"review_id": "u0mvGEiu82", "reviewer": "Reviewer_ddSg", "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\n* The paper addresses an important problem of enhancing the expressivity and performance of graph learning, which is a challenging and practical task in machine learning. The paper is genuinely well-written with helpful illustration figures.\n* A novel and effective encoding of ELENE, which leverages the edge-level ego-network information to capture the structural signals of the input graph, is proposed to distinguish strongly regular graphs, a family of 3-WL equivalent graphs with theoretical groundings.\n* Extensive experiments and analysis demonstrate the advantages of ELENE and ELENE-L over existing methods on various datasets and tasks. The paper also shows that ELENE and ELENE-L improve memory usage by up to 18.3x compared to sub-graph GNN baselines.\n\nWeaknesses:\n* As pointed out by the authors, approaches [1-2] similar to ELENE have been proposed recently, but the difference between ELENE and [1-2] is not explicitly discussed. This is essential especially since the theoretical findings are built upon the results from [1]. Therefore, a detailed discussion between ELENE and [1-2] as well as the experimental comparison between them is needed to further clarify the motivation. \n\n* While Section 7.5 indicates the memory scalability of ELENE against GIN and GIN+AK, it is unclear whether ELENE could tackle graphs with massive nodes (more than 10^5). This concern arises since ELENE-L (ED) can hardly be employed on the reported real-world benchmark datasets (as indicated by the authors from Section 7.4). This might be available by introducing some large graph sampling techniques. \n\n* The performance of ELENE achieves incremental improvement over a small set of baselines. For example, in Table 3, ELENE could only achieve on-par performance on two datasets and weaker performance on the other three in comparison with the other baselines. Therefore, the evaluation could be more convincing by introducing more related baselines (such as [1-2]) or other real-world benchmarks that could better demonstrate the expressivity like the ones in Table 1. In other words, how the enhancement of expressivity could be reflected in real-world settings needs further demonstration.\n\n* In the discussion of memory usage comparison, it seems unfair to emphasize the comparison between GIN+ELENE and GIN-AK since the parameter complexity is different. From Table 4, it can be noticed that GIN+ELENE-L (ND) has comparable memory consumption against GIN-AK+ while GIN+ELENE-L (ED) uses more memory than GIN-AK+. Therefore, it would be better to conduct parameter complexity analysis to better reflect the memory usage analysis.\n\n* Minor issues: [2] is not correctly cited in its published journal. What is the difference between GIN-AK and GIN-AK+?\n\n\n[1] Beyond 1-WL with Local Ego-Network Encodings, LoG 22\n\n[2] Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting, TPAMI 22", "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": "The paper proposes a novel edge-level ego-network encoding for learning on graphs, called ELENE, which can enhance the expressivity and performance of message-passing graph neural networks (MP-GNNs). ELENE captures the structural information of the two ego networks of adjacent nodes in the input graph and can distinguish strongly regular graphs, a family of hard-to-differentiate graphs. The paper also introduces two variants of ELENE, one that is sparse and one that is learnable. It shows that they have different expressive power depending on whether they are node-centric or edge-centric. The paper evaluates ELENE and its variants on various graph learning tasks, such as graph classification, graph regression, and proximity tasks. The results show that they significantly match or improve the state-of-the-art methods while reducing memory usage.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please kindly refer to the Weaknesses.", "broader_impact_concerns": "The broader impact is fully discussed in the Broader Impact Statement section from my perspective.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7GHdoqQjHD", "reviewer": "Reviewer_o54i", "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- Novel, and rather interesting approach to graph learning methods, incorporating edge-level ego-network embeddings.\n- Theoretical results show improvement in terms of expressivity, matching, and surpassing expressivity results from IGEL. \n- *Technical validity*: The theorems seem correct, supporting the paper's arguments.\n- One of the most interesting and selling points of the method is their efficient memory usage. In particular, they seem to be superior with respect to another competitive baseline GIN-AK$^+$.\n\n**Weaknesses**\n- [Density analysis] Section 7.5 could benefit from a more detailed investigation of denser graphs. A plot similar to 7, but with increasing density would be very insightful to capture the impact of the parameter $d$ of the SRGs.\n- [Baseline Comparison] Since scalability is one of the main contributing axes of the method, it would be very helpful to report, also, the behavior of competing baselines with respect to increasing graph sizes (in Section 7.5).\n- In Table 3, baselines (CIN and GCN-AK$^+$ seem to outperform ELENE on 3 out of 5 tasks. However, I do not see that as a strong weakness, since the required memory consumption is higher for the baselines.", "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": "The authors introduce a novel edge-level ego-network encoding (ELENE) to enhance the learning capabilities of Message Passing Graph Neural Networks (MP-GNNs). ELENE improves expressivity by providing additional node and edge features and extends standard message-passing schemes. The encoding shows superiority in distinguishing a challenging class of 3-WL equivalent graphs, namely the Strongly Regular Graphs. \n\nTheir theorems seem to be correct, and provide expressivity results over ELENE, and ELENE-L configurations. The paper develops a thorough experimental framework for evaluating ELENE's contribution to graph learning tasks. Its empirical evaluation across various benchmarks shows that ELENE matches or exceeds existing baselines in tasks like graph classification and regression, with a significant reduction in memory usage.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Following my thoughts on *Weaknesses* section, I suggest that the following changes would further improve the paper:\n1. Inclusion of an increasing density for SRGs plot, showcasing the correlation with respect to the density. Thus, the authors can further validate the computational complexity claims.\n2. Inclusion of competing baselines in the scalability evaluation. Figures 7,8, and 9 show only the comparison with GIN.\n3. Another interesting addition would be the experimentation with different graph types (with more diverse density patterns) to further enhance the scalability claims.", "broader_impact_concerns": "The ethical implications are not discussed. I do not see however any particular reason of ethical implications that would require an addition of a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2iGWBixhhd", "reviewer": "Reviewer_suwS", "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\n- The paper is well written. It was easy for me to follow and understand the method.\n\n- The authors provide many comparisons with other methods, both qualitatively and quantitatively.\n\n- The method seems novel to me, and seems to be effective in practice.\n\n- The authors provide many details about the implementation and experimental settings.\n\nWeaknesses:\n \n- In page 1 the authors claim \"This flexibility extends the expressive power of MP-GNNs and their robustness,\". Can you please refer to the robustness aspect?\n\n- In page 5 the authors mention several subgraph GNNs method (\"GNN-AK,\nNGNNs, SUN, ESAN, or SPEN.\"), but their citation only comes several pages after. I would expect the citation to at least be in order of appearance in text. Thus I would recommend to include the references there as well.\n\n- In section 4, the authors first discuss a simple ELENE approach, but to my understanding there is no equation that defines it. Can you please add an equation so it is easier to compare the two proposed methods?\n\n- In equations 5 and 6, is gamma learned? or is it a hyperparameter? \n\n- The authors mention the over-squashing problem several times in the paper. Is there anything theoretical or practical that can be said about ELENE with respect to this problem?\n\n- In terms of \"subgraph expresiveness without running subgraph gnns\", the authors should cite and discuss \"Efficiently Counting Substructures by Subgraph GNNs without Running GNN on Subgraphs\"\n\n- In terms of lightweight / efficient subgraph GNNs, the authors should cite and discuss \"Ordered Subgraph Aggregation Networks\", \"MAG-GNN: Reinforcement Learning Boosted Graph Neural Network\", and \"Efficient Subgraph GNNs by Learning Effective Selection Policies‏\".\n\n- In terms of paths in GNNs, the authors discuss the shortest path MPNN, but I would appreciate it if the authors can also discuss the differences between works like \"pathGCN: Learning General Graph Spatial Operators from Paths‏ \", and \"Path neural networks: Expressive and accurate graph neural networks\".", "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": "The authors propose ELENE and ELENE(L), two approaches to include subgraph information in MPNNs without the need to run subgraph GNNs. The authors thoroughly discuss the relation of their paper to others, and provide strong motivation for the proposed method and research direction. \n\nThe method is nicely analyzed to show the expressive power of ELENE, followed by a significant amount of experiments and computational complexity, and cost analyses.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, I think that the paper is in great condition and is highly relevant. It should be published after minor changes, as described in my review.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three expert reviewers. All reviewers recommended acceptance of the paper and I agree with them. The reviewers initially raised concerns about the scalability of the proposed approach, the lack of baselines, the limited number of datasets and types of graphs. The reviewers also complained about missing related work. Those concerns were addressed by the authors in the revision and the quality of the paper improved significantly. I thus think that the paper is now ready for publication.
Decision: Accept (poster)