PaperlayerView exact revision on arXiv

Source-linked AI summary

Column Networks for Collective Classification

Trang Pham, Truyen Tran, Dinh Phung, Svetha Venkatesh

arXiv:1609.04508v2cs.LGcs.AIstat.ML

TL;DR

Collective classification must jointly label networked objects, yet it remains computationally challenging and has not fully benefited from deep learning. The paper proposes Column Network (CLN), an efficient deep model for multi-relational data, and reports higher accuracy than state-of-the-art rivals across three real-world applications.

  • Problem

    Collective classification exploits dependencies among networked objects, but learning and inference are computationally challenging and general multi-relational deep-learning solutions remain open.

  • Method

    CLN is a deep network of interacting mini-column nets that jointly learns local and relational features while encoding multi-relations and long-range dependencies.

  • Results

    CLN achieves higher accuracy than state-of-the-art rivals on software-delay prediction, PubMed Diabetes publication classification, and film-genre classification.

  • Takeaways & Limitations

    CLN provides collective classification with learning and inference that are linear in network size and relation count.

  • Takeaways & Limitations

    The study considers only homogeneous prediction tasks, assuming all instances are of the same type.

Abstract

from arXiv · show

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 computational 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, linear 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 applications, CLN demonstrates a higher accuracy than state-of-the-art rivals.

1 Introduction

Collective classification jointly labels networked objects, but existing approaches face computational challenges and limited deep-learning integration. The paper introduces Column Network (CLN), a compact and efficient deep model that learns local and relational features while outperforming state-of-the-art rivals across three applications.

  • Collective classification jointly classifies networked instances to exploit dependencies that may indicate relationships between their classes.
  • Existing collective-classification models are mostly shallow and do not emphasize jointly learning local and relational features.
  • CLN uses interacting mini-column feedforward networks whose short-range exchanges produce increasing interaction ranges with depth, enabling long-range dependencies.
  • Parameter sharing across CLN hidden layers allows depth to grow without introducing new parameters.
  • CLN encodes multi-relations, learns local and relational features simultaneously, supports higher-order dependencies, and has learning and inference costs linear in network size and relation count.
  • CLN outperforms state-of-the-art rivals on software-delay prediction, PubMed Diabetes publication classification, and film-genre classification.

2 Preliminaries

The paper formalizes collective classification over multi-relational entity graphs, where labels are inferred jointly from local features and relational structure. It contrasts this setting with stacked learning, which sequentially turns intermediate predictions into relational features.

  • 2.1 Collective Classification in Multi-relational Setting: The multi-relational graph allows multiple relation types between entities, with each relation being unidirectional or bidirectional.
  • 2.1 Collective Classification in Multi-relational Setting: An entity’s neighbor set is the union of its relation-specific neighbor sets.
  • 2.1 Collective Classification in Multi-relational Setting: Collective classification infers unknown entity labels simultaneously from a graph, local feature vectors, and observed labels.
  • 2.1 Collective Classification in Multi-relational Setting: Inference targets the joint conditional distribution P(Y | G), making learning and inference challenging.
  • 2.2 Stacked Learning: Stacked learning repeatedly predicts class probabilities and feeds intermediate outputs to neighbor classifiers as relational features.

3 Column Networks

Column Networks use one neural mini-column per entity, with relational communication between columns and stacked layers that build higher-order representations. Highway components, parameter sharing, and efficient neighborhood aggregation support deep models without proportional growth in model size.

  • 3.1 Architecture: Each entity has a feedforward mini-column that passes information through its own layers and those of connected neighbors, with communication determined by relation types.
  • 3.1 Architecture: Mean-pooling aggregates abstract neighbor features by relation without reducing graph size, while alternative pooling and attention mechanisms are also possible.
  • 3.2 Highway Network as Mini-Column: Highway gates let previous states and gradients propagate through deep mini-columns, addressing the difficulty of training very deep feedforward networks.
  • 3.3 Parameter sharing: Parameter sharing makes hidden layers identical, so CLN depth can grow without increasing model size and may benefit small and medium datasets.
  • 3.4 Long-range dependencies: Multiple layers expand each entity’s receptive field, allowing top-layer representations to incorporate long-range dependencies and potentially the entire graph.
  • 3.5 Mini-batch training: A mini-batch approximation freezes neighbor activations during updates, enabling mini-batch training instead of expensive full-batch computation.

4 Experiments and Results

CLN is evaluated across software delay prediction, PubMed Diabetes classification, and film genre classification against collective and non-collective baselines. Across these applications, the reported CLN variants achieve strong results, including the best collective-method comparison in software delay prediction and strong F1 performance on PubMed and movies.

  • 4.3 Software Delay Prediction: The software-delay CLN-HWN-full configuration peaks at an F1-score with 10 hidden layers and hidden dimension 10.Figure 3 compares layer counts from 2 to 30 and hidden dimensions 5, 10, and 20.
  • 4.3 Software Delay Prediction: CLN-HWN-full beats the best collective method, SL-RF, by 3.1 points in software delay prediction, while mini-batch training is roughly 6x faster with a 0.7% loss.The non-collective HWN-noRel nearly reaches SL-RF, falling short by 2 points.
  • 4.4 PubMed Diabetes Classification: On PubMed Diabetes, the two CLN-HWN versions perform best on both MicroF1-score and MacroF1-score, while HWN-noRel outperforms the two best NetKit baselines.The best CLN-HWN setting uses 40 hidden dimensions and 10 recurrent layers.
  • 4.5 Film Genre Prediction: On movie genres, CLN-HWN-mini outperforms CLN-HWN-full by 1.3 points on Macro-F1, and CLN-HWNs work best with 30 hidden dimensions and 10 recurrent layers.Table 4 reports MicroF1 and MacroF1 performance.
  • 4.5 Film Genre Prediction: CLN-FNN performs poorly on imbalanced movie labels, with F1-scores of 5.4% for label 7 and 13.3% for label 8, whereas CLN-HWN performs well across classes.MacroF1 is the average of all classes’ F1-scores.

5 Related Work

Related work connects collective classification in statistical relational learning with deep learning. Collective classifiers combine relational classification with joint inference, while comparatively less work has addressed general networked data using deep networks.

  • Statistical Relational Learning: Statistical relational learning includes probabilistic relational models, conditional random fields, relational Markov networks, and Markov logic networks.These works form part of the field’s development since the late 1990s.
  • Collective Classification: Collective classifiers use relational classifiers and collective inference to exploit dependencies among networked entities.Relational classifiers use neighbor predictions or probabilities as features, while collective inference jointly infers labels.
  • Deep Learning: Deep learning provides compact multilayered networks for function approximation and recurrent program construction, but general networked data has received less attention.Prior work has paired structured outputs with deep networks, but the passage distinguishes this from general networked data.

6 Discussion

CLN is a deep neural network for fast collective classification, combining flexible network architectures with efficient training and inference. It performs competitively across three real-world applications, while current work assumes homogeneous instance types.

  • 6 Discussion: CLN has linear complexity in data size and relation count for both training and inference, while achieving competitive performance across three real-world applications.The applications are software-project delay prediction, PubMed Diabetes publication classification, and film genre classification.
  • 6 Discussion: CLN is a network of narrow deep networks whose layers incorporate preceding neighbor layers, and it can use shared or node-specific relations.Highway networks are used in the implementation, but the architecture can potentially use other feedforward networks.
  • 6 Discussion: The current framework considers homogeneous prediction tasks, while future extensions include learned attention-based pooling and support for multiple instance types.The paper identifies these as open directions rather than evaluated capabilities.
Loading 1609.04508v2…