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. …

- 葉津源 (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 *🇹🇼

- NPO — Combinatorial problem
- Graph with an Adversary
- Surveys of Recommendation System and Streaming Data

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.

**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

**Transition pattern for next…**

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…

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 GNN2. 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)

[In short]

An Adversarial…

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

Learning Category-Specific Mesh Reconstruction from Image Collections

*Pixel2mesh*

*pixel2mesh++*

Learning Efficient Point Cloud Generation for Dense 3D Object Reconstruction

DeepSFM: Structure From Motion Via Deep Bundle Adjustment

Deep Non-Rigid Structure from Motion

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

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

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

Table of ContentWhat is mesh?Popular 3d model dataset collectionsTransformation: sampling point cloud from CAD or mesh

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

back to 《A Deeper Learner》main page

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

back to 《A Deeper Learner》main page

back to 《A Deeper Learner》main page

no time to write will finish latter