Graph Neural Network solving Non-deterministic Polynomial-time Optimization problems

There have been works on solving combinatorial problems with Graph Neural Networks. In this post, I will go through 3 important papers on this matter.

Table of Contents1. Overview
>>> What is a combinatorial problem?
>>> Why Graph Neural Network?
2. Outline of papers
>>> Approximation Ratios of Graph Neural Networks for Combinatorial Problems, Sato et al., NIPS 2019.
>>> Exact Combinatorial Optimization with Graph Convolutional Neural Networks, Gasse et al., NIPS 2019.
>>> Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP, Prates et al., AAAI 2019. …

Bio and Table of Content

Info monster starring at you
Info monster starring at you
this is an Infomonster


  • 葉津源 (Jimmy Yeh)
  • Currently studying Ph.D. in
    the Graduate Institute of Communication Engineering, National Taiwan University
  • Research focus: Mesh generation, 3D reconstruction, Graph Neural Networks.

This blog is for the AI community, for writing down technical issues with machines, and for Taiwan 🇹🇼

Table of Content

All roads to 3D reconstruction

Graph Neural Network Paper Review


Convex Optimization (know your Gradient Descents!)

How does Graph Neural Network interact with these topics?

Recommender System

Graph Neural Networks in Recommender Systems: A Survey, arxiv 2020

For e-commerce and social media platforms, a recommender system is important. Motivation for GNN on RS: (1) RS data is essentially graphs:
Relevant information includes social relationships, bipartite user-item interaction graphs, item transitions, which can all be represented well as a graph structure. (2) GNN is good on graphs.

General Recommendation

static preference. model user-item compatibility by implicit (click) or explicit (rating)

Can utilize side knowledge:

  • social network → influence modeling (friends); preference integration (user-item; social)
  • knowledge graph → graph simplification (kg too complicate); multi-relation propagation; user integration

Sequential Recommendation

Transition pattern for next…

Given .obj (& .mtl) files, how to render images from different camera angles? With Blender Python API.

The ShapeNet dataset

As documented on their website, ShapeNet is an ongoing collaborative effort between researchers at Princeton, Stanford, and TTIC to establish a richly annotated, large-scale dataset of 3D shapes. Currently, ShapeNetCore is a subset of ShapeNet containing single clean 3D models with manually verified category and alignment annotations are released.

In ShapeNetCore (v2), the directory structure is roughly:
> taxonomy.json: listing the synsetId(s) and the English name(s) of the model-type, as well as the combined number of model instances.

> [synsetId]: synset noun offset for the model type in WordNet v3.0 (v3.1 is available online) as an eight-digit zero-padded string, e.g…

Research on Adversarial Attack against Graph Neural Network.

Deep Learning Networks are prone to be messed with “Adversarial Attacks.” Now this problem has come to haunt Graph Neural Networks. In this post, 2 papers and a tutorial are summarized.

Table of Contents1. Overview
>>> What is an Adversarial Attack
>>> Attack on GNN
2. Outlines
>>> Adversarial Attacks on Neural Networks for Graph Data, Zügner et al., KDD 2018.
>>> Adversarial Examples on Graph Data: Deep Insights into Attack and Defense, Wu et al., IJCAI 2019.
>>> Deep Graph Learning: Foundations, Advances and Applications, Rong et al., KDD 2020 tutorial. (Robustness of GNN)

1. Overview

What is an Adversarial Attack

[In short]
An Adversarial…

what are the baselines?

How to create the 3D mesh?

Deform from sphere or ellipsoid mesh

Learning to Predict 3D Objects with an Interpolation-based Differentiable Renderer

Learning Category-Specific Mesh Reconstruction from Image Collections



Create Point Cloud

Learning Efficient Point Cloud Generation for Dense 3D Object Reconstruction

Deep + structure from motion

DeepSFM: Structure From Motion Via Deep Bundle Adjustment

Deep Non-Rigid Structure from Motion

Deep nrsfm++: Towards 3d reconstruction in the wild

relevant medium post

Unsupervised Deep Persistent Monocular Visual Odometry and Depth Estimation in Extreme Environments

Unsupervised Scale-consistent Depth and Ego-motion Learning from Monocular Video

What happens when we implement the techniques on the Liberty statue? (direct transfer)

How to mesh, this is the question for my deep learning research

A coarse polygonal mesh of a dolphin.
Table of ContentWhat is mesh?Popular 3d model dataset collectionsTransformation: sampling point cloud from CAD or mesh

What is mesh?

Popular 3d model dataset collections

ABC: A Big CAD Model Dataset For Geometric Deep Learning

  • includes STL file, with dense (yet possibly low quality) triangulation.




Transformation: sampling point cloud from CAD or mesh

Convex non-smooth and the convergence of mirror descent with relative smoothness

back to 《A Deeper Learner》main page

Relative smoothness

In the last lecture, we find smoothness required for convergence guarantee. How to generalize smoothness? Ans: Bregman divergence.

Bregman divergence

D_h(y,x)\equiv h(y) — h(x) — \langle\nabla h(x), y-x\rangle
D_h(y,x)\equiv h(y) — h(x) — \langle\nabla h(x), y-x\rangle
The Bregman divergence.

Cauchy’s argument, Smoothness & strong convexity, and the Convergence of gradient descent.

back to 《A Deeper Learner》main page


Definitions, properties, and proofs for convex functions.

back to 《A Deeper Learner》main page

Convex vs Non-convex

Jimmy Yeh

no time to write will finish latter

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store