Column Networks for Collective Classification

By Trang Pham, Truyen Tran, Dinh Q. Phung, Svetha Venkatesh. 2016

152 citations recorded by the source corpus.

Relational learning deals with data that are characterized by relational structures. An important task is collective classification, which is to jointly classify networked objects. While it holds a great promise to produce a better accuracy than non-collective classifiers, collective classification is computationally challenging and has not leveraged on the recent breakthroughs of deep learning. We present Column Network (CLN), a novel deep learning model for collective classification in multi-relational domains. CLN has many desirable theoretical properties: (i) it encodes multi-relations between any two instances; (ii) it is deep and compact, allowing complex functions to be approximated at the network level with a small set of free parameters; (iii) local and relational features are learned simultaneously; (iv) long-range, higher-order dependencies between instances are supported naturally; and (v) crucially, learning and inference are efficient with linear complexity in the size of the network and the number of relations. We evaluate CLN on multiple real-world applications: (a) delay prediction in software projects, (b) PubMed Diabetes publication classification and (c) film genre classification. In all of these applications, CLN demonstrates a higher accuracy than state-of-the-art rivals.

Subfields: Artificial Intelligence, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Graph Learning

Citations in the corpus

Representation Learning on Graphs with Jumping Knowledge Networks (2018, methodology): “Graph Attention Networks (GAT) (Veliˇckovi´c et al., 2018) and VAIN (Hoshen, 2017) learn to select the important neighbors via an attention mechanism.”
Representation Learning on Graphs: Methods and Applications (2017, methodology): “There are a number of recent approaches that follow the basic procedure outlined in Algorithm 1, including graph convolutional networks (GCN) [34, 35, 52, 55], column networks [49], and the GraphSAGE algorithm [28].”
Predict then Propagate: Graph Neural Networks meet Personalized PageRank (2018, background): “, 2016), message passing (or neighbor aggregation) algorithms (Kearnes et al., 2016; Kipf & Welling, 2017; Hamilton et al., 2017; Pham et al., 2017; Monti et al., 2017; Gilmer et al., 2017), and neighbor aggregation via recurrent neural networks (Scarselli et al.”
Modeling Relational Data with Graph Convolutional Networks (2017, background): “A number of extensions to the original graph neural network have been proposed, most notably (Li et al. 2016) and (Pham et al. 2017), both of which utilize gating mechanisms to facilitate optimization.”
A Comprehensive Survey on Graph Neural Networks (2019, background): “Spatial-based models are more ﬂexible to handle multi-source graph inputs such as edge inputs [15], [27], [86], [95], [96], directed graphs [25], [72], signed graphs [97], and heterogeneous graphs [98], [99], because these graph inputs can be incorporated into the aggregation function easily.”
Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking (2017, methodology): “Graph convolutional networks are another family of approaches that adapt conventional CNNs to graph data (Kipf & Welling, 2016a; Defferrard et al., 2016; Henaff et al., 2015; Monti et al., 2016; Niepert et al., 2016; Pham et al., 2017).”
All You Need Is Low (Rank): Defending Against Adversarial Attacks on Graphs (2020, background): “Graph representation learning [16, 30] and deep learning techniques [19, 32] have shown outstanding results in addressing the problem of node classification.”
NeVAE: A Deep Generative Model for Molecular Graphs (2018, methodology): “2, are very similar to the ones used in several graph representation learning algorithms such as GraphSAGE (Hamilton et al., 2017), column networks (Pham et al., 2017), and GCNs (Kipf and Welling, 2016a).”
Hypergraph Convolution and Hypergraph Attention (2019, background): “, 2016), skip connection (Pham et al., 2017), jumping connection (Xu et al.”
Graph Neural Networks With Convolutional ARMA Filters (2019, background): “This is different from a skip connection that either takes the output of the previous layer X(t−1) as input (Pham et al., 2017; Hamilton et al., 2017), or connects all the layers in a GNN stack directly to the output (Wu et al.”
Deep Learning on Graphs: A Survey (2018, unknown): “CLN [60] trained different parameters for different edge types in a heterogeneous graph and averaged the results.”
Deep Gaussian Embedding of Attributed Graphs: Unsupervised Inductive Learning via Ranking (2017, methodology): “Most of these approaches [13, 3, 10, 18, 19, 22] utilize the graph Laplacian and the spectral definition of a convolution and boil down to some form of aggregation over neighbors such as averaging.”
Reinforcement Learning on Web Interfaces Using Workflow-Guided Exploration (2018, methodology): “We design our DOM embedder to capture the various interactions between DOM elements, similar to recent work in graph embeddings (Kipf & Welling, 2017; Pham et al., 2017; Hamilton et al., 2017).”
Diffusion Improves Graph Learning (2019, methodology): “In general, GNNs are classified into spectral-based models [11, 16, 28, 32, 41], which are based on the eigendecomposition of the graph Laplacian, and spatialbased methods [23, 26, 43, 52, 56, 62, 74], which use the graph directly and form new representations by aggregating the representations of a ”
Graph Neural Networks: A Review of Methods and Applications (2018, unknown): “The Column Network (CLN) proposed in [73] also utilizes the highway network.”
Graph Classification via Deep Learning with Virtual Nodes (2017, methodology): “Several other methods extend convolutional operations to irregular local neighborhoods [Atwood and Towsley, 2016; Niepert et al., 2016; Pham et al., 2017a].”