📒
PaperNotes
  • PAPER NOTES
  • Meta-Learning with Implicit Gradient
  • DARTS: Differentiable Architecture Search
  • Meta-Learning of Neural Architectures for Few-Shot Learning
  • Towards Fast Adaptation of Neural Architectures with Meta Learning
  • Editable Neural Networks
  • ANIL (Almost No Inner Loop)
  • Meta-Learning Representation for Continual Learning
  • Learning to learn by gradient descent by gradient descent
  • Modular Meta-Learning with Shrinkage
  • NADS: Neural Architecture Distribution Search for Uncertainty Awareness
  • Modular Meta Learning
  • Sep
    • Incremental Few Shot Learning with Attention Attractor Network
    • Learning Steady-States of Iterative Algorithms over Graphs
      • Experiments
    • Learning combinatorial optimization algorithms over graphs
    • Meta-Learning with Shared Amortized Variational Inference
    • Concept Learners for Generalizable Few-Shot Learning
    • Progressive Graph Learning for Open-Set Domain Adaptation
    • Probabilistic Neural Architecture Search
    • Large-Scale Long-Tailed Recognition in an Open World
    • Learning to stop while learning to predict
    • Adaptive Risk Minimization: A Meta-Learning Approach for Tackling Group Shift
    • Learning to Generalize: Meta-Learning for Domain Generalization
  • Oct
    • Meta-Learning Acquisition Functions for Transfer Learning in Bayesian Optimization
    • Network Architecture Search for Domain Adaptation
    • Continuous Meta Learning without tasks
    • Learning Causal Models Online
    • Meta-Dataset: A Dataset of Datasets for Learning to Learn from Few Examples
    • Conditional Neural Progress (CNPs)
    • Reviving and Improving Recurrent Back-Propagation
    • Meta-Q-Learning
    • Learning Self-train for semi-supervised few shot classification
    • Watch, Try, Learn: Meta-Learning from Demonstrations and Rewards
  • Nov
    • Neural Process
    • Adversarially Robust Few-Shot Learning: A Meta-Learning Approach
    • Learning to Adapt to Evolving Domains
  • Tutorials
    • Relax constraints to continuous
    • MAML, FO-MAML, Reptile
    • Gradient Descent
      • Steepest Gradient Descent
      • Conjugate Gradient Descent
  • KL, Entropy, MLE, ELBO
  • Coding tricks
    • Python
    • Pytorch
  • ml
    • kmeans
Powered by GitBook
On this page
  • Motivation
  • Three common greedy algorithms on Graphs
  • Overview
  • Relation to Q-learning (taking MVC for example)
  • How to represent the node embedding:
  • How to measure the Q-value for each node:
  • Reference

Was this helpful?

  1. Sep

Learning combinatorial optimization algorithms over graphs

NIPS 2017 9-22-2020

PreviousExperimentsNextMeta-Learning with Shared Amortized Variational Inference

Last updated 4 years ago

Was this helpful?

Motivation

The current methods for combinatorial optimization problem cannot learn from experience.

Can we learn from experience?

Given a graph optimization problem GGG and a distribution DDD of problem instances, can we learn a better greedy heuristics that generalize to unseen instances from DDD ?

Three common greedy algorithms on Graphs

Given weighted graph: G(V,E,w)G(V,E,w)G(V,E,w) , www : edge weight function, w(u,v)w(u,v)w(u,v) is the weight of edge (u,v)∈E(u,v)\in E(u,v)∈E

Minimum Vertex Cover (MVC):

Given a graph GGG, find a subset of nodes S⊆VS\subseteq VS⊆V, s.t. every edge is covered.

  • (u,v)∈E⇔u∈S or v∈S(u,v)\in E \Leftrightarrow u\in S \text{ or } v\in S(u,v)∈E⇔u∈S or v∈S

  • ∣S∣|S|∣S∣ is minimized

Maximum Cut (MAXCUT):

Given a graph GGG, find a subset of nodes S⊆VS\subseteq VS⊆V, s.t. the weight of cut-set ∑(u,v)∈Cw(u,v)\sum_{(u,v)\in C}w(u,v)∑(u,v)∈C​w(u,v) is maximized.

cut-set: CCC, the set of edges with one end in SSS and the other end in V\SV \backslash SV\S

Traveling Salesman Problem (TSP)

Overview

basic idea

  1. original graph with initial state

  2. input the graph to an embedding model (structure2vec) for T steps

  3. each node has a corresponding score based on structure2vec

  4. pick up the node with the highest score (after one iteration)

  5. go back to step 2 and repeat until termination

Relation to Q-learning (taking MVC for example)

Reinforcement Learning

MVC (Minimum Vertex Cover)

score we earned at current step

current screen

current selected nodes

move your board left/right

select a node

Action value function

predicted future total rewards

structure2vec embedding

How to choose the action

How to represent the node embedding:

How to measure the Q-value for each node:

Reference

  • https://arxiv.org/abs/1704.01665

  • https://github.com/Hanjun-Dai/graph_comb_opt

Reward

State

Action

Policy

R(t)R(t)R(t)
rt=−1r^t=-1rt=−1
SSS
iii
Q^(S,i)\hat{Q}(S,i)Q^​(S,i)
π(s)\pi(s)π(s)
i∗=argmax⁡i(Q^(S,i))i^* = \operatorname{argmax}_i(\hat{Q}(S,i))i∗=argmaxi​(Q^​(S,i))
v∗=argmax⁡v(Q^(S,v))v^* = \operatorname{argmax}_v(\hat{Q}(S,v))v∗=argmaxv​(Q^​(S,v))
RL vs MVC