---
abstract: 'Graph Convolutional Neural Networks (GCNNs) extend classical CNNs to graph data domain, such as brain networks, social networks and 3D point clouds. It is critical to identify an appropriate graph for the subsequent graph convolution. Existing methods manually construct or learn one fixed graph for all the layers of a GCNN. In order to adapt to the underlying structure of node features in different layers, we propose dynamic learning of graphs and node features jointly in GCNNs. In particular, we cast the graph optimization problem as distance metric learning to capture pairwise similarities of features in each layer. We deploy the Mahalanobis distance metric and further decompose the metric matrix into a low-dimensional matrix, which converts graph learning to the optimization of a low-dimensional matrix for efficient implementation. Extensive experiments on point clouds and citation network datasets demonstrate the superiority of the proposed method in terms of both accuracies and robustness.'
author:
- |
    Jiaxiang Tang, Wei Hu, Xiang Gao, Zongming Guo\
    Institute of Computer Science and Technology, Peking University, China\
    {hawkey1999, forhuwei, gyshgx868, guozongming}@pku.edu.cn
nocite: '[@*]'
title: Joint Graph and Feature Learning In Graph Convolutional Neural Networks 
---

=1

Introduction {#sec:intro}
============

Graph Convolutional Neural Networks (GCNNs) have been receiving increasing attention as a powerful tool for irregularly structured data on graphs, such as citation networks, social networks and 3D point clouds. The construction of an appropriate graph topology plays a critical role in GCNNs for efficient feature learning. In settings where the graph is inaccurate or even not readily available, it is necessary to infer or learn a graph topology from data before it is used for guiding graph convolution in GCNNs.

Most of the previous studies construct underlying graphs from data empirically, such as $k$-Nearest-Neighbor ($k$-NN) graphs [@wang2019dgcnn; @te2018rgcnn], which may lead to sub-optimal solutions. Few methods exploit *graph learning* for optimized representation [@Jiang2018GraphLN; @li2018adaptive; @shi2018non; @li2019spatio], which learns a fixed and shared graph for all instances, or an individual graph for each instance, or a combination of shared and individual graphs. However, only *one fixed* graph is learned and applied to all layers of the entire network, which may not well capture the underlying structure of node features in different layers dynamically.

Extending on these previous studies, we propose a Joint Learning Graph Convolutional Network (JLGCN), which exploits *dynamic* learning of graphs and node features *jointly* in GCNNs. In particular, we optimize an underlying graph kernel from data features via distance metric learning that characterizes pairwise similarities of data. We deploy the *Mahalanobis distance* [@mahalanobis1936], which takes into account data correlations for intrinsic representation. Given a K-dimensional feature vector $\mathbf{f}_i$ per node $i$, $\mathbf{f}_i \in \mathbb{R}^K$, the Mahalanobis distance between the features $\mathbf{f}_i$ and $\mathbf{f}_j$ of nodes $i$ and $j$ is defined as: $d_{\mathbf{M}}(\mathbf{f}_i,\mathbf{f}_j)=\sqrt{(\mathbf{f}_i - \mathbf{f}_j)^{\top} \mathbf{M} (\mathbf{f}_i - \mathbf{f}_j)}$, where $\mathbf{M} \in \mathbb{R}^{K \times K}$ is the Mahalanobis distance metric matrix which reflects feature correlations. Hence, we convert the problem of graph learning to the optimization of $\mathbf{M}$. As $\mathbf{M}$ is positive semi-definite (PSD), it is often nontrivial to solve efficiently. Instead, we decompose it as $\mathbf{M} = \mathbf{R} \mathbf{R}^{\top}$ and learn $\mathbf{R}$ for ease of optimization, where $\mathbf{R} \in \mathbb{R}^{K \times S}$ has a lower dimension $S<<K$ to reduce number of parameters for efficient implementation. Given features $\mathbf{f}$, we seek to minimize the Graph Laplacian Regularizer (GLR) [@shuman2013emerging] $\mathbf{f}^{\top}\mathbf{L}(\mathbf{R})\mathbf{f}$ by optimizing $\mathbf{R}$, which measures the smoothness of features $\mathbf{f}$ with respect to the graph Laplacian $\mathbf{L}$[^1]. This essentially enforces the graph encoded in $\mathbf{L}(\mathbf{R})$ to capture pairwise similarities of $\mathbf{f}$. Hence, we formulate the joint learning of graphs $\mathbf{L}(\mathbf{R})$ and node features $\mathbf{f}$ as an optimization problem, which minimizes a weighted sum of the GLR and cross-entropy. We set this objective as the loss function of the proposed JLGCN to guide network model optimization, which employs a localized first-order approximation of spectral graph convolution as in [@Kipf2016SemiSupervisedCW]. Further, the learned graph at the previous layer is added to that of the current layer for multi-level feature learning. The proposed JLGCN can be integrated into any GCNN architecture for applications such as node classification and graph classification. To validate the effectiveness of the proposed JLGCN, we apply it to semi-supervised learning for citation networks and 3D point cloud learning problems. Extensive experimental results demonstrate the superiority and robustness of JLGCN compared with state-of-the-art methods on four datasets even with a small model size.

Our contributions can be summarized as follows:

-   We propose joint learning of underlying graphs and node features at each layer of a GCNN, which captures pairwise similarities of node features dynamically.

-   We cast the graph learning problem as distance metric learning with the Mahalanobis distance deployed. We further decompose the distance metric into a low-dimensional matrix for efficient implementation, which is optimized from both the GLR and cross entropy along with node features.

-   Extensive experiments on semi-supervised learning and point cloud classification demonstrate the superiority and robustness of our method.

Related Work {#sec:related}
============

Graph Convolution Neural Networks
---------------------------------

As a generalization of CNNs to irregular graph domain, GCNNs can be categorized into two main classes: spectral methods and spatial methods.

### Spectral methods

This class of methods define graph convolution based on the spectral representation of graphs. [@bruna2013spectral] defines the convolution in graph Fourier transform domain by eigen-decomposition of the graph Laplacian, but requires intense computations. [@defferrard2016convolutional] addresses this problem by leveraging Chebyshev polynomials to approximate spectral filters and achieves localized filtering. GCN [@Kipf2016SemiSupervisedCW] further simplifies the previous work by employing only first-order approximation of the filters. Our proposed joint learning of graphs and node features is based on GCN, which has spectral interpretation and scales linearly with the number of edges.

### Spatial methods

Instead of spectral representation, spatial methods define graph convolution directly on each node and its neighbors for feature propagation. Mixture model network [@monti2017geometric] provides a unified generalization of CNN architectures on graphs. Graph attention network (GAT) in [@velivckovic2017graph] employs self-attention mechanism to solve the node classification problem on citation networks. DGCNN [@wang2019dgcnn] proposes edge convolution to aggregate local features, which is applied to point cloud learning problem.

Graph Learning in GCNNs
-----------------------

Graph Learning in GCNNs can be categorized into three classes based on the graph domain to address: 1) fixed-domain graph learning, in which the underlying graph is fixed; 2) varying-domain graph learning, where graphs vary across data instances; and 3) hybrid graph learning, which combines the former two classes.

### Fixed-domain Graph Learning

This class of graph learning assumes there is a shared graph structure underlying all instances with fixed vertices. In applications such as semi-supervised node classification of citation networks, there is only *one fixed* graph to be learned and shared by all the instances to classify. GLCN [@Jiang2018GraphLN] learns a non-negative function that represents the pairwise relationship between two vertices using attention mechanism via a single-layer neural network, and optimizes it by minimizing GLR in the loss function. Instead, our method models pairwise similarity more explicitly by adopting Mahalanobis distance, and we learn different graphs at different layers.

### Varying-domain Graph Learning

Instances corresponding to varying domains may require different graphs with possibly arbitrary number of vertices. Graph learning for such data applications learns adaptive graphs tailored for different individuals. Spatio-temporal graph routing (STGR) is proposed [@li2019spatio] to learn one spatial graph and one temporal graph for each skeleton instance. Adaptive graph convolution network (AGCN) is proposed [@li2018adaptive] to construct a unique residual Laplacian matrix by learning Mahalanobis distance metric for each instance. Different from the task-driven AGCN where the Mahalanobis distance metric $\mathbf{M}$ is learned by minimizing the cross-entropy only, we optimize $\mathbf{M}$ via both the GLR and cross-entropy. Also, we assume $\mathbf{M}$ is low rank and set $S << K$ to reduce number of parameters while AGCN adopts $S = K$;

### Hybrid Graph Learning

For special applications like skeleton-based action recognition, both fixed-domain and varying-domain graph learning can be applied according to the way of graph construction. NLGCN [@shi2018non] builds three graphs for each instance: the pre-defined physical skeleton graph, a shared graph for all instances, and an individual graph learned from each instance’s own feature in a non-local [@wang2018non] manner.

Background in Spectral Graph Theory {#sec:graph}
===================================

Graph and Graph Laplacian
-------------------------

An undirected graph $\mathcal{G}=\{\mathcal{V},\mathcal{E},\mathbf{A}\}$ is composed of a vertex set $\mathcal{V}$ of cardinality $\left|\mathcal{V}\right|=N$, an edge set $\mathcal{E}$ connecting vertices, and a weighted adjacency matrix $\mathbf{A}$. $\mathbf{A} \in \mathbb{R}^{N \times N}$ is a real and symmetric matrix, where $a_{i,j} \geq 0$ is the weight assigned to the edge $(i,j)$ connecting vertices $i$ and $j$. Edge weights often measure the similarity between connected vertices.

The graph Laplacian matrix is defined from the adjacency matrix. Among different variants of Laplacian matrices, the *combinatorial graph Laplacian* is defined as $\mathbf{L}:=\mathbf{D}-\mathbf{A}$, where $\mathbf{D}$ is the *degree matrix*—a diagonal matrix where $d_{i,i}=\sum_{j=1}^N a_{i,j}$.

Graph Laplacian Regularizer
---------------------------

Graph signal refers to data that resides on the nodes of a graph, such as temperatures on a sensor network. A graph signal $\mathbf{x}\in\mathbb{R}^N$ defined on a graph $\mathcal{G}$ is *smooth* with respect to $\mathcal{G}$ [@spielman2007spectral] if $$\mathbf{x}^{\top} \mathbf{L} \mathbf{x} =\sum_{i=1}^{N} \sum_{j=1}^{N} w_{i,j}(x_i - x_j)^2 < \epsilon,
    \label{eq:prior}$$ where $\epsilon$ is a small positive scalar. To satisfy Eq. , connected node pair $x_i$ and $x_j$ must be similar for a large edge weight $w_{i,j}$; for a small $w_{i,j}$, $x_i$ and $x_j$ can differ significantly. Hence, Eq. forces $\mathbf{x}$ to adapt to the topology of $\mathcal{G}$, and is commonly called the *graph Laplacian Regularizer* (GLR) [@shuman2013emerging; @pang2017graph].

Joint Learning of Graphs and Features {#sec:method}
=====================================

In this section, we first propose the problem formulations of graph learning and node feature learning respectively assuming one of the other is known, and then combine them to the formulation of jointly learning.

Problem Formulation of Graph Learning
-------------------------------------

As a graph essentially captures *pairwise similarities* within data $\mathbf{x} \in \mathbb{R}^N$, we cast the problem of graph learning as *distance metric learning*, *i.e.*, learning a distance function for each data pair $\{x_i,x_j\}$ for similarity calculation. Specifically, given K-dimensional feature vectors $\mathbf{f}^i_l \in \mathbb{R}^K$ and $\mathbf{f}^j_l \in \mathbb{R}^K$ of node $i$ and $j$ at the $l$-th layer respectively, we employ the commonly used Gaussian kernel to define an edge weight $a_{i,j}$ as $$a_{i,j}=\exp\left\{-d^2(\mathbf{f}^i_l,\mathbf{f}^j_l)\right\},$$ where $d(\mathbf{f}^i_l,\mathbf{f}^j_l)$ is a distance metric between $\mathbf{f}^i_l$ and $\mathbf{f}^j_l$. The Gaussian kernel enforces edge weights to be in range $[0,1]$, thus ensuring the resulting combinatorial graph Laplacian to be PSD [@cheung2018graph].

While there exist various definitions of distance metrics, such as Euclidean distance and bilateral filtering distance [@tomasi1998bilateral], we deploy the *Mahalanobis distance*, which is defined as $$d_{\mathbf{M}_l}(\mathbf{f}^i_l,\mathbf{f}^j_l) = \sqrt{(\mathbf{f}^i_l - \mathbf{f}^j_l)^{\top} \mathbf{M}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)},
\label{eq:m_distance}$$ where $\mathbf{M}_l \in \mathbb{R}^{K \times K}$ is a PSD matrix, and $l$ is the index of layers. The Mahalanobis distance captures correlations among features via $\mathbf{M}_l$, which is widely adopted in the machine learning literature [@li2018adaptive; @luo2019robust].

Each edge weight is then computed as $$a_{i,j} = \exp\left\{-(\mathbf{f}^i_l - \mathbf{f}^j_l)^{\top} \mathbf{M}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\right\},
\label{eq:gaussian_kernel}$$ from which we can calculate the corresponding adjacency matrix and graph Laplacian.

As the graph Laplacian can be computed from edge weights by definition, we convert the graph learning problem to an optimization problem over $\mathbf{M}_l$. We optimize $\mathbf{M}_l$ by minimizing Graph Laplacian Regularizer in Eq. , which enforces the graph to capture the underlying structure of features. Let $s_{i,j} = (x_i-x_j)^2$, we have the following problem formulation for graph learning over all the layers of the network, with the objective as the sum of GLR over all the layers: $$\begin{split}
&\begin{split}
    \min_{\mathbf{M}_l}
     & \sum_l \sum_{\{i,j\}}\exp\left\{-(\mathbf{f}^i_l-\mathbf{f}^j_l)^{\top} \mathbf{M}_l (\mathbf{f}^i_l-\mathbf{f}^j_l) \right\} \, s_{i,j}
     \end{split} \\
& \text{s.t.} \quad \,\mathbf{M}_l \succeq 0, \, \forall l.
\label{eq:optimization}
\end{split}$$

Since $\mathbf{M}_l$ is PSD and symmetric, Eq. is computationally expensive to solve in general. Instead, we decompose $\mathbf{M}_l$ into $$\mathbf{M}_l = \mathbf{R}_l \mathbf{R}^{\top}_l,
    \label{eq:learnable_r}$$ where $\mathbf{R}_l \in \mathbb{R}^{K \times S}$, and $S \le K$ is a hyper-parameter to control the complexity of computing distance between high-dimensional features. When $K$ is large and $S << K$, the number of parameters for $\mathbf{M}_l$ is significantly reduced while assuming $\mathbf{M}_l$ is low rank, which is a common assumption in distance metric learning [@liu15aaai; @luo2019robust].

Then the Mahalanobis distance in Eq. becomes $$\begin{split}
d_{\mathbf{M}_l}(\mathbf{f}^i_l,\mathbf{f}^j_l)  
&= \sqrt{(\mathbf{f}^i_l - \mathbf{f}^j_l)^{\top} \mathbf{R}_l \mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)} \\
&= \sqrt{(\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l))^{\top}\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)}\\
&= \|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2, 
\end{split}
\label{eq:m_distance_decompose}$$ which is essentially a linear transformation of the Euclidean distance by $\mathbf{R}_l$. When $\mathbf{R}_l$ is an identity matrix, $d_{\mathbf{M}_l}(\mathbf{f}^i_l,\mathbf{f}^j_l)$ defaults to the Euclidean distance.

Hence, each edge weight can be computed as $$a_{i,j} = \exp\left\{-\|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2^2 \right\}.
\label{eq:weight_R}$$ Accordingly, the optimization problem in Eq. converts to $$\min_{\{\mathbf{R}_l\}}
     \sum_l \sum_{\{i,j\}}\exp\left\{-\|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2^2 \right\} \, s_{i,j},
     \label{eq:opt_graph_R}$$ which allows to remove the PSD constraint of $\mathbf{M}_l$ and is thus more efficient to solve. The optimal adjacency matrix $\mathbf{A}_l^*$ at the $l$-th layer is then computed from the optimized $\mathbf{R}_l$ via Eq. .

Problem Formulation of Node Feature Learning
--------------------------------------------

Assuming the availability of the learned optimal graph encoded in $\mathbf{A}_l^*$ and the optimal graph $\mathbf{A}_{l-1}$ in the previous layer, we learn node features based on a modified graph spectral convolution in GCN [@Kipf2016SemiSupervisedCW] for its simplicity and effectiveness. Given features of all nodes $\mathbf{F}_{l-1}$ from the $(l-1)$-th layer, the graph convolution at the $l$-th layer computes the output feature $\mathbf{F}_{l}$ as: $$\mathbf{F}_{l} = \mathbf{A}_l\mathbf{F}_{l-1} \mathbf{W}_l
\label{eq:gcn}$$ where $\mathbf{W}_l$ is a trainable parameter, and $\mathbf{A}_l$ is the re-normalized adjacency matrix calculated as $$\mathbf{A}_l=\mathbf{\Lambda}^{-\frac{1}{2}} (\mathbf{A}_{l-1}+\mathbf{A}_l^*) \mathbf{\Lambda}^{-\frac{1}{2}}$$ $\mathbf{\Lambda}$ is the normalization diagonal matrix. We essentially replace the re-normalization matrix $\mathbf{I}_N$ in the original GCN layer with our learned optimal graph $\mathbf{A}_l^*$. When $l=1$, $\mathbf{A}_0=\mathbf{0}$ is a zero matrix. In special cases where a ground truth graph is provided such as in semi-supervised node classification, $\mathbf{A}_0$ is the ground truth graph. The ground truth graph may be inaccurate or could be improved further. For instance, in a citation network, an unweighted graph is often available to describe the citation relationship among papers. We can further learn a weighted graph to learn hidden connections and characterize how well correlated connected papers are, which enhances the model capacity.

The objective of node feature learning is to minimize the cross entropy between predicted labels and ground truth labels, which is task-driven. We predict the label of each node by applying the softmax function to the output feature at the final $L$-the layer: $$\mathbf{\hat Y} = \text{softmax}(\mathbf{F}_L).$$ As $\mathbf{F}_L$ is learned from Eq. , $\mathbf{\hat Y}$ is a function of the set of parameters $\{\mathbf{W}_l, \mathbf{R}_l\}$ at each layer. By optimizing the cross-entropy loss, we have the following problem formulation of node feature learning: $$\min_{\{\mathbf{W}_l,\mathbf{R}_l\}} 
-\sum_{i=1}^N \sum_{c=1}^C \mathbf{Y}_{ic} \log(\hat{\mathbf{Y}}_{ic}(\mathbf{W}_l, \mathbf{R}_l)), 
\label{eq:opt_node}$$ where $N$ is the number of input instances, $C$ is the number of classes, and $\mathbf{Y}$ denotes the ground truth label matrix.

Problem Formulation of Joint Learning
-------------------------------------

Integrating Eq. and Eq. , we pose the joint learning of underlying graphs and node features as minimizing both GLR and the cross entropy. The final problem formulation is $$\begin{split}
\min_{\{\mathbf{W}_l, \mathbf{R}_l\}} 
& -\sum_{i=1}^N \sum_{c=1}^C \mathbf{Y}_{ic} \log(\hat{\mathbf{Y}}_{ic}(\mathbf{W}_l, \mathbf{R}_l)) \\
& + \lambda \sum_l \sum_{\{i,j\}}\exp\left\{-\|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2^2 \right\} \, s_{i,j},
\end{split}
\label{eq:opt_R}$$ where $\lambda > 0$ is a hyper-parameter for the trade-off between the cross entropy and the GLR term.

Proposed Network Structure {#sec:network}
==========================

Having discussed the problem formulation of joint learning, we elaborate on the proposed network architecture to realize dynamic learning of graphs and node features, with focus on the JLGCN Layer.

JLGCN Layer
-----------

![Demonstration of a JLGCN layer. A graph is first learned from node features, and then employed to propagate node features via graph convolution.[]{data-label="fig:layer"}](figures/layer.pdf){width="2.6in"}

As illustrated in Fig. \[fig:layer\], the JLGCN layer is composed of two modules: the graph learning module and node feature learning module. The graph learning module learns a graph encoded by an $N \times N$ dense adjacency matrix $\mathbf{A}$ from input node features. $\mathbf{A}$ is then employed by the node feature learning module to propagate node features via our proposed graph convolution in Eq. . Both modules are jointly optimized according to the objective in Eq. , *i.e.*, the loss function is defined as $$\begin{split}
E=& -\sum_{i=1}^N \sum_{c=1}^C \mathbf{Y}_{ic} \log(\hat{\mathbf{Y}}_{ic}(\{\mathbf{W}_l, \mathbf{R}_l\})) \\
& + \lambda \sum_l \sum_{\{i,j\}}\exp\left\{-\|\mathbf{R}^{\top}_l (\mathbf{f}^i_l - \mathbf{f}^j_l)\|_2^2 \right\} \, s_{i,j},
\end{split}
\label{eq:loss}$$ The algorithmic details are provided in Alg. \[alg:layer\].

**Input:** features $\mathbf{F}_{l-1}$ and adjacency matrix $\mathbf{A}_{l-1}$ from the previous layer\
**Output:** features $\mathbf{F}_l$ and learned adjacency matrix $\mathbf{A}_l$\
**Initialize:** trainable parameters $\mathbf{R}_l, \mathbf{W}_l$

**Forward Pass:** Compute distance metric $d_\mathbf{M}$ by Eq. Update $\mathbf{A}_l $ by Eq. Update $\mathbf{F}_l $ by Eq. **Backward Pass:** Update $\mathbf{R}_l$ and $\mathbf{W}_l$ via backward propagation with the loss function defined in Eq. .

![image](figures/network.pdf){width="6in"}

JLGCN Network
-------------

In principle, our JLGCN layer can be integrated into any GCNN architecture for both node classification and graph classification tasks. Fig. \[fig:network\] demonstrates the architecture of the JLGCN network. Node features are extracted by alternatively learning an optimal graph based on features and propagating features based on the learned graph, which are then fed into the classification module for label prediction.

### Node classification configuration

We stack multiple JLGCN layers and deploy leaky ReLU activation [@xu2015empirical]. Dropout is applied to the last layer’s input to reduce over-fitting. Features from the last layer is then employed for prediction of labels at each node.

### Graph classification configuration

We stack multiple JLGCN layers followed by batch normalization [@ioffe2015batch] and leaky ReLU activation. Graph max pooling is applied to features from the last layer, which are then fed into a fully connected network for the classification of the entire graph.

Further, we perform feature concatenation at each layer $l$ with $\mathbf{f}_{l-1}$ from the previous layer for multi-level feature learning to enhance the model capacity. This leads to $$\mathbf{f}_{l} = (\mathbf{f}_{l-1} || \mathbf{A}_l \mathbf{f}_{l-1}) \mathbf{W}_l,
\label{eq:gcn_concat}$$ where $||$ is the concatenation operator in feature dimension. This essentially assigns more weighting to each node’s own feature when no ground truth graph is available and accelerates the convergence.

Experimental Results {#sec:results}
====================

In order to evaluate the performance of JLGCN, we apply it to the problems of semi-supervised node classification and point cloud classification, which are discussed in order as follows.

Semi-supervised node classification
-----------------------------------

### Datasets

We test our method on three citation network datasets, *i.e.*, Citeseer, Cora and Pubmed [@sen2008collective]. The statistics of the datasets are summarized in Tab. \[tab:citation\_datasets\].

  **Dataset**   **Nodes**   **Edges**   **Classes**   **Features**   **Label Ratio**
  ------------- ----------- ----------- ------------- -------------- -----------------
  Citeseer      3,327       4,732       6             3,703          0.036
  Cora          2,708       5,429       7             1,433          0.052
  Pubmed        19,717      44,338      3             500            0.003

  : Summary of citation network datasets.[]{data-label="tab:citation_datasets"}

### Experimental settings

We follow the experimental setup of previous work [@yang2016revisiting; @Kipf2016SemiSupervisedCW; @velivckovic2017graph], and use the same data partition as in [@yang2016revisiting]. The features are $L2$-normalized before fed into the network. Since our method builds a dense adjacency matrix among all nodes, we sub-sample 10,000 nodes for Pubmed dataset to evaluate our model due to memory limitation. We set the number of JLGCN layers in our network to 2, and the number of hidden units in each layer to 16. For the dimension of the Mahalanobis distance metric matrix $\mathbf{R}\in \mathbb{R}^{K\times S}$, we set $S$ to 16 for both layers and initialize it randomly if not specified. We apply dropout with $p=0.5$ for both layer’s input, and use leaky ReLU activation with negative slope $\alpha=0.2$ between two layers. We train our JLGCN for a maximum of 500 epochs using ADAM algorithm [@kingma2014adam] with a learning rate of 0.1 and weight decay of 0.0005. The learning rate is decayed by 0.5 every 100 epochs. The hyper parameter $\lambda$ for GLR is set to 0.0001. We report the average classification accuracy of 10 runs with different random seeds.

### Baselines

We compare our JLGCN against the baseline of GCN [@Kipf2016SemiSupervisedCW] and Planetoid [@yang2016revisiting], and also against some other graph neural network based semi-supervised learning methods, including Graph Attention Network (GAT) [@velivckovic2017graph] and Graph Markov Neural Network (GMNN) [@qu2019gmnn]. These methods use the same dataset partition as in our method for fair comparison with available codes.

### Results

Tab. \[tab:results\_citation\] shows the comparison results on three citation network datasets. The best results are marked in bold. Overall, we note that 1) JLGCN outperforms the GCN baseline on all datasets significantly by only adding a graph learning module to each layer. This clearly demonstrates the effectiveness of jointly learning graphs and node features. Compared to the unweighted ground truth graph used in GCN, our learned graphs (as shown in Fig. \[fig:visual\_cora\]) enhance the semi-supervised learning results. 2) JLGCN also outperforms all the other recent work on the original Citeseer and Cora datasets and our sub-sampled Pubmed dataset. These results demonstrate the effectiveness of JLGCN in conducting semi-supervised classification tasks on graph data.

[p[1.4in]{}p[0.4in]{}p[0.4in]{}p[0.4in]{}]{} **Algorithm** & **Citeseer** & **Cora** & **Pubmed\***\

  -----------------------
  Planetoid
  [@yang2016revisiting]
  -----------------------

  : Results of semi-supervised node classification. \[\*\] means we sub-sample 10,000 nodes to perform the experiments.[]{data-label="tab:results_citation"}

& 64.7 & 75.7 & 77.2\

  -----------------------------
  GCN
  [@Kipf2016SemiSupervisedCW]
  -----------------------------

  : Results of semi-supervised node classification. \[\*\] means we sub-sample 10,000 nodes to perform the experiments.[]{data-label="tab:results_citation"}

& 70.3 & 81.5 & 78.4\

  -------------------------
  GAT
  [@velivckovic2017graph]
  -------------------------

  : Results of semi-supervised node classification. \[\*\] means we sub-sample 10,000 nodes to perform the experiments.[]{data-label="tab:results_citation"}

& 72.5 & 83.0 & 78.8\

  ---------------
  GMNN
  [@qu2019gmnn]
  ---------------

  : Results of semi-supervised node classification. \[\*\] means we sub-sample 10,000 nodes to perform the experiments.[]{data-label="tab:results_citation"}

& 73.1 & 83.7 & 79.4\
JLGCN & **73.7** & **83.9** & **79.7**\

### Robustness test

We design two experiments to test the robustness of our model: 1) we lower the label ratio by employing less training data. We adopt five missing ratios {0, 0.25, 0.5, 0.75, 0.9} of training nodes to train and evaluate; 2) we test the robustness of our model to incomplete ground truth graph, *i.e.*, we randomly drop out edges in the ground truth graph, with edge missing ratios set as {0, 0.25, 0.5, 0.75, 0.9, 1.0}. When the edge missing ratio is 1.0, an empty ground truth graph is fed into the network. Since randomly initialized graph is hard to converge, we set $S=K$ for the transformation matrix $\mathbf{R}$ and initialize it as an identity matrix in this case. Fig. \[fig:robust\_citation\] shows our model significantly outperforms GCN and GAT, especially when the edge missing ratio is high. This validates the superiority of our learned graph structure in terms of robustness.

### Ablation study

We first examine the effectiveness of the graph learning module on Cora dataset. Specifically, we compare with 1) GCN, where the ground truth graph is employed; 2) GCN + Euclidean, where we replace the proposed graph learning with manual graph construction using Euclidean distance metric to compute edge weights; 3) JLGCN without dynamic updating of graphs, *i.e.*, we only learn one graph from the input data feature. As reported in Tab. \[tab:ablation\], our method leads to the best result when we adopt the Mahalanobis distance metric and learn different graphs at different layers jointly with node features from data.

Secondly, we evaluate the performance of JLGCN with different $\lambda$—the weighting parameter of GLR in the loss function—with respect to different edge missing ratios. As listed in Tab. \[tab:ablation\], we see that JLGCN achieves the highest accuracy when $\lambda$ is set to 0.0001. Also, GLR helps improve the performance especially when the ground truth graph is incomplete or even unavailable.

### Visualization of the learned graph

We also visualize the learned graph at each layer in Fig. \[fig:visual\_cora\], and compare them with the ground truth graph. The value of the matrix is log-transformed to make it more interpretable. Note that the learned graph is both dense and weighted, which not only adds self-connection to the unweighted ground truth graph as the original GCN does, but also extracts additional hidden connections between similar nodes. Also, the learned graph at the second layer puts higher weighting to self-connection compared to the first layer, showing that different layers correspond to varying graphs as we assumed.

Point cloud classification
--------------------------

Furthermore, we test our model on point cloud classification to validate the effectiveness of our model when no ground truth graph is available.

### Datasets

We test on ModelNet40 dataset for point cloud classification. ModelNet40 includes 12,311 CAD models from 40 man-made categories, which are split into 9,843 for training and 2,468 for testing. As in previous work [@qi2017pointnet; @qi2017pointnet++; @wang2019dgcnn], we uniformly sample 1024 points on mesh faces according to face area and normalize them into a unit sphere, where only coordinates of points are employed as input features.

### Experimental settings

We stack 3 JLGCN layers to extract point cloud features as well as learn the underlying graph without any ground truth graph. The hidden units for each layer is {64, 128, 1024}. After extracting point cloud features, we deploys a permutation-invariant graph max-pooling to generate a global context feature for the entire point cloud, and employs a fully connected network with hidden units of {512, 256, 40} to classify the point cloud. The negative slope of leaky ReLU activation is set to 0.2 and dropout with $p=0.5$ is used in the fully connected classification network. We train the network with a learning rate of 0.001 for 400 epochs and decay it by 0.5 every 40 epochs using ADAM. The batch size is set to 32, weight decay to 0.0001 and $\lambda$ to 0.01.

### Baselines

We also provide a GCN based model as the baseline, which empirically constructs a $k$-NN graph as the underlying graph. $k$ is set to 20 in the classification task based on the density of point clouds. We mainly compare our JLGCN model against the baseline GCN, and also compare against other state-of-the-art methods, including methods tailored for point cloud learning such as PointNet [@qi2017pointnet], PointNet++ [@qi2017pointnet++], PointGCN [@zhang2018graph], RGCNN [@te2018rgcnn], and DGCNN [@wang2019dgcnn].

### Results

Tab. \[tab:results\_modelnet\] presents results for ModelNet40 classification. Our method improves the baseline by about 2% with only 3MB of parameters added, demonstrating the learned graph is superior to the empirical $k$-NN graph. Also, our method achieves comparable results compared to state-of-the-art methods for point loud learning, while our model is simpler and contains much smaller amount of parameters. Note that, our method achieves the best performance among all spectral graph convolution based methods.

[p[0.3in]{}p[0.9in]{}p[0.4in]{}p[0.4in]{}p[0.4in]{}]{} **Category** & **Algorithm** & & &\

  -----------
  Pointwise
  MLP
  -----------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

&

  -------------------
  PointNet
  [@qi2017pointnet]
  -------------------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& 40 & 86.0 & 89.2\

  -----------
  Pointwise
  MLP
  -----------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

&

  ---------------------
  PointNet++
  [@qi2017pointnet++]
  ---------------------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& 12 & - & 90.7\

  ----------
  Spectral
  GCNN
  ----------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

&

  -------------------
  PointGCN
  [@zhang2018graph]
  -------------------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& 41 & 86.1 & 89.5\

  ----------
  Spectral
  GCNN
  ----------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

&

  ----------------
  RGCNN
  [@te2018rgcnn]
  ----------------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& 22 & 87.3 & 90.5\

  ---------
  Spatial
  GCNN
  ---------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

&

  ------------------
  DGCNN
  [@wang2019dgcnn]
  ------------------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& 21 & **90.2** & **92.9**\

  ----------
  Spectral
  GCNN
  ----------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& GCN (baseline) & **10** & 84.2 & 88.7\

  ----------
  Spectral
  GCNN
  ----------

  : Results of point cloud classification on ModelNet40.[]{data-label="tab:results_modelnet"}

& JLGCN & 13 & 87.2 & 90.8\

### Robustness test

Further, we test the robustness of our model when the point cloud is of low density. We randomly drop out points with missing ratios {0, 0.25, 0.5, 0.75, 0.9}. As shown in Fig. \[fig:robust\_pc\], our model outperforms the GCN baseline significantly, and keeps high accuracy even when the point cloud density is quite low.

![Robustness test with different missing ratios of point clouds.[]{data-label="fig:robust_pc"}](figures/robust_pc.pdf){width="3in"}

Conclusion {#sec:conclude}
==========

We propose joint learning of graphs and node features in Graph Convolutional Neural Networks, which dynamically learns graphs adaptive to the structure of node features in different layers. In particular, we optimize an underlying graph kernel via distance metric learning with the Mahalanobis distance employed. The metric matrix is decomposed into a low-dimensional matrix and optimized based on Graph Laplacian Regularizer. Extensive experiments demonstrate the superiority and robustness of our method in semi-supervised learning and point cloud learning problems.

[10]{}

Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph cnn for learning on point clouds. , 2019.

Gusi Te, Wei Hu, Amin Zheng, and Zongming Guo. Rgcnn: Regularized graph cnn for point cloud segmentation. In [*2018 ACM Multimedia Conference on Multimedia Conference*]{}, pages 746–754. ACM, 2018.

Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning-convolutional networks. In [*IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*]{}, pages 11313–11320, 2019.

Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In [*Thirty-Second AAAI Conference on Artificial Intelligence*]{}, 2018.

Lei Shi, Yifan Zhang, Jian Cheng, and Hanqing Lu. Non-local graph convolutional networks for skeleton-based action recognition. , 2018.

Bin Li, Xi Li, Zhongfei Zhang, and Fei Wu. Spatio-temporal graph routing for skeleton-based action recognition. In [*Thirty-Third AAAI Conference on Artificial Intelligence (AAAI)*]{}, 2019.

P. C. Mahalanobis. On the generalized distance in statistics. , 2(1):49–55, 1936.

David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. , 30(3):83–98, 2013.

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. , abs/1609.02907, 2016.

Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. , 2013.

Micha[ë]{}l Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In [*Advances in neural information processing systems*]{}, pages 3844–3852, 2016.

Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In [*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*]{}, pages 5115–5124, 2017.

Petar Veli[č]{}kovi[ć]{}, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. , 2017.

Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In [*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*]{}, pages 7794–7803, 2018.

Daniel A Spielman and Shang-Hua Teng. Spectral partitioning works: Planar graphs and finite element meshes. , 421(2-3):284–305, 2007.

Jiahao Pang and Gene Cheung. Graph laplacian regularization for image denoising: Analysis in the continuous domain. , 26(4):1770–1785, 2017.

Gene Cheung, Enrico Magli, Yuichi Tanaka, and Michael K Ng. Graph spectral image processing. , 106(5):907–930, 2018.

Carlo Tomasi and Roberto Manduchi. Bilateral filtering for gray and color images. In [*Iccv*]{}, volume 98, page 2, 1998.

Lei Luo, Jie Xu, Cheng Deng, and Heng Huang. Robust metric learning on grassmann manifolds with generalization guarantees. In [*Proceedings of the AAAI Conference on Artificial Intelligence*]{}, volume 33, pages 4480–4487, 2019.

Wei Liu, Cun Mu, Rongrong Ji, Shiqian Ma, John R Smith, and Shih-Fu Chang. Low-rank similarity metric learning in high dimensions. In [*Twenty-ninth AAAI conference on artificial intelligence*]{}, 2015.

Bing Xu, Naiyan Wang, Tianqi Chen, and Mu Li. Empirical evaluation of rectified activations in convolutional network. , 2015.

Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. , 2015.

Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. , 29(3):93–93, 2008.

Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. , 2016.

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. , 2014.

Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. , 2019.

Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In [*Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition*]{}, pages 652–660, 2017.

Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. In [*Advances in neural information processing systems*]{}, pages 5099–5108, 2017.

Yingxue Zhang and Michael Rabbat. A graph-cnn for 3d point cloud classification. In [*2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*]{}, pages 6279–6283. IEEE, 2018.

[^1]: In spectral graph theory, a graph Laplacian matrix is an algebraic representation of connectivities and node degrees of the corresponding graph, which will be defined formally later.
