TL;DR
This paper introduces "Circle Features," novel local graph features inspired by social network "circles of friends," to enhance graph transformers for link prediction. By incorporating these features as biases into the self-attention mechanism, their proposed Circle Feature Graphormer (CFG) model achieves state-of-the-art performance on the ogbl-citation2 dataset.
What Problem Does This Paper Address?
Link prediction, the task of identifying missing connections in a graph, is crucial in many domains. While traditional methods rely on node and edge features or local neighborhood structures, recent advancements have leveraged Graph Neural Networks (GNNs) and Graph Transformers to capture deeper and global graph information. However, existing methods might still struggle to fully capture the nuanced local relationships that indicate a strong potential connection. This paper aims to improve link prediction by introducing new local features that better represent these "friendship" dynamics within a graph, specifically by borrowing the concept of "circles of friends."
Methods
The core contribution of this paper is the introduction of two novel "Circle Features":
- Modified Swing Feature: This feature is an adaptation of the "swing" concept, originally for bipartite graphs, to general graphs. It aims to quantify the strength of connection between two nodes based on their shared common neighbors, with a specific focus on how these neighbors form "circles."
- Bridge Feature: This feature measures the importance of bridges that connect different "circles of friends" for a pair of nodes. It quantifies how many shared circles exist between two nodes, indicating a potentially stronger relationship.
These circle features are then integrated into a Circle Feature aware Graph transformer (CFG) model. CFG builds upon the SIEG network, which uses a double-tower structure to capture both global and local graph information. Crucially, the circle features are incorporated as biases within the self-attention mechanism of the graph transformer. This allows the model to explicitly consider these local "friendship" dynamics when calculating attention scores, thereby enhancing its ability to predict missing links.
Datasets
The experiments were conducted on the ogbl-citation2 dataset. This dataset is a directed graph representing a citation network, where nodes are papers and edges represent citations. Each paper node is associated with 128-dimensional word2vec features summarizing its title and abstract, and meta-information about the publication year. The task involves predicting missing citations.
Key Insights and Ideas
- "Circles of Friends" as a Graph Feature: The paper successfully translates the intuitive concept of social circles into quantifiable graph features. This highlights the potential of drawing inspiration from social dynamics to improve graph representation learning.
- Local Features Enhance Global Models: By incorporating local "circle" information as biases into a powerful global model like a graph transformer, the CFG model demonstrates that local structural nuances can significantly boost the performance of models designed for global context.
- Bias Mechanism for Attention: Using circle features as biases in the self-attention mechanism is an effective way to guide the transformer's focus towards relevant local structures, rather than relying solely on learned attention weights.
Key Results
The proposed Circle Feature Graphormer (CFG) model achieved state-of-the-art performance on the ogbl-citation2 dataset for the link prediction task. Specifically, the paper reports that CFG outperforms all listed baseline methods. The results indicate that CFG, especially when using both the modified swing and bridge features (CFG2), demonstrates superior predictive accuracy, as measured by Mean Reciprocal Rank (MRR).
Limitations and Future Work
- Computational Complexity: While not explicitly detailed as a limitation, the computation of circle features might introduce additional computational overhead, especially for very large graphs.
- Generalizability: The paper focuses on the ogbl-citation2 dataset. Further research could explore the effectiveness of these circle features on other types of graphs and link prediction tasks.
- Future Work: The authors suggest optimizing transformer self-attention mechanisms further with circle features in future work. This implies exploring different integration methods or more complex feature definitions.
Summary updated