{'fraction_non_alphanumeric': 0.04369910818146568, 'fraction_numerical': 0.010895696006203956, 'mean_word_length': 4.577638408304498, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Effective Decoding in Graph Auto-Encoder using Triadic Closure

The (variational) graph auto-encoder and its variants have been popularly used for representation learning on graph-structured data. While the encoder is often a powerful graph convolutional network, the decoder reconstructs the graph structure by only considering two nodes at a time, thus ignoring possible interactions among edges. On the other hand, structured prediction, which considers the whole graph simultaneously, is computationally expensive. In this paper, we utilize the well-known triadic closure property which is exhibited in many real-world networks. We propose the triad decoder, which considers and predicts the three edges involved in a local triad together. The triad decoder can be readily used in any graph-based auto-encoder. In particular, we incorporate this to the (variational) graph auto-encoder. Experiments on link prediction, node clustering and graph generation show that the use of triads leads to more accurate prediction, clustering and better preservation of the graph characteristics.


Introduction
With the proliferation of online social networks, an enormous number of people are now connected digitally. Besides people, almost everything is also increasingly connected either physically or by all sorts of relationships, leading to the recent popularity of the internet of things and knowledge graphs. In today's big data era, it is thus important for organizations to derive the most value and insight out of this colossal amount of data entities and inter-relationships.
In general, nodes in the graph represent data entities, while edges represent all sorts of fine-grained relationships. For example, in a social network, the nodes are users that are connected by edges denoting pairwise friendships. In an author collaboration network, the edges denote co-authorship relationships. Besides social networks and knowledge graphs, data in domains such as chemistry and natural language semantics are often naturally represented as graphs.
There are a number of important tasks in graph analytics. A prominent example is link prediction (Wang, Chen, and Li 2017), which predicts whether an edge should exist between two given nodes. Since its early success at LinkedIn, Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. link recommendation has attracted significant attention in social networks, and also in predicting associations between molecules in biology, and the discovery of relationships in a terrorist network. Other popular graph analytics tasks include the clustering of nodes , and automatic graph generation (Bojchevski et al. 2018). Node clustering aims to partition graph nodes into a set of clusters such that the intra-cluster nodes are much related (densely connected) with each other as compared to the inter-cluster nodes. These cluster structures occur frequently in many domains such as computer networks, sociology, and physics. Graph generation refers to the task of generating similar output graphs given an input graph. It can be used in the discovery of molecule structures and dynamic network prediction.
However, graphs are typically difficult to analyze because they are large and highly sparse. Recently, there is a surge of interest in learning better graph representations (Goyal and Ferrara 2018;Hamilton, Ying, and Leskovec 2017). Different approaches are proposed to embed the structural and attribute information in a graph to a low-dimensional vector space, such that both the neighborhood similarity and community membership are preserved . A particularly successful unsupervised representation learning model on graphs is the variational auto-encoder (VAE) (Kingma and Welling 2014), and its variants such as the variational graph auto-encoder (VGAE), graph auto-encoder (GAE) (Kipf and Welling 2016b), adversarially regularized graph auto-encoder (ARGA), and adversarially regularized variational graph auto-encoder (ARVGA) (Pan et al. 2018). All these auto-encoder models consist of an encoder, which learns the latent representation, and a decoder, which reconstructs the graph-structured data based on the learned representation. The encoder is often based on the powerful graph convolutional network (GCN) (Kipf and Welling 2016a). However, the decoder is relatively primitive, and prediction of a link is based simply on the inner product between the latent representations of the nodes involved.
As nodes in a graph are interrelated, instead of predicting each link separately, all the candidate links in the whole graph should be considered together, leading to a structured prediction problem. However, learning of structured prediction models is often NP-hard (Globerson et al. 2015). A re-cent model along this direction is the structured prediction energy network (SPEN) (Belanger and McCallum 2016). However, design of the underlying energy function is still an open question, and computation of the underlying Hessian is computationally expensive.
On the other hand, an interesting property exhibited in many real-world networks is the so-called triadic closure, which is first proposed by Simmel (1908). This mechanism states that for any three nodes {i, j, k} in a graph, if there are edges between (i, j) and (i, k), it is likely that an edge also exists between j and k. It is then popularized by Granovetter (1973), who demonstrated empirically that triadic closure can be used to characterize link connections in many domains. For example, if two people (A and B) in a friendship network have a common friend, it is likely that A and B are also friends. If two papers in a citation network cite the same paper (suggesting that they belong to the same topic), it is likely that one also cites the other. Besides, the triadic closure is also fundamental to the understanding and prediction of network evolution and community growth (Caplow 1968;Bianconi et al. 2014;Zhou et al. 2018).
In this paper, we utilize this triadic closure property as an efficient tradeoff between structured prediction (which considers the whole graph simultaneously but is expensive) and individual link prediction (which is simple but ignores interactions among edges). Specifically, we propose the triad decoder, which predicts the three edges involved in a triad together. The triad decoder can readily replace the vanilla decoder in any graph-based auto-encoder. In particular, we incorporate this into VGAE and GAE, leading to the triad variational graph auto-encoder (TVGA) and triad graph auto-encoder (TGA). Experiments are performed on link prediction, node clustering and graph generation using a number of real-world data sets. The prediction and clustering results are more accurate, and the graphs generated preserve more characteristics of the input graph, demonstrating the usefulness of triads in graph analytics.

Related Work: Graph Auto-Encoder
The variational graph auto-encoder (VGAE) and its nonvariational variant graph auto-encoder (GAE) are introduced in (Kipf and Welling 2016b). Using the variational autoencoder (VAE) framework (Kingma and Welling 2014), they are based on unsupervised deep learning model consisting of an encoder and a decoder.

GCN Encoder
Let the graph be G = (V, E), where V is a set of N nodes, and E is the set of edges. Let its adjacency matrix be A. The encoder is a graph convolutional network (GCN) (Kipf and Welling 2016a), which is a deep learning model for graphstructure data. For a L-layer GCN, the layer-wise propagation rule is given by: H (l) and W (l) are the feature map and weight at the lth layer, respectively, and relu(·) is the ReLU activation function. H (0) is the matrix of node feature vectors X, and H (L) is the (deterministic) graph embedding matrix Z. Often, L = 2 (Kipf and Welling 2016b), leading to the following encoder: (1) In VGAE, the embedding (encoder output) is probabilistic. Let z i be the embedding of node i. It is assumed to follow the normal distribution: where μ i and log σ are outputs from two GCNs that share the first-layer weights. The distribution for all the embedding vectors is then q(Z|X,

Inner Product Decoder
The decoder is often a vanilla model based on the inner product between the latent representations of two nodes. For GAE, the graph adjacency matrixÂ is reconstructed from the inner product of two node embeddings as: where σ is the sigmoid activation function. For the VGAE, the decoder is also based on inner products, but is probabilistic:

Triad Decoder
Based on triadic closure, the presence of a particular edge in a triad is dependent on whether the other two edges are present. Specifically, consider the triad Δ = (i, j, k). Let I ij be the indicator function representing whether nodes i and j are connected (i.e., I ij = 1, if i, j are connected; and 0 otherwise). As the presence of edges (i, j), (i, k), and (j, k) are interrelated, we propose to predict the three edge probabilities {P (I ij |Δ), P (I ik |Δ), P (I jk |Δ)} (denoted {e ij (Δ), e ik (Δ), e jk (Δ)}) together, using as inputs the three embeddings z i , z j , z k , where z i 's are the latent representations of the nodes learned by the graph encoder.

Structure
The structure of the proposed triad decoder is shown in Figure 1. First, we perform 1 × 1 convolution, which corresponds to a linear transform, on the three node embeddings z i , z j , z k . This is followed by the rectified linear (ReLU) nonlinearity, producing the vector z triplet . Its output for the lth dimension is ReLU(w i z il +w j z jl +w k z kl ). Note that this contains information from the whole triad. Vector z triplet is then further nonlinearly transformed by the fully connected (FC) layer and another ReLU nonlinearity. The whole block, which is denoted F, is finally merged with the three inner products constructed from z i , z j , z k . This additional inner product connections serve similarly as the residual connection in residual networks (He et al. 2016). The output of the triad decoder is: When F outputs a zero mapping, it reduces to the standard inner product decoder.

Model Training
The triad decoder can be readily used to replace the decoder in any graph-based auto-encoder. In this paper, we incorporate this into the VGAE and GAE, leading to the triad variational graph auto-encoder (TVGA) and the triad graph auto-encoder (TGA), respectively ( Figure 2). The whole network can be trained end-to-end, and the training procedure is shown in Algorithm 1. The total number of triads in the graph is N 3 , which is large. As is common in deep learning, we use stochastic gradient descent (SGD) or its variants for better scalability. In particular, the popular Adam optimizer (Kingma and Ba 2014) will be employed in the experiments. In each iteration, we sample B triads {Δ 1 , . . . , Δ B } from the graph to form a mini-batch B. The probability for the presence of a particular edge (i, j) in the mini-batch isē where Optimization Objective First, we consider TVGA. Let A ij be the observed graph adjacency matrix. As in (Kipf and Algorithm 1 Training the triad variational graph autoencoder (TVGA) and triad graph auto-encoder (TGA) using SGD. Here, the encoder and decoder parameters are combined and denoted by w. L w ({ē ij }, A, X) is the loss function (for TVGA, it is the negative of (6); for TGA, it is (7)).
1: initialize w 0 ; 2: t ← 0; 3: while w not converged do 4: encode the graph G to latent embedding Z using (1) for TGA and (2)  obtainē ij 's for the triads from (4) and (5); 8: Welling 2016b), this variational model is trained by maximizing the variational lower bound: w.r.t. the encoder parameters (W (1) , W (2) of the GCN) and decoder parameters. Here, the first term is the negative of the graph reconstruction error, while the second term is the Kullback-Leibler divergence between the encoder output distribution for the embeddings (q(·) in (2)) and some prior distribution p(·). In this paper, we assume that the latent dimensions are i.i.d., and follow the standard normal distribution: As for the non-variational version TGA, the Kullback-Leibler divergence is removed from (6) as in (Pan et al. 2018), and only the following graph reconstruction error is minimized: Sampling the Training Triads Real-world networks are typically sparse. If triads are sampled randomly from the graph in step 6 (of Algorithm 1), it is likely that most node pairs in the training triads are disconnected. This resultant high class imbalance can lead to severe performance deterioration for most classifiers.
To alleviate this problem, we construct a more balanced training data set by sampling each triad Δ = (i, j, k) as follows. First, a node i is randomly sampled from the graph. Let N (i) be the set containing all neighbors of i. With probability p, we sample the next node j from N (i); and with probability 1−p, sample j from a faraway node not in N (i). After sampling j, the last node k in the triad is similarly sampled from N (j) with probability p; and from a node not in N (j) with probability 1 − p.
The class imbalance can be controlled by appropriately setting p. First, note that the expected number of connected edges in a triad Δ is E[I ij + I jk + I ik ] = E[I ij ] + P (I ik |observed 2 edges) can be estimated by the global clustering coefficient (Wasserman and Faust 1994), which is defined as the ratio of the number of closed triads (i.e., all three nodes in the triad are connected to each other) to the total number of triads. For P (I ik |observed 1 edge) and P (I ik |observed 0 edge), intuitively, the effect of the presence of one or zero edge on I ik is small. Thus, we simply assume that both probabilities are the same as the prior probability P (I ik ), which can be estimated from the graph density (Lawler 2001). Hence, To construct a balanced training set, the desired p can be obtained by setting the above to 3/2.
Space Complexity VGAE/GAE (Kipf and Welling 2016b) and ARVGA/ARGA (Pan et al. 2018) take the whole graph as input. The space complexities are both O(N 2 ), where N is the number of nodes. For large graphs, the adjacency matrix may not even be able to fit into memory. In contrast, the proposed algorithm is trained on mini-batches of triads. The space complexity is O(max (N, B)), which are much smaller than N 2 and thus much more scalable.

Inference
After training, the learned model can be used on a variety of graph learning tasks. In this section, we focus on link prediction, node clustering and graph generation.

Link Prediction
In link prediction, one wants to predict whether an edge exists between nodes i and j. Recall that the proposed triad decoder predicts all three edges in the whole triad simultaneously, and so the three nodes need to be inputted together.
In constructing these triads during inference, intuitively a node faraway from the node pair (i, j) carries little information. Hence, instead of using both neighboring and faraway nodes to construct triads as in training, we only aggregate predictions from nodes k that are in N (i) ∪ N (j). For each such k, the decoder predicts the probability for each (i, j) edge using (4). The average probability over all these k's is taken as the final probability for the presence of an edge. On using NetGAN for link prediction, one has to first generate a number of random walks and accumulate the corresponding transition counts to an N × N matrix, which is then thresholded to produce the predicted links. Thus, the space and time complexities are both O(N 2 ). In contrast, the proposed algorithm predicts the edge directly by (5) in O(1) time. With N neighbr nodes in the union of neighborhoods of i and j (typically, N neighbr N ), the total complexity is O(N neighbr ). Hence, the proposed algorithm is much more efficient. On the other hand, VGAE/GAE and ARVGA/ARGA only take O(1) space and time. However, as will be seen in the experiments, their link prediction results are much inferior.

Node Clustering
With the learned node embedding, one can apply a standard clustering algorithm to cluster the nodes. Recall that the encoder and decoder in a graph-based auto-encoder are trained together in an end-to-end manner. Hence, though the decoder is not explicitly used in node clustering, an improved decoder (such as the proposed triad decoder) can guide the learning of better node representations in the embedding space.

Graph Generation
TVGA, which is based on the VAE framework, can be used to generate graphs. TGA, on the other hand, is not probabilistic and cannot be used for graph generation.
Let N be the target number of nodes to be generated. We first randomly sample N z i 's from the posterior (normal) distribution of TVGA in the latent space. We then randomly sample K triads from these z i 's. For each triad, (4) is used to predict the probabilities for the three constituent edges. Finally, the predictions are averaged over all K triads, and stored in an estimated adjacency matrixÂ. To ensure symmetry, we replace each entryÂ ij ofÂ by (Â ij +Â ji )/2.
We assume that the generated graph has to be connected. Inspired by NetGAN, the following strategy is used to generate such a graph fromÂ. First, for every node i, we sample an edge e ij to node j with probability p ij = A ij / N k=1Â ik , and add it to the graph if it is new. Afterwards, we continue adding edges to the graph until the

Experiments
In this section, we demonstrate the performance of the proposed algorithm on link prediction, node clustering and graph generation. Experiments are performed on three standard benchmark citation graph data sets 1 (Sen et al. 2008): Cora, Citeseer, and Pubmed (Table 1). Each node represents an article, and has a boolean feature vector whose entries indicate whether a specific word occurs in the article. Each node also has a label, indicating the class it belongs to. The edges are citation links. We treat the graphs as undirected graphs, and all self-loops are removed. Moreover, we only use the largest connected component in each graph.

Link Prediction
In this experiment, 85% of the edges and non-edges (unconnected nodes) from each graph are randomly selected to form the training set, another 10% is used as the validation set, and the remaining 5% as testing set. The proposed algorithm uses a mini-batch size of 5,000. Adam (Kingma and Ba 2014) is the optimizer, with a learning rate of 0.0005. Both the hidden layer and embedding layer of the encoder have 32 hidden units. The convolution layer in the triad decoder has 4 filters (i.e., the dimension of z triplet is 1 × 32 × 4).
Triad Sampling Scheme First, we study how the proposed sampling scheme alleviates the class imbalance problem. Figure 3 shows the proportion of existent edges in the triads, with different sampling probabilities p.
With random sampling (yellow dot in the figure), the ratio of existent edges is very small, and the data set is highly imbalanced. As expected, using a larger p means that node j is more likely to be connected to node i, and node k is more likely to be connected to node j, leading to a higher proportion of edges being observed in the sampled triads. The red dot corresponds to the p value obtained by the proposed sampling scheme. As can be seen, the ratios of existent edges are 1 http://www.cs.umd.edu/ ∼ sen/lbc-proj/LBC.html all close to 0.5 on the three data sets, indicating that the proposed sampling scheme has effectively alleviated the class imbalance problem.
Comparison with the State-of-the-Art The proposed algorithm (using both random triad sampling and the proposed sampling scheme) is compared with the following baselines: (i) node2vec ( (3) is then used to obtain edge probabilities. NetGAN generates random walks and accumulates the corresponding transition counts, which are used to measure how likely there is an edge between two nodes. Note that node2vec, SC and NetGAN do not make use of node features. The other four baselines use the graph convolutional network (Kipf and Welling 2016a) as encoder.
In particular, ARVGA and ARGA are modified from VGAE and GAE, respectively, by adding a discriminator that are trained adversarially.
For performance evaluation, we use the area under the ROC curve (AUC) and average precision (AP) as in (Kipf and Welling 2016b).
Results are shown in Table 2. As can be seen, node2vec, SC and NetGAN, which do not utilize node features, have the worst performance. TVGA and TGA outperform the other VAE-based methods, showing that triad information leads to more accurate predictions. Moreover, the proposed triad sampling scheme performs significantly better than random triad sampling (TVGA(rand) and TGA(rand)). Hence, we will only experiment with the proposed triad

Node Clustering
In this section, we consider the unsupervised task of clustering nodes in the graph. We perform clustering on the obtained node embeddings using the K-means clustering algorithm, where K is set to be the number of classes in Table 1. The following baselines are compared with the proposed algorithm: (i) node2vec; (ii) spectral clustering (SC); (iii) text-associated DeepWalk (TADW) (Yang et al. 2015); (iv) VGAE; (v) GAE; (vi) ARVGA; and (vii) ARGA. SC is a general clustering algorithm, while TADW is designed specifically for graphs. We do not compare with SEAL and NetGAN, since they do not produce node embeddings for clustering. The node labels in Table 1 are used as ground-truth clustering labels. For performance evaluation, we follow (Xia et al. 2014) and first match the predicted labels with the ground-truth labels using the Munkres assignment algorithm (Munkres 1957), and then report the (i) accuracy (acc); (ii) normalized mutual information (NMI); (iii) F1-score (F1); (iv) precision; and (v) adjusted rand index (adj-RI). As in (Pan et al. 2018), we only evaluate on the Cora and Citeseer data sets.
Results on Cora and Citeseer are shown in Tables 3 and 4. TVGA and TGA outperform the other methods on both data sets across all metrics. SC does not perform well, as it does not utilize node features and is not designed for graphs.

Graph Generation
In this experiment, we train the model on an input graph, and then try to generate similar graphs. Following (Bojchevski et al. 2018), we only experiment on the Cora and Citeseer data sets. Moreover, as NetGAN can only generate graphs with the same number of nodes as the input graph, we set the numbers of nodes and edges to be generated to be equal to those in the input graph.
The following baselines are compared with the proposed model: (i) configuration model (conf. model) (Molloy and Reed 1995); (ii) degree-corrected stochastic block model (DC-SBM) (Karrer and Newman 2011); (iii) Net-GAN 3 ; (iv) GraphRNN (You et al. 2018); (v) variational graph auto-encoder (VGAE); and (vi) adversarially regularized variational graph auto-encoder (ARVGA). The configuration model and DC-SBM are classic graph generation algorithms, which model certain graph statistics directly. NetGAN generates graphs via accumulating random walks. GraphRNN generates nodes sequentially. Besides, note that the configuration model, DC-SBM, NetGAN and GraphRNN do not utilize node features. Moreover, we do not compare with GraphVAE (Simonovsky and Komodakis 2018) and the graph neural network based model in (Li et al. 2018), as they can only be used on very small graphs.
As in (Bojchevski et al. 2018), performance is evaluated by a number of statistics measured on the generated graph. These include the Gini coefficient, maximum degree, num-   Figure 4: An original subgraph from Cora, and the corresponding subgraphs generated by various methods.
ber of triangles, assortativity (i.e., Pearson correlation of degrees of connected nodes), power law exponent (i.e., exponent of the power law distribution for degrees), clustering coefficient (as defined in NetGAN), and characteristic path length (i.e., average number of steps along the shortest paths for all node pairs). Tables 5 and 6 show the results on Cora and Citeseer. Though the configuration model and DC-SBM excel at some metrics that they directly model (such as "maximum degree" and "power law exponent"), they fail to reproduce others. GraphRNN does not perform well. It has to be trained on all breadth-first-search orderings (which can be in the order of O(|V |!)). In (You et al. 2018), GraphRNN has only been trained on small graphs with a maximum of 500 nodes (while the Cora and Citeseer data sets here are much larger). The rightmost columns in Tables 5 and 6 show the average rank of each method over all statistics. TVGA, by utilizing both pairwise node information and triadic structure, ranks the highest and generates graphs with similar statistics to the original one (Hamilton, Ying, and Leskovec 2017). Figures 4 and 5 show parts of the generated graphs. As can be seen, the graphs generated by TVGA are more similar to the original graphs than the others. For example, in Figure 4, both the input and TVGA-generated graphs have three dominant clusters. However, this is not obvious in the other graphs generated. Similarly, in Figure 5, one can observe three dominant clusters (arranged in a triangle) in both the input and TVGA-generated graphs, but not in the others.

Conclusion
In this paper, we proposed a novel triad decoder that uses the whole local triad information, and is able to model the triadic closure property that is fundamental in real-world networks. It can be readily used in any graph-based auto-encoder. Experimental results show that the proposed decoder, when used with the (variational) graph auto-encoder, outperforms the state-of-the-art on link prediction, node clustering and graph generation tasks.