PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-dimensional Graph Convolutional Networks

Yao Ma, Suhang Wang, Charu C. Aggarwal, Dawei Yin, Jiliang Tang

arXiv:1808.06099v1cs.SI

TL;DR

Multi-dimensional graphs contain multiple relation types and interactions across dimensions, which single-dimensional graph convolutional networks are not designed to capture. This paper proposes mGCN to model within- and across-dimension interactions for node representations, and reports that it outperforms baselines across settings on two datasets.

  • Problem

    Many real-world graphs have multiple relation types and cross-dimension interactions, while most graph convolutional networks are designed for single-dimensional graphs.

    Source: §1 · p. 1

  • Method

    mGCN models within- and across-dimension interactions using dimension-specific node representations, then combines them into general representations.

    Source: §1 · p. 2, §2 · p. 2, §2.4 · p. 5

  • Results

    mGCN outperforms all baselines across settings on the Epinions and DBLP node-classification datasets.

    Source: §3.3.1 · p. 7

  • Takeaways & Limitations

    The authors conclude that mGCN is effective on two real-world multi-dimensional networks.

    Source: §5 · p. 9

    The within- and across-dimension aggregations are combined by weighted average; the authors suggest exploring more advanced combinations and temporal information.

    Source: §5 · p. 9

Abstract

from arXiv · show

Convolutional neural networks (CNNs) leverage the great power in representation learning on regular grid data such as image and video. Recently, increasing attention has been paid on generalizing CNNs to graph or network data which is highly irregular. Some focus on graph-level representation learning while others aim to learn node-level representations. These methods have been shown to boost the performance of many graph-level tasks such as graph classification and node-level tasks such as node classification. Most of these methods have been designed for single-dimensional graphs where a pair of nodes can only be connected by one type of relation. However, many real-world graphs have multiple types of relations and they can be naturally modeled as multi-dimensional graphs with each type of relation as a dimension. Multi-dimensional graphs bring about richer interactions between dimensions, which poses tremendous challenges to the graph convolutional neural networks designed for single-dimensional graphs. In this paper, we study the problem of graph convolutional networks for multi-dimensional graphs and propose a multi-dimensional convolutional neural network model mGCN aiming to capture rich information in learning node-level representations for multi-dimensional graphs. Comprehensive experiments on real-world multi-dimensional graphs demonstrate the effectiveness of the proposed framework.

1 INTRODUCTION

Graph convolutional networks commonly target single-dimensional graphs, but real-world networks can contain multiple relation types between nodes. The paper proposes mGCN to model interactions within and across dimensions and combine the resulting information for node-level representation learning.

1 INTRODUCTION

  • Earlier graph convolutional neural network work includes graph-level and node-level representation learning, with reported applications such as graph classification and node classification.This paper focuses on node-level representation learning.Source: §1 · p. 1
  • Prior graph convolutional networks often model only one relation type between a node pair, whereas real-world networks may have several.Examples include subscription, sharing, and commenting on YouTube, and viewing and purchasing on Amazon.Source: §1 · p. 1
  • Multiple relation types can connect node pairs, and relations across dimensions can interact, challenging graph convolutional networks designed for single-dimensional graphs.The paper frames the task as modeling both within-dimension and across-dimension node interactions, then combining their information.Source: §1 · p. 1
  • mGCN combines a principled approach to within- and across-dimension interactions with a framework for node-level representation learning on multi-dimensional graphs.The paper also reports experiments on real-world multi-dimensional graphs.Source: §1 · p. 2

2 THE PROPOSED FRAMEWORK

mGCN represents each node with dimension-specific and general representations, then models within- and across-dimension interactions and combines their information. Its layers repeat this process, with linkage-based unsupervised training and sampling for optimization.

2.1 General and dimension-specific representations

  • A general node representation is projected into dimension-specific representations, which are concatenated and combined by a feed-forward network to form a general representation.Generating the dimension-specific representations from the same general representation allows them to share information; the procedure is also described as reducing representation parameters.Source: §2.1 · p. 3

2.2 Modeling the within-dimension interactions

  • Within each dimension, mGCN applies single-dimensional GCN aggregation over within-dimension neighbors using a row-normalized adjacency matrix with self-loops.The node itself is included among its within-dimension neighbors.Source: §2.2 · p. 4

2.3 Modeling the across-dimension interactions

  • Across dimensions, mGCN takes a weighted average of a node's dimension-specific representations, learning dimension importance from projection matrices with bilinear attention and softmax normalization.The method uses learned projection matrices because dimension correlations may not be explicitly available beforehand.Source: §2.3 · p. 4

2.4 Multi-dimensional Graph Convolutional Networks

  • Each mGCN layer transforms general representations into dimension-specific ones, aggregates within- and across-dimension information, combines those results, and produces the next general representations.A hyperparameter controls the relative importance of the within- and across-dimension aggregation components.Source: §2.4 · p. 4
  • The model uses an unsupervised linkage-based loss to estimate whether node pairs are linked in each dimension, with positive and negative triplets as samples.The negative samples are non-links for a fixed source node and dimension.Source: §2.4 · p. 5

2.5 An Optimization Method

  • Optimization uses negative sampling, samples within-dimension neighbors for aggregation, and applies mini-batch ADAM.For each positive link, the negative-sample set is formed by randomly sampling non-neighbors; the stated sampling size is n times the positive-sample set.Source: §2.5 · pp. 5–6

3 EXPERIMENTS

Experiments evaluate mGCN on two real-world multi-dimensional graphs using node classification and link prediction. The reported results favor mGCN over the baselines in node classification, while link-prediction performance varies by dimension and mGCN exceeds single-dimensional methods on average comparisons.

3.1 Datasets

  • The experiments use DBLP yearly co-authorship dimensions and Epinions dimensions for co-review, helpfulness-rating, co-rating, trust, and distrust.DBLP covers publications from 1998–2017; user labels are assigned from publication or product categories, respectively.Source: §3.1 · p. 6

3.2 Comparison algorithms

  • The comparison includes single-dimensional embedding baselines applied to an aggregated graph, a multi-dimensional MINES baseline, GCN, and mGCN-noa.The authors omit applying single-dimensional methods separately to each dimension and aggregating representations, citing likely data sparsity.Source: §3.2 · pp. 6–7

3.3 Node Classification

  • Node classification hides 10%–90% of labels, trains logistic regression on 64-dimensional representations, and averages results over 10 train/test splits.The metrics are F1-macro and F1-micro; mGCN uses its general representations.Source: §3.3 · p. 7

3.3.1 Experiments Results.

  • mGCN outperforms all baselines across every tested setting on Epinions and DBLP node classification.The comparisons are shown in Figures 4 and 5.Source: §3.3.1 · p. 7, Figure 4 · p. 8, Figure 5 · p. 8
  • The mGCN node-classification scores exceed GCN, MINES, and mGCN-noa, supporting the use of multi-dimensional relations and across-dimension attention.The authors attribute the comparisons with MINES and mGCN-noa to capturing within- and across-dimension information and to the attention mechanism, respectively.Source: §3.3.1 · p. 7

3.4 Link prediction

  • Link prediction removes links by dimension, balances positive and randomly sampled negative pairs, and evaluates AUC; DBLP uses only its 2017 dimension.Epinions uses 20% link removal in each of five dimensions; DBLP uses 50% or 70% removal in its final dimension.Source: §3.4 · p. 7

3.4.1 Experiments Results.

  • On Epinions link prediction, performance varies substantially by dimension, single-dimensional methods trail MINES and the mGCN variants, and mGCN beats GCN and mGCN-noa on average.Table 3 reports AUC by dimension and an average; the DBLP results are described as similar.Source: §3.4.1 · p. 8, Table 3 · p. 8

3.5 Components Analysis

  • With α tested at 0, 0.3, 0.5, 0.7, and 1, both F1 metrics peak around 0.5 and decline beyond it, while either component alone performs poorly.The authors interpret the trend as evidence that within- and across-dimension information are complementary.Source: §3.5 · pp. 8–9, Figure 7 · p. 9

4 RELATED WORK

Prior work extends representation learning and convolution from regular data to graphs, while multi-dimensional graph embeddings and graph convolution address distinct parts of the setting. Most graph convolution methods discussed here target single-dimensional graphs, motivating the paper’s focus on multi-dimensional graphs.

4 RELATED WORK

  • Isomap and Laplacian Eigenmap reduce graph dimensions but usually require computationally expensive eigen-decomposition, limiting scalability to large graphs.Source: §4 · p. 9
  • DeepWalk, LINE, and node2vec draw on word embedding and can scale to graphs with millions of nodes.Source: §4 · p. 9
  • Multi-dimensional network embedding methods extend word-embedding approaches to multi-dimensional graphs.Source: §4 · p. 9
  • Some graph convolution methods target graph-level representations [6] [14] [26], while others learn node representations [20] [33].Source: §4 · p. 9
  • Most graph convolution methods discussed are designed for single-dimensional graphs, whereas many real-world graphs have multiple relation types.Source: §4 · p. 9

5 CONCLUSIONS AND FUTURE WORK

The paper presents mGCN, which combines dimension-specific and general node representations while modeling within- and across-dimension interactions. Experiments on two real-world multi-dimensional networks demonstrate the framework’s effectiveness; the authors identify representation combination and temporal information as future directions.

5 CONCLUSIONS AND FUTURE WORK

  • mGCN uses dimension-specific representations for each dimension and general representations for the graph, modeling within- and across-dimension interactions before combining them with a fully connected layer.Source: §5 · p. 9
  • Experiments on two real-world multi-dimensional networks demonstrate the proposed framework’s effectiveness.Source: §5 · p. 9
  • The current model combines within- and across-dimension representations by weighted average; nonlinear or feed-forward combinations are suggested for exploration.Source: §5 · p. 9
  • The authors identify temporal information, such as link creation timestamps in within-dimension aggregation, as a future direction.Source: §5 · p. 9

Related papers

Loading 1808.06099v1…