End to end learning and optimization on graphs

Abstract

Real-world applications often combine learning and optimization problems on graphs. For instance, our objective may be to cluster the graph in order to detect meaningful communities (or solve other common graph optimization problems such as facility location, maxcut, and so on). However, graphs or related attributes are often only partially observed, introducing learning problems such as link prediction which must be solved prior to optimization. Standard approaches treat learning and optimization entirely separately, while recent machine learning work aims to predict the optimal solution directly from the inputs. Here, we propose an alternative decision-focused learning approach that integrates a differentiable proxy for common graph optimization problems as a layer in learned systems. The main idea is to learn a representation that maps the original optimization problem onto a simpler proxy problem that can be efficiently differentiated through. Experimental results show that our ClusterNet system outperforms both pure end-to-end approaches (that directly predict the optimal solution) and standard approaches that entirely separate learning and optimization. Code for our system is available at https://github.com/bwilder0/clusternet.

Accepted at NeurIPS 2019

References in corpus (11)

• Modularity and community structure in networks
• Finding community structure in very large networks
• Finding community structure in networks using the eigenvectors of matrices
• Learning Combinatorial Optimization Algorithms over Graphs
• Attention, Learn to Solve Routing Problems!
• Task-based End-to-end Model Learning in Stochastic Optimization
• Differentiable Dynamic Programming for Structured Prediction and Attention
• Learning Role-based Graph Embeddings
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• GAP: Generalizable Approximate Graph Partitioning Framework
• Detecting community structure in networks using edge prediction methods

Cited by in corpus (15)

• Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• Graph Neural Network Based Coarse-Grained Mapping Prediction
• Decision Trees for Decision-Making under the Predict-then-Optimize Framework
• On Training Implicit Models
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Solving Structured Hierarchical Games Using Differential Backward Induction
• Fuzzy c-Means Clustering for Persistence Diagrams
• Learning Graph Structure With A Finite-State Automaton Layer
• Understanding Deep Architectures with Reasoning Layer
• Task-Based Learning via Task-Oriented Prediction Network with Applications in Finance
• Partition and Code: learning how to compress graphs
• Balanced Order Batching with Task-Oriented Graph Clustering
• OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems
• Fully Linear Graph Convolutional Networks for Semi-Supervised Learning and Clustering