Title: CONDITIONAL GRAPH NEURAL FIELDS

Abstract: Graph convolutional networks have achieved tremendous success in the tasks of graph node classification. These models could learn a better node representation through encoding the graph structure and node features. However, the correlation between the node labels are not considered. In this paper, we propose a novel architecture for graph node classification, named conditional graph neural fields (CGNF). By integrating the conditional random fields (CRF) in the graph convolutional networks, we explicitly model a joint probability of the entire set of node labels, thus taking advantage of neighborhood label information in the node label prediction task. Our model could have both the representation capacity of graph neural networks and the prediction power of CRFs. Experiments on several graph datasets demonstrate effectiveness of CGNF.

1. INTRODUCTION:

Graph is an expressive representation for diverse datasets. Node classification on graphs has many real world applications. For example, to classify publications we build citation networks where publications are nodes and the research fields are node labels (Hamilton et al., 2017) . To study the protein-disease relations we could construct protein-protein interaction (PPI) graphs where each protein is a node and diseases are treated as node labels. Node classification on graphs is a general task that creates knowledge and has real social impact, e.g., by exploring the similarities between proteins, we can learn novel protein target for treating diseases and use that knowledge to facilitate drug repurposing and safety monitoring (Zitnik et al., 2018; Ma et al., 2018) .

Many earlier works take connectivity-based approaches to classify nodes, which mainly operate on the graph structure alone. The underlying assumption is that nodes that are closely connected in the graph should have similar labels. Among the most successful connectivity-based methods are node embedding techniques including (Perozzi et al., 2014; Grover & Leskovec, 2016a; Tang et al., 2015a; Hamilton et al., 2017; Kipf & Welling, 2016) . More recently, features of neighboring nodes are included in learning node embedding. These feature-based approaches incorporate graph connectivities via regularization (Zhu et al., 2003; Belkin et al., 2006) or aggregation over local neighborhoods (Defferrard et al., 2016; Kipf & Welling, 2017; Chen et al., 2018a) . Among them, the graph convolutional networks (GCN) become one of the most successful methods of node embedding for arbitrary graphs with node features (Kipf & Welling, 2017; Defferrard et al., 2016; Hamilton et al., 2017; Chen et al., 2018a) .

Although GCN gets good node embeddings and node classification performance via aggregating node features and graph connectivities, the correlation of node labels was not exploited. In practice, the labels of neighborhood nodes in a graph are often mutually impacted. For example, in citation networks the labels (fields of research) for neighborhood nodes (publications) are often consistent: a paper citing another tends to appear in similar or related fields to the cited one. Unfortunately, we are not able to simply treat labels as additional node features because label information are not available in test set. Instead, the key question is how to leverage label correlation in addition to node features in node classification.

We notice that energy-based approaches such as the conditional random fields (CRF) (Lafferty et al., 2001) are desirable for capturing structured labels including correlation of node labels. However, they may involve non-trivial optimization to perform predictions.

In this paper we propose a new deep architecture to extend the GCN by defining an energy function to capture the dependencies between labels for better node embedding and classification. In particular, 

2. BACKGROUND:

Graph Convolutional Networks Over the past few years, several graph convolutional network models emerged to compute informative node feature representations for arbitrary graphs (Kipf & Welling, 2017; Defferrard et al., 2016; Hamilton et al., 2017; Chen et al., 2018a) . GCN models learn node embeddings in the following manner: Given each graph node initially attached with a feature vector, the embedding vector of each node are the transformed weighted sum of the feature vectors of its neighbors. All nodes are simultaneously updated to perform a layer of forward propagation over neural networks. The deeper the network, the larger the local neighborhood. Thus global information is disseminated to each graph node for learning better node embeddings. Specifically, given an undirected graph with input features matrix of nodes X and adjacency matrix of the underlying graph A, a multi-layer neural network is constructed on the graph with the following layer-wise propagation rule:

EQUATION

where Ã = A + I is the adjacency matrix with self-connections. I is the identity matrix, D is a diagonal matrix such that Dii = j Ãij , W (l) is a layer-specific parameter matrix, H (l) is the node representation in the l th layer, H (0) = X, and σ is an activation function (e.g. ReLU or sigmoid). However, labels and label correlation is not modeled in GCN.

Conditional Random Fields The conditional random fields (CRF) is an undirected probabilistic graphical model commonly used for structured prediction tasks, e.g. named entity recognition and image segmentation. Formally, given input feature x ∈ R d , CRF aims at finding the label set y that maximizes the conditional probability P (y|x). In particular, CRF defines a joint probability over cliques {x c } in the graph. A clique is any fully connected subset of the the graph. CRF represents P (y|x) as a product of clique potential Φ c (x c , y c ). Each potential function Φ c depends only on part of the feature input x denoted as x c and a label subset y a . This factorization can allow us to represent P (y|x) much more efficiently (Sutton et al., 2012) . By making sure the factorization form of P (y|x) sum to 1, partition function Z(x) is used for normalization use as follows:

EQUATION

where Z(x) = y c c Φ a (x c , y c ) is a normalizer required for a valid probability distribution.

3 CGNF METHOD

3.1. TASK FORMULATION:

Consider the problem of multi-class node classification. The input graph G = {X, Y , A} includes node feature matrix X, adjacency matrix A, and the output node label matrix Y . More specifically, we have

X = [x 1 , x 2 , • • • , x N ] ∈ R N ×D and Y = [y 1 , y 2 , • • • , y N ] ∈ R N ×M

, where N is the number of nodes in the graph, D is the dimension of node features, and M is the number of distinct labels. The i th node has a feature vector x i , and a one-hot label vector y i . The graph connectivity is specified through the adjacency matrix A ∈ R N ×N , where A i,j ∈ A indicates the edge weight 

Y ∈ R N ×M label vectors for all nodes A ∈ R N ×N ; Â ∈ R N ×N graph adjacency matrix; a normalized version of A f (•) graph convolutional networks (GCN) H ∈ R N ×M ; h i ∈ R M GCN prediction probability distribution; row i of H W 0 ∈ R D×S , W 1 ∈ R S×M learnable weight matrix of GCN Z(•) partition function N (i) neighbor node set of node i E(•) energy function ψ(•); φ(•) unary potential of E; pairwise potential of E U ∈ R M ×M

learnable correlation weight matrix between node i and node j. We follow convention to denote Â = D-1 2 Ã D-1 2 as a normalized version of Ã, which will be used in our model later.

We follow the traditional setting of GCN and formalize the learning in semi-supervised setting where we assume we observe the labels Y tr only for some of the nodes X tr . Our goal is to predict the labels Ŷte for other unlabeled nodes X te . To start with, we consider {X tr , Y tr , A tr } as training set, and {X te , Y te , A te } as test set.

3.2. THE CGNF MODEL:

Given input graph G = {X, Y , A} as previous described, our goal is to predict node labels Y for graph G. We can learn node embeddings and use them to make such predictions. In this paper, we follow (Kipf & Welling, 2017) and use a two-layer GCN model given by Eq. 3.

EQUATION

Here W 0 ∈ R D×S , W 1 ∈ R S×M are weight parameters of GCN. Softmax function is applied rowwise to make each row {h i } N 1 of GCN prediction H ∈ R N ×M . However, the training of GCN is conditionally independent for each node, and label correlation is ignored by this model.

To fill this gap, we aim to integrate label correlations into the GCN model. Energy based models, such as CRF, are flexible ways to define the variable dependencies. So in a general graph, considering both the impact of node features and label dependency, we can define the energy function as belows.

E(Y , X, A) = E c (Y c , X c , A) = i ψ(y i , x i ) + γ (i,j)∈E,i<j φ(y i , y j , A i,j ) (4)

where c is a clique, E ∈ R M is the edge set, the unary potential ψ(•) is designed to measure the compatibility between observed node x i and its label y i ; and pairwise potential φ(•) is meant for capturing label correlation; γ is a mixture weight. With this energy function, we can derive the Gibbs distribution, i.e. the conditional probability P (Y |X, A) as given by Eq. 5.

EQUATION

where Z = Y ∈Y exp(-E(Y , X, A)) is the normalizer (or called partition function), E is the energy function which is an indicator of the likelihood of the corresponding relationships within the clique, with a higher energy configuration having lower probability; Y is the label space consisting of unique label assignments Y . Then our objective is to maximize this conditional probability.

To enhance Eq. 4 by the neural network representations of GCN, the energy function can be reformulated as:

E(Y , X, A) = i ψ(y i , h i ) + γ (i,j)∈E,i<j φ(y i , y j , Âi,j ) (6)

where h i is the previously mentioned GCN prediction H on node i and Âi,j is an element in the normalized adjacency matrix Â. Separating the energies for each node, we can further express the energy function as Eq. 7.

E(Y , X, A) = i   ψ(y i , h i ) + γ 2 j∈N (i) φ(y i , y j , Âi,j )   (7)

where N (i) is the neighborhood of node i. Here, we focus on node i. Initially, node i in graph has its input feature x i and is connected to other node such as node j with edge weight denoted as A i,j . First and second order neighbor nodes of node i are utilized in two-layer GCN setting to generate graph prediction probability h i ∈ H using Eq. 3 and at the meantime we can get normalized graph adjacency matrix Â. Then we utilize specific designed graph-based energy function in Eq. 7 consisting of unary and pairwise potential in Eq. 8 to make accurate node classification using Eq. 13.

Specifically, in a graph we define the unary potential for node i as the prediction loss of GCN, denoted as ψ(y i , h i ). We also define the pairwise potential between node i and node j as φ(y i , y j , Âi,j ), which is impacted by two factors: the normalized edge weights Âi,j and label correlation weights U yi,yj . The two potential functions are computed as Eq. 8.

EQUATION

φ(y i , y j , Âi,j ) = -2 Âi,j U yi,yj

where y i and y j are the corresponding label index of label vector y i and y j ; and U yi,yj ∈ U is the learnable correlation/transition weight between label y i and y j .

Like in the traditional CRF, when all components for conditional probability in Eq. 5 are introduced throughly above, a common way is to use negative log likelihood as training objective function in Eq. 9 to find optimal parameters like W 0 , W 1 , U :

-log P (Y |X, A) = E(Y , X, A) + log Z(X, A) (9) = E(Y , X, A) + log Y exp(-E(Y , X, A))

Using the energy based conditional probability, the inference of new labels is comparably easy in this model. Notice that in Eq. 9 Since P (Y |X, A) ∝ exp(-E(Y , X, A)), after getting the parameters in the training phase, the inference of the test labels will simply be min Y E(Y , X, A). However, how to optimize the parameters by minimizing the negative log likelihood is a great challenge. The computation of the normalizer Z(X, A) is often intractable, which causes a big problem in training.

In the next section, we will introduce two ways to solve the problem.

3.3. PARAMETER OPTIMIZATION:

In this section, we introduce the training ( parameter optimization) for CGNF. It is implemented on the training data Y tr , X tr , A tr , but for simplicity here we omit the subscripts for all Y , X, A.

As we know, exact minimization of the energy based function Eq. 9 is intractable. So we consider a simple but effective approximation method, the pseudo likelihood method. A pseudo likelihood (Besag, 1975) provides a good approximation of the joint probability. Use of the pseudo likelihood (PL) in place of the true likelihood function in a maximum likelihood analysis can lead to good estimates.

EQUATION

where N (i) are the neighbors of node x i . The pseudo likelihood has the significant advantage that it only requires normalizing over the possible labels at one node. It could reduce the computation complexity of the normalizer from O(M N ) to O(M N ).

Recall the conditional probability given by Eq 5 and Eq 7, for each node x i , the conditional probability given its neighborhood is calculated as follows:

P (y i |y N (i) , X, A) = exp(-ψ(y i , h i ) -γ j∈N (i) φ(y i , y j , Âi,j ) y i (exp(-ψ(y i , h i ) -γ j∈N (i) φ(y i , y j , Âi,j )) (11) = exp(-log p(y i |h i ) -2γ j∈N (i) Âi,j U yi,yj y i (exp(-log p(y i |h i ) -2γ j∈N (i) Âi,j U y i ,yj )

y i is all the possible label for node x i . Notice here we do not have the 1 2 coefficient on the pairwise potential, as we need to extract all dependent potentials of node x i .

The new training objective, i.e. the negative log pseudo-log-likelihood, becomes the following form:

-log P L(Y |X, A) = i -log P (y i |y N (i) , X, A) = (12) i   ψ(y i , h i ) + γ j∈N (i)

φ(y i , y j , Âi,j ) + log

y i (exp(-ψ(y i , h i ) -γ j∈N (i) φ(y i , y j , Âi,j ))   = - i,k (Y log H) i,k -2γ i,j,i =j ( Â (Y U Y T )) i,j + i log k (H exp(2γ ÂY U )) i,k

where i is the index of training nodes; (•) i,j is the element of a matrix at row i and column j; and indicates element-wise multiplication.

3.4. INFERENCE OF TEST LABELS FOR CGNF:

In the previous section, we introduced how to train the model and get the optimized parameter estimation. As we explained in 3.2, after getting the model parameters, next the inference for new labels can be performed by optimizing Eq. 13.

min Ŷte E( Ŷte , X, A, Y tr ) = min Ŷte   -log p( Ŷte |H) -γ i =j ( Â ( Ŷ U Ŷ T )) i,j   (13)

where Ŷ = concatenate(Y tr , Ŷte ). To find the minimum value we have to find the "best" test labels, which is exponentially complex. Hence we approximate the inference in two ways. The simplest way is not to consider the correlation between test labels just use training labels to infer one test label each time.

y i = arg min yj E(y i , Y tr , X, A) = arg min j [-log(h i ) -2γ Âtr Y U T ] j (14)

Alternatively, we could use a dynamic-programming-style (DP) method to find the minimum. We randomly select a test node as the start and randomly permute the other test nodes. Then we can do beam search along the order of the permuted test nodes (each beam search with beam size K can get K best sets and we select just the best one). Let us repeat this process T times, and then we compare all the T beam-search results and select the best one. Then we can just select one best according to their energy. The inference time in this case will be linear. The algorithm is summarized below.

Algorithm 

as {z i } |Ytr| 1

where z i is the new index for node i;

for i = 1 to |Y te | do for all Ŷ1:i ∈ B do { Ŷ1:i } ← extend { Ŷ1:i-1 } with y i ∈ label set Y ; Append topK({ Ŷ1:i }) using E into B; end for B ← topK(B); end for t ← t + 1; Compute current minimum energy score s ← min Ŷ ∈B E(X, A, Y tr , Ŷ ); Compute current best output Y * c ← arg min Ŷ ∈B E(X, A, Y tr , Ŷ ); if s ≤ s then s ← s ; Y c ← Y * c ; end if end while return Ŷ * ← Y c ;

3.5. INDUCTIVE LEARNING ACROSS GRAPHS:

Following the framework of GCN, our node classification task is essentially a semi-supervised learning task in one fixed graph. However, sometimes we have several graphs which do have connection with each other. In this case we can conduct an inductive learning for CGNF. Compared with semisupervised setting, the only difference of inductive learning is that we cannot see the test nodes in the training phase. Thus we need to predict H tr only based on the training nodes X tr and their adjacency matrix A tr . Then we can still use Eq. 13 for training.

For inference of the test labels, as we lose the connections between training nodes and test nodes, so the trainings labels cannot directly impact the inference of test labels. In fact, we can still form a graph containing both training data and test data, however A i,j = 0 for training node i and test node j. So the pairwise potential between training nodes and test nodes will also become 0 according to Eq. 8. So Eq. 14 is not useful anymore, because the pairwise potential becomes 0 if we just utilize the training labels for inference. Instead, in this case we will use the DP-style inference.

4. EXPERIMENTS:

Data We evaluated the effectiveness of CGNF on the following benchmark tasks: (1) classifying research topics using the Cora citation dataset (McCallum et al., 2000) ; (2) categorizing academic papers with the Pubmed database; (3) classify research areas using the Citeseer citation dataset (Sen et al., 2008) ; and (4) classifying protein functions across various biological protein-protein interaction (PPI) graph (Borgwardt et al., 2005) . Implementation details are in A.3 in Appendix. Baselines To evaluate the effectiveness of our method, we compare with the following baselines.

• GCN (Kipf & Welling, 2017) learns latent representations by encoding graph structure and node features. It demonstrated significant improvement in semi-supervised node classification tasks.

• GraphSAGE (Hamilton et al., 2017) is an inductive variant of GCN which can generate node embedding for unseen data by sampling and aggregating features from a node's local neighborhood.

• FastGCN (Chen et al., 2018a) enhanced GCN with inductive ability and efficiency by interpreting graph convolutions as integral transforms of embedding function under probability measures. Monte Carlo approaches were used to estimate integrals and lead to batched training scheme.

• DeepWalk (Perozzi et al., 2014) learns node embedding by extracting node sequence from graph using truncated random walks. Skip-gram method is also utilized to maximum the conditional probability of neighbor nodes given context node. It is a state-of-the-art graph embedding method that showed effectiveness on large-scale social networks classification datasets.

• LINE (Tang et al., 2015b) is the follow-up method of DeepWalk. It considers both first-order proximity and second-order proximity by maximizing the joint probability between nodes.

• Node2Vec (Grover & Leskovec, 2016b ) is a variant of DeepWalk by introducing two additional hyper-parameters q, p to control transition probability of random walk. They approximate best first search and depth first search behavior for learning more informative representations.

For semi-supervised learning, we used the same setting for all the baselines, i.e. training the node embedding using all node features from both training data and test data. While for inductive learning, we use node features only from training data. 

4.1. RESULTS:



As shown in:



5. RELATED WORKS:

The connectivity-based node classification approaches operate on the graph structure alone. Among the most successful connectivity-based methods are node embedding techniques including (Perozzi et al., 2014; Grover & Leskovec, 2016a; Tang et al., 2015a; Hamilton et al., 2017; Kipf & Welling, 2016 ). An underlying assumption of these techniques is that nodes which are closely connected in the graph, should have similar labels. In the feature-based setting the graph structure can be incorporated in different ways, for instance by using regularization (Zhu et al., 2003; Belkin et al., 2006) , combining attributes with node embeddings, or aggregating them over local neighborhoods (Defferrard et al., 2016; Kipf & Welling, 2017; Chen et al., 2018a) .

Incorporating probabilistic graphical model like conditional random fields (CRF) and neural networks is one possible approach to tackle structured prediction task in different domains. Initial works such as CNF (Peng et al., 2009) and NeuroCRF (Do & Artieres, 2010) yielded powerful models by adding neural networks layer after CRF's input. Similar idea shown in (Chen et al., 2018b) which applied CRF inference as a post-processing step after the training of deep convolutional neural networks for image segmentation task. Another line of works tried to integrate CRF with deep neural networks in end-to-end form see (Zheng et al., 2015; Ma & Hovy, 2016; Long et al., 2018; Vemulapalli et al., 2016) . For example, (Zheng et al., 2015) formulated CRF with Gaussian pairwise potentials and mean-field approximate inference (Krähenbühl & Koltun, 2011) in recurrent neural networks way in image segmentation task, and for sequence labeling tasks, (Ma & Hovy, 2016 ) used a sequential CRF on top of DNNs to jointly decode labels for the whole sentence.

In addition, in Appendix, we also built a connection between CGNF and the graph based semisupervised models.

6. CONCLUSION:

In this paper we propose CGNF that extends GCN by defining an energy function to capture the dependencies between labels for better node embedding and classification. We proposed efficient ways to make the learning of CGNF tractable. Compared with GCN, the proposed model gained significant performance increase. Future direction includes exploring other efficient approximation method for training (such as mean-field inference) and applying this energy based framework to other graph neural networks.

:



Figures and Tables:

Figure 1: Graphical structure of CGNF.Here, we focus on node i. Initially, node i in graph has its input feature x i and is connected to other node such as node j with edge weight denoted as A i,j . First and second order neighbor nodes of node i are utilized in two-layer GCN setting to generate graph prediction probability h i ∈ H using Eq. 3 and at the meantime we can get normalized graph adjacency matrix Â. Then we utilize specific designed graph-based energy function in Eq. 7 consisting of unary and pairwise potential in Eq. 8 to make accurate node classification using Eq. 13.

we model the pairwise label relation with a pairwise energy function and propose a new model integrating graph node embedding and conditional random fields. The proposed model, coined conditional graph neural fields (CGNF), has the following contributions: • CGNF is the first work that bridges GCN and CRF to directly capture label correlations for more accurate node classification in graphs. Experimental results on several graph datasets demonstrated the advantage of CGNF over several baselines including GCN. • We designed a specific graph-based energy function and proposed an efficient way for approximate training as well as two efficient inference schemes for predicting test labels. • Experimental results on several graph datasets demonstrate our advantage over other graph neural networks such as GCN.

Table content: <table/>

Notation references

Table content: <table><tr><td>Notation</td><td>Definition</td></tr><tr><td>G : {X, Y , A}</td><td>the whole graph data</td></tr><tr><td>X ∈ R N ×D</td><td>node feature matrix</td></tr><tr><td>Y</td><td>label space consisting of unique label assignments</td></tr></table>

1 Inference CGNF with dynamic programming Input: Node feature matrix X, adjacency matrix A, times T and beam size K, energy function E; Output: Estimated best output Ŷ * ; Initialize process times t ← 0; energy function score s ← inf; candidate output Y

Table content: <table/>

Dataset Statistics

Table content: <table><tr><td>Dataset</td><td>Nodes</td><td colspan="4">Edges Classes Features Training/Validation/Test</td></tr><tr><td>Cora</td><td>2, 708</td><td>5, 429</td><td>7</td><td>1, 433</td><td>140/500/1000</td></tr><tr><td colspan="3">Pubmed 19, 717 44, 338</td><td>3</td><td>500</td><td>60/500/1000</td></tr><tr><td colspan="2">Citeseer 3, 327</td><td>4, 732</td><td>6</td><td>3, 703</td><td>120/500/1000</td></tr><tr><td>PPI</td><td colspan="2">43,471 81,044</td><td>3</td><td>50</td><td>120/500/1000</td></tr></table>

CGNF is compared to a variety of high-performing baselines on a selection of benchmark graph node classification tasks. Results show CGNF models achieve the highest accuracy among all baselines with respect for all semi-supervised scenarios.

Table content: <table><tr><td>For skip-gram based methods including DeepWalk, Node2Vec and LINE, they perform worse than</td></tr><tr><td>GCN-based models due to these methods are all inherently unsupervised learning methods with</td></tr><tr><td>post-processing supervised classifiers. As a contrast, GCN-based methods combine semi-or super-</td></tr><tr><td>vised classification which can embed richer graph information to yield better performance. Notice</td></tr><tr><td>that since GraphSAGE learns inductively, on Cora, Pubmed, and Citeseer it yields slightly lower</td></tr><tr><td>accuracy than GCN.</td></tr></table>

Performance Comparison(micro-F1).

Table content: <table><tr><td>Methods</td><td colspan="4">Cora Pubmed Citeseer PPI (inductive)</td></tr><tr><td>GCN</td><td>.813</td><td>.790</td><td>.709</td><td>.488</td></tr><tr><td>GraphSAGE</td><td>.766</td><td>.779</td><td>.657</td><td>.524</td></tr><tr><td>FastGCN</td><td>.778</td><td>.778</td><td>.680</td><td>.481</td></tr><tr><td>DeepWalk</td><td>.753</td><td>.723</td><td>.479</td><td>NA</td></tr><tr><td>Node2Vec</td><td>.743</td><td>.727</td><td>.517</td><td>NA</td></tr><tr><td>LINE</td><td>.620</td><td>.619</td><td>.355</td><td>NA</td></tr><tr><td colspan="2">CGNF PL(no DP) .832</td><td>.792</td><td>.722</td><td>NA</td></tr><tr><td>CGNF PL(DP)</td><td>.823</td><td>.794</td><td>.716</td><td>.491</td></tr></table>

Peer review (iclr2019):
 This paper proposes a conditional graph neural network to explore the label correlation. In fact, this method combines graph convolutional neural network and CRF together. The novelty is incremental. No new insight is provided toward this topic. For experiments, how did you train DeepWalk (Node2vec)? By using all nodes or the selected training set? It should be clarified in the paper. Additionally, Table 3 says the result of semi-supervised methods. But how did you conduct semi-supervised learning for DeepWalk or Node2vec? =================== After feedback: Thanks for authors* feedback. Some of my concerns have been addressed. But the novelty is still not significant. On the other hand, the dataset used in this paper is simple. Specifically, at least the first 3 datasets are single-label and the number of classes is not large. They are too simple to support the claim. It*s better to use multi-label datasets to show that the proposed method can really capture the correlation of labels.