PaperlayerView exact revision on arXiv

Source-linked AI summary

Composition-based Multi-Relational Graph Convolutional Networks

Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, Partha Talukdar

arXiv:1911.03082v2cs.LGstat.ML

TL;DR

Existing GCNs largely focus on simple undirected graphs, while relational graphs require directed, labeled edges and relation representations without excessive parameterization. COMPGCN jointly embeds nodes and relations using knowledge-graph composition operators. Across link prediction, node classification, and graph classification, it reports effectiveness over existing GCN-based methods, while its background identifies over-parameterization as a central challenge addressed through parameter sharing and basis decomposition.

  • Problem

    Existing relational GCNs suffer from over-parameterization and generally learn node representations without relation vectors needed for tasks such as link prediction.

  • Method

    COMPGCN jointly embeds nodes and relations in multi-relational graphs using knowledge-graph composition operators within a GCN framework.

  • Results

    COMPGCN demonstrates effectiveness over existing GCN-based methods across link prediction, node classification, and graph classification, and generalizes several multi-relational GCN methods.

  • Takeaways & Limitations

    The framework provides a general approach for incorporating relational information into GCNs while scaling with increasing numbers of relations.

  • Takeaways & Limitations

    Relation-specific parameters in prior relational GCN formulations become over-parameterized as the number of relations increases.

Abstract

from arXiv · show

Graph Convolutional Networks (GCNs) have recently been shown to be quite successful in modeling graph-structured data. However, the primary focus has been on handling simple undirected graphs. Multi-relational graphs are a more general and prevalent form of graphs where each edge has a label and direction associated with it. Most of the existing approaches to handle such graphs suffer from over-parameterization and are restricted to learning representations of nodes only. In this paper, we propose CompGCN, a novel Graph Convolutional framework which jointly embeds both nodes and relations in a relational graph. CompGCN leverages a variety of entity-relation composition operations from Knowledge Graph Embedding techniques and scales with the number of relations. It also generalizes several of the existing multi-relational GCN methods. We evaluate our proposed method on multiple tasks such as node classification, link prediction, and graph classification, and achieve demonstrably superior results. We make the source code of CompGCN available to foster reproducible research.

1 INTRODUCTION

GCNs primarily address simple undirected graphs, while multi-relational graphs require handling labeled, directed edges and learning relation representations. COMPGCN addresses these gaps by jointly embedding nodes and relations through knowledge-graph composition operations.

  • Multi-relational graphs contain directed, labeled edges, but many existing GCN approaches learn only node representations and suffer from over-parameterization.
  • Knowledge-graph embedding methods jointly learn node and relation representations but are restricted to link-prediction objectives.
  • COMPGCN incorporates knowledge-graph entity-relation composition operations into GCNs for task-specific learning on multi-relational graphs.
  • COMPGCN jointly embeds nodes and relations, generalizes several multi-relational GCN methods, and scales with the number of relations.
  • COMPGCN was evaluated on node classification, link prediction, and graph classification, with source code and datasets made available for reproducibility.

2 RELATED WORK

Prior work extends GCNs to relational graphs through direction-specific filters, decomposition, or relational weights, while knowledge-graph embedding methods learn representations for link prediction. COMPGCN instead provides a generic framework for combining GCNs with knowledge-graph composition operators.

  • Graph Convolutional Networks: Standard GCN research includes extensions based on message passing, attention, sampling, and graph-level representations for non-Euclidean data.
  • GCNs for Multi-Relational Graph: Relational GCN approaches reduce parameterization through basis or block-diagonal decomposition, but primarily embed graph nodes.
  • GCNs for Multi-Relational Graph: Ye et al. extend GCNs to jointly embed nodes and relations, whereas COMPGCN can leverage any knowledge-graph composition operator.
  • Knowledge Graph Embedding: Knowledge-graph embedding methods score triples so valid facts rank above invalid ones and include translational, semantic-matching, and neural-network approaches.

3 BACKGROUND

GCNs aggregate transformed neighborhood information, and stacking layers captures multi-hop dependencies. Relational GCNs extend this framework by adding inverse edges, but relation-specific parameters can become over-parameterized as the relation count grows.

  • GCN on Undirected Graphs: A GCN layer transforms node features using a normalized adjacency matrix with self-connections, learnable weights, and an activation function.
  • GCN on Undirected Graphs: Stacking GCN layers produces representations that incorporate multi-hop graph dependencies.
  • GCN on Multi-Relational Graphs: For directed relational graphs, each edge is complemented with an inverse edge so information can flow in both directions.
  • GCN on Multi-Relational Graphs: Relation-specific parameters cause over-parameterization as the number of relations increases, motivating direction-specific weights and basis or block-diagonal decomposition.

4 COMPGCN DETAILS

COMPGCN jointly learns node and relation representations for multi-relational graphs by combining relation-aware message passing with entity-relation composition. It uses basis representations and shared transformations to remain parameter-efficient, generalize existing methods, and scale with the number of relations.

  • Model overview: COMPGCN jointly learns d-dimensional representations for both nodes and relations, unlike methods that embed only nodes.Relation vectors also allow available relation features to initialize the model.
  • Relation-based composition: COMPGCN composes neighboring node and relation embeddings using subtraction, multiplication, or circular-correlation operations.The framework restricts experiments to non-parameterized operators but can be extended to parameterized alternatives.
  • Node updates: The node update is relation-aware and linear, O(|R|d), in the number of feature dimensions, with separate filters for original, inverse, and self edges.Direction-specific weights distinguish the three edge types during aggregation.
  • Relation updates: COMPGCN transforms relation embeddings into the node embedding space so they can be reused in subsequent layers.A learnable Wrel matrix performs this projection after the node update.
  • Scaling: COMPGCN represents relations with basis vectors and shares later-layer transformations, making it more parameter-efficient than Relational-GCN as relation counts increase.Unlike Relational-GCN, it uses embedding vectors rather than layer-specific basis matrices.
  • Generalization: Proposition 4.1 shows that COMPGCN generalizes Kipf-GCN, Relational GCN, Directed GCN, and Weighted GCN.The reductions are obtained through suitable choices of relation weights and composition functions.

5 EXPERIMENTAL SETUP

The experiments evaluate COMPGCN across link prediction, node classification, and graph classification, using relational GCN and knowledge-graph baselines. Results are reported with task-specific datasets and metrics.

  • Evaluation tasks: COMPGCN is evaluated on link prediction using FB15k-237 and WN18RR, with filtered MRR, MR, and Hits@N reported.
  • Evaluation tasks: Node classification predicts node labels from features and connections, while graph classification evaluates labels for entire graphs.
  • Baselines: The relational GCN baselines include R-GCN, D-GCN, and W-GCN, representing basis-decomposed, direction-specific, and weighted relational aggregation approaches.
  • Baselines: Link-prediction comparisons include translational, semantic, neural, and relational baselines such as TransE, DistMult, ConvE, R-GCN, RotatE, and VR-GCN.
  • Baselines: Node-classification baselines are Feat, WL, and RDF2Vec; graph-classification baselines are PACHYSAN, DGCNN, and GIN.
  • Reported comparisons: Table 4 evaluates link prediction on FB15k-237 across scoring functions, encoders, composition operators, and relational basis counts.

6 RESULTS

Across link prediction, scalability, and classification experiments, COMPGCN generally matches or exceeds competing relational GCN methods while retaining parameter efficiency. Its strongest configuration uses ConvE with circular-correlation, and limited-basis variants remain effective as relation counts grow.

  • Link prediction: COMPGCN outperforms existing methods on 4 of 5 metrics for FB15k-237 and 3 of 5 metrics for WN18RR.
  • Link prediction: COMPGCN achieves average relative MRR increases of around 6%, 4%, and 3% with TransE, DistMult, and ConvE objectives versus the best baseline.
  • Link prediction: ConvE + COMPGCN with circular-correlation is the best-performing link-prediction method overall.
  • Composition operators: With DistMult, multiplication performs best, whereas with ConvE, circular-correlation surpasses the other composition operators.
  • Scalability: With B = 100, performance becomes comparable to using individual embeddings for every relation, while the parameter-efficient variant outperforms baselines in all settings.
  • Scalability: Using 5 relation basis vectors, COMPGCN has comparable performance to the full model across relation counts and consistently outperforms R-GCN.
  • Classification: COMPGCN outperforms all baselines on node classification and performs comparably on graph classification, improving by 3% on average across node-classification datasets and by 3% on PTC.

7 CONCLUSION

The conclusion presents COMPGCN as a multi-relational GCN framework that jointly embeds nodes and relations through knowledge-graph composition operators. It reports effectiveness across tasks, generalization of existing methods, and scalability through parameter sharing and basis decomposition.

  • COMPGCN jointly embeds nodes and relations using composition operators from knowledge-graph embedding techniques.
  • The framework generalizes several existing multi-relational GCN methods and alleviates over-parameterization through shared relation embeddings and basis decomposition.
  • Experiments on link prediction, node classification, and graph classification support COMPGCN’s effectiveness over existing GCN methods and scalability with increasing relation counts.

A.1 EVALUATION BY RELATION CATEGORY

COMPGCN improves link-prediction performance across all four relation categories on FB15k-237, with the largest gain for one-to-many relations.

  • Around 10% average MRR improvement occurs for one-to-one relations versus ConvE + W-GCN.
  • 10.5% average MRR improvement occurs for one-to-many relations versus the best-performing baseline.
  • 7.5% average MRR improvement occurs for many-to-one relations versus the best-performing baseline.
  • 4% average MRR improvement occurs for many-to-many relations versus the best-performing baseline.
  • The results indicate that COMPGCN handles both simple and complex relation patterns effectively.

A.2 DATASET DETAILS

The evaluation uses separate datasets for link prediction, node classification, and graph classification, covering knowledge graphs, molecules, museum artifacts, and chemical compounds.

  • Link Prediction: FB15k-237 and WN18RR are used for link prediction, with inverse relations removed from FB15k-237 to prevent direct inference.
  • Node Classification: MUTAG (Node) tests carcinogenicity identification for complex molecules, while AM predicts Amsterdam Museum artifact categories from links and attributes.
  • Graph Classification: MUTAG (Graph) contains 188 compounds classified by mutagenic effect on a bacterium.
  • Table 7 summarizes the datasets used across all three evaluation tasks.
  • Graph Classification: PTC contains 344 chemical compounds labeled by carcinogenicity in male and female rats.

A.3 HYPERPARAMETERS

The implementation evaluates COMPGCN with task-specific training settings, including embedding dimensions, validation procedures, losses, graph readout, and common optimization choices.

  • All tasks use COMPGCN built on the PyTorch Geometric framework.
  • Link Prediction: Link prediction uses 200-dimensional node and relation embeddings, validation-based hyperparameter selection, and binary cross-entropy with label smoothing.
  • Node Classification: Node classification uses 10% of training data for validation, 32 hidden units, and cross-entropy loss.
  • Graph Classification: Graph classification reports mean and standard deviation across 10-fold cross-validation and averages node embeddings for graph-level representations.
  • Adam optimization and Xavier initialization are used for all experiments.
Loading 1911.03082v2…