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.
Introduction
Graph Joint Attention Networks (CATs) represent a significant evolution of the popular Graph Attention Network (GAT) framework. While standard GNNs have revolutionized graph representation learning, they often suffer from "structural blindness." Most attention-based GNNs calculate weights based solely on internal node features, ignoring the broader structural context—such as community clusters or higher-order topological similarities—that exists outside the immediate neighborhood. This reliance on local features can also lead to overfitting, limiting the model's ability to generalize.
CATs address these issues by allowing the model to "look beyond" simple node features. By integrating external structural information into the attention mechanism, CATs not only achieve state-of-the-art performance on node classification and clustering tasks but also reach the theoretical upper bound of expressive power for message-passing neural networks.
Methodology: Conjoint Attentions
The core innovation of CATs is the Conjoint Attention (CA) mechanism, which combines traditional feature-based attention with "structural interventions."
Structural Interventions
Before the GNN execution, the model generates a structural correlation matrix ($C$). The authors propose two primary methods for this:
- Matrix Factorization (MF): Captures node cluster or community embeddings efficiently.
- Self-Expressiveness (SC): Captures global structural correlations, providing a more comprehensive view of the graph's topology.
The Conjoint Layer Architecture
The conjoint layer calculates two distinct scores for every edge: a feature similarity score ($f_{ij}$) and a structural similarity score ($s_{ij}$). These are integrated using one of two strategies:
- Implicit Direction (CAT-I): The model learns parameters to automatically balance the importance of features versus structure.
- Explicit Direction (CAT-E): The structural score acts as a hard filter, ensuring that nodes that are structurally irrelevant do not receive high attention weights regardless of feature similarity.
Theoretical Expressiveness
To ensure theoretical robustness, CATs include a learnable parameter ($\epsilon$) for the center node's self-loop. This design choice allows the model to distinguish between different graph multisets, making it as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) test, the gold standard for GNN discriminative capacity.
Experimental Results
The effectiveness of CATs was evaluated across five benchmarking datasets: Cora, Cite, and Pubmed (citation networks), CoauthorCS (co-authorship), and the large-scale OGB-Arxiv dataset.
Performance in Node Classification
CAT variants consistently outperformed a wide array of baselines, including GCN, GAT, GraphSAGE, and GIN. Notably, on the challenging OGB-Arxiv dataset, CATs showed significant improvements over standard GAT, demonstrating their utility in real-world, large-scale scenarios.
Efficiency and Scalability
Despite the additional computational steps for structural interventions, the Matrix Factorization (MF) variant remains highly efficient. On the massive OGB-Arxiv dataset, CAT-I-MF required only approximately 1GB more memory than a standard GAT, making it a viable candidate for industrial-scale applications.
Discussion and Conclusion
CATs demonstrate that graph structure should be treated as a "first-class citizen" in the attention mechanism rather than just a roadmap for message passing. By moving beyond simple feature concatenation and using conjoint attention, the model achieves a smoother integration of diverse information types.
While the Self-Expressiveness (SC) strategy offers deep structural insights, it comes with higher space complexity. Future work may focus on optimizing SC for extremely large graphs or exploring adversarial training to improve robustness against noisy structural data. Overall, CATs provide a powerful and theoretically grounded framework for more expressive and accurate graph representation learning.
Summary updated