{'fraction_non_alphanumeric': 0.024864064534245528, 'fraction_numerical': 0.00673933576698236, 'mean_word_length': 4.931859479103574, 'pattern_counts': {'":': 0, '<': 0, '<?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}}
Inductive Graph Embeddings through Locality Encodings

Learning embeddings from large-scale networks is an open challenge. Despite the overwhelming number of existing methods, is is unclear how to exploit network structure in a way that generalizes easily to unseen nodes, edges or graphs. In this work, we look at the problem of finding inductive network embeddings in large networks without domain-dependent node/edge attributes. We propose to use a set of basic predefined local encodings as the basis of a learning algorithm. In particular, we consider the degree frequencies at different distances from a node, which can be computed efficiently for relatively short distances and a large number of nodes. Interestingly, the resulting embeddings generalize well across unseen or distant regions in the network, both in unsupervised settings, when combined with language model learning, as well as in supervised tasks, when used as additional features in a neural network. Despite its simplicity, this method achieves state-of-the-art performance in tasks such as role detection, link prediction and node classification, and represents an inductive network embedding method directly applicable to large unattributed networks.

• Our work shows that structural relationships within a graph can be represented in a compact embedding space, and that the resulting embedding vectors are effective in supervised and unsupervised learning tasks.
• The proposed local encodings generalize to unseen graphs from the same domain in a multi-label node classification setting, outperforming methods based on Graph Convolutional Networks.
• Our experiments show that execution times scale polynomially as the number of nodes grow in randomly generated graphs under equivalent generation parameters.
representation learning, structural node similarity

Introduction
Graph structures are the natural way to represent arbitrary relationships in complex domains. Because of their generality, they can be applied to problems in which represented entities display rich interactions between each other. However, compactly capturing such interactions is a non-trivial task, often made unfeasible, for example, by the high-dimensionality and complexity of real-world networks.
Representation learning has been successfully applied to graphs, capturing useful interactions in compact ways [5]. The learned representations can be used for downstream machine learning tasks, and have seen applications as varied as molecule generation for drug design [15], content recommendation in social platforms [21], or social network analysis [13].
A wide array of learning approaches have focused on local node features and interactions. Transductive approaches require all nodes in the graph to be available at training time to learn a representation for each of them. Transductive methods can capture rich relationships within networks in a scalable manner. However, the resulting representations do not generalize to unseen nodes or edges, and require additional attention to deal with label permutations.
In contrast, inductive approaches [4] aim to compactly represent network interactions so that the specific identity of a node is irrelevant to its representation. Inductive representations are typically derived from attributes of nodes and edges within their neighbourhoods. In either case, inductive models tend to be more demanding than their transductive counterparts, particularly when entire graphs or node neighbourhoods ought to be sampled during training [7].
In this paper, we introduce IGEL (Inductive Graph Embeddings through Locality Encoding), a novel inductive method for learning structural graph embeddings. IGEL aims to overcome the aforementioned issues in previous works by representing network structures explicitly, in the form of neighbourhood structure dictionaries. Dense vector representations are then learned from the structural dictionaries, in either an unsupervised graph-dependent process or under full supervision for a target task.
We organize the paper as follows: in Section 2, we discuss the main lines of ongoing research in the state-of-the-art. Afterwards, we describe our model in Section 3. In Section 4 we present experimental results which consider different learning settings and an empirical anslysis of the complexity of IGEL. Finally, we discuss our results and conclude in Section 5.

Related Work
In this section, we briefly review the contributions most related to our work, grouping them according to their setting and their associated limitations. We then describe IGEL in this context, and give an introduction to how the method serves as a solution to existing problems. For a more comprehensive review of graph embedding techniques at large, we refer the reader to existing surveys [2,19].

Unattributed Graph Embeddings
First approaches to learning graph representations were applicable in unattributed settings as exemplified by models such as DeepWalk [13]. Deep-Walk reduces the problem of learning compact node representations to the task of training a word2vec [10] skip-gram language model over sequences of node labels sampled with random walks generated from a graph. Later, node2vec [3] further extended this idea by introducing additional parameters to control the locality of the random walks, and thus, the properties of the learned latent spaces.
An alternative transductive approach, LINE [16], tackled the problem by learning representations on the basis of structure. LINE minimizes the KL-divergence between the probability distribution of distinguishing adjacent nodes and between nodes with similar edges out of learned representations. The use of pairwise similarity measures has been further explored more recently by VERSE [17]. VERSE tailors similarity measures such as personalized PageRank or SymRank into the loss function, aiming to capture explicit properties from underlying network relationships in contrast to context-based language models.
Problem A. The aforementioned methods are scalable and showed remarkable results in representing graphs in varied settings. However, they are limited by their nature as transductive approaches, namely, that the representations do not generalize to unseen nodes, edges or graphs.

Convolutional Graph Networks
More recently, research has focused on methods that learn inductive graph representations. Inductive representations are attractive as they can be applied on either transductive or inductive settings, so long as the same attributes are available on seen and unseen problem instances. Early models, such as Planetoid [20] derived their representations from an embedding layer in a neural network whose input included node attributes, to perform semisupervised training on classification tasks.
However, a key component of graph data is that connected nodes can hold profound relationships between each other. Capturing those relationships can be a complex task, and much work has been devoted to it, particularly on works with Graph Convolutional Networks (GCNs) [12]. GCNs aggregate features from local neighbourhoods and the attributes of their nodes in order to generate a new feature representation for a given node. Because of this, they are ideal to capture the interactions between nodes and their neighbours. As such, GCNs have been successfully applied tasks such as semi-supervised learning [7] or node classification [18]. However, training GCNs when working on massive graphs is a challenge.
In this direction, some work has focused on sampling the graph during training, as proposed by LGCL [1] and GraphSAGE [4]. LGCL starts from a set nodes selected randomly and adds nodes incrementally by sampling according to a BFS strategy, until a budget of nodes is reached. Similarly, GraphSAGE represents a node by sampling a fixed number of neighbours at each distance from the node. This sampling approach bounds computational cost to a constant factor, trading off computational cost for predictive performance.
Based on this idea, methods such as PinSAGE [21] have shown promising results by building inductive models that can cope with web-scale problems by adapting sampling-based models to distributed environments.
Problem B. GCN models are applied in the presence of attributed data on nodes or edges. Applying them to unattributed networks is not straightforward, and it is not clear how the representations capture structural aspects or in tasks that require learning from node-to-node relationships.

Structural Representations
To this end, models such as struct2vec [14], have been proposed to deal with graph substructures directly. Particularly, struct2vec tackles the is-sue by learning skip-gram representations on a constructed meta-graph that connects structurally-similar nodes within a threshold.
Problem C. Constructing a meta-graph is a computationally costly process, as it relies on computing a pair-wise structural similarity measure across all nodes. Struct2vec proposes a series of optimizations to reduce the wouldbe quadratic computational cost, however, the learned representations remain label-dependent and, thus, they are affected by the aforementioned limitations of transductive approaches.

Our Contribution in Context
In this work, we tackle some of the problems we described about existing graph representation methods, namely: Problem A The difficulty in translating transductive network embeddings such as DeepWalk or node2vec to unseen graphs from the same domain. Rather than working with individual nodes, we learn embeddings of graph structures, which capture more general properties of the graph. Problem B Graph Convolutional Networks on unattributed graphs leverage node and edge attributes. We propose an inductive yet unattributed representation learning method. The resulting embeddings can serve potentially as additional input features to deep neural networks or graph convolutions. Problem C The scalability problems of existing structural embedding methods. Methods such as struct2vec [14] require to compute a similarity multilayer graph, which is expensive. We propose a similar structural representation, but avoid computing meta-graph structures by borrowing randomwalk sampling techniques to learn an inductive representation.
In the next section, we detail how IGEL functions, relating the building blocks of the method with the problems we seek to solve.

The IGEL Algorithm
In this section we describe IGEL in detail. We first provide an overview of the method and then drill down into the two steps that compose its high level algorithm. As IGEL embeddings can be trained in either supervised or unsupervised settings, we close the section with a formal description of the different objectives, paving the way for the experimental section of this work.

Overview
The main idea of IGEL is to represent local graph structures inductively by learning dense embeddings over a sparse space of structural attributes that appear in the surroundings of nodes in a graph. These dense embeddings can be learned in supervised or unsupervised ways, with the overall process encompasing two main steps. For a given graph G = V, E composed of a set of vertices V and edges E, representing a node requires: 1. Encoding. The first step encodes local graph structures in the form of a sparse vector recording the frequencies of structural attributes found for every given node n ∈ V . 2. Embedding. The sparse encoding is used as input to an embedding model, that transforms the input vector into a dense representation of the aggregated structural attributes.

Encoding Local Graph Structures
We capture the local structure by considering the neighbourhood of a node. For a given node n ∈ V and encoding distance α ∈ N, let G α (n) denote the sub-graph of G containing all nodes found at distance at most α from n, and the edges connecting them. From the neighbourhood graph G α (n), we represent the structural features of node n by considering the number of times a degree d is found at distance c in the graph G α (n), c = 0, . . . , α.
In this way, the structural features can be understood as a succession of distance c ∈ N and degree δ ∈ N tuples (c, δ) and their respective counts. Given the max-degree δ max of G, a sparse feature vector x n ∈ R , with = δ max × α, can be constructed such that the ith component of x n , i = cδ max + δ, contains the number of times the tuple (c, δ) appears in G α (n). A visual representation of this encoding process is shown in Figure 1.
The proposed encoding can be further processed and normalized. In this work, we log-normalize each feature count z as log 2 (1+z) and then normalize the transformed features to the [0, 1] interval. Also, if during testing we need to compute the features for a new node with degree δ > δ max , we use the bin corresponding δ max to store its frequency.

Embedding of the Sparse Representations
At this point, we can represent a node in terms of its immediate surroundings, but this representation is sparse and high dimensional. A simple way to transform the sparse structural features into a dense, lower dimensional, representation is through a linear transformation: where e n is d-dimensional, and W ∈ R ×d is a learnable matrix of parameters, d . Each row in W captures the vector representation of each single structural feature. Intuitively, this can be understood as a weighted average of the encoded structural features, representing the node in terms of its immediate surroundings. Figure 2 provides a visual overview.

Learning the Embeddings
We now describe the learning procedure for the parameters W such that the general structural properties of the original encoding are preserved.Such properties to preserve are task-dependent: in exploratory network analysis, we aim to learn representations that capture general graph properties such as degree distributions, centrality measures, or structural similarities. In classification tasks, the objective is to identify attributes that are useful to discriminate between the classes, if the model can capture them. We now define the two optimization objectives considered by IGEL corresponding to both scenarios.

Unsupervised Setting
Our objective in the unsupervised setting is to capture the global network features in terms of the local structures surrounding every node. We formulate this problem similarly to skip-gram based methods [3,13], which optimize a likelihood function from sample data generated through random walks on the graph. In the following, we describe the two steps involved in learning the embeddings.
Distributional Sampling through Random Walks-Our sampling strategy generates sample paths over the graph, selecting the next node uniformly from the neighbours of the current node. Figure 3 illustrates a possible random walk of length 9 in the same graph of Figure 1. Each node contains the time-step(s) when it was visited during the random walk.
This step is similar to existing sample-based transductive methods, such as DeepWalk [13]. In contrast to other methods such as node2vec [3], our method uses unbiased random walks, and does not require tuning of the probabilities of in-out and return paths when sampling each graph. Additionally, our approach does not require any previous computation of a structural metagraph, as proposed by struct2vec [14]. Instead, we perform w random walks of length s starting from each node in the network.
As we randomly sample the structure of the graph, we produce sequences of traversed nodes. These sequences are used in the optimization objective we describe next. Negative Sampling Optimization Objective-Given a random walk ω, defined as a sequence of nodes of length s, we define the context C(n, ω) associated to the occurrence of a node n in ω as the the sub-sequence in ω containing the nodes that appear close to n, including repetitions. Closeness is determined by the hyper-parameter p, the size of the positive context window, i.e., the context contains all nodes that appear at most p steps before/after the node within ω.
Similarly to DeepWalk or node2vec, we define a skip-gram negative sampling objective that learns to identify nodes appearing in similar contexts within the random walks. Given a node n t ∈ V in random walk ω, our task is to learn embeddings that assign high probability for nodes n o ∈ V appearing in the context C(n t , ω), and lower probability for nodes not appearing in the context. As we focus on the learned representation capturing these symmetric relationships, the probability of n o being in C(n t , ω) is given by: where σ(·) is the logistic function. The global objective function is the following negative sampling loglikelihood to be maximised. For each random walk and each node in the random walk, we sum the term corresponding to the positive cases for structures found in the context, and the expectation over z negative, randomly where P n (V ) is the noise distribution from which the z negative samples are drawn. We maximize (3) through gradient ascent. Table 1 summarizes the hyper-parameters in the unsupervised setting.

Supervised Setting
Besides its direct usage as an inductive node embedding method, IGEL can also be used as a node embedding layer in a deep neural network. In particular, the embedding of Eq. (1) can be fed into a downstream model as additional input features for a multilayer perceptron (MLP) or a graph neural network (GNN). In this case, the weight matrix W is jointly learned with the rest of the model parameters Θ. Instead of capturing global structural properties through random walks as before, the model in the supervised setting captures salient structural features that have predictive power in a particular task. Figure 4 illustrates the general model for a standard node classification task, in which the IGEL embeddings are used in combination with possibly additional node attributes F n to generate a final outputŷ that is used to predict the node class label.
Using IGEL as a feature layer additionally allows for pre-training and fine-tuning when data is not sufficiently available. This is similar to natural language domains, where language models are first trained on large corpora and then retrained for specific tasks at hand. Analogously, the IGEL layer can be learned first in the unsupervised manner described in the previous section, and subsequently refined to a specific inference task. Without loss of generality, we focus on multi-label classification without pre-training. For M independent labels, the task is to minimise the binary cross-entropy of the predicted labels associated to nodes: where y i n is one if i is the true class label of node n, and zero otherwise, and y i n is the network output corresponding to the class with label i.

Computational Complexity
We now describe the computational complexity of IGEL in relation to other embedding methods. Time and parameter complexities of other methods is described as in [2,19]. We differentiate time complexity, expressed in terms of computational steps given an input graph, and parameter complexity, which refers to the number of learnable parameters corresponding to a particular model. We note that certain parameters such as the number of random walks or their length in sampling-based methods appear as a constant, which we do not include in our analysis.
We first consider the parameter complexity. Let γ be the number of bins required to encode the local degree-based representation, which we set to the maximum degree δ max in this work 1 . Since each embedding vector has dimension d and we have γ bins for each encoding distance, the number of parameters scales as O On the other hand, the time complexity involves two main steps: a preprocessing step that computes the encoding of the local representations, and the computations required at each optimization step. The encoding step requires to visit all nodes at distance α from each node n, and repeat that for each node in the graph, therefore the time complexity is exponential in α, O(|V | × δ α max ). Once the local representations are computed, however, the optimizations step can be done efficiently, involving only a product that grows linearly with the number of parameters, or a forward-pass in a neural network. Table 2 compares the time and parameter complexities of several models. Transductive models such as DeepWalk, node2vec or struct2vec scale linearly with respect to the number of nodes, both in terms of time and parameters. Inductive methods based on graph convolutions incur in higher training costs, as signals have to be propagated across the whole set of nodes and edges. Their parameter complexity, however, is not directly dependent on either, and is instead a function of the number of input features. Sampling-based methods such as GraphSAGE reduce the time complexity cost by ensuring that a fixed number of sampled nodes are used during training and inference.
We note that IGEL lies at the crossroads of the previous methods. Its time complexity depends on both the number of nodes and the size of their surrounding neighbourhoods, similar to sampling-based GCNs. However, IGEL lacks the fixed bounds in the number of operations that is guaranteed by sampling a constant number of nodes at a time. Due to this fact, we expect IGEL's performance to degrade on denser graphs with neighbourhoods containing a wider range of different degrees among their nodes. Finally, IGEL's parameter complexity is closer to transductive methods, with a bound given by the maximum degree in the graph. Table 2: A comparison of graph representation methods in terms of their average parameter and time complexities. The parameters α stands for IGEL's encoding distance, r is the sampling factor for sampling GCNs, ρ is the convolutional distance in GCNs, δ max is the maximum degree and d is either the size of the embedding vectors or the number of features, depending on the method.

Experimental Evaluation
In this section, we evaluate IGEL in different tasks. We first analyze visually the type of structural properties captured by the method. Then, we evaluate the method in link prediction tasks for medium-sized graphs. Finally, we apply IGEL to an inductive multilabel node classification task in a large collection of protein graphs. For this analysis, we use the graphs described in Table 4. The goal of this section is to evaluate experimentally the following hypothesis: 1. Generality and scalability: the method should be capable of represent-ing structural aspects in small and large graphs alike. 2. Inductivity: the method should learn representations from graphs seen during training that generalize to unseen graphs from the same domain. 3. Scalability and compatibility with deep learning approaches: the method should outperform or be competitive with existing deep neural methods when used in conjunction with them without incurring in too excessive additional costs.

Unsupervised Setting
We first evaluate IGEL in the unsupervised setting using networks that are amenable for visual analysis. We focus on analyzing how the encoding distance parameter α influences the learned representations.
Les MisÃľrables Network -In this task, we consider a variation of the original Les MisÃľrables network [8] in which two identical copies of the network are connected by an edge between two nodes from each copy selected randomly, as shown in Figure 5. This allows us to analyze how the IGEL embeddings can capture structural similarity from distant areas of the graph.
We first use IGEL to learn feature representations for every node, and subsequently cluster the obtained embeddings. For a complete description of the experiment and parameter settings, see Appendix A. Figure 5 shows the composite network with nodes colored based on their clusters. For α = 1, the local encodings only consider direct neighbours. In this case, the resulting embeddings capture the standard notion of community or homophily, i.e., nodes with the same color are densely connected between each other and weakly connected to the rest. Furthermore, the embeddings corresponding to nodes within the two copies of each community also appear clustered together, although some nodes are not directly connected. This shows that IGEL embeddings can capture structural similarity, not only locally, but also from distant nodes in the graph. Larger encoding distances allow IGEL to capture relationships on larger portions of the graph. For α = 2, shown in Figure 5(b), the embeddings are clustered in two major groups, separating frequently visited nodes-with higher degrees and closeness centrality, and hence more commonly appearing in the sampling process-from connecting bridges or edges.
Sister Cities Network -We now illustrate how IGEL can be used for knowledge discovery using a larger network: the network of Sister Cities [6], a graph mined from Wikipedia where nodes correspond to cities and links to partnerships. We follow a similar approach as before and train IGEL embeddings for each node. We then perform a clustering analysis of the embeddings. Appendix B shows the details of the setup.
The obtained clusterings allows us to identify interpretable roles for the nodes, for example, cities that are country capitals. To quantitatively test this, we use an external labeled dataset that assigns a total of 179 nodes as country capitals, and then evaluate IGEL as a binary classifier by treating the nodes that belong to the cluster containing the highest number of capital cities as positive, and the rest of the nodes as negative. Figure 6 shows a geo-plot with label colors corresponding to a subset of 872 capital cities. Remarkably, this cluster composed of IGEL embeddings consistently outperforms heuristic methods by capturing up to 28% more country capitals, as measured by F1-score (see Table B.9 in the Appendix for details). From these results, we can conclude that IGEL is also effective discovering non-trivial embeddings that are interpretable.

Link Prediction
We now evaluate IGEL on the task of predicting whether an edge exists between two given nodes. To generate training data, we follow the methodology proposed in [3], which allows us to compare with previous transductive algorithms.
In particular, for a given graph, we generate negative examples (nonexisting edges) by sampling random pairs of nodes that are not connected in the original graph. Positive examples (existing edges) are obtained by removing half of the edges while keeping the mutilated graph after the edge Figure 5: Visualization of the embeddings in the (cloned) Les Misérables network: node colors reflect the clustering of the embeddings obtained for two different encoding distances, α = 1 (left) or α = 2 (right). In addition to capture community structure, the IGEL embeddings also generalize structurally similar nodes between distant regions. Node sizes correspond to their harmonic closeness centrality score. Figure 6: Geo-plot of the learned clusters on the Sister Cities dataset, filtering only cities that are capitals. Each point is a city, with a radius proportional to its degree, and colored by the group assigned by the clustering model. To learn the clusters, we use an IGEL encoding distance α = 4 and rum KMeans with k = 6. removals connected 2 . Both sets of node pairs are chosen to have the same cardinality.
The mutilated graph is used to train the IGEL embeddings using the unsupervised objective of Equation (3). Once the weight matrix W has been learned, we formulate a classification task, to classify pairs of nodes according to the labels described before.
For this final step, we use a logistic regression classifier with features corresponding to the Hadamard (element-wise) product of the embedding vectors of the nodes at each end of the predicted edge. This is the best combination of features reported in [3]. Note that this setting can be seen as a special case of our Equation (4) with M = 2 and the deep architecture being replaced by a single layer of additional weights.
We optimize all hyper-parameters described in Table 1, together with the encoding distance, using grid search. Our experimental setting involves link prediction on in a social media setting in the Facebook ego-network graph, and a citation network on arXiv capturing collaboration between scientists. We observe that the performance only depends strongly in two parameters: the encoding distance α and, to a lesser extent, the number of negative samples z. In general, we observe a diminishing returns effect, e.g., for α = 3 the performance is comparable to that of using α = 2 while taking an order of magnitude more time. In Section 4.4 we evaluate empirically the impact of α in the complexity of the algorithm. Table 5: Area Under the ROC Curve (AUC) results for the Facebook and AstroPhysics arXiv graphs. IGEL outperforms transductive methods, only using local degree structure. Hyper-parameters are optimized using grid search in IGEL, and transductive methods are the best ones reported in [3].

Method
Facebook arXiv DeepWalk [13] 0.968 0.934 LINE [16] 0.949 0.890 node2vec [3] 0.968 0.937 IGEL 0.976 0.984 Table 5 shows the best performing configuration on a series of five independent experiments. The best performing configuration on the Facebook graph features α = 2, learning d = 256 component vectors with e = 10 walks per node, each of length s = 150 and p = 8 negative samples per positive for the unsupervised negative sampling. Respectively on arXiv, we find the best configuration at α = 2, d = 256, e = 2, s = 100 and p = 9. Finally, we note that we run each experiment on a machine with 8 cores, 16GB of memory and a single GPU with 8GB of memory.
Compared to previous transductive approaches, which represent every individual node independently, our method represents nodes in terms of the aggregated representations of structural features within their neighbourhoods, which can lead to the same representation shared by different nodes. Despite this, IGEL outperforms previous methods such as DeepWalk, LINE and node2vec, that have access to the whole graph when learning node representations.

Node Classification
In this section, we evaluate how IGEL is able capture structural attributes that generalize to unseen graphs from the same domain. For that, we consider an inductive multi-label node classification task, in which we explore the performance of IGEL with or without pre-training and fine-tuning. The objective is to predict 121 different binary labels capturing protein functions in a series of Protein-to-Protein Interaction (PPI) graphs. Aside from the graph structures, every node has an additional set of attributes, allowing us to evaluate how the performance of IGEL differs in attributed networks. In this case, we use the supervised setting with the objective of Equation (4).
We use the supervised baselines proposed by GraphSAGE [4] and LCGL [1], and further compare with a fully supervised version of GraphSAGE [18]. We perform randomized grid search to identify the best possible set of parameters for an MLP containing IGEL and (optionally) feature inputs.
We analyze both encoding distances α ∈ {1, 2}, with other IGEL hyperparameters being fixed after a small greedy search based on the best configurations in the link prediction experiments. For the MLP model, we perform a greedy architecture search, including the number of hidden units, activation functions and depth. Our results show scores averaged over five different seeded runs with the same configuration, as obtained from the parameter search. We run each experiment on a machine with 8 cores, 16GB of memory and a single GPU with 8GB of device memory. Table 7 shows the classification results in terms of micro-averaged F1 score. Our model using structural embeddings and node features significantly outperforms both LGCL and every GraphSAGE instantiation with α = 1. In this case, we find that a higher value of α = 2 produces worse results than α = 1, which we attribute to overfitting. We believe that using regularization would help further improve these results. For reproducibility, we note that the best performing configuration is found with α = 2 on d = 256 length embedding vectors, concatenated with node features as the input layer for 1000 epochs in a 3-layer MLP using ELU activations with a learning rate of 0.005. Additionally, we apply 100 epoch patience for early stopping monitoring the F1 score on the validation set.
Remarkably, we note that a model trained using only graph structural features at α = 1 is able to outperform every GraphSAGE configuration that uses sampling. This highlights the strong predictive power of structural features alone, which is often disregarded when node or edges attributes are available.

Complexity Analysis
We finish this experimental evaluation with an empirical analysis of the computational complexity of IGEL. For that, we evaluate our implementation in the unsupervised setting using synthetic data generated according to the ErdÃűs-Renyi model. We control for three aspects that condition the runtime of the algorithm: the number of nodes |V |, the encoding distance α, and the average degree per node.
The training process is then performed with a realistic parameter configuration for encoding distances α = 1, 2, 3. For each training configuration, we execute five independent experiments. Each run is performed on a Slurmbased cluster requesting 48 cpu cores and 200GB of memory on each setting. We record the overall training times, and analyze the run-time as a function of the size of the graph and the average degree. fixed. We observe that α does not significantly affect the cost in this setting. Furthermore all curves show an approximate linear scaling for |V | ≥ 1, 024 (note the log-scale in both axes), showing that IGEL can be applied to largescale graphs in this regime. We also analyze the influence of the average degree for different values of α in Figure 7 (b). In this case, for α = 1, we observe an almost constant runtime as a function of the average degree, suggesting that the direct structural features can be feasibly applied to denser graphs. On the other hand, the runtime grows linearly with the average degree for values of α > 2, which is an actual limitation of IGEL in large-scale, dense networks 3 .
Overall, these results show that IGEL is a scalable method for values of α = 1, 2. We believe that ideas from sampling-based GCN literature can be extended to purely structural methods like IGEL to allow for the encoding and learning of very distant structural features.

Conclusions
In this work we have presented IGEL, a novel inductive network embedding method that compactly captures graph structures in a dense latent space. To the best of our knowledge, IGEL is the first inductive embedding algorithm explicitly designed for unattributed graphs that captures structural features without the need for node attributes.
Our results show that IGEL is scalable and can compete with transductive approaches in tasks such as link prediction on unattributed graphs. Additionally, IGEL can inductively generalize to unseen graphs, outperforming models based on Graph Convolutional Networks in a multi-label classification setting. Our work also highlights future directions for research, namely, regarding the improvement of time and memory consumption, finding ways to capture global aspects of a graph that IGEL cannot represent, and managing the evolution of degree-based structural features in temporal graphs.
IGEL is able to capture the additional structural similarity due to the cloned nature of the two subgraphs.

Appendix B. Additional Results on Sister Cities Network
We obtain our results on the Sister Cities Network running unsupervised IGEL for 2 epochs with a batch size of 25000, an Adam learning rate of 0.01, and 30 steps per random walk. The positive context window size is 7, with a proportion of 10 negative samples per positive and 30-component embedding vectors. We direct the reader to the code repository, in which configs/clusteringLarge.json contains the exact hyper-parameter configuration used.
Correlation with node indicators-For every node, we compute a score given only the embeddings of nodes in the graph, and then study its correlation to PageRank, Closeness, Betweenness and Degree centralities. To do so, we start with the intuition that a highly central node should be highly similar to its neighbours, since its representation should minimise the distance with any of the surrounding nodes. With this in mind, we compute the per-node scores as the sum of similarity scores between the node embedding and the embeddings of every one of its neighbours. Finally, our similarity function is the dot product between embedding vectors.
Since we are comparing distributions that are defined over different domains, such as probabilities in the case of PageRank or integers in the case of degree, we focus on the rank rather than the actual values between scores and metrics. Thus, we use Spearman's ρ correlation statistic to measure the monotonicity between both. The results for different encoding distances are shown in Table B.8. The correlation between embedding scores and results show several patterns. First, the embedding scores between a node and its neighbours is highly correlated with Degree, PageRank and Betweenness centralities. Second, closeness centrality is the least correlated of the metrics, as it measures how near a node is to every other node, in effect capturing a global property that needs to look beyond immediate node neighbourhoods. This falls in line with the hypothesis that we discussed in the previous section, in which larger graphs should display scores that are less correlated with global metrics. We direct the reader to Table B.10 for the correlations in the Les MisÃľrables graph, which exhibit higher correlations with the metrics across the board, and more so with closeness in particular.
Analysis of Capitals-To compare the clustering model, we set a baseline with a heuristic approach based on node degree and PageRank score. We rank the nodes by either metric and take as many nodes as there are in the positive cluster. We then compute F1-scores for the cluster, degree and PageRank approaches, as shown in Table B.9.
Upon qualitative inspection, we additionally notice that the clusters associated with capital cities usually include large, densely populated cities. Additionally, we found that the model often discriminates against capital cities located in Africa. We propose this may be caused by a reduced coverage of sister relationships in Wikipedia, or from the lack of such links between African cities and the rest of the world. Table B.9: Comparison between F1-scores of the cluster containing the most capitals C and the result taking the top |C| nodes as ranked by degree or PageRank. Bold means that the configuration is the best in a row, italic that it is the best result for the encoding distance in that row.