Science, Irving K. Barber Faculty of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Liu, Xiaoou
Master of Science - MSc
University of British Columbia
This thesis studies the effectiveness of Graph Neural Networks (GNNs) for node classification. We conduct systematic experiments on several representative deep-learning models for graph data, using training data generated from the Stochastic Block Model (SBM) and the theoretical results on the fundamental limits of this model as guidance in the design of our experiments. While GNNs are widely believed to be powerful learning models for graph data, our empirical findings suggest that they do not necessarily outperform other machine-learning-based methods and traditional algorithms for node classification. In particular, we observe that GNN-based methods fail to exploit the information from labeled nodes in semi-supervised learning settings. We propose an effective data augmentation method to enhance GNN-based methods by making better use of labeled information in the training data. Our experiments using synthetic data from SBMs and real-world datasets demonstrate that our method can significantly enhance the capabilities of GNN models and notably improve their performance for node classification. Additionally, in the context of unsupervised learning, we discuss the possibility of incorporating other types of side information into GNNs that may exist in multiplex network data.
The Effectiveness of GNNs forNode Classification: TheSignificance of Side InformationbyXiaoou LiuB.Eng., Beijing Jiaotong University, 2021A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)June 2024© Xiaoou Liu 2024The following individuals certify that they have read, and recommend tothe College of Graduate Studies for acceptance, the thesis entitled:The Effectiveness of GNNs for Node Classification: The Significance ofSide Informationsubmitted by Xiaoou Liu in partial fulfillment of the requirements for thedegree of Master of Science.Dr. Yong Gao, Irving K Barber Faculty of ScienceSupervisorDr. Shan Du, Irving K Barber Faculty of ScienceDefense Committee MemberDr. Ifeoma Adaji, Irving K Barber Faculty of ScienceDefense Committee MemberDr. Suliman Gargoum, School of EngineeringUniversity ExamineriiAbstractThis thesis studies the effectiveness of Graph Neural Networks (GNNs)for node classification. We conduct systematic experiments on several repre-sentative deep-learning models for graph data, using training data generatedfrom the Stochastic Block Model (SBM) and the theoretical results on thefundamental limits of this model as guidance in the design of our experiments.While GNNs are widely believed to be powerful learning models for graphdata, our empirical findings suggest that they do not necessarily outperformother machine-learning-based methods and traditional algorithms for nodeclassification. In particular, we observe that GNN-based methods fail to ex-ploit the information from labeled nodes in semi-supervised learning settings.We propose an effective data augmentation method to enhance GNN-basedmethods by making better use of labeled information in the training data.Our experiments using synthetic data from SBMs and real-world datasetsdemonstrate that our method can significantly enhance the capabilities ofGNN models and notably improve their performance for node classification.Additionally, in the context of unsupervised learning, we discuss the possi-bility of incorporating other types of side information into GNNs that mayexist in multiplex network data.iiiLay SummaryThe graph serves as a powerful data structure for modeling real-world re-lational data, ranging from social media interactions to biomedical networks.This research explores the performance of various deep-learning models forclassifying nodes within graphs. Our experimental findings show that populardeep-learning models do not always work better than other methods for thistask. We observe that GNN-based methods struggle to use the labeled dataeffectively, particularly in scenarios where there is not much useful informa-tion in the network. We propose an approach to enhance the deep-learningmethods by augmenting the network data using additional information.ivPrefaceThis thesis was entirely written by myself. I performed all experimentalwork and detailed analysis of research data independently.I am grateful to my supervisor, Dr. Yong Gao, for his help in refiningthe writing and for our idea discussions during meetings. I also appreciateCongsong Zhang for his valuable discussions.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 1Chapter 2: Preliminaries . . . . . . . . . . . . . . . . . . . . . . 52.1 Graphs and Networks . . . . . . . . . . . . . . . . . . . . . . . 52.2 Graph Machine Learning . . . . . . . . . . . . . . . . . . . . . 62.2.1 Clustering and Community Detection . . . . . . . . . . 72.2.2 Node Classification . . . . . . . . . . . . . . . . . . . . 102.3 Graph Embedding . . . . . . . . . . . . . . . . . . . . . . . . 122.3.1 Graph Embedding Input and Output . . . . . . . . . . 122.3.2 Graph Embedding Methods . . . . . . . . . . . . . . . 142.4 Graph Neural Network . . . . . . . . . . . . . . . . . . . . . . 15viTABLE OF CONTENTS2.5 The Stochastic Block Model . . . . . . . . . . . . . . . . . . . 162.5.1 The Definition of Stochastic Block Model . . . . . . . . 172.5.2 Fundamental Limits . . . . . . . . . . . . . . . . . . . 21Chapter 3: Graph Embedding Methods . . . . . . . . . . . . . . 243.1 DeepWalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Node2vec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3 LINE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4 Graph Convolution Networks . . . . . . . . . . . . . . . . . . 303.5 GraphSAGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.6 Graph Autoencoder . . . . . . . . . . . . . . . . . . . . . . . . 333.6.1 GAE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.6.2 VGAE . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Chapter 4: The Performance of Graph Embedding Methodson Node Classification: Experimental Findings . . 374.1 Experimental Design and Methodology . . . . . . . . . . . . . 374.1.1 Experiment Setup . . . . . . . . . . . . . . . . . . . . . 394.1.2 Embedding Methods Configurations . . . . . . . . . . . 394.2 Theoretical Baseline . . . . . . . . . . . . . . . . . . . . . . . 414.2.1 Baseline for k=2 . . . . . . . . . . . . . . . . . . . . . 414.2.2 Baseline for General k . . . . . . . . . . . . . . . . . . 454.3 Experiments in the Unsupervised Learning Settings . . . . . . 464.4 Experiments in the Semi-Supervised Learning Settings . . . . 49Chapter 5: Multilayer Stochastic Block Models and Side In-formation . . . . . . . . . . . . . . . . . . . . . . . . . 545.1 The Multilayer Stochastic Block Model . . . . . . . . . . . . . 545.2 M-SBM Data Augmentation for Semi-Supervised Learning . . 575.2.1 A Multilayer Data Augmentation Approach . . . . . . 585.2.2 Experiments on the Synthetic Data . . . . . . . . . . . 59viiTABLE OF CONTENTS5.2.3 Experiments on Real-World Datasets . . . . . . . . . . 625.3 M-SBM Data Augmentation for Unsupervised Learning . . . . 655.4 Summary of M-SBM Data Augmentation . . . . . . . . . . . . 67Chapter 6: Conclusion and Future Work . . . . . . . . . . . . . 68Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70viiiList of TablesTable 4.1 Common parameters in experiments. A note regarding*: This represents different settings in various experi-ments. . . . . . . . . . . . . . . . . . . . . . . . . . . . 40Table 4.2 Specific parameters in experiments. . . . . . . . . . . . 41Table 5.1 Comparison of results from different embedding meth-ods using original SBMs and two-layer M-SBMs as train-ing data. A note regarding */M-SBM: This designationpertains to results obtained by integrating the originalSBM with an additional layer graph, constructed byrandomly shuffling the edges between the known labelnodes in the original SBM. . . . . . . . . . . . . . . . . 60Table 5.2 The accuracy of different graph embedding methodsat different reveal ratios ρ. A note regarding */M-SBM: This designation pertains to results obtained byintegrating the original SBM with an additional layergraph, constructed by randomly shuffling the edges be-tween the known label nodes in the original SBM. . . . 62Table 5.3 Experiments in Real-World Datasets. A note regard-ing */M-SBM: This designation pertains to results ob-tained by integrating the original real-world networkwith an additional layer graph, constructed by ran-domly shuffling the edges between the known label nodesin the original real-world network. . . . . . . . . . . . . 64ixLIST OF TABLESTable 5.4 Experiment of VGAE in the Unsupervised LearningSettings. . . . . . . . . . . . . . . . . . . . . . . . . . . 66xList of FiguresFigure 2.1 Zachary’s karate club network. . . . . . . . . . . . . . 9Figure 2.2 Community detection using spectral clustering. . . . . 10Figure 2.3 Anomaly detection. . . . . . . . . . . . . . . . . . . . 11Figure 2.4 Design process of GNNs [62]. . . . . . . . . . . . . . . 16Figure 2.5 Graph generated using SBM(34, 2, 0.1, 0.01) to modelZachary’s karate club network. . . . . . . . . . . . . . 19Figure 3.1 Sequences generated by random walks. . . . . . . . . . 26Figure 3.2 Biased random walks in Node2vec [27]. . . . . . . . . . 27Figure 3.3 Sampling strategy in GraphSAGE. . . . . . . . . . . . 33Figure 3.4 The architecture of an autoencoder. . . . . . . . . . . 34Figure 3.5 The architecture of a GAE [37]. . . . . . . . . . . . . . 34Figure 3.6 The architecture of a VGAE [37]. . . . . . . . . . . . . 35Figure 4.1 The framework of experiments. . . . . . . . . . . . . . 38Figure 4.2 Unsupervised results when k=2. . . . . . . . . . . . . 47Figure 4.3 Unsupervised results when k=4. . . . . . . . . . . . . 48Figure 4.4 Semi-supervised results when k = 2. . . . . . . . . . . 50Figure 4.5 Semi-supervised results when k = 4. . . . . . . . . . . 51Figure 4.6 The number of epochs for early stopping in VGAE. . . 53Figure 4.7 The Frequency of Accuracy over Random Guess. . . . 53Figure 5.1 Two SNR = 1 Curves . . . . . . . . . . . . . . . . . . 58xiLIST OF FIGURESFigure 5.2 Percentage improvement in accuracy for different graphembedding methods. Percentage improvement is cal-culated by M−SBMAccuracy−OriginalAccuracyOriginalAccuracy× 100%. . . . 61Figure 5.3 Percentage improvement in accuracy at different re-veal ratios ρ. Percentage improvement is calculatedby M−SBMAccuracy−OriginalAccuracyOriginalAccuracy× 100%. . . . . . . . 63Figure 5.4 The diagram of the two-layer M-SBM. . . . . . . . . . 66xiiAcknowledgementsI would like to express my deepest gratitude to my supervisor, Dr. YongGao, for his unwavering support, invaluable guidance, and insightful feedbackthroughout my graduate studies. I am grateful to Dr. Shan Du and Dr.Ifeoma Adaji for carefully reviewing my thesis in preparation for the defense.I am also grateful to my colleague, Ph.D. Candidate Congsong Zhang,for his encouragement and intellectual contributions. Furthermore, I want tothank my family for their endless love, understanding, and encouragement.I am truly fortunate to have such incredible mentors, colleagues, andfamily members who have played pivotal roles in my academic and personalgrowth. Their unwavering support was instrumental in enabling me to com-plete my master’s degree.xiiiChapter 1IntroductionThe graph serves as a powerful data structure for modeling real-world re-lational data, ranging from social media interactions to biomedical networks.By analyzing the graph of user interactions on a social media platform, suchas comments, likes, and follows, it is possible to tailor recommendations fortargeted advertising that align with users’ preferences and behaviors [12].Similarly, analyzing the graph of molecular interactions enhances the pre-diction of drug-disease associations and improves protein function prediction[59].However, analyzing and extracting patterns from these graph structuresrequires significant computational resources [16]. In recent years, graph em-bedding methods have emerged as a popular approach for transforming graphdata into low-dimensional vector spaces while preserving the intrinsic graphstructure and relevant information [26]. Traditional graph embedding meth-ods typically rely on matrix factorization, but the emergence of deep learninghas led to the development of graph embedding methods based on techniquessuch as random walks and neural networks [11]. Machine learning algorithmscan be leveraged to analyze the low-dimensional representations produced bythese graph embedding methods to solve various downstream tasks, includ-ing clustering, node classification, and link prediction.Stochastic block models (SBMs) are generative models for graphs withplanted clusters [1]. These models are characterized by parameters that de-fine the size of graphs, the number of clusters, and the probabilities of con-nections within and between clusters. Community detection is the processof identifying groups of nodes in a graph that are more densely connected to1each other than to the rest of the graph. SBMs are widely employed in thetheoretical study of community detection and clustering due to their con-trollable community structure [13]. Graphs generated from SBMs are alsoutilized as benchmark data in recent research [20]. Extensive research hasfocused on community detection problems in SBMs, particularly in the recov-erability of hidden community structures [31]. Currently, it has been provedthat there exists a threshold in SBMs for a function of model parameters.This function represents the detection signal from the model for communitydetection problems [3]. As the parameters of the SBM vary across the thresh-old, a remarkable phenomenon known as a phase transition occurs, where therecoverability of the graph experiences a sudden change [18]. When the signalexceeds the threshold, the community detection problem becomes solvableto a certain degree. Conversely, when the signal in a SBM falls below thisthreshold, the community detection problem becomes unsolvable.There are two types of thresholds: the information-theoretic thresholdand the algorithmic threshold [1]. While the information-theoretic thresholdestablishes a theoretical limit on the recoverability of communities, the algo-rithmic threshold is concerned with the practical feasibility of their recoveryusing specific algorithms. Above the information-theoretic threshold, we pos-sess at least the minimum information in the detection signal required for thesuccessful recovery of communities in SBMs. Below this threshold, however,the community structure cannot be recovered, regardless of the choice of al-gorithm or its computational complexity. On the other hand, the algorithmicthreshold refers to the strength of signals necessary to effectively solve theproblems, i.e., in polynomial time in terms of the number of vertices.It can be seen that community detection and the phase transition phe-nomenon in SBMs have been extensively studied theoretically [1, 3, 32]. Al-though there is a lot of research on using GNN to solve node classificationproblems [28, 36, 37], there are only a few experiments analyzing the perfor-mance of graph neural networks using community detection on SBMs [34].2There is currently a lack of comprehensive and systematic experimental eval-uation and comparison of the effectiveness of various graph embedding meth-ods in solving community detection problems within SBMs. In this thesis,we conducted a comprehensive performance analysis, specifically focusing onparameters near the detection threshold. Furthermore, we implement bothunsupervised learning and semi-supervised learning methods. To the best ofour knowledge, our experiments are the first to experimentally validate thephase transition in the recoverability of community structure and to evaluatethe performance of various graph embedding methods on SBMs.The useful information in graphs not only exists in the graph structurebut also in the form of side information such as node labels, additional layersin multilayer graphs [48], and other non-graphic information [22]. With theaid of side information, it is possible to recover the community structure inSBMs even below the threshold for standard tasks. Mohammad et al. [22]showed that using non-graphical side information can improve the thresholdfor exact recovery in the unsupervised learning setting. Sheng et al. [50]demonstrated the disappearance of weak recovery thresholds in the semi-supervised setting. However, the extent to which the side information ofnode labels is effectively used in semi-supervised models has not been deeplystudied. We propose a data augmentation method and conduct experimentsto assess its effectiveness.The primary contributions in this thesis are as follows: Through empiricalexperiments, we substantiate that the weak recovery threshold is eliminatedin semi-supervised learning settings. We find that shallow graph embeddingmethods based on random walks use node labels more effectively as side in-formation than graph neural network models in semi-supervised learning. Wepropose a multilayer stochastic block model and conduct a theoretical anal-ysis of its fundamental limit. Additionally, we propose a multilayer dataaugmentation approach to enhance the effectiveness of graph embeddingmethods using side information in both semi-supervised and unsupervised3learning scenarios.The whole thesis is divided into six chapters. In Chapter 2, we providepreliminaries and a comprehensive literature review relevant to the thesis. InChapter 3, we introduce six graph embedding methods used in this thesis.In Chapter 4, we outline our experimental framework and present empiricalfindings from experiments using different embedding methods. Chapter 5introduces a multilayer stochastic block model and our data augmentationapproach, discussing the role of side information in both unsupervised learn-ing and semi-supervised learning scenarios. Finally, in Chapter 6, we presentthe conclusion and discuss future work.4Chapter 2Preliminaries2.1 Graphs and NetworksA network is a set of entities with relations between them [29]. Theentities are called vertices or nodes, and the relations are called edges orlinks. For example, in the network of the Internet, nodes represent comput-ers or routers and edges represent cable or wireless data connections [19].In a metabolic network, nodes represent metabolites and edges representmetabolic reactions [38]. The study of networks has a long history, datingback to the 1930s when sociologists and psychologists began investigating so-cial interactions among people [54]. Unlike other data structures, networksfocus on the interactions between nodes rather than the behavior of individ-ual nods.Graphs represent the abstract structure of networks. In this thesis, theterms ‘graph’ and ‘network’ are used interchangeably. Formally, a graph isdenoted as G(V,E), where V represents the set of nodes and E represents theset of edges. An edge between node u and node v is denoted by (u, v). In adirected graph, the edge (u, v) represents an ordered pair where node u is thestart node and v is the end node. In an undirected graph, the start node andthe end node can be interchanged, meaning that edges are unordered pairsof nodes. We note that in the implementation of deep learning frameworks,an undirected graph is transformed into a directed graph by replacing eachedge in the undirected graph with two directed edges, one in each direction.Throughout this thesis, when the context is clear, we will also abuse thenotation to represent an undirected edge by (u, v). In this thesis, we are52.2. GRAPH MACHINE LEARNINGmainly concerned with simple graphs, where multiple edges between the samepair of nodes (multi-edges) or edges originating from and pointing to the samenode (self-edges) are not present.The edges information can be represented as an adjacency matrix A ∈{0, 1}|V |×|V |, where the element Auv = 1 if there exists an edge connectingnode u and node v, and it is 0 otherwise. In a weighted graph, where edgesare associated with weights, the elements in matrix A ∈ R|V |×|V | representthe edge weights corresponding to the edges.Heterogeneous graphs and multilayer graphsIn certain scenarios, networks may consist of multiple types of nodesand/or edges [29]. These graphs are referred to as heterogeneous graphs andare prevalent in real-world applications where multiple relationships existbetween different entities [53]. For instance, in biomedical networks, thedrug-disease treatment associations (DDA) graph includes two types of edges,“may treat” and “may be treated by”, along with two types of nodes suchas drugs and diseases [59].More generally, we consider a multilayer graph in which different layersare defined on the same set of nodes [43]. The edges within this graphmay connect nodes within a single layer or traverse across different layers.A tangible example of such a graph is found in social media networks. Wegather information on the same group of users from multiple social platforms,such as Facebook, Twitter, and Instagram. Each social platform constitutesa distinct layer, comprising information related to user interactions such ascomments and likes. Additionally, connections between nodes can also beestablished across different layers.2.2 Graph Machine LearningMachine learning is a method that constructs models by learning fromdata, identifying patterns, and making decisions with minimal human in-62.2. GRAPH MACHINE LEARNINGtervention. Graph machine learning, abbreviated as GML, pertains to theapplication of machine learning principles to graph data [55]. A primarygoal of GML is to compress vast, sparsely connected graph data structuresto enable effective predictive analytics and inference.GML tasks can be classified into two primary categories: semi-supervisedlearning and unsupervised learning. In this thesis, we focus on unsupervisedlearning tasks, specifically community detection, and semi-supervised learn-ing tasks, specifically node classification.2.2.1 Clustering and Community DetectionClustering is a traditional technology for unsupervised learning tasks inmachine learning. It aims to partition unlabeled datasets into usually non-overlapping subsets, known as clusters [57]. Samples within the same clustershare higher similarity, measured using metrics such as Jaccard coefficient[14], Fowlkes and Mallows index [24], Dunn index [9], Euclidean distance,Manhattan distance [10], and so on. Traditional clustering algorithms includeK-means [30], DBSCAN [35], spectral clustering [45], PCA [58] and GMM[61]. There are various applications of clustering, such as in medical researchfor grouping large sets of patient data to discover disease characteristics, orin text analysis to effectively organize and summarize textual information.In this thesis, we employ an optimized version of the K-means clusteringalgorithm, known as K-means++ [7], for our experiments. The details ofK-means++ are discussed in the remainder of this section.As shown in Algorithm 1, the K-means++ algorithm has two main com-ponents. The first part involves the selection of cluster centroids. Assumingthe data D is divided into k clusters, we start by randomly selecting onesample from the input data points as the first cluster centroid. For eachsample d in the dataset, we calculate its distance E(d) to the nearest alreadychosen cluster centroid. The principle for selecting a new sample as a clustercentroid is that a sample with larger E(d) values has a higher probability72.2. GRAPH MACHINE LEARNINGAlgorithm 1: KMeans++ Algorithm [33]Data: Number of cluster k, set of n data items D = d1, d2, . . . , dnResult: A set of k clusters1 Arbitrarily choose the first cluster centroid c1 from D;2 repeat3 For each di , computer the distance to the nearest clustercentroid cj using E(di) =√(cj − di)2;4 Choose the next cluster centroid cj = di with probabilityE(di)2∑ni E(di)2 ;5 until all the cluster centroids have been chosen;6 repeat7 Assign each d to the cluster with the closest centroid c;8 Update each cluster centroids c by taking the average of all theassigned d in each cluster ;9 until no longer changes in the cluster centroids ;of being chosen as a cluster centroid. Then, repeat these two steps until wehave selected k cluster centroids. The second part is the standard K-meansalgorithm with these k initial cluster centroids. For any given sample d, wecompute its distance to all cluster centroids and assign this sample to thecluster associated with the nearest cluster centroid. We update the centroidof each cluster using the average method and repeat this process until allvalues no longer change.One prominent feature of networks is their inherent community structure:a group of nodes with stronger internal connections and sparse external con-nections. Community detection is a specialized graph-based clustering al-gorithm designed to address complex network problems [23]. Communitydetection and clustering are similar in that they both aim to identify sets ofsimilar data within a dataset. However, clustering algorithms have broaderapplications in machine learning, dealing with a wider range of data types,while community detection is custom-tailored for network analysis, relying82.2. GRAPH MACHINE LEARNINGFigure 2.1: Zachary’s karate club network.solely on edges between nodes. Notable successful community detection al-gorithms include Louvain community detection [17], Leiden community de-tection [52], Walktrap community detection [47], spectral clustering [45] andso on. It is worth noting that in this thesis, we exclusively consider nodesbelonging to a single community, meaning there are no overlapping nodesacross different communities.Here is an application example of community detection using the well-known dataset, Zachary’s karate club network [60]. Figure 2.1 illustrates thesocial relationships among members of a karate club. There are 34 membersrepresented as nodes, and the social connections outside the club are repre-sented as edges. After collecting the data, a conflict arose between managerA and coach B, prompting the members to take sides. Half of the memberschose to follow B and establish a new club, while the remaining half soughta new coach or left the club. Figure 2.2 shows the results of partitioning thenetwork into two communities using spectral clustering. All but one memberhave been correctly classified.Clustering algorithms have evolved and matured since 1963. However,traditional clustering algorithms are not directly suitable for application to92.2. GRAPH MACHINE LEARNINGFigure 2.2: Community detection using spectral clustering.graph data. There are two primary reasons for this [11]. First, clustering al-gorithms typically operate on independently unrelated sequential data, whilenetworks are complex structures with arbitrary sizes and intricate topologicalstructures. Second, complex networks are generally sparse, while clusteringis commonly applied to dense datasets. Therefore, in Section 2.3, we willintroduce how graph embedding techniques can be used to adapt traditionalclustering algorithms for community detection in graph data.2.2.2 Node ClassificationClassification is a common supervised machine learning task in which amodel tries to predict the correct label for a given input dataset. In theclassification process, the model is extensively trained on a labeled trainingdataset, and subsequently employed to make predictions on a separate testdataset, which typically consists of new, previously unseen data.Node classification pertains to the process of assigning labels to a subsetof nodes within a graph. The ultimate goal of this process is to predictthe labels for the remaining, unclassified nodes within the same graph. Toillustrate, consider the following example involving anomaly detection. In a102.2. GRAPH MACHINE LEARNINGFigure 2.3: Anomaly detection.social network, users represented by red nodes are known to be fraudulent,while those denoted by green nodes are considered normal users. The task isto predict whether the remaining gray nodes in the network are fraudulentusers or not.Node classification, in contrast to standard classification tasks, is com-monly regarded as a semi-supervised machine learning task [39]. This cat-egorization arises from the necessity, during model training, to incorporatenot only partial node labeling but also inter-node connections. This allowsfor the iterative refinement of labels for previously unclassified nodes untilall nodes within the entire network achieve a state of convergence. Duringthe training phase, the entire graph structure and its encompassing edgesare considered, making it challenging to explicitly demarcate training andtesting sets. This framework is referred to as semi-supervised learning.Node classification solutions can be realized through various methodolo-gies, including the analysis of relationships embedded within the graph, thederivation of node embedding vectors, and the application of graph neuralnetworks [56]. Detailed discussions on node embedding vectors will be pre-sented in Section 2.3, while graph neural networks will be explored in Section2.4.112.3. GRAPH EMBEDDING2.3 Graph EmbeddingDealing with graph data in the context of machine learning presentsunique challenges and difficulties. Graphs differ from Euclidean data typeslike images, audio, and text. One of the characteristics of graphs is invariance[41], meaning that even if the positions or arrangements of nodes change, aslong as the connections between nodes remain unchanged, the essence of thegraph remains the same. Moreover, nodes within a graph can be labeled inany order. For instance, if we initially label nodes as 1, 2, 3, 4, 5, and subse-quently relabel them as 2, 5, 4, 1, 3, the adjacency matrix will change, butthe underlying graph structure will remain the same. Furthermore, tradi-tional machine learning typically assumes that samples are independent andidentically distributed (i.i.d.), a condition not met by graph data. Thus, thechallenge lies in effectively utilizing such non-Euclidean graph data as inputfor a variety of machine learning downstream tasks.Graph embedding provides an effective and efficient solution to reduce thedimensionality of graph data and address related tasks. Graph embeddingis a process that maps graph data to low-dimensional vectors, transform-ing nodes, edges, and their features into a vector space while preserving asmuch of the graph structure and information as possible [26]. The ultimategoal of different graph embedding methods is to output optimal vectors thatencapsulate information about the similarity of nodes. In other words, simi-lar nodes should have similar embedding vectors. Graph embedding can bethought of as a preprocessing step, converting high-dimensional graphs intoa computationally manageable format. Graph embedding makes it feasibleto apply machine learning techniques to graph-based problems effectively.2.3.1 Graph Embedding Input and OutputGraph embedding can take various forms of input, including homogeneousgraphs, heterogeneous graphs, and graphs with side information [11]:122.3. GRAPH EMBEDDING• Homogeneous Graphs: These are graphs in which both nodes and edgesare of a single type. Common examples include undirected, unweightedgraphs, where only the structural information of the graph is consid-ered. However, edge weights and directions can provide additional in-formation about the graph.• Heterogeneous Graphs: Heterogeneous graphs, as discussed in Section2.1, differ from homogeneous graphs in that they possess more complexhigh-order structures and different types of nodes and edge attributeshold distinct meanings. Consequently, different solutions may be re-quired when applying heterogeneous graphs to various practical appli-cations.• Graphs with Side Information: These graphs come with additionalinformation, such as labels, attributes, or node features. Integratingthe topological structure and unstructured auxiliary information intoembedding vectors is currently a hot research area. The challenge liesin effectively merging these two sources of data to create comprehensiveembedding.The output of graph embedding is driven by the specific tasks it needs toserve and can be categorized based on the granularity of these downstreamtasks [11]:• Whole-Graph Embedding: The goal of whole-graph embedding is torepresent the entire graph as a vector, facilitating the prediction ofglobal graph properties. These types of tasks, often referred to asgraph-level tasks, are typically suitable for small graphs, such as thoserepresenting proteins or molecules. The aim is to capture essentialgraph-level characteristics to make predictions or inferences about theentire graph.• Node Embedding: Node embedding focuses on representing each indi-vidual node as a vector in a low-dimensional space. Nodes belonging132.3. GRAPH EMBEDDINGto the same class or community are represented with similar vectors,preserving structural and contextual information. Common node-leveltasks include node classification and node clustering. For instance, in asocial network, based on the relationships between different users, onecan assign community labels or perform other node-centric tasks.• Edge Embedding: Edge embedding aims to represent edges as low-dimensional vectors. Edge-level tasks often involve edge prediction.For example, in knowledge graphs, we can predict missing relation-ships between entities, determining whether there exists a connectionbetween two given entities. Edge embeddings can analyze relationshipsand infer missing connections.2.3.2 Graph Embedding MethodsCurrently, graph embedding methods can be broadly categorized intothree main classes based on the techniques they employ:• Matrix Factorization-Based Methods: These methods rely on matrixfactorization techniques to capture the inherent structure within graphs.They often factorize the graph’s adjacency matrix into lower-dimensionalrepresentations. Examples include techniques like Singular Value De-composition (SVD), graph factorization (GF) [5], and variants of thesemethods tailored for graph embedding.• Random Walk-Based Methods: Random walk-based techniques use theidea of exploring graphs through random walks or traversals. By simu-lating random walks, these methods capture local neighborhood infor-mation and structural features of nodes. Methods such as DeepWalk[46] and Node2vec [27] are prominent examples of this category. Theygenerate embeddings by treating each node as a starting point for ran-dom walks and using the sequences of visited nodes to learn represen-tations.142.4. GRAPH NEURAL NETWORK• Deep Learning-Based Methods: Deep learning-based methods havegained significant attention in recent years due to their ability to cap-ture complex, non-linear relationships within graphs. These methodstypically utilize neural network architectures like Graph ConvolutionalNetworks (GCNs) [36] and GraphSAGE [28] to perform graph embed-ding. Deep learning-based techniques are known for their capacity toincorporate both structural and node-specific information in an end-to-end manner, making them suitable for a wide range of graph-relatedtasks.2.4 Graph Neural NetworkWith the recent successes of neural networks, various domains such asimage classification and natural language processing have been effectivelyaddressed using models like Convolutional Neural Networks (CNNs) [40] andRecurrent Neural Networks (RNNs) [15]. These neural network models arewell-suited for Euclidean data. However, applying them to graph data, whichis considered non-Euclidean, is not straightforward. This is because thecomplex topological structure of graphs cannot be easily represented usingrectangular or grid-like arrays.As a result, Graph Neural Networks (GNNs) constructed through mes-sage passing have garnered significant research attention. The general designprocess of GNNs is illustrated in Figure 2.4 [62].In the first part, it is essential to determine the type of input graphdata, whether it is homogeneous or heterogeneous, directed or undirected.Different types of graphs necessitate distinct message-passing approaches.In the second part, the primary task of GNN layers is to embed informa-tion from neighboring nodes into each node, thereby preserving the topolog-ical information from the graph in the embedding vectors. Each node in thegraph needs to collect embeddings or messages from all its neighbors. Once152.5. THE STOCHASTIC BLOCK MODELFigure 2.4: Design process of GNNs [62].local information is retained, aggregation begins. Aggregation functions likesum, max, or mean are employed to combine all the received messages. Bystacking multiple message-passing GNN layers, nodes can aggregate infor-mation from an increasing neighborhood. After stacking three layers, nodespossess information from neighbors up to a distance of three edges.In the third part, different loss functions are constructed based on thegranularity of downstream tasks. These loss functions guide the message-passing process and influence the node embedding vectors. For instance,semi-supervised learning tasks use the cross-entropy function with labeleddata as the loss function, while unsupervised learning tasks employ the cross-entropy function with respect to the adjacency matrix.The primary differences among various GNN-based methods lie in the dis-tinct ways they aggregate and propagate information. For example, GraphConvolutional Networks (GCNs) aggregate neighbor information using con-volutional operators [36], while GraphSAGE aggregates neighbor informationafter sampling [28]. We will introduce the details of these different algorithmsin the third section.2.5 The Stochastic Block ModelWith significant advancements in the fields of community detection andclustering, a multitude of models and algorithms have been developed in162.5. THE STOCHASTIC BLOCK MODELmachine learning, network science, social sciences, and statistical physics.However, several fundamental questions persist:• Are communities always discoverable when they exist? Can we identifythem completely or not?• How can we measure the quality of the communities once they havebeen extracted from the graph?• How do we evaluate different detection algorithms?To address these questions, the Stochastic Block Model (SBM) has emergedas a pivotal benchmark in community detection and a fertile ground forstudying various clustering problems in machine learning and statistics [1].In the following section, we will introduce the definition of the SBM and theconcept of phase transitions in community detectability.2.5.1 The Definition of Stochastic Block ModelThe Stochastic Block Model (SBM) is a probabilistic generative modelwith planted clusters or community structures as the ground truth. In anSBM, each node is assumed to belong to one and only one pre-defined com-munity and the edge probability between two nodes only depends on thecommunities to which the nodes belong to [1]. In this thesis, we focus on thesymmetric SBMs.Definition 2.1. The symmetric stochastic block model, denoted by SBM(n, k, p, q),defines a graph with n nodes and k planted communities. In this model,p ∈ [0, 1] is the probability for two nodes within a community to have anedge, and q ∈ [0, 1] is the probability for two nodes from different commu-nities to have an edge. A community labeling of the nodes is denoted byσ = {σu, 1 ≤ u ≤ n} ∈ [k]n, where σu is the community labels of node u.172.5. THE STOCHASTIC BLOCK MODELThe adjacency matrix A of an SBM is a random 0-1 matrix such thatP (A (u, v) = 1) = pI(u,v) ∗ q(1−I(u,v)) (2.1)whereI(u, v) =1, when σu = σv0, when σu ̸= σv.In a SBM(n, k, p, q), we use Vi = {u | σu = i, 0 ≤ i < n} to denote theset of nodes in the community i. We assume that the size of the plantedcommunity is the same, i.e., |V i| = |V |/k. Note that when p = q, the SBMdegenerates into the Erdo¨s-Re´nyi (ER) random graph G(n, p) [21], and nomeaningful reconstruction of the communities is possible.The SBM is employed to create a synthetic network that exhibits similarstructural properties to the real-world network. For instance, we aim to simu-late the generation of Zachary’s karate club network, as introduced in Section2.2. Figure 2.5 is the network generated using the SBM(34, 2, 0.1, 0.01). Theadvantages of employing the SBM are multifaceted [32]. Firstly, the SBMallows the generation of synthetic networks that closely mirror the struc-tural traits of real-world networks. This simulated environment provides acontrolled platform for evaluating community detection algorithms, wherethe ground truth is known. Additionally, the SBM acts as a benchmark forevaluating algorithm reliability when dealing with real-world networks whosetrue community structure is unknown, particularly in cases with overlaps oruncertainties. Lastly, experiments conducted on the SBM provide insightsand guidance for community detection across various datasets. They providea clearer understanding of the limits and behaviors of detection algorithmperformance in controlled settings.Definition 2.2. [1] For a given graph, let σ ∈ [k]n be the ground truth fornode community labels, and let σ̂ ∈ [k]n be the predicted community labels.182.5. THE STOCHASTIC BLOCK MODELFigure 2.5: Graph generated using SBM(34, 2, 0.1, 0.01) to model Zachary’skarate club network.The overlap of two labelings is defined as:Overlap = maxπ∈Pk∑n−1u=0 1(σu = π(σ̂u))n, (2.2)where Pk represents the set of all possible permutation mappings among thek classes and 1(·) is the indicator function. Node that |Pk| = k!.The measure of Overlap is the maximum among all permutations of k-class labels. It is important to note that we use label permutation to addresscommunity detection problems in symmetric SBMs. It is necessary to notethat under unsupervised learning settings, in symmetric SBMs where allcommunity-wise connection probabilities are the same, and the size of eachcommunity is also the same, communities become indistinguishable from eachother [1]. Since we are unable to recover the true community labels, our ob-jective is to reconstruct the network partition into communities. In essence,the focus is on identifying the grouping of nodes into communities ratherthan assigning specific labels to those communities.The semi-supervised learning setting is different, as a small portion of192.5. THE STOCHASTIC BLOCK MODELnode labels is provided. The performance can be measured directly by theaccuracy, which represents the proportion of nodes correctly classified. Fora binary classification problem, accuracy is calculated throughaccuracy =TP + TNTP + FP + TN + FN, (2.3)where TP, TN, FP, and FN respectively represent true positive, true negative,false positive, and false negative.• True Positive refers to the number of predictions where the classifiercorrectly predicts the positive class as positive.• True Negative refers to the number of predictions where the classifiercorrectly predicts the negative class as negative.• False Positive refers to the number of predictions where the classifierincorrectly predicts the negative class as positive.• False Negative refers to the number of predictions where the classifierincorrectly predicts the positive class as negative.For a multi-class classification problem, accuracy is calculated throughaccuracy =Correct predictionsAll predictions. (2.4)Different levels of recovery correspond to different recovery requirements.Note that all recovery requirements in this thesis are going to be asymptotic,taking place with high probability as n tends to infinity [1].Definition 2.3. [1] The following recovery requirements are solved if thereexists an algorithm that takes G as an input and outputs σˆ ∈ σˆ(G) such that• Exact recovery: P (Overlap (σ, σˆ) = 1) = 1− o(1).• Weak recovery: P (Overlap (σ, σˆ) > α ) = 1− o(1).202.5. THE STOCHASTIC BLOCK MODELThe symmetric SBM(n, k, p, q) is weakly recoverable if there exists ε > 0and an algorithm that takes SBM as an input and outputs σˆ ∈ σˆ(SBM)such thatP(Overlap (σ, σˆ) >1k+ ε)= 1− o(1). (2.5)The notion of exact recovery necessitates flawless retrieval of each nodelabel. Conversely, weak recovery allows partial correctness in label retrieval,permitting certain misclassifications. The parameter α symbolizes algorithmaccuracy. When the achievable α is too small, labels obtained by any de-tection algorithms become less meaningful as it indicate a high proportionof misclassifications. This is why, in Definition 2.3 of weakly recoverable inthe SBM, it requires Overlap > 1k+ ε, where 1kis the achievable α obtainedthrough random guess labeling. The accuracy of random guessing approachesapproximately 1k,i.e., limn→∞Overlap (σ, σˆ) = 1k. α = 1kserves as a threshold todistinguish whether the detection algorithm has effectively resolved the weakrecovery problem or not [1].Another special case to consider is the symmetric SBM(n, k, p, q) wherep = q. In this instance, the SBM reduces to an ER graph G(n, p), whereno distinct community structure can be exploited by detection algorithms torecover the ground truth partition. The edges between nodes are independentand not dependent on their classes. The probability of nodes being correctlyclassified will be 1k.2.5.2 Fundamental LimitsThe fundamental limits of community detection refer to theoretical bound-aries and challenges that exist in identifying communities or clusters withincomplex networks [3]. From an information-theoretic perspective, it involvesidentifying conditions under which the discovery of communities is feasible,regardless of complexity or the specific algorithms employed. From a com-212.5. THE STOCHASTIC BLOCK MODELputational perspective, this imposes additional limitations on the existenceof efficient algorithms that solve the problem, indicating that they operatewithin polynomial time in the number of nodes. This fundamental limit istypically characterized by the phase transition of the recoverability of com-munity structure in the SBM [18]. A phase transition is a sudden change inthe properties of a system as the control parameters cross some threshold. Inthe symmetric SBM, the community detection problem will undergo a phasetransition as model parameters change. Within a specific range of parame-ters, the network’s community structure can be recovered, whereas in otherranges, recovery becomes challenging or even impossible. Specifically, it hasbeen proven that phase transitions take place at different thresholds definedby particular functions of the parameters, such as the Chernoff-Hellinger(CH) threshold for exact recovery and the Kesten-Stigum (KS) threshold forweak recovery [1], as summarized in the following theorems.Theorem 2.4 (Exact recovery - Chernoff-Hellinger divergence). [2] An in-stance is taken from the SBM (n, k, aln (n) , bln (n)) where constants a, b >0, and we defineD+ (a, b) =(√a−√b)2k. (2.6)When D+ (a, b) > 1, the exact recovery task in G is efficiently solvable. Onthe contrary, when D+ (a, b) ≤ 1, the exact recovery task in G is unsolvable.Theorem 2.5 (Weak recovery - Kesten-Stigum (KS) threshold). [1] An in-stance is taken from the SBM (n, k, a/n, b/n) where constants a, b > 0, andwe define the signal-to-noise ratio (SNR) as follows:SNR =(a− b)2k(a+ (k − 1)b) . (2.7)• For any k > 2, it is possible to solve weak recovery efficiently if andonly if SNR > 1.• If k ≥ 4, it is possible to solve weak recovery information theoretically222.5. THE STOCHASTIC BLOCK MODEL(i.e., not necessarily in polynomial time in n) for some SNR strictlybelow 1.Note that in cases where k ≥ 4, there exists a challenging but detectablegap between the information-theoretic threshold and the algorithm threshold[4]. Within this gap, an algorithm might exist to solve the weak recoveryproblem, but there is no guarantee that it running in polynomial time. On theother hand, when the SNR > 1, algorithms, such as the Belief Propagation(BP) algorithm [1], can efficiently solve the problem in polynomial time.Studying exact recovery is experimentally challenging because it requiresall predicted labels to be correct, which is hard to guarantee in every real-istic experimental setting. Therefore, in this thesis, we focus on the weakrecovery problem (also known as detection), as it becomes a more realisticand achievable objective for experimental analysis.From Theorem 2.4 and Theorem 2.5, graphs generated from the SBMat the thresholds are sparse, with the degree being constant or logarithmicin the number of nodes. Consequently, our experimental focus is on thesespecific parameter ranges. These concepts and related challenges also provideguidance for dense graphs because they reveal the performance limits anddifficulties of community detection under different parameter configurations.Another task closely related to weak recovery is the learnability of pa-rameters of the SBM: Given a graph G is generated by SBM(n, k, p, q), isit possible to obtain a consistent estimator for the parameters p and q? Fora symmetric SBM with two communities, it is important to note that weakrecovery, which essentially means correctly identifying the community struc-ture without knowing specific labels, is equivalent to learnability [1]. If weakrecovery cannot be achieved, the underlying parameters (p and q) are notconsistently estimable.23Chapter 3Graph Embedding MethodsGraph embedding is a technique used in machine learning and dataanalysis to convert the complex structures of graphs or networks into low-dimensional, continuous vector representations. These embedding methodsenable the application of machine learning techniques for processing graphdata. This section introduces six distinct graph embedding methods usedin experiments. Among these methods, there are three shallow embeddingmethods, such as DeepWalk, Node2vec, and LINE, and three graph neuralnetworks (GNN)-based methods, including GCN, GraphSAGE, and GAE.These methods were chosen for their popularity and different advantagesin the field. DeepWalk and Node2vec are both random-walk-based methods.Their simplicity and effectiveness in capturing community structures withingraphs make them valuable baseline methods. LINE is designed to handlelarge-scale networks efficiently. GCN is a basic GNN-based model, whichhas demonstrated superior performance in semi-supervised learning tasks ongraphs. GraphSAGE aggregates features from a node’s local neighborhood,making it highly adaptable and scalable for large, evolving graphs. GAEsuse an encoder-decoder architecture which is particularly powerful for unsu-pervised learning tasks. These proven effective graph embedding methodsare well-suited for our experiments.3.1 DeepWalkDeepWalk is an unsupervised embedding method based on the idea ofusing random walks to explore the graph and generate sequences of nodes.243.1. DEEPWALKIt uses these sequences to learn node embeddings from the Skip-gram model.Algorithm 2 [46] outlines the fundamental operation of DeepWalk throughtwo primary steps: generating random walks and training a Skip-gram modelto obtain node embeddings.Algorithm 2: DeepWalk(G,w, d, γ, t)Data: graph G(V,E), window size w, embedding size d, walks pervertex γ, walk length tResult: matirx of vertex representations Φ ∈ R|V |×d1 Initialization: Sample Φ from U |V |×d ;2 Build a binary Tree T from V ;3 for i = 0 to γ do4 O = Shuffle(V );5 for each vi ∈ O do6 Wvi = RandomWalk(G, vi, t);7 SkipGram(Φ,Wvi , w);8 end9 end• Random Walks: DeepWalk starts by randomly traversing the graphstructure. In each round, the random walk sets each node as a startingpoint, and then randomly selects other nodes to generate sequencesbased on the predefined path length. The number of random walks isalso an adjustable parameter. For instance, in Figure 3.1, a set pathlength of 4 is established within a single round to obtain all randomwalk paths. These sequences will serve as the training set for the Skip-gram model.• Skip-gram Model: This model learns to predict the likelihood of nodesbeing close to each other in the network based on their shared ran-dom walk sequences. This process is similar to word embeddings innatural language processing (NLP) [44]. The frequency of two nodes253.2. NODE2VECFigure 3.1: Sequences generated by random walks.co-occurring within a sequence corresponds to their similarity. Specif-ically, in Algorithm 3 [46] lines 1 to 3, for each node within everysequence, the likelihood of other nodes appearing within the windowrange, denoted as w, around that particular node is computed. Theassumption of independence is used to effectively overlook the sequen-tial order of nodes. In line 4, the node’s embedding vector is updatedusing a gradient descent algorithm, with the learning rate representedby α.Algorithm 3: SkipGram(Φ,Wvi , w)1 for each vj ∈ Wvi do2 for each uk ∈ Wvi [j − w : j + w] do3 J (Φ) = −logPr(uk|Φ(vj)) ;4 Φ = Φ− α ∗ ∂J∂Φ;5 end6 end3.2 Node2vecNode2vec, similar to DeepWalk, is a graph embedding method that com-bines the exploration of Depth-First Search (DFS) and Breadth-First Search(BFS) neighborhoods. Both these two methods use sequences obtained263.2. NODE2VECFigure 3.2: Biased random walks in Node2vec [27].through random walk to train a Skip-gram model for acquiring node em-beddings.However, DeepWalk generates entirely random sequences. Its limitationlies in the inability of its embedding vectors to adequately reflect the orig-inal network’s structural characteristics, such as homophily and structuralequivalence. On the other hand, Node2vec aims to capture the structural in-formation of graphs by using a biased random walk strategy to create theseembeddings. The key concept is to create flexible random walks by intro-ducing two parameters: e (return parameter) and f (in-out parameter). Theparameter e encourages the walk to revisit nodes within a short number ofsteps, capturing the local neighborhood. The parameter f allows the walk tomove away from the starting node, exploring more global graph structures.We mainly focus on how Node2vec generates biased random walks.In the Figure 3.2 [27], s represents the previous node, v denotes thecurrent node, and x1, x2, x3 are the neighbors of v. The probability of thenext node is determined by the bias function [27]:273.3. LINEα(v, x) =1e, d(s, x) = 01, d(s, x) = 11f, d(s, x) = 2, (3.1)where d(s, x) is the shortest path distance between nodes s and x.Parameter e governs the probability of revisiting recently visited nodes.A lower e biases the sequence towards revisiting nodes. On the other hand,parameter f dictates whether the walk tends towards BFS or DFS. For f > 1,the sequence leans towards visiting nodes closer to the current node, resem-bling BFS. In contrast, for f < 1, the sequence inclines towards visitingnodes farther from the current node, resembling DFS. These parameters sig-nificantly influence walk behavior, enabling a balance between broad graphexploration and local neighborhood structures.3.3 LINELINE, which stands for large-scale information network embedding, aimsto create embeddings that capture both local and global structures of a net-work. LINE achieves this by constructing two types of objective functions,one for first-order proximity and another for second-order proximity.• First-order Proximity: This proximity serves to depict the local simi-larity between two nodes in a graph. If there exists an edge betweennodes i and j, the edge weight wi,j represents the first-order proximityof the two vertices. Otherwise, the first-order proximity is consideredas 0. Specifically, for an undirected edge (i, j), the joint probability ofvertices vi and vj is expressed as [51]:p1(vi, vj) =11 + e−−→u Ti −→u j(3.2)283.3. LINE,where −→u i represents the vector representation of node vi.Define the empirical distribution as [51]p′1(vi, vj) =wi,j∑i,j∈E wi,j. (3.3)Therefore, the objective function is [51]L1 = d(p′1(vi, vj), p1(vi, vj))= −∑i,j∈Ewi,jlog(p1(vi, vj)).(3.4)The function d() is the distance between two distributions. The resultis using the Kullback-Leibler (KL) divergence to measure the differencebetween these distributions and simplifying the result by disregardingconstant terms. LINE aims to preserve the local network structureby optimizing the objective function L1 that captures the first-orderproximity.• Second-order Proximity: This proximity aims to characterize the struc-tural similarity between two nodes in the graph. It assumes that nodessharing a considerable number of common neighborhoods are similar,whereas if there are no shared adjacent neighborhoods between twonodes, their second-order proximity is considered as 0. We not onlyuse −→u i to denote the vector representation of the node itself but alsouse −→u ′i to represent the vector representation of the node as a contextnode for other nodes. The probability of node vi generating contextnode vj is [51]p2(vj|vi) = e−→u ′Tj −→u i∑|V |k=1 e−→u ′Tj −→u i. (3.5)Similarly, the empirical distribution is defined as [51]293.4. GRAPH CONVOLUTION NETWORKSp′2(vj|vi) =wi,j∑k∈E wi,k. (3.6)Therefore, the objective function is [51]L2 = −∑i,j∈Ewi,jlog(p2(vj|vi)). (3.7)LINE aims to capture the global structure of the network by optimizingthe objective function L2 that captures the second-order proximity.3.4 Graph Convolution NetworksThe three methods we mentioned aim to preserve structural informationwithin the embedding vectors through techniques such as random walks andproximity. These vectors are subsequently used in node classification tasks.Conversely, GNN-based methods involve learning and training on the graphbased on specific tasks. They train a virtual network to store the structuralinformation surrounding each node.Based on Section 2.4, the primary distinction among various GNN meth-ods lies in their differing approaches to aggregating and passing messages.The key idea behind GCNs is to learn node representations by using con-volutional operations to aggregate information from neighboring nodes in agraph. This concept comes from both spectral graph theory and Convolu-tional Neural Networks (CNNs).Equation 3.8 [36] represents the propagation function in a basic form ofGCN. H(l+1) denotes the updated embeddings at the next layer. H l rep-resents the node embeddings at layer l. Specifically, H0 signifies the inputfeature matrix. Aˆ = A+I represents the adjacency matrix of the graph withadded self-connections. Dˆ is the degree matrix derived from Aˆ. Dˆ−12 AˆDˆ12symmetrically normalizes the adjacency matrix Aˆ to reduce the scale gap303.5. GRAPHSAGEbetween the output vector and the input vector after multiple layers. Bymultiplying the normalized adjacency matrix with the node embeddings atthe current layer, the information from the neighborhood is aggregated tothe node embeddings at the next layer. W (l) signifies the weight matrix atlayer l, and σ(·) represents the activation function, such as ReLU.H(l+1) = σ(Dˆ−12 AˆDˆ12H(l)W (l)) (3.8)GCN uses this propagation function for information propagation and ag-gregation, capable of being stacked in multiple layers. In this thesis, we usea two-layer GCN, with the propagation equation as follows:GCN(A,X) = AˆReLU(AˆXW (0))W (1), (3.9)where X is the input feature matrix and W (0)) and W (1) are the parametersthat the GCN learns.If the graph data lacks features, the feature matrix can be replaced withan identity matrix. The resulting output is then employed in a classifier fornode classification tasks. It is essential to note that GCN is a semi-supervisednode classification approach. Furthermore, GCNs can be integrated into anencoder-decoder architecture to undertake unsupervised tasks, such as graphautoencoders in Section 3.6.3.5 GraphSAGEGraphSAGE is a GNN-based graph embedding technique that divergesfrom frequency domain methods, such as GCN. Unlike GCN, which ofteninvolves spectral graph theory and the transformation of graphs into a spec-tral domain using techniques like graph Laplacians or eigendecomposition,GraphSAGE follows a spatial domain approach. It aims to learn node embed-dings by sampling and aggregating features from a node’s local neighborhood313.5. GRAPHSAGEwithin the graph structure [28].• Sampling Strategy: In GraphSAGE, a fixed number of neighbors arechosen for each node in the graph. For instance, in Figure 3.3, the rednode is the selected central nodes. The yellow nodes are the first-hopneighbors of the red node, denoting a distance of 1 from the red node.Similarly, the blue nodes are the second-hop neighbors of the red node.A predetermined quantity of nodes is uniformly and randomly sampledfrom both the first and second-hop neighbors. This strategy allows fora balanced and informative selection of neighboring nodes and can alsocapture local information effectively and efficiently.• Aggregation Functions: GraphSAGE aggregates features from a node’ssampled neighbors to generate the node’s embedding. It uses aggrega-tion functions such as mean, max pooling, LSTM, or mean poolingoperations to combine the features. The choice of aggregator functionsallows for different ways to combine information. For instance, distinctaggregator functions can be used to aggregate information from firstand second-hop neighbors, allowing the model to capture diverse in-formation from neighborhoods. In this thesis, we use the max poolingaggregation function.• Unsupervised Learning and Semi-supervised Learning: GraphSAGEsupports both unsupervised and semi-supervised training modes. Graph-SAGE uses unsupervised learning to aggregate and acquire node rep-resentations by sampling and aggregating features from their neighbor-hoods. The distinction lies in the choice of the loss function. The lossfunction in unsupervised learning measures the similarity between thenodes and their neighboring nodes, where a higher similarity indicatesmore shared neighbors. Conversely, in semi-supervised learning, theloss function differs and aligns with specific downstream tasks, such aslogistic regression for node classification tasks.323.6. GRAPH AUTOENCODERFigure 3.3: Sampling strategy in GraphSAGE.3.6 Graph AutoencoderAn Autoencoder (AE) is a type of artificial neural network used for un-supervised learning and dimensionality reduction [8]. It aims to learn acompressed representation or embedding of input data by training the net-work to reconstruct the input as accurately as possible. Figure 3.4 showsthe architecture of an autoencoder. There are three modules: an encoder,a decoder, and compressed embeddings denoted as Z. The embedding Z istreated as a feature and can be used for various downstream tasks, includingsupervised learning, clustering, visualization, and other applications. Thestructure and purpose of Graph Autoencoders (GAE) are similar to those ofAutoencoders (AE), but GAE is specifically designed for processing graphdata.3.6.1 GAESimilar to traditional autoencoders, GAE also has an encoder-decoderarchitecture [37]. The encoder takes node features and maps them into alower-dimensional latent space, while the decoder reconstructs the original333.6. GRAPH AUTOENCODERFigure 3.4: The architecture of an autoencoder.Figure 3.5: The architecture of a GAE [37].graph structure from the learned latent space. This latent space representa-tion captures important structural and feature information about the nodes.As shown in Figure 3.5 [37], the encoder component of GAE consists ofa two-layer GCN, as explained in Section 3.4. The decoder uses the innerproduct of the embedding vectors Z and its transpose to generate the recon-structed adjacency matrix, denoted as A′ = Z · ZT .GAE employs a loss function that quantifies the difference between theinput graph structure (or graph features) and the graph structure recon-structed from the learned embeddings. Typically, this loss function measuresthe similarity between the original adjacency matrix and the reconstructedadjacency matrix. The loss function used in our GAE model is defined as343.6. GRAPH AUTOENCODERFigure 3.6: The architecture of a VGAE [37].follows [37]:L = − 1Nn∑i=0n∑j=0(Aij logA′ij + (1− Aij) log(1− A′ij)). (3.10)GAE is applicable in both unsupervised and semi-supervised learning set-tings. During the process of learning node representations, GAE does notrequire labels on nodes for training. The resulting embedding vectors canbe employed in unsupervised clustering algorithms such as k-means and DB-SCAN to accomplish node classification tasks. Additionally, GAE supportstraining classifiers, such as Logistic Regression, for performing node classifi-cation tasks in the semi-supervised setting.3.6.2 VGAEThe Variational Graph Auto-Encoder (VGAE) extends the GAE by in-corporating the principle of the variational autoencoder (VAE) into the graphembedding process. This extension enables the model to learn probabilisticdistributions across the latent space. Specifically, in the VGAE encoder, themodel learns the mean and variance parameters of a normal distribution in-stead of weights W , assuming that the embedding vector of a node followsa normal distribution. Subsequently, by sampling from this normal distribu-tion, it generates the embedding representations for each node.As shown in Figure 3.6 [37], similar to GAE, the encoder in VGAE also353.6. GRAPH AUTOENCODERconsists of a two-layer GCN. However, the embedding vector Z in VGAE isnot derived from a deterministic GCN output, but it is sampled from a mul-tidimensional Gaussian distribution. The mean µ and variance log σ of theGaussian distribution are determined by two GCN layers GCNµ(X,A) andGCNσ(X,A). The node embeddings can be re-sampled from this Gaussiandistribution. The embedding vector Z is represented as [37]:Z = µ+ ϵσ, (3.11)where ϵ ∈ N (0, 1).The decoder component is also the inner product of the embedding vec-tors. The loss function in VGAE is [37]L = Eq(Z|X,A)[log p(A|Z)]−KL[q(Z|X,A)||p(Z)]. (3.12)The first term in the loss function, similar to GAE, measures the differencebetween the adjacency matrix obtained through the distribution q and theoriginal adjacency matrix. The second term is the Kullback-Leibler (KL)divergence between the learned distribution q(Z|X,A) across the latent spaceand a standard Gaussian distribution p(Z).36Chapter 4The Performance of GraphEmbedding Methods on NodeClassification: ExperimentalFindingsThis chapter presents a comprehensive exploration of the performance ofgraph embedding methods on node classification. Our experiments considerboth unsupervised and semi-supervised learning settings, offering an under-standing of capabilities in different scenarios. We conducted experiments ondatasets generated from the SBM with different parameters, paying particu-lar attention to the region of the parameter space around the phase transition,focusing on the recoverability of hidden communities under the model. Thereare two interesting observations from our experiments. First, in unsupervisedlearning settings, GNN-based methods may face challenges when the SNRis around the threshold. Second, GNN-based methods exhibit threshold be-havior similar to that in unsupervised learning settings even in the setting ofsemi-supervised learning.4.1 Experimental Design and MethodologyAs shown in Figure 4.1, our experiments consist of four steps.1. In the first step, we generate the experimental datasets using the model374.1. EXPERIMENTAL DESIGN AND METHODOLOGYFigure 4.1: The framework of experiments.SBM(n, k, p, q). In this model, n nodes are partitioned into k commu-nities, and members in the same group are assigned unique labels from1 to k. Independently, with the probability p, we generate edges be-tween two nodes within the same community, and with the probabilityq, we generate edges between two nodes in different communities.2. The second step involves training various graph embedding methods,including random walk-based methods, LINE, and GNN-based meth-ods. Detailed configurations of these methods will be elaborated on inSection 4.1.3.3. In the third step, we generate the node embedding vectors. Shallowgraph embedding methods and LINE generate node embedding vectorsin an isolated stage, specifically designed for the subsequent node clas-sification task. In contrast, GNN-based methods follow an end-to-endprocess, where embedding learning and the learning for the downstreamtask are conducted simultaneously.[42].4. In the last step, we use the embedding vectors for the node classifica-384.1. EXPERIMENTAL DESIGN AND METHODOLOGYtion task, considering both unsupervised and semi-supervised scenar-ios. In the setting of unsupervised learning, we apply the k-means++algorithm to generate k clusters for the nodes. In the setting of semi-supervised learning, the embeddings are used to train a multi-labelclassifier for predicting the labels of the nodes.4.1.1 Experiment SetupWe employed OpenNE(https://github.com/thunlp/OpenNE), an open-source Python package for graph embedding, to learn node embeddings forDeepWalk [46], Node2vec [27], LINE[51] and GCN [36]. We implemented theGraphSAGE [28] method using the StellarGraph library, which is a Pythonlibrary for machine learning on graph-structured data. For GAE and VGAE,we use the implementation provided in [37]. All these methods are imple-mented in Python using the TensorFlow deep learning framework. The ex-periments were conducted on a Windows system with the following hardwarespecifications: CPU - Intel(R) Core(TM) i7-7700HQ CPU @ 2.81 GHz, GPU- NVIDIA GeForce GTX 1060, Memory - 16GB.4.1.2 Embedding Methods ConfigurationsAll the considered embedding methods share some common parametersin their configurations, such as the size of graphs and the dimension of nodeembedding vectors. In the setting of semi-supervised learning, additionalshared parameters include label files and the testing ratio. Table 4.1 showsthe values set for these common parameters in our experiments.On the other hand, each method also has other controllable parametersas follows. Table 4.2 shows the values set for these specific parameters in ourexperiments.• Random-walk-based methods, such as DeepWalk and Node2vec, use aSkip-gram model to train sequences derived from random walks. Con-394.1. EXPERIMENTAL DESIGN AND METHODOLOGYParameter ValueThe size of graphs *Treat the graph as weighted FalseTreat the graph as directed FalseThe dimension of embedding vectors 128Label files *Testing ratio ρ *Table 4.1: Common parameters in experiments. A note regarding *: Thisrepresents different settings in various experiments.trollable parameters include the number of random walks starting ateach node, the length of random walks, window size for node sequences,and parameters e and f governing random walk behavior in Node2vec.• LINE optimizes first-order and second-order proximity objective func-tions to derive node embeddings. Controllable parameters include neg-ative sampling ratio and the order of LINE (first-order, second-order,or a combination of both).• GNN-based methods such as GCN, GraphSAGE, GAE, and VGAEtrain a network model that stores structural information around eachnode. Node embedding is derived from the weight matrix W in thehidden layers of the model. GCN, GAE, and VGAE have controllableparameters such as node features, learning rate for gradient descent,training epochs, dropout rate, and the number of units in the hiddenlayer. GraphSAGE’s parameters include the number of node pairs permini-batch, training epochs, sizes of 1-hop and 2-hop neighbor samples,and layer sizes. A testing ratio for node classification is essential for allgraph embedding methods involved in semi-supervised learning tasks.404.2. THEORETICAL BASELINEMethod Parameter ValueRandom-walk-basedThe number of random walks 32The length of the random walk 64Window size of the node sequence 10e for Node2vec 0.25f for Node2vec 0.5LINENegative sampling ratio 5The order of LINE 1GNN-basedThe number of layers in a GNN model 2Node features Identity matrixTraining epochs Max 1000Learning rate 0.01Dropout rate 0.1The number of units in the hidden layer 256GraphSAGEThe size of mini-batch 50Training epochs 4The size of samples [16,8]The size of layers [128,128]Aggregation function Max pooling aggregatorTable 4.2: Specific parameters in experiments.4.2 Theoretical BaselineIn Section 3.5, we discussed that for a SBM(n, k, p, q), the measureOverlap for random guessing can reach 1k, i.e., limn→∞Overlap (σ, σˆ) = 1k+ε [1].We consider 1kas the theoretical baseline for determining the effectiveness ofan algorithm in community detection tasks. As we consider the number ofnodes to be finite in our experiments, we will use a more accurate baseline.The details are discussed in the rest of this section, specifically for k = 2 andin the general case of k,4.2.1 Baseline for k=2We consider a graph G generated from the SBM(n, 2, p, q). The twohidden communities in G have the same size n2. Let σ ∈ {0, 1}n be a pre-assigned labeling and σˆ ∈ {0, 1}n be a labeling of all nodes by random414.2. THEORETICAL BASELINEguessing, i.e., for each node with a probability of 0.5, we assign the label 0or label 1. We have that σˆ is a collection of independent Bernoulli variables.We aim to calculate the expected value of the maximum overlap, given allpossible permutations of σˆ. For k = 2, there are two permutations, denotedby π1 and π2, whereπ1(σˆ) =0, σ = 01, σ = 1 and π2(σˆ) =1, σ = 00, σ = 1 .Let X be the number of nodes of which the original labels and the labelsobtained by random guessing under the permutation π1 are the same, i.e.,X =n−1∑u=01(σu = π1(σ̂u)), (4.1)and let Y be the number of nodes of which the original labels and the labelsobtained by random guessing under the permutation π2 are the same, i.e.,Y =n−1∑u=01(σu = π2(σ̂u)). (4.2)Note that X + Y = n, and both X and Y follow binomial distribution, i.e.,X, Y ∼ B(n, 0.5).The expected value of max(X, Y ) is given by:424.2. THEORETICAL BASELINEE(max(X, Y )) = E(max(X,n−X))=n∑k=0max(k, n− k)P(X = k)=n2−1∑k=0(n− k)P(X = k) +n∑k=n2kP(X = k)=n2−1∑k=0(n− k)(nk)0.5n +n∑k=n2k(nk)0.5n= 0.5nn2−1∑k=0(n− k)(nk)+n∑k=n2k(nk)= 0.5nn2−1∑k=0(n− k)(nn− k)+n∑k=n2k(nk)= 0.5n n∑k=n2+1k(nk)+n∑k=n2k(nk)(4.3)Since the expected value of the binomial distribution E(X) =∑nk=0 k(nk)0.5n= 0.5n, we can get434.2. THEORETICAL BASELINEE(max(X, Y ))− 0.5n = 0.5n n∑k=n2+1k(nk)+n∑k=n2k(nk)−n∑k=0k(nk)= 0.5n n∑k=n2+1k(nk)−n2−1∑k=0k(nk)= 0.5n · n n∑k=n2+1(n− 1k − 1)−n2−1∑k=0(n− 1k − 1)= 0.5n · nn−1∑k=n2(n− 1k)−n2−2∑k=0(n− 1k)= 0.5n · n(n− 1n2)= 0.5n · n2(nn2)(4.4)Applying Stirling’s approximation for n!, which is n! =√2πn(ne)n(1 +o(1)) and simplifying, we getE(max(X, Y )) = 0.5n+ 0.5n · n2· 2n√π · n2(1 + o(1))= 0.5n+√n2π(1 + o(1))(4.5)444.2. THEORETICAL BASELINETherefore, by Definition 2.2, the Overlap isOverlap = maxπ∈Pk∑n−1u=0 1(σu = π(σ̂u))n=E(max(X, Y ))n= 0.5 +√12πn(1 + o(1))(4.6)Formula (4.6) suggests that as n approaches infinity, the Overlap tendsto 12. When n is finite, we use this Overlap as our theoretical baseline.4.2.2 Baseline for General kFor the case when k > 2, the situation becomes considerably more compli-cated, and obtaining analytical solutions is challenging. In such cases, we useMonte Carlo simulations to estimate the value of Overlap where n is finite.Monte Carlo simulation is a method that approximates problem solutionsby generating a series of random numbers. It involves seeking a statisticalanalogue and obtaining an approximate solution through experimental sam-pling [49]. In simple terms, Monte Carlo simulation involves generating alarge number of samples using a computer. It utilizes discrete data insteadof continuous data and replaces probabilities with the frequency of events,providing an approximation to problem solutions.Listing 4.1 shows the pseudo-code for the Monte Carlo Simulation. Whenn approaches infinity, the observed Overlap tends to converge towards 1k.However, under the finite condition, the Overlap surpasses the theoretical1kthreshold. Our simulation results serve as a result of random guessingin experimental settings and provide a practical baseline for evaluating therecoverability of graphs in experimental designs.454.3. EXPERIMENTS IN THE UNSUPERVISED LEARNING SETTINGSListing 4.1: Monte Carlo Simulation Pythonn = 400k = 4m = 1000000probabilities = [1/k] * kpermutations = list(itertools.permutations(range(1, k + 1)))acc = 0.0for _ in range(m):results = [np.random.multinomial(n, probabilities) for _ inrange(k)]max_value = max([sum([results[idx][label-1] for idx, label inenumerate(permutation)]) for permutation in permutations])acc += max_valueexpected_max = acc/moverlap = expected_max/(k*n)4.3 Experiments in the UnsupervisedLearning SettingsWe conducted experiments to evaluate the performance of six embed-ding methods in the unsupervised learning setting: Deepwalk, Node2vec,LINE(1st), GraphSAGE, GAE, and VGAE.We set the parameters of SBM(n, k, p, q)as n = 400, k = 2, p = 0.06 and vary q to generate different training datawith SNR ∈ [0.1, 4]. Within this parameter range, the average degree isguaranteed to be between 10 and 20. In all figures and tables in Chapter 4and Chapter 5, the embedding vector dimension is 128, and each data pointrepresents an average result of 100 independent runs.From Figure 4.2, we observe that these six methods closely align with thetheoretical detection threshold when the number of communities is equal to 2(Theorem 2.5). When SNR < 0.9, all methods perform worse than random464.3. EXPERIMENTS IN THE UNSUPERVISED LEARNING SETTINGSFigure 4.2: Unsupervised results when k=2.guessing. As SNR increases from 0.9 to 1, the accuracy of graph embeddingmethods starts to rise, and after SNR > 1, accuracy increases rapidly.Figure 4.3 shows the experiments we conducted with the number of com-munities set to 4. We observed that these six methods also closely align withthe theoretical detection thresholds when the number of communities is equalto 4 (Theorem 2.5). When SNR < 0.8, all methods perform worse than ran-dom guessing, because the community structure recovery is not possible. Onthe other hand, when 0.8 < SNR < 1.0, all of these methods are better thanrandom guessing. Recalling the theoretical result, this interval of (0.8, 1.0)corresponds to the gap discussed in the theoretical analysis. In this range, itis possible to solve weak recovery problem information-theoretically, but thealgorithm may not necessarily run in polynomial time. Our result demon-strates the superiority of these graph embedding methods over traditionalalgorithms, such as the Belief Propagation method which has been proven tofail in solving the weak recovery problem for these parameters.474.3. EXPERIMENTS IN THE UNSUPERVISED LEARNING SETTINGSFigure 4.3: Unsupervised results when k=4.More interestingly, when SNR is around 1, the performance of the GNN-based embedding methods, such as GraphSAGE, GAE, and VGAE, is ob-served to be inferior to shallow embedding methods including Deepwalk andnode2vec. The degradation in performance for GNN-based methods is par-ticularly evident as the SNR decreases. This finding sheds light on the sensi-tivity of GNN-based methods to the quality of the signal relative to the noisein the graph.In summary, graph embedding methods exhibit greater power and effec-tiveness compared to traditional clustering methods. However, GNN-basedmethods may face challenges when the SNR is around the threshold.484.4. EXPERIMENTS IN THE SEMI-SUPERVISED LEARNING SETTINGS4.4 Experiments in the Semi-SupervisedLearning SettingsAs discussed in Chapter 3, some graph embedding methods are specifi-cally designed for applications in semi-supervised learning. In this section,we report the results of experiments using different embedding methods inthe semi-supervised learning setting.Notably, as the following Theorem 4.1 shows, the previously establishedthreshold disappears in semi-supervised learning settings. We are interestedin the effectiveness of graph embedding methods in this scenario and in ex-perimentally verifying the theorem analysis.We consider a semi-supervised task where we have training graph dataSBM(n, k, p, q), along with a reveal ratio ρ [50] indicating the proportionof nodes with known labels.Theorem 4.1. [50] Given a graph SBM(n, 2, p, q) and a reveal ratio ρ ≥ 0,there exists an algorithm that can solve the semi-supervised weak recoveryproblem with any reveal ratio ρ > 0 for arbitrary SNR > 0.We conducted experiments in this scenario. We set the reveal ratio ρ =0.2 and the parameters of SBM(n, k, p, q) as n = 400,k = 2, p = 0.06, andvary q to generate different training data with SNR ∈ [0.1, 4]. Within thisparameter range, the average degree is guaranteed to be between 10 and 20.As shown in Figure 4.4, our experimental results for shallow embeddingmethods conform to Theorem 4.1, which is that the phase transition phe-nomenon disappears in semi-supervised learning settings. When SNR > 0.1,all shallow embedding methods, such as DeepWalk, Node2vec, and LINE ex-hibit significantly higher Overlap compared to random guessing. We notethat the SBM is still unrecoverable using all these graph embedding methodsin the region where SNR < 0.1. This is because the number of nodes in theSBM used in the experiments is 400, which represents a finite size.494.4. EXPERIMENTS IN THE SEMI-SUPERVISED LEARNING SETTINGSFigure 4.4: Semi-supervised results when k = 2.Surprisingly, we observe that GNN-based methods still deteriorate withinthe threshold established in unsupervised learning. For example, for GNN-based methods in the range of 0.6 < SNR < 0.8, Overlap experiences asharp decline. When the SNR < 0.6, the Overlap is lower than randomguessing, GNN-based methods still have a region where weak recovery tasksare not feasible.Our observations suggest that GNN-based methods exhibit threshold be-havior similar to unsupervised learning settings even in the setting of semi-supervised learning. We conjecture that GNN-based methods may not fullyutilize the side information provided by node labels. To validate our obser-vations and hypotheses, we conduct further experiments to delve into moredetails. We set the parameters of SBM(n, k, p, q) as k = 4 for which there isno theoretical theorem established when the number of communities is equalto 4, and the other parameters remain the same.From Figure 4.5, we observe that when the number of communities is504.4. EXPERIMENTS IN THE SEMI-SUPERVISED LEARNING SETTINGSFigure 4.5: Semi-supervised results when k = 4.equal to 4, although not guaranteed by the theoretical theorem, the experi-mental results are similar to the situation where the number of communitiesis equal to 2. Shallow embedding methods in the semi-supervised learn-ing setting do not exhibit a threshold, while GNN-based methods show aclear threshold. Specifically, shallow embedding methods, such as Deep-Walk, Node2vec, and LINE, perform better than random guessing for allSNR > 0.1, indicating that there is no detection threshold for these shal-low embedding methods. However, GNN-based methods, including GCN,GraphSAGE, GAE, and VGAE, all exhibit a region where the SBM is unre-coverable. The phase transition phenomenon for GAE and VGAE occurs inthe range 0.7 < SNR < 0.8, while for GCN and GraphSAGE, it occurs inthe range 0.5 < SNR < 0.6. This observation aligns with our conjecture.To better illustrate the phase transition phenomenon, we conducted anearly stopping experiment using VGAE as an example. The number of epochsthat VGAE runs is proportional to the training time. ”Early stopping” is514.4. EXPERIMENTS IN THE SEMI-SUPERVISED LEARNING SETTINGSa technique used during the training of machine learning models to preventoverfitting. The basic idea is to monitor the model’s performance on a valida-tion set during training and stop the training process when the performanceon the validation set starts to degrade, indicating that the model is overfit-ting to the training data. Therefore, the VGAE model’s performance on avalidation set is monitored at the end of each epoch. If the performance doesnot improve or starts to degrade for a certain number of consecutive epochs,training is stopped early.In our experiments, the number of epochs for early stopping dependson two hyperparameters: the minimum number of epochs to stop and thenumber of epochs with no improvement. Based on empirical results, we chosetwo reasonable hyperparameters, setting the minimum number of epochs tostop to 300 and the number of epochs with no improvement to 50.From Figure 4.6, we observe that as SNR changes from 0.1 to 2.0, the earlystopping epochs first increase and then decrease. On one hand, when SNR isbelow the threshold, the graph is unrecoverable, and the model cannot learneffective information from the graph. Therefore, when 0.1 < SNR < 0.5,the epochs quickly reach the minimum value for training and stop early. Onthe other hand, when SNR is greater than the threshold, the model requiresmore epochs for training.Figure 4.7 illustrates the frequency of instances where the accuracy achievedby the DeepWalk and VGAE methods surpasses that of random guessesacross 100 experiments. The curve for DeepWalk grows relatively slowlyand approaches a straight line. In contrast, the curve for VGAE shows anoticeable increase in the interval (0.75, 1.0), with a steep slope. Moreover,when we increase the size of the graph, the curve tends to exhibit an abrupttransition, especially around the threshold. In other words, there is a sharptransition in the ability to recover the graph when the SNR is around thethreshold.524.4. EXPERIMENTS IN THE SEMI-SUPERVISED LEARNING SETTINGSFigure 4.6: The number of epochs for early stopping in VGAE.Figure 4.7: The Frequency of Accuracy over Random Guess.53Chapter 5Multilayer Stochastic BlockModels and Side InformationRecent literature has shown a growing interest in using side informationto address community recovery problems [25]. In this chapter, we introducea multilayer stochastic block model (M-SBM) and demonstrate how the com-bination of different layers can, to a certain degree, overcome the thresholdof recoverability in a single-layer SBM. We show that side information canbe encoded into additional layers, leading to an improvement in the weakrecoverability of the original graph data.In the semi-supervised learning scenario, we propose a method that usesknown labels in a single-layer SBM to construct additional layers. Our exper-iments demonstrate that integrating the additional layers with the originallayer can significantly improve the performance of graph embedding methods,especially those based on Graph Neural Networks (GNNs). In the unsuper-vised learning scenario, we consider a special M-SBM model where partialinformation about the community structure from an additional layer can beintegrated into the main layer to enhance the performance of embeddingmethods. We substantiate the effectiveness of our methods through empiri-cal experiments.5.1 The Multilayer Stochastic Block ModelIn recent years, multilayer network analysis, particularly concerning com-munity detection, has drawn significant attention. For instance, researchers545.1. THE MULTILAYER STOCHASTIC BLOCK MODELhave applied a Bayesian approach to a multilayer network known as the hi-erarchical stochastic block model (HSBM) to address community detectionchallenges [6]. Additionally, studies have investigated the threshold for theexact recovery problem within the correlated stochastic block model [48]. Inthis section, we introduce a multilayer stochastic block model (M-SBM) totheoretically understand the weak recovery problem in a multilayer network.Definition 5.1 (Multilayer Stochastic Block Model). A multilayer stochasticblock model, denoted as M -SBM(n, L, (ki, ai, bi)Li=1), consists of a collectionof L symmetric single-layer stochastic block models {SBMi (n, ki, ai/n, bi/n)}Li=1.These SBMi are defined on the same set of n nodes. For each SBMi, the nnodes are divided into ki communities with intra-community edge probabilityai/n and inter-community edge probability bi/n.We are interested in investigating how the additional layers will influencethe fundamental limit for the weak recovery problem in the M-SBM. In thescenario where the parameters ai and bi across different layers are the same,we establish Theorem 5.2. In Theorem 5.2, we also assume that the commu-nity labels are consistent across all L layers of the SBM, implying identicalcommunity structures. Therefore, the objective of the weak recovery prob-lem is equivalent to that in the single-layer SBM. We demonstrate that thethreshold for weak recoverability in the M-SBM is lower than that in thesingle-layer SBM.Theorem 5.2. Consider a M-SBM(n, L, (ki, ai, bi)Li=1), where (ki, ai, bi)Li=1is equal to (k, a, b) for each layer and the node community labels are the same.Then, we have• For any k ≥ 2, it is possible to solve weak recovery efficiently if andonly if (a−b)2k(a+(k−1)b) >1L.• For k ≥ 4, it is possible to solve weak recovery information-theoreticallyfor some (a−b)2k(a+(k−1)b) strictly below1L.555.1. THE MULTILAYER STOCHASTIC BLOCK MODELProof. Let the edges of the M -SBM(n, L, (ki, ai, bi)Li=1) within L layers beall included in an augmented graph G, i.e., E (G) =⋃Li=1E(SBM i). Dupli-cated edges are treated as a single edge. Since all layers of the M-SBM areSBM(n, k, a/n, b/n) and the node community labels are the same, G canbe regarded as a single-layer SBM(n, k, p, q) where intra-community edgeprobability isp = 1−(1− an)L= 1−(1− Lan+L (L− 1)2!(an)2+O((an)2)), (5.1a)and inter-community edge probability isq = 1−(1− bn)L= 1−(1− Lan+L (L− 1)2!(bn)2+O((bn)2)). (5.1b)As the number of nodes n tends to infinity, we see that p tends to La/nand q tends to Lb/n. As a consequence, the parameters of the augmentedgraph G tend toward the parameters of SBM(n, k, La/n, Lb/n). Based onTheorem 2.5, the SNR of graph G, denoted as SNR(G), is L(a−b)2k(a+(k−1)b) . Fol-lowing from Theorem 2.5, we have that for any k ≥ 2, it is possible to solveweak recovery problem in graph G efficiently(in polynomial time in n)) if andonly if L(a−b)2k(a+(k−1)b) > 1. For k ≥ 4, it is possible to solve weak recovery prob-lem in graph G information-theoretically (not necessarily in polynomial timein n) for some L(a−b)2k(a+(k−1)b) strictly below 1. Since the objective of the weakrecovery problem in M-SBM is equivalent to that in the single-layer graphG, we establish the threshold of weak recoverability in M-SBM as delineatedin Theorem 5.2.Recalling Theorem 2.5, the SNR of a single-layer SBM(n,k,p,q) is givenby (a−b)2k(a+(k−1)b) . We define the SNR of an M-SBM to be equal to that of asingle-layer SBM, which includes all edges in all M-SBM layers. For exam-ple, if we can construct a two-layer M-SBM using two identical SBM(n,k,p,q),the union of the two layers can be treated as a single-layer SBM(n, k, 1 −565.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNING(1 − p)2, 1 − (1 − q)2). Consequently, the region of SNR less than 1 for thetwo-layer M-SBM, compared to the SNR of a single-layer SBM, becomessmaller. For a more intuitive and clear understanding of the variation of thethreshold between an M-SBM and a single-layer SBM, Figure 5.1 illustratesthe SNR for both a single-layer SBM and a two-layer M-SBM composedof layers with the same parameters. In Figure 5.1, there are two curvesfor SNR = 1, where the x-axis represents the probability of edges withinthe same community, and the y-axis represents the probability of edges be-tween different communities. The blue curve corresponds to the equationSNR(SBM(400, 4, a/400, b/400)) = 1, while the red curve corresponds tothe equation SNR(M-SBM(400, 2, (4, a/400, b/400)) = 1. The regions be-tween each curve denote the undetectable zone where SNR < 1, while theremaining regions indicate the detectable zone where SNR > 1. We can seethat the undetectable region of the M-SMB curve is smaller compared to theSBM curve.Motivated by the variation of the threshold between an M-SBM and asingle-layer SBM, a possible approach to applying Theorem 5.2 to enhancethe effectiveness of GNN-based embedding methods in a single-layer graphis to learn the parameters of the SBM and use the learned parameters toconstruct the additional layers. However, it has been proven that when theaverage node degree of the model is constant, learning the parameters ofthe SBM is as challenging as solving the weak recovery problem [1]. In thenext section, we propose two methods that use different side information toconstruct additional layers, augmenting the original single-layer graph.5.2 M-SBM Data Augmentation forSemi-Supervised LearningIn this section, we introduce a data augmentation-like approach to en-hance graph embedding methods in the semi-supervised learning setting.575.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNINGFigure 5.1: Two SNR = 1 CurvesIn our experiments, we observe significant improvements in the accuracy ofGNN-based methods in the region where the performance of those methodsdeteriorates. The experiments also show the effectiveness of our methods ontwo real-world datasets.5.2.1 A Multilayer Data Augmentation ApproachWe consider the task of node classification in the setting of semi-supervisedlearning, where node labels are provided for a subset of nodes. Based on thetheoretical analysis of M-SBM, our objective is to use the adjacency infor-mation among the known labels to construct an additional layer. This newlayer is then combined with the original graph to form an augmented graphwhich serves as training data.Let’s consider a graph G(V,E) generated from the model SBM(n, k, p, q),along with a subset of nodes Vs that have known community labels. Letσ : Vs → {1, 2, . . . , k} be the labeling function for Vs in G. For each class i,we define Vsi = {v ∈ Vs | σv = i} as the set of nodes in Vs that belong tocommunity i. The set of all edges induced in Vsi is represented as E(Vsi).In our multilayer data augmentation approach, we first construct an ad-585.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNINGditional graph G′ based on the adjacency matrix of G and the set of nodeswith known community labels Vs, where G′ is defined as follows:V (G′) = V (G), E(G′) =k⋃i=1E ′(Vsi) ∪(E(G) \k⋃i=1E(Vsi)), (5.2)In the above equation, E ′(Vsi) is a set of edges obtained from E(Vsi) asfollows: for each edge (u, v) ∈ E(Vsi), we replace it with an edge (u′, v′),where u′ and v′ are randomly selected from Vsi .We replace the original graph G with an augmented graph Ga as ourtraining data, where Ga combines all edges from a two-layer M-SBM formedby the graph G and the additional graph G′. The augmented graph Ga isdefined as follows:V (Ga) = V (G), E(Ga) = E(G) ∪ E(G′). (5.3)We can see that the augmented graph Ga and the original graph G havethe same set of edges between nodes with unknown labels, while Ga containsmore edges between nodes with known labels.It is important to note that the augmented graph Ga may not necessarilyfollow the edge distribution assumed in Theorem 5.2. However, we believethat the parameters of Ga are close to those of the original graph G. Weleave the theoretical analysis of this as a subject for future research.To evaluate the effectiveness of the multilayer data augmentation ap-proach we proposed, we have conducted experiments using synthetic datagenerated from SBMs and two real-world datasets. The results of these ex-periments are reported and discussed in the rest of this section.5.2.2 Experiments on the Synthetic DataAs mentioned in Section 5.2.1, the purpose of our proposed method isto construct an additional graph using known partial node labels, which is595.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNINGSNR 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 2.0 4.0Random Guess 0.291 0.291 0.291 0.291 0.291 0.291 0.291 0.291 0.291 0.291 0.291 0.291DeepWalk 0.299 0.314 0.327 0.352 0.367 0.380 0.451 0.456 0.459 0.427 0.709 0.811DeepWalk/M-SBM 0.306 0.333 0.349 0.364 0.383 0.427 0.464 0.469 0.489 0.436 0.723 0.832Node2vec 0.312 0.320 0.330 0.360 0.380 0.400 0.436 0.487 0.508 0.429 0.782 0.884Node2vec/M-SBM 0.336 0.336 0.346 0.364 0.386 0.421 0.442 0.499 0.517 0.439 0.788 0.889LINE 0.296 0.286 0.299 0.325 0.297 0.307 0.315 0.325 0.324 0.363 0.438 0.550LINE/M-SBM 0.302 0.307 0.299 0.327 0.294 0.311 0.327 0.343 0.329 0.365 0.440 0.556GCN 0.275 0.284 0.281 0.280 0.281 0.326 0.342 0.350 0.403 0.413 0.650 0.839GCN/M-SBM 0.278 0.305 0.310 0.312 0.332 0.378 0.378 0.392 0.496 0.525 0.782 0.829GraphSAGE 0.264 0.265 0.275 0.286 0.290 0.307 0.315 0.348 0.365 0.370 0.718 0.859GraphSAGE/M-SBM 0.283 0.286 0.294 0.302 0.311 0.336 0.323 0.358 0.423 0.448 0.725 0.897GAE 0.285 0.287 0.293 0.271 0.296 0.275 0.277 0.366 0.393 0.444 0.570 0.726GAE/M-SBM 0.294 0.318 0.390 0.396 0.417 0.430 0.439 0.507 0.539 0.533 0.611 0.857VGAE 0.275 0.271 0.292 0.277 0.287 0.249 0.252 0.301 0.374 0.533 0.668 0.832VGAE/M-SBM 0.321 0.327 0.361 0.377 0.408 0.421 0.427 0.470 0.530 0.558 0.726 0.885Table 5.1: Comparison of results from different embedding methods usingoriginal SBMs and two-layer M-SBMs as training data. A note regarding*/M-SBM: This designation pertains to results obtained by integrating theoriginal SBM with an additional layer graph, constructed by randomly shuf-fling the edges between the known label nodes in the original SBM.a graph with similar edge distribution as the original one. This additionalgraph is then used as the second layer in the M-SBM, along with the originalgraph, forming a two-layer M-SBM. In Table 5.1, we show the experimentalresults of seven graph embedding methods using the original graph and thedata-augmented M-SBM as training data. We set the parameters of originalSBM(n, k, p, q) as n = 400, k = 4, p = 0.06, and vary q to generate differenttraining data with SNR ∈ [0.1, 4.0]. For the two-layer M-SBM, we set thereveal ratio ρ to 0.2. We then use the adjacency information between theknown label nodes to construct the augmented M-SBM.Through Table 5.1, we observe that the accuracy of all graph embed-ding methods is improved when using the M-SBM data augmentation ap-proach. Particularly, GNN-based methods do not exhibit a threshold for anySNR > 0. Figure 5.2 illustrates the percentage improvement in accuracyfor different graph embedding methods. From Figure 5.2, we can see that605.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNINGFigure 5.2: Percentage improvement in accuracy for different graphembedding methods. Percentage improvement is calculated byM−SBMAccuracy−OriginalAccuracyOriginalAccuracy× 100%.GCN, GraphSAGE, GAE, and VGAE show larger improvements, especiallynear the threshold. In contrast, DeepWalk, Node2vec, and LINE exhibit rel-atively smaller improvements. This also indicates that our proposed methodenables GNN-based methods to better use node labels as side information.Table 5.2 presents the accuracy of different graph embedding methods atvarious reveal ratios ρ. Figure 5.3 illustrates the percentage improvementin accuracy for DeepWalk, Node2vec, GAE, and VGAE at different revealratios ρ. We can observe that shallow embedding methods consistently showstable and relatively low accuracy improvement across different reveal ratios615.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNINGρ. In contrast, GNN-based methods show a significant improvement at lowerreveal ratios ρ, but the improvement decreases as reveal ratios ρ increase.This indicates that our approach can have a significant effect even when onlya small fraction of node labels is known.ρ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9DeepWalk 0.316 0.456 0.479 0.512 0.554 0.556 0.633 0.637 0.700DeepWalk/M-SBM 0.327 0.469 0.486 0.550 0.575 0.610 0.650 0.693 0.738Node2vec 0.299 0.461 0.496 0.542 0.590 0.613 0.675 0.692 0.766Node2vec/M-SBM 0.324 0.467 0.518 0.571 0.662 0.670 0.670 0.705 0.775LINE 0.258 0.271 0.296 0.338 0.330 0.294 0.375 0.300 0.450LINE/M-SBM 0.274 0.298 0.318 0.358 0.395 0.418 0.442 0.486 0.500GraphSAGE 0.324 0.358 0.382 0.435 0.450 0.466 0.491 0.512 0.575GraphSAGE/M-SBM 0.357 0.367 0.453 0.487 0.495 0.542 0.568 0.608 0.662GCN 0.250 0.350 0.382 0.450 0.535 0.568 0.575 0.675 0.775GCN/M-SBM 0.250 0.392 0.428 0.575 0.690 0.808 0.819 0.887 0.950GAE 0.238 0.366 0.388 0.417 0.440 0.525 0.533 0.575 0.603GAE/M-SBM 0.343 0.505 0.512 0.543 0.585 0.588 0.603 0.613 0.625VGAE 0.238 0.301 0.309 0.324 0.458 0.530 0.537 0.575 0.588VGAE/M-SBM 0.445 0.470 0.536 0.610 0.614 0.613 0.642 0.688 0.725Table 5.2: The accuracy of different graph embedding methods at differentreveal ratios ρ. A note regarding */M-SBM: This designation pertains toresults obtained by integrating the original SBM with an additional layergraph, constructed by randomly shuffling the edges between the known labelnodes in the original SBM.5.2.3 Experiments on Real-World DatasetsIn our evaluation, we also consider these two real-world datasets to pro-vide a comprehensive assessment of our proposed method’s effectiveness. Wecompared our approach with seven graph embedding methods across thesetwo datasets.• Wiki consists of 2,405 web pages categorized into 19 different classes,interconnected by a network of 17,981 links. The average degree is 14.9.625.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNINGFigure 5.3: Percentage improvement in accuracy at different reveal ratiosρ. Percentage improvement is calculated by M−SBMAccuracy−OriginalAccuracyOriginalAccuracy×100%.635.2. M-SBM DATA AUGMENTATION FOR SEMI-SUPERVISED LEARNING• Cora dataset comprises 2,708 machine learning papers, categorized into7 classes. Between papers, there are 5429 citations. The average degreeis 4.0.Wiki Coraρ 0.2 0.5 0.8 0.2 0.5 0.8DeepWalk 0.810 0.831 0.839 0.795 0.799 0.822DeepWalk/M-SBM 0.815 0.834 0.841 0.796 0.829 0.856Node2vec 0.803 0.828 0.835 0.780 0.805 0.812Node2vec/M-SBM 0.809 0.831 0.839 0.783 0.821 0.854LINE 0.726 0.766 0.780 0.463 0.485 0.500LINE/M-SBM 0.728 0.770 0.781 0.469 0.494 0.535GAE 0.664 0.697 0.738 0.663 0.733 0.799GAE/M-SBM 0.786 0.812 0.823 0.713 0.765 0.812VGAE 0.671 0.723 0.748 0.697 0.752 0.775VGAE/M-SBM 0.788 0.821 0.857 0.701 0.771 0.823Table 5.3: Experiments in Real-World Datasets. A note regarding */M-SBM: This designation pertains to results obtained by integrating the originalreal-world network with an additional layer graph, constructed by randomlyshuffling the edges between the known label nodes in the original real-worldnetwork.Table 5.3 presents the results of different graph embedding methods onthese two real-world datasets. All graph embedding methods have an ac-curacy improvement when using our proposed approach, with GNN-basedmethods exhibiting a larger enhancement. Our comprehensive evaluationacross these real-world datasets and the incorporation of label-assistive GNNsdemonstrate the robustness and potential of our approach in addressing com-plex graph-based tasks.645.3. M-SBM DATA AUGMENTATION FOR UNSUPERVISED LEARNING5.3 M-SBM Data Augmentation forUnsupervised LearningIn the context of unsupervised learning, the influence of side informationon community detection thresholds can also be explored, similar to whatwas observed in semi-supervised learning. We consider the scenario wherethe training data has multilayers that are highly consistent and provide com-plementary information about the network’s community structure. This canserve as another type of side information. To explore this further, we con-sidered a specific case of M-SBM for investigation.Let {G1 ∼ SBM1 (n, 4, p1, q2)}, {G2 ∼ SBM2 (n, 2, p2, q2)} be two-layerM-SBM , where SNR(G1) < 1 and SNR(G2) ≫ 1. We assume that thecommunity in G1 and G2 is consistent. This means that each communityin G2 consistently contains two communities from G1. As shown in Figure5.4, G1 serves as the main layer with four communities, and the connectionswithin communities are not very dense. On the other hand, G2, serving asan additional layer, has two communities that can be exactly recovered.Let V1 and V2 represent the nodes of the two communities obtained byexact recovery in G2. Then, we choose node u ∈ V1 and v ∈ V2 to formE(Vs) = {(u, v)}. In the proposed approach, instead of using G1(V,E) asthe training data, we use an augmented graph G¯1(V,E′), which is defined asfollow:V(G¯1)= V(G¯1), E(G¯)= E(G¯)− E(Vs)In this scenario, we have a graph G2 where there are two identifiable largecommunities, but smaller communities within it are challenging to detect.Therefore, we started by detecting the larger region and then reduced theedges between them in the G2. This adjustment made it possible to detectthe smaller communities in G1.Table 5.4 presents the results of simulated experiments using VGAE.655.3. M-SBM DATA AUGMENTATION FOR UNSUPERVISED LEARNINGFigure 5.4: The diagram of the two-layer M-SBM.SNR(G1) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 2.0 4.0G1 0.262 0.262 0.265 0.297 0.290 0.272 0.305 0.320 0.352 0.310 0.475 0.845M-SBM({G1, G2}, 2) 0.515 0.540 0.545 0.592 0.593 0.612 0.657 0.665 0.673 0.707 0.882 0.981Table 5.4: Experiment of VGAE in the Unsupervised Learning Settings.665.4. SUMMARY OF M-SBM DATA AUGMENTATIONThe graphs used in experiments are {G1 ∼ SBM(400, 4, p1, q1)} and {G2 ∼SBM(400, 2, p2, q2)}. Their nodes and the community labels of the twographs are consistent. The first row shows the results when G1 is used as asole graph in unsupervised learning settings with different SNRs. The secondrow displays the results of experiments where G2 is used as side informationto augment G1. It can be observed that this approach significantly improvesthe accuracy of graph embedding methods in unsupervised learning settings.5.4 Summary of M-SBM DataAugmentationIn summary, Chapter 5 has introduced the concept of a multilayer stochas-tic block model (M-SBM) and demonstrated how the integration of side in-formation can improve community recoverability in both semi-supervised andunsupervised learning settings.Our experiments have shown that the M-SBM data augmentation methodusing known labels in a single-layer SBM significantly enhances the perfor-mance of all graph embedding methods in semi-supervised learning settings.This improvement is especially notable for GNN-based methods, with themost noticeable enhancement around SNR = 1. Furthermore, by incor-porating partial community structure information from an additional layer,we have improved the effectiveness of embedding methods in unsupervisedlearning settings.67Chapter 6Conclusion and Future WorkIn conclusion, this thesis provides a comprehensive exploration of theeffectiveness of graph embedding methods for node classification. We exper-imentally confirm the phase transition in the recoverability of communitystructure in SBMs. Despite the widely held belief that GNNs are powerfullearning models for graph data [36], our experiments show that they maynot necessarily outperform shallow embedding methods and traditional al-gorithms for node classification. Notably, GNN-based embedding methodsface challenges in using information from node labels, particularly in semi-supervised learning scenarios with a relatively weak SNR in the graph.To address these challenges, we propose a technique for multilayer dataaugmentation that enhances GNN-based embedding methods in semi-supervisedlearning. By using the adjacency information among the known labels toconstruct an additional layer, our methods demonstrate significant improve-ments in the capabilities and performance of GNN-based models. Syntheticdata from SBMs and real-world datasets validate the efficacy of our pro-posed techniques. Furthermore, we discuss the potential of incorporatingother types of side information into GNNs in the setting of unsupervisedlearning, particularly in multiplex network data.The work in this thesis also has some limitations. The first is the lackof in-depth theoretical support, especially when the number of communitiesis larger than two (k > 2) in semi-supervised learning settings, even thoughour experiments suggest that the detection threshold is similar to when thenumber of communities is equal to two (k = 2). Another limitation is that theexperimental data used has a relatively small number of graph nodes, which68may not fully capture the complexities of larger networks. Additionally, thereis a lack of experimental evaluations for cases where the M-SBM has morethan two layers (L > 2).Addressing these limitations in future research will be crucial. Our futurework can start by addressing these limitations. Additionally, exploring theintegration of other types of side information into GNNs presents a promisingdirection for enhancing the performance and applicability of graph embed-ding methods. We can also experiment with the practical application of themethods discussed in Section 5.3 in unsupervised learning settings, such astheir application in social networks.69Bibliography[1] Emmanuel Abbe. Community detection and stochastic block mod-els: Recent developments. Journal of Machine Learning Research,18(177):1–86, 2018. → pages 1, 2, 17, 18, 19, 20, 21, 22, 23, 41, 57[2] Emmanuel Abbe, Afonso S. Bandeira, and Georgina Hall. Exact recov-ery in the stochastic block model. IEEE Transactions on InformationTheory, 62(1):471–487, 2016. → pages 22[3] Emmanuel Abbe and Colin Sandon. Community detection in generalstochastic block models: Fundamental limits and efficient algorithmsfor recovery. In 2015 IEEE 56th Annual Symposium on Foundations ofComputer Science, pages 670–688, 2015. → pages 2, 21[4] Emmanuel Abbe and Colin Sandon. Detection in the stochastic blockmodel with multiple clusters: proof of the achievability conjectures,acyclic bp, and the information-computation gap. arXiv preprintarXiv:1512.09080, 2015. → pages 23[5] Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josi-fovski, and Alexander J Smola. Distributed large-scale natural graphfactorization. In Proceedings of the 22nd International World Wide WebConference (WWW 2013), 2013. → pages 14[6] Arash Amini, Marina Paez, and Lizhen Lin. Hierarchical StochasticBlock Model for Community Detection in Multiplex Networks. BayesianAnalysis, 19(1):319 – 345, 2024. → pages 5570Bibliography[7] David Arthur and Sergei Vassilvitskii. K-means++: The advantagesof careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAMSymposium on Discrete Algorithms, page 1027–1035, USA, 2007. Societyfor Industrial and Applied Mathematics. → pages 7[8] Pierre Baldi. Autoencoders, unsupervised learning, and deep architec-tures. In Proceedings of ICML Workshop on Unsupervised and TransferLearning, volume 27 of Proceedings of Machine Learning Research, pages37–49, Bellevue, Washington, USA, 02 Jul 2012. PMLR. → pages 33[9] James C. Bezdek and Nikhil R. Pal. Cluster validation with generalizeddunn’s indices. In Proceedings 1995 the 2nd New Zealand InternationalTwo-Stream Conference on Artificial Neural Networks and Expert Sys-tems, pages 190–193, 1995. → pages 7[10] Noureddine Bouhmala. How good is the euclidean distance metric for theclustering problem. In the 5th IIAI International Congress on AdvancedApplied Informatics (IIAI-AAI), pages 312–315, 2016. → pages 7[11] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Acomprehensive survey of graph embedding: Problems, techniques, andapplications. IEEE Transactions on Knowledge and Data Engineering,30(09):1616–1637, sep 2018. → pages 1, 10, 12, 13[12] David Carmel, Naama Zwerdling, Ido Guy, Shila Ofek-Koifman, Na-dav Har’el, Inbal Ronen, Erel Uziel, Sivan Yogev, and Sergey Chernov.Personalized social search based on the user’s social network. In Pro-ceedings of the 18th ACM Conference on Information and KnowledgeManagement, CIKM ’09, page 1227–1236, New York, NY, USA, 2009.Association for Computing Machinery. → pages 1[13] Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community de-tection with line graph neural networks. In the 7th International Confer-71Bibliographyence on Learning Representations, ICLR 2019, New Orleans, LA, USA,May 6-9, 2019. OpenReview.net, 2019. → pages 2[14] Jiangfei Cheng and Li Zhang. Jaccard coefficient-based bi-clusteringand fusion recommender system for solving data sparsity. In Advancesin Knowledge Discovery and Data Mining, pages 369–380, Cham, 2019.Springer International Publishing. → pages 7[15] Kyunghyun Cho, Bart van Merrie¨nboer, Caglar Gulcehre, Dzmitry Bah-danau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learningphrase representations using RNN encoder–decoder for statistical ma-chine translation. In Proceedings of the 2014 Conference on EmpiricalMethods in Natural Language Processing (EMNLP), pages 1724–1734,Doha, Qatar, October 2014. Association for Computational Linguistics.→ pages 15[16] Resul Das and Mucahit Soylu. A key review on graph data science:The power of graphs in scientific studies. Chemometrics and IntelligentLaboratory Systems, 240:104896, 2023. → pages 1[17] Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and AlessandroProvetti. Generalized louvain method for community detection in largenetworks. In the 11th International Conference on Intelligent SystemsDesign and Applications, pages 88–93, 2011. → pages 9[18] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zde-borova´. Asymptotic analysis of the stochastic block model for modularnetworks and its algorithmic applications. Phys. Rev. E, 84:066106, Dec2011. → pages 2, 22[19] Benoit Donnet and Timur Friedman. Internet topology discovery: asurvey. IEEE Communications Surveys Tutorials, 9(4):56–69, 2007. →pages 572Bibliography[20] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, ThomasLaurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neu-ral networks. Journal of Machine Learning Research, 24(43):1–48, 2023.→ pages 2[21] P. Erdo¨s and A. Re´nyi. On random graphs i. Publicationes MathematicaeDebrecen, 1959. → pages 18[22] Mohammad Esmaeili and Aria Nosratinia. Semi-supervised node classi-fication by graph convolutional networks and extracted side information.arXiv preprint arXiv:2009.13734, 2020. → pages 3[23] Santo Fortunato. Community detection in graphs. Physics Reports,486(3):75–174, 2010. → pages 8[24] Edward B. Fowlkes and Colin L. Mallows. A method for comparing twohierarchical clusterings. Journal of the American Statistical Association,78(383):553–569, 1983. → pages 7[25] Julia Gaudio, Miklos Z Racz, and Anirudh Sridhar. Exact communityrecovery in correlated stochastic block models. In Conference on Learn-ing Theory, pages 2183–2241. PMLR, 2022. → pages 54[26] Palash Goyal and Emilio Ferrara. Graph embedding techniques, appli-cations, and performance: A survey. Knowledge-Based Systems, 151:78–94, 2018. → pages 1, 12[27] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learningfor networks. In Proceedings of the 22nd ACM SIGKDD internationalconference on Knowledge Discovery and Data Mining, pages 855–864,2016. → pages xi, 14, 27, 39[28] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representa-tion learning on large graphs. Advances in Neural Information Process-ing Systems, 30, 2017. → pages 2, 15, 16, 32, 3973Bibliography[29] William L. Hamilton. Graph representation learning. Synthesis Lectureson Artificial Intelligence and Machine Learning, 14(3):1–159. → pages5, 6[30] John A. Hartigan and Manchek A. Wong. Algorithm as 136: A k-meansclustering algorithm. Journal of the Royal Statistical Society. Series C(Applied Statistics), 28(1):100–108, 1979. → pages 7[31] Simon Heimlicher, Marc Lelarge, and Laurent Massoulie´. Commu-nity detection in the labelled stochastic block model. arXiv preprintarXiv:1209.2910, 2012. → pages 2[32] Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt.Stochastic blockmodels: First steps. Social Networks, 5(2):109–137,1983. → pages 2, 18[33] Fadhl Hujainah, Rohani Bakar, Abdullah Nasser, Basheer Al-haimi, andKamal Zamli. Srptackle: A semi-automated requirements prioritisationtechnique for scalable requirements of software system projects. Infor-mation and Software Technology, 131:106501, 03 2021. → pages 8[34] Tatsuro Kawamoto, Masashi Tsubaki, and Tomoyuki Obuchi. Mean-field theory of graph neural networks in graph partitioning. Advancesin Neural Information Processing Systems, 31, 2018. → pages 2[35] Kamran Khan, Saif Ur Rehman, Kamran Aziz, Simon Fong, andS. Sarasvady. Dbscan: Past, present and future. In The Fifth Interna-tional Conference on the Applications of Digital Information and WebTechnologies, pages 232–238, 2014. → pages 7[36] Thomas N Kipf and Max Welling. Semi-supervised classification withgraph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.→ pages 2, 15, 16, 30, 39, 6874Bibliography[37] Thomas N Kipf and Max Welling. Variational graph auto-encoders.arXiv preprint arXiv:1611.07308, 2016. → pages xi, 2, 33, 34, 35, 36,39[38] D-S Lee, Juyong Park, KA Kay, Nicholas A Christakis, Zoltan N Olt-vai, and AL Baraba´si. The implications of human metabolic networktopology for disease comorbidity. Proceedings of the National Academyof Sciences, 105(29):9880–9885, 2008. → pages 5[39] Kangjie Li and Wenjing Ye. Semi-supervised node classification viagraph learning convolutional neural network. Applied Intelligence,52(11):12724–12736, sep 2022. → pages 11[40] Zewen Li, Fan Liu, Wenjie Yang, Shouheng Peng, and Jun Zhou. Asurvey of convolutional neural networks: Analysis, applications, andprospects. IEEE Transactions on Neural Networks and Learning Sys-tems, 33(12):6999–7019, 2022. → pages 15[41] La´szlo´ Lova´sz. Large Networks and Graph Limits. Colloquium Publica-tions, 2012. → pages 12[42] Guixiang Ma, Nesreen K Ahmed, Theodore L Willke, and Philip S Yu.Deep graph similarity learning: A survey. Data Mining and KnowledgeDiscovery, 35:688–725, 2021. → pages 38[43] Yao Ma, Suhang Wang, Charu C. Aggarwal, Dawei Yin, and Jil-iang Tang. Multi-dimensional graph convolutional networks. ArXiv,abs/1808.06099, 2018. → pages 6[44] Toma´s Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficientestimation of word representations in vector space. In The 1st Interna-tional Conference on Learning Representations, 2013. → pages 2575Bibliography[45] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering:Analysis and an algorithm. In Advances in Neural Information Process-ing Systems, volume 14. MIT Press, 2001. → pages 7, 9[46] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: onlinelearning of social representations. In Proceedings of the 20th ACMSIGKDD international conference on Knowledge Discovery and DataMining, KDD ’14. ACM, August 2014. → pages 14, 25, 26, 39[47] Pascal Pons and Matthieu Latapy. Computing communities in largenetworks using random walks. In Computer and Information Sciences- ISCIS 2005, pages 284–293, Berlin, Heidelberg, 2005. Springer BerlinHeidelberg. → pages 9[48] Miklos Racz and Anirudh Sridhar. Correlated stochastic block mod-els: Exact graph matching with applications to recovering communities.Advances in Neural Information Processing Systems, 34:22259–22273,2021. → pages 3, 55[49] Reuven Y. Rubinstein and Dirk P. Kroese. Simulation of Discrete-EventSystems, chapter 3, pages 91–106. John Wiley Sons, Ltd, 2016. → pages45[50] Junda Sheng and Thomas Strohmer. Semi-supervised clustering ofsparse graphs: Crossing the information-theoretic threshold. arXivpreprint arXiv:2205.11677, 2022. → pages 3, 49[51] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, andQiaozhu Mei. Line: Large-scale information network embedding. In Pro-ceedings of the 24th international conference on world wide web, pages1067–1077, 2015. → pages 28, 29, 30, 39[52] Vincent A. Traag, Ludo Waltman, and Nees Jan Van Eck. From louvain76Bibliographyto leiden: guaranteeing well-connected communities. Scientific Reports,2019. → pages 9[53] Xiao Wang, Deyu Bo, Chuan Shi, Shaohua Fan, Yanfang Ye, andPhilip S. Yu. A survey on heterogeneous graph embedding: Methods,techniques, applications and sources. IEEE Transactions on Big Data,9:415–436, 2020. → pages 6[54] Margaret Mary Wood. The Stranger a Study in Social Relationships.Columbia University Press, New York Chichester, West Sussex, 1934.→ pages 5[55] Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, andHuan Liu. Graph learning: A survey. IEEE Transactions on ArtificialIntelligence, 2(2):109–127, 2021. → pages 7[56] Wang Shiping Dai Yuanfei Guo Xiao, Shunxin and Wenzhong. Graphneural networks in node classification: survey and evaluation. MachineVision and Applications, 2021. → pages 11[57] Rui Xu and D. Wunsch. Survey of clustering algorithms. IEEE Trans-actions on Neural Networks, 16(3):645–678, 2005. → pages 7[58] Ka Yee Yeung and Walter L. Ruzzo. Principal component analysis forclustering gene expression data. Bioinformatics, 17(9):763–774, 09 2001.→ pages 7[59] Xiang Yue, Zhen Wang, Jingong Huang, Srinivasan Parthasarathy, So-heil Moosavinasab, Yungui Huang, Simon M Lin, Wen Zhang, PingZhang, and Huan Sun. Graph embedding on biomedical networks: meth-ods, applications and evaluations. Bioinformatics, 36(4):1241–1251, 102019. → pages 1, 677Bibliography[60] Wayne Zachary. An information flow model for conflict and fission insmall groups1. Journal of anthropological research, 33, 11 1976. → pages9[61] Yi Zhang, Miaomiao Li, Siwei Wang, Sisi Dai, Lei Luo, En Zhu, Huiy-ing Xu, Xinzhong Zhu, Chaoyun Yao, and Haoran Zhou. Gaussianmixture model clustering with incomplete data. ACM Transactions onMultimedia Computing, Communications, and Applications (TOMM),17(1s):1–14, 2021. → pages 7[62] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang,Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graphneural networks: A review of methods and applications. AI Open, 1:57–81, 2020. → pages xi, 15, 1678
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Gao, Yong
The effectiveness of GNNs for node classification : the significance of side information
Text