# Graph Construction using Principal Axis Trees for Simple Graph Convolution

arXiv: https://arxiv.org/abs/2302.12000 · HTML: https://mlsanity.com/paper/2302.12000/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 22 Feb 2023.

## Builds on (most cited first, 17 of 17)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [SpectralNet: Spectral Clustering using Deep Neural Networks](https://mlsanity.com/paper/1801.01587/) (2018)
- [Revisiting Over-smoothing in Deep GCNs](https://mlsanity.com/paper/2003.13663/) (2020)
- [K-nearest Neighbor Search by Random Projection Forests](https://mlsanity.com/paper/1812.11689/) (2018)
- [Graph Fusion Network for Multi-Oriented Object Detection](https://mlsanity.com/paper/2205.03562/) (2022)
- [Mediated Experts for Deep Convolutional Networks](https://mlsanity.com/paper/1511.06072/) (2015)
- [A Dependency Syntactic Knowledge Augmented Interactive Architecture for End-to-End Aspect-based Sentiment Analysis](https://mlsanity.com/paper/2004.01951/) (2020)
- [Similarity Kernel and Clustering via Random Projection Forests](https://mlsanity.com/paper/1908.10506/) (2019)
- [DC2: A Divide-and-conquer Algorithm for Large-scale Kernel Learning with Application to Clustering](https://mlsanity.com/paper/1911.06944/) (2019)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are increasingly becoming the favorite method for graph learning. They exploit the semi-supervised nature of deep learning, and they bypass computational bottlenecks associated with traditional graph learning methods. In addition to the feature matrix X, GNNs need an adjacency matrix A to perform feature propagation. In many cases, the adjacency matrix A is missing. We introduce a graph construction scheme that constructs the adjacency matrix A using unsupervised and supervised information. Unsupervised information characterizes the neighborhood around points. We used Principal Axis trees (PA-trees) as a source for unsupervised information, where we create edges between points falling onto the same leaf node. For supervised information, we used the concept of penalty and intrinsic graphs. A penalty graph connects points with different class labels, whereas an intrinsic graph connects points with the same class labels. We used the penalty and intrinsic graphs to remove or add edges to the graph constructed via PA-tree. We tested this graph construction scheme on two well-known GNNs: 1) Graph Convolutional Network (GCN) and 2) Simple Graph Convolution (SGC). The experiments show that it is better to use SGC because it is faster and delivers better or the same results as GCN. We also test the effect of oversmoothing on both GCN and SGC. We found out that the level of smoothing has to be carefully selected for SGC to avoid oversmoothing.