: Unsupervised Inductive Edgeless Network Embedding

Yong-Min Shin, Student Member, IEEE, Cong Tran, Student Member, IEEE,

Won-Yong Shin, Senior Member, IEEE,  and  Xin Cao
Y.-M. Shin and W.-Y. Shin are with the School of Mathematics and Computing (Computational Science and Engineering), Yonsei University, Seoul 03722, Republic of Korea (e-mail: {jordan3414, wy.shin}@yonsei.ac.kr).
C. Tran is with the Department of Computer Science and Engineering, Dankook University, Yongin 16890, Republic of Korea, and also with the Machine Intelligence & Data Science Laboratory, Yonsei University, Seoul 03722, Republic of Korea (e-mail: contran@ieee.org).
X. Cao is with the School of Computer Science and Engineering, The University of New South Wales, Sydney 2052, Australia (e-mail: xin.cao@unsw.edu.au).

(Corresponding author: Won-Yong Shin.)

We study the problem of embedding edgeless nodes such as users who newly enter the underlying network, while using graph neural networks (GNNs) widely studied for effective representation learning of graphs thanks to its highly expressive capability via message passing. Our study is motivated by the fact that existing GNNs cannot be adopted for our problem since message passing to such edgeless nodes having no connections is impossible. To tackle this challenge, we propose , a new framework that enables GNNs to generate node embeddings even for edgeless nodes through unsupervised inductive learning. Specifically, we start by constructing a $k$-nearest neighbor graph ($k$NNG) based on the similarity of node attributes to replace the GNN's computation graph defined by the neighborhood-based aggregation of each node. As our main contributions, the known network structure is used to train model parameters, while a new loss function is established using energy-based learning in such a way that our model learns the network structure. For the edgeless nodes, we inductively infer embeddings for the edgeless nodes by using edges via $k$NNG construction as a computation graph. By evaluating the performance of various downstream machine learning (ML) tasks, we empirically demonstrate that  consistently outperforms state-of-the-art methods of inductive network embedding. Moreover, our findings corroborate the effectiveness of  in judiciously combining the replaced computation graph with our newly designed loss. Our framework is GNN-model-agnostic; thus, GNN models can be appropriately chosen according to ones' needs and ML tasks.

Computation graph, edgeless node, graph neural network (GNN), inductive learning, network embedding.

§ INTRODUCTION

GRAPHS are a ubiquitous way to organize a diverse set of real-world data such as social networks, citation networks, molecular graph structures, and recommender systems—all of these domains can be readily modeled as graphs.[In the following, we use the terms "graph" and "network" interchangeably.] Moreover, nodes in graphs are often associated with rich attribute information <cit.>, which motivates researchers to leverage both structural and attribute information for various downstream analyses including node classification <cit.>, link prediction <cit.>, and community detection <cit.>. However, conducting these analyses poses several practical challenges such as the high computational complexity due to combinatorial computation steps of most graph processing/analysis algorithms and the extremely high dimensionality in an irregular form <cit.>.

To overcome these problems, network embedding, also known as network representation learning, has gained increasing attention for the past few years as a fundamental tool for analyzing networks <cit.>. Network embedding learns a mapping from each node in a graph to a low-dimensional vector in an embedding space while preserving intrinsic network properties, resulting in an efficient representation of the graph in the sense of solving downstream machine learning (ML) problems with little or no modification. Recently, for networks in which node attributes are available, so-called attributed networks,  graph neural networks (GNNs) have been widely studied as a powerful means to extract useful features from such networks while performing network embedding or solving other graph mining problems <cit.>. As a deep learning-based approach for adopting neural networks as a building block, GNNs are known to have high expressive capability via message passing in effectively learning network representations <cit.> and thus to be a successful model for performing various downstream ML tasks.

Nevertheless, existing network embedding models including GNNs face inherent limitations in applications to real-world scenarios where underlying networks are acquired incompletely with some edgeless nodes whose topological information is not available, i.e., nodes having no connections <cit.> (see Fig. <ref>). In real-world networks extracted from various systems, there are several sources of incompleteness for the network structure. First, in co-authorship networks, some papers may be contributed by single (or isolated) authors, creating nodes without any connections to others. For example, a statistical analysis showed that 15.48% of the published papers in the field of information retrieval during the period of 2001–2008 were single-authored papers <cit.>. Second, in other real-world networks including social networks, some users may completely hide their friendships due to privacy settings specified by such users <cit.>. As an example, a demographic analysis of Facebook users in New York City in June 2011 demonstrated that 52.6% of the users hid the lists of Facebook friends <cit.>. Despite the absence of connectivity information associated with such hidden or new nodes, it would be still possible to perform downstream graph mining tasks when the attribute information of nodes (e.g., authors' biographical features and research interests) is available since such information is much easier to acquire through publicly available sources such as Google Scholar. Even if the analysis of networks harnessing node attributes has emerged as another research area, little attention has been paid to the embedding technique for more challenging yet practical situations in which an underlying attributed network is incomplete with edgeless nodes. Although there are only a few attempts (e.g., Graph2Gauss <cit.> and DEAL <cit.>) to solve the aforementioned problem in the context of inductive link prediction, the performance of other downstream tasks has been unexplored yet. Moreover, there are still potential future directions towards embedding methodology since embedding models in prior studies <cit.> were built upon a rather simple multi-layer perceptron (MLP).

Applications of our  framework to a social network with edgeless nodes.

§.§ Main Contributions

In this paper, we consider a practical scenario of attributed networks in which a portion of nodes have no available edges, i.e., topological information. In this attributed network model, we study the problem of embedding such edgeless nodes (e.g., users who newly enter the underlying network), which should be judiciously handled along with downstream tasks as long as network embedding is concerned. More specifically, we are interested in inductively and unsupervisedly discovering embeddings of edgeless nodes by effectively designing an entirely new GNN framework.

Motivated by the wide applications of GNNs to attributed networks and their generalization abilities <cit.>, a natural question arising is: "Will existing GNN models be applicable and beneficial for solving the problem of inductive edgeless network embedding?" To answer this question, we present , a novel framework that enables GNNs to generate node embeddings even for edgeless nodes through effective inductive learning. However, developing our framework basically faces key research challenges. First, existing GNNs cannot be adopted for our study since message passing to new edgeless nodes having no connections is impossible. As illustrated in Fig. <ref>, the edgeless nodes (the black filled nodes) can never benefit from existing GNN models, as there are no connections to the underlying network. To overcome this problem, we start by utilizing a $k$-nearest neighbor graph ($k$NNG) constructed based on the similarity of node attributes as a means to replace the GNN's original computation graph that is defined by the neighborhood-based aggregation of each node. This allows us to construct another computation graph in a different manner by creating edges to which edgeless nodes are incident using the attribute information. We note that this new kNNG is generated under the homophily assumption that adjacent nodes in the underlying network tend to have similar node attributes. Second, more importantly, this graph construction imposes another research on how to effectively generate embeddings using this new computational graph along with the GNN architecture while still taking advantage of the topological information. To tackle this challenge, as our basic idea, we make use of the known network structure to train model parameters. In particular, we newly establish a loss function built upon the energy-based learning <cit.>, which has been widely used as a general framework for both probabilistic and non-probabilistic approaches to learning. Specifically, our new loss function generally exploits not only the first-order proximity of node pairs but also higher-order positive relations in learning node embeddings from the underlying network structure; in our study, we confine our loss term related to learning positive relations to encode the second-order proximities since it is sufficient to guarantee satisfactory performance. The model based on our loss function is unsupervisedly learned since it does not necessitate node labels. Due to the fact that our  framework is based on the inductive learning, for edgeless nodes, it is possible to infer embeddings without retraining by using edges via construction of another computation graph including the edgeless nodes.

To validate the superiority of the proposed  framework, we comprehensively perform empirical evaluations for various real-world attributed networks. Experimental results show that our framework consistently outperforms state-of-the-art inductive network embedding approaches for almost all cases when we carry out three downstream ML tasks such as link prediction, node classification, and community detection. Interestingly, it is observed that simply adopting the existing GNN's loss functions in the newly constructed $k$NNG indeed fails to guarantee satisfactory performance and is even far inferior to naïve baseline methods employing node attributes only. This implies that our newly designed loss function plays a very crucial role to successfully infer embeddings of the edgeless nodes by bridging the structural and attribute information. Our experimental results also demonstrate the robustness of our  framework to a more difficult and challenging situation where a large portion of node attributes are missing. Moreover, we investigate the impact of hyperparameters by finding that both the second-order proximity loss term and the parameter controlling negative node pairs in our loss are vital for the training model to infer high-quality embeddings. Additionally, we analyze and empirically validate the computational complexity of the  framework.

It is worth noting that our framework is GNN-model-agnostic and thus different GNN architectures can be appropriately chosen according to ones' needs and ML tasks. Furthermore, we are capable of embedding edgeless nodes through the inductively learned model in the inference phase; this is possible by generating edges via simple $k$NNG construction, rather than designing another learning module for graph construction that leads to an increase of computation with a potentially sophisticated training procedure.

The main technical contributions of this paper are five-fold and summarized as follows:

* We propose , a novel unsupervised inductive network embedding framework for attributed networks with edgeless nodes.

* We formalize our problem by adopting GNN models yet introducing new design paradigms such as the $k$NNG-based computation graph construction and the network structure learning from our energy-based new loss function.

* We validate our proposed  framework through extensive experiments using five real-world attributed networks.

* We analyze and empirically show the computational complexity of .

Our methodology sheds light on how to effectively discover embeddings even when no topological structure of some nodes is available.

§.§ Organization and Notations

The remainder of this paper is organized as follows. In Section <ref>, we review significant studies that are related to our work. In Section <ref>, we explain the methodology of our study, including the problem definition and an overview of our  framework. Section <ref> describes implementation details of the proposed framework. Comprehensive experimental results are discussed in Section <ref>. Finally, we provide a summary and concluding remarks in Section <ref>.

Notation     Description

$G$     Given attributed network

0pt9pt$\mathcal{V}$     Set of nodes in $G$

0pt9pt$\mathcal{V}'$     Set of edgeless nodes

0pt9pt$\mathcal{V}^{\textnormal{all}}$     $\mathcal{V} \cup \mathcal{V}'$

0pt9pt$\mathcal{E}$     Set of edges in $G$

0pt9pt$\mathcal{X}$     Set of attributes of nodes in $\mathcal{V}$

0pt9pt$\mathcal{X}'$     Set of attributes of nodes in $\mathcal{V}'$

0pt9pt$\mathcal{X}^{\textnormal{all}}$     $\mathcal{X} \cup \mathcal{X}'$

0pt9pt$G_{k\textnormal{NN}}$     $k$NNG constructed from $\mathcal{X}$

0pt9pt$G_{k\textnormal{NN}}^{\textnormal{all}}$     $k$NNG constructed from $\mathcal{X}^{\textnormal{all}}$

0pt9pt$\mathbf{Z}$     Embedding for the nodes in $\mathcal{V}$

0pt9pt$\mathbf{Z}'$     Embedding for the nodes in $\mathcal{V}'$

0pt9pt$\mathbf{Z}^{\textnormal{all}}$     Embedding for the nodes in $\mathcal{V}^{\textnormal{all}}$

0pt9pt$\theta$     Parameter of the GNN model

Summary of notations.

Table <ref> summarizes the notation that is used in this paper. This notation will be formally defined in the following sections when we present our methodology and the technical details.

§ RELATED WORK

The framework that we propose in this study is related to three broader topics of research, namely unsupervised network embedding, GNNs, and applications of $k$NN to GNNs.

Unsupervised network embedding. Unsupervised learning of node embeddings has been widely studied. DeepWalk <cit.> and node2vec <cit.> were developed based on the Skip-gram model <cit.>, where truncated random walks are used to sample positive pairs of nodes. LINE <cit.> was designed by formulating optimized objective functions to explicitly capture the first-order and second-order proximities. GraRep <cit.> employed matrix factorization to capture the $h$-step relationship between each node and its $h$-step neighbors in a graph with different values of $h$. Deep autoencoder-based models for learning node representations were also developed in <cit.>. Furthermore, a significant amount of progresses have been made toward network embeddings in networks with node attributes, so-called attributed networks <cit.>. In TADW <cit.>, text attributes were incorporated into matrix factorization techniques. DANE <cit.> was designed under a deep autoencoder model that leverages the network structure and node attributes. Graph2Gauss <cit.> adopted an MLP architecture with node attributes while using a rank-based loss. More recently, DEAL <cit.> was modeled by constructing both attribute-oriented and structure-oriented encoders and then aligning two types of embeddings via the two encoders. We note that, in <cit.>, the problem of inductive link prediction was addressed when the network structure of new nodes is unknown.

GNNs. GNN models in attributed networks have drawn considerable attention due to their state-of-the-art performance on various ML tasks, where representation vectors of neighboring nodes are aggregated recursively through the message passing mechanism. As the most influential study, GCN <cit.> originally presented an effective network representation model that naturally combines the network structure and node attributes in the learning process. Instead of aggregating all neighbors in the aggregation process (e.g., GCN), in GraphSAGE <cit.>, more delicate aggregation methods such as average, max pooling, and long short-term memory (LSTM) were developed along with neighborhood sampling. GAT <cit.> was presented by synthesizing self-attention layers, where different importances are assigned to neighboring nodes. By analyzing the expressive capability of popular GNN models, a simple architecture exhibiting a further representational power was designed in <cit.>. JK-Nets <cit.> was designed by using intermediate layer-aggregation mechanisms for better representation learning. DGL <cit.> utilized a mutual information maximization approach for training GNNs. Recent attempts include not only efficient designs of GNN models in <cit.> but also designs of very deep GCNs for a further performance boost in <cit.>.

Applications of $k$NN to GNNs. $k$NN-based similarity has been widely studied to solve various downstream ML tasks from the image domain (e.g., image denoising <cit.>) to the graph domain. In particular, for ML tasks on graphs, several studies were recently carried out to take advantage of $k$NNG construction alongside GNNs. To perform semi-supervised node classification, AM-GCN <cit.> proposed a multi-channel GCN model by learning node embeddings based on not only the network structure but also the $k$NNG generated from node attributes. Another application of $k$NNG construction to GCNs includes the case where the network structure is incomplete <cit.>; Bernoulli parameters used to infer the network structure along with all possible edges were initialized via $k$NNG construction. VGCN <cit.> adopted $k$NNG construction as a prior over networks for variational inference in the absence of the network structure.

Despite these contributions, it has been largely underexplored in the literature how to exploit the power of GNNs in the context of structure-unaware network embedding, i.e., edgeless network embedding. Although GNNs are built upon message passing mechanisms that are shown to flexibly model complex interactions among nodes, they cannot be straightforwardly employed to solve our problem since no information can be passed from/to the edgeless nodes. Moreover, recent studies on inductive link prediction in <cit.>, <cit.> are limited only to MLP architectures and thus do not take advantage of potentials of rather powerful GNNs. As opposed to our work, applications to other downstream tasks such as node classification and community detection were not studied in <cit.>.

§ METHODOLOGY

We first describe our network model with basic settings and formulate the problem. Then, we explain an overview of the proposed  framework as a solution to the problem of inductive edgeless network embedding.

§.§ Network Model and Basic Settings

Let us denote a given network as $G = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is set of $N$ nodes and $\mathcal{E}$ is the set of edges between pairs of nodes in $\mathcal{V}$. We assume $G$ to be an undirected unweighted attributed network without self-loops or repeated edges. We define $\mathbf{x}_{i} \in \mathbb{R}^{f}$ as the attribute vector of node $v_{i} \in \mathcal{V}$, and $\mathcal{X} = \{\mathbf{x}_{1}, \cdots,\mathbf{x}_{N}\}$ as the set of node attribute vectors, where $f$ is the number of attributes per node.

In the inductive learning setting, we would like to newly introduce a set of $M$ edgeless nodes, denoted as $\mathcal{V}'$, which has not been seen yet during the training phase.[In our study, although the existence of edgeless nodes is known beforehand, we treat them as newly given since existing GNN models cannot provide a way of integrating the edgeless nodes into the underlying network.] Each of these $M$ nodes has an associated attribute vector $\mathbf{x}'_{i} \in \mathbb{R}^{f}$ for $i\in\{1,\cdots,M\}$. We denote the set of attributes of these $M$ nodes as $\mathcal{X}' = \{\mathbf{x}'_{1}, \cdots,\mathbf{x}'_{M}\}$. However, the network structure of these $M$ nodes in $\mathcal{V}'$ is unavailable, which is a feasible scenario (e.g., a co-authorship network, where some nodes are single-authored papers). In other words, two types of edges, including the edges connecting two nodes in $\mathcal{V}'$ and the edges connecting one node in $\mathcal{V}$ and another node in $\mathcal{V}'$, are not given beforehand, as in <cit.>. In this context, these nodes in $\mathcal{V}'$ are the so-called edgeless nodes.

§.§ Problem Definition

Given a network $G = (\mathcal{V},\mathcal{E})$ and two sets of node attributes, $\mathcal{X}$ and $\mathcal{X}'$, inductive edgeless network embedding aims to discover embeddings of edgeless nodes in such a way that the embedding vectors unsupervisedly encode the unseen structural information.

§.§ Overview of Our  Framework

In this subsection, we explain our methodology along with the overview of the proposed  framework. We start by stating that GNNs basically operate on a computation graph $G_c$, which aggregates the neighbors of each node and thus determines the flow of information in the message passing mechanism <cit.>. The typical choice of $G_{c}$ is the underlying network itself, i.e., $G_{c} = G$. However, unlike prior studies on GNN models, when we turn our attention to edgeless nodes in $\mathcal{V}'$, we fail to compute their embeddings due to the fact that no topological structure of the edgeless nodes is available and thus no information can be exchanged via the typical computation graph $G_{c}$.

Schematic overview of our  framework.

To overcome this problem, we introduce an alternative approach to constructing the GNN's computation graph $G_c$. More specifically, we are interested in constructing $G_c$ such that edges for all nodes in both $\mathcal{V}$ and $\mathcal{V}'$ are created using the set of node attributes in a consistent fashion. To this end, for each $v \in \mathcal{V}$, we construct a $k$NNG, denoted as $G_{k\textnormal{NN}}$, by forming edges from the top-$k$ similar nodes in $\mathcal{V}\setminus\{v\}$ so that $G_c=G_{k\textnormal{NN}}$ (refer to the graph $G_{k\textnormal{NN}}$ in the top blue box of Fig. <ref>). Additionally, we construct $G^{\textnormal{all}}_{k\textnormal{NN}} = (\mathcal{V}^\textnormal{all},\mathcal{E}^{\textnormal{all}}_{k\textnormal{NN}})$, another $k$NNG that is composed of all nodes in $\mathcal{V}^\textnormal{all} = \mathcal{V} \cup \mathcal{V}'$, where $\mathcal{E}^{\textnormal{all}}_{k\textnormal{NN}}$ is the set of associated edges with all the nodes in $\mathcal{V}^{\textnormal{all}}$. Starting from $G_{k\textnormal{NN}}$, we create additional edges by selecting the top-$k$ similar nodes in $\mathcal{V}$ for each node in $\mathcal{V}'$, as illustrated in the bottom blue box of Fig. <ref>.

Note that it is possible to use other methods such as the $\epsilon$-neighborhood graph <cit.> that harness the local neighborhood relationships between data points to construct the GNN's computation graph. Nonetheless, we choose $k$NNG construction since it is a widely applicable methodology that can be realized only using the attribute information of nodes. It is also worth noting that a $k$NNG is constructed by assuming the so-called “homophily principle", the tendency of adjacent nodes to have similar node attributes, which is analogous to the usage of $k$NN in image denoising <cit.> to exploit the self-similarity assumption <cit.>. Such construction enables us to coherently generate all the edges associated with the edgeless nodes in $\mathcal{V}'$.

Now, let us describe the training phase of our  framework. The new computation graph $G_{c} = G_{k\textnormal{NN}}$ and the set of node attributes, $\mathcal{X}$, are fed to a GNN model to calculate embedding vectors for the nodes in $\mathcal{V}$:

\begin{equation}
\label{trainembspace}
\mathbf{Z} = \textsf{GNN}_{\theta}(G_{k\textnormal{NN}}, \mathcal{X}),
\end{equation}

where each row of ${\bf Z}\in \mathbb{R}^{N\times d}$ indicates the embedding of each node in $\mathcal{V}$; $d$ is the dimension of the embedding space; and $\theta$ is the learned model parameters of our .

The core component of  is the optimization of model parameters $\theta$ by establishing a non-straightforward and sophisticated loss function. In our study, we aim at training the GNN model using a new loss function built upon energy-based learning <cit.>, while exploiting not only the first-order proximity of node pairs but also the second-order relations in learning node embeddings from the underlying network structure. In other words, the embedding ${\bf Z}$ is first found by running a GNN model on the constructed $G_{k\textnormal{NN}}$ from the node attributes and is then optimized by leveraging the local network structure of each node (i.e., the multi-hop neighbors as well as direct neighbors) in the underlying network $G$. Hence, our training model based on the new loss function in  learns how to map the node attributes into the structural information, which is the most distinct and prominent characteristic that does not exist in conventional GNN models. The model is trained through unsupervised learning without any node labels. The implementation details of the energy-based loss function will be specified in Section <ref>.

Next, we turn to the inference phase, which inductively finds embeddings for the newly given edgeless nodes in $\mathcal{V}'$. Another computation graph $G_c=G_{k\textnormal{NN}}^{\textnormal{all}}$ and the set of node attributes, $\mathcal{X}^{\textnormal{all}} = \mathcal{X} \cup \mathcal{X}'$, are fed to the trained GNN model to calculate embedding vectors ${\bf Z}^{\textnormal{all}}\in \mathbb{R}^{(N+M)\times d}$ for all the nodes in $\mathcal{V}^{\textnormal{all}}$, including the edgeless nodes, by feedforward computation as follows:

\begin{equation}
\label{testembspace}
\mathbf{Z}^{\textnormal{all}} = \textsf{GNN}_{\theta}(G_{k\textnormal{NN}}^{\textnormal{all}}, \mathcal{X}^{\textnormal{all}}).
\end{equation}

Then, we discover the embeddings $\mathbf{Z}' \in \mathbb{R}^{M\times d}$ only for the edgeless nodes in $\mathcal{V}'$ by selecting the corresponding vectors from ${\bf Z}^\textnormal{all}$.
Finally, we are able to perform various downstream ML tasks using $\mathbf{Z}'$ (i.e., the embedding vectors of the edgeless nodes in $\mathcal{V}'$).

Since our method is GNN-model-agnostic, various GNN models such as <cit.>, <cit.>, <cit.>, <cit.>, <cit.> can be adopted, which will be specified in the next section.

§ PROPOSED  FRAMEWORK

In this section, we  elaborate on our  framework that generates embeddings for edgeless nodes. Our  framework is composed of initialization, model training, and inference phases. The overall procedure of our framework is summarized in Algorithm <ref>.

As one of the main contributions to the design of our framework, we start the initialization phase by constructing two computation graphs $G_{k\textnormal{NN}}$ and $G_{k\textnormal{NN}}^{\textnormal{all}}$ from $\mathcal{X}$ and $\mathcal{X}^{\textnormal{all}}$, respectively, via a function $k$ whose input includes a computation graph to be expanded ($\emptyset$ if none), a set of node attributes, and a given parameter $k$.[For the $k$NNG construction, we adopt the cosine similarity metric <cit.> to evaluate the pairwise similarity between two node attributes. Besides the cosine similarity, other measures such as the heat kernel can be used as well.]

[1]

$G$, $\mathcal{X}$, $\mathcal{X}'$, $\theta$, $k$, $\alpha, num\_epochs$
Initialization:  $G_{k\textnormal{NN}} \leftarrow k\textsf{NNG}(\emptyset, \mathcal{X}, k)$;
$G_{k\textnormal{NN}}^{\textnormal{all}} \leftarrow k\textsf{NNG}(G_{k\textnormal{NN}}, \mathcal{X}', k)$;
$\theta \leftarrow \textnormal{random initialization}$
/* Training phase */
$i=1,\cdots, num\_epochs$
Sample a batch $\mathcal{B}$ from $G$
$\mathcal{B}' \subset \mathcal{B}$
$\mathbf{Z} \leftarrow \textsf{GNN}_{\theta}(G_{k\textnormal{NN}}, \mathcal{X})$
$\mathcal{L} \leftarrow \mathcal{L}_{0} + \alpha \mathcal{L}_{\textnormal{2nd}}$
Update $\theta$ by taking one step of gradient descent
/* Inference phase */
$\mathcal{X}^{\textnormal{all}} \leftarrow \mathcal{X} \cup \mathcal{X}'$
$\mathbf{Z}^{\textnormal{all}} \leftarrow \textsf{GNN}_{\theta}(G_{k\textnormal{NN}}^{\textnormal{all}}, \mathcal{X}^{\textnormal{all}})$
Acquire $\mathbf{Z}'$ from $\mathbf{Z}^{\textnormal{all}}$

The training phase

The inference phase

Illustration of our  framework, which consists of the training phase in which $G_\textnormal{$k$NN}$ and $G$ represent the computation graph and the underlying network, respectively, and the inference phase in which the trained GNN model generates the embedding vectors using another computation graph $G_{k\textnormal{NN}}^\textnormal{all}$ as the input.

Next, we explain the training phase of the GNN model where the learnable model parameters $\theta$ in (<ref>) are initialized (refer to line 1 in Algorithm <ref>). To train our model for $num\_epochs$ training epochs, we use a batch $\mathcal{B}$ per epoch consisting of multiple samples of a node quadruplet $(v_i,v_j,v_n,v_t)$,[For sampling $v_n$, we may follow a sampling strategy using the degree-based unigram noise distribution <cit.>, but we empirically find that using naïve random sampling is sufficient to guarantee the performance.] where $(v_i,v_j) \in \mathcal{E}$, $(v_i,v_n) \notin \mathcal{E}$, and $v_t$ is a two-hop neighbor of $v_i$, as depicted in the underlying network $G$ of Fig. <ref>. More specifically, we first acquire the set of edges (i.e., the connectivity information), $\mathcal{E}$, and then sample two nodes $(v_n,v_t)$ for each $(v_i,v_j)\in\mathcal{E}$ to create a quadruplet $(v_i,v_j,v_n,v_t)$, which yields the batch $\mathcal{B}$. We further subsample mini-batches $\mathcal{B}'\subset\mathcal{B}$ to efficiently train the model (refer to line 5). The sampled quadruplets are fed into the loss function in the training loop along with the calculated embedding $\mathbf{Z} = \textsf{GNN}_{\theta}(G_{k\textnormal{NN}}, \mathcal{X})$ for all nodes in $\mathcal{V}$
(refer to lines 6–7). Before stating our loss function, we describe the GNN model, which is designed to be model-agnostic. To this end, we show a general form of the message passing architecture <cit.>, in which we iteratively update the representation of a node by aggregating representations of its neighbors using two functions, namely AGGREGATE and UPDATE. Formally, at the $p$-th layer of a GNN, $\textnormal{AGGREGATE}^{(p)}_{i}$ aggregates (latent) feature information from the local neighborhood of node $v_i$ in the computation graph $G_c$ as follows:

\begin{equation}
\label{aggregateequation}
\mathbf{m}^{p}_{i} \leftarrow \textnormal{AGGREGATE}^{(p)}_{i}(\{\mathbf{h}_{j}^{p-1}|v_j \in \mathcal{N}_{i} \cup \{v_i\} \}),
\end{equation}

where ${\bf h}^{p-1}_j$ denotes the latent representation vector of node $v_j$ at the $(p-1)$-th layer, $\mathcal{N}_{i}$ indicates the set of neighbor nodes of $v_{i}$ in $G_{c}$, and ${\bf m}_i^p$ is the aggregated information at the $p$-th layer. We note that self-loops are typically added to the computation graph $G_{c}$ for self-information preservation. In the update step, the latent representation at the next layer is produced by using each node and its aggregated information from $\textnormal{AGGREGATE}^{(p)}_{i}$ as follows:

\begin{equation}
\label{updateequation}
\mathbf{h}^{p}_{i} \leftarrow \textnormal{UPDATE}^{(p)}_{i}(v_i,\mathbf{m}^{p}_{i}).
\end{equation}

Additionally, for each node $v_i$, the node attributes ${\bf x}_i \in \mathcal{X}$ are initially used as the representation vector (i.e., $\mathbf{h}^{0}_{i} = \mathbf{x}_{i}$), and the representation at the final layer is the embedding vector ${\bf z}_i \in {\bf Z}$.

Now, let us state how the above two functions AGGREGATE and UPDATE in (<ref>) and (<ref>), respectively, can be specified by several types of GNN models. As the pioneer work of GNN models, GCN <cit.> can be implemented by using

\begin{align}
\textnormal{AGGREGATE}^{(p)}_{i} &= \sum_{j} \dfrac{1}{\sqrt{\textnormal{degree}(i)+1}\sqrt{\textnormal{degree}(j)+1}}\mathbf{h}^{p-1}_{j}\\
\textnormal{UPDATE}^{(p)}_{i} &= \sigma(\mathbf{W}^{p}\cdot\mathbf{m}^{p}_{i}),
\end{align}

where $\textnormal{degree}(\cdot)$ indicates the degree of each node and $\sigma(\cdot)$ is the activation function.
In addition, as one of powerful GNN models, GraphSAGE <cit.> with the mean aggregator can be designed by setting

\begin{align}
\textnormal{AGGREGATE}^{(p)}_{i} &= \dfrac{1}{\textnormal{degree}(i)+1}\sum_{j}\mathbf{h}^{p-1}_{j}\\
\label{graphsageupdate}
\textnormal{UPDATE}^{(p)}_{i} &= \sigma(\mathbf{W}^{p}\cdot \textnormal{concat}(\mathbf{h}^{p-1}_{i}, \mathbf{m}^{p}_{i})),
\end{align}

where $\textnormal{concat}(\cdot,\cdot)$ is the concatenation operation of two input vectors and $\mathbf{W}^{p}$ is a learnable weight matrix. Other popular GNN variants such as GAT <cit.> and GIN <cit.> can also be specified according to their designed function settings. Note that, for GCN and GraphSAGE with $L$ layers, the model parameters $\theta$ can be expressed as the set of weights $\{\mathbf{W}^{p}\}_{p=1,\cdots,L}$.

As our next main contribution, we propose our own loss function for a given mini-batch $\mathcal{B}'$ of quadruplets as follows:

\begin{equation}
\label{mainlossfunction}
\mathcal{L} =  \mathcal{L}_{0} + \alpha \mathcal{L}_{\textnormal{2nd}},
\end{equation}

which is basically built upon the energy-based learning in <cit.> that aims at training a model in the sense of minimizing the energy of node pairs. Here, $\alpha > 0$ is a hyperparameter that balances between the two loss terms in (<ref>). Our loss function enables us to exploit not only the first-order proximity but also the second-order positive relations in learning node representations from the network structure. The first term $\mathcal{L}_0$ in (<ref>) is defined as

\begin{equation}
\label{L0loss}
\mathcal{L}_{0} = \frac{1}{|\mathcal{B}'|}\sum_{(v_i,v_j,v_n,v_t)\in\mathcal{B}'} (E^{+}_{ij} + D_{in} E^{-}_{in}),
\end{equation}

where $\mathcal{B}'$ is the sampled quadruplets $(v_i,v_j,v_n,v_t)$ in which $(v_i,v_j)\in \mathcal{E}$, $(v_i,v_n)\notin \mathcal{E}$, and $v_t$ is a two-hop neighbor of $v_i$ (see Fig. <ref>) (note that $v_i$, $v_j$, and $v_n$ in the quadruplet are used for calculation); $E^{+}_{ij}$ and $E^{-}_{in}$ denote generic energy functions of positive node pairs $(v_i,v_j)$ and negative node pairs $(v_i,v_n)$, respectively; and

\begin{equation}
\label{Dloss}
D_{in} = \exp{\left( \dfrac{\beta}{d_{sp}(v_{i}, v_{n})}\right)}.
\end{equation}

Here, $d_{sp}(v_{i}, v_{n})$ is the shortest path between $v_{i}$ and $v_{n}$, and $\beta > 0$ is a hyperparameter controlling negative node pairs. For long $d_{sp}(v_i,v_n)$, the term $E_{in}^{-}$ corresponding to the energy function of negative node pairs would contribute less to $\mathcal{L}_0$. In our study, as in <cit.>, we set $E_{ij}^{+} = \phi(\textnormal{sim}(\mathbf{z}_{i}, \mathbf{z}_{j}))$ and $E_{in}^{-} = \phi(-\textnormal{sim}(\mathbf{z}_{i}, \mathbf{z}_{n}))$, where $\textnormal{sim}(\cdot)$ is the cosine similarity and $\phi(x) = \gamma^{-1}\log(1+\exp(-\gamma x + b))$ for hyperparameters $\gamma > 0$ and $b \geq 0$. While (<ref>) is a good representation of the pairwise ranking-based loss <cit.> in effectively capturing the network structure, only the first-order proximity for positive node pairs is taken into account. Motivated by the fact that higher-order positive relations of node pairs are also proven to be useful to enhance the performance of network embedding methods <cit.>, we introduce $\mathcal{L}_{\textnormal{2nd}}$ to incorporate the ranking of nodes with respect to the second-order proximity as follows:

\begin{equation}
\label{Lalphaloss}
\mathcal{L}_{\textnormal{2nd}} = \frac{1}{|\mathcal{B}'|}\sum_{(v_i,v_j,v_n,v_t)\in\mathcal{B}'}J_{it}E_{it}^{+},
\end{equation}

where $v_i$ and $v_t$ in the quadruplet are only used for calculation; and $J_{it}$ is the Jaccard similarity <cit.>, which measures the degree of the second-order proximity of node pairs $(v_i,v_t)$, as not all two-hop neighbors have high second-order proximities. In our study, rather than higher-order positive relations, we take only into account the second-order positive relations of node pairs. This is because such a loss function setting leads to quite satisfactory performance, which will be shown in Section <ref>, and expanding to more than three-hop relationships is computationally quite expensive. After the loss $\mathcal{L}$ is calculated, the model parameters $\theta$ are updated using gradient descent optimization (refer to line 8 of Algorithm <ref>).

It is worth noting that our loss function accurately captures the structural information of the network by encoding not only the multi-hop relationships between negative node pairs but also the second-hop relationships between positive node pairs. A schematic example of the training process of our  framework is illustrated in Fig. <ref>, where the quadruplet $(v_i,v_j,v_n,v_t)$ for target node $v_i$ is shown.

Finally, we turn to describing the inference phase. As visualized in Fig. <ref>, we are capable of inductively finding embedding vectors ${\bf Z}^{\textnormal{all}}$ for $\mathcal{V}^{\textnormal{all}}$ using the trained model parameters $\theta$ as well as the input of the GNN model including $G_{k\textnormal{NN}}^{\textnormal{all}}$ and $\mathcal{X}^{\textnormal{all}}$ via a single feedforward process. That is, it follows that $\mathbf{Z}^{\textnormal{all}} = \textsf{GNN}_{\theta}(G_{k\textnormal{NN}}^{\textnormal{all}}, \mathcal{X}^{\textnormal{all}})$ (refer to lines 12–13). We then discover the embedding vectors ${\bf Z}'$ for the edgeless nodes in $\mathcal{V}'$.

Next, we address the computational complexity of our proposed  framework as follows.

We note that the feedforward process of GNNs includes the computation of both AGGREGATE and UPDATE functions and its computational complexity is given by $\mathcal{O}(2|\mathcal{E}|+|\mathcal{V}|)$ (refer to <cit.> for more details). In our  framework, the number of edges in a computation graph depends on the $k$NNG construction. For the best case where all edges are created by selecting $k$ neighbors of each node in the sense of minimizing the graph density, $k|\mathcal{V}|/2$ edges are generated, thus yielding the computational complexity of $\Omega((k+1)|\mathcal{V}|)$. For the worst case, corresponding to the mutually exclusive selection of edges, $k|\mathcal{V}|$ edges are generated; the complexity is thus bounded by $\mathcal{O}((2k+1)|\mathcal{V}|)$. Hence, the computational complexity of our  is finally given by $\mathcal{O}(k|\mathcal{V}|)$, indicating a linear complexity in $k$ and $|\mathcal{V}|$.

§ EXPERIMENTAL EVALUATION

In this section, we first describe real-world datasets used in the evaluation. We also present two state-of-the-art methods and three baseline methods for comparative studies. After describing our experimental settings as well as downstream ML tasks and their performance metrics, we comprehensively evaluate the performance of our  framework and five benchmark methods.

Dataset     NN     NE     NA      NC     HR

Cora      2,485     5,069     1,433      7      0.80

Citeseer     2,120     3,679     3,703     6     0.73

Wiki     2,357     12,714     4,973      19     0.34

Pubmed     19,717     44,324     500     3     0.80

Coauthor-CS     18,333     81,894     6,805     15     0.81

Summary of statistics of five datasets, where NN, NE, NA, NC, and HR denote the number of nodes, the number of edges, the number of node attributes, the number of classes, and the homophily ratio, which is defined as the fraction of edges whose connected nodes have the same class label <cit.>, respectively.

§.§ Dataset

Five real-world attributed network datasets, commonly adopted from the literature of attributed network embedding, are used to acquire the network structure $G$ and the set of node attributes, $\mathcal{X}^{\text{all}}$. For all experiments, we only consider the largest connected component without isolated nodes. The main statistics of each dataset are summarized in Table <ref>. In the following, we describe important characteristics of the datasets.

Cora, Citeseer <cit.>, and Pubmed <cit.>. The three datasets are citation networks. Each node is a publication from various research topics, each of which represents the class label, and an edge exists if one publication cited another. The attribute matrix is the bag-of-word representation comprising a corpus of documents for Cora and Citeseer and is the representation weighted by term frequency-inverse document frequency (TF-IDF) for Pubmed. We use the version provided in <cit.> for our experiments.

Wiki <cit.>. The Wiki dataset is a network of web pages where the nodes are web documents in Wikipedia. Edges are constructed when two web pages have hyperlinks. The attribute matrix is the representation weighted by TF-IDF.

Coauthor-CS <cit.>. The Coauthor-CS dataset is a co-authorship network where nodes are authors and are connected if they are co-authors of a paper. The attribute matrix includes keywords in each author's papers, and the class labels indicate the most active research field for each author.

§.§ Benchmark Methods

In this subsection, we present two state-of-the-art methods for inductive edgeless network embedding and three baseline methods for comparison.

DEAL <cit.>. This state-of-the-art approach aims to solve the inductive link prediction problem. To this end, the embeddings generated by two encoders, namely an MLP encoder using node attributes and a linear encoder using one-hot node representations are aligned to learn the connections between the node attributes and the network structure so that the encoder generates a link prediction score for edgeless nodes.

Graph2Gauss (G2G) <cit.>. As another state-of-the-art method, the G2G model trains an MLP encoder that represents each node as a Gaussian distribution to capture the uncertainties of embeddings. The model also investigates its application to the problem of inductive link prediction.

Inference only with node attributes (Att-Only). As a baseline, we include the case where the attribute matrix is only used for inference. In other words, the attribute matrix itself is taken into account as node embeddings.

SAGE-$k$NNG1. This baseline method basically adopts the loss function and the GNN architecture in GraphSAGE <cit.> that serves as a state-of-the-art GNN model with no modification, while using the underlying network $G$ as a computation graph during the training phase. However, during the inference phase, due to the absence of connectivity information on edgeless nodes in $\mathcal{V}'$, we generate additional edges on the existing $G$ via $k$NNG construction based on the similarity of node attributes $\mathcal{X}^{\textnormal{all}}$ for each edgeless node in order to perform message passing along with the trained GraphSAGE model.

SAGE-$k$NNG2. As in , this baseline model utilizes the $k$NNG generated from node attributes for both training and inference. On the other hand, this baseline adopts the loss function and the GNN architecture that are identical to those in GraphSAGE during the training phase.

We remark that, although network completion <cit.> was carried out to discover the network structure of edgeless nodes, it requires either the assumption of a power-law degree distribution of the underlying graph <cit.> or a set of structurally similar graphs as training data to learn the distribution of the graphs <cit.>. Such a network completion problem aims to infer the missing nodes and edges with no node identity, which thus basically differs from our edgeless network embedding problem. Moreover, even if the GCN model in <cit.> employed the $k$NNG construction to initialize edge probabilities, it was built upon a transductive setting that requires complete retraining when unseen nodes newly enter the underlying network; thus, it cannot be straightforwardly compared to inductive network embedding without significant modifications of the existing model. In this context, we do not adopt the network completion methods in <cit.> and the transductive GCN model in <cit.> as benchmark methods. Our problem would tackle another new and under-explored challenge to infer embeddings for the edgeless nodes.

§.§ Downstream Tasks With Performance Metrics

To empirically validate the performance of the proposed framework over the above benchmark methods in an inductive setting, we consider three downstream ML tasks and assess the performance via five metrics. We note that all metrics are in a range of $[0,1]$, and higher values represent better performance. The performance of each ML task is evaluated on edgeless nodes since we focus on the inductive setting along with inductive representation learning of edgeless nodes.

Link prediction <cit.> aims to predict edges that are likely to be existent. In our study, we predict edges to which edgeless nodes are incident by obtaining a reconstructed graph $\hat{G}^\text{all}$ via calculated embeddings, i.e., $\hat{G}^\text{all}=\sigma({\bf Z}^\text{all}{\bf Z}^{\text{all}\top})$, where $\top$ denotes the transpose of a matrix. That is, we focus on predicting the set of two types of edges including the edges connecting two nodes in $\mathcal{V}'$ and the edges connecting one node in $\mathcal{V}$ and another node in $\mathcal{V}'$. We adopt the average precision (AP) and area under curve (AUC) scores for this task.

Node classification <cit.> aims to classify new nodes into their ground truth classes. We train a logistic regression classifier using a portion of node embeddings in a supervised manner. We adopt the macro-$F_1$ and micro-$F_1$ scores for this task.

Community detection <cit.> aims to unsupervisedly find the set of communities. We apply $k$-means clustering, one of standard clustering techniques, to the embeddings for all nodes in $\mathcal{V}^{\text{all}}$ and then assign a community label to each node to predict ground-truth communities of new nodes. We adopt the normalized mutual information (NMI) for this task.

§.§ Experimental Setup

We first describe the settings of neural networks. In our experiments, we adopt 1-layer GNN models. This is due to the fact that edges generated by $k$NNG construction can be thought of as proxy edges, which implies that we have little benefit from stacking multiple GNN layers that may propagate the noisy information aggregated from some undesirable multi-hop neighbors.[For the performance of our  framework with respect to the number of GNN layers, we refer to https://github.com/jordan7186/Edgeless-GNN-external/blob/main/Additional_experiment.md.] It is worth noting that, even with the single-layer setting, we are still capable of capturing the multi-hop relationships between node pairs by adjusting model parameters through our loss function in (<ref>). The dimension of the final embedding space as well as each intermediate hidden latent space (if any) is set to 64. We train our GNN model via the Adam optimizer <cit.> with a learning rate of 0.0005 and a weight decay rate of 0.0005. All models were implemented via a geometric learning library in PyTorch, named PyTorch Geometric <cit.>.

In the $k$NNG construction, we set $k=3$ for all experiments. This is because 1) our experimental findings reveal that the performance is insensitive to the value of $k$ (refer to Table <ref> for experimental results in terms of link prediction) and 2) the value of $k$ needs to be set as small as possible since the computational complexity of  scales linearly with $k$ (refer to Remark <ref>).[For the performance of our  framework with respect to $k$ for all three downstream ML tasks, we refer to https://github.com/jordan7186/Edgeless-GNN-external/blob/main/Additional_experiment.md.]

$k$     2     3     4      5     6

AP      0.9376      0.9385      0.9325       0.9365       0.9385

AUC      0.9279      0.9279      0.9279       0.9279       0.9279

Performance of our  framework on the link prediction task for the Citeseer dataset according to different values of $k$.

From each dataset, we randomly split the set of nodes into training/validation/test sets with a ratio of 85/5/10%. In our experiments, the validation and test sets accounting for 15% of nodes are treated as new edgeless nodes. Note that the results from different training/validation/test splits essentially showed a tendency similar to those reported in Section <ref>. We use the scores from the validation set to tune the hyperparameters and determine the number of training iterations. That is, we use the values of hyperparameters (e.g., $\alpha$ and $\beta$ presented in our loss function) optimally found according to different datasets and downstream ML tasks. For each evaluation, we run experiments over 10 different splits of training/validation/test sets to compute the average score.

§.§ Experimental Results

In this subsection, our empirical study is designed to answer the following five key research questions.

* Q1. How do underlying GNN models affect the performance of the  framework?

* Q2. How do model hyperparameters affect the performance of the  framework?

* Q3. How much does the  framework improve the performance of various downstream ML tasks over state-of-the-art methods of inductive edgeless network embedding?

* Q4. How robust is our  framework to the noise of node attributes?

* Q5. How scalable is our  framework with vital parameters including the graph size?

To answer these research questions, we comprehensively carry out experiments in the following subsections.

§.§.§ Comparative Study Among GNN Models (Q1)

In Fig. <ref>, we show the performance of different downstream ML tasks using various GNN models in our  framework using the Cora dataset. Note that the results from other datasets showed a tendency similar to those reported in this subsection.[We refer to https://github.com/jordan7186/Edgeless-GNN-external/blob/main/Additional_experiment.md.] Since our framework is GNN-model-agnostic, any existing models can be adopted; however, in our experiments, we adopt the following three widely used GNN models from the literature <cit.>, namely GCN <cit.>  (), GraphSAGE <cit.> (), and GIN <cit.> ().[For the GIN model, we exceptionally use the UPDATE function composed of a two-layer MLP and the ReLU activation function <cit.> according to the original implementation in <cit.>.] Our findings are as follows:

*  consistently outperforms other models regardless of downstream tasks. Such a gain is possible due to the concatenation operation of the UPDATE function in (<ref>), which enables the GraphSAGE model to elaborately assign different weights to the aggregated messages from neighbors via the constructed $k$NNG and latent information of each node itself, unlike other models with the mean/sum aggregator <cit.>.

* For other two models, one does not always dominate another.  performs better than  in terms of link prediction and community detection while an opposite trend occurs for node classification.

From these findings, we use  in our subsequent experiments unless otherwise stated.

/pgfplots/ybar legend/.style=
/pgfplots/legend image code/.code=
(0cm,0cm) rectangle (3pt,0.8em);,

width  = ,
height = 5cm,
major x tick style = transparent,
bar width=0.025*,
ymajorgrids = true,
ylabel = Performance,
symbolic x coords=AP,AUC,Macro-$F_1$, Micro-$F_1$, NMI,
xtick = data,
scaled y ticks = false,
enlarge x limits=0.1,
legend cell align=left,
legend style=at=(0.5,1.1), anchor=south,legend columns=3,font=
[style=black,fill=bblue,mark=none, error bars/.cd,
y dir=both,y explicit]
coordinates (AP, 0.8571) +-(0.008739,0.008739) (AUC,0.8582)+-(0.008807,0.008807) (Macro-$F_1$,0.3144)+-(0.055296,0.055296) (Micro-$F_1$,0.4725)+-(0.051736,0.051736) (NMI,0.4269)+-(0.034585,0.034585);

[style=black,fill=rred,mark=none, error bars/.cd,
y dir=both,y explicit]
coordinates (AP, 0.8929)+-(0.014009,0.014009) (AUC,0.8905)+-(0.012708,0.012708) (Macro-$F_1$,0.6783)+-(0.033525,0.033525) (Micro-$F_1$,0.7177)+-(0.03432,0.03432) (NMI,0.5109)+-(0.02128,0.02128);

[style=black,fill=ggreen,mark=none, error bars/.cd,
y dir=both,y explicit]
coordinates (AP, 0.8367)+-(0.009232,0.009232) (AUC,0.8501)+-(0.009274,0.009274) (Macro-$F_1$,0.6536)+-(0.042634,0.042634) (Micro-$F_1$,0.7036)+-(0.026011,0.026011) (NMI,0.3783)+-(0.039053,0.039053);

Performance of downstream ML tasks according to different GNN models in our  framework.

legend columns=-1,
legend entries=AP,AUC,Macro-$F_1$,Micro-$F_1$,NMI,
legend to name=named,
xmax=4,xmin=0,ymin= 0.45,ymax=0.95,
xlabel=(a) Effect of $\alpha$.,ylabel=Performance, width = 4.5cm, height = 5.5cm,
coordinates(0, 0.891504725) (1,0.894843) (2,0.893776) (3,0.892775) (4,0.895773);
coordinates(0, 0.881797247) (1,0.887297) (2,0.890166) (3,0.888849) (4,0.890424);
coordinates(0, 0.597285184) (1,0.628233) (2,0.633282) (3,0.665009) (4,0.643166);
coordinates(0, 0.652016129) (1,0.661694) (2,0.681452) (3,0.697581) (4,0.675);
coordinates(0, 0.47700881) (1,0.474801) (2,0.488063) (3,0.496644) (4,0.472434);

xmax=4,xmin=0,ymin= 0.45,ymax=0.95,
xlabel=(b) Effect of $\beta$., width = 4.5cm, height = 5.5cm,
coordinates(0, 0.888846) (0.5, 0.89234056) (1,0.900714) (2,0.890307) (3,0.894157) (4,0.88021);
coordinates(0, 0.885711) (0.5, 0.890825048) (1,0.896112) (2,0.884786) (3,0.88854) (4,0.873073);
coordinates(0, 0.670731) (0.5, 0.675209966) (1,0.668276) (2,0.644362) (3,0.625497) (4,0.611651);
coordinates(0, 0.714919) (0.5, 0.711693548) (1,0.695565) (2,0.664113) (3,0.670968) (4,0.642339);
coordinates(0, 0.486029) (0.5, 0.527029735) (1,0.522733) (2,0.484934) (3,0.494736) (4,0.473787);

Performance of downstream ML tasks according to different values of hyperpaprameters $\alpha$ and $\beta$ in our  framework.

1c          2cLink prediction     2cNode classification     Community detection

Dataset     Method     AP     AUC     Macro-$F_1$     Micro-$F_1$     NMI

6*90Cora           0.8930 $\pm$ 0.0140    0.8905 $\pm$ 0.0127     0.6783 $\pm$ 0.0140     0.7177 $\pm$ 0.0343     0.5109 $\pm$ 0.0212

DEAL     0.8550 $\pm$ 0.0134     0.8585 $\pm$ 0.0105     0.6410 $\pm$ 0.0332     0.6903 $\pm$ 0.0270    0.4321 $\pm$ 0.0193

G2G     0.7966 $\pm$ 0.0470     0.8113 $\pm$ 0.0205     0.5983 $\pm$ 0.0165     0.6346 $\pm$ 0.0328     0.4089 $\pm$ 0.0354

Att-Only    0.7546 $\pm$ 0.0126     0.7584 $\pm$ 0.0129     0.4923 $\pm$ 0.0347     0.5681 $\pm$ 0.0287     0.2213 $\pm$ 0.0602

SAGE-$k$NNG1     0.5961 $\pm$ 0.0193     0.5713 $\pm$ 0.0203     0.1990 $\pm$ 0.0481     0.3008 $\pm$ 0.0466     0.0615 $\pm$ 0.0228

SAGE-$k$NNG2     0.5889 $\pm$ 0.0208     0.5672 $\pm$ 0.0186     0.2100 $\pm$ 0.0167     0.3068 $\pm$ 0.0197     0.0569 $\pm$ 0.0206

6*90Citeseer          0.9385 $\pm$ 0.0062     0.9313 $\pm$ 0.0072     0.5832 $\pm$ 0.0378     0.6697 $\pm$ 0.0299     0.4497 $\pm$ 0.0506

DEAL     0.9128 $\pm$ 0.0063     0.9059 $\pm$ 0.0074     0.5733 $\pm$ 0.0445     0.6701 $\pm$ 0.0350     0.3984 $\pm$ 0.0362

G2G     0.8545 $\pm$ 0.0721     0.8619 $\pm$ 0.0149     0.5424 $\pm$ 0.0110     0.6417 $\pm$ 0.0415     0.4131 $\pm$ 0.0363

Att-Only     0.8535 $\pm$ 0.0110     0.8448 $\pm$ 0.0112     0.5186 $\pm$ 0.0399     0.6293 $\pm$ 0.0402     0.2884 $\pm$ 0.0407

SAGE-$k$NNG1     0.5816 $\pm$ 0.0216     0.5588 $\pm$ 0.0236     0.1926 $\pm$ 0.0443     0.2995 $\pm$ 0.0264     0.0585 $\pm$ 0.0178

SAGE-$k$NNG2     0.6024 $\pm$ 0.0250     0.6035 $\pm$ 0.0317     0.2004 $\pm$ 0.0316     0.3023 $\pm$ 0.0403     0.0458 $\pm$ 0.0116

6*90Wiki           0.7241 $\pm$ 0.0157     0.6842 $\pm$ 0.0211     0.5340 $\pm$ 0.0316     0.6596 $\pm$ 0.0273     0.6061 $\pm$ 0.0355

DEAL     0.6724 $\pm$ 0.0220     0.6622 $\pm$ 0.0217     0.2065 $\pm$ 0.0256     0.4017 $\pm$ 0.0285     0.5561 $\pm$ 0.0264

G2G     0.6026 $\pm$ 0.0265     0.6088 $\pm$ 0.0177     0.4124 $\pm$ 0.0596     0.5859 $\pm$ 0.0308     0.5213 $\pm$ 0.0488

Att-Only     0.6206 $\pm$ 0.0078     0.5725 $\pm$ 0.0095     0.2802 $\pm$ 0.0375     0.4557 $\pm$ 0.0418     0.4057 $\pm$ 0.0432

SAGE-$k$NNG1     0.5730 $\pm$ 0.0066     0.5329 $\pm$ 0.0150     0.0258 $\pm$ 0.0067     0.1702 $\pm$ 0.0232     0.1589 $\pm$ 0.0216

SAGE-$k$NNG2     0.5648 $\pm$ 0.0134     0.5300 $\pm$ 0.0090     0.0327 $\pm$ 0.0061     0.1714 $\pm$ 0.0290     0.1469 $\pm$ 0.0270

6*90Pubmed           0.9413 $\pm$ 0.0033     0.9426 $\pm$ 0.0026    0.8307 $\pm$ 0.0104     0.8306 $\pm$ 0.0102     0.3051 $\pm$ 0.0242

DEAL     0.8974 $\pm$ 0.0025     0.9119 $\pm$ 0.0024     0.8247 $\pm$ 0.0048     0.8264 $\pm$ 0.0040     0.3285 $\pm$ 0.0119

G2G     0.8535 $\pm$ 0.0085     0.8756 $\pm$ 0.0062     0.8278 $\pm$ 0.0106     0.8304 $\pm$ 0.0094     0.3101 $\pm$ 0.0285

Att-Only     0.8977 $\pm$ 0.0047     0.8878 $\pm$ 0.0054     0.8164 $\pm$ 0.0077     0.8155 $\pm$ 0.0068     0.3217 $\pm$ 0.0091

SAGE-$k$NNG1     0.6077 $\pm$ 0.0104     0.6074 $\pm$ 0.0112     0.3867 $\pm$ 0.0165     0.4560 $\pm$ 0.0121     0.0196 $\pm$ 0.0145

SAGE-$k$NNG2     0.6191 $\pm$ 0.0086     0.6210 $\pm$ 0.0111     0.3830 $\pm$ 0.0145     0.4498 $\pm$ 0.0212     0.0263 $\pm$ 0.0238

CS           0.9531 $\pm$ 0.0017     0.9503 $\pm$ 0.0017     0.8932 $\pm$ 0.0122     0.9218 $\pm$ 0.0058     0.7981 $\pm$ 0.0141

DEAL     0.9342 $\pm$ 0.0020     0.9319 $\pm$ 0.0021     0.8689 $\pm$ 0.0106     0.9124 $\pm$ 0.0065     0.6631 $\pm$ 0.0113

G2G     0.8234 $\pm$ 0.0097     0.8516 $\pm$ 0.0051     0.8120 $\pm$ 0.0140     0.8738 $\pm$ 0.0078     0.6857 $\pm$ 0.0083

Att-Only     0.9034 $\pm$ 0.0020     0.9096 $\pm$ 0.0018     0.8301 $\pm$ 0.0214     0.8924 $\pm$ 0.0111     0.5662 $\pm$ 0.0150

SAGE-$k$NNG1     0.7074 $\pm$ 0.0035     0.6872 $\pm$ 0.0031     0.0356 $\pm$ 0.0034     0.2363 $\pm$ 0.0080     0.0674 $\pm$ 0.0233

SAGE-$k$NNG2     0.7149 $\pm$ 0.0074     0.6952 $\pm$ 0.0055     0.0704 $\pm$ 0.0074     0.2513 $\pm$ 0.0123     0.0436 $\pm$ 0.0114

Performance comparison among  and benchmark methods in terms of five performance metrics (average $\pm$ standard deviation). Here, the best method for each case is highlighted using underlines.

§.§.§ Sensitivity to Hyperparameters (Q2)

In Fig. <ref>, we investigate the impact of hyperparameters $\alpha$ and $\beta$ on the performance of , using the Cora dataset, where $\alpha$ controls the strength of the second-order proximity loss term in (<ref>) and $\beta$ controls the effect of negative node pairs in (<ref>). Note that the results from other datasets showed a tendency similar to those reported in this subsection.[We refer to https://github.com/jordan7186/Edgeless-GNN-external/blob/main/Additional_experiment.md.] When a hyperparameter ($\alpha$ or $\beta$) varies so that its effect is clearly revealed, another parameter is set to the pivot values $\alpha=4$ and $\beta=1$. We observe the following:

* The effect of $\alpha$ and $\beta$ is more prominent in node classification and community detection.

* From Fig. <ref>a, the maximum tends to be achieved at $\alpha=3$ regardless of downstream tasks. When $\alpha$ exceeds this value, the effect of the second-order proximity becomes over-amplified, thus leading to distorted embeddings.

* From Fig. <ref>b, the case of $\beta>1$ tends to deteriorate the performance. This is because, in such a case, the exponent in (<ref>) will explode while providing an unbalanced repulsive force between negative node pairs. In contrast, when $\beta=0$, the performance also gets reduced. Therefore, we conclude that setting $\beta$ to a low value near 1 achieves satisfactory performance.

§.§.§ Comparison With State-of-the-Art Approaches (Q3)

The performance comparison between our  framework and two state-of-the-art inductive network embedding methods, including DEAL <cit.> and G2G <cit.>, as well as a baseline method only using node attributes, namely Att-Only, is comprehensively presented in Table <ref> with respect to five performance metrics using all five real-world datasets.[Simple modification of the transductive GCN model in <cit.> in such a way that edges are removed to generate edgeless nodes results in unsatisfactory performance in node classification. For the experimental results, we refer to https://github.com/jordan7186/Edgeless-GNN-external/blob/main/Additional_experiment.md.] We note that the hyperparameters are tuned differently according to each individual dataset and downstream task for all the aforementioned methods. In Table <ref>, the value with an underline indicates the best performer for each case. We would like to make the following insightful observations:

1c          4cThe portion of missing node attributes (%)

Metric     Method     20     40     60     80

6*90AP           0.8719 $\pm$ 0.0097     0.8517 $\pm$ 0.0124     0.8083 $\pm$ 0.0143     0.7875 $\pm$ 0.0157

DEAL     0.8328 $\pm$ 0.0092     0.8050 $\pm$ 0.0056     0.7755 $\pm$ 0.0122     0.7514 $\pm$ 0.0117

G2G     0.7503 $\pm$ 0.0131     0.7268 $\pm$ 0.0154     0.7047 $\pm$ 0.0154     0.6987 $\pm$ 0.0154

Att-Only    0.7252 $\pm$ 0.0079     0.6837 $\pm$ 0.0106     0.6370 $\pm$ 0.0071     0.6038 $\pm$ 0.0109

SAGE-$k$NNG1     0.5712 $\pm$ 0.0195     0.5380 $\pm$ 0.0196     0.5287 $\pm$ 0.0158     0.5162 $\pm$ 0.0189

SAGE-$k$NNG2     0.5700 $\pm$ 0.0226     0.5349 $\pm$ 0.0197     0.5023 $\pm$ 0.0159     0.5160 $\pm$ 0.0139

6*90AUC           0.8815 $\pm$ 0.0092     0.8642 $\pm$ 0.0160     0.8565 $\pm$ 0.0154     0.8408 $\pm$ 0.0103

DEAL     0.7952 $\pm$ 0.0101      0.7918 $\pm$ 0.0081     0.7900 $\pm$ 0.0129     0.7921 $\pm$ 0.0131

G2G     0.7945 $\pm$ 0.0131     0.7652 $\pm$ 0.0113     0.7508 $\pm$ 0.0186     0.7423 $\pm$ 0.0177

Att-Only    0.7582 $\pm$ 0.0101     0.7365 $\pm$ 0.0073     0.7170 $\pm$ 0.0067     0.7001 $\pm$ 0.0100

SAGE-$k$NNG1     0.5589 $\pm$ 0.0203     0.5343 $\pm$ 0.0150     0.5222 $\pm$ 0.0183     0.5160 $\pm$ 0.0182

SAGE-$k$NNG2     0.5571 $\pm$ 0.0147     0.5378 $\pm$ 0.0194     0.5114 $\pm$ 0.0218     0.5201 $\pm$ 0.0141

6*90Macro-$F_1$           0.5779 $\pm$ 0.0332     0.5603 $\pm$ 0.0404     0.5002 $\pm$ 0.0253     0.4580 $\pm$ 0.0461

DEAL     0.5755 $\pm$ 0.0378     0.5157 $\pm$ 0.0262     0.4884 $\pm$ 0.0261     0.4412 $\pm$ 0.0297

G2G     0.5250 $\pm$ 0.0322     0.4808 $\pm$ 0.0326    0.4389 $\pm$ 0.0560     0.4083 $\pm$ 0.0244

Att-Only     0.4214 $\pm$ 0.0429     0.3571 $\pm$ 0.0411     0.3330 $\pm$ 0.0394     0.2863 $\pm$ 0.0402

SAGE-$k$NNG1     0.1881 $\pm$ 0.0284     0.1676 $\pm$ 0.0353     0.1233 $\pm$ 0.0247     0.0854 $\pm$ 0.0130

SAGE-$k$NNG2     0.1847 $\pm$ 0.0334     0.1499 $\pm$ 0.0328     0.1020 $\pm$ 0.0164     0.0776 $\pm$ 0.0114

6*90Micro-$F_1$           0.6701 $\pm$ 0.0290     0.6229 $\pm$ 0.0449     0.6161 $\pm$ 0.0444     0.6028 $\pm$ 0.0311

DEAL     0.6459 $\pm$ 0.0277     0.6447 $\pm$ 0.0261     0.6375 $\pm$ 0.0285     0.6451 $\pm$ 0.0271

G2G     0.6120 $\pm$ 0.0394     0.5903 $\pm$ 0.0280     0.5455 $\pm$ 0.0413     0.5548 $\pm$ 0.0110

Att-Only    0.5399 $\pm$ 0.0250     0.5064 $\pm$ 0.0376     0.4536 $\pm$ 0.0434     0.4262 $\pm$ 0.0217

SAGE-$k$NNG1     0.3052 $\pm$ 0.0208     0.2822 $\pm$ 0.0328     0.2842 $\pm$ 0.0272     0.2939 $\pm$ 0.0252

SAGE-$k$NNG2     0.2802 $\pm$ 0.0154     0.2967 $\pm$ 0.0106     0.2641 $\pm$ 0.0246     0.2838 $\pm$ 0.0235

6*90NMI           0.4381 $\pm$ 0.0276     0.3922 $\pm$ 0.0357     0.3087 $\pm$ 0.0300     0.2838 $\pm$ 0.0262

DEAL     0.3638 $\pm$ 0.0360     0.3442 $\pm$ 0.0271     0.2866 $\pm$ 0.0383     0.2398 $\pm$ 0.0269

G2G     0.3397 $\pm$ 0.0355     0.2915 $\pm$ 0.0174     0.2444 $\pm$ 0.0252     0.2100 $\pm$ 0.0316

Att-Only     0.1575 $\pm$ 0.0390     0.1198 $\pm$ 0.0248     0.0845 $\pm$ 0.0275     0.0720 $\pm$ 0.0211

SAGE-$k$NNG1     0.0497 $\pm$ 0.0118     0.0436 $\pm$ 0.0122     0.0496 $\pm$ 0.0096     0.0398 $\pm$ 0.0103

SAGE-$k$NNG2     0.0525 $\pm$ 0.0140     0.0405 $\pm$ 0.0110     0.0351 $\pm$ 0.0121     0.0428 $\pm$ 0.0078

Performance comparison among  and benchmark methods in terms of five performance metrics (average $\pm$ standard deviation) using the Cora dataset when some of node attributes are missing. Here, the best method for each case is highlighted using underlines.

* Our  framework consistently outperforms benchmark methods except for only a few cases in node classification and community detection.

* The performance gap between our  and the second best method is the largest when we perform node classification using the Wiki dataset; the maximum improvement rates of $29.5\%$ and $12.5\%$ are achieved in terms of macro-$F_1$ and micro-$F_1$ scores, respectively. This coincides with the argument in <cit.>, where GraphSAGE, the underlying GNN model applied to our , is shown to be robust to networks even with low homophily ratios such as Wiki (refer to Table <ref>).

* The G2G method <cit.> tends to exhibit poor performance, being even inferior to Att-Only, on the link prediction task for the Pubmed and Coauthor-CS datasets. This is because the Kullback-Leibler (KL) divergence, used in the loss of G2G to measure the similarity of node pairs, is asymmetric and does not well preserve the transitivity of proximity in undirected graphs as discussed in <cit.>, thus leading to distortion in the embedding space to some extent.

* More importantly, the two $k$NNG-aided baseline methods, SAGE-$k$NNG1 and SAGE-$k$NNG2, exhibit the worst performance; their performance is even much lower than that of Att-Only, another baseline. This indicates that the $k$NNG construction alone is not sufficient to bring satisfactory performance on downstream tasks and thorough efforts should be devoted to optimizing the model parameters using a non-straightforward and sophisticated loss function. In contrast to GraphSAGE <cit.>, our newly designed loss function takes into account not only the shortest path distance between negative node pairs but also the second-order positive relations of node pairs. Thus, our framework is able to consistently achieve quite superior performance to that of the above baselines while utilizing the $k$NNG-based computation graph construction.

* Let us compare the performance of methods according to different downstream ML tasks. For a given dataset, the highest gain of  over benchmark methods tends to be achieved in either node classification or community detection. This comes from the fact that DEAL <cit.>, the second best performer, was originally designed for the link prediction task.

* The performance comparison between node classification and community detection is made as follows. It is likely that the gain of  over benchmark methods is higher mostly in the community detection task than that in the node classification task except for the Wiki and Pubmed datasets. Since our framework including the $k$NNG construction is inherently designed unsupervisedly, it is generally advantageous to (unsupervised) community detection. For the Wiki dataset, the potential benefits of  are slightly diminished due to the low homophily ratio, indicating that the agreement between the $k$NNG constructed from node attributes and the true network structure might be low. For the Pubmed dataset, there is a dissimilar tendency on the overall performance between the two tasks: 1) the node classification performance is quite satisfactory regardless of methods, revealing that the Macro-$F_1$ and Micro-$F_1$ scores are more than 0.8; and 2) in sharp contrast, all methods do not achieve competent performance in community detection. These findings imply that the label information in semi-supervised classification is potent due to the inherent limitation, including fuzzy community boundaries, in the Pubmed dataset, as already stated in other studies <cit.>.

§.§.§ Robustness to the Degree of Observability of Node Attributes (Q4)

We now evaluate the performance of downstream ML tasks in more difficult settings that often occur in real environments where a large portion of node attributes are missing. In these experiments, we fix the hyperparameters for all tasks for simplicity and only show the results for the Cora dataset since the results from other datasets follow similar trends.

We create incomplete attributed networks by randomly masking $\{20,40,60,80\}\%$ of node attributes in each dataset. The performance comparison between our  framework and the five benchmark methods is presented in Table <ref> with respect to five performance metrics. Our findings demonstrate that, while the performance tends to degrade with an increasing portion of missing node attributes for all the methods, our  consistently achieves superior performance compared to other methods in terms of all performance metrics even for the case where only a small portion of node attributes are observable. This implies that our framework is robust to the degree of observability of node attributes even if a $k$NNG is constructed using the set of incomplete node attributes.

§.§.§ Scalability (Q5)

To empirically validate the average runtime complexity discussed in Remark <ref>, we conduct experiments using the Pubmed dataset whose number of nodes is sufficiently large in flexibly altering the graph size, where a full-batch setting is assumed. For the first experiment, we sample subgraphs of various sizes having $\{1,000, 3,000, 5,000, 7,000, 9,000, 11,000\}$ nodes from Pubmed via forest fire sampling <cit.> so as to examine the scalability while preserving the same structural properties. For the second experiment, we use a subgraph of a fixed size with 2,500 nodes while varying the parameter $k$ in $k$ from 2 to 8. We illustrate the runtime in seconds with respect to different $|\mathcal{V}|$'s and $k$'s in Figs. <ref>a and <ref>b, respectively. Asymptotic solid lines are also shown in the figure, showing a trend that is consistent with our experimental results. These results validate our analytical claim, i.e., a linear complexity scaling in $k$ and $\mathcal{V}$ .

§ CONCLUDING REMARKS

In this paper, we explored an open yet important problem of how to exploit the power of GNNs in the context of embedding of topologically unseen nodes. To tackle this challenge, we introduced , a novel GNN framework that unsupervisedly and inductively discovers embeddings of edgeless nodes in attributed networks. Specifically, we developed an approach to 1) first constructing a new computation graph based on the similarity of node attributes unlike the original one used in GNNs and 2) then training our model by establishing our own loss function that exploits not only the first-order proximity of node pairs but also higher-order relations so as to more delicately learn embeddings from the underlying network structure. Using five real-world datasets, we demonstrated that, for almost all cases, our  framework consistently outperforms state-of-the-art inductive network embedding methods, including DEAL and G2G, as well as three baseline methods, when we perform three downstream ML tasks. We also found that our  still achieves superior performance compared to the benchmark methods even for more difficult yet practical situations where only a small portion of node attributes are observable. Moreover, we analytically and empirically showed the scalability of our  framework.

Potential avenues of future research include the design of more robust  framework when a portion of node attributes are noisy and/or missing in attributed networks. Another interesting direction is to design a new GNN architecture (rather than adopting existing GNNs) that better suits for the circumstance in which the network structure of some nodes is unknown.

footnotesize,samples=10,scaled y ticks=false, yticklabel style=
/pgf/number format/fixed,
/pgf/number format/precision=5
, scaled x ticks=false, xticklabel style=
/pgf/number format/fixed,
/pgf/number format/precision=5

xmax=12000,xmin=-1000,ymin= 0
xlabel=(a) $|\mathcal{V}|$,ylabel=Runtime (s), width = 4.7cm,
xtick = 1000,5000,9000]
[only marks, mark = o] coordinates(1000, 0.01156) (3000,0.04296) (5000,0.08351) (7000,0.12889) (9000,0.17839) (11000, 0.22516);
[draw=red, mark=none,domain=1000:11000]0.00002195*x-0.0208;

footnotesize,samples=10,yticklabel style=
/pgf/number format/fixed,
/pgf/number format/precision=2
scaled y ticks=false

xmax=9,xmin=1,ymin= 0.02,ymax=0.1,
xlabel=(b) $k$, width = 4.7cm,
[only marks, mark = o, color = blue] coordinates(2, 0.0229) (3, 0.0338) (4, 0.0462) (5, 0.0572) (6, 0.0706) (7, 0.0831) (8, 0.0949);
[draw=red, mark=none,domain=2:8]0.0121*x-0.0021;

The computational complexity of  with respect to $k$ and $|\mathcal{V}|$, where the analytical results with proper biases are also plotted with red solid lines.

§ ACKNOWLEDGMENTS

§ ACKNOWLEDGMENT

This research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2021R1A2C3004345), by a grant of the Korea Health Technology R&D Project through the Korea Health Industry Development Institute (KHIDI), funded by the Ministry of Health & Welfare, Republic of Korea (HI20C0127), and by the Yonsei University Research Fund of 2021 (2021-22-0083).