Ana Alexandre

Andres

Arthur

Enzo

Kavya, Marc Jean-Baptiste George

Maria P Marie-Caroline

Marvin Marion

Mathieu C Mathieu Vu

Mihir, Mouna, Sagar, Ségolène, Tasnim, Théodore, Xiaoyu Matthieu T Maïssa

William Shakespeare

Macbeth Ne

; Yekpare

Ahmet Hamdi Tanpınar

Nicolas Sébastien

De Chamfort

Younes and Yunshi , and all the others that I might have missed. I also would like to thank Maria V. for the gatherings she hosted and for

titre:

Apprentissage de représentations sur graphes par diffusions de marche aléatoire mots cl és: L'apprentissage de représentations sur graphes, classification des noeuds, prédiction de liens, représentations de noeuds r ésum é: L'objectif principal de l'Apprentissage de Représentations sur Graphes est de plonger les noeuds dans un espace vectoriel de petite dimension. Dans cette thèse, nous abordons plusieurs enjeux dans le domaine.

Tout d'abord, nous étudions comment exploiter l'existence de communautés structurelles locales inhérentes aux graphes tout en apprenant les représentations. Nous apprenons des représentations améliorées de la communauté en combinant les informations latentes avec les représentations.

De plus, nous nous concentrons sur l'expressivité des représentations. Nous mettons l'accent sur les distributions de familles exponentielles pour saisir des modèles d'interaction riches. Nous proposons un modèle qui combine les marches aléatoires avec une matrice de factorisation sous forme de noyau.

Dans la dernière partie de la thèse, nous étudions des modèles permettant un bon compromis entre efficacité et précision. Nous proposons un modèle évolutif qui calcule des représentations binaires.

title:

Graph representation learning with random walk diffusions keywords: Graph representation learning, node classification, link prediction, node representations abstract: Graph Representation Learning aims to embed nodes in a low-dimensional space.

In this thesis, we tackle various challenging problems arising in the field.

Firstly, we study how to leverage the inherent local community structure of graphs while learning node representations. We learn enhanced community-aware representations by combining the latent information with the embeddings. Moreover, we concentrate on the expressiveness of node representations. We emphasize exponential family distributions to capture rich interaction patterns. We propose a model that combines random walks with kernelized matrix factorization.

In the last part of the thesis, we study models balancing the trade-off between efficiency and accuracy. We propose a scalable embedding model which computes binary node representations.

R É S U M É

Les données structurées sous forme de graphes sont omniprésentes dans de multiples domaines d'application comme les télécommunications, la biologie, et les plateformes de réseaux sociaux. L'extraction d'informations pertinentes à partir de graphes est une tâche cruciale pour traiter les problèmes d'apprentissage en analyse de réseaux. L'objectif principal de l'Apprentissage de Représentations sur Graphes (ARG) est de plonger les noeuds du graphe dans un espace vectoriel de petite dimension, tout en préservant les propriétés structurelles du réseau. Dans cette thèse, nous abordons plusieurs enjeux liés à l'ARG. Pour cela, nous développons des algorithmes expressifs et adaptatifs capables de tirer parti de la richesse sémantique structurelle des graphes via des diffusions de marche aléatoires.

Tout d'abord, nous étudions comment exploiter l'existence de communautés structurelles locales inhérentes aux graphes tout en apprenant les représentations. En particulier, nous introduisons les Topical Node Embeddings (TNE), un cadre générique pour améliorer les capacités prédictives des modèles en s'appuyant sur des processus de marche aléatoire. Néanmoins, en apprenant ces représentations, la plupart des modèles existants ignorent les groupes de noeuds densément connectés. Notre modèle attribue une étiquette de communauté latente à chaque noeud avec l'aide de divers modèles statistiques. Nous apprenons ensuite des représentations améliorées de la communauté en combinant les informations latentes avec les représentations. Nous démontrons que les TNE améliorent les capacités prédictives des représentations.

Dans la deuxième partie de la thèse, nous nous concentrons sur l'expressivité des représentations et nous mettons l'accent sur les distributions de familles exponentielles pour saisir des modèles d'interaction riches entre les noeuds dans des séquences de marche aléatoires. Nous introduisons le modèle Exponential Family Graph Embedding (EFGE), qui généralise les techniques d'apprentissage de représentation de graphe à l'aide marche aléatoire, à des familles de distributions exponentielles. Nous étudions trois exemples particuliers de ce modèle qui correspondent à des distributions exponentielles bien connues, nous analysons leurs propriétés et montons leurs liens avec les modèles d'apprentissage non supervisé existants.

iii Dans la troisième partie, nous étudions l'expressivité de l'ARG en nous concentrant sur les modèles de factorisation matricielle. De nombreuses approches reposant sur la factorisation matricielle apprennent les représentations en décomposant une matrice décrivant les similitudes entre les noeuds. Néanmoins, en raison de la structure complexe des graphes du monde réel, les vecteurs appris préservent difficilement la proximité des noeuds, entraînant une perte de performances dans les tâches en aval. En outre, ces algorithmes nécessitent des ressources de calcul et de mémoire élevées en raison de la construction exacte de la matrice de similarité. Pour répondre à ces défis, nous proposons kernelNE qui combine les marches aléatoires avec une matrice de factorisation sous forme de noyau. Nous examinons une formulation d'apprentissage à plusieurs noyaux qui permet une combinaison linéaire de fonctions de noyau.

Dans la dernière partie de la thèse, nous étudions des modèles permettant un bon compromis entre efficacité et précision. Au fur et à mesure que la taille des réseaux augmente, les modèles classiques sont confrontés à des défis de calcul pour s'adapter à de grands graphes. Malgré les nombreux efforts récents pour concevoir des algorithmes adaptables sur les problèmes d'apprentissage de noeuds, la plupart de ces algorithmes ont une faible précision sur les tâches en aval. Nous proposons NodeSig, un modèle évolutif qui calcule les représentations binaires. NodeSig exploite les probabilités de diffusion de marche aléatoire via une méthode dite de "hashing", pour calculer efficacement les représentations.

A B S T R A C T

Graph-structured data is ubiquitous in many application domains such as information technologies, biology, physics and social networks. The problem of extracting meaningful information from graphs is a crucial task for dealing with learning problems in network analysis. As a prominent paradigm, Graph Representation Learning (GRL) aims to embed nodes in a low-dimensional space, preserving the structural properties of the network. In this thesis, we tackle various challenging problems arising in GRL, developing expressive and scalable algorithms capable of leveraging rich structural semantics of real-world graphs via random walk diffusions.

Firstly, we study how to leverage the inherent local community structure of graphs while learning node representations. In particular, we introduce Topical Node Embeddings (TNE), a generic framework to enhance node representations' predictive capabilities relying on random walk-based methods. Most of the existing models are deprived of considering densely connected node group patterns while learning representations. Our model assigns a latent community label to each node with the favor of various statistical models and community detection algorithms. We then learn enhanced community-aware representations by combining the latent information with the embeddings. We demonstrate that TNE improves the predictive capabilities of embeddings in various tasks.

In the second part of the thesis, we concentrate on the expressiveness of node representations and we emphasize exponential family distributions to capture rich interaction patterns between nodes in random walk sequences. We introduce the Exponential Family Graph Embedding (EFGE) model, which generalizes random walk-based graph representation learning techniques to exponential family conditional distributions. We study three particular instances of this model that correspond to well-known exponential family distributions, analyzing their properties and showing their relationship to existing unsupervised learning models.

In the third part, we further study the expressiveness of GRL, focusing on matrix factorization models. Many approaches that rely on matrix factorization learn embeddings by decomposing a matrix designed to signify similarities among nodes. Nevertheless, due to the complex structure of real-world graphs, the learned embedding vectors cannot well preserve node v vi proximity, causing a performance loss in downstream tasks. Additionally, they require high computational and memory resources because of the exact realization of the similarity matrix. To address such challenges, we propose KernelNE, a model that combines random walks with kernelized matrix factorization. To further improve the model's performance, we examine a multiple kernel learning formulation that allows a linear combination of kernel functions.

In the last part of the thesis, we study models balancing the trade-off between efficiency and accuracy. As the size of networks increases, widely used models face computational challenges to scale to large graphs. While there is a recent effort towards designing algorithms that solely deal with scalability issues in node representation learning, most of them behave poorly in terms of accuracy on downstream tasks. Here, we propose NodeSig, a scalable embedding model which computes binary node representations. NodeSig exploits random walk diffusion probabilities via stable random projection hashing, towards efficiently computing embeddings in the Hamming space.

A C K N O W L E D G E M E N T

I would like to express my deepest gratitude to my advisor, Prof. Fragkiskos Malliaros, for his invaluable guidance and support during my doctoral research. His encouragements always kept me afloat during my course of doctoral research. Apart from his precious help to my research activities, I have learned lots of things from him. His passion, keen interest in research, friendful and helpful attitude inspired me a lot. I'm highly indebted to him for accompanying me during my Ph.D. journey. I would also like to thank Prof. Nikos Paragios for believing me and providing me the opportunity of starting this journey.

I am much obliged to all the jury members of my Ph.D. thesis committee, Prof. Céline Hudelot, Prof. Thomas Bonald, Prof. Philippe Cudré-Mauroux, Prof. Massih-Reza Amini, Dr. Yuxiao Dong, and Prof. Tina Eliassi-Rad for all their insightful comments and invaluable feedback. I would like to give a special thanks to Prof. Apostolos Papadopoulos not only for attending my thesis defense but also for all his suggestions and his valuable time to review the dissertation. I am very fortunate to obtain a chance to work with him during the last two years. I'm very grateful for all of our discussions and his great help with positive energy. I would like to express my sincerest gratitude to Mrs. Jana Dutrey for her great help and the gentle approach she showed me to deal with all the required procedures and the obstacles I encountered during my stay in France. I am very thankful to Mr. Anthony Guindon for his technical support. Many thanks to all the faculty of the CVN lab, Prof. Jean-Christophe Pesquet, Prof. Hugues Talbot, Prof. Émilie Chouzenoux, Prof. Maria Vakalopoulou, and Prof. Marc Castella for building a wonderful research atmosphere in the lab.

Many thanks to all my collaborators from IFPEN and especially to Surabhi for her outstanding effort, work, and patience. Many thanks to all the other members of CVN that I obtained a chance to share the same atmosphere - Node classification for KernelNE on PPI . . . . . . . Table 5.5

L I S T O F F I G U R E S

Link prediction task for KernelNE . . . . . . . . . . . Table 5.6

Comparison of methods for 10% training ratio . . . . Table 5.7

Comparison of methods for 50% training ratio . . . . Table 5.8

Comparison of methods for 90% training ratio . . . . Table 5.9

Comparison of models for link prediction . . . . . . .

W

ith the advancements in information technologies, graphs have become indispensable mathematical objects to model and represent the interactions among entities. They naturally emerge in numerous disciplines, including physics, chemistry, social sciences, and all related fields. Protein-protein interaction networks, recommender systems, and friendship networks are only a few examples of these different domains [START_REF] Newman | The Structure and Function of Complex Networks[END_REF]. They constitute ubiquitous elements not only for their ability to model complex structures but they also provide an elegant framework to analyze and study the intricate patterns composed by the individual units of the network [START_REF] Amaral | Complex networks[END_REF].

Graph analysis is important to gain insights into the network's hidden patterns and perform various predictive tasks by using the extracted information. For instance, one might wish to estimate the protein function in multi-omics data [START_REF] Gligorijević | deepNF: deep network fusion for protein function prediction[END_REF], recommend new products to a customer [START_REF] Lu | Recommender system application developments: A survey[END_REF], and find a community of people sharing the same particular hobby in a social network [START_REF] Fortunato | Community detection in graphs[END_REF]. Traditional techniques aim to carefully design feature vectors by choosing essential graph measures concerning the task of interest, relying on the network's structural properties, such as clustering coefficient and core number [START_REF] Fragkiskos | The core decomposition of networks: theory, algorithms and applications[END_REF]. These handcrafted feature vectors are further incorporated into machine learning models to carry out the desired tasks.

Although these graph measures provide information about the various properties of a node, they are unable to capture the interactions among nodes sufficiently-a critical point in learning and prediction tasks. For instance, despite the fact that the degree of a node describes well the size of its local neighborhood, it cannot reveal further structural properties related to these neighbors and their interactions. Likewise, while the clustering coefficient and k-core number can provide insights about the connectivity patterns of a node, it is strenuous to properly leverage them towards inferring 1 relationships among nodes which could be utilized by a machine learning model. Furthermore, features corresponding to node pairs can be extracted through graph similarity-based algorithms, such as the Jaccard and Adamic-Adar indices [START_REF] Linyuan | Link prediction in complex networks: A survey[END_REF]. Nevertheless, such features are often limited to specific networks or downstream tasks (e.g. link prediction), and also might require an extensive computational workload [START_REF] Linyuan | Link prediction in complex networks: A survey[END_REF].

Therefore, classical machine learning techniques on graphs that rely on handcrafted features are not effective in practice, suffering also from high space and computational cost. To this end, the research community have inclined to alternative approaches, leading to the birth of learnable models which mainly aim to automatically extract these features (representations) from the underlying graphs [START_REF] Goyal | Graph Embedding Techniques, Applications, and Performance: A Survey[END_REF][START_REF] Hamilton | Graph Representation Learning[END_REF]. The core idea of Graph Representation Learning (GRL) is to learn representations (also known as embeddings) of nodes in a lower-dimensional space, in which the embedding vectors reflect properties of interest. Due to the superior performance of GRL on various practical applications, recently we have witnessed an immense increase in the number of relevant studies [START_REF] Hamilton | Graph Representation Learning[END_REF].

Representation learning is not a new field; it has already been scrutinized in various domains, such as signal processing, natural language processing, and object recognition [START_REF] Bengio | Representation Learning: A Review and New Perspectives[END_REF]. Although the evolution of the graph representation learning field [GF18; CZC18] has been highly influenced by studies from diverse domains, developing an effective and efficient algorithm poses plenty of challenges. Unlike other data structures, networks have additional information indicating the relationships between pairs of nodes. Hence, a GRL model should be able to capture various topological patterns and underlying properties of the network. It is already well-known that realworld networks do not emerge from random and irregular forms. In fact, they share interesting and non-trivial characteristics, such as a heavy tail in the degree distribution and community structures [START_REF] Albert | Statistical mechanics of complex networks[END_REF]. Therefore, such topological properties should be properly leveraged in the learning procedure [START_REF] Feng | Representation Learning for Scale-free Networks[END_REF][START_REF] Wang | Community Preserving Network Embedding[END_REF]. Although plenty of approaches have been developed in the literature, emphasizing different aspects of networks in the representation learning process, most of them have commonly prioritized the algorithm's accuracy in downstream tasks, such as classification and link prediction.

Graph representation learning approaches consider various characteristics of networks in learning the representations. However, these features need to be expressed under a suitable model in order to convey the extracted information in the embeddings effectively. Therefore, the expressiveness of the representations is another criterion influencing the quality of the embeddings. On the other hand, the growing size of networks entails the need for scalable techniques that can run on networks consisting of millions of nodes and edges. Many previously proposed models are not practically applicable due to the high computational resource demands-thus, algorithms balancing the effectiveness and the scalability have become a prominent direction recently.

To that end, designing effective and efficient algorithms is of great significance for applications that involve learning from graph-structured data. Therefore, we consider the following challenges and points of interest, while developing GRL models:

• How to explicitly incorporate information about the rich structural semantics of real-world graphs in the GRL process.

• How to design models that could properly capture the complex interactions and relationships among nodes, towards improving expressiveness.

• How to design scalable GRL models that can efficiently handle large graphs.

thesis statement and overview of contributions

The dissertation's crux motivation is to study network analysis with graph representation learning approaches. In light of the challenges stated in the previous section, we focus on developing representation learning methods relying on random walks, in an unsupervised manner. Figure 1.1 gives an overview of the contributions of this thesis, which can be summarized as follows:

explicit integration of community information.

How to incorporate the community structure of networks in learning node representations? Many complex networks comprise groups of nodes having tight connections than the rest of the network. These substructures naturally emerge during the growth of networks. For instance, in social networks, people sharing similar hobbies or interests tend to be closer to each other; similarly, proteins interacting with each other are more likely to share the same cellular functions forming densely connected groups. Although various algorithms have been developed to detect these patterns, they are disregarded in the design of GRL models. We introduce a novel approach, TNE (Topical Node Embeddings) [C ¸M18; C ¸M21], which aims to integrate the community structure of a network in the embedding learning process. TNE is a general framework that can be applied with various random walk-based methods to learn community-aware embeddings. We examine the behavior of the proposed framework by adapting various latent community detection algorithms. We evaluate its performance in node classification and link prediction tasks (Chapter 3).

modeling node interactions with exponential family. How to model and capture the underlying pattern of node pairs properly within random walks sequences?

Previously proposed random walk-based approaches, although applying different strategies to generate node sequences, they mainly utilize the soft-max or sigmoid functions to model the distribution of nodes within random walks. Nevertheless, this might prohibit to capture richer types of interaction patterns among nodes that co-occur within a random walk. Here, we introduce a family of models, called EFGE (Exponential Family Graph Embeddings) [C ¸M19b; C ¸M20], which generalizes the conventional approaches with exponential family distributions. EFGE allows employing a wide range of conditional distributions to interpret the complex relationships among nodes; hence, we can learn more expressive embeddings conveying the intricate patterns among nodes in the network. We also show the connection between BigClam [START_REF] Yang | Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach[END_REF], a widely-used overlapping community detection, and an instance of our proposed model, building a bridge between two different graph mining applications (Chapter 4). Our extensive experimental evaluation deomostrates that leveraging exponential family distributions can further boost the predictive ability of the embeddings on downstream tasks. a kernelized matrix factorization framework based on random walks.

How to augment the predictive capacity of random walk-based matrix factorization methods with kernel functions? Kernel functions are generally integrated with linear models to map the data points into a higher-dimensional space, so that they are transformed into a structure that can be expressed with linear approaches in the new space. Although there are various graph representation learning approaches relying on matrix factorization, they follow linear techniques to decompose the designed target matrix. We propose a novel model, called KernelNE (Kernel Node Embeddings) [C ¸M19a; C ¸SM21], which incorporates universal kernels in learning representations. It bypasses the exact realization of the target matrix through random walks, thereby alleviating the optimization step's computation burden. We further enhance the model's capability with MKernelNE, which allows combining multiple kernels. The experimental evaluation demonstrates that the integration of kernels provides to the proposed approach the ability to grasp the underlying patterns of complex data, leading to more expressive node representations (Chapter 5). scalable node embeddings.

How to develop an algorithm balancing scalability and efficiency on downstream tasks?

Real-world networks have been continuously growing with newly added links and nodes-thus, the algorithms dealing with large-scale networks have become essential. Nevertheless, most of the previously proposed approaches are not capable of dealing with large networks due to high computational resource requirements. Recently, random projection-based node embedding algorithms have received significant attention, even though showing lower predictive capabilities on downstream tasks compared to learning-based methods. Here, we propose NodeSig [C ¸PM21], a model which targets to balance the trade-off between efficiency and accuracy. It brings together random walk diffusion and hashing techniques relying on αstable random projections. The design of the proposed methodology provides efficient projections of target node vectors recursively. It computes binary representations in the Hamming space, in which the pairwise distances approximate the chi similarity among the initially designed node vectors (Chapter 6). The experimental evaluation shows that NodeSig achieves good accuracy on downstream tasks compared to recent highly-scalable models, while at the same time being able to run within reasonable time.

outline of the thesis

The rest of the dissertation is organized as follows. In Chapter 2, we briefly describe the fundamental elements of graph theory and probability theory. We also summarize the methods developed in the graph representation learning field. Later, we provide the details of the experimental evaluation and a description of the networks used in the experiments. Chapter 3 shows how to enhance node embeddings by means of the community structure of networks with the TNE model. Chapter 4 introduces the EFGE model that leverages exponential family distributions to better capture the underlying interaction patterns of node pairs within the generated node sequences. Chapter 5 presents KernelNE and MKernelNE, which combine kernel functions with matrix factorization. Chapter 6 is devoted to NodeSig, the proposed scalable model that computes binary node embeddings. Finally, the arguments concluding the dissertation and possible future research directions are stated in Chapter 7.

I

n this chapter, we provide the fundamental concepts and background materials necessary throughout the dissertation. In the beginning, we describe the essential elements related to graph theory and probability theory. Moreover, we provide a general overview concerning graph representation learning methods in a separate section. For more detailed information on the field, the reader might refer to [Ray13; KT05; Tao13; Ham20; HYL17b; Zha+20; GF18; CZC18]. Finally, we discuss the experiments that we perform to evaluate the performance of the algorithms and the network datasets. Throughout the dissertation, we will use the notation M to denote a matrix, while the term M (i,j) points out the entry located at the i'th row and j'th column of the matrix. M (i,:) and M[i] indicate the i'th row of the matrix.

basics of graph theory

Graphs are the key elements to study objects and the relationships among them. Throughout the dissertation, we use the terms network and graph interchangeably. More formally, a graph is defined as follows:

Definition 2.1. A graph is an ordered pair G = (V, E ) consisting of non-empty sets V and E ⊆ V × V. The elements of V are called the vertices or nodes of G, and those of E the edges of G.

The edges of the graph might also indicate direction. A directed graph or digraph is a graph G = (V, E ) where E consists of the ordered pairs of nodes. In this case, the pairs (u, v) and (v, u) do not represent the same edge. It might be also allowed to have multiple edges or parallel edges which are two or more edges joining the same pair of nodes, and the graph containing parallel edges is called multigraph. Definition 2.2. A graph G = (V, E ) is called weighted if there is a weight function W : E → R assigning each edge to a real number.

Weighted graphs naturally arise in many applications, which enable the edges to convey additional information. For instance, it can be used to represent the distance or the cost of traveling between cities. The endpoints of an edge can also be connected to the same node, and such an edge (v, v) is called loop. In Figure 2.1, we depict various graph types to illustrate the given definitions.

Definition 2.3. An unweighted, undirected graph containing no loops or multiple edges is called simple graph.

Throughout the dissertation, we solely consider simple graphs to provide consistency in the experiments unless stated otherwise. Nodes u and v are adjacent or neighbours, if the pair (u, v) is an element of the edge set E . The degree of a node is defined as the number of its neighbours.

Another representation of a graph is the matrix form, with the adjacency matrix being the most commonly used.

Definition 2.4. The adjacency matrix of a simple graph G is the

|V | × |V |-matrix M with entries M (v,u) = 1 if (v, u) ∈ E and M (v,u) = 0 if (v, u) ∈ E .
For a weighted graph, the entries indicate the corresponding weights of the edges. Note that, the adjacency matrix is always symmetric for undirected graphs according to its diagonal.

Two graphs might have exactly the same structure, and they can have different namings. More formally, we can express it in the following way:

Definition 2.5. Two graphs G = (V G , E G ) and H = (V H , E H ) are isomorphic if there exits a bijection f : V G → V H such that (u, v) ∈ E G if and only if ( f (u), f (v)) ∈ E H for all v, u ∈ V G .
A graph might also be a part of the structure of another one or we might be interested to consider only a part of a graph.

Definition 2.6. A graph H = (V H , E H ) is a subgraph of G = (V G , E G ) if V H ⊆ V G and E H ⊆ E G .
One might be interested in visiting a node by starting from one another, but there must be a path from this pair of nodes. More formally, we define it as follows:

Definition 2.7. Let w = (v 1 , . . . , v L ) be sequence where v l ∈ V for all l ∈ {1, . . . , L}. Then, it is called a walk of length L from node v 1 to v L if (v l , v l+1 ) ∈ E for all l ∈ {1, . . . , L -1}. A walk w = (v 1 , . . . , v L ) is closed if v 1 = v L . It is a path if the nodes in the walk are distinct, i.e. v i = v j for all i = j. It is called cycle if it is closed and v i = v j for i = j except that v 1 = v L .
It is also possible to have several distinct paths between a pair of nodes. However, It might also be important to find the shortest one since it can provide the best solution for efficiency in many practical applications such as transportation and robotics. Let G = (V, E ) be a graph with a weight function

W : E → R. Then, the minimum distance d G (v, u, W) is defined by min L-1 ∑ l=1 W[(v l , v l+1 )] (v 1 , . . . , v l ) is a walk such that v := v 1 and u := v l .
If there is no walk from v to u, the distance is defined by d G (v, u, W) := ∞. There are several algorithms to compute the shortest paths in a graph such as Dijkstra's algorithm and Floyd-Warshall algorithm

[Ray13; KT05]. If the distance d G (v, u, W) < ∞ for all u, v ∈ V, then the graph G is called connected; otherwise it is disconnected.

basics of probability theory

In this section, we briefly present the essential elements of probability theory. Let X be a non-empty set and let P(X) be its power set which consists of all subsets of X.

Definition 2.8. A nonempty collection of subsets X ⊆ P (X) is σ-algebra (or σ-field) if the following three conditions hold:

• X ∈ X ; • if A ∈ X , then X\A ∈ X ; • if a sequence of elements A 1 , A 2 ,. . . ∈ X , then ∪ i=1 A i ∈ X .
We follow the conventional approach and the σ-algebra B(X) for X is used to denote its Borel σ-algebra, i.e., the smallest σ-algebra containing all open sets in X [START_REF] Tao | An Introduction to Measure Theory[END_REF].

Definition 2.9. A measurable space (X, X ) is an ordered pair where X is a σalgebra of X, and the elements of X is called measurable sets.

Definition 2.10. A function µ from X to R is called measure on (X, X ) if it satisfies • µ(∅) = 0; • For all A ∈ X , µ(A) ≥ 0; • For any finite or countable collections of pairwise disjoint sets A i ∈ X , it satisfies µ (∪ i=1 A i ) = ∑ i=1 µ(A i ).
We use the notation R to denote the extended real number system ( R := R ∪ {-∞, +∞}). A probability measure µ : X → [0, 1] is a measure satisfying µ(X) = 1. A probability space is an ordered pair (X, X , µ) where µ is a probability measure defined on the measurable space (X, X ).

Definition 2.11. A mapping X from a probability space (X, X , µ) to a measurable space (Y, Y ) is called random variable if X is a measurable function, which means that for every B ∈ Y its preimage X -1 (B) = {a : X(a) ∈ B} is in X .

Definition 2.12. For a random variable X : X → Y, the measure ν on (Y, Y ) defined by ν(B) := µ X -1 (B) = µ {X ∈ B} for every B ∈ Y is called the distribution of the random variable X.

µ{X t+1 = y t+1 |X t = y t , . . . , X 0 = y 0 } = µ{X t+1 = y t+1 |X t = y t ,. . ., X t+1-m = y t+1-m } for t ≥ m. Definition 2.15. A Markov chain X = {X t : t ≥ 0} is time-homogeneous if µ (X t+1 = s|X t = r) = µ (X t = s|X t-1 = r) for all t ≥ 1 and s, r ∈ Y.
The transition probabilities can be also represented by a matrix P where each entry is defined by P (s,r) := µ (X t+1 = r|X t = s). The dissertation mainly considers the methods relying on random walks, and we define a uniform random walk as follows: Definition 2.16. A uniform random walk of length L on a graph G = (V, E ) with a root node v 1 ∈ V as a time-homogeneous stochastic process with random variables {X l : 1 ≤ l ≤ L} such that X 1 = v 1 and X l+1 is a node chosen uniformly at random from the set of neighbors of X l for each l ∈ {1, . . . , L -1}.

graph representation learning: an overview

The history of graph embeddings can be dated back to the 1900s, with the initial works in the topological graph theory field studying the embedding of graphs in surfaces [START_REF] Archdeacon | Topological Graph Theory -A Survey[END_REF]. However, the graph representation learning field has shown impressive evolution and expansion during the past six years as a subfield of machine learning, and recent studies have considered more general types of problems. The intuition behind the approaches relies on finding an embedding vector in a lower-dimensional space such that the desired information in the network can be captured by the pairwise distances in the new space. By following the definition provided in [START_REF] Hamilton | Representation Learning on Graphs: Methods and Applications[END_REF][START_REF] Hamilton | Graph Representation Learning[END_REF], it can be more formally stated in the following way.

Definition 2.17. Let G = (V, E ) be a graph, (X, d X ) be a metric space and s G (•, •) be a user-specified function showing the pairwise proximities among nodes, our aim is to find a mapping E : V → X minimizing the function

1 |T| ∑ (v,u)∈T d X E[v], E[u]), s G (v, u) , (2.1)
where is the error or loss function defined by the user to measure the discrepancy between correct and the estimated proximity values, and T ⊆ V × V is the training set.

By optimizing the above function, we can learn node representations E[v] ∈ X for each node v ∈ V. An immediate and common choice for the embedding space X is the real vector space R d for many approaches and we will call d embedding or representation size throughout the thesis. In the remaining part of this section, we provide a brief overview and a categorization of various notable instances in the graph representation learning field.

Dimensionality Reduction

The early works of graph embeddings have relied on classical dimensionality reduction techniques. One of the first approaches is Principal Component Analysis (PCA) [START_REF] Jolliffe | Principal component analysis: a review and recent developments[END_REF], which projects the adjacency matrix of the network or a designed data matrix into a latent space in which the variance of the data is maximized. Linear Discriminant Analysis [START_REF] Tharwat | Linear discriminant analysis: A detailed tutorial[END_REF] is a supervised method contrary to PCA and projects the data on a subspace in which the class-separation is maximized. Multidimensional Scaling (MDS) [START_REF] Kruskal | Multidimensional Scaling. Quantitative Applications in the Social Sciences[END_REF] targets to position a set of points by preserving given pairwise Euclidean distances. Since these methods assume that data lay on a linear subspace, they might fail if the underlying data posses a highly nonlinear pattern. Therefore, alternative ideas have arisen in order to overcome this problem. Isometric Feature Mapping (Isomap) [START_REF] Tenenbaum | A Global Geometric Framework for Nonlinear Dimensionality Reduction[END_REF] extends MDS by integrating with the geodesic distances along the manifold. Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF] finds a projection of the data by maintaining distances within local neighborhoods. Lastly, kernel methods or tricks [START_REF] Hofmann | Kernel Methods in Machine Learning[END_REF] are generally used to map the non-linearly separable data points to a higher-dimensional space. They allow computing the inner products in the new space without exactly needing to know the mapping function so that the linear models can be adapted to capture the intrinsic characteristic of the complex data points.

Matrix Factorization-Based Approaches

The approaches relying on matrix factorization learn representations by decomposing a target matrix T ∈ R |V |×|V | designed based on a proximity measure. The graph factorization algorithm [START_REF] Ahmed | Distributed Large-Scale Natural Graph Factorization[END_REF] is one of the earliest works, which proposes an immediate and natural idea to learn embeddings by minimizing the following objective function:

argmin E 1 2 ∑ (v,u)∈E T (v,u) -E[v] • E[u] 2 + λ 2 ∑ v∈V E[v] 2 ,
where the target matrix T is chosen as the adjacency matrix of the given graph and λ is the regularization parameter. TADW [START_REF] Yang | Network Representation Learning with Rich Text Information[END_REF] combines text features of nodes into network representation learning under the matrix factorization framework as follows:

argmin

A,B T -A BX + λ 2 A 2 F + B 2 F .
Here, the text features corresponding to each node are represented by X ∈ R f ×|V | . The target matrix is selected as T = 0.5 • W + W 2 where f is the feature vector size and W is the adjacency matrix. HOPE [START_REF] Ou | Asymmetric Transitivity Preserving Graph Embedding[END_REF] demonstrates that several high-order proximity measurements such as Katz For a walk w = (v 1 , . . . , v L ) ∈ V L , the surrounding nodes v l-γ ,. . ., v l-1 , v l+1 , . . ., v l+γ located within a certain distance γ around center node v l composes the context set of node v l . The embeddings are further learned by maximizing Pr(v l-γ , . . . , v l-1 , v l+1 , . . . , v l+γ |v l ).

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 Context
By assuming conditional independence, the objective can be written as

F (Ω) = argmax Ω 1 N •L ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log Pr(v l+j |v l ; Ω), (2.2)
where w = (v 1 , . . . , v L ) ∈ W is a walk of length L, γ is the window size,

N := |W |
) := exp A[v l+j ] • B[v l ] ∑ v∈V exp (A[v] •B[v l ]) .
However, calculating Pr(v l+j , v l ) for each pair (v l+j , v l ) is not feasible due to the normalization term so an approach such as Hierarchical Softmax

F (Ω) = argmax Ω 1 N •L ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log Pr(v l+j |v l )+ k ∑ i=1 s i ∼p - E log(1 -Pr(s i |v l )) ,
where k is the number of negative samples, the probability measure is chosen as the sigmoid function σ(x) := (1 + exp(-x)) -1 and p -is the user-specified distribution to generate the negative instances. DeepWalk [START_REF] Perozzi | DeepWalk: Online Learning of Social Representations[END_REF] is the first proposed random walk-based approach. It produces walks by uniformly choosing the next node at random from the neighbors of the current one in which it resides. Node2Vec [GL16] leverages the idea with additional parameters to control the behavior of the random walk as Breadth First Search (BFS) or Depth First Search (DFS) explorations. More precisely, it selects the next node with a probability proportional to the coefficient π v,s = α p,q (u, s)W[v, s] where α p,q (u, s) is defined by

α p,q (u, s) =          1 p x ≤ d(u, s) = 0 1 0 ≤ x ≤ d(u, s) = 1 1 q d(u, s) = 2,
Each W[v, s] represents the weight of the edge, v is the current node in which the walk resides, u is the previously visited node just before v, d G (u, s) represents the distance between nodes u and s, and takes values from the set {0, 1, 2}. For low values of return parameter p, the walk inclines to move to already visited nodes, and it explores unvisited nodes for small values of in-out parameter q. BiasedWalk [NM18] extends it by introducing an additional parameter to estimate how far a candidate node is from the initial node of each walk.

As the NetMF method presented earlier and it does not explicitly simulates random walks, it can also be considered as a random walk based approach. In fact, the authors of NetMF have shown that the objective function of various random walk-based methods can be expressed as a matrix factorization task under certain conditions, drawing inspirations from Levy and Goldberg [START_REF] Levy | Neural Word Embedding as Implicit Matrix Factorization[END_REF]. In particular, NetMF learns embeddings by factorizing the shifted PPMI matrix defined by

T := log max vol(G) k • L L ∑ l=1 P (l) , 1 D -1 ,
where k is the number of negative samples, D is the diagonal matrix with row sums of the adjacency matrix W of the graph, P := D -1 W and vol(G) is defined by ∑ v,u∈V W (v,u) .

Neural Network-Based Approaches

Neural networks are undoubtedly one of the most outstanding models in recent years. They have been successfully applied in many fields, from computer vision to NLP, with plenty of diverse architectures and designs [START_REF] Goodfellow | Deep Learning[END_REF]. Various methods relying on neural network architectures have been proposed for graph-structured data. Here, we only name some of the very well-known methods. SDNE [START_REF] Wang | Structural Deep Network Embedding[END_REF] proposes a deep autoencoder model under a semi-supervised architecture framework, jointly optimizing the first-order and second-order proximities:

argmin B ( X -X) C 2 F +α ∑ (v,u)∈V 2 s v,u H (L) (:,v) -H (L) (:,u) 2 2 + ν 2 L ∑ l=1 B (l) 2 F + B(l) 2 F H l (:,v) = σ(B (l) H (l-1) (:,v) + C (l) ) ∀ l ∈ {1, . . . , L} ∀v ∈ V and H (0) (:,v) := X (:,v) ∀v ∈ V,
where B (l) is trainable weights and C is the bias term for layer l. The adjacency matrix of the graph is considered as the input X of the model, H (L) (:,v) indicates the final embedding vector of node v and X represents the reconstructed data. SDAE [START_REF] Cao | Deep Neural Networks for Learning Graph Representations[END_REF] is another deep neural network architectures extracting representations from the PPMI matrix by means of a stacked denoising autoencoders [START_REF] Vincent | Stacked Denoising Autoencoders: Learning Useful Representations in a Deep Network with a Local Denoising Criterion[END_REF].

We can also learn representations by encoding the network structure and node features together. The intuition relies on the message-passing framework in which each node aggregates information from its local neighborhood or from a determined set of nodes. Graph Convolutional Network (GCN) [START_REF] Kipf | Semi-Supervised Classification with Graph Convolutional Networks[END_REF] proposes a multi-layer convolutional architecture with the following propagation rule: (l) and H (0) = X, where W = W + I is the adjacency matrix with added self-loops, D is the diagonal matrix for D (v,v) = ∑ w∈V W(v,w) and X is a matrix of node features. Similarly, B (l) is trainable weights for layer l and σ(•) indicates the activation function such as ReLU(•) = max(0, •). It is a semi-supervised approach extracting the embeddings by encoding both graph structure and node features. GraphSAGE [START_REF] Hamilton | Inductive Representation Learning on Large Graphs[END_REF] extends the former method for inductive learning settings. It can efficiently generate node embeddings for previously unseen nodes. The random walk-based approaches [START_REF] Goyal | Graph Embedding Techniques, Applications, and Performance: A Survey[END_REF] can also be stated as naive examples since they apply the shallow, two-layer neural networks for the optimization step similar to SkipGram [Mik+13b] model. A plethora of graph neural network models have recently been proposed [KBG19; Boj+20; JB20]. The interested reader could refer to [START_REF] Hamilton | Representation Learning on Graphs: Methods and Applications[END_REF][START_REF] Hamilton | Graph Representation Learning[END_REF].

H (l+1) = σ D-0.5 W D-0.5 H (l) B

Large Scale Embedding Approaches

The continuously growing size of networks has opened up a new direction towards fast and accurate approaches. It is a promising and ascending field since the high computational and resource requirements of many existing techniques make them inapplicable for large scale networks consisting of millions of nodes and links.

The random walk methods can also be included in this category since they aim to approximate the proximity measures between nodes by generating node sequences. The LINE [START_REF] Tang | LINE: Large-scale Information Network Embedding[END_REF] method optimizes an objective function that captures both first-order and second-order proximity of each node. An advantage of it is that it can be applied to weighted networks as well. However, the main limitation of these methods is that they do not scale well for large networks. They have focused on increasing the effectiveness of data mining tasks (e.g., classification, link prediction, network reconstruction), whereas the efficiency side has not received significant concern. To address this problem, recent advances in graph representation learning use random projection or hashing techniques (more specifically, variants of locality-sensitive hashing [START_REF] Paulevé | Locality sensitive hashing: a comparison of hash function types and querying mechanisms[END_REF]) to boost performance, trying to maintain effectiveness.

One of the first scalable approaches, RandNE [START_REF] Zhang | Billion-Scale Network Embedding with Iterative Random Projection[END_REF], is based on iterative Gaussian random projections, adapting to any desired proximity level. The orthogonal projection of the weighted sum of the powers of the adjacency matrix W gives the final representations E as shown in Equation (2.3). Each term is recursively defined by E l := W • E l-1 for each l > 0 and the initial term E 0 is chosen as the orthogonal projection matrix:

E = α 0 E 0 + α 1 E 1 + • • • + α L-1 E L-1 + α L E L , α l ∈ R, ∀l ∈ {0, . . . , L}. (2.3)
In the same line, FastRP [START_REF] Chen | Fast and Accurate Network Embeddings via Very Sparse Random Projection[END_REF] uses sparse Gaussian random projections. It applies the same general formulation except it omits the initial term E 0 .

Recently, embedding techniques rely on hashing have emerged as a promising alternative to enable faster processing while, at the same time, retaining good accuracy results. The NetHash [START_REF] Wu | Efficient Attributed Network Embedding via Recursive Randomized Hashing[END_REF] algorithm expands each node of the graph into a rooted tree up to a predetermined depth, and then by using a bottom-up approach, encodes structural information as well as attribute values into minhash [START_REF] Broder | On the Resemblance and Containment of Documents[END_REF] signatures in a recursive manner. A similar approach has been used in NodeSketch [START_REF] Yang | NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching[END_REF], which applies a recursive sketching process. It learns integer-valued embeddings in Hamming space in which the pairwise distances approximate the weighted Jaccard similarity [START_REF] Li | 0-Bit Consistent Weighted Sampling[END_REF] among the initially designed node vectors.

Other Variants

In the literature, there are numerous graph representation learning approaches proposed for studying and analyzing a different aspect of networks.

We have briefly described a number of notable methods from each distinct category, but there are still lots of exciting works deserving to be mentioned. In this part, we name a couple of methods which cannot be exactly classified as one of the types mentioned above.

A graph coarsening framework, HARP [START_REF] Chen | HARP: Hierarchical Representation Learning for Networks[END_REF], firstly extracts embeddings by running a method such as DeepWalk and LINE on the compressed network, and then node representations are further prolonged for the initial network. It essentially focuses on improving the scalability of representation learning algorithms. Another approach Struct2Vec [START_REF] Leonardo | Struc2vec: Learning Node Representations from Structural Identity[END_REF] aims to capture the structural identity of nodes in learning node representations and considers a hierarchical metric to measure similarities.

description of datasets

In this section, we describe the networks which are commonly used in most of the experiments throughout the dissertation. We examine the performance of algorithms on seven networks of different types and sizes. To be consistent in the experiments, we consider each network as undirected and unweighted.

• CiteSeer [START_REF] Chen | HARP: Hierarchical Representation Learning for Networks[END_REF] is a citation network obtained from the CiteSeer library, in which each node corresponds to a paper, and the edges indicate reference relationships among papers. The node labels represent the subjects of the paper.

• Cora [START_REF] Sen | Collective classification in network data[END_REF] is another citation network constructed from the publications in the machine learning area; the documents are classified into seven categories.

• DBLP [Per+17] is a co-authorship graph, where an edge exists between nodes if two authors have co-authored at least one paper. The labels represent the research areas.

• PPI [GL16] is a graph extracted from the protein-protein interaction network for Homo Sapiens in which biological states are used as labels of nodes. • AstroPh [LKF07] is a collaboration network built from the papers submitted to the ArXiv repository for the Astro Physics subject area, from January 1993 to April 2003.

• HepTh [START_REF] Leskovec | Graph Evolution: Densification and Shrinking Diameters[END_REF] is constructed in a similar way from the papers submitted to ArXiv for the High Energy Physics -Theory category.

• Facebook [LM12] is a social network extracted from a survey conducted via a Facebook application.

• Gnutella [START_REF] Ripeanu | Mapping the Gnutella Network[END_REF] is the peer-to-peer file-sharing network constructed from the snapshot collected in August 2002 in which nodes and edges correspond to hosts and connections among them, respectively.

The detailed statistics of the datasets are provided in Table 2.1. The networks in the first group have node labels so they are used in the node classification experiments and the others are only used in the link prediction experiments.

machine learning tasks and evaluation metrics

We mainly perform two types of experiments to evaluate and compare our approaches to the baseline methods. We have implemented the experimental setup in Python with the scikit-learn [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] package.

Operator

Symbol Definition Average E[v] j + E[u] j /2 Hadamard E[v] j × E[u] j Weighted L1 • 1 E[v] j -E[u] j Weighted L2 • 2 E[v] j -E[u] j

Node Classification

For the node classification task, we have access to the labels of a certain fraction of nodes in the network (training set), and our goal is to predict the labels of the remaining nodes (test set). After learning the representation vectors for each node, we split them into varying sizes of training and testing sets. Unless otherwise specified, the experiments are carried out by applying a one-vs-rest logistic regression classifier with L 2 regularization. In order to provide more reliable experimental results, the same procedure is repeated 50 times. We report the average performance in terms of both micro-averaged F 1 and macro-averaged F 1 scores [START_REF] Vickery | Reviews : van Rijsbergen[END_REF], which are defined by

Micro-F 1 = 2PR P + R and Macro-F 1 = 2P k R k P k + R k P := ∑ K k=1 tp k ∑ K k=1 tp k + f p k R := ∑ K k=1 tp k ∑ K k=1 tp k + f n k P k := tp k tp k + f p k R k := tp k tp k + f n k ,
where K is the number of classes, tp k is the true positive, f n k is the false negative and f p k is the false positive results for the corresponding class k.

Link Prediction

In the link prediction task, we have limited access to the edges of the network, and our goal is to predict the missing (unseen) edges between nodes. [START_REF] Grover | Node2Vec: Scalable Feature Learning for Networks[END_REF]. We perform experiments using the logistic regression classifier with L 2 regularization. We report the Area Under Curve (AUC) [START_REF] Alpaydin | Introduction to Machine Learning[END_REF] score of the operators showing the best performance for each method.

T O P I C -AWA R E L AT E N T M O D E L S F O R R E P R E S E N TAT I O N L E A R N I N G O N G R A P H S

R

andom walk-based graph representation learning methods have received particular attention over the last years thanks to their success in several graph analysis problems, including node classification, link prediction, and clustering. They transform the network into a collection of node sequences, aiming to learn node representations by predicting the context of each node within the sequence. In this chapter, we introduce TNE, a generic framework to enhance the embeddings of nodes acquired by means of random walk-based approaches with topic-based information. Similar to the concept of topical word embeddings in Natural Language Processing, the proposed model first assigns each node to a latent community with the favor of various statistical graph models and community detection methods and then learns the enhanced topic-aware representations. The experimental results demonstrate that by incorporating node and community embeddings, TNE outperforms widely-known baseline GRL models.

introduction

Initial studies in the field of graph representation learning have been inspired by the advancements in the area of Natural Language Processing (NLP), borrowing various ideas originally developed for computing word embeddings.

A prominent example here is the SkipGram architecture [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF], which aims to find latent representations of words by estimating their context within the sentences of a textual corpus. As we have discussed in Chapter 2, many pioneer studies in GRL [PARS14; GL16; NM18] utilize the idea of random walks to transform graphs into a collection of sentences -as an analogy to the area of natural language -and these sentences or walks are later being used to learn node embeddings.

Although random walk-based approaches are strong enough to capture local connectivity patterns, they mainly suffer to sufficiently convey information about more global structural properties. More precisely, real-world networks have an inherent clustering (or community) structure, which can be utilized to further improve the predictive capabilities of node embeddings.

One can interpret such structural information based on an analogy to the concept of topics in a collection of documents. In a similar way as word embeddings can be enhanced with topic-based information [START_REF] Liu | Topical Word Embeddings[END_REF], here we aim at empowering node embeddings by employing information about the latent community structure of the network-that can be achieved by a process similar to the one of topic modeling.

In this chapter, we propose Topical Node Embeddings (TNE), a framework in which node embeddings are enhanced with topic (or community) information towards learning topic-aware node representations-something that leads to further improvements in the performance on downstream tasks. Local clustering patterns are of great importance on many applications, enabling to grasp hidden information of the network properly. For instance, consider two individuals sharing common friends or interests, that are not yet represented by a direct link in the network. A careful analysis of the local community structure can further help to infer the missing information (e.g., missing links), and therefore boost the predictive capabilities of node embeddings. Motivated by that, the proposed TNE framework aims to directly leverage the latent community structure of the graph while learning node embedding vectors. The main contributions of the chapter can be summarized as follows:

• Latent graph models and topic representations. We show how existing latent space discovery models, such as community detection and topic models, can be incorporated into the node representation learning process.

• Node representation learning framework. We propose a new model, called TNE, which first learns community embeddings from the graph and then uses them to improve the node representations extracted by ran-dom walk-based methods. We examine various instances of this model, studying their properties.

• Enriched feature vectors. We perform a detailed empirical evaluation of the embeddings learned by TNE on the tasks of node classification and link prediction. As the experimental results indicate, the proposed model learns feature vectors which can boost the performance on downstream tasks.

The rest of the chapter is organized as follows. Section 3.2 describes several related works, and gives the fundamental concepts by formulating the problem. In Section 3.3, we introduce the concept of topical node representation learning. The proposed TNE model is described in Section 3.4. Section 3.5 presents the experimental results, and finally, we conclude our work in Section 3.6. source code.

Our model has been implemented in Python and the source code can be found at: https://abdcelikkanat.github.io/projects/TNE/.

background concepts and related work

In this section, we will first briefly review the objective of the random walkbased approaches. We will also provide an overview of the community detection problem, focusing on aspects that are useful for the presentation of the proposed methodology.

Learning Node Embeddings with Random Walks

Let G = (V, E ) be a graph with the vertex set V and the edge set E . As we have discussed in Chapter 2, our goal is to find a mapping B : V → R d , where B[v] will correspond to the representation of node v in a lowerdimensional space R d ; d is referred to as the embedding or dimension size, and is much smaller than the cardinality of the vertex set. As we have mentioned previously, graph representation learning methods based on the popular SkipGram architecture (e.g., [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF][START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF]) learn node representations using node sequences produced by random walks over a given network. They mainly target to maximize the log-likelihood of the occurrences of nodes within a certain distance with respect to each other, as follows:

F N (A, B) := argmax Ω ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log Pr(v l+j | v l ; Ω), (3.1)
where Ω = (A, B) is the model parameters that we would like to learn, W is the set of random walks w = (v 1 , . . . , v l , . . . , v L ) ∈ V L of length L, and γ refers to the window size. A common choice for the probability measure in Equation (3.1) is the softmax or sigmoid function. (Please refer to Subsection 2.3.3 in Chapter 2 for a detailed explanation.) Note that, the nodes appearing inside the window size of center node v l are referred to as context nodes.

We obtain two different representation vectors A[v] and B[v]

for each node v ∈ V but we will consider only B[v] in the experimental evaluation, which corresponds to the vector when the node is interpreted as a center node.

Community Structure

The integration of community information in learning embedding can be beneficial since it is one of the key elements of complex networks making them distinct from arbitrary graph structures. In general, a set of nodes having dense connections than the rest of the network is referred to as a community, but the formal and precise definition might vary depending on the context in which it is introduced. For instance, the notion of modularity has been introduced to measure the quality of a division of the network [START_REF] Newman | Modularity and community structure in networks[END_REF]. Networks with high modularity represent the existence of clusters of nodes having high intra-connections and sparse links between the nodes from different clusters. It is formally defined by where W (v,u) indicates the edge weight between nodes u and v, vol

modularity(G) := 1 2vol(G) ∑ v,u∈V W (u,v) - m v m u vol(G) δ(z v , z u ), (3.2)
(G) is 1/2 ∑ v,u∈V W (v,u) , m v is defined by ∑ u∈V W (v,u)
, and δ z v ,z u is Kronecker delta function, which is equal to 1 if nodes v and u are assigned to the same community (i.e., z u = z v ), while δ(z v , z u ) = 0 otherwise.

However, the optimization of modularity is computationally intractable, so Blondel et al. [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF] has proposed a greedy algorithm, namely Louvain, to address this issue. The algorithm is initialized by assigning a distinct community label to each node of the given network, so the number of communities is proportional to the number of nodes at the beginning of the procedure. Then, each node is assigned to the community label of its neighbor producing the highest marginal gain, or it preserves its current label if there is no more gain for any of its neighbors. The process is repeated until no further improvement is feasible.

Real-world networks might also have an overlapping community structure so that a node might be a member of multiple communities as shown in Figure 3.1. Many methods have been proposed to deal with the overlapping community detection problem [MV13; LFK09]. For instance, the BigClam [START_REF] Yang | Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach[END_REF] approach models the latent interaction strength, X (k) (v,u) , between nodes v and u in a community k ∈ {1, . . . , K} by a Poisson distribution with mean defined by F (k,v) • F (k,u) where each entry F (k,v) of the vector indicates a nonnegative weight and K is the number of communities. Therefore, the total amount of interaction strength between nodes v and u is

X (v,u) := K ∑ k=1 X (k) (v,u) where X (k) (v,u) ∼ Pois(F (k,v) • F (k,u) ).
In other words, if a pair of nodes shares many common communities, the total amount of latent interactions, X (v,u) , between them becomes high, and it leads to high edge probability defined by Pr(X v,u > 0). More formally and compactly, the approach optimizes the following log-likelihood function:

argmax F ∑ (v,u)∈E log(Pr(X (v,u) > 0)) + ∑ (v,u) ∈E log(Pr(X (v,u) = 0)) (3.3) = argmax F ∑ (v,u)∈E log(1 -exp(-F (:,v) • F (:,u) )) -∑ (v,u) ∈E F (:,v) • F (:,u) . (3.4)
After learning the affiliation factor, F (v,k) , the BigClam model assigns node v to community k if F (v,k) exceeds a certain threshold value.

In the following sections, we will present the proposed TNE model, which independently learns node and community (topic) embeddings, and then combines them to obtain expressive topical representations. We extract the networks' latent community structure by using the community detection methods described above or various statistical models relying on random walks. We will then leverage the extracted community information into the learning procedure of community representations. To the best of our knowledge, very few models benefit from the community structure of real networks while learning embeddings. The ComE model [START_REF] Cavallari | Learning Community Embedding with Community Detection and Node Embedding on Graphs[END_REF] proposes a closed-loop procedure among the encoding of communities, learning node embeddings and community detection in the network. M-NMF [START_REF] Wang | Community Preserving Network Embedding[END_REF] targets to learn node representations by incorporating community structure information in a non-negative matrix factorization formulation. COSINE [START_REF] Zhang | COSINE: Community-Preserving Social Network Embedding From Information Diffusion Cascades[END_REF] is a generative model learning the social network embeddings from information diffusion cascades. A recent approach, GEMSEC [START_REF] Benedek Rozemberczki | GEMSEC: Graph Embedding with Self Clustering[END_REF], learns node embeddings with an explicitly defined community preserving objective function.

learning topic representations

As we have mentioned above, complex networks, such as those arising from social or biological settings, consist of latent clusters of different sizes in which the nodes are more likely to be connected to each other [GN02; LFK09; Each node v is assigned to a community label z, maximizing the posterior probability Pr(z|v) by using the TNE-Glda model. MV13; HER09; Hen+]. Our main goal here is to use the latent clusters of a network in order to obtain enriched representations. This can be achieved by enhancing node embedding vectors with topic representations. By replacing a node v l with its community label z l in a random walk, we learn community embeddings by predicting the nodes in the context of a community label. More formally, we can define our objective function to learn topic representations as follows:

F T ( A, B) := argmax Ω=( A, B) 1 N•L ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log Pr(v l+j | z l ; Ω). (3.5)
By maximizing the log-probability above, we obtain the embedding vectors corresponding to each community label z l ∈ {1, . . . , K}. In this work, we mainly use two approaches to detect latent communities. The first one is based on novel combination of generative statistical models accompanied with random walks, while the second one is based on traditional community detection algorithms that utilize the network structure itself.

v 9 v 8 v 7 v 3 v 4 v 1 v 2 v 6 v 7 v 7 v 3 v 4 v 1 v 2 z 3 z 6 z 7 z 10 z 1 z 9 z 8 z 7 z 3 z 4 z 4 v 7 v 3 v 1 v 2 z 12 Random walk-based a) Initial network b) Generation of random walks v 1 v 2 v 3 v 5 v 4 v 8 v 7 v 6 v 9 v 10 v 11 v 12 v 1 v 2 v 3 v 5 v 4 v 8 v 7 v 6 v 9 v 10 v 11 v 12 v 1 v 2 v 3 v 5 v 8 v 7 v 6 v 9 v 10 v 11 v 12 v 4
Network structure-based c) Latent community assignments

v l z l θ w a 0 φ k b 0 L N K (a) Glda model a 0 θ k b 0 φ k z 1 v 1 z 2 v 2 . . . . . . z L v L p 0 π K (b) Ghmm model

Random Walks and Generative Graph Models

Most real-world networks can be expressed as a combination of nested or overlapping communities [START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF]. Therefore, when a random walk is initialized, it does not only visit neighboring nodes but also traverses communities in the network (see Figure 3.3b). In that regard, we assume that each random walk can be represented as random mixtures over latent communities, and each community can be characterized by a distribution over nodes. In other words, we can write the following generative model for each walk over the network:

1. For each k ∈ {1, . . . , K} • φ k ∼ Dir(b 0 ) 2. For each walk w = (v 1 , . . . , v l , . . . , v L ) • θ w ∼ Dir(a 0 ) • For each vertex v l ∈ w -z l ∼ Multinomial(θ w ) -v l ∼ Multinomial(φ z l )
Here, N indicates the number of walks, a 0 , b 0 ∈ R are the hyperparameters of the symmetric Dirichlet prior distributions, and the vectors φ k and θ w contain |V | and K components, respectively. If we consider each random walk as a document and the collection of random walks as a corpus, it can be seen that the statistical process defined above corresponds to the well known Latent Dirichlet Allocation (LDA) model [START_REF] Blei | Latent Dirichlet Allocation[END_REF]. Therefore, each community corresponds to a distinct topic in the terminology of NLP (we use the terms topic and community interchangeably in the rest of the chapter). We will refer to this model as Glda (the plate representation is shown in Figure 3.4a).

As we show in Lemma 3.1, the relative frequency of the occurrences of a node in the generated walks is proportional to its degree in the network for large number of walks or walk lengths. This property was first empirically demonstrated in the work of Perozzi, Al-Rfou, and Skiena [START_REF] Perozzi | DeepWalk: Online Learning of Social Representations[END_REF]. Here, we provide a formal argument of this empirical observation.

Lemma 3.1. Let G = (V, E ) be a connected graph, {X l } l≥1 be a Markov chain with state space V and P be a transition matrix, where

P (v,u) is defined as 1/deg(v) for each edge (v, u) ∈ E and 0 otherwise. If the Markov chain is aperiodic, then lim L→∞ 1 L E O (v) L = deg(v) 2|E | , where O (v)
L is a random variable representing the number of occurrences of the node v in a random walk of length L.

Proof. Since the graph is connected, each state can be accessed by any other one. Thus, the Markov chain is also irreducible having a unique limiting distribution π. Note that π v is equal to deg(v)/ ∑ u∈V deg(u) since it satisfies πP = π. Then, we can write:

lim L→∞ 1 L E O (v) L = lim L→∞ 1 L E L ∑ l=1 1 {X l =v} = lim L→∞ 1 L L ∑ l=1 E 1 {X l =v} = lim L→∞ 1 L L ∑ l=1 Pr (X l = v) = π v = deg(v) ∑ u∈V deg(u) = deg(v) 2|E | ,
where the equality in the second line follows from Cesàro Theorem [DeV07], since Pr(X l = v) converges to π v as L goes to infinity.

In the previous Glda model, the latent community assignment of each node is independently chosen from the community label of the previous node in the random walk. However, the hidden state of the current node can play an important role towards determining the next vertex to visit, as the random walk also traverses through communities. Therefore, we can write the following generative process, by modifying the Glda model:

1. For each k ∈ {1, . . . , K} • φ k ∼ Dir(b 0 ) • θ k ∼ Dir(a 0 ) 2. π ∼ Dir(p 0 ) 3. For each walk w = (v 1 , . . . , v i , . . . , v L ) • z 1 ∼ Dir(π) • For each vertex v l ∈ w, for all 2 ≤ l < L -v l ∼ Multinomial(φ z l ) -z l+1 ∼ Multinomial(θ z l ) • v L ∼ Multinomial(φ z L )
Here, a 0 , b 0 , p 0 ∈ R are the hyperparameters of the Dirichlet distributions, and the vectors θ k and φ k contain K and |V | components, respectively. The above model, in fact, corresponds to the well-known Hidden Markov Model (HMM) with symmetric Dirichlet priors over transition and emission distributions. In our experiments, we adopt the Infinite Hidden Markov Model (IHMM) [START_REF] Van | Beam Sampling for the Infinite Hidden Markov Model[END_REF] (we will refer to this model as Ghmm; the plate representation is shown in Figure 3.4b). Note that, unlike the Glda model, in the generation of each node sequence the same transition probabilities are used.

Network Structure-Based Modeling

In the previous models, the generated random walks are used to detect the community (or topic) assignment of each node in the given node sequence.

Here, we utilize two additional community detection models described in Section 3.2, which directly target to extract communities of nodes from a given network. The first one corresponds to the well-known Louvain algorithm by [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF] that extracts communities based on modularity maximization, while the second one to the BigClam model for overlapping community detection [START_REF] Yang | Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach[END_REF].

topical node embeddings

In this section, we will describe the proposed Topical Node Embedding (TNE) model for learning topic-aware node representations. An overview of the model is given in Figure 3.3. TNE aims to enhance node embeddings using information about the underlying topics of the graph obtained by the models described in Section 3.3. This can be achieved by learning node and topic embedding vectors independently of each other, jointly maximizing the objectives defined in Equations (3.1) and (3.5). Combining these two objectives, we derive the following:

argmax

Ω, Ω 1 N•L ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0
log Pr v l+j |v l ; Ω node embedding

+ log Pr v l+j |z l ; Ω community embedding .
In our approach, we use the sigmoid function for the probability measure in the above equation and we adopt the negative sampling strategy [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF], in order to make our computations more efficient. After obtaining the node and topic representations, our final step is to efficiently incorporate these two feature vectors, B[v] and B[z] of node v and community label z respectively, so as to obtain the final topic-enhanced node embedding. For this purpose, we concatenate node embedding vector B[v] with the expected topic vector with respect to the distribution Pr(•|v). Our strategy can be formulated as follows: where ⊕ indicates the concatenation operation. We refer to the final vector obtained after concatenating the node and topic feature vectors as topical node embedding.

B[v] ⊕ ∑ k∈{1,...,K} Pr(k|v) • B[k], (3.6
Algorithm 3.1 provides the pseudocode of the proposed TNE model. The general structure of our framework as follows. First, we need a collection of walks over the network to learn node and topic embeddings. We further produce node-context pairs and use SkipGram to learn node embeddings following Equation (3.1). Then, we choose a strategy (shown as T in Algorithm 3.1) to learn topic representations. This step is quite flexible in the formulation of TNE. One approach is to generate topic assignments z l of each node v l ∈ V in the walk w ∈ W, based on the random walk-based generative models Glda and Ghmm, defined in Section 3.3.1. Alternatively, we can directly infer the latent clustering structure based on BigClam and Louvain models, as described in Section 3.3.2. We learn topic representations by replacing the center node with its corresponding community label through Equation 3.5. Lastly, we combine node and topic embeddings using Equation (3.6) to obtain the final topical node embedding vectors. Depending on the method used to learn topical representations, we will refer to the corresponding instances of TNE as TNE-Glda, TNE-Ghmm, TNE-Louvain and TNE-BigClam.

Complexity Analysis

The time complexity of TNE varies depending on the algorithm used to detect latent topics and communities. For a given node sequences and topic assignments, the representations can be learned in the order of O(d

• γ • k • |W | • L)

experimental evaluation

In this section, we present the experimental setup and parameter settings for TNE and for the baseline models. The performance of the proposed model is examined in two downstream tasks: node classification and link prediction. We use eight different networks in our experiments as described in Section 2.4 and the statistics of the networks can be found in Table 2.1.

Baseline Methods

We consider seven baseline methods to compare the performance of our approach. We have described most of them in Section 2, but we also provide an overview here, including parameter settings:

(i) DeepWalk [START_REF] Perozzi | DeepWalk: Online Learning of Social Representations[END_REF] performs uniform random walks to generate the set of node sequences; then, the SkipGram model [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF][START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF] is used to learn node representations.

(ii) Node2Vec [START_REF] Grover | Node2Vec: Scalable Feature Learning for Networks[END_REF] combines SkipGram with biased random walks, using two extra parameters that control the walk in order to simulate a BFS or DFS exploration. In the experiments, we set those parameters to 1.0. As we have already mentioned, in our approach we sample context nodes using this biased random walk strategy.

(iii) LINE [START_REF] Tang | LINE: Large-scale Information Network Embedding[END_REF] learns nodes embeddings relying on first-and secondorder proximity information of nodes.

(iv) HOPE [START_REF] Ou | Asymmetric Transitivity Preserving Graph Embedding[END_REF] is a matrix factorization approach aiming at capturing similarity patterns based on a higher-order node similarity measure.

In the experiments, we consider the Katz index, since it demonstrates the best performance among other proximity indices.

(v) NetMF [START_REF] Qiu | Network Embedding As Matrix Factorization: Unifying DeepWalk, LINE, PTE, and Node2Vec[END_REF] targets to factorize the matrix approximated by the pointwise mutual information of center and context pairs. The experiments have been conducted for large window sizes (γ = 10) with a rank size of 256 due to its good performance.

(vi) GEMSEC [START_REF] Benedek Rozemberczki | GEMSEC: Graph Embedding with Self Clustering[END_REF] leverages the community structure of real-world graphs, learning node embeddings and the cluster assignments simultaneously. We have performed parameter tuning to set the number of communities from {5, 15, 20, 25, 50, 75, 100}.

(vii) Lastly, M-NMF [START_REF] Wang | Community Preserving Network Embedding[END_REF] extracts node embeddings under a modularitybased community detection framework based on non-negative matrix factorization. We have observed that the algorithm poses good performance by setting its parameters α = 0.1 and β = 5. We have performed parameter tuning for the number of communities using values from the following set: {5, 15, 20, 25, 50, 75, 100}.

Parameter Settings

The instances of TNE are fed with random walks generated by the Node2Vec model. Throughout the thesis, we apply the same parameter values for the random walk-based approaches, where the number of walks per node is set to 80, the walk length to 10, and the window size to 10. Moreover, we sample 5 negative instances for each center-context node pair. To speed up the training process, we adopt the negative sampling [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF] strategy.

Stochastic Gradient Descent (SGD) has been used for optimization, setting the initial learning rate to 0.0025 and its minimum value to 10 -5 . We learn topic and node embedding vectors of sizes 32 and 96, respectively, so as the obtain feature vectors of length 128.

In the learning process of topic assignments of nodes with the TNE-Glda model, we perform collapsed Gibbs sampling [START_REF] Griffiths | Finding scientific topics[END_REF] for parameter estimation and for inference. The Monte Carlo Markov Chain (MCMC) approach is used for the parameter estimation of TNE-Ghmm, with beam sampling for latent sequence resampling steps [START_REF] Van | Beam Sampling for the Infinite Hidden Markov Model[END_REF]. The number of topics for TNE-Glda is set to 100 for DBLP, 125 for Cora and set to 150 for the other networks. The initial number of states for TNE-Ghmm is chosen as 20.

Node Classification

The detailed results for the different instances of TNE framework as well as for the baseline methods are provided in Tables 3.1 to 3.4. Experiments are reported for different ratios of training data (2%-90%). For each model, the first row corresponds to Micro-F 1 scores, while the second one to Macro-F 1 scores.

As we can observe, the TNE-Louvain and TNE-BigClam models perform quite well, outperforming most of the baseline methods for different training ratios. For instance, they have higher Macro-F 1 scores around 4.55% and 6.82% than the best baseline approach for 10% training ratio of the PPI network. In the case of the Cora network, TNE-Glda performs better especially for higher training ratios, with 1.33% performance gain in terms of Micro-F 1 score. It is also the best performing approach on the PPI network for high training sizes. The overall better performance of the two network structure-based instances TNE-Louvain and TNE-BigClam over random walk-based models (e.g., TNE-Glda, TNE-Ghmm), can possibly be explained by the way that latent communities are extracted. While with TNE-Glda and TNE-Ghmm we are able to utilize random walks for both node and topic representations, it seems that those random walk are not expressive enough to recover the clustering structure as effectively as algorithms tailored to this task, such as BigClam and Louvain.

K = 50 K = 75 K = 100 K = 125 K = 150 K = 175 K = 200 (a)

The Effect of Number of Topics and Topic Embedding Sizes

We have further analyzed the effect of the chosen number of topics K on the performance of the TNE-Glda model on the CiteSeer network. As shown in Figure 3.5a, the increase in the number of topics makes positive contribution to the classification performance up to a certain level for TNE-Glda model, reaching its highest F 1 -score for around K = 150. The chosen number of topics seems to be a more crucial parameter especially for larger training data sizes.

The size of the topic embedding vector learned by Equation (3.5) is another factor affecting the performance of TNE. We examine the influence of the topic embedding size on the TNE-Louvain model over the Citeseer network. In the experiment, we have fixed the total embedding length to d n + d t to 128, and we vary the length of topic (d t ) and node (d n ) embeddings. As it can be observed in Figure 3.5b, for small node embedding sizes, the scores diminish drastically since topic embeddings alone do not convey sufficient information to effectively represent the nodes On the contrary, when we accurately balance the lengths of topic and node embeddings (for d t = 48 in this particular case), the contribution of topic-enhanced embeddings over purely node embeddings is evident.

Link Prediction

We also evaluate the performance of TNE variants in the link prediction task by following the experimental setup described in Section 2. In Table 3.5, we provide the Area Under Curve (AUC) scores over various types of networks. TNE-Ghmm model shows better performance; it outperforms the baselines over almost every network, with gains in percentage ranging from 0.92% (Facebook) upto 3.16% (Cora) compared to the best baseline method.

The variations of TNE always obtain the first rank except Citeseer, PPI and Gnutella networks. TNE-Louvain and TNE-BigClam also demonstrate very close and comparable achievements to TNE-Ghmm. The variants of the TNE model possess the highest score on Facebook.

Running Time

We have performed all the experiments on an Intel Xeon 2.4GHz CPU server (32 Cores) with 60GB of memory. In order to examine the exact running time of the TNE variants, we have performed an experiment on artificially generated Erd ös-Rényi random graphs [START_REF] Erdős | On the Evolution of Random Graphs[END_REF] of varying sizes, ranging from 2 8 to 2 13 nodes. The running times are reported in Figure 3.6. As expected, the TNE-Louvain is the most scalable instance, due to the efficient way to infer the community structure.

Further Empirical Analysis of TNE

We further analyze the behaviour of the various TNE instances on artificially generated networks, focusing on controlled classification experiments. We generate random graphs by following a similar approach as in the work [START_REF] Berberidis | Node Embedding with Adaptive Similarities for Scalable Learning over Graphs[END_REF]. In particular, we use the Stochastic Block Model (SBM) to construct graphs that consist of three clusters A, B and C, each one consists of 1, 000 nodes. Figure 3.7 provides a schematic representation of the process. An intra-community link is added with probability p, while an edge between communities A and B is added with probability q. We use an additional parameter c in order to introduce asymmetry for inter-community links for the community pairs A -C and B -C. We have constructed three networks (G 1 , G 2 , G 3 ) for parameters p = [0.06, 0.065, 0.07], q = [0.04, 0.035, 0.003] and c = [1.25, 1.429, 1.667], respectively. In our classification experiments, node labels correspond to community assignments. Table 3.6 provides the Micro-F 1 scores for different walk lengths on G 1 , G 2 and G 3 , with 40% of the datasets used as training set. We perform uniform random walks following DeepWalk's strategy, and the instances of TNE are fed with the same node sequences. As we can observe, the performance of the models increases depending on the walk length, since by increasing the number of center-context node pairs improves the ability of the models to capture the structural properties of the graph. Comparing the extreme cases G of G 1 and G 3 , the latter shows more distinguishable community structure. Therefore, TNE has better performance on G 3 since the community detection algorithms are able to correctly assign topic-community labels. Among them, TNE-Louvain is the best performing instance. It detects good modularity communities from the graph structure itself, and thus, contrary to TNE-Glda and TNE-Ghmm, it does not rely on the the generated random walk sequences. Furthermore, it is more successful to find the clusters of the stochastic block model graphs compared to TNE-BigClam, since BigClam focuses on overlapping communities that do not appear on these artificially generated graphs.

conclusion and future work

In this chapter, we have proposed TNE, a topic-aware family of models for GRL. TNE takes advantage of the latent community structure of graphs, leading to the concept of topical node embeddings. We have examined four instances of the proposed model, that either use random walks to learn topic representations or rely on well-known community detection algorithms. TNE is capable of producing enriched representations, compared to traditional random walk-based approaches or matrix factorization-based models, leading to improved performance results in the tasks of node classification and link prediction.

As future work, we are interested to extend the TNE model towards utilizing the hierarchical community structure of real-world networks, learning hierarchical node representations. Furthermore, we plan to examine the robustness of the learning representations with respect to changes on the structure of the graph.

Graph representation learning techniques relying on random walks generate node sequences to capture the relationships among nodes. The extracted information is further used in learning node embeddings with an approach similar to the popular SkipGram model. This chapter emphasizes exponential family distributions to capture rich interaction patterns between nodes. We introduce the generic exponential family graph embedding model that generalizes random walk-based network representation learning techniques to exponential family conditional distributions. We study three particular instances of this model, analyzing their properties and showing their relationship to existing unsupervised learning models. Our experimental evaluation on real-world datasets demonstrates that the proposed techniques outperform well-known baseline methods in two downstream machine learning tasks: node classification and link prediction.

introduction

As we have discussed in Chapter 2, random walk-based approaches typically sample a set of node sequences from the input graph. The main point that essentially differentiates these methods from each other is their strategy to generate (i.e., sample) these sequences. They construct center-context node pairs by examining the occurrences of nodes in a certain distance with respect to each other inside the walks. Then, widely used NLP models, such as the SkipGram model [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF], are applied to learn latent node representations.

Although SkipGram approach models the conditional distribution of nodes within a random walk based on the softmax function, it might prohibit to capture rich interaction patterns among nodes. Motivated by the limitation of current random walk-based GRL methodologies, we argue that 51 considering more expressive conditional probability models might lead to more informative latent node representations.

In particular, we capitalize on exponential family models to grasp interactions between nodes in random walks, which are a mathematically convenient parametric set of probability distributions allowing us to represent relationships among entities flexibly. More precisely, we introduce the concept of Exponential Family Graph Embeddings (EFGE), which generalizes random walk-based GRL techniques to exponential family conditional distributions. We study three particular instances of the proposed EFGE model that correspond to widely known exponential family distributions, namely the Bernoulli, Poisson, and Normal distributions. The extensive experimental evaluation of the proposed models in the tasks of node classification and link prediction suggests that the proposed EFGE approaches can further improve the predictive capabilities of node embeddings, compared to traditional SkipGram-based and other baseline methods. In addition, we further study the objective function of the proposed parametric models, providing connections to well-known unsupervised graph learning models under appropriate parameter settings.

The major contributions of the chapter can be summarized as follows:

• We introduce a novel representation learning model, called EFGE, which generalizes classical SkipGram-based approaches to exponential family distributions, towards more expressive GRL methods that rely on random walks. We study three instances of the model, namely the EFGE-Bern, EFGE-Pois, and EFGE-Norm models, that correspond to well-known distributions.

• We show that the objective functions of existing unsupervised representation learning models, including word embedding in NLP [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] and overlapping community detection [START_REF] Yang | Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach[END_REF], can be re-interpreted under the EFGE model.

• In a thorough experimental evaluation, we demonstrate that the proposed exponential family graph embedding models generally outperform widely used baseline approaches in various learning tasks on graphs. In addition, the running time to learn the representations is similar to other SkipGram-based models.

The rest of the chapter is organized as follows. In Section 4.2 we introduce some preliminary and background concepts. Then, Section 4.3 introduces the proposed approach. The experimental evaluation is presented in Section 4.4. Finally, we summarize and conclude our paper in Section 4.5. source code.

The implementation of the proposed models is provided in the following adress: https://abdcelikkanat.github.io/projects/EFGE/.

background concepts and related work

In this section, we will briefly review some preliminary concepts related to random-walk based approaches and exponential families.

Random Walk-based Node Embeddings

As we have discussed in the previous chapters, the objective function of random walk-based node representation learning models is defined in the following way:

argmax Ω 1 N•L ∑ w∈W L ∑ l=1 ∑ v∈C (l) γ (w) log p y (l) w,v ; Ω , (4.1)
where y (l)

w,v j represents the relationship between the center w l and context node v in the walk w = (w 1 , . . . , w L ) ∈ W. Here, C (l) γ (w) := w l+j : max{1, l -γ} ≤ j = 0 ≤ min{l + γ, L} denotes the set of context nodes of node w l , N is the number of walks, L is walk length and Ω = (A, B) is the model parameters. We consider A[v] to represent the embedding vector of v in all downstream machine learning applications.

Random walk-based graph representation learning methods can use different approaches to sample the context of a particular node. For instance, DeepWalk performs uniform truncated random walks, while Node2Vec is based on second-order random walks to capture context information. Another crucial point related to SkipGram based models is the way that how the relationship among center and context nodes in Equation (4.1) is modeled. In particular, DeepWalk uses the softmax function to model the conditional distribution p(•) of a context node for a given center, in such a way that nodes occurring in similar contexts tend to get close to each other in the latent representation space. In a similar way, Node2Vec adopts the negative sampling strategy, where it uses the sigmoid function to model the occurrence of a node in the context of another one. As we will present in the following section, we rely on exponential family distributions in order to further extend and generalize random-walk GRL models to conditional probability distribution beyond the softmax function-towards capturing richer types of node interaction patterns.

Exponential Families

We introduce the exponential family distributions, a parametric set of probability distributions that include, among others, the Gaussian, Binomial, and Poisson distributions. A class of probability distributions is called exponential family distributions if they can be expressed as

p(y) = h(y) exp ηT(y) -A(η) , (4.2)
where h is the base measure, η is the natural parameter, T is the sufficient statistic of the distribution and A(η) is the log-normalizer or log-partition function [START_REF] Andersen | Sufficiency and Exponential Families for Discrete Sample Spaces[END_REF]. Different choices of base measure and sufficient statistics lead us to obtain different probability distributions. For instance, the base measure and sufficient statistic of the Bernoulli distribution are h(y) = 1 and T(y) = y respectively, while for the Poisson distribution we have h(y) = 1/y! and T(y) = y.

As we mentioned above, exponential families contain a wide range of commonly used distributions, providing a general class of models by reparameterizing distributions in terms of the natural parameters η. In the related literature, exponential family distributions have been utilized to learn embeddings for high-dimensional data of different types (e.g., market basket analysis) [Rud+16; Liu+17; Rud+17]. Our approach generalizes exponential family embedding models to graphs by redefining the natural parameter η v,u as the product of context and center vectors in the following way:

η v,u := f A[v] • B[u] ,
where f is called the link function. As we will present shortly in the following section, we have many alternative options for the form of the link function.

learning node embeddings with exponential families

In this section, we propose the exponential family graph embedding models, referred to as EFGE. The main idea behind this family of models is to utilize the expressive power of exponential family distribution towards conditioning context nodes with respect to the center node of interest. Initially, we will describe the formulation of the general objective function of the EFGE model, and then we will present particular instances of the model based on different exponential family distributions.

Let W be a collection of node sequences generated by following a random walk strategy over a given graph G, as defined in Chapter 2. Based on that, we can define a generic objective function to learn node embeddings in the following way:

L(A, B) := argmax Ω ∑ w∈W L ∑ l=1 ∑ v∈V log p(y (l) (w,v) ; Ω) + λ 2 A 2 F + B 2 F , (4.3)
where y

(l) (w,v)
is the observed value indicating the relationship between the center w l and context node v. We incorporate the objective with the regularization term to obtain more informative embedding, which also improves the performance of the model in downstream tasks. The term λ refers to the regularization parameter and • F is the Frobenius norm. Here, we aim to find embedding vectors (A, B) by maximizing the log-likelihood in Equation (4.3). Note that, the objective function in Equation (4.3) is quite similar to the one of the SkipGram model [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] presented in Equation (4.1), except that we also include nodes that are not belonging to context sets.

Instead of restricting ourselves to the Sigmoid or Softmax functions in order to model the probability in the objective function of Equation (4.3), we provide a generalization assuming that each y where R(A, B) indicates the regularization term in Equation 4.3 and it will be omitted in the rest of the chapter for simplicity. As we can observe, Equation (4.4) which is the objective function of the generic EFGE graph embeddings model, generalizes the classic models to exponential family conditional distributions given in Equation (4.2). That way, the proposed EFGE approaches have the additional flexibility to utilize a wide range of exponential distributions, allowing them to capture more complex types of node interactions beyond simple co-occurrence relationships. It is also important to stress out that, the first term of Equation (4.4) does not depend on parameter η w l ,v ; this brings an advantage during the optimization process.

A general overview of our proposed model is as follows: Initially, we sample a set of N random walks relying on a chosen walk strategy. This strategy can be any context sampling process, such as uniform random walks (as in DeepWalk [START_REF] Perozzi | DeepWalk: Online Learning of Social Representations[END_REF]) or biased random walks (as in Node2Vec [START_REF] Grover | Node2Vec: Scalable Feature Learning for Networks[END_REF] or in BiaedWalk [START_REF] Nguyen | BiasedWalk: Biased Sampling for Representation Learning on Graphs[END_REF]). Then, based on the chosen instance of the EFGE model, we learn center and context embedding vectors. In this chapter, we examine three particular instances of the EFGE model, that represent well known exponential family distributions. In particular, we utilize the Bernoulli, Poisson, and Normal distributions leading to the corresponding EFGE-Bern, EFGE-Pois and EFGE-Norm models. For illustration purposes, Figure 4.1 depicts the Dolphins network composed by two communities and the embeddings in two dimensions as computed by different models. As we can observe, for this particular toy example, the proposed EFGE-Bern and EFGE-Pois approches learn representations that are able to differentiate nodes with respect to their communities. In the following sections, we analyze the properties of these models in detail.

The EFGE-Bern Model

Our first model is the EFGE-Bern, in which we will model the occurrence of a node in the context set of another one. Let Y (l) w,v be a random variable following a Bernoulli distribution which is equal to 1 if node v appears in the context set C (l) γ (w) of node w l . It can be written by

Y (l) (w,v) = X (l-γ) (w,v) ∨ • • • ∨X (l-1) (w,v) ∨ X (l+1) (w,v) ∨ • • • ∨X (l+γ) (w,v)
, where each X (l+j) (w,v) indicates the appearance of v at the specific position l + j (-γ ≤ j = 0 ≤ γ) in the walk w ∈ W.

Here, we assume that X

L B (A, B) = argmax Ω ∑ w∈W L ∑ l=1 ∑ v∈C (l) γ (w) log p(y (l) (w,v) ) + ∑ v ∈C (l) γ (w) log p(y (l) (w,v) ) = argmax Ω ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log p(x (l+j) (w,w l+j ) )+ ∑ v∈V v =w (l+j) log p(x (l+j) (w,v) ) . (4.5)
Note that, the exponential form of a Bernoulli distribution with a parameter π is equal to exp (ηx -A(η)), where the log-normalizer A(η) is log(1 + exp(η)) and the parameter π is the sigmoid function σ(η) = 1/ 1 -exp(-η)). Therefore, we can rewrite the objective function L B (A, B) as follows:

L B (A, B) = argmax Ω ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log σ(η (w l ,w l+j ) ) + ∑ v∈V v =w l+j log σ(-η (w l ,v) ) .
We choose the identity map for the link function f (•), so η w l ,v directly becomes equal to the product of vectors A[v] and B[w l ]. for large values of k.

Proof. Let q -(•|w l ) be the true conditional distribution of a random walk method for generating negative samples defined over V. Then, Equation 4.5 can be rewritten in the following way:

∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log p(x (l+j) (w,w l+j ) ) + k ∑ r=1 E s∼q - log p(x (l+j) (w,s) ) ≈ ∑ w∈W L ∑ l=1 ∑ v∈C (l) γ (w) log p(y (l) w,v ) + k ∑ r=1 E s∼q - y log p(y (l) (w,s) ) = ∑ w∈W L ∑ l=1   ∑ v∈C w (w l ) log p(y (l) (w,v) ) + |C (l) γ (w)| ∑ c=1 k ∑ r=1 E s∼q - y log p(y (l) (w,s) )   ≈ ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log p(y (l) (w,v) ) + |C (l) γ (w))| ∑ c=1 k ∑ r=1 1 |V \C (l) γ (w)| ∑ v ∈C (l) γ (w) log p(y (l) (w,v) )   = ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log p(y (l) (w,v) ) + ∑ v ∈C (l) γ (w) log p(y (l) (w,v) )   = ∑ w∈W L ∑ l=1 ∑ v∈V log p(y (l) (w,v) ) =L B (A, B),
where the fourth line follows from the law of large numbers for the sample size of |V \C be a value indicating the number of occurrences of node v in the context of w l . We assume that Y

(w,v) follows a Poisson distribution, with the mean value λ (w l ,v) being the number of appearances of node v in the surroundings of w l within the window size γ. Similar to the previous model, it can be expressed as

Y (l) (w,v) = X (l-γ) (w,v) + • • • + X (l-1) (w,v) + X (l+1) (w,v) + • • • + X (l+γ) (w,v) , where X (l+j) (w,v) ∼ Pois(λ (l+j) (w l ,v) ) for -γ ≤ j = 0 ≤ γ. That way, we obtain λ (w l ,v) = ∑ γ j=-γ λ (l+j) (w l ,v) ,
(l) (w,v) ) + η (w l ,v) y (l) (w,v) -exp( η (w l ,v) ) ,
where the base measure h(y

(l) (w,v) ) is equal to 1/y (l)
(w,v) !. Note that, the number of occurrence y (l) (w,v) is equal to 0 if v does not appear in the context of w l ∈ V. Following a similar strategy as in the EFGE-Bern model, the equation can be split into two parts for the cases where y (w,v) > 0 and y (w,v) = 0. That way, we can adopt the negative sampling strategy (given in Equation (4.6)) as follows:

∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0
log(x

(l+j) (w,w l+j ) !)+η (w l ,w l+j ) x (l+j) (w,w l+j ) -exp(η (w l ,w l+j ) ) + k ∑ r=1 E s∼q --exp(η (w l ,s) ) .
Note that, in the EFGE-Pois model, we do not specify any particular link function; thus, the natural parameter is equal to the product of the embeddings vectors.

Relationship to overlapping community detection

As we have discussed in Section 3.2 of Chapter 3, BigClam [YL13] is a widely used overlapping community detection method. It can be seen that an objective function similar to BigClam [START_REF] Yang | Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach[END_REF], can be obtained by unifying the objectives of the EFGE-Bern and EFGE-Pois models. The relationship is provided in Lemma 4.2. Besides, each entry of the node embedding vector can be considered as a coefficient indicating the node's membership strength to the corresponding community. In this case of BigClam, the vector entries are restricted to non-negative values. Lemma 4.2. Let Z (l) (w,v) be independent random variables following Poisson distribution with natural parameter η (w l ,v) which is defined by log

(A[v] •B[w l ]) and let Y (l) (w,v) ∼ Bern(π (l) (w,v) )
. For a set, W, of walks of length 2 containing all distinct node pairs, if the parameter π

(l) (w,v) is chosen by p(Z (l) (w,v) > 0), then the objective function of EFGE-Bern model is equal to 2 ∑ (u,v)∈E log 1-exp -A[v] • B[w l ] -∑ (u,v) ∈E A[v] • B[w l ] . Proof. Let Y (l)
(w,v) be Bernoulli distributions with parameter π (w l ,v) as defined above. Then, the objective function L B (A, B) defined in Subsection 4.3.1 can be divided into parts and it can be written as follows:

L B (A, B)= ∑ w∈W L ∑ l=1 ∑ v∈V log p(y (l) (w,v) ) = ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log p(y (l) (w,v) = 1) + ∑ v ∈C (l) γ (w) log p(y (l) (w,v) = 0)   = ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log p(z (l) (w,v) > 0) + ∑ v ∈C (l) γ (w) log p((z (l) w,v) = 0)   = ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log 1 -p(z (l) w,v = 0) + ∑ v ∈C (l) γ (w) log p(z (l) (w,v) = 0)   = ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log 1 -exp(η (w l ,v) ) -∑ v ∈C (l) γ (w) η (w l ,v)   = ∑ w∈W L ∑ l=1   ∑ v∈C (l) γ (w) log 1-exp -A[v] •B[w l ] -∑ v ∈C (l) γ (w) A[v] •B[w l ]   = 2 ∑ (u,v)∈E log 1-exp -A[v] •B[w l ] -2 ∑ (u,v) ∈E A[v] •B[w l ].
The last line follows from the assumption that the set of walks, W, consists of all distinct node pairs of length 2, which in fact corresponds to the edge set of the graph, and the window size, γ, is set to 1.

The EFGE-Norm Model

If a node v appears in the context of w l more frequently with respect to other nodes, we can say that v has a higher interaction with w l than the rest of the nodes. Therefore, we will consider each y (l) (w,v) in this model as a weight indicating the strength of the relationship between the nodes w l and v. We assume that X

(l+j) (w,v) ∼ N (1, σ 2 + ) if v ∈ C (l) γ (w), and
X (l+j) (w,v) ∼ N (0, σ 2 -)
otherwise. Hence, we can obtain that Y

(l) (w,v) ∼ N ( µ, σ 2 ) if we follow a similar assumption Y (l) (w,v) = ∑ γ j=-γ X (l+j) (w,v)
as in the previous model where µ is the number of occurrences of v in the context. The definition of the objective function, L N (A, B), for the EFGE-Norm model is defined as follows:

L N (A, B) = ∑ w∈W L ∑ l=1 ∑ -γ≤j≤γ j =0 log h(x (l+j) (w,w l+j ) )+ x (l+j) (w,w l+j ) η (w l ,w l+j ) σ + - η 2 (w l ,w l+j ) 2 + k ∑ r=1 E s∼q - log h(x (l+j) (w,s) ) + x (l+j) (w,s) η (w l ,s) σ -- η 2 (w l ,s) 2 ,
where the base measure h(x) is exp(-x 2 /2σ 2 )/ √ 2πσ for known variance.

In this model, we choose the link function as f (x) = exp(-x), so η (w l ,v) is defined as exp(-A[v] • B[w l ]).

Optimization

For the optimization step of our models, we use Stochastic Gradient Descent (SGD) [START_REF] Bottou | Stochastic gradient learning in neural networks[END_REF] to learn representations Ω = (A, B). Since it is computationally costly to compute the gradients for each node pair, we take advantage of the formulation of the objective function of each model. It can be divided into two parts according to the values of X (l+j) (w,v) ; thus, we adopt the negative sampling strategy, setting sampling size to k = 5 in all the experiments. We sample negative instances from the vertex set with respect to the number of occurrences of nodes in the generated walks raised to the power of 0.75 similar to the approach described in [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF].

experimental evaluation

In this section, we evaluate the performance of the proposed approach in the node classification and link prediction tasks. In the experimental evaluation of the proposed approach, we have used the same datasets described in Chapter 2. The baseline methods have been run with the same parameter settings explained in Chapter 3. For the EFGE model, we set the regular-ization parameter, λ, to 0.01 for PPI network, and it is set to 0.1 for the other networks in the classification experiments. For the link prediction, it is simply considered as 0.01 for all cases.

Node Classification

experimental set-up.

For the classification task, we apply the same strategy described in the previous chapter. In brief, our goal is to predict the correct labels of nodes in the test set with having access only to a limited number of node labels in the training set. We split the nodes into a wide range of training ratios varying from 2% up to 90% in order to evaluate the models better. We perform our experiments applying a one-vs-rest logistic regression classifier with L 2 regularization. experimental results.

We report the results in Tables 4.1 to 4.4 in which the first and the second rows of each method indicates the Micro-F 1 and the Macro-F 1 scores, respectively. The best and second best performing models are indicated with bold and underlined text. As we have discussed in Section 4.3, the EFGE-Bern approach models the occurrence of a node in the context of one another node. The model shows superior performances over Cora network, especially for small training ratios. For instance, the approach has 5.90% Micro-F 1 and 8.49% Macro-F 1 gains in scores for 2% training ratio concerning the highest baseline score and its performance gains are 1.71% and 2.01% in terms of Micro-F 1 and Macro-F 1 scores for the training set size of 10%. The model also holds the highest scores after EFGE-Pois model on the DBLP network. The EFGE-Pois is the best performing approach among the three EFGE instances in general. The percentage gain for Micro-F 1 score compared to the best baseline technique, varies from 3.93% up to 8.99% on Citeseer and differs from 2.30% up to 6.39 on the DBLP network. Since the approach models the number of appearances of a node in the context sets, it is more sensitive to the occurrence counts.

The last instance of EFGE that we have employed is the EFGE-Norm model, which utilizes normal distribution to represent the interaction weights between nodes. The model presents comparable performances on Cora and DBLP networks and it is the best approach over the PPI network with up to 12.08% Micro-F 1 and 9.90% Macro-F 1 gains. The approach possesses a similar trend to EFGE-Pois model since the mean of the distribution depends on the occurrence counts. If a node appears more frequently in the context of a particular node, it will have a higher interaction weight with it.

Overall, the classification experiments show that the proposed EFGE-Pois and EFGE-Norm models perform well, outperforming most baselines, especially on a limited number of training data. This can qualitatively be explained by the fact that those exponential family distribution models enable to capture the number of occurrences of a node within the context of another one while learning the embedding vectors. Of course, the structural properties of the network, such as the existence of community structure, might affect the performance of these models. For instance, as we have seen in the toy example of Fig. 4.1, the existence of well-defined communities at the Dolphins network allows the EFGE-Pois model to learn more discriminative embeddings with respect to the underlying communities (as we expect to have repetitions of nodes that belong to the same community while sampling the context of a node based on random walks).

Link Prediction

experimental set-up.

For this experiment, we randomly remove half of the edges of a given network, keeping the residual network connected. Then, we learn node representations using the residual network, which are further used to build edge feature vectors with various operators. Please refer to Section 2.5 of Chapter 2 for more details about the link prediction experiment, concerning the construction of training and test sets. experimental results.

Table 4.5 shows the Area Under Curve (AUC) scores for the link prediction task. The performances of EFGE variants are distinctive for the networks such as DBLP, AstroPh, HepTh and Facebook with gains 1.34%, 0.82%, 1.17% and 0.77%, respectively and the models show slightly better performance over Citeseer and Cora. Since we use the walks produced by Node2Vec, the performance of the EFGE instances highly affected by these generated walks; this can be especially seen over Gnutella network. The average clustering coefficients of Gnutella, PPI and Citeseer are relatively small compared to the rest of the network and the scores reveal the possible correlation between the clustering coefficient and the performance of EFGE variants.

Parameter Sensitivity

In this subsection, we evaluate how the performance of our models is affected under different parameter settings. In particular, we mainly examine the effect of embedding dimension d and the effect of the window size γ used to sample context nodes.

the effect of dimension size.

The dimension size d of embedding vectors is a crucial parameter affecting the performance of models. Therefore, we have conducted experiments examining the influence of embedding dimension d on the Citeseer network. As shown in Figure 4.2, the increase in the dimension size has a positive impact for all models over Micro-F 1 scores. When the dimension size increases from 32 up to 224, we observe a gain of around 18% for EFGE-Bern, around 17% for EFGE-Pois and 14.43% for EFGE-Norm model over the training set constructed from 50% of the network. While there is a big leap in the scores from the dimension size 64 to 96 for EFGE-Norm, the rest of the EFGE instances show a similar characteristic between the dimension sizes 32 and 64. The impact of the dimension size is more prominent for these variants of EFGE than for the EFGE-Norm model.

the effect of window size. We examine our approach's sensitivity under various window sizes ranging from 2 to 18 over the Citeseer network. Figure 4.3a depicts the Micro-F 1 scores for the training set composed by 50% of the network. As we can observe, the variants of the EFGE model tend to show better performance around window size of 8. EFGE-Pois shows superior performance compared to the other models since it models the number of occurrences of nodes within a random walk sequence, and potentially are benefited by a large γ value. On the contrary, the performance of the EFGE-Bern model (which in fact captures simple co-occurrence relationships) deteriorates for large window sizes more. EFGE-Norm is the most sensitive approach to the window size since possible outlier nodes occurring in the context sets causes a significant drop in its performance.

the effect of standard deviation of efge-norm model.

The EFGE-Norm model has an extra parameter σ which can influence the performance of the method. We examine the impact of σ, with five different values, performing experiments over the CiteSeer network. this value for all the experiments conducted in the node classification and link prediction tasks.

conclusion and future work

In this chapter, we introduced exponential family graph embeddings (EFGE), proposing three instances (EFGE-Bern, EFGE-Pois and EFGE-Norm) that generalize random walk approaches to exponential families. The benefit of these models stems from the fact that they allow utilizing exponential family distributions over center-context node pairs, going beyond simple co-occurrence relationships. We have also examined how the objective functions of the models can be expressed in a way that negative sampling can be applied to scale the learning process. The experimental results have demonstrated that instances of the EFGE model can outperform widely used baseline methods. As future work, we further plan to generalize the proposed model by integrating various topological properties of the network and possible node features into the node representation learning procedure.

M U LT I P L E K E R N E L R E P R E S E N TAT I O N L E A R N I N G O N G R A P H S

M

atrix factorization and random walk-based methods have become popular approaches for learning representations of nodes in a lower-dimensional space. In this chapter, we aim to bring together the best of both worlds, towards learning node embeddings. In particular, we propose a weighted matrix factorization model that encodes random walk-based information about nodes of the network. The benefit of this novel formulation is that it enables us to utilize kernel functions without realizing the exact proximity matrix so that it enhances the expressiveness of existing matrix decomposition methods with kernels and alleviates their computational complexities. We further extend the approach with a multiple kernel learning formulation that provides the flexibility of learning the kernel as the linear combination of a dictionary of kernels in data-driven fashion. We perform an empirical evaluation on real-world networks, showing that the proposed model outperforms baseline node embedding algorithms in two downstream machine learning tasks.

introduction

As we have discussed in Chapter 2, the area of GRL has been highly impacted by both traditional dimensionality reduction approaches [START_REF] Belkin | Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering[END_REF][START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF] and by the field of NLP [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF]. Specifically, models relying on matrix factorization techniques [BN01; CLX15; Ou+16] and random-walk based embedding models have gained considerable attention (e.g., [PARS14; GL16; C ¸M20; CM20]).

In this part of the dissertation, we will examine how kernel functions can be used to further enhance node embeddings. Kernel functions have often been introduced along with popular learning algorithms, such as PCA [START_REF] Sch Ölkopf | Kernel principal component analysis[END_REF], SVM [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF], Spectral Clustering [START_REF] Inderjit | Kernel Kmeans: Spectral Clustering and Normalized Cuts[END_REF], and Collaborative Filtering [START_REF] Liu | Kernelized Matrix Factorization for Collaborative Filtering[END_REF], to name a few. Most traditional learning models are insufficient to capture the underlying substructures of complex datasets, since they rely on linear techniques to model nonlinear patterns existing in data. Kernel functions [START_REF] Hofmann | Kernel Methods in Machine Learning[END_REF] on the other hand, allow to map non-linearly separable points into a (generally) higher dimensional feature space, so that the inner product in the new space can be computed without needing to compute the exact feature maps-bringing further computational benefits. Besides, to further reduce model bias, multiple kernel learning approaches have been proposed to learn optimal combinations of kernel functions [START_REF] Mehmet | Multiple Kernel Learning Algorithms[END_REF]. Nevertheless, despite their wide applications in various fields [HSS08; Wan+12], kernel and multiple kernel methods have not been thoroughly investigated for learning node embeddings.

In this chapter, we aim to combine matrix factorization and random walks in a kernelized model for learning node embedding. The potential advantage of such a modeling approach is that it allows to leverage and combine the elegant mathematical formulation offered by that matrix factorization with the expressive power of random walks to capture a notion of "stochastic" node similarity in an efficient way. More importantly, this formulation enables to leverage kernel functions in the node representation learning task. Because of the nature of matrix factorization-based models, node similarities can be viewed as an inner products of vectors lying in a latent space-which allows to utilize kernels towards interpreting the embeddings in a higher dimensional feature space using non-linear maps. Besides, multiple kernels can be utilized to learn more discriminative node embeddings. Note that, although graph kernels is a well-studied topic in graph learning [START_REF] Kriege | A survey on graph kernels[END_REF], it mainly focuses on graph classification-a task outside of the scope of this chapter. To the best of our knowledge, random walk-based multiple kernel matrix factorization has not been studied before for learning node embeddings.

The main contributions of the chapter can be summarized as follows:

• We propose KernelNE (Kernel Node Embeddings), a novel approach for learning node embeddings by incorporating kernel functions with models relying on weighted matrix factorization, encoding random walk-based structural information of the graph. We further examine the performance of the model with different types of kernel functions.

• To further improve expressiveness, we introduce MKernelNE, a multiple kernel learning formulation of the model. MKernelNE extends the kernelized weighted matrix factorization framework by learning a linear combination of a predefined set of kernels.

• We demonstrate how both models (simple and multiple kernel learning) leverage negative sampling to efficiently compute node embeddings.

• We extensively evaluate the proposed method's performance in the downstream tasks of node classification and link prediction. We show that the proposed approaches generally outperform well-known baseline methods on various real-world graph datasets. Besides, due to the efficient model optimization mechanism, the running time is comparable to the one of random walk models.

The rest of the chapter is organized as follows. We present the related works of the field in Section 5.2 and then, the problem formulation is described in Section 5.3. The proposed approach is introduced and experimental evaluations are carried out in Section 5.4. Finally, we conclude the paper in Section 5.6. source code.

The implementation of the proposed methodology in C++ can be reached at the following address: https://abdcelikkanat.github.io/ projects/kernelNE/.

related work

Although most algorithms in the broader field of machine learning have been developed for the linear case, real-world data often requires nonlinear models capable of unveiling the underlying complex relationships towards improving the performance on downstream tasks. To that end, kernel functions allow computing the inner product among data points in a typically high-dimensional feature space, in which linear models could still be applied, without explicitly computing the feature maps [START_REF] Hofmann | Kernel Methods in Machine Learning[END_REF]. Because of the generality of the inner product, kernel methods have widely been used in a plethora of models, including Support Vector Machine [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF], PCA [START_REF] Sch Ölkopf | Kernel principal component analysis[END_REF], spectral clustering [DGK04; AS10], collaborative filtering [START_REF] Liu | Kernelized Matrix Factorization for Collaborative Filtering[END_REF], and nonnegative matrix factorization for image processing tasks [START_REF] Fei Zhu | Kernel nonnegative matrix factorization without the pre-image problem[END_REF], to name a few.

Undoubtedly, the most prominent application of kernels in network analysis concerns the definition of a graph kernel [KJM20]-a kernel function that mainly targets to measure the similarity between a pair of graphs, with direct applications in the graph classification task. Recent approaches have also been proposed to leverage graph kernels for node classification, but in a supervised manner [START_REF] Tian | Rethinking Kernel Methods for Node Representation Learning on Graphs[END_REF]. Other related applications of kernel methods on graphs include topology inference [SBG17; RIG17], signal reconstruction [START_REF] Romero | Kernel-Based Reconstruction of Graph Signals[END_REF], and anomaly detection [START_REF] Mateos | Connecting the Dots: Identifying Network Structure via Graph Signal Processing[END_REF].

The expressiveness of kernel methods can further be enhanced using multiple kernel functions in a way that the best possible combination of a set of predefined kernels can be learned [START_REF] Francis | Multiple Kernel Learning, Conic Duality, and the SMO Algorithm[END_REF][START_REF] Mehmet | Multiple Kernel Learning Algorithms[END_REF]. Besides improving prediction performance, multiple kernels have also be used to combine information from distinct heterogeneous sources (please see [START_REF] Mehmet | Multiple Kernel Learning Algorithms[END_REF] and [START_REF] Wang | Bridging deep and multiple kernel learning: A review[END_REF] for a detailed presentation of several multiple kernel learning algorithms and their applications).

Despite the widespread applications of the kernel and multiple kernel learning methods, utilizing them for learning node embeddings via matrix factorization in an unsupervised way, is a problem that has not been thoroughly investigated. Previously, works that are close to our problem settings, which follow a methodologically different factorization approach (e.g., leveraging nonnegative matrix factorization [START_REF] Liu | Kernelized Matrix Factorization for Collaborative Filtering[END_REF]), targeting different application domains (e.g., collaborative filtering [START_REF] An | Multiple kernel nonnegative matrix factorization[END_REF]). The multiple kernel framework for graph-based dimensionality reduction proposed by Lin et al. [START_REF] Lin | Multiple Kernel Learning for Dimensionality Reduction[END_REF] is also close to our work. Nevertheless, their work focuses mainly on leveraging multiple kernel functions to fuse image descriptors in computer vision tasks properly.

As will be presented shortly, in this chapter, we propose novel unsupervised models for node embeddings that implicitly perform weighted matrix decomposition in a higher-dimensional space through kernel functions. The target pairwise node proximity matrix is properly designed to leverage information from random walk sequences, and thus, our models do not require the exact realization of this matrix. Both single and multiple kernel learning formulations are studied. Emphasis is also put on optimization aspects to ensure that node embeddings are computed efficiently.

modeling and problem formulation

Our goal is to find node representations in a latent space, preserving properties of the network. More formally, we define the general objective function of our problem as a weighted matrix factorization [START_REF] Srebro | Weighted Low-rank Approximations[END_REF], as follows: Depending on the desired graph properties that we are interested to encode, there are many possible alternatives to choose matrix M; such include the number of common neighbors between a pair of nodes, higher-order node proximity based on the Adamic-Adar or Katz indices [START_REF] Ou | Asymmetric Transitivity Preserving Graph Embedding[END_REF], as well leveraging multi-hop information [START_REF] Cao | GraRep: Learning Graph Representations with Global Structural Information[END_REF]. Here, we will design M as a sparse binary matrix utilizing information of random walks over the network. Note that, matrices M and W do not need to be symmetric.

argmin A,B W (M -AB ) 2 F Error term + λ 2 A 2 F + B 2
Let W be a collection of walks of length L and γ be the window size. We consider M (v,u) as a binary value which equals to 1 if node u appears in the context of v in any walk. We set F (v,u) to 2 • γ • #(v), where #(v) indicates the total number of occurrences of node v in the generated walks. Setting each term W (v,u) as the square root of F (v,u) , the objective function in Equation (5.1) can be expressed under a random walk-based formulation, as follows:

argmin A,B W M -AB 2 F + R(A, B) = argmin A,B √ F M -AB 2 F + R(A, B) = argmin A,B ∑ v∈V ∑ u∈V F (v,u) M (v,u) -A[u], B[v] 2 + R(A, B) = argmin A,B ∑ w∈W L ∑ l=1 γ ∑ j=-γ j =0 ∑ u∈V 1 {w l+j } (u) -A[u], B[w l ] 2 + R(A, B), (5.2)
where each w = (w 1 , . . . , w l , . . . , w L ) ∈ V L indicates a random walk of length L in the collection W, and R(A, B) is the regularization term. As mentioned in the previous chapters, matrix A in Equation (5.2) indicates the embedding vectors of nodes when they are considered as contexts; those will be the embeddings that are used in the experimental evaluation. The choice of matrix M and the reformulation of the objective function, offers a computational advantage during the optimization step. Moreover, such formulation also allows us to further explore kernelized version in order to exploit possible nonlinearity of the model.

kernel-based node representation learning

Most matrix factorization techniques that aim to find latent low-dimensional representations (e.g., [Qiu+18; Qiu+19; Ou+16]), adopt the Singular Value Decomposition (SVD); it provides the best approximation of the objective function stated in Equation (5.1), as long as the weight matrix is uniform [START_REF] Eckart | The approximation of one matrix by another of lower rank[END_REF]. Nevertheless, in our case the weight matrix is not uniform, therefore we need the exact realization of the target matrix in order to perform SVD.

To overcome this limitation, we leverage kernel functions to learn node representations via matrix factorization.

Let (X, d X ) be a metric space and H be a Hilbert space of real-valued functions defined on X. A Hilbert space is called reproducing kernel Hilbert space (RKHS) if the point evaluation map over H is a continuous linear functional. Furthermore, a feature map is defined as a function Φ : X → H from the input space X into feature space H. Every feature map defines a kernel K : X × X → R as follows:

K(x, y) := Φ(x), Φ(y) ∀(x, y) ∈ X 2 .
It can be seen that K(•, •) is symmetric and positive definite due to the properties of an inner product space.

A function g : X → R is induced by K, if there exists h ∈ H such that g = h, Φ(•) for a feature vector Φ of kernel K. Note that, this is independent of the definition of the feature map Φ and space H [START_REF] Steinwart | On the Influence of the Kernel on the Consistency of Support Vector Machines[END_REF]. Let I κ := {g :

X → R | ∃h ∈ H s.t. g = h, Φ(•)
} be the set of induced functions by kernel K. Then, a continuous kernel K on a compact metric space (X, d X ) is universal, if the set I κ is dense in the space of all continuous real-valued functions C(X). In other words, for any function f ∈ C(X) and > 0, there exists

g h ∈ I κ satisfying f -g h ∞ ≤ ,
where g h is defined as h, Φ(•) for some h ∈ H.

In this chapter, we consider universal kernels, since we can always find h ∈

H satisfying | h, φ(x i ) -α i | ≤ for given {x 1 , . . . , x N } ⊂ X, {α 1 , ..., α N } ⊂ R and
> 0 by Proposition 5.1. If we choose α i 's as the entries of a row of our target matrix M, then the elements h and φ(x i ) indicate the corresponding column vectors of A and B, respectively. Then, we can obtain a decomposition of the target matrix by repeating the process for each row. However, the element h might not always be in the range of feature map Φ; in this case, we will approximate the correct values of M. Proposition 5.1 (Universal kernels [START_REF] Steinwart | On the Influence of the Kernel on the Consistency of Support Vector Machines[END_REF]). Let (X, d X ) be a compact metric space and K(•, •) be a universal kernel on X. Then, for all compact and mutually disjoint subsets S 1 , . . . , S n ⊂ X, all α 1 , . . . , α n ∈ R, and all > 0, there exists a function g induced by K with g ∞ ≤ max

i |α i | + such that g |S - n ∑ i=1 α i 1 S i ∞ ≤ ,
where S := n i=1 S i and g |S is the restriction of g to S.

Universal kernels also provide a guarantee for the injectivity of the feature maps, as shown in Lemma 5.1; therefore, we can always find y ∈ X, such that

Φ(y) = h if h ∈ Φ(X)
. Otherwise, we can learn an approximate pre-image solution by using a gradient descent technique [START_REF] Honeine | Preimage Problem in Kernel-Based Machine Learning[END_REF].

Lemma 5.1 [START_REF] Steinwart | On the Influence of the Kernel on the Consistency of Support Vector Machines[END_REF]). Every feature map of a universal kernel is injective.

Proof. Let Φ(•) : X → H be a feature vector of the kernel K(•, •). Assume that Φ is not injective, so we can find a pair of distinct elements x, y ∈ X such that Φ(x) = Φ(y) and x = y. By Proposition 5.1, for any given > 0, there exists a function g = h, Φ(•) induced by K for some h ∈ H, which satisfies

g |S -(1 S 1 -1 S 2 ) ∞ ≤ ,
where S := S 1 ∪ S 2 for the compact sets S 1 = {x} and S 2 = {y}. Then, we have that | Φ(x), h -Φ(y), h )| ≥ 2 -2 . In other words, we obtain Φ(x) = Φ(y), which contradicts our initial assumption.

Single Kernel Node Representation Learning

Following the kernel formulation described above, we can now perform matrix factorization in the feature space by leveraging kernel functions. In particular, we can move the inner product from the input space X to the feature space H, by reformulating Equation (5.2) as follows:

argmin A,B ∑ w∈W L ∑ l=1 γ ∑ j=-γ j =0 ∑ u∈V 1 {w l+j } (u) -Φ(A[u]), Φ(B[w l ]) 2 + R(A, B) = argmin A,B ∑ w∈W L ∑ l=1 γ ∑ j=-γ j =0 ∑ u∈V 1 {w l+j } (u) -K A[u], B[w l ] 2 + R(A, B). (5.3)
To this end, we obtain a kernelized matrix factorization model for node embeddings based on random walks. For the numerical evaluation of our method, we use the following universal kernels [MXZ06; Ste02]:

K G (x, y) = exp -x -y 2 σ 2 σ ∈ R K S (x, y) = 1 1 + x -y 2 σ σ ∈ R + ,
where K G and K S correspond to the Gaussian and Schoenberg kernels respectively. We will refer to the proposed kernel-based node embeddings methodology as KernelNE (the two different kernels will be denoted by Gauss and Sch). A schematic representation of the basic components of the proposed model is given in Figure 5.1.

Model optimization

The estimation problem for both parameters A and B is, unfortunately, non-convex. Nevertheless, when we consider each parameter separately by fixing the other one, it turns into a convex problem. By taking advantage of this property, we employ Stochastic Gradient Descent (SGD) [START_REF] Bottou | Stochastic gradient learning in neural networks[END_REF] in the optimization step of each embedding matrix. Note that, for each center node w l ∈ V in Equation (5.3), we have to compute the gradient for each u ∈ V, which is computationally intractable. However, Equation (5.3) can be divided into two parts concerning the values of 1 {w l+j } (u) ∈ {0, 1}, as follows:

∑ u∈V 1 {w l+j } (u) -K A[u], B[w l ] 2 = 1 -K A[w l+j ], B[w l ] 2 + ∑ s -∈V \{w l+j } K A[s -], B[w l ] 2 ≈ 1 -K A[w l+j ], B[w l ] 2 + |V \{w l+j }| E s -∼ p - K A[s -], B[w l ] 2 = 1 -K A[w l+j ], B[w l ] 2 positive sample + k E s -∼p - K A[s -], B[w l ] 2 negative sample ,
where k is defined as |V | -1. That way, we can apply negative sampling [START_REF] Mikolov | Distributed Representations of Words and Phrases and Their Compositionality[END_REF]. For each center node w l , we sample k negative instances s -from the noise distribution p -. Then, we can rewrite the objective function of Equation (5.3) in the following way:

F S := argmin A,B ∑ w∈W L ∑ l=1 γ ∑ j=-γ j =0 1-K A[w l+j ], B[w l ] 2 + k ∑ r=1 s - r ∼p - K A[s - r ],B[w l ] 2 + R(A, B).
(5.4) Equation (5.4) corresponds to the objective function of the proposed Ker-nelNE model. In the following subsection, we will examine how this model could be further extended to leverage multiple kernels.

Multiple Kernel Node Representation Learning

Selecting a proper kernel function K(•, •) and the corresponding parameters (e.g., the bandwidth of a Gaussian kernel) is a critical task during the learning phase. Nevertheless, choosing a single kernel function might impose potential bias, causing limitations on the performance of the model.

Having the ability to properly utilize multiple kernels could increase the expressiveness of the model, capturing different notions of similarity among embeddings [START_REF] Mehmet | Multiple Kernel Learning Algorithms[END_REF]. Besides, learning how to combine such kernels, might further improve the performance of the underlying model. In particular, given a set of base kernels {K j } K j=1 , we aim to find an optimal way to combine the given kernels, as follows: where the combination function f c is parameterized on c ∈ R K that indicates kernel weights. Due to the generality of the multiple kernel learning framework, f c can be either a linear or nonlinear function.

K c (x, y) = f c {K i (x, y)} K i=1 |c , c) Learning embeddings Context nodes Center node w l u B[w l ] Φ(A[u]) Φ(B[w l ]) H X Φ(•) Φ(•) A[u] A[u] B[w l ] a) Initial network b) Generation of random walks v 1 v 2 v 3 v 5 v 4 v 8 v 7 v 6 v 9 v 10 v 11 v 12 v 1 v 2 v 3 v 5 v 4 v 8 v 7 v 6 v 9 v 10 v 11 v 12 v 1 v 2 v 3 v 5 v 8 v 7 v 6 v 9 v 10 v 11 v 12 v 4
In this paragraph, we examine how to further strengthen the proposed kernelized weighted matrix factorization, by linearly combining multiple kernels. More precisely, let K 1 , . . . , K K be a set of kernel functions satisfying the properties presented previously. Then, we restate the objective as follows:

F M := argmin A,B,c ∑ w∈W L ∑ l=1 γ ∑ j=-γ j =0 1 - K ∑ i=1 c i K i (A[w l+j ], B[w l ]) 2 + k ∑ r=1 s - r ∼p - K ∑ i=1 c i K i (A[s - r ], B[w l ]) 2 + λ 2 A 2 F + B 2 F + β 2 c 2 2 , (5.5)
where c = [c 1 , . . . , c K ] ∈ R K . Here, we introduce an additional parameter c j representing the contribution of the corresponding kernel K i . β > 0 is a tradeoff parameter for the regularization term, and similarly, the coefficients c 1 ,. . .,c K are optimized by fixing the remaining model parameters A and B. Equation (5.5) corresponds to the objective function of the proposed multiple kernel learning model MKernelNE. Unlike the common usage of multiple kernels [GA11], we do not constrain the coefficients to non-negative values. We interpret each entry of the target matrix as a linear combination of inner products of different kernels' feature maps. As discussed in the previous sections, our main intuition relies on obtaining more expressive embeddings by moving the factorization step into a higher dimensional space.

Algorithm 5.1 provides the pseudocode of the proposed approach. For a given collection of random walks W, we firstly determine the center-context node pairs (w l , w l+j ) in the node sequences. Recall that, for each center node in a walk, its surrounding nodes within a certain distance γ, define its context. Furthermore, the corresponding embedding vectors B[w l ] of center node w l and A[w l+j ] of context w l+j are updated by following the rules which we describe in detail below. Note that, we obtain two different representations,

A[v] and B[v],

for each node v ∈ V since the node can have either a center or context role in the walks. The gradients in Algorithm 5.2 are given below. For notation simplicity, we denote each

K i (A[u], B[v]) by the term K i (u, v). ∇ A[x] F M := 1 {u} (x) -2 K ∑ i=1 c i ∇ A[u] K j (u, v) 1 - K ∑ i=1 c i K i (u, v) + 2 k ∑ r=1 s - r ∼p - 1 {s - r } (x) K ∑ i=1 c i ∇ A[s - r ] K i (s - r , v)K i (s - r , v) + λA[x] ∇ B[v] F M := -2 K ∑ i=1 c i ∇ B[v] K i (u, v) 1 - K ∑ i=1 c i K i (u, v) + 2 k ∑ r=1 s - r ∼p - K ∑ i=1 c i ∇ B[v] K i (s - r , v)K i (s - r , v) + λB[v] ∇ c t F M = -2 1 - K ∑ i=1 c i K i (u, v) K t (u, v)+ 2 k ∑ r=1 s - r ∼p - K ∑ i=1 c i K i (s - r , v) K t (s - r , v) + βc t

Complexity Analysis

For the generation of walks, we apply the biased random walk strategy proposed in Node2Vec, which can be performed in O(|W | • L) steps [START_REF] Grover | Node2Vec: Scalable Feature Learning for Networks[END_REF] for the precomputed transition probabilities, where L indicates the walk length and W denotes the set of walks. For the algorithm's learning procedure, we can carry out Line 5 of Algorithm 5.1 at most 2γ • |W | • L times for each center-context pair, where γ represents the window size. The dominant operation in Algorithm 5.2 is the multiplication operation of the update rules in Lines 6, 7, and 9; the running time can be bounded by O(k

• K • d),
where k is the number of negative samples generated per center-context pair, K is the number of kernels, and d is the representation size. To sum up, the overall running time of the proposed approach can be bounded by end for 8: end for

O(γ • |W | • L • K • d • k) steps.

experimental evaluation

In this section, we assess the performance of the proposed approach by following the same experimental setup and network datasets that we have employed in the previous sections.

Parameter Settings

The different instances of KernelNE and MKernelNE are fed with random walks similar to those used in Node2Vec, setting hyper-parameters p, q to 1.0. For the training process, we adopt the negative sampling strategy [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] as described in Subsection 5.4.1. For the kernel parameters, the value of σ has been chosen as 2.0 for the single kernel version of the model (KernelNE). For MKernelNE, we have considered three kernels and their parameters are set to 1.0, 2.0, 3.0 and 1.0, 1.5, 2.0 for MkernelNE-Gauss and MkernelNE-Sch, respectively. The regularization parameters are set to λ = 10 -2 and β = 0.1. In the node classification task, we have access to the labels of a certain fraction of nodes in the network (training set), and our goal is to predict the labels of the remaining nodes (test set). The experiments are carried out by applying an one-vs-rest logistic regression classifier with L 2 regularization [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF]. experimental results.

A[x] ← A[x] -η∇ A[x] F M 7: B[v] ← B[v] -η∇ B[v] F M /*
Tables 5.1 to 5.4 report the Micro-F 1 and Macro-F 1 scores of the classification task. With boldface and underline, we indicate the best and second-best performing model, respectively. As we can observe, the single and multiple kernel versions of the proposed methodology outperform the baseline models, showing different characteristics depending on the graph dataset. While the Schoenberg kernel comes into prominence on PPI network, the Gaussian kernel shows good performance for the rest networks. We further observe that leveraging multiple kernels with MKernelNE often has superior performance compared to the single kernel model, especially for smaller training ratios. For instance, MKernelNE-Gauss provides an increase in the Micro-F 1 score ranging from 2.15% to 6.85% and improvement in the Macro-F 1 scores varying from 2.62% to 5.67% on the DBLP network.

In general, we have observed that the integration of Gaussian kernel exhibits higher performance than the Schoenberg kernel in the classification experiments.

Link Prediction

experimental set-up.

As we have described in the previous chapters, for the link prediction task, we remove half of the network's edges by retaining its connectivity, and we learn node embedding on the residual network. For networks consisting of disconnected components, we consider the giant component among them as our initial graph. The removed edges constitute the positive samples for the testing set; the same number of node pairs that do not exist in the original graph is sampled at random to form the negative samples. Then, the entries of the feature vector corresponding to each node pair (u, v) in the test set are computed based on various elementwise operations that we have described in Chapter 2. In the experiments, we apply logistic regression with L 2 regularization.

experimental results. Table 5.5 presents the Area Under Curve (AUC) scores for the link prediction task. In the case of the single kernel model KernelNE, the Schoenberg kernel (KernelNE-Sch) performs significantly better than the Gaussian one. It has higher scores ranging from 0.74% to 9.28% on most of the networks except PPI, Facebook, and Gnutella. We observe that MKernelNE provides a performance gain of up to 0.12% for the Schoenberg kernel and up to 5.29% for the Gaussian kernel. Since the single kernel model, KernelNE-Sch is the best performing approach for Baselines KernelNE MKernelNE D e e p W a l k most networks, the impact of adopting multiple kernels for the Gaussian case is more distinctive than the Schoenberg kernel. The baselines surpass the performance of our proposed models only on the PPI and Gnutella networks. Although KernelNE and MKernelNE methods attain their highest scores for the Weighted L2 operator that we have described in Chapter 2, KernelNE-Gauss achieves a remarkable score with the average metric on Gnutella network. Overall, both the KernelNE and MKernelNE approaches perform well across different datasets compared to the rest of baseline models.

N o d e 2 V e c L IN E H O P E N e t M F G E M S E C M -N M F G a u s s S c h G a u s s S c

Parameter Sensitivity

In this subsection, we examine how the performance of the proposed models is affected with respect to the choice of parameters.

the effect of dimension size.

The dimension size is a critical parameter for node representation learning approaches since the desired properties of networks are aimed to be preserved in a lower-dimensional space. Figure 5.2 depicts the Micro-F 1 score of the proposed models for varying embedding dimension sizes, ranging from d = 32 up to d = 224 over the Citeseer network. As it can be seen, all the different node embedding instances, both single and multiple kernel ones, have the same tendency with respect to d; the performance increases proportionally to the size of the embedding vectors. Focusing on 10% training ratio, we observe that the performance gain almost stabilizes for embedding sizes greater than 96. the effect of kernel parameters.

We have further studied the behavior of the kernel parameter σ of the Gaussian and Schoenberg kernel respectively (as described in Section 5.4.1). Figure 5.3 show how the Micro F 1 node classification score is affected with respect to σ for various training ratios on the Citeseer network. For the Gaussian kernel, we observe that the performance is almost stable for σ values varying from 0.25 up to 2.0, showing a sudden decrease after 4.0. For the case of the Schoenberg kernel, we observe an almost opposite behavior. Recall that, parameter σ has different impact on these kernels (Section 5.4.1). In particular, the Micro-F 1 score increases for σ values ranging from 0.25 to 0.50, while the performance almost stabilizes in the range of 4.0 to 8.0.

D E E P W A L K N O D E 2 V E C L I N E H O P E N E T M F G E M S E C M -N M F K E R N E L N E M K E R N E L N E 1 × 10 4 2 × 10 4 3 × 10 4 4 × 10 4
Running time (in seconds) More than 2 days

Running Time Comparison

For the running time comparison of the different models, we have generated an Erdös-Rényi G n,p graph model [START_REF] Erdős | On the Evolution of Random Graphs[END_REF], by choosing the number of nodes n = 10 5 and the edge probability p = 10 -4 . Figure 5.4 depicts the running time (in seconds) for both the baseline and the proposed models.

For this particular experiment, we have run all the models on a machine of 1TB memory with a single thread when it is possible. We do not report the running time of GEMSEC, since the experiment did not manage to complete within 2 days. As we can observe, both the proposed models have comparable running time-utilizing multiple kernels with MKernelNE improves performance on downstream tasks without heavily affecting efficiency. Besides, KernelNE runs faster than LINE, while MKernelNE with three kernels shows also a comparable performance. It is also important to note that although NetMF is a well-performing baseline model (especially in the task of node classification) which also relies on matrix factorization of a random walk proximity matrix, the model is not very efficient because of the way that the factorization is performed (please see Section. 5.2 for more details). On the contrary, our kernelized matrix factorization models are more efficient and scalable by leveraging negative sampling to improve scalability.

In addition to the running time comparison of the proposed approach against the different baseline models, we further examine the running time of KernelNE and MKernelNE (using three base kernels) over Erd ös-Rényi graphs of varying sizes, ranging from 2 8 to 2 13 nodes. In the generation of random graphs, we set the edge probabilities so that the expected node degree of graphs is 10. Figure 5.5 shows the running time of the proposed models. Since the Gaussian and Schoenberg kernels have similar performance, we report the running time for the Gaussian kernel only. As we observe, considering multiple kernels does not significantly affect the scalability properties of the MKernelNE model.

Visualization and Clustering of Embedding Vectors

As we have discussed in Chapter 3, Modularity is a measure designed to assess the quality of the clustering structure of a graph [START_REF] Newman | Networks: An Introduction[END_REF]. High modularity implies good clustering structure-the network consists of substructures in which nodes densely connected with each other to each other. Here, we perform a simple visualization and clustering experiment to examine the ability of the different node embedding models to capture the underlying community structure, preserving network's modularity in the embedding space. Note that, to keep the settings of the experiment simple, we leverage the raw embedding vectors visualizing them in the two-dimensional space (instead of performing visualization with t-SNE [START_REF] Van Der Maaten | Visualizing Data using t-SNE[END_REF] or similar algorithms).

We perform experiments on the Dolphins toy network, which contains 62 nodes and 159 edges. We use the Louvain algorithm [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF] to detect the communities in the network. Each of these detected five communities is represented with a different color in Figure 5.6a. We also use the proposed and the baseline models to learn node embeddings in two-dimensional space.

As we can observe in Figure 5.6, different instances of MKernelNE learn embedding vectors in which nodes of the same community are better distributed in the two-dimensional space. Besides, to further support this observation, we run the k-means clustering algorithm [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] on the embedding vectors, computing the corresponding Normalized Mutual Information (NMI) scores [START_REF] Malliaros | Clustering and Community Detection in Directed Networks: A Survey[END_REF], assuming as ground-truth communities the ones computed by the Louvain algorithm in the graph space. While the NMI scores for Node2Vec and NetMF are 0.532 and 0.572 respectively, KernelNE-Sch achieves 0.511 while for KernelNE-Gauss we have 0.607. The NMI scores significantly increase in the case of the multiple kernel models MKernelNE-Sch and MKernelNE-Gauss, which are 0.684 and 0.740 respectively.

conclusion and future work

In this chapter, we have studied the problem of learning node embeddings with kernel functions. We have first introduced KernelNE, a model that aims at interpreting random-walk based node proximity under a weighted matrix factorization framework, allowing to utilize kernel functions. To further boost performance, we have introduced MKernelNE, extending the proposed methodology to the multiple kernel learning framework. Besides, we have discussed how parameters of both models can be optimized via negative sampling in an efficient manner. Extensive experimental evaluation showed that the proposed kernelized models substantially outperform baseline GRL methods in node classification and link prediction tasks.

The proposed kernelized matrix factorization opens up further research directions in network representation learning that we aim to explore in future work. To incorporate the sparsity property prominent in real-world networks, a probabilistic interpretation [START_REF] Mnih | Probabilistic Matrix Factorization[END_REF] of the proposed matrix factorization mode would be suitable. Besides, it would be interesting to examine how the proposed models could be extended in the case of dynamic networks [START_REF] Seyed Mehran Kazemi | Representation Learning for Dynamic Graphs: A Survey[END_REF].

an overview of the proposed learning-based models

We have, so far, introduced three different graph representation learning approaches addressing the same problem from different perspectives. We have devised our models based on the generation of random walks in order to have a flexible architecture to learn node embeddings. In the next chapter, we will present the last contribution of the dissertation, which focuses on a different objective concerning the design of scalable algorithms. Therefore, here we will briefly review and compare the methods proposed so far in this thesis.

The first approach, TNE, has explicitly leveraged the extracted community information in learning node representations. Later on, we have extended the traditional SkipGram model by modeling node interactions with exponential family distributions. Finally, we have proposed a random walk-based kernelized matrix factorization method to learn more expressive embeddings.

We have mainly evaluated the performance of these approaches in two downstream tasks: node classification and link prediction. For each network, we report the score of the baseline method performing the best-so, the chosen baseline model might differ depending on the dataset. The results are depicted in Tables 5.6 to 5.9. In all tables, we use boldface to denote the best performing model, while underline indicates the best score among the variations of each method. To have a comprehensive overview of the methods in terms of performance, for the node classification task we report the Micro-F 1 scores for training ratios of 10%, 50%, and 90%. As we can observe in Tables 5.6 to 5.8, the instances of EFGE become prominent for various networks-modeling the node interactions with a proper distribution, produces more expressive embeddings. This model performs especially well for 10% training size. On the other hand, TNE and KerneNE show comparable results for larger training sets.

In the link prediction experiments (Table 5.9), the KernelNE-Sch and MKernelNE-Gauss variants show good performance-being the best performing models over the four networks. KernelNE-Gauss is also the method having the highest score over the PPI and Gnutella networks after the bestperforming baseline. We observe that the integration of community infor-mation positively contributes to the performance of the TNE instances, that possess comparable scores.

R A N D O M WA L K D I F F U S I O N M E E T S H A S H I N G F O R S C A L A B L E G R A P H E M B E D D I N G S

M

ost widely used models face computational challenges to scale to large networks, as the size of the networks increases. While there is a recent effort towards designing algorithms that solely deal with scalability issues, most of them behave poorly in terms of accuracy on downstream tasks. In this chapter, we aim at studying models that balance the trade-off between efficiency and accuracy. In particular, we propose NodeSig, a scalable embedding model that computes binary node representations. NodeSig exploits random walk diffusion probabilities via stable random projection hashing towards efficiently computing embeddings in the Hamming space. Our extensive experimental evaluation on various graphs has demonstrated that the proposed model achieves a good balance between accuracy and efficiency compared to well-known baseline models on two downstream tasks.

introduction

As we have discussed in Chapters 2 to 5, the majority of the existing node embedding approaches propose learning-based techniques relying either on matrix factorization or on node context sampling to infer nodes proximities [START_REF] Hamilton | Representation Learning on Graphs: Methods and Applications[END_REF]. However, the computational cost and the high memory usage burden bring limitations to their applicability on large-scale networks. Recent graph representation studies aim to improve running time complexity via matrix sparsification techniques [START_REF] Qiu | NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization[END_REF] or capitalizing on hierarchical graph representations [START_REF] Vincent D Blondel | Fast unfolding of communities in large networks[END_REF] but the quality of the embeddings deteriorates significantly.

Besides the computational burden of model optimization, most of the proposed algorithms learn low-dimensional embeddings in the Euclidean space. A few recent studies have suggested learning discrete node representations [Lia+18; Wu+18; Yan+19], in which Hamming distance is leveraged to compute the pairwise similarity of embedding vectors very fast. The basic idea builds upon fast sketching techniques for scalable similarity search, mainly based on data-independent or data-dependent hashing techniques [START_REF] Wang | A Survey on Learning to Hash[END_REF].

Although binary embeddings speedup distance measure computations, the corresponding models often undergo computationally intensive learning procedures, especially in the case of learning-to-hash models [START_REF] Lian | High-Order Proximity Preserving Information Network Hashing[END_REF].

In this chapter, we propose NodeSig, a scalable model for computing expressive binary node embeddings based on stable random projections. NodeSig first leverages random walk diffusions to estimate higher-order node proximity. Then, a properly defined sign random projection hashing technique is applied to obtain binary node signatures in the Hamming space, leading to an approximation of the chi similarity (χ) [START_REF] Pele | The Quadratic-Chi Histogram Distance Family[END_REF] between the proximity vectors in the original space. Since these vectors are constructed based on the occurrence frequencies of nodes within random walks, chi similarity emerges as a natural choice of similarity metric, frequently used to compare histograms in various areas including natural language processing and computer vision [START_REF] Ye | Multi-Label Active Learning with Chi-Square Statistics for Image Classification[END_REF][START_REF] Huong | Centroid neural network with Chi square distance measure for texture classification[END_REF]. Each component of NodeSig has been designed to ensure the scalability of the model, while at the same time the accuracy on downstream tasks is not compromised or even improves compared to traditional models. Figure 6.1 positions NodeSig regarding accuracy and running time, providing a comparison to different models on the DBLP network. As we observe, NodeSig's running time is comparable to that of models that focus solely on scalability (e.g., NodeSketch, RandNE, LouvainNE), with improved accuracy even higher than Node2Vec or HOPE in this particular dataset. The main contributions of the chapter can be summarized as follows:

• We introduce NodeSig, a scalable and expressive model for binary node embeddings based on stable random projection hashing of random walk diffusion probabilities. NodeSig leverages higher-order proximity information among nodes, while its design allows scaling to large graphs without sacrificing accuracy.

• The distance computation between node signatures in the embedding space is provided by the Hamming distance on bit vectors, which is significantly more efficient than distance computations based on other distance measures. Besides, NodeSig can easily be extended to deal with dynamic networks since the computation of node embeddings are entirely independent of each other. In other words, the embedding of a particular node relies on local information without requiring knowledge about other nodes' representations.

• In a thorough experimental evaluation, we demonstrate that the proposed binary embeddings achieve superior performance compared to various baseline models on two downstream tasks. At the same time, the running time required to compute node signatures allows the model to scale on large graphs.

The rest of the chapter is organized as follows. Section 6.2 presents related work in the field. Section 6.3 presents the proposed approach in detail. Performance evaluation results are offered in Section 6.4, whereas Section 6.5 discusses the potential of the approach for dynamic networks. Finally, we summarize the work in Section 6.6. source code.

The implementation of the proposed model in C++ can be found at the address: https://abdcelikkanat.github.io/projects/nodesig/.

related work

The main limitation of the conventional graph representation learning techniques is that they do not scale well for large networks. The main focus has been put on increasing the effectiveness of data mining tasks (e.g., classification, link prediction, network reconstruction) whereas the efficiency dimension has not received significant attention. To attack this problem, recent advances in GRL use random projection or hashing techniques (more specifically, variants of locality-sensitive hashing) in order to boost performance, trying to maintain effectiveness as well.

One of the first scalable approaches (RandNE) was proposed in [START_REF] Zhang | Billion-Scale Network Embedding with Iterative Random Projection[END_REF]. RandNE is based on iterative Gaussian random projection, being able to adapt to any desired proximity level. In the same line, FastRP was proposed in [START_REF] Chen | Fast and Accurate Network Embeddings via Very Sparse Random Projection[END_REF] which is faster than RandNE and also more accurate. Lou-vainNE [START_REF] Kumar Bhowmick | LouvainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding[END_REF] suggested learning node representations by aggregating the embeddings of nodes extracted at varying levels of the hierarchy.

Recently, embedding techniques based on hashing have emerged as a promising alternative to enable faster processing while at the same time retain good accuracy results. The NetHash algorithm, proposed in [START_REF] Wu | Efficient Attributed Network Embedding via Recursive Randomized Hashing[END_REF], expands each node of the graph into a rooted tree, and then by using a bottom-up approach encodes structural information as well as attribute values into minhash signatures in a recursive manner. A similar approach has been used in NodeSketch [START_REF] Yang | NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching[END_REF], where the context of every node is defined in a different way whereas the embedding vector of each node contains integer values and the weighted Jaccard similarity coefficient is being used. Based on performance evaluation results reported in [START_REF] Yang | NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching[END_REF], NodeSketch is extremely efficient managing to reduce the embedding cost by orders of magnitude in comparison to baseline approaches. Moreover, NodeSketch achieves comparable (or even better) F1 score in the node classification task as well as comparable or better precision in the link prediction task with respect to the baseline techniques.

Our proposed model, NodeSig, takes a different approach. First, it samples weights from the Cauchy distribution in order to construct the projection matrix. Then, it obtains the projected values by performing recursive update walk diffusion probabilities, and then we demonstrate how the random projections can efficiently be performed by propagating the sampled weights without the need for the explicit realization of the target matrix. Finally, we obtain the binary representations by incorporating a nonlinear mapping through a simple sign function. An overview of the basic steps of NodeSig is given in Figure 1.1.

Random Walk Diffusion for Node Proximity Estimation

In most cases, direct links among nodes are not sufficient to grasp various inherent properties of the network that are related to node proximity. It is highly probable that the network might have missing or noisy connections, thus relying solely on first-order proximity can reduce the expressiveness of the model. Random walk diffusions constitute an interesting way to leverage higher-order information while computing embeddings. The underlying idea relies on the co-occurrence frequencies of nodes up to a certain distance in the random walks; nodes appearing more frequently close to each other within the random walks share similar characteristics, and therefore should be placed close to each other in the embedding space. This idea has been exploited by various representation learning models [PARS14; GL16] and our works [C ¸M20; C ¸M19a; C ¸M21] described in the previous chapters. Nevertheless, sampling multiple random walks, as used in various models significantly increases the training time causing scalability issues.

To overcome this problem, in this chapter we directly leverage random walk diffusions, adopting a uniform random walking strategy to extract information describing the structural roles of nodes in the network. Let P used to denote the right stochastic matrix associated with the adjacency matrix W of the graph, which is obtained by normalizing the rows of the matrix. More formally, P can be written as P (v,u) := W (v,u) / ∑ x∈V W (v,x) , defining the transition probabilities of the uniform random walk strategy. We use a slightly modified version of the transition matrix by adding a self-loop on each node, in case it does not exist.

Note that the probability of visiting the next node depends only on the current node that the random walk resides; therefore, node u can be visited starting from v by taking l steps with probability P (l) (v,u) , if there is a path connecting them. For a given walk length L, we define the matrix M as

M := P + • • • + P (l) + • • • + P (L) ,
where P (l) indicates the l-order proximity matrix and each entry M (v,u) in fact specifies the expectation of visiting u starting from node v within L steps. By introducing an additional parameter α, M(α) can be rewritten by:

M(α) := αP + • • • + α (l) P (l) + • • • + α (L) P (L) .
Higher order node proximities can be captured using longer walk lengths, where the impact of the walk at different steps is controlled by the importance factor α. As we will present in the next paragraph, matrix M(α) is properly exploited by a random projection hashing strategy to efficiently compute binary node representations.

Learning Binary Embeddings

Random projection methods [START_REF] Vempala | The random projection method[END_REF] have been widely used in a wide range of machine learning applications that are dealing with large scale data. They mainly target to represent data points into a lower dimensional space by preserving the similarity in the original space. Here, we aim at encoding each node of the network in a Hamming space H d H , {0, 1} d ; we consider the normalized Hamming distance d H as the distance metric [START_REF] Yi | Binary Embedding: Fundamental Limits and Fast Algorithm[END_REF]. The benefit of binary representations is twofold: first, they will allow us to perform efficient distance computation using bitwise operations, and secondly reduce the required disk space to store the data.

Random projections are linear mappings; the binary embeddings though require nonlinear functions to perform the discretization step, and a natural choice is to consider the signs of the values obtained by the Johnson-Lindenstrauss (JL) [START_REF] Johnson | Extensions of lipschitz maps into Banach spaces[END_REF] transform. More formally, it can be written that

h W (x) := sign(x W),
where W is the projection matrix whose entries W (i,j) are independently drawn from normal distribution and sign(x) j is equal to 1 if x j > 0 and 0 otherwise. The approach was first introduced by Goemans and Williamson [START_REF] Michel | Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming[END_REF] for a rounding scheme in approximation algorithms, demonstrating that the probability of obtaining different values for a single bit quantization is proportional to the angle between vectors, as it is shown in Theorem 6.1. The main idea relies on sampling uniformly distributed random hyperplanes in R d . Each column of the projection matrix, in fact, defines a hyperplane and the arc between vectors x and y on the unit sphere is intersected if h W (x) j and h W (y) j take different values. Theorem 6.1 ([GW95]). For a given pair of vectors x, y ∈ R n ,

P h W (x) j = h W (y) j = 1 π cos -1 x y x 2 y 2 ,
where W (i,j) ∼ N (0, 1) for 1 ≤ i, j ≤ N.

Although the signs of JL random projections allow us to approximate the angle between the vectors in the original space, in our settings, we would prefer to preserve a distance metric that can fit better the input data M(α). Note that, the node proximity matrix M(α) contains non-negative elements that are computed based on the occurrence frequencies of nodes within random walks. Hence, we will focus on estimating distance metrics capable of comparing histogram-type data by properly redesigning the projection matrix. The stable random projections approach [START_REF] Li | Sign Cauchy Projections and Chi-Square Kernel[END_REF] generalizes the aforementioned idea by using a symmetric α-stable distribution with unit scale in order to sample the elements of the projection matrix, for 0 < α ≤ 2. Li et al. [START_REF] Li | Sign Cauchy Projections and Chi-Square Kernel[END_REF] proposed the following upper bound

P h W (x) j = h W (y) j ≤ 1 π cos -1 ρ α (6.1)
for non-negative vectors (x i ≥ 0, y i ≥ 0, 1 ≤ i ≤ N), where ρ α is defined by

ρ α := ∑ m=1 x α/2 m y α/2 m ∑ m=1 x α i ∑ m=1 y α m 2/α .
It is well known that the bound is exact for α = 2, which also corresponds to the special case in which normal random projections are performed. When the vectors are chosen from the 1 (R + ) space (i.e., ∑ i=1 x i = 1, ∑ i=1 y i = 1), it is easy to see that the χ 2 similarity ρ χ 2 defined as ∑ i=1 (2x i y i )/(x i + y i ) is always greater or equal to ρ 1 , as suggested by Lemma 6.1. Lemma 6.1. For given x, y ∈ R d satisfying x i , y i ≥ 0 for all 1 ≤ i ≤ d and

∑ i=1 x i = ∑ i=1 y i = 1, then ρ 1 ≤ ρ χ 2 .
Proof.

ρ 1 = ∑ i=1 x 1/2 i y 1/2 i √ ∑ i=1 x i ∑ i=1 y i 2 = ∑ i=1 √ x i y i 2 = ∑ i=1 2x i y i √ x i + y i √ x i + y i √ 2 2 ≤ ∑ i=1 2x i y i x i + y i ∑ i=1 x i + y i 2 = ∑ i=1 2x i y i x i + y i = ρ χ 2 ,
where the inequality follows from the Cauchy-Schwarz inequality.

Besides, it has been empirically shown [START_REF] Li | Sign Cauchy Projections and Chi-Square Kernel[END_REF] that the collision probability for Cauchy random projections with unit scale can be well estimated, especially for sparse data:

P h W (x) j = h W (y) j ≈ 1 π cos -1 ρ χ 2 ≤ 1 π cos -1 ρ 1 . (6.2)
Note that, the matrix M(α) described in the previous paragraph consists of non-negative values; its row sums are equal to ∑ L l=1 α (l) and M(α) is sparse enough for small walk lengths. Therefore, we design the projection matrix by sampling its entries from the Cauchy distribution, aiming to learn binary representations preserving the chi-square similarity. The chi-square distance is one of the measures used for histogram-based data, commonly used in the fields of computer vision and natural language processing [Ye+15; Huo+09]. for each neighbour node u ∈ N (v) do 9:

temp[v] ← temp[v] + P[v, u] × (W[u] + R[u])
E[v] ← sign(R[v]
) 18: end for for Line 6, since the required computation for each node is completely independent.

Discussion for Dynamic Networks

The majority of existing network representation learning models have been developed for static networks. Nevertheless, most real-world networks undergo structural changes and evolve over time with the addition and removal of links and nodes [START_REF] Seyed Mehran Kazemi | Representation Learning for Dynamic Graphs: A Survey[END_REF]. Therefore, being able to design models that properly adapt to dynamic networks is an important point to investigate.

As we discuss here, the proposed method allows for efficient updates of the embeddings, without requiring any costly learning procedures.

More precisely, the key point in the dynamic case, is that the learned embedding vectors should be efficiently updated instead of being recalculated from scratch. If an edge is added or removed for a pair of nodes (u, v) ∈ V × V, the terms R (l) (w,:) in Equation (6.3) for node w ∈ V are affected, for all l > k := min{dist(w, u), dist(w, v)}-thus, it suffices to update only these affected terms. The transition probabilities for nodes u and v also change even though the remaining nodes are not affected, so all the terms P (v,:) must be divided by ∑ w∈N (v) P (v,w) in order to normalize the transition probabilities and similarly the same procedure must also be applied to node u after each edge insertion and deletion operation.

Evidently, more research is required towards this direction in order to provide a method that scales well when the input data changes rapidly (i.e., in the form of a stream).

experimental evaluation

In this section, we report empirical evaluation results demonstrating the effectiveness and efficiency of NodeSig compared to baseline algorithms. All the experiments have been performed on an Intel Xeon 2.4GHz CPU server (32 Cores) with 60GB of memory.

Datasets and Baseline Models

datasets.

We perform experiments on networks of different scales and types. In addition to the networks that we have described in Chapter 2, we also use Blogcatalog [START_REF] Tang | Relational Learning via Latent Social Dimensions[END_REF], which is a social network constructed by using the relationships among bloggers, where node labels indicate the blog categories specified by the blogger. The network contains 10, 312 nodes, 333, 893 edges and 39 labels. Youtube [START_REF] Tang | Scalable Learning of Collective Behavior Based on Sparse Social Dimensions[END_REF] which has been crawled from the corresponding video sharing platform. Node labels indicate categories of videos among 47 possible options and it exactly consists of 1, 138, 499 nodes and 2, 990, 443 edges. baseline models.

We have considered six representative baseline methods in the evaluation. In particular, two of these methods (Node2Vec, LINE) correspond to widely used node embedding models that we have also employed in previous chapters. The remaining ones constitute more recent models aiming to address the scalability challenge, which we provide brief information about them below. For all methods, we learn embedding vectors of size 128.

• NetSMF [START_REF] Qiu | NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization[END_REF] is a sparse matrix factorization method, recently proposed to deal with the scalability constraints of NetMF [START_REF] Qiu | Network Embedding As Matrix Factorization: Unifying DeepWalk, LINE, PTE, and Node2Vec[END_REF]-a model that relies on the pointwise mutual information of node co-occurrences. In our experiments, we set the rank parameter to 512 and the number of rounds to 10, 000 for all networks except PPI and Youtube in which the model was unable to run. In these cases, the rank parameter is set to 256, while the number of rounds to 1, 000 and 50 for PPI and Youtube, respectively.

• RandNE [START_REF] Zhang | Billion-Scale Network Embedding with Iterative Random Projection[END_REF] is an efficient method based on Gaussian random projections, and one of the most widely applied scalable models. The experiments were conducted by setting the parameters suggested by the authors. In the case of node classification, the transition matrix with parameter values q = 3 and weights = [1, 10 2 , 10 4 , 10 5 ] was used, while the adjacency matrix with q = 2 and weights = [1, 1, 10 -2 ] was considered in the link prediction experiments.

• LouvainNE [Bho+20] constructs a hierarchical subgraph structure and aggregates the node representations learned at each different level to obtain the final embeddings. In our experiments, we have used the recommended parameter settings and α was set to 0.01.

• NodeSketch [START_REF] Yang | NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching[END_REF] learns embeddings in the Hamming space, using minhash signatures. For the Cora network, we have performed parameter tuning for the values of α and order k, which are set to 0.1 and 20, respectively. For the remaining datasets, we have used the best-performing settings recommended by the authors.

For simplicity, we set the importance factor α to 1 in all the experiments of NodeSig, as we have observed that the algorithm shows comparable performance for values close to 1; a detailed analysis of the behaviour of NodeSig with respect to the importance factor is given in Section 6.4.4. The walk length is set to 3 for Cora, and to 5 for all the other networks in the classification experiment. For the link prediction task, the walk length is chosen as 15 for all networks. We set the dimension size of the embedding vectors to 8, 192 bits in order to be consistent with the experiments with the baseline methods, since modern computer architectures use 8 Bytes for storing floating point data types.

Multi-label Node Classification

The networks described previously consist of nodes having at least one or more labels. In the classification task, our goal is to correctly infer the labels of nodes chosen for the testing set, using the learned representations and the labels of nodes in the rest of the network, namely the nodes in the training set. The evaluation follows a strategy similar to the one used by baseline models [START_REF] Yang | NodeSketch: Highly-Efficient Graph Embeddings via Recursive Sketching[END_REF].

experimental set-up.

The experiments are carried out by training an one-vs-rest SVM classifier with a pre-computed kernel, which is designed by computing the similarities of node embeddings. The similarity measure is chosen depending on the algorithm that we use to learn representations. More specifically, the Hamming similarity for NodeSketch and the Cosine similarity for the rest baselines methods are chosen in order to build the kernels for the classifier. For NodeSig, we use the chi similarity χ, defined as 1 -d χ 2 , where d χ 2 is equal to for the vectors satisfying ∑ j x j = ∑ j y j = 1 and x j ≥ 0, y j ≥ 0 for all 1 ≤ j ≤ d. Hence, we apply a small transformation while constructing the kernel matrix of the SVM in order to approximate the chi similarity, instead of using cos -1 ρ χ 2 /π in Equation (6.2), which is estimated directly via the Hamming distance.

d χ 2 := d ∑ i=1 (x j -y j ) 2 x j + y j = d ∑ j=1 (x j + y j ) - d ∑ m=1 4x j y j x j + y j = 2 -2ρ χ 2 ,
experimental results.

For the multi-label node classification task, Tables 6.1 to 6.5 report the average Micro-F 1 and Macro-F 1 scores over 10 runs, where the experiments are performed on different training set sizes. The symbol "-" is used to indicate that the corresponding algorithm is unable to run due to excessive memory usage or because it requires more than one day to complete. The best and second best performing models for each training ratio (10%, 50%, and 90%) are indicated with bold and underlined text, respectively.

As we observe, NodeSig consistently outperforms the baselines for higher training ratios on the Blogcatalog and Cora networks, while the obtained Macro-F 1 score is very close to the performance of NetSMF for 10% training ratio on Blogcatalog. In the case of the Cora network which corresponds to the smallest one used in our study, Node2Vec shows better performance for small training ratio of 10%. For the Youtube and DBLP networks, the proposed NodeSig model along with NodeSketch perform equally well. This is quite surprising, since both these methods that correspond to data-independent hashing techniques offer a clear performance gain over traditional models, such as Node2Vec and HOPE. Lastly, for the PPI dataset, NodeSig obtains consistently the highest scores for Micro-F 1 , while its main competitor, NodeSketch, has close performance for the Macro-F 1 score.

Link Prediction

The second downstream task used to assess the quality of node embeddings is the one of link prediction.

experimental set-up.

As we have described in the previous chapter, half of the edges of a given network are removed by still keeping the residual network connected. Node embeddings are learned on the rest of the graph. As it has been described in Section 6.4.2, we build the features corresponding to the node pair samples using the similarities between embedding vectors; the similarity measure is chosen depending on the algorithm that we use to extract the representations. Since the Youtube dataset is relatively larger than the rest of the networks, we work on 7% of its initial size. We predict edges by constructing the similarity list of edges, and we provide the Area Under Curve (AUC) scores in Table 6.6. experimental results.

For the link prediction task, NodeSig acquires the highest AUC scores on three datasets, while it is also the second best performing model for the remaining two. In the case of the Youtube dataset, all baselines demonstrate comparable results. Although Node2Vec shows good performance across most datasets in the link prediction task, it does not perform well on the Blogcatalog networks, mainly because of its high density. On the other hand, NodeSig reaches the highest score on this dataset, with a clear difference to its main competitor, NodeSketch.

Parameter Sensitivity

Next, we analyze how the behavior of the proposed NodeSig algorithm is affected by the parameter setting. More specifically, we concentrate on the influence of three parameters, namely walk length L, importance factor α and dimension size d, examining the impact on the Cora network.

effect of walk length.

In order to examine the influence of the walk length on the performance, we perform experiments for varying lengths by fixing the importance factor α to 1.0. Figure 6.3 depicts the Micro-F 1 scores for different training ratios. We observe a significant increase in performance when the walk length increases, particularly for small training ratios and walk lengths. Although it shows a wavy behavior for the largest training ratio, there is a logarithmic improvement depending on the walk length. NodeSig better captures the structural properties of the network in longer walks, thus the low performance observed on small training ratios can be compensated with longer walks. effect of importance factor.

The importance factor is another parameter of NodeSig, which controls the impact of walks of different lengths: the importance of the higher levels is increasing for α > 1, while it can be diminished choosing α < 1. Figure 6.3 depicts the performance of NodeSig on the Cora network, fixing the walk length value to 3. Although we do not observe a steady behavior for the large training set, higher values of α, especially around 4, positively contribute to the performance; values smaller than 1 have negative impact on the performance.

effect of dimension size.

The dimension size is a crucial parameter affecting the performance of the algorithm, since a better approximation to the chi similarity measure can be obtained for larger dimension sizes, following Hoeffding's inequality [START_REF] Hoeffding | Probability Inequalities for Sums of Bounded Random Variables[END_REF]. Therefore, we perform experiments for varying dimension sizes, by fixing the walk length to 3. Figure 6.3 depicts the Micro-F 1 scores of the classification experiment for different dimension sizes ranging from 2 9 to 2 17 . Although we have fluctuating scores on the large training set due to the randomized behavior of the approach, the impact of the dimension size can be observed clearly on the small training set size. On the other hand, we observe an almost stable behavior for the training ratio of 50%, encouraging the use of small embedding sizes towards reducing storage requirements.

Running Time Comparison

The running time is of great importance, since the embedding models are expected to scale and run in reasonable time on large graphs. We have recorded the elapsed real (wall clock) time of all baseline models including the one of NodeSig, and the results are provided in n = 100, 000 and p = 0.0001. All the experiments have been conducted on the server whose specifications have been given in the beginning of Section 6.4. We use 32 threads for each algorithm, when it is applicable. If a model cannot run due to excessive memory usage with the parameter settings described in Section 6.4.1, the parameters are set to values closest to its default parameters, which enables the models to run in reasonable time. For NodeSig, the walk length is set to 5, and α to 1 in all experiments.

As we observe, NodeSig runs faster than HOPE, Node2Vec as well as NetSMF. This is happening because HOPE requires an expensive matrix factorization, while Node2Vec needs to simulate random walks to obtain their exact realizations. Although NetSMF has been proposed as the scalable extension of another matrix factorization model [START_REF] Qiu | Network Embedding As Matrix Factorization: Unifying DeepWalk, LINE, PTE, and Node2Vec[END_REF], we have observed that it requires high memory footprint; therefore, we could not run it with the default parameters specified by the authors of the corresponding paper. Furthermore, although the remaining baseline methods run faster compared to NodeSig, as we have already presented, the proposed model generally outperforms them both in classification and link prediction tasks. These experiments further support the intuition about designing NodeSig, as an expressive model that balances accuracy and running time.

discussion for dynamic networks

The majority of existing network representation learning models have been developed for static networks. Nevertheless, most real-world networks undergo structural changes and evolve over time with the addition and removal of links and nodes [START_REF] Seyed Mehran Kazemi | Representation Learning for Dynamic Graphs: A Survey[END_REF]. Therefore, being able to design models that properly adapt to dynamic networks is an important point to investigate. As we discuss here, the proposed method allows for efficient updates of the embeddings, without requiring any costly learning procedures.

More precisely, the key point in the dynamic case, is that the learned embedding vectors should be efficiently updated instead of being recalculated from scratch. If an edge is added or removed for a pair of nodes (u, v) ∈ V × V, the terms R (l) (w,:) in Equation (6.3) for node w ∈ V are affected, for all l > k := min{dist(w, u), dist(w, v)}-thus, it suffices to update only these affected terms. The transition probabilities for nodes u and v also change even though the remaining nodes are not affected, so all the terms P (v,:) must be divided by ∑ w∈N (v) P (v,w) in order to normalize the transition probabilities and similarly the same procedure must also be applied to node u after each edge insertion and deletion operation.

Evidently, more research is required towards this direction in order to provide a method that scales well when the input data changes rapidly (i.e., in the form of a stream).

conclusions and future work

In this chapter, we have introduced NodeSig, an efficient binary node embedding model. Each component of model has properly been designed to improve scalability without sacrificing effectiveness on downstream tasks. NodeSig exploits random walk diffusion probabilities via stable random projection hashing, towards efficiently computing representations in the Hamming space that approximate the chi similarity. The experimental results have demonstrated that NodeSig outperformed in accuracy recent highlyscalable models, being able to run within reasonable time duration, while at the same time it shows comparable or even better accuracy with respect to widely used baseline methods in multi-label node classification and link prediction. As future work, we plan to further study the properties of the model for attributed and dynamic networks and also study the performance of parallel/distributed alternatives.

C O N C L U S I O N

The appearance of graph-structured data in many application domains has stirred the development of graph learning tools. In recent years, the focus of research studies has shifted towards techniques that automatically extract feature vectors, thereby encouraging the interest in graph representation learning. These features are further used to perform various downstream tasks, so numerous approaches have been developed targeting different aspects of the problem. In this dissertation, we have considered methods leveraging random walk diffusions to improve the effectiveness and efficiency of node embedding methods.

summary of contributions

We have introduced several algorithms addressing various challenges problems in the field. The main contributions of the thesis can be compiled as follows.

Explicit Integration of Community Information

The community structure is one of the key aspects of complex networks, distinguishing them from random graph structures. A community is a group of nodes having higher connections among them than the rest of the network, where these nodes can share common characteristics. In light of this fact, in Chapter 3 we have proposed a novel framework, Topical Node Embedding (TNE), which explicitly incorporates the underlying community structure in the representation learning process. TNE extracts the latent node community assignments with various community detection methods and statistical models relying on graphs. Then, it learns node and community embeddings independently by means of the generated node sequences, leveraging the SkipGram model. The final representation of nodes is obtained by concatenating their embedding vectors with the community representations. The extensive experimental evaluation has showed that the integration of community information in learning embeddings enhances the node representations' performance in downstream tasks.

Modeling Node Interactions with Exponential Family Distributions

Most of the random walk-based models presented in the literature, rely on [START_REF] Mikolov | Efficient Estimation of Word Representations in Vector Space[END_REF] to model the interactions between nodes appearing in the generated node sequences. Nevertheless, this could cause limitations concerning the expressiveness of the model. To address this point, we have introduced the EFGE model in Chapter 4, which leverages exponential family conditional distributions. In particular, we have employed three instances of exponential family distributions to represent the interactions among nodes and learn their representations. We have further shown the connection between BigClam, a well-known overlapping community detection method, and the variants of the EFGE model under appropriate parameter settings. The experimental evaluation has demonstrated the benefit of exponential family distributions on the performance of downstream tasks.

A Kernelized Matrix Factorization Framework Based on Random Walks

Kernel functions are generally applied on linear models to enhance their modeling capacity, allowing them to capture complex non-linear structures existing in data. In Chapter 5, we have adopted universal kernels under a matrix factorization framework to learn node representations. We have proposed KernelNE, a model which leverages random walks to mitigate the computational burden of the optimization step and the exact realization of the target matrix. To further strengthen the predictive capabilities, we have introduced MKernelNE, a multiple kernel learning formulation of the model. The experiments have shown that we could learn more expressive embedding vectors grasping the complex co-occurrence information patterns of nodes within the random walks by means of kernel functions.

Scalable Graph Representation Learning

With the growing size of networks, many learning-based graph representation learning models become inapplicable to large-scale networks. Therefore, in recent years, the research community has concentrated on developing approaches that take advantage of sketching techniques to overcome this problem. In Chapter 6, we have introduced a novel approach, NodeSig, which is capable of handling networks consisting of millions of nodes and edges. NodeSig learns binary representations in the Hamming space utilizing sign α-stable random projections, which allows to approximate the chi similarity between random walk-based node representations. We have further developed an approach to carry out projections of the features in a recursive way without the need of realizing the exact matrix. We have shown that the proposed approach balances the trade-off between the performance in downstream tasks and the computational burden for large-scale networks.

future directions

Although we have observed an immense increase in the number of research studies in graph representation learning over the past few years, there are still various subjects worthy of discussion. In this section, we will briefly describe ongoing and possible research topics for future work.

Dynamic Networks

Most graph representation learning approaches have primarily focused on static networks. Nevertheless, many real-world networks naturally undergo changes over time. For instance, each time a new user joins a social network platform, the connections that she makes to other users cause a change in the network structure and contribute to the evolution of the network. Therefore, developing efficient representation learning techniques for dynamic networks is of great significance. Classical representation learning methods can be used for learning the embeddings of a dynamic network at each particular state; the embedding vectors though should be updated concerning the modifications occurring in the network. For instance, in the case of random walk-based methods, which this dissertation also relies on, can be adapted for dynamic networks. A possible idea might be to perform random walks only for the nodes which have been affected by the change that happened in the network, within a certain time interval. If a node is removed from the network, then we can also remove the existing walks containing it, or we can perform new random walks for an inserted node [START_REF] Nguyen | Dynamic Network Embeddings: From Random Walks to Temporal Random Walks[END_REF][START_REF] Seyed Mehran Kazemi | Representation Learning for Dynamic Graphs: A Survey[END_REF]. Then, the node representations can be updated based on this new set of walks. Dynamic networks might also possess additional rich semantics, including node and edge features, thereby taking this additional information into account while updating the embeddings could constitute another future research direction.

Scalable Algorithms

Networks consisting of millions of nodes and edges have recently become ubiquitous in various disciplines, such as biology, recommender systems, and social sciences-making scalability a core property in the algorithm design process. As we have discussed in Chapter 2 and Chapter 6, approaches relying on sketching techniques have recently become prominent in the field, as they constitute a quite effective framework in computing embeddings. The idea mainly relies on first constructing feature vectors corresponding to the nodes of the graph; these vectors are then given as input to a hashing algorithm to compute signatures, which are used as embeddings. The input data for the sketching algorithms should also be carefully designed. Choosing simple vectors, such as the rows of the adjacency matrix, might not convey sufficient information about node proximity, thus causing limitations on the predictions on downstream tasks. On the other hand, designing higher-order proximity matrices requires high computational cost for largescale networks. Therefore, building informative node features in an efficient way that can be used as input to hashing algorithms, is still a crucial problem to investigate. It can be tackled with recursive techniques, provided that it is allowed by the sketching scheme, as we have adopted in the NodeSig method proposed in Chapter 6. Nevertheless, the chosen sketching technique should also be compatible with the assumptions of the feature data, including the distance measure.

There are mainly two different hashing techniques: locality sensitive hashing (LSH) and learning to hash [START_REF] Wang | A Survey on Learning to Hash[END_REF]. LSH algorithms are dataindependent, and have extensively been employed in various domains, ranging from natural language processing to computer vision. A typical example is the sign random projections technique, which learns binary representations preserving the angular similarity of the input vectors [START_REF] Li | Sign Cauchy Projections and Chi-Square Kernel[END_REF]. Although graph representation learning methods relying on LSH propose fast sketching schemes, their performance is often limited compared to more traditional learning-based models. Learning to hash approaches can be an alternative to overcome this limitation, constituting a promising future research direction. They aim to learn hash functions for a given dataset by minimizing the discrepancy between the similarities in the original space and the embedding space. Learning to hash enables to adapt a wide range of various hash functions. For instance, one can incorporate kernel functions [START_REF] He | Scalable similarity search with optimized kernel hashing[END_REF] with the data vectors of nodes in order to learn the projection matrix, leading to better performance on downstream tasks. Moreover, as we have discussed in the previous section, adapting such methods to compute embedding in large-scale dynamic networks constitutes another interesting direction.

Graph Neural Networks

Graph Neural Networks (GNNs) [START_REF] Hamilton | Representation Learning on Graphs: Methods and Applications[END_REF][START_REF] Hamilton | Graph Representation Learning[END_REF] provide effective tools for graph analysis tasks by learning node or network embeddings in a lowerdimensional space. They constitute powerful models enabling to incorporate side information such as node features with the network structure in the representation learning process. Nevertheless, GNNs require expensive computational resources, especially for large networks-making scalability a vital property to investigate.

The early GNN models [KW17; Vel+18] have required the whole network structure and the features in the memory during the optimization step. Therefore, they were not very suitable especially for large-scale networks. Furthermore, graph sampling strategies [START_REF] Hamilton | Inductive Representation Learning on Large Graphs[END_REF][START_REF] Hamilton | Graph Representation Learning[END_REF] have become the leading technique to cope with this problem. The idea basically relies on sampling a fixed number of nodes from the k-hop neighborhood of each node. It also acts as an edge dropout process and thus, enhancing performance [START_REF] Rong | DropEdge: Towards Deep Graph Convolutional Networks on Node Classification[END_REF]. Nevertheless, on large-scale graphs, even the sampling process itself is challenging. The number of nodes within the k-hop neighborhood drastically increases even for small k values, since the graph structure is non-Euclidean for many real-world networks. Node sampling might also result in the loss of particular patterns of the network and the deprivation of influential nodes. Therefore, as future work, it is interesting to examine how to properly leverage random walks to address the scalability limitation of GNN models [START_REF] Ying | Graph Convolutional Neural Networks for Web-Scale Recommender Systems[END_REF], while at the same time, preserving key structural properties of the underlying graph that could impact the accuracy on downstream tasks.

Although many GNNs relying on deep architectures [START_REF] Wu | A Comprehensive Survey on Graph Neural Networks[END_REF] have been developed, shallow models also demonstrate comparable performance with less computational complexity [START_REF] Wu | Simplifying Graph Convolutional Networks[END_REF]. Besides, higher number of layers also leads to over-smoothing. Therefore, a promising direction is to investigate how to adapt shallow models with rich diffusion functions towards designing scalable GNN models, without sacrificing the predictive performance [START_REF] Klicpera | Diffusion Improves Graph Learning[END_REF][START_REF] Fabrizio Frasca | SIGN: Scalable Inception Graph Neural Networks[END_REF].

AUC

  T O F A C R O N Y M S / A B B R E V I AT I O N S

Figure 1 . 1 :

 11 Figure 1.1: Overview of the contributions of the thesis.

Figure 2 . 1 :

 21 Figure 2.1: Illustration of different graph types. (a) A simple graph is an unweighted and undirected graph without loops and multi edges; (b) For a directed graph, edges indicate an orientation, and (c) edges can have weights in a weighted graph. (d) In a multigraph, having multiple edges or loops are permitted.

Figure 2 . 3 :

 23 Figure 2.3: Illustration of a random walk generation.

Figure 3 . 1 :

 31 Figure 3.1: Overlapping community structure types in a network.

Figure 3 . 2 :

 32 Figure3.2: The topic-community assignments in Zachary's Karate Club network. Each node v is assigned to a community label z, maximizing the posterior probability Pr(z|v) by using the TNE-Glda model.

Figure 3 . 3 :

 33 Figure 3.3: Schematic representation of the TNE model. The final representations are learned by combining node and topic embedding vectors. The representation of a node is learned using random walks performed over the network; its topic representation is similarly learned by assigning a topic/community label based either on random walks (TNE-Glda, TNE-Ghmm) or network structure-based approaches (TNE-Louvain, TNE-BigClam).

Figure 3 . 4 :

 34 Figure 3.4: Plate representations of random walk-based topic representation models.

  with the negative sampling technique for k sampled instances because we have |W | number of walks and there are 2 • γ • (k + 1) • L center-context pairs for each walk. If the Louvain algorithm is chosen, the communities can be detected in O |V | • log 2 (|V |) operations, while O (|V| • K) steps are required for BigClam when the number of communities is high. The models that rely on random walks and generative models (Glda, Ghmm), can be run in O (W • L • K • I), where I is the number of iterations [Por+08; VG+08].

Figure 3 . 5 :

 35 Figure 3.5: Parameter sensitivity of TNE-Glda and TNE-Louvain models.

  Figure 3.6: Running time analysis of the TNE model on Erd ös-Rényi random graphs.

Figure 3 . 7 :

 37 Figure 3.7: Link sampling in the Stochastic Block Model.

Figure 4 . 1 :

 41 Figure 4.1: Visualization of the Dolphins network composed by 2 communities and the corresponding embeddings for d = 2.

  follows an exponential family distribution. That way, the objective function used to learn node embedding vectors Ω = (A, B) can be rewritten as follows: ) + η w l ,v T(y (l) w,v ) -A(η w l ,v ) + R(A, B), (4.4)

  v) 's, are independent variables. We can express the objective function of the EFGE-Bern model, L B (A, B), by dividing Equation (4.4) into two parts with respect to the values of Y (w,v) and X (l+j) (w,v) :

  4.3.1.1 Relationship to negative samplingAlthough the negative sampling strategy [Mik+13b; MK13] was proposed to approximate the objective function of the SkipGram model, any rigorous theoretical argument showing the connection between them has not been provided. In Lemma 4.1, we show that the log-likelihood L B (A, B) of the EFGE-Bern model in fact can approximated by the objective function of negative sampling given in Equation (4.6). In our implementation, we adopt negative sampling in order to improve the efficiency of the computation. Lemma 4.1. The log-likelihood function L B (A, B) can be approximated by ∑

γ

  (w)|, and k is set to |V \C (l) γ (w)|/|C (l) γ (w)| in the fourth line.4.3.2 The EFGE-Pois ModelIn this model, we will use the Poisson distribution to capture the relationship between context and center nodes in a random walk sequence. Let Y (l) (w,v)

  since the sum of independent Poisson random variables is also Poisson. By plugging the exponential form of the Poisson distribution into Equation (4.3), we can derive the objective function L P (A, B) of the model as:

Figure 4 . 2 :

 42 Figure 4.2: Influence of the dimension size (d) over Citeseer the network.

  Figure 4.3b depicts how the Micro-F 1 scores alter for various value. The results clearly indicate that the model performs well for the value 0.5 of σ. For this reason, we have set

Figure 4 . 3 :

 43 Figure 4.3: Influence of the window size (γ) and standard deviation (σ) of EFGE-Norm on the CiteSeer network for the training set ratio of 50%.

  where M ∈ R |V |×|V | is the target matrix constructed based on the desired properties of a given network, which is used to learn node embeddings A, B ∈ R |V |×d , and • F denotes the Frobenius norm. We will use R(A, B) to denote the regularization term of Equation (5.1). Each element W (v,u) of the weight matrix W ∈ R |V |×|V | captures the importance of the approximation error between nodes v and u, and indicates the Hadamard product.

Figure 5 . 1 :

 51 Figure 5.1: Schematic representation of the KernelNE model. A set of node sequences is firstly generated by following a random walk strategy. By using the co-occurrences of node pairs within a certain window size, node representations are learned by optimizing their maps in the feature space.

Algorithm 5. 1

 1 MKernelNE Input: Graph: G = (V, E ) Representation size: d Set of walks: W Window size: γ Kernel function: K Kernel parameter(s): σ Output: Embedding matrix: A 1: Initialize matrices: A, B ∈ R |V |×d /* Extract center-context node pairs */ 2: for all w = (w 1 , . . . , w L ) ∈ W do 3: for l ← 1 to L do 4:for j = 0 ← -γ to γ do 5:A, B, c ← UpdateEmb(A, B, c, w l , w l+j , K, σ)

  Update individual kernel weights */ 8: if number of kernels > 1 then 9: c ← c -η∇ c F M

Figure 5 . 2 :

 52 Figure 5.2: Influence of the dimension size (d) on the Citeseer network.

Figure 5 . 3 :

 53 Figure 5.3: Influence of kernel parameters on the Citeseer network.

Figure 5 . 4 :

 54 Figure 5.4: Comparison of running times of the KernelNE and MKernelNE models with the baselines.

Figure 5 . 5 :

 55 Figure 5.5: Running time analysis of the KernelNE and MKernelNE models on Erd ös-Renyi graphs of varying sizes.

Figure 5 . 6 :

 56 Figure 5.6: Visualization of node embeddings of Dolphins in the 2D space. The node colors indicate community labels, computed using the Louvain algorithm.

Figure 6 . 1 :

 61 Figure 6.1: Comparison of models on the DBLP network. NodeSig balances between good accuracy and low running time.

Algorithm 6. 1

 1 NodeSig Input: Graph: G = (V, E ) with the transition matrix P Representation size: d Walk length: L Importance factor: α Output: Embedding matrix: E /* Initialization */ 1: for each node v ∈ V do 2: R[v] ← 0 d = (0, . . . , 0) 3: W[v] ∼ Cauchy(0, 1) d / ∑ L l=1 α l 4: end for /* Project the matrix with recursive update rules */ 5: for l ← 1 to L do 6:for each node v ∈ V do 7:temp[v] ← 0 d = (0, . . . , 0)8:

Figure 6 . 3 :

 63 Figure 6.3: Influence of various parameters of the NodeSig model in terms of Micro-F 1 score on the Cora network for varying training set.

  1.1 Overview of contributions . . . . . . . . . . . . . . . . Running time analysis of the TNE model . . . . . . . Figure 3.7 Link sampling in the Stochastic Block Model . . . . . Figure 4.1 Visualization of the Dolphins network and embeddings Figure 4.2 Influence of the dimension size of EFGE . . . . . . . . Comparison of models on the DBLP network . . . . . Figure 6.2 Schematic representation of NodeSig . . . . . . . . . Figure 6.3 Influence of the parameters for NodeSig . . . . . . . Statistics of networks . . . . . . . . . . . . . . . . . . . Table 2.2 Binary operators for constructing edge feature vectors Table 3.1 Node classification for TNE on Citeseer . . . . . . . . Table 3.2 Node classification for TNE on Cora . . . . . . . . . . Table 3.3 Node classification for TNE on DBLP . . . . . . . . . Table 3.4 Node classification for TNE on PPI . . . . . . . . . . . Table 3.5 Link prediction task for TNE . . . . . . . . . . . . . . Table 3.6 Node classification for TNE on Stochastic Block Model Table 4.1 Node classification for EFGE on Citeseer network . . . Table 4.2 Node classification for EFGE on Cora network . . . . Table 4.3 Node classification for EFGE on DBLP network . . . Table 4.4 Node classification for EFGE on PPI network . . . . . Table 4.5 Link prediction task for EFGE . . . . . . . . . . . . . . Table 5.1 Node classification for KernelNE on Citeseer . . . . . Table 5.2 Node classification for KernelNE on Cora . . . . . . Table 5.3 Node classification for KernelNE on DBLP . . . . . . Table 5.4

	Figure 2.1	Illustration of different graph types . . . . . . . . . .
	Figure 2.2	Context and center nodes within a window . . . . . .
	Figure 2.3	Illustration of a random walk generation . . . . . . .
	Figure 3.1	Overlapping community structure types . . . . . . . .
	Figure 3.2	Topic-community assignments in the network . . . .
	Figure 3.3	Schematic representation of the TNE model . . . . . .
	Figure 3.4	Random walk-based topic representation models . .
	Figure 3.5	Parameter sensitivity of TNE-Glda and TNE-Louvain
	Figure 3.6
	Figure 4.3	Influence of the window size and standard deviation
	Figure 5.1	Schematic representation of the KernelNE model . .
	Figure 5.2	Influence of the dimension size of KernelNE . . . .
	Figure 5.3	Influence of kernel parameters of KernelNE . . . . .
	Figure 5.4	Comparison of running times . . . . . . . . . . . . . .
	Figure 5.5	Running time analysis of KernelNE and MKernelNE
	Figure 5.6	Visualization of node embeddings of Dolphins . . . .
	Figure 6.1

xvii L I S T O F TA B L E S Table 2.1

Table 6 . 1

 61 Node classification for NodeSig on Blogcatalog . . . . Table 6.2 Node classification for NodeSig on Cora . . . . . . . . Table 6.3 Node classification for NodeSig on DBLP . . . . . . . Table 6.4 Node classification for NodeSig on PPI . . . . . . . . Table 6.5 Node classification for NodeSig on Youtube . . . . . .

	symbol	meaning
	γ	Window size
	χ	Chi similarity
	A[v]	Representation of context node v
	B[v]	Representation of center node v
	C C d	(l) γ (w)	Number of connected components Context set of node w l in the walk w Representation size
	E G	Edge set Graph
	k		Number of negative samples

Table 6.6 Link prediction task for NodeSig . . . . . . . . . . . . Table 6.7 Running time analysis and average speedup . . . . . xix L I S T O F S Y M B O L S

  It is called Markov Chain if it satisfiesµ{X t+1 = y t+1 |X t , . . . , X 0 } = µ{X t+1 = y t+1 |X t },for all y t+1 ∈ Y and t ≥ 0.

Definition 2.13. A discrete-time stochastic process on a countable set Y is a collection of Y-valued random variables {X t : t ≥ 0} defined on a probability space (X, X , µ). Definition 2.14. A Markov chain X = {X t : t ≥ 0} with memory m is a stochastic process satisfying

  Statistics of networks |V |: number of nodes, |E |: number of edges, |K|: number of labels and |C|: number of connected components.

	|V | CiteSeer 3,312 Cora 2,708 DBLP 27,199 66,832 |E | 4,660 5,278 PPI 3,890 38,739	|K| 6 7 4 50	|C| 438 78 2,115 35	Avg. Degree Type 2.814 Citation 3.898 Citation 4.914 Collaboration 19.917 Biological
	AstroPh 17,903 19,7031 24,827 HepTh 8,638 88,234 Facebook 4,039 Gnutella 8,104 26,008	----	1 1 1 1	22.010 5.7483 43.6910 6.4186	Collaboration Collaboration Social network Peer-to-peer
	Table 2.1:

  Output: Embedding vectors of length: d n + d t 1: Perform N random walks of length L for each node 2: Learn node representations by optimizing Equation (3.1)

	Number of walks: N Walk length: L Window size: γ
	Number of communities: K Topic representation learning method: T Node embedding size: d n Community embedding size: d t

) Algorithm 3.1 Topical Node Embeddings (TNE) Input: Graph: G = (V, E ) 3: Learn topic representations by optimizing Equation (3.5), using any of the models T of Section 3.3 4: Concatenate node and topic embeddings with Equation (3.6)

404 0.452 0.476 0.493 0.506 0.560 0.576 0.582 0.594

			2%	4%	6%	8%	10% 30% 50%	70%	90%
		DeepWalk	0.421 0.462 0.488 0.502 0.517 0.569 0.587 0.596 0.597 0.374 0.419 0.446 0.461 0.476 0.524 0.540 0.547 0.546
		Node2Vec	0.451 0.491 0.514 0.529 0.543 0.583 0.595 0.600 0.603 0.397 0.443 0.466 0.483 0.497 0.535 0.546 0.549 0.550
	Baselines	LINE HOPE NetMF	0.300 0.353 0.384 0.407 0.418 0.476 0.494 0.505 0.512 0.243 0.303 0.334 0.357 0.367 0.423 0.440 0.448 0.454 0.197 0.204 0.207 0.208 0.216 0.253 0.276 0.299 0.316 0.060 0.065 0.066 0.068 0.075 0.121 0.150 0.178 0.202 0.401 0.473 0.507 0.525 0.538 0.579 0.590 0.594 0.601 0.346 0.421 0.454 0.474 0.487 0.528 0.538 0.542 0.548
		GEMSEC	0.384 0.439 0.459 0.479 0.491 0.532 0.545 0.552 0.558 0.339 0.400 0.422 0.439 0.451 0.488 0.497 0.499 0.501
		M-NMF	0.264 0.317 0.340 0.370 0.382 0.439 0.449 0.456 0.457 0.161 0.229 0.261 0.293 0.306 0.370 0.381 0.390 0.390
		Glda	0.395 0.451 0.493 0.514 0.535 0.593 0.610 0.616 0.618 0.352 0.411 0.454 0.474 0.494 0.548 0.562 0.568 0.567
	TNE	0.407 0.474 0.502 0.518 0.526 0.568 0.583 0.583 0.594 0.360 0.425 0.457 0.473 0.481 0.521 0.534 0.533 0.543 0.453 0.496 0.517 0.537 0.551 0.604 0.619 0.627 0.638 Louvain 0.0.449 0.488 0.508 0.527 0.546 0.597 0.612 0.619 0.624 Ghmm BigClam 0.402 0.443 0.464 0.483 0.502 0.549 0.562 0.566 0.568

Table 3

 3

			2%	4%	6%	8%	10% 30% 50% 70% 90%
		DeepWalk	0.617 0.688 0.715 0.732 0.747 0.799 0.815 0.825 0.832 0.569 0.664 0.698 0.717 0.735 0.788 0.806 0.815 0.821
		Node2Vec	0.659 0.720 0.743 0.759 0.770 0.816 0.831 0.839 0.845 0.612 0.694 0.724 0.743 0.755 0.804 0.820 0.828 0.832
	Baselines	LINE HOPE NetMF	0.416 0.498 0.546 0.581 0.609 0.701 0.728 0.741 0.747 0.306 0.425 0.492 0.543 0.578 0.691 0.720 0.733 0.738 0.284 0.301 0.301 0.302 0.302 0.302 0.302 0.304 0.306 0.067 0.066 0.067 0.066 0.066 0.067 0.067 0.068 0.074 0.636 0.716 0.748 0.767 0.773 0.821 0.834 0.841 0.844 0.591 0.694 0.731 0.751 0.760 0.811 0.824 0.832 0.835
		GEMSEC	0.470 0.530 0.568 0.587 0.601 0.674 0.714 0.735 0.744 0.406 0.477 0.527 0.546 0.562 0.646 0.689 0.713 0.722
		M-NMF	0.507 0.580 0.622 0.642 0.656 0.717 0.732 0.736 0.742 0.459 0.550 0.598 0.622 0.638 0.706 0.722 0.728 0.734
		Glda	0.612 0.672 0.710 0.731 0.751 0.817 0.840 0.850 0.856 0.575 0.650 0.694 0.715 0.738 0.807 0.829 0.837 0.841
	TNE	0.624 0.697 0.734 0.749 0.762 0.809 0.824 0.828 0.834 0.585 0.672 0.715 0.734 0.746 0.798 0.812 0.816 0.823 0.679 0.721 0.743 0.756 0.765 0.815 0.835 0.846 0.850 Louvain 0.645 0.699 0.724 0.738 0.749 0.802 0.822 0.832 0.836 Ghmm
		BigClam	0.631 0.693 0.720 0.740 0.754 0.809 0.828 0.837 0.851 0.589 0.671 0.702 0.725 0.739 0.798 0.818 0.828 0.838

.1: Node classification for varying training sizes on Citeseer. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively. Table

3

.2: Node classification for varying training sizes on Cora. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively. Table

3

.3: Node classification for varying training sizes on DBLP. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

Table 3

 3

		0.62
	Micro-F 1 Scores	0.59 0.60 0.61
		0.58
		30	50	70	90
			Training set ratios (%)

.4: Node classification for varying training sizes on PPI. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

  Table 3.5: Area Under Curve (AUC) scores for the link prediction task.

			Citeseer Cora DBLP PPI AstroPh HepTh Facebook Gnutella
		DeepWalk	0.828	0.779 0.944 0.860	0.961	0.896	0.984	0.695
	Baselines	Node2Vec LINE HOPE NetMF GEMSEC	0.827 0.739 0.744 0.780 0.749	0.781 0.944 0.861 0.696 0.930 0.878 0.712 0.873 0.880 0.745 0.910 0.785 0.734 0.920 0.771	0.961 0.969 0.931 0.872 0.816	0.896 0.844 0.836 0.858 0.823	0.983 0.967 0.975 0.974 0.733	0.694 0.839 0.748 0.654 0.639
		M-NMF	0.751	0.714 0.891 0.886	0.948	0.861	0.977	0.755
		Glda	0.809	0.775 0.958 0.772	0.977	0.903	0.993	0.728
	TNE	Ghmm Louvain	0.793 0.809	0.806 0.959 0.872 0.780 0.959 0.780	0.979 0.977	0.908 0.905	0.993 0.993	0.796 0.721
		BigClam	0.795	0.767 0.958 0.844	0.977	0.904	0.993	0.723

.717 0.769 0.771 0.864 0.882 0.877 0.964 0.964 0.969

  TNE-BigClam 0.710 0.749 0.757 0.856 0.873 0.872 0.912 0.933 0.940 Table 3.6: Classification on the SBM with Micro-F 1 scores for 40% training set ratio.

	1 50 DeepWalk 0.708 0.721 0.720 0.859 0.856 0.861 0.914 0.931 0.936 G 2 G 3 10 100 10 50 100 10 50 100 Walk length, L
	TNE-Glda 0.708 0.750 0.759 0.860 0.875 0.876 0.913 0.938 0.944
	TNE-Ghmm 0.707 0.752 0.762 0.861 0.877 0.875 0.916 0.938 0.944
	TNE-Louvain 0

  Table5.2: Node classification on Cora for varying training sizes. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

			2%	2% 4%	4% 6%	6% 8%	8% 10% 30% 50% 70% 90% 10% 30% 50% 70% 90%
		0.617 0.688 0.715 0.732 0.747 0.799 0.815 0.825 0.832 0.569 0.664 0.698 0.717 0.735 0.788 0.806 0.815 0.821 0.110 0.131 0.143 0.151 0.156 0.188 0.206 0.218 0.226 DeepWalk DeepWalk 0.076 0.099 0.113 0.123 0.129 0.164 0.181 0.190 0.192
		0.659 0.720 0.743 0.759 0.770 0.816 0.831 0.839 0.845 0.612 0.694 0.724 0.743 0.755 0.804 0.820 0.828 0.832 0.115 0.136 0.148 0.157 0.164 0.196 0.211 0.221 0.226 Node2Vec Node2Vec 0.078 0.101 0.116 0.125 0.132 0.167 0.180 0.188 0.190
	Baselines	Baselines LINE HOPE NetMF	0.416 0.498 0.546 0.581 0.609 0.701 0.728 0.741 0.747 0.306 0.425 0.492 0.543 0.578 0.691 0.720 0.733 0.738 0.284 0.301 0.301 0.302 0.302 0.302 0.302 0.304 0.306 0.067 0.066 0.067 0.066 0.066 0.067 0.067 0.068 0.074 0.636 0.716 0.748 0.767 0.773 0.821 0.834 0.841 0.844 0.591 0.694 0.731 0.751 0.760 0.811 0.824 0.832 0.835 0.109 0.133 0.149 0.162 0.170 0.210 0.226 0.235 0.242 LINE HOPE NetMF 0.063 0.084 0.099 0.111 0.120 0.164 0.181 0.191 0.192 0.068 0.069 0.069 0.070 0.069 0.071 0.077 0.086 0.093 0.019 0.019 0.019 0.019 0.018 0.020 0.025 0.030 0.033 0.085 0.100 0.116 0.126 0.131 0.176 0.193 0.203 0.211 0.045 0.064 0.080 0.090 0.095 0.137 0.152 0.161 0.160
		0.470 0.530 0.568 0.587 0.601 0.674 0.714 0.735 0.744 0.406 0.477 0.527 0.546 0.562 0.646 0.689 0.713 0.722 0.078 0.082 0.085 0.087 0.089 0.112 0.131 0.143 0.151 GEMSEC GEMSEC 0.059 0.063 0.067 0.070 0.073 0.098 0.113 0.122 0.125
		M-NMF	0.507 0.580 0.622 0.642 0.656 0.717 0.732 0.736 0.742 0.459 0.550 0.598 0.622 0.638 0.706 0.722 0.728 0.734 0.097 0.112 0.119 0.123 0.128 0.143 0.153 0.162 0.168 M-NMF 0.071 0.089 0.097 0.103 0.108 0.125 0.135 0.141 0.141
	KernelNE	KernelNE Gauss Sch	0.696 0.739 0.759 0.772 0.780 0.820 0.837 0.846 0.851 Gauss 0.664 0.721 0.743 0.758 0.767 0.809 0.826 0.836 0.840 0.695 0.736 0.750 0.759 0.765 0.790 0.800 0.806 0.812 Sch 0.631 0.697 0.721 0.734 0.745 0.780 0.790 0.795 0.799 0.102 0.121 0.134 0.142 0.148 0.180 0.192 0.200 0.203 0.051 0.067 0.078 0.086 0.092 0.125 0.138 0.146 0.147 0.126 0.154 0.172 0.185 0.195 0.232 0.244 0.250 0.256 0.069 0.091 0.107 0.119 0.128 0.171 0.187 0.196 0.198
	MKernelNE	MKernelNE Gauss Sch	0.701 0.748 0.764 0.775 0.781 0.812 0.823 0.828 0.833 0.656 0.723 0.746 0.761 0.769 0.801 0.813 0.818 0.820 0.699 0.742 0.757 0.767 0.772 0.797 0.806 0.812 0.818 0.637 0.708 0.733 0.749 0.756 0.787 0.796 0.802 0.804 0.128 0.156 0.174 0.186 0.195 0.231 0.242 0.249 0.254 Gauss Sch 0.071 0.094 0.109 0.122 0.131 0.172 0.187 0.195 0.197 0.128 0.156 0.173 0.186 0.194 0.230 0.241 0.247 0.251 0.071 0.094 0.110 0.122 0.130 0.169 0.184 0.192 0.193
				2%	4%	6%	8%	10% 30% 50% 70% 90%
		DeepWalk	0.550 0.588 0.603 0.611 0.616 0.630 0.633 0.635 0.636 0.496 0.527 0.540 0.547 0.551 0.563 0.565 0.566 0.567
		Node2Vec	0.575 0.599 0.612 0.618 0.623 0.636 0.639 0.641 0.641 0.517 0.541 0.551 0.557 0.561 0.571 0.574 0.575 0.574
		Baselines	LINE HOPE NetMF	0.553 0.576 0.585 0.590 0.594 0.606 0.610 0.611 0.611 0.469 0.498 0.510 0.517 0.522 0.536 0.540 0.541 0.541 0.379 0.379 0.379 0.379 0.379 0.380 0.383 0.387 0.391 0.137 0.137 0.137 0.137 0.138 0.140 0.146 0.152 0.160 0.577 0.589 0.596 0.601 0.605 0.617 0.620 0.623 0.623 0.490 0.506 0.513 0.518 0.522 0.530 0.531 0.533 0.533
		GEMSEC	0.538 0.566 0.583 0.591 0.597 0.611 0.614 0.615 0.615 0.477 0.501 0.513 0.519 0.523 0.534 0.535 0.537 0.536
			M-NMF	0.501 0.527 0.540 0.545 0.551 0.568 0.574 0.577 0.579 0.345 0.383 0.400 0.410 0.418 0.443 0.450 0.454 0.455
		KernelNE	Gauss Sch	0.575 0.595 0.606 0.613 0.617 0.630 0.633 0.635 0.636 0.517 0.536 0.545 0.551 0.554 0.564 0.566 0.567 0.569 0.609 0.617 0.621 0.624 0.627 0.635 0.637 0.638 0.640 0.531 0.546 0.552 0.556 0.559 0.568 0.570 0.571 0.572
		MKernelNE	0.614 0.624 0.630 0.633 0.636 0.646 0.648 0.650 0.650 Gauss 0.547 0.560 0.566 0.570 0.573 0.582 0.583 0.584 0.584 0.615 0.621 0.625 0.628 0.631 0.639 0.641 0.643 0.643 Sch 0.538 0.551 0.557 0.561 0.564 0.572 0.574 0.576 0.576

Table

5

.3: Node classification on DBLP for varying training sizes. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively. Table

5

.4: Node classification on PPI for varying training sizes. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

Table 5 .

 5 5: Area Under Curve (AUC) scores for link prediction.

	h

Table 5 . 9 :

 59 Table 5.7: Comparison of methods for node classification with 50% training ratio. Comparison of learning-based models in the link prediction task.

				TNE			EFGE		KernelNE MKernelNE
	B a s e li n e	G L d a	G H m m	L o u v a in	B ig C l a m	B e r n	P o is	N o r m	G a u s s	S c h	G a u s s	S c h
	Citeseer 0.543 0.535 0.526 0.551 0.546 0.565 0.571 0.564 0.555 0.561 0.566 0.570 Cora 0.773 0.751 0.762 0.765 0.754 0.787 0.784 0.786 0.780 0.765 0.781 0.772 DBLP 0.623 0.617 0.619 0.625 0.625 0.639 0.640 0.640 0.617 0.627 0.636 0.631 PPI 0.164 0.173 0.172 0.178 0.180 0.179 0.184 0.185 0.148 0.195 0.195 0.194
	Table 5.6: Comparison of methods for node classification with 10% training ratio.
				TNE			EFGE		KernelNE MKernelNE
	B a s e li n e	G L d a	G H m m	L o u v a in	B ig C l a m	B e r n	P o is	N o r m	G a u s s	S c h	G a u s s	S c h
	Citeseer 0.595 0.610 0.583 0.619 0.612 0.621 0.621 0.617 0.611 0.602 0.613 0.609 Cora 0.834 0.840 0.824 0.835 0.828 0.835 0.822 0.829 0.837 0.800 0.823 0.806 DBLP 0.639 0.634 0.635 0.642 0.641 0.655 0.655 0.656 0.633 0.637 0.648 0.641 PPI 0.226 0.233 0.227 0.226 0.229 0.227 0.231 0.234 0.192 0.244 0.242 0.241

  Table 6.1: Node classification for varying training sizes on Blogcatalog. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

		2%	4%	6%	8%	10% 30% 50% 70% 90%
	HOPE	0.239 0.273 0.289 0.300 0.303 0.314 0.314 0.319 0.328 0.085 0.100 0.107 0.113 0.117 0.116 0.117 0.120 0.125
	Node2Vec	0.285 0.322 0.332 0.335 0.342 0.348 0.354 0.355 0.350 0.109 0.136 0.146 0.149 0.157 0.158 0.170 0.173 0.170
	0.326 0.351 0.366 0.376 0.380 0.392 0.399 0.402 0.412 NetSMF 0.152 0.174 0.188 0.201 0.203 0.216 0.226 0.226 0.226
	LouvainNE	0.041 0.032 0.030 0.034 0.046 0.107 0.155 0.161 0.172 0.022 0.020 0.020 0.019 0.023 0.031 0.039 0.040 0.041
	RandNE	0.258 0.289 0.310 0.312 0.322 0.340 0.339 0.340 0.349 0.097 0.117 0.137 0.138 0.148 0.166 0.164 0.171 0.177
	NodeSketch	0.220 0.253 0.276 0.295 0.304 0.359 0.380 0.387 0.400 0.074 0.101 0.115 0.130 0.144 0.211 0.237 0.248 0.259
	NodeSig	0.266 0.319 0.338 0.354 0.361 0.398 0.410 0.419 0.430 0.108 0.144 0.165 0.182 0.196 0.249 0.270 0.281 0.287

Table 6 . 3 :

 63 Table6.2: Node classification for varying training sizes on Cora. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively. Node classification for varying training sizes on DBLP. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

		2%	4%	6%	8%	10% 30% 50% 70% 90%
	HOPE	0.474 0.560 0.632 0.654 0.687 0.763 0.780 0.787 0.803 0.395 0.494 0.611 0.620 0.672 0.757 0.772 0.780 0.798
	Node2Vec	0.641 0.707 0.745 0.754 0.757 0.798 0.805 0.813 0.833 0.581 0.663 0.723 0.736 0.742 0.786 0.791 0.798 0.821
	0.670 0.732 0.753 0.773 0.778 0.813 0.826 0.839 0.830 NetSMF 0.636 0.701 0.743 0.763 0.769 0.806 0.817 0.832 0.817
	LouvainNE	0.577 0.656 0.675 0.685 0.691 0.710 0.717 0.724 0.745 0.497 0.615 0.632 0.642 0.660 0.673 0.683 0.690 0.705
	RandNE	0.421 0.494 0.529 0.576 0.581 0.664 0.684 0.693 0.702 0.312 0.443 0.486 0.552 0.558 0.659 0.683 0.690 0.694
	NodeSketch	0.474 0.604 0.654 0.696 0.710 0.807 0.842 0.860 0.882 0.340 0.549 0.621 0.670 0.690 0.795 0.832 0.852 0.873
	NodeSig	0.514 0.659 0.699 0.727 0.746 0.823 0.850 0.869 0.886 0.433 0.622 0.679 0.712 0.732 0.813 0.841 0.861 0.878
		2%	4%	6%	8%	10% 30% 50% 70% 90%
	HOPE	0.568 0.597 0.610 0.619 0.621 0.629 0.634 0.632 0.633 0.464 0.501 0.514 0.524 0.524 0.533 0.540 0.538 0.539
	Node2Vec	0.606 0.615 0.612 0.615 0.617 0.629 0.629 0.626 0.632 0.503 0.522 0.491 0.493 0.495 0.535 0.528 0.524 0.532
	NetSMF	0.597 0.618 0.629 0.628 0.626 0.644 0.648 0.647 0.650 0.511 0.536 0.548 0.543 0.521 0.565 0.578 0.578 0.580
	LouvainNE	0.490 0.511 0.502 0.508 0.497 0.504 0.510 0.511 0.515 0.348 0.393 0.365 0.376 0.343 0.359 0.374 0.376 0.395
	RandNE	0.399 0.415 0.412 0.421 0.425 0.438 0.435 0.436 0.438 0.201 0.232 0.224 0.242 0.241 0.257 0.254 0.255 0.253
	NodeSketch	0.516 0.584 0.615 0.645 0.666 0.791 0.848 0.881 0.902 0.393 0.501 0.544 0.584 0.614 0.767 0.831 0.868 0.890
	0.613 0.648 0.672 0.692 0.705 0.797 0.844 0.873 0.896 NodeSig 0.523 0.581 0.616 0.641 0.661 0.772 0.825 0.858 0.882

051 0.073 0.095 0.111 0.118 0.167 0.183 0.191 0.194Table 6 . 4 :

 64 Node classification for varying training sizes on PPI. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

		2%	4%	6%	8%	10% 30% 50% 70% 90%
	HOPE	0.346 0.353 0.348 0.344 0.341 0.341 0.344 0.344 0.345 0.213 0.222 0.208 0.202 0.197 0.199 0.205 0.202 0.203
	Node2Vec	--	--	--	--	--	--	--	--	--
	NetSMF	0.371 0.384 0.387 0.381 0.386 0.373 0.373 0.360 0.364 0.254 0.271 0.275 0.266 0.265 0.248 0.249 0.239 0.236
	LouvainNE	0.179 0.247 0.236 0.249 0.249 0.252 0.249 0.249 0.254 0.067 0.066 0.063 0.062 0.063 0.062 0.063 0.065 0.071
	RandNE	0.320 0.334 0.335 0.337 0.335 0.342 0.343 0.339 0.343 0.196 0.207 0.212 0.212 0.204 0.218 0.222 0.218 0.221
	NodeSketch	0.399 0.416 0.427 0.433 0.440 0.459 0.467 0.471 0.472 0.294 0.327 0.346 0.355 0.367 0.399 0.412 0.421 0.422
	0.429 0.445 0.450 0.454 0.456 0.464 0.466 0.469 0.467 NodeSig 0.332 0.362 0.372 0.380 0.388 0.402 0.408 0.413 0.411

Table 6 . 5 :

 65 Node classification for varying training sizes on Youtube. For each method, the rows indicates the Micro-F 1 and Macro-F 1 scores, respectively.

  Table 6.6: Area Under Curve (AUC) scores for link prediction.

		Blogcatalog Cora DBLP PPI	Youtube
	HOPE	0.517	0.662 0.769 0.524	0.514
	Node2Vec	0.595	0.747 0.844 0.615	0.531
	NetSMF	0.570	0.717 0.832 0.549	0.541
	LouvainNE	0.501	0.698 0.785 0.575	0.529
	RandNE	0.622	0.590 0.697 0.504	0.511
	NodeSketch	0.703	0.710 0.714 0.512	0.510
	NodeSig	0.822	0.740 0.860 0.655	0.536

  Table 6.7. The Random network indicates the G n,p Erd ös-Renyi random graph model [ER60], using

		B lo g ca ta lo g	C o ra	D B L P	P P I	Y o u tu b e	R a n d o m	S p e e d u p
	HOPE	89	26	185	32	9183 1117	1.8x
	Node2Vec	1187	15	164	62	-	749	5.6x
	NetSMF	2241	15	183	13	5399 454	1.4x
	LouvainNE	0.29	0.06	0.21 0.13 5.70	1.2 0.001x
	RandNE	3.18	1.50	6.22 2.02 161.8	23	0.03x
	NodeSketch 106.84 13.46 21.93 9.26 2300 190	0.45x
	NodeSig	120	4.38	41	14	5508 209	1.0x

  Table 6.7: Running time (in seconds) and average speedup.

rules instead of explicitly realizing the data matrix. Finally, a bit-vector is generated, corresponding to the signature of the projected data. As we will show shortly, NodeSig shows comparable or even better accuracy results compared to NodeSketch, while at the same time, it can easily be adapted to more demanding settings like dynamic or streaming environments.

proposed approach

In this section, we introduce the proposed approach, referred to as NodeSig, which aims at representing the nodes of the network as fixed-length binary codes. The model mainly relies on sign stable random projections of a properly designed matrix that captures higher order proximity among nodes. Initially, we describe how we construct this target matrix by using random As it is shown in Figure 6.2, the last step of NodeSig for obtaining binary node representations is to utilize the signs of the projected data. In other words, the embedding vector E[v] for each node v ∈ V is computed as follows:

Note that, the projection of the exact realization of M(α) can be computationally intensive, especially for large walks. Instead, it can be computed by propagating the weights W (u,j) for each dimension j (1 ≤ j ≤ d), using the following recursive update rule:

where N (v) refers to the set of neighbors of node v ∈ V and R

(v,j) is equal to the projected data, M (v,:) (α) • W (:,j) for the walk length l, and R (0) (v,j) is initialized to zero. By Lemma 6.2, it can be seen that the projection of M(α) can be computed with the recursive update rules defined in Equation 6.3. Lemma 6.2. Let P be N × N a right stochastic matrix and M (L) (α) be the matrix defined by αP + • • • + α (l) P (l) + • • • + α (L) P (L) . For a given W ∈ R N×D , we have

where each R (l) (i,j) is recursively defined by αP (i,:) W (:,j) + R (l-1) (:,j)

for all l ∈ {1, . . . , L}, i ∈ {1, . . . , N} and R (0) is set to 0.

Proof. For l = 1, we have that R

(i,j) = αP (i,:) W (:,j) + R

(:,j) = αP (i,:) W (:,j) + 0 = αP (i,:) W (:,j) , for all j ∈ {1, . . . , d}, and i ∈ {1, . . . , N} so the claim in Equation (6.4) holds.

Let us assume that it is true for n = l ≥ 1. Then, R

(i,j) = αP (i,:) W (:,j) + R

Thus, the claim holds for n+1 = l. By the principle of induction, it satisfies for all l ∈ {1, . . . , L}.

Algorithm 6.1 provides the pseudocode of NodeSig. Firstly, we generate the projection matrix by sampling the weights from the Cauchy distribution with unit scale. The samples are further divided by ∑ l=1 α (l) , because the row sums of M(α) must be equal to 1. Then, we compute the terms R (l) (v,j) by propagating the weights in Line 9 at each walk iteration l < L. Note that, the term R in the pseudocode is a vector of length d, thus we obtain the final representation of each node using the signs of R (L) (v,j) . (v,j) values in the update rule of Equation 6.3. Note that, the performance of the algorithm can be boosted by using parallel processing for each dimension of embedding vectors or

Time and Space Complexity