Source-linked AI summary
Approximation Ratios of Graph Neural Networks for Combinatorial Problems
Ryoma Sato, Makoto Yamada, Hisashi Kashima
TL;DR
The paper asks how powerful GNNs are for learning approximation algorithms for combinatorial problems. It introduces stronger GNN classes and connects them to distributed local algorithms, establishing approximation limits and showing that coloring-based features improve them.
Problem
The paper addresses the limited theoretical understanding of what approximation ratios GNNs can achieve for NP-hard combinatorial problems.
Method
The paper introduces VVC-GNNs and CPNGNNs and uses their relationship with distributed local algorithms to analyze GNN capabilities.
Results
CPNGNNs achieve (∆+1)-approximation for minimum dominating set and 2-approximation for minimum vertex cover, while degree-only features impose corresponding lower bounds for all GNNs.
Takeaways & Limitations
Adding coloring or weak coloring to node features theoretically improves approximation ratios, indicating that preprocessing and feature engineering strengthen GNN capability.
Takeaways & Limitations
The analysis assumes bounded-degree graphs, and handling graphs without degree bounds is described as difficult.
Abstract
from arXiv · showhide
In this paper, from a theoretical perspective, we study how powerful graph neural networks (GNNs) can be for learning approximation algorithms for combinatorial problems. To this end, we first establish a new class of GNNs that can solve a strictly wider variety of problems than existing GNNs. Then, we bridge the gap between GNN theory and the theory of distributed local algorithms. We theoretically demonstrate that the most powerful GNN can learn approximation algorithms for the minimum dominating set problem and the minimum vertex cover problem with some approximation ratios with the aid of the theory of distributed local algorithms. We also show that most of the existing GNNs such as GIN, GAT, GCN, and GraphSAGE cannot perform better than with these ratios. This paper is the first to elucidate approximation ratios of GNNs for combinatorial problems. Furthermore, we prove that adding coloring or weak-coloring to each node feature improves these approximation ratios. This indicates that preprocessing and feature engineering theoretically strengthen model capabilities.
1 Introduction
The paper studies how GNNs can learn approximation algorithms for NP-hard combinatorial problems, introducing stronger models and relating GNN capability to distributed local algorithms.
- Motivation: GNNs cannot exactly solve the discussed NP-hard problems under P ≠ NP, motivating approximation-ratio analysis for learned algorithms.The paper focuses on minimum dominating set, minimum vertex cover, and related combinatorial problems.
- Approach: The paper bridges GNN theory and distributed local algorithms to analyze approximation ratios and derive lower bounds for algorithms GNNs can learn.Distributed local algorithms use only a constant number of synchronous communication rounds.
- Main results: With degree-only node features, no GNN can achieve (∆+1−ε)-approximation for minimum dominating set or (2−ε)-approximation for minimum vertex cover.Here ε > 0 and ∆ is the maximum node degree.
- Main results: CPNGNNs are the most powerful proposed GNNs and achieve (∆+1)-approximation for minimum dominating set and 2-approximation for minimum vertex cover.They are strictly more powerful than GIN and attain optimal approximation ratios among GNNs.
- Feature engineering: Adding coloring or weak coloring to node features improves approximation ratios, showing that preprocessing and feature engineering can strengthen GNN capability.Weak 2-coloring is given as an example of an additional feature.
2 Related Work
The related work positions GNNs among graph-learning and combinatorial-optimization methods, while introducing distributed local algorithms as a theoretical comparison framework.
- Graph neural networks: GNNs have been developed in variants including GCN, GraphSAGE, and GAT, while GIN was presented as powerful as the Weisfeiler-Lehman test.The paper builds on prior analyses of GNN expressive capability.
- Combinatorial optimization: Prior deep-learning approaches applied pointer networks and GNNs to combinatorial problems, sometimes combining GNNs with search methods.This paper studies using GNNs alone rather than relying on search methods.
- Distributed local algorithms: A distributed local algorithm lets nodes decide outputs using infinite local computation and a constant number of communication rounds.Such algorithms have applications including wireless sensor networks and sublinear-time algorithms.
- Distributed local algorithms: Distributed local-algorithm models differ in their use of node identifiers, port numbering, randomness, and graph assumptions such as bounded degree.The paper uses port numbering and assumes bounded-degree graphs without unique identifiers or randomness.
3 Preliminaries
The preliminaries define bounded-degree graph problems, node-feature assumptions, and existing GNN classes that aggregate and broadcast neighborhood information in different ways.
- Problem setting: A GNN model maps a graph and node to a node label, providing the formal interface used to study expressive capability for graph problems.The model is parameterized by θ.
- Problem setting: The paper studies graph problems on bounded-degree graphs, where a GNN solves a problem when one parameter setting produces a valid solution for every graph in the degree-bounded family.A graph problem associates each graph with a set of node-labeling solutions.
- Problem setting: The default node feature is a one-hot encoding of node degree, with coloring or weak coloring considered later as additional graph-derived features.The feature restriction is intended to focus on graph-theoretic properties.
- Known model classes: MB-GNNs aggregate neighbor features as a multiset and broadcast the same message from a node to all its neighbors.GraphSAGE-mean, GCN, GAT, and GIN are identified as examples.
- Known model classes: SB-GNNs use set-based aggregation and form a subclass of MB-GNNs, so MB-GNNs are strictly stronger in the paper’s analysis.GraphSAGE-pool is given as an example of SB-GNNs.
4 Novel Class of GNNs
The paper introduces port-numbered GNNs, including VVC-GNNs and CPNGNNs, which can send different messages across incident edges and thereby exceed existing model classes.
- Port numbering: A consistent port numbering pairs the two ports associated with each edge through an involutive mapping.The port functions identify the neighbor sending to a node’s port and that neighbor’s corresponding port.
- Port-numbered GNNs: Port numbering lets GNNs send different messages to different neighboring nodes, strengthening capability beyond models that broadcast identical messages.This construction is based on consistent port numberings.
- VVC-GNNs: VVC-GNNs are a new class that computes embeddings using port-numbered neighbor information, with the embedding assembled from port-specific inputs.The displayed construction includes port-tail and port-number terms for neighboring positions.
- CPNGNNs: CPNGNNs are proposed as an example of VVC-GNNs, and any graph problem solvable by a VVC-GNN is solvable by some CPNGNN parameterization.The paper presents CPNGNNs as the most powerful model among VVC-GNNs.
5 GNNs with Distributed Local Algorithms
The paper connects GNN classes with distributed local algorithms and uses that connection to characterize their relative problem-solving power. It shows that VVC-GNNs can solve a problem that MB-GNNs cannot, while CPNGNNs represent the most powerful VVC-GNN model.
- 5.2 Hierarchy of GNNs: CPNGNNs are the most powerful VVC-GNNs, with a parameter choice capable of solving every graph problem solvable by a VVC-GNN.The model is introduced as the consistent-port-numbering variant of VVC-GNNs.
- 5.1 Relationship with Distributed Local Algorithms: Theorem 1 equates the graph problems solvable by L-GNNs with those solvable by distributed local algorithms on the corresponding L(1) model.The equivalence holds for SB, MB, and VVC classes under finite node features.
- 5.1 Relationship with Distributed Local Algorithms: The correspondence supports simulating any L-GNN with the L(1) model and any distributed local algorithm on L(1) with an L-GNN.This lets distributed-local-algorithm results establish which combinatorial problems GNNs can or cannot solve.
- 5.2 Hierarchy of GNNs: SB-GNNs form a subclass of MB-GNNs, which form a subclass of VVC-GNNs; the paper uses distributed-local-algorithm results to establish these inclusions are proper.The hierarchy is considered for model classes using degree features.
- 5.2 Hierarchy of GNNs: VVC-GNNs can find a single leaf in a star graph, whereas MB-GNNs cannot distinguish the graph’s leaf nodes and cannot solve that task.Port numbering distinguishes the leaf nodes for VVC-GNNs; the paper reports supplementary experiments confirming the distinction.
6 Most Powerful GNN for Combinatorial Problems
CPNGNNs characterize the strongest proposed GNN capability for combinatorial problems, matching VVC-GNNs and connecting to distributed local algorithms. Their approximation limits depend strongly on node features: degree-only features yield weak guarantees, while weak 2-coloring improves some problems.
- CPNGNNs: CPNGNNs solve exactly the graph problems solvable by VVC-GNNs and are supported as the most powerful model in that class.Theorem 3 establishes equality between the problem sets solved by CPNGNNs and VVC-GNNs; the model can simulate many distributed local algorithms.
- Minimum Dominating Set Problem: For minimum dominating set, degree-only CPNGNNs achieve optimal approximation ratio ∆+1, matching the trivial all-nodes algorithm.They cannot solve any α-approximation for 1 ≤ α < ∆+1, and the paper identifies this as a worst-case limitation of degree-only features.
- Minimum Vertex Cover Problem: For minimum vertex cover, CPNGNNs achieve optimal approximation ratio 2, and any α < 2 is impossible.Although this matches the simple greedy algorithm, the corresponding distributed local algorithm is not straightforward.
- Scope: Theoretical guarantees are restricted to bounded-degree graphs, and removing that assumption makes the graph problems more difficult.The paper explicitly limits its analysis to bounded-degree graphs and states the general case is not covered by the reported guarantees.
7 Conclusion
The paper introduces VVC-GNNs and CPNGNNs, relates their capabilities to distributed local algorithms, and derives approximation ratios for combinatorial graph problems. It also shows that coloring-based node features improve these ratios, highlighting preprocessing and feature engineering as capability-strengthening mechanisms.
- VVC-GNNs have the same ability to solve graph problems as a computational model of distributed local algorithms, while CPNGNNs are an example of VVC-GNNs.
- The paper elucidates approximation ratios learnable by CPNGNNs for minimum dominating set and minimum vertex cover, and presents these as lower bounds for all GNNs.
- Adding coloring or weak coloring to node features improves approximation ratios for combinatorial graph problems.
- These results indicate that preprocessing and feature engineering theoretically strengthen GNN model capability.
A Proofs
The proofs establish equivalence between VVC-GNNs and distributed local algorithms, characterize relative model power, and derive approximation-ratio consequences for several graph problems.
- Theorem 1 establishes that VVC-GNNs and distributed local algorithms on the VVC(1) model solve the same set of graph problems.
- The proof constructs each direction of the equivalence: VVC-GNN inference gives a distributed local algorithm, and each such algorithm can be represented by a VVC-GNN.
- With degree features, the solvable problem classes satisfy PSB-GNNs ⊊ PMB-GNNs ⊊ PVVC-GNNs.
- The CPNGNN proof uses consistent port numbering to reconstruct local views and show that CPNGNNs can match the capabilities of VVC-GNNs.
- For minimum vertex cover, the optimal VVC approximation ratio is 2, while maximum matching has no optimal ratio without coloring but admits stated coloring-dependent guarantees.
B How to Calculate a Consistent Port Numbering and a Weak 2-Coloring
The paper describes linear-time procedures for calculating consistent port numbering and weak 2-coloring.
- A consistent port numbering can be calculated in linear time, and the paper provides its procedure in Algorithm 3.
- A weak 2-coloring can also be calculated in linear time using breadth-first search, with Algorithm 4 providing the procedure.
- When the input graph is bipartite, the weak-coloring procedure returns a 2-coloring.
C Experiments
Experiments test whether CPNGNNs can solve the single-leaf problem on star graphs, which existing multiset-broadcasting GNNs cannot solve. CPNGNNs solve the task across all reported training trials, whereas GCN, GraphSAGE, and GAT do not.
- The task requires selecting a single leaf from a star graph, while non-star inputs may produce any node subset.
- No MB-GNN can solve the task because all leaf nodes have identical latent vectors at every layer and therefore receive the same decision.
- After 10000 training iterations, the two-layer CPNGNN solved the finding single leaf problem in all 10 trials with different seeds.The experiment used a four-node star graph with one center and three leaves for training and testing.
- GCN, GraphSAGE, and GAT failed to solve the finding single leaf problem, consistent with the theoretical limitation of existing GNNs.