Graph transformer with high-degree nodes anchoring for graph partitioning.

Area of Science:

• Computer Science
• Artificial Intelligence
• Machine Learning

Background:

• Graph partitioning is crucial for dividing nodes into balanced subsets.
• Graph Neural Networks (GNNs) are increasingly used but struggle with global balancing and anchor node smoothing.
• Existing GNNs primarily focus on local graph structures, neglecting essential global context.

Purpose of the Study:

• To develop an improved graph partitioning method addressing limitations of current GNNs.
• To integrate both local and global graph information for superior partitioning performance.
• To leverage high-degree nodes as anchors for more accurate and balanced partitions.

Main Methods:

• A local-global graph Transformer network is proposed, calculating attention between connected nodes and a global virtual node.
• High-degree nodes are identified as vital and used as anchors, with labels assigned via traditional methods.
• A semi-supervised framework combines traditional graph partitioning loss with supervised loss from high-degree node anchoring.

Main Results:

• The proposed graph Transformer network effectively combines local and global graph structures.
• The method demonstrates superior balancing properties in graph partitioning.
• Experimental results show the model outperforms both heuristic and existing deep learning methods on key partition metrics.

Conclusions:

• The novel graph Transformer network with anchor nodes offers a significant advancement in graph partitioning.
• Integrating local-global attention and high-degree node anchoring leads to improved partitioning accuracy and balance.
• This approach provides a robust alternative to existing methods for complex graph partitioning tasks.