{'fraction_non_alphanumeric': 0.03238856286677488, 'fraction_numerical': 0.00963915594955675, 'mean_word_length': 4.476750547045952, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
k-hop Graph Neural Networks

Graph neural networks (GNNs) have emerged recently as a powerful architecture for learning node and graph representations. Standard GNNs have the same expressive power as the Weisfeiler-Leman test of graph isomorphism in terms of distinguishing non-isomorphic graphs. However, it was recently shown that this test cannot identify fundamental graph properties such as connectivity and triangle freeness. We show that GNNs also suffer from the same limitation. To address this limitation, we propose a more expressive architecture, k-hop GNNs, which updates a node's representation by aggregating information not only from its direct neighbors, but from its k-hop neighborhood. We show that the proposed architecture can identify fundamental graph properties. We evaluate the proposed architecture on standard node classification and graph classification datasets. Our experimental evaluation confirms our theoretical findings since the proposed model achieves performance better or comparable to standard GNNs and to state-of-the-art algorithms.


Introduction
In the past years, the amount of graph-structured data has grown steadily in a wide range of domains, such as in social networks and in chemoinformatics. Learning useful representations from graph data is essential for many real-world applications. For instance, in social network analysis, one might be interested in predicting the interests of users represented by the nodes of a network [35]. In biology, an issue of high interest is the prediction of the functions of proteins modeled as graphs [3]. These applications typically involve either node-focused or graph-focused tasks, the difference lying in the entity of interest, a node or a graph.
Graph Neural Networks (GNNs) have recently emerged as a general framework addressing both noderelated and graph-related tasks [4]. Although numerous GNN variants have been proposed in the past years [9,26,18,13,17,10,14,31,37], they all share the same basic idea, and can be reformulated into a single common framework. Specifically, GNNs employ a message passing procedure, where each node updates its feature vector by aggregating the feature vectors of its neighbors [7]. After k iterations of the message passing procedure, each node obtains a feature vector which captures the structural information within its k-hop neighborhood. These representations can be used as features for node-related tasks. For graph-related tasks, GNNs compute a feature vector for the entire graph using some permutation invariant readout function such as summing the feature vectors of all the nodes of the graph.
The GNN architectures have achieved state-of-the-art performance in many tasks such as in node classification and in link prediction. Furthermore, they have seen considerable success in graphrelated tasks even though they have faced intense competition from graph kernels, the approach that dominated the field for more than a decade [21]. With the exception of the work of Scarselli et al. [25], until recently, there has been little attempt to understand the properties and limitations of GNNs. It was clear though that there is a close connection between GNNs and the Weisfeiler-Lehman (WL) test of graph isomorphism [32], a powerful heuristic which can successfully test isomorphism for a broad class of graphs [1]. Similar to GNNs, the WL test iteratively updates a given node's label by aggregating the labels of its neighbors. Specifically, the algorithm augments the label of each node by the sorted multiset of labels of neighboring nodes, and compresses these augmented labels into new, short labels. To test graph isomorphism, this relabeling procedure is repeated until the label sets of the input graphs are not identical, or the number of iterations reaches a specific value.
Some recent studies have made attempts to formally characterize the expressive power of GNNs [19,34]. These studies have compared the expressiveness of GNNs with that of the WL test, and have shown that GNNs do not have more power in terms of distinguishing between non-isomorphic graphs than the WL algorithm. To make matters worse, it was recently shown that the WL subtree kernel (which capitalizes on the WL test) has insufficient expressive power for identifying fundamental graph properties [16]. It remains though unclear how GNNs encode subgraph/graph information into their learned representations, and whether they can identify such properties. Since these architectures are directly related to the WL test, they may also lack expressive power, and they may fail to identify these properties. Hence, the need for more powerful representations is more essential than ever.
Present Work. In this paper, we further analyze the representational power of GNNs. Specifically, we study if GNNs can identify specific properties of graphs. We say that a GNN identifies a property if no two graphs are mapped to the same feature vector unless they both have or both do not have the property. We demonstrate that the standard GNN fails to identify fundamental graph properties such as connectivity, bipartiteness and triangle-freeness. We show that this limitation of GNNs stems from the myopic nature of the message-passing procedure which only considers the direct neighbors of each node. To account for that, we propose a novel architecture, called k-hop-GNNs, which takes into account not only the immediate neighbors of each node, but its whole k-hop neighborhood. By updating node features using not only the direct neighbors, but taking into account the entire k-hop neighborhood, we can capture structural information that is not visible when aggregating only the 1-hop neighborhood. The proposed model is strictly more powerful than the standard GNN architecture. Furthermore, in contrast to the GNN framework, the proposed architecture is capable of distinguishing global properties such as connectivity. We demonstrate the proposed architecture in a variety of node and graph classification tasks. The results show that the proposed k-hop-GNNs are able to consistently outperform traditional GNNs on most datasets. Our main contributions are summarized as follows: • We show that standard GNNs cannot identify essential graph properties such as connectivity, bipartiteness and triangle-freeness • We propose k-hop-GNNs, a novel architecture for performing machine learning on graphs which is more powerful that traditional GNNs.
• We evaluate the proposed architecture on several node classification and graph classification datasets, and achieve performance better or comparable to standard GNNs and to state-ofthe-art algorithms.
The rest of this paper is organized as follows. Section 2 introduces some preliminary concepts and summarizes the standard graph neural network model. Section 3 analyzes the expressive power of the graph neural network model highlighting its limitations. Section 4 presents the proposed model for performing machine learning tasks on graph-structured data, and shows that it is theoretically more powerful than the standard graph neural network architecture. Section 5 evaluates the proposed architecture on several standard datasets. Finally, Section 6 concludes.

Preliminaries
We start by fixing our notation, and we then present the standard graph neural network framework.

Notation
Let G = (V, E) be an undirected graph consisting of a set V of nodes and a set E of edges between them. We will denote by n the number of nodes and by m the number of edges. The neighborhood of radius k (or k-hop neighborhood) of a node v ∈ V is the set of nodes at a distance less than or equal to k from v and is denoted by N k (v). Given a set of nodes S ⊆ V , the subgraph induced by S is a graph that has S as its node set and it contains every edge of G whose endpoints are in S. The neighborhood subgraph of radius k of a node v ∈ V is the subgraph induced by the neighborhood of radius k of v and v itself, and is denoted by G k v . A node-labeled graph is a graph with labels on nodes. That is, given a set of labels L, there exists a function : V → L that assigns labels to the nodes of the graph. Instead of discrete labels, nodes may also be annotated with multiple categorical or real-valued properties. These graphs are known as attributed graphs.

Graph Neural Networks
For graphs with discrete node labels, these vectors usually correspond to some representations (e. g., one-hot encoding) such that two nodes v and u have identical feature vectors if and only if (v) = (u). For attributed graphs, these feature vectors may be set equal to the attribute vectors of the nodes. For instance, in biology, proteins are represented as graphs where nodes correspond to secondary structure elements and the feature vector of each secondary structure element contains its physical properties. For graphs without node labels and node attributes, these vectors can be initialized with a collection of local vertex features that are invariant to vertex renumbering (e. g., degree, k-core number, number of triangles, etc). A GNN model consists of a series of neighborhood aggregation layers. Each one of these layers uses the graph structure and the node feature vectors from the previous layer to generate new representations for the nodes. The feature vectors are updated by aggregating local neighborhood information.
Suppose we have a GNN model that contains T neighborhood aggregation layers. In the t th neighborhood aggregation layer (t > 0), the hidden state h (t) v of a node v is updated as follows: By defining different AGGREGATE (t) and MERGE (t) functions, we obtain a different GNN variant.
For the GNN to be end-to-end trainable, both functions need to be differentiable. Furthermore, since there is no natural ordering of the neighbors of a node, the AGGREGATE (t) function must be permutation invariant. There are numerous concrete implementations of the above GNN framework. Some of them integrate the AGGREGATE (t) and MERGE (t) steps into a single function [14,37] as follows: is a multi-layer perceptron of the t th neighborhood aggregation layer. Note that the majority of the proposed models use 1-layer perceptrons instead of MLPs. Another widely-used GNN model is implemented as follows [17]: where again MLP For node-level tasks, the node feature vectors h (T ) v of the final neighborhood aggregation layer are usually passed on to a fully-connected neural network. For graph-level tasks, GNNs apply a READOUT function to node representations generated by the final neighborhood aggregation layer to obtain a vector representation over the whole graph: Similarly to the AGGREGATE (t) function, the READOUT function is necessary to be differentiable and permutation invariant. A common READOUT function computes the mean of the representations of the nodes: However, there have also been proposed more sophisticated functions based on sorting [37], on concatenation across the iterations/layers [34] and on clustering [30,36].

Limitations of the Standard GNN Model
To gain theoretical understanding of the properties and weaknesses of GNNs, we capitalize on concepts introduced by Goldreich in the context of property testing [8], and further refined by Kriege et al. for investigating the expressive power of graph kernels [16].
Let G n be the set of graphs on n vertices, where n ∈ N. A graph property is a set P of graphs that is closed under isomorphism. We denote the set of graphs in P on n vertices by P n . In this paper we study the following three fundamental graph properties: (1) connectivity, (2) bipartiteness, and (3) triangle-freeness. A graph is connected if there is a path from any vertex to any other vertex in the graph. A graph G = (V, E) is bipartite if its set of vertices V can be decomposed into two disjoint sets V 1 and V 2 , i. e., V = V 1 ∪ V 2 , such that every edge e ∈ E connects a vertex in V 1 to a vertex in V 2 . Finally, a graph is triangle-free if it does not contain a triangle (i. e., a cycle of three vertices). Following Kriege et al. [16], we say that a GNN can identify a property if no two graphs obtain the same representation unless they both have or both do not have the property.
Definition 1. Let P be a graph property. If for each n ∈ N, a GNN produces different representations for every G 1 ∈ P n and G 2 ∈ P n , i. e., it holds that h G1 = h G2 , then we say that P can be identified by the GNN.
We next study if the standard GNN architecture can identify the above three graph properties. We assume that either all nodes or nodes with the same degree are annotated with the same feature vector. We first show that the standard GNN produces exactly the same representation for the nodes of all regular graphs of a specific degree in G n for some n ∈ N.
Lemma 1. The standard GNN maps the nodes of two regular graphs of the same size and degree to the same feature vector.
Proof. Let G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) be two two non-isomorphic regular graphs of the same degree with the same number of vertices. We show for an arbitrary iteration t ≥ 1 and nodes v2 . All nodes have the same initial representation, hence, in iteration 0, it holds that h } be the multisets of feature vectors of the neighbors of v 1 and v 2 , respectively. By the induction hypothesis, we know that M v1 = M v2 and that h such that independent of the choice of the AGGREGATE (t) and MERGE (t) functions in Equation 1, we get h v2 . This holds as the input to both functions AGGREGATE (t) and MERGE (t) is identical. This proves that h v2 , and thereby the lemma.
Interestingly, since the standard GNN produces identical feature vectors for the nodes of all regular graphs of a specific dergee in G n for some n ∈ N, then it also produces identical representations for the graphs themselves. We next show that the GNN architecture cannot identify the three graph properties defined above since for each one of these properties, there exists one regular graph in P n and another regular graph of the same degree in G n \ P n .   Proof. Consider a cycle with six vertices (graph G 2 ) and two triangles with three vertices (graph G 1 ) as illustrated in Figure 1. Both G 1 and G 2 are regular graphs of the same degree with the same number of vertices. Hence, according to Lemma 1, after T neighborhood aggregation steps, the nodes of both graphs have obtained identical representations, i. e., h Therefore, independent of the choice of the READOUT function in Equation 3, the two graphs will have identical representations, h G1 = h G2 , since the input to the READOUT function is identical. Clearly, G 1 is disconnected, while G 2 is connected. Hence, these two graphs correspond to a counterexample to the distinguishability of connectivity. Furthermore, consider the graphs G 3 and G 4 as illustrated in Figure 2. Note that G 3 contains triangles, but is not bipartite, whereas G 4 is bipartite, and triangle-free. Both G 3 and G 4 are regular graphs of the same degree with the same number of vertices. Therefore, they obtain identical representations h G3 = h G4 , and correspond thus to a counterexample to the distinguishability of the above two properties.

k-hop Graph Neural Networks
In this section, we propose a generalization of GNNs, so-called k-hop Graph Neural Networks (k-hop GNNs). This new model consists of neighborhood aggregation layers that do not take into account only the direct neighbors of the nodes, but their entire k-hop neighborhood. Hence, instead of the neighborhood aggregation layer shown in Equation 1, the proposed model updates the hidden state h (t) v of a node v as follows: We next present an instance of the proposed architecture which is strictly stronger than standard GNNs in terms of distinguishing non-isomorphic graphs, and is capable of identifying graph properties which are not captured by the standard GNN architecture.

Proposed Architecture
Let G = (V, E) be a graph. In what follows, we will focus on a single node v ∈ V , and we will present how the representation of this node is updated during the neighborhood aggregation phase.
Node v will also be referred as the root of the k-hop neighborhood subgraph G k v . For a given iteration/layer t, and a root node v, we define an inner representation x u of each node u ∈ N k (v) and we initialize it as x u = h (t−1) u . We will next describe how the hidden state h (t) v of the root v is computed. Let UPDATE(w, S) denote a module which takes as input a node w and a set of nodes S, and is defined as follows: where MLP, MLP 1 , MLP 2 are multi-layer perceptrons and x v , x u are the inner representations of nodes w and u, respectively. The proposed approach uses a series of UPDATE modules to update the representations of the nodes that belong to the k-hop neighborhood of v, following a sequential procedure from the most distant ones to the direct neighbors of v. Although the neural network learns a new vector representation for some of the nodes u ∈ N k (v), these feature vectors are only calculated in the context of updating the root node's representation. Hence, after computing the new representation h (t) v of v, these representations are not useful any more. These inner representations should not be confused with the h (t) u representation that the network learns for each of these nodes by taking into account their own k-hop neighborhoods.
denotes the ring of nodes at distance d, which we refer to as the nodes at level d. Note that the neighbors of a node u ∈ R d (v) belong to one of the next three sets: . Specifically, u cannot be connected with nodes at levels l > d + 1 because then these nodes would belong to level d + 1 instead of l. Furthermore, u cannot be connected with nodes at levels l < d − 1 because then u would belong to some level smaller than d. Given a node u ∈ N k (v), the inner representation x u of u is updated at most twice. The two updates aggregate information from the neighbors of u that are located at the immediately higher and at the same level of the neighborhood subgraph, respectively. Hence, the proposed model performs the following two types of updates of inner representations: (1) updates across rings of nodes, and (2) updates within a ring of nodes. We next present these two updates in detail: • Updates across rings of nodes: Let u ∈ R d (v) be a node that belongs to the k-hop neighborhood of v and whose shortest path distance from v is equal to d. Let also If B is not empty, the representation x u of u is updated as follows: Otherwise, if u has no neighbors at the next higher level (i. e., N 1 (u) ∪ R d+1 (v) is empty), then its representation is not updated.
• Updates within a ring of nodes: If u has one or more neighbors at the same level of G k v , and hence D = N 1 (u) ∩ R d (v) is not empty, the representation x u of u is re-updated as follows: The proposed approach starts from the most distant nodes and follows a sequential procedure updating the feature vectors of nodes that are gradually closer to the root. The first type of update (across rings) precedes the second (within a ring). After all its direct neighbors u ∈ N 1 (v) have been processed, the hidden state of the root node v is computed as follows: 0,across v, N 1 (v) As mentioned above, although the model learns a new inner representation x u for some of the nodes in N k (v), these representations are only learned for the purpose of updating the root node's hidden state. Furthermore, it is clear that for a single neighborhood aggregation layer, the proposed model needs at most 2k UPDATE modules. As we will show next, the proposed model can capture the structural information within the root node's k-hop neighborhood even if it comprises of a single neighborhood aggregation layer. Hence, instead of using multiple neighborhood aggregation layers/iterations, it is more suitable to increase the value of k. The various steps of the proposed model are illustrated in Algorithm 1.
After T iterations (i. e., T neighborhood aggregation layers), the emerging node feature vectors h   Figure 3: The 2-hop neighborhood graph G 2 v1 of a node v 1 of graph G.

Example
We next provide a simple example that illustrates the update procedure that was presented above. Specifically, Figure 3 shows the 2-hop neighborhood graph G 2 v1 of a node v 1 ∈ V . As mentioned above, we first consider the most distant nodes (i. e., nodes v 4 and v 5 since v 4 , v 5 ∈ R 2 (v 1 )). The representations of nodes v 4 and v 5 are not updated since these two nodes are at the frontier of G 2 v1 . Furthermore, there is no edge between the two nodes. However, these two nodes contribute to the update of the representation of node v 2 . Specifically, the inner representation of node v 2 is updated as follows: x v2 = UPDATE (t) 1,across v 2 , {v 4 , v 5 } Then, we update the inner representations of nodes whose shortest path distance from the root is 1 and which are connected with other nodes with the same distance from the root. There is one such pair of nodes (i. e., nodes v 2 and v 3 ) which are updated as: Finally, we update the root by aggregating information from its direct neighbors:

Expressive Power
We next study the identifiability of the proposed k-hop GNN. The following Theorem comprises the main results about graph properties that can be identified by the proposed model.

Computational Complexity.
Of course, the increase of expressiveness does not come without a price. Clearly the time complexity of the k-hop GNN is higher than that of the standard GNN. The model needs to extract the khop neighborhoods of all nodes. This can be done in linear time in the number of edges in the neighborhood of each node. Hence, its complexity is O(nm) in the worst case. Furthermore, to update the representations of the nodes, the model requires the use of three MLPs for each edge of the k-hop neighborhood subgraphs. However, for sparse graphs and small values of k, the number of edges in each k-hop neighborhood is small and therefore, the complexity is low (constant in practice).

Experimental Evaluation
In this Section, we evaluate the performance of the proposed k-hop GNN in two tasks: (1) node classification, (2) graph classification. We compare the performance of the proposed model against the standard GNN architecture and against strong baselines.

Node Classification
The main objective of node classification is to assign class labels to unlabeled nodes. Each node v i ∈ V has an associated class label y i and the goal is to learn a representation vector h Datasets. We evaluate the proposed model on synthetic graphs with planted structural equivalences. To generate the graphs, we follow the same procedure as in [5]. Structurally equivalent nodes are assigned the same class labels.
All the generated graphs consist of a cycle of length 40 and some basic shapes ("house", "fan", "star") which are regularly placed along the cycle. In the "basic" setup, 10 instances of only one of the three types (randomly chosen with uniform probability) are placed along the cycle. In the "varied" setup, 10 instances of each one of the three shapes are randomly placed along the cycle. The use of multiple shapes increases the number and complexity of the structural role patterns, posing a challenge to the learning algorithms. To assess how the algorithms perform in noisy scenarios, we introduce two additional configurations ("basic perturbed" and "varied perturbed") where we add edges uniformly at random on the generated graphs. The number of edges that are added is equal to 10% of the edges of the graph.

Baselines.
We compare the proposed model against three recent state-of-the-art techniques for learning structural node representations: (1) RolX, a method based on non-negative matrix factorization of a node-feature matrix that describes each node based on this given set of latent features [11], (2) struc2vec, a method which learns structural node embeddings through a sequence of walks on a multilayered graph [24], and (3) GraphWave, an algorithm that builds upon techniques from signal processing and generates a structural embedding for each node based on the diffusion of a spectral graph wavelet centered at the node [5]. Note that these three algorithms are unsupervised, in the sense that they only take a graph as input and not any class labels of the nodes. We also compare the k-hop GNN model against DeepWalk, a method for learning node representations such that nodes that reside in close network proximity are assigned similar latent representations [22]. Besides the above four methods, we also compare the proposed model against the standard GNN architecture as described in Equation 1.
Experimental setup. For each configuration, we generate 20 graphs using the procedure described above. For each graph, we perform 10-fold cross validation. We repeat the whole process 25 times. We measure the performance of the different algorithms using the following two evaluation metrics: (1) average accuracy and (2) average F1-score.
For the unsupervised algorithms, we learn an embedding for each node, and we predict the class label of each node in the test set using a 4-nearest neighbors classifier. For all baselines, we use the default parameter values. Specifically, for struc2vec, we set the probability that the random walks stays in current layer to 0.3, the dimensionality of the embeddings to 128, the number of epochs to 5, the number of walks per node to 10, the walk length to 80 and the context window size to 10.  For DeepWalk, we set the dimensionality of the embeddings to 128, the number of epochs to 5, the number of walks per node to 80, the walk length to 40 and the context window size to 10. Finally, for RolX, we did not use any approach for automatically detecting the number of different roles, but we directly provided the algorithm with the correct number of roles. For the proposed k-hop GNN model and the standard GNN model, we train the models on the training set of each fold and use the models to classify the nodes of the test set. We use 2 and 3 neighborhood aggregation layers for the standard GNN, and 1 layer for the proposed 2-hop and 3-hop GNNs. The neighborhood aggregation layers of all architectures consist of MLPs with 2 layers. Batch normalization is applied to the output of every neighborhood aggregation layer. The hidden-dimension size of the MLPs was set equal to 8. Moreover, we used the Adam optimizer with a learning rate of 10 −2 , and we trained the neural networks for 200 epochs.
Results. Table 1 shows that the instances of the proposed k-hop GNN architecture outperform all the baselines in the node classification task. DeepWalk is the worst-performing method. This is not surprising since this method cannot capture structural similarity. Regarding the remaining methods, in the least challenging configuration ("basic"), the k-hop GNN models, and RolX perform the best. All these methods yield perfect performance, while the standard GNN models and GraphWave exhibit slightly worse performance. In the presence of noise ("basic perturbed" configuration), the performance of all methods degrades a lot. Specifically, the 2-hop GNN model is the best-performing method followed by the 3-hop GNN model, RolX, GraphWave, and the two standard GNN models, in that order. DeepWalk and struc2vec perform much worse than the other methods in that configuration.
In the "varied" configuration, the k-hop GNN models are once again the best-performing methods along with RolX. In the "varied perturbed" configuration, the 2-hop GNN model yields the best performance. The 3-hop GNN model achieves slightly worse performance, while the performance of the remaining methods is much lower. From the two noisy configurations, it is clear that the baseline methods are more prone to noise compared to the k-hop GNN model. Furthermore, regarding the  Table 2: Average classification accuracy of GNNs and the proposed k-hop GNN models on the 3 synthetic datasets.
two instances of the k-hop GNN model, the 2-GNN model outperforms the 3-hop GNN model in all but one ("basic" where they achieve the same performance) configurations. This is probably related to the structure of the employed shapes. It should be mentioned that the diameter of all three shapes is equal to 2. Finally, the proposed k-hop GNN models outperform the two standard GNN models in all experiments, thereby validating our theoretical results. Overall, the proposed k-hop GNN model is robust and achieves good performance, demonstrating that it can learn high-quality node representations.

Graph Classification
We next apply the proposed architecture to the problem of graph classification, i. e., the supervised learning task of assigning a graph to a set of predefined categories. Specifically, given a set of graphs {G 1 , . . . , G N } ⊆ G and their class labels {y 1 , . . . , y N }, the goal is to learn a representation vector h Gi such that the class label of every graph of the test set can be predicted as y i = f (h Gi ). For this task, we are going to evaluate the performance of the proposed model in two different types of datasets: (1) synthetic datasets containing graphs that satisfy or do not satisfy the considered graph properties, and (2) standard widely-used datasets from real-world scenarios.

Synthetic Datasets
In this set of experiments, we seek to identify potential benefits of our proposed k-hop GNN architecture over the standard GNN model.

Datasets.
In order to investigate if the proposed model can distinguish triangle-freeness, bipartiteness and connectivity, we created three synthetic datasets. Each one of these datasets consists of 800 4-regular graphs. All the graphs have the same size (60 nodes), and each graphs is assigned a class label which denotes whether it satisfies the corresponding property or not (i. e., binary classification task). All the nodes are assigned identical labels. Furthermore, all three datasets are balanced, i. e., half of the graphs (400 graphs) satisfy the examined graph property, while the rest of the graphs (400 graphs) do not satisfy it.
Baselines. We compare our model against the standard GNN architecture of Equations 1 and 3. Based on our theoretical results, we expect the standard GNN model to perform much worse than the proposed model on these 3 datasets.
Experimental Setup. To measure the performance of the 4 models, 10-fold cross-validation was employed.
For the proposed k-hop GNN models (2-hop GNN and 3-hop GNN), we used a single neighborhood aggregation layer, while for the standard GNN, we used 2 and 3 layers. The hidden-dimension size of these layers was chosen from {16, 32, 64}. To generate graph representations, we employed a readout function that sums the vector representations of the nodes. The generated graph representations are then fed into a two layer MLP, with a softmax output. We used the ReLU activation function, and we chose the batch size from {32, 64, 128}. We used the Adam optimizer with a learning rate of 10 −2 , while we set the number of epochs to 100.
Results. We report in Table 2 average prediction accuracies across the 10 folds. It is clear that the standard GNN architectures are unable to distinguish the 3 graph properties. Specifically, they all achieve an average accuracy equal to 50% on all three datasets which can be attributed to the balanced splits of the training/test sets. On the other hand, the proposed k-hop GNN architectures achieved much higher average accuracies, indicating that the proposed architecture can distinguish the 3 properties in regular graphs. In the case of bipartiteness, the 3-hop GNN model yielded perfect performance, while in the case of connectivity, its average accuracy was also very high. The performance of the 2-hop GNN model was slightly worse than that of the 3-hop GNN model. However, the former managed to better distinguish triangle-free graphs than the latter. Overall, we can conclude that in contrast to the GNN architectures, the proposed architecture leads to more expressive node representations which allow it to capture more accurately the structural properties of graphs.

Real-World Datasets
We evaluate the proposed k-hop GNN model on standard graph classification datasets derived from bioinformatics, chemoinformatics, and from social networks.
Datasets. We use the following 3 datasets from bioinformatics and chemoinformatics: (1) MUTAG, (2) PROTEINS, (3) NCI1. We also use the following 2 social interaction datasets: (1) IMDB-BINARY, (2) IMDB-MULTI. We next give more details about the employed datasets 1 . MUTAG consists of 188 mutagenic aromatic and heteroaromatic nitro compounds. The task is to predict whether or not each chemical compound has mutagenic effect on the Gram-negative bacterium Salmonella typhimurium. PROTEINS comprises of 1, 113 proteins represented as graphs where vertices are secondary structure elements and there is an edge between two vertices if they are neighbors in the amino-acid sequence or in 3D space. The task is to classify proteins into enzymes and non-enzymes. NCI1 contains 4, 110 chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines. Each enzyme is a member of one of the Enzyme Commission top level enzyme classes (EC classes) and the task is to correctly assign the enzymes to their classes. IMDB-BINARY and IMDB-MULTI contain 1, 000 and 1, 500 movie collaboration graphs, respectively.
Note that the social network graphs are unlabeled, while all other graph datasets come with dicrete node labels. Hence, for the social network graphs, we assign an one-dimensional feature to each node which is equal to its degree, while for the remaining datasets, we use one-hot encodings of the node labels.
Experimental Setup. We performed 10-fold cross-validation where 10% of the graphs of each training fold was used as a validation set. The whole process was repeated 10 times for each dataset and each approach.
We chose parameters for the graph kernels as follows. For the Weisfeiler-Lehman subtree kernel and for the Weisfeiler-Lehman optimal assignment kernel, we chose the number of iterations from h = {4, 5, 6, 7}, while the graphlet kernel that we implemented samples 500 graphlets of size up to 6 from each graph. For the proposed k-hop GNN models (2-hop GNN and 3-hop GNN), we used a single neighborhood aggregation layer, while for the standard GNN, we used 2 and 3 layers. The parameters of the neighborhood aggregation layers correspond to MLPs with 2 layers. Batch normalization is applied to the output of every neighborhood aggregation layer. The hiddendimension size of the MLPs was chosen from {16, 32, 64}. To generate graph representations, we employed a readout function that sums the vector representations of the nodes. The generated graph representations are then fed into a two layer MLP, with a softmax output. We used the ReLU activation function, and we chose the batch size from {32, 64, 128}. We used the Adam optimizer with an initial learning rate of 10 −3 and decay the learning rate by 0.5 every 50 epochs. We set the number of epochs to 500, and we select the epoch with the best validation accuracy.
Results. We report in Table 3 Table 3: Average classification accuracy (± standard deviation) of the baselines and the proposed k-hop GNN models on the 5 graph classification benchmark datasets. The "Average Rank" column illustrates the average rank of each method. The lower the average rank, the better the overall performance of the method.
of actors and actresses. The diameter of these graphs is at most equal to 2, and therefore, the 3-hop neighborhoods of the nodes are identical to their 2-hop neighborhoods. This is why we do not report the performance of the 3-hop GNN on these two datasets.
In general, we observe that the variants of the proposed model achieve high levels of performance. Specifically, they achieve the second best performance on MUTAG, the third best performance on IMDB-BINARY, and the fourth best performance on the NCI1 and IMDB-MULTI datasets. On most datasets, the proposed model yields only slightly worse accuracies compared to the best performing method, the WL-OA kernel. Interestingly, the two k-hop GNN models perform equally well in general. More specifically, the 3-hop GNN achieves slightly better accuracy than the 2-hop GNN on most datasets. However, the difference in performance is not very large. Furthermore, it should be mentioned that the proposed k-hop GNN models outperform the two standard GNN models on all datasets, demonstrating their superiority. Overall, the proposed architecture yields good performance, demonstrating that it can learn not only high-quality node representations, but also graph representations.

Conclusion
In this paper, we analyzed the expressive power of GNNs, showing that a wide class of GNN architectures cannot identify fundamental properties of graphs such as triangle-freeness and bipartiteness.
To account for that, we proposed a generalization of GNNs, so-called k-hop GNNs, which update a node's representation by aggregating information not only from its direct neighbors, but from its k-hop neighborhood. This new model is strictly stronger then GNNs in terms of distinguishing non-isomorphic graphs and is capable of identifying graph properties that are not captured by standard GNNs. We evaluated the proposed model on standard node classification and graph classification datasets. The empirical results validated our theoretical findings since the proposed model achieved performance better or comparable to standard GNNs and to state-of-the-art algorithms.
modules can generate different representations for the nodes of a neighborhood subgraph of a disconnected graph compared to those of the nodes of the neighborhood subgraph of a connected graph.
Bipartiteness It is well-known that a graph is bipartite if and only if it does not contain an odd cycle. If G is bipartite and l is the length of the smallest odd cycle in G, then the k-hop neighborhood subgraphs (k ≥ l−1 2 ) of more than one nodes contain a cycle of odd length. According to Lemma 3 (below), the k-hop neighborhood subgraph of a node v contains a cycle of odd length if and only if the shortest path lengths from two adjacent nodes u, w ∈ N k (v) to v are identical. In other words, there exist two nodes both at the same level i of the k-hop neighborhood subgraph of node v that are connected to each other with an edge. During the process of updating the representation of the root v, the feature vectors of these nodes are also updated as follows: x u = UPDATE (0) i,within u, D . This update does not take place in the case of a non-bipartite graph since D = ∅ for all nodes of all neighborhood subgraphs. Based on Lemma 2, these nodes can obtain different representations from all the representations of the nodes of a neighborhood subgraph extracted from a bipartite graph. Lemma 3. Let G k v be the k-hop neighborhood subgraph of a node v. Then, G k v contains a cycle of odd length if and only if the shortest path lengths from two adjacent nodes u, w ∈ N k (v) to v are identical.
Proof. Let u, w be two vertices such that u, w ∈ N k (v). Assume that the shortest path lengths between each of these two vertices and the root v are identical and equal to d ∈ N such that d ≤ k. If u and w are connected by an edge, then G k v contains a cycle of length 2d + 1 which is clearly an odd number. This proves the first statement. For the second statement, assume that G k v contains a cycle of odd length and there is no edge between two vertices whose shortest path lengths from the root v are identical. Then, from all the nodes of the cycle, there is a single node u such that the shortest path distance d ∈ N from the root v to u is maximum. Since this is a cycle, there are two paths from v to u of length d. Hence, the length of the cycle is 2d which is an even number, contradicting the assumption.