Attention Models with Random Features for Multi-layered Graph Embeddings

Uday Shankar Shanthamallu, Jayaraman J. Thiagarajan, Huan Song, Andreas SpaniasarXiv 2018 · OpenReview

TL;DR

This paper introduces GrAMME, a novel framework for semi-supervised learning on multi-layered graphs using attention mechanisms. It demonstrates that using simple random node attributes, combined with attention-based feature learning, can significantly outperform existing methods for node classification, even when explicit node features are unavailable.

What Problem Does This Paper Address?

Modern data often comes with multiple, interconnected views (e.g., social networks with different types of relationships, or biological networks with various interaction types). Representing this complex data as a single graph is insufficient, leading to the use of multi-layered graphs. However, extending existing graph learning techniques to these multi-layered structures is challenging. Specifically, the paper tackles the problem of semi-supervised node classification in multi-layered graphs, where only a subset of nodes have labels. A key challenge is learning effective node representations that capture both within-layer and across-layer dependencies, especially when explicit node attributes are scarce or absent.

Methods

The core of the proposed solution lies in leveraging graph attention networks (GATs) for feature learning. The authors introduce two novel architectures:

  • GrAMME-SG (Supra Graph): This approach constructs a "supra graph" by adding virtual edges between nodes with the same ID across different layers. This allows a standard GAT to process the entire interconnected structure, inferring inter-layer dependencies implicitly.
  • GrAMME-Fusion: This architecture takes a more modular approach. It first processes each layer independently using GATs and then uses a "supra fusion layer" with specialized fusion heads to combine the representations from each layer. This is computationally more efficient than GrAMME-SG.

A key innovation is the use of randomized node attributes as input features. Instead of relying on potentially unavailable explicit node features, the authors initialize node representations with random vectors. They then train the attention models end-to-end to learn embeddings that are highly effective for the downstream classification task. They also introduce a weighted attention mechanism that allows for more efficient learning by assigning varying importance to different attention heads.

Datasets

The paper evaluates its proposed methods on seven benchmark multi-layered graph datasets from diverse domains:

  • Vickers-Chan: Social structure of students.
  • Congress Votes: Congressional voting records.
  • Leskovec-Ng: Temporal collaboration network.
  • Reinnovation: Global Innovation Index data.
  • Mammography (UCI): Mammographic mass lesions.
  • CKM (Social): Information diffusion among physicians.
  • Balance Scale: Psychological experiment results.

These datasets vary in size, number of layers, and number of classes, providing a comprehensive evaluation.

Key Insights and Ideas

  • Random features are surprisingly powerful: The paper strongly advocates for using simple random node attributes as input for GATs in semi-supervised learning on graphs. This is a significant finding, as it bypasses the need for complex feature engineering or the availability of rich node attributes, which are often a bottleneck in real-world applications.
  • Attention excels at capturing inter-layer dependencies: The attention mechanism, originally designed for sequential data, proves to be a flexible and effective tool for modeling the complex relationships between layers in multi-layered graphs. It can learn these dependencies without explicit prior knowledge.
  • Two-pronged approach for multi-layered graphs: The GrAMME-SG and GrAMME-Fusion architectures offer distinct strategies for handling multi-layered data. GrAMME-SG's supra-graph approach is powerful when strong inter-layer dependencies exist, while GrAMME-Fusion's layer-wise processing with fusion is more computationally efficient and generally performs better.
  • Weighted attention for efficiency: The proposed weighted attention mechanism allows for significant performance gains with fewer attention heads, leading to reduced computational complexity, which is crucial for large multi-layered graphs.

Key Results

The proposed GrAMME architectures consistently outperform state-of-the-art baselines (DeepWalk, Node2Vec, LINE, PMNE, MNE) across all seven benchmark datasets.

  • Significant improvements: For instance, on the Vickers-Chan dataset, GrAMME achieved over 25% improvement compared to DeepWalk and about 14% over MNE.
  • Robustness with limited data: The methods demonstrate strong performance even with as little as 10% of labeled nodes, highlighting their effectiveness in low-data regimes.
  • Computational efficiency: GrAMME-Fusion, in particular, shows comparable performance to GrAMME-SG but with significantly lower computational complexity, making it more scalable.

Limitations and Future Work

  • GrAMME-SG over-parameterization: The paper notes that GrAMME-SG can sometimes over-parameterize inter-layer dependencies, potentially leading to noisy edges. This suggests that GrAMME-SG might be more suitable for scenarios with very strong, well-defined inter-layer dependencies.
  • Future Directions: The authors suggest extending their work to handle multimodal networks and interdependent networks. They also propose exploring the effectiveness of their attention models for other challenging graph inference tasks like multi-layered link prediction and influential node selection.

Summary updated

Abstract

Modern data analysis pipelines are becoming increasingly complex due to the presence of multi-view information sources. While graphs are effective in modeling complex relationships, in many scenarios a single graph is rarely sufficient to succinctly represent all interactions, and hence multi-layered graphs have become popular. Though this leads to richer representations, extending solutions from the single-graph case is not straightforward. Consequently, there is a strong need for novel solutions to solve classical problems, such as node classification, in the multi-layered case. In this paper, we consider the problem of semi-supervised learning with multi-layered graphs. Though deep network embeddings, e.g. DeepWalk, are widely adopted for community discovery, we argue that feature learning with random node attributes, using graph neural networks, can be more effective. To this end, we propose to use attention models for effective feature learning, and develop two novel architectures, GrAMME-SG and GrAMME-Fusion, that exploit the inter-layer dependencies for building multi-layered graph embeddings. Using empirical studies on several benchmark datasets, we evaluate the proposed approaches and demonstrate significant performance improvements in comparison to state-of-the-art network embedding strategies. The results also show that using simple random features is an effective choice, even in cases where explicit node attributes are not available.
BibTeX
@misc{shanthamallu2018attention,
  author = {Uday Shankar Shanthamallu and Jayaraman J. Thiagarajan and Huan Song and Andreas Spanias},
  title = {{Attention Models with Random Features for Multi-layered Graph Embeddings}},
  year = {2018},
  eprint = {1810.01405},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.01405},
}
Figure