See the published version of this article at Computational Social Networks.
This is a preprint, a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
Research
Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs
Jiang Zhang
Beijing Normal University
Corresponding Author
License:
This work is licensed under a CC BY 4.0 License. Read Full License
View the published version at Computational Social Networks.
In computer science, there exist a large number of optimization problems defined on graphs, that is to find a best node state configuration or a network structure such that the designed objective function is optimized under some constraints. However, these problems are notorious for their hardness to solve because most of them are NP-hard or NP-complete. Although traditional general methods such as simulated annealing (SA), genetic algorithms (GA) and so forth have been devised to these hard problems, their accuracy and time consumption are not satisfying in practice. In this work, we proposed a simple, fast, and general algorithm framework based on advanced automatic differentiation technique empowered by deep learning frameworks. By introducing Gumbel-softmax technique, we can optimize the objective function directly by gradient descent algorithm regardless of the discrete nature of variables. We also introduce evolution strategy to parallel version of our algorithm. We test our algorithm on four representative optimization problems on graph including modularity optimization from network science, Sherrington-Kirkpatrick (SK) model from statistical physics, maximum independent set (MIS) and minimum vertex cover (MVC) problem from combinatorial optimization on graph, and Influence Maximization problem from computational social science. High-quality solutions can be obtained with much less time consuming compared to traditional approaches.
Keywords
Optimization problems on graphs, Gumbel-softmax, Evolution strategy
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Due to technical limitations, full-text HTML conversion of this manuscript could not be completed. However, the manuscript can be downloaded and accessed as a PDF.
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Published
Version 2
Posted 09 Sep, 2020
Published
On 01 Feb, 2021
No community comments so far
Editorial decision: Accept
On 06 Dec, 2020
Review #1 received
Received 14 Nov, 2020
Reviewer #1 agreed
On 16 Oct, 2020
Reviewers invited
Invitations sent on 15 Oct, 2020
Editor assigned
On 05 Sep, 2020
Submission checks complete
On 04 Sep, 2020
Editor invited
On 04 Sep, 2020
No comments provided
Editorial decision: Minor Revision
On 12 Jul, 2020
Review #1 received
Received 11 Jul, 2020
Reviewer #1 agreed
On 25 May, 2020
Reviewers invited
Invitations sent on 24 Apr, 2020
Editor assigned
On 15 Apr, 2020
First submitted
On 14 Apr, 2020
Submission checks complete
On 14 Apr, 2020
Editor invited
On 14 Apr, 2020
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Systems and Networking
Learn more about our company.
This preprint is under consideration at Computational Social Networks. A preprint is a preliminary version of a manuscript that has not completed peer review at a journal. Research Square does not conduct peer review prior to posting preprints. The posting of a preprint on this server should not be interpreted as an endorsement of its validity or suitability for dissemination as established information or for guiding clinical practice.
Learn more about In Review
Research
Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphs
Jiang Zhang
Beijing Normal University
Corresponding Author
Badges
Prescreen
This manuscript passed our Prescreen assessment
Complete author information
Appropriate declaration statements
Potential risks to human health
Prescreen
Peer Review Timeline
CURRENT STATUS: Published
Version 2
Posted 09 Sep, 2020
Published
On 01 Feb, 2021
No community comments so far
Editorial decision: Accept
On 06 Dec, 2020
Review #1 received
Received 14 Nov, 2020
Reviewer #1 agreed
On 16 Oct, 2020
Reviewers invited
Invitations sent on 15 Oct, 2020
Editor assigned
On 05 Sep, 2020
Submission checks complete
On 04 Sep, 2020
Editor invited
On 04 Sep, 2020
No comments provided
Editorial decision: Minor Revision
On 12 Jul, 2020
Review #1 received
Received 11 Jul, 2020
Reviewer #1 agreed
On 25 May, 2020
Reviewers invited
Invitations sent on 24 Apr, 2020
Editor assigned
On 15 Apr, 2020
First submitted
On 14 Apr, 2020
Submission checks complete
On 14 Apr, 2020
Editor invited
On 14 Apr, 2020
Metrics
Comments: 0
PDF Downloads: ...
HTML Views: ...
Subject Areas
Systems and Networking
License:
This work is licensed under a CC BY 4.0 License. Read Full License
View the published version at Computational Social Networks.
In computer science, there exist a large number of optimization problems defined on graphs, that is to find a best node state configuration or a network structure such that the designed objective function is optimized under some constraints. However, these problems are notorious for their hardness to solve because most of them are NP-hard or NP-complete. Although traditional general methods such as simulated annealing (SA), genetic algorithms (GA) and so forth have been devised to these hard problems, their accuracy and time consumption are not satisfying in practice. In this work, we proposed a simple, fast, and general algorithm framework based on advanced automatic differentiation technique empowered by deep learning frameworks. By introducing Gumbel-softmax technique, we can optimize the objective function directly by gradient descent algorithm regardless of the discrete nature of variables. We also introduce evolution strategy to parallel version of our algorithm. We test our algorithm on four representative optimization problems on graph including modularity optimization from network science, Sherrington-Kirkpatrick (SK) model from statistical physics, maximum independent set (MIS) and minimum vertex cover (MVC) problem from combinatorial optimization on graph, and Influence Maximization problem from computational social science. High-quality solutions can be obtained with much less time consuming compared to traditional approaches.
Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Due to technical limitations, full-text HTML conversion of this manuscript could not be completed. However, the manuscript can be downloaded and accessed as a PDF.