Learning Conjoint Attentions for Graph Neural Nets

Tiantian He, Yew Soon Ong, Lu Bai

TL;DR

Standard Graph Attention Networks (GATs) often suffer from "tunnel vision," focusing primarily on internal node features while ignoring broader structural context. This paper introduces Conjoint Attentions (CAs), a novel framework that blends internal node features with external "structural interventions" (such as cluster memberships). This approach creates more expressive and robust Graph Conjoint Attention Networks (CATs) that consistently outperform state-of-the-art baselines in both node classification and clustering tasks.

The Problem: Internal Factor Bias and Overfitting

Graph Neural Networks (GNNs) typically aggregate information from a node's neighbors to learn representations. Attention-based GNNs, like the popular GAT, improve upon this by learning to "weight" which neighbors are most important. However, the authors identify two major limitations in current attention mechanisms:

  1. Internal Factor Bias: Current attention mechanisms rely almost exclusively on layer-wise node features (internal factors). They largely ignore "external" structural information—such as whether two nodes belong to the same community or share higher-order structural similarities—that cannot be captured by local features alone.
  2. Overfitting: Relying too heavily on raw node features can lead to overfitting during training, limiting the model's ability to generalize to unseen data.

The goal of this research is to design a more "purposeful" attention mechanism that considers both what a node is (its features) and where it sits within the global graph (its structure).

Methodology: Conjoint Attentions and CATs

The authors propose Conjoint Attentions (CAs) and the resulting Graph Conjoint Attention Networks (CATs). The core innovation lies in introducing a "Structural Intervention" prior to the standard message-passing phase.

1. Structural Interventions

Before the GNN begins its layer-wise aggregation, the model calculates external structural correlations ($C_{ij}$) between nodes. The authors suggest two primary types of interventions:

  • Matrix Factorization (MF): Captures node cluster embeddings to represent community structure.
  • Self-Expressiveness (SC): Captures global relations, measuring how well one node can be represented by a linear combination of others.

2. Conjoint Attention Strategies

The model computes a feature-based attention score ($f_{ij}$) and a structural-based score ($s_{ij}$). It then combines them using one of two distinct strategies to form the final conjoint attention ($\alpha_{ij}$):

Architecture of Conjoint Attentions showing Implicit and Explicit strategies
  • Implicit Direction (CAT-I): The model learns two parameters ($r_f$ and $r_s$) to automatically balance the importance of features versus structure during training.
  • Explicit Direction (CAT-E): The structural score directly scales the feature score. If the structural intervention indicates two nodes are irrelevant, the feature-based attention is explicitly suppressed.

3. Theoretical Expressive Power

To back up their empirical design, the authors provide a rigorous theoretical proof. They demonstrate that by adding a specific "improving term" to their aggregation function, CATs can reach the theoretical upper bound of expressive power for message-passing GNNs (the 1-Weisfeiler-Lehman test). This means CATs can distinguish complex graph structures that standard GATs cannot.

Key Insights

  • Structure as a Prior: Instead of hoping the GNN learns the graph structure implicitly through layers of message passing, CATs treat structure as an explicit "intervention" or prior.
  • Beyond Local Neighbors: By using global structural metrics like Self-Expressiveness, the attention mechanism accounts for relationships that aren't immediately obvious from the local adjacency matrix.
  • Robustness through Diversity: Combining heterogeneous factors (features + structure) makes the attention scores more stable and less prone to the noise found in raw node features.

Empirical Results

The authors evaluated their models on five well-known benchmarks: Cora, Cite, Pubmed, CoauthorCS, and the massive OGB-Arxiv dataset. The CAT models were tested on both semi-supervised node classification and node clustering.

Node classification accuracy across five benchmark datasets
  • Classification: CAT-I and CAT-E consistently outperformed GAT, GCN, and other strong baselines. For example, on the challenging OGB-Arxiv dataset, CAT-I achieved an accuracy of ~72.89%, significantly higher than the standard GAT's ~72.39%.
  • Clustering: The performance gains were even more pronounced in clustering tasks, where structural information is vital. On OGB-Arxiv, CAT-I reached ~77.72% clustering accuracy, while standard GAT trailed at ~76.04%.
  • Ablation Study: The authors confirmed that using both features and structural interventions performed better than using either in isolation, validating the core "conjoint" hypothesis.

Limitations and Future Work

While highly effective, the framework has a few limitations:

  • Computational Complexity: While Matrix Factorization is efficient, the Self-Expressiveness (SC) strategy has high space complexity, making it difficult to scale to extremely large graphs without more efficient optimization methods.
  • Sensitivity to Intervention Quality: The model's performance is tied to the quality of the external structural metrics. If the chosen "intervention" is noisy or poorly suited to the graph, it could negatively impact the attention scores.

For future work, the authors suggest exploring adversarial strategies to make the model more robust to "contaminated" structural factors, as well as extending the Conjoint Attention framework to multi-view and heterogeneous graphs.

Summary updated

Abstract

In this paper, we present Conjoint Attentions (CAs), a class of novel learning-to-attend strategies for graph neural networks (GNNs). Besides considering the layer-wise node features propagated within the GNN, CAs can additionally incorporate various structural interventions, such as node cluster embedding, and higher-order structural correlations that can be learned outside of GNN, when computing attention scores. The node features that are regarded as significant by the conjoint criteria are therefore more likely to be propagated in the GNN. Given the novel Conjoint Attention strategies, we then propose Graph conjoint attention networks (CATs) that can learn representations embedded with significant latent features deemed by the Conjoint Attentions. Besides, we theoretically validate the discriminative capacity of CATs. CATs utilizing the proposed Conjoint Attention strategies have been extensively tested in well-established benchmarking datasets and comprehensively compared with state-of-the-art baselines. The obtained notable performance demonstrates the effectiveness of the proposed Conjoint Attentions.
BibTeX
@inproceedings{he2021learning,
  author = {Tiantian He and Yew Soon Ong and Lu Bai},
  title = {{Learning Conjoint Attentions for Graph Neural Nets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=XNDLiJ5DGM},
}
Figure