图是互连节点的集合，节点node通过边edge连接，由G=(V, E)表示
Edges can be
directed、weighted
Nodes and edges can havetypesandmetadata
图可用于表示Social networks、Collaboration networks、Transportation networks、Computer networks、Connectomics等
Properties of real-world graphs:big、sparse、degrees can be highly skewed/a power law degree distribution
相关术语
完备
complete图：一个图的所有节点都有n-1个相邻节点，也就是说所有节点都具备所有可能的连接方式
从i到j的路径path是指从i到达j的边的序列，该路径的长度length等于所经过的边的数量
图的直径diameter是指连接任意两个节点的所有最短路径中最长路径的长度 测地路径geodesic path是指两个节点之间的最短路径
如果所有节点都可通过某个路径连接到彼此，则它们构成一个连通分支connected component。如果一个图仅有一个连通分支，则该图是连通的connected
如果一个图的边是有顺序的配对，则该图是有向的directed。i的入度in-degree是指向i的边的数量，出度out-degree是远离i的边的数量
如果可以回到一个给定节点，则该图是有环的cyclic。相对地，如果至少有一个节点无法回到，则该图就是无环的acyclic
图可以被加权weighted，即在节点或关系上施加权重
如果一个图的边数量相比于节点数量较小，则该图是稀疏的sparse。相对地，如果节点之间的边非常多，则该图是密集的dense
Social Network
A social network is a graph made up of: a set of
individuals, called “nodes”, and tied by one or moreinterdependency, such as friendship, called “edges”
Social Network Analysis
- Community Detection
- Influence Maximization
- Link Prediction
- Network Evolution
- Network Embedding
- Deep Learning for Networks
Dynamic Network
networks are dynamic in nature
changes are smooth
edges and nodes arrive over time
确定最优路径
Breadth-First Search(BFS)requires O(n+m) work on n vertices and m edges
Depth-First Search(DFS)requires O(n+m) work on n vertices and m edges
确定网络中节点的重要性
评估群体聚类的方式
edge list存储有边连接的每一对节点的IDadjacency matrix通常是在内存中加载的方式adjacency listcompressed sparse row (CSR)需要两个数组Offsets和Edges
Problem Representation Learning for Networks Graph Representation Learning Network Embedding Graph Embedding
Tasks
- Node classification
- Link prediction
- Community detection
Includings Node Embedding Edge Embedding (sub)Graph Embedding
static graph setting
Goal: encode structural and content information
- shallow embedding
matrix factorization
random walk
- deep embedding
neighborhood autoencoder
neighborhood aggregation
dynamic graph setting
Goal: encode evolving graph information
- 直接添加时序信息
- 先对动态过程建模，再利用模型encode
evolving graph information
- structure
- attribute
- evolution pattern
time
- discrete-time/snapshot
loss of information between snapshots, lack of ability to capture fine-grained temporal dynamics, the selection of appropriate aggregation granularity which is often misspecified
- continuous-time/finer time granularity
2018 WWW Tutorial Representation Learning on Networks William L. Hamilton, Rex Ying and Jure Leskovec
2017 Representation Learning on Graphs: Methods and Applications William L. Hamilton, Rex Ying and Jure Leskovec
2019 WWW Tutorial Representation Learning on Networks: Theories, Algorithms, and Applications Jie Tang and Yuxiao Dong
2019 KDD Workshop Perspectives and Outlook on Network Embedding and GCN Peng Cui
2019 KDD Tutorial Learning From Networks ——Algorithms, Theory, & Applications Peng Cui
2017 A Survey on Network Embedding Peng Cui, Xiao Wang, Jian Pei and Wenwu Zhu
structure-preserving methods and property-preserving methods
2017 Graph Embedding Techniques, Applications, and Performance: A Survey Palash Goyal and Emilio Ferrara
2001 Laplacian eigenmaps and spectral techniques for embedding and clustering Mikhail Belkin and Partha Niyogi
2015 CIKM Grarep: Learning graph representations with global structural information Shaosheng Cao, Wei Lu, and Qiongkai Xu
2014 KDD Deepwalk: online learning of social representations Bryan Perozzi, Rami Alrfou, and Steven Skiena
新节点表示
2015 WWW Line: Large-scale information network embedding Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei
新节点表示
2016 KDD node2vec: Scalable feature learning for networks Aditya Grover and Jure Leskovec
2016 KDD Structural deep network embedding Daixin Wang, Peng Cui and Wenwu Zhu
2016 AAAI Deep neural networks for learning graph representations Shaosheng Cao, Wei Lu and Qiongkai Xu
2014 ICLR Spectral networks and locally connected networks on graphs Joan Bruna, Wojciech Zaremba, Arthur Szlam and Yann LeCun
2015 NIPS Convolutional networks on graphs for learning molecular fingerprints David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael Gomez-Bombarelli, Timothy Hirzel, Alan Aspuru-Guzik and Ryan P. Adams
2016 NIPS Convolutional neural networks on graphs with fast localized spectral filtering Michael Defferrard, Xavier Bresson and Pierre Vandergheynst
2016 ICLR Gated graph sequence neural networks Yujia Li, Daniel Tarlow, Marc Brockschmidt and Richard Zemel
2017 NIPS Inductive representation learning on large graphs William L. Hamilton, Rex Ying and Jure Leskovec
2017 ICML Neural message passing for quantum chemistry Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals and George E. Dahl
2017 ICLR Semi-supervised classification with graph convolutional networks Thomas N. Kipf and Max Welling
GCN
2017 NIPS Predicting organic reaction outcomes with Weisfeiler-Lehman network Wengong Jin, Connor W. Coley, Regina Barzilay and Tommi Jaakkola
2018 ICLR FastGCN: Fast learning with graph convolutional networks via importance sampling Jie Chen, Tengfei Ma and Cao Xiao
2018 ICLR Graph attention networks Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio and Yoshua Bengio
2017 KDD metapath2vec: Scalable representation learning for heterogeneous networks Yuxiao Dong, Nitesh V. Chawla and Ananthram Swami
2018 AAAI Link prediction via subgraph embedding-based convex matrix completion Zhu Cao, Linlin Wang, and Gerard de Melo
2016 TKDE Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg and Aram Galstyan code
BCGD
2017 CIKM Attributed Network Embedding for Learning in a Dynamic Environment Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang and Huan Liu
DANE
2017 ICML Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs Rakshit Trivedi, Hanjun Dai, Yichen Wang and Le Song code
Know-Evolve
2018 WWW Continuous-Time Dynamic Network Embeddings Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh and Sungchul Kim
CTDNE
2018 Streaming Graph Neural Networks Yao Ma, Ziyi Guo, Zhaochun Ren, Eric Zhao, Jiliang Tang and Dawei Yin
DGNN
2018 TKDE High-order Proximity Preserved Embedding For Dynamic Networks Dingyuan Zhu, Peng Cui, Ziwei Zhang, Jian Pei and Wenwu Zhu
DHPE
2018 IJCAI Dynamic Network Embedding :An Extended Approach for Skip-gram based Network Embedding Lun Du, Yun Wang, Guojie Song, Zhicong Lu and Junshan Wang
DNE
2018 AAAI Dynamic Network Embedding by Modeling Triadic Closure Process Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu and Yueting Zhuang code
DynamicTriad
2018 DynGEM: Deep Embedding Method for Dynamic Graphs Palash Goyal, Nitin Kamra, Xinran He and Yan Liu code
DynGEM
2018 dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning Palash Goyal, Sujit Rokka Chhetri and Arquimedes Canedo code
dyngraph2vec
2018 KDD Embedding Temporal Network via Neighborhood Formation Yuan Zuo, Guannan Liu, Hao Lin, Jia Guo, Xiaoqian Hu and Junjie Wu
HTNE
2018 KDD NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen and Wei Wang
NetWalk
2018 AAAI TIMERS: Error-Bounded SVD Restart on Dynamic Networks Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang and Wenwu Zhu code
TIMERS
2019 IJCAI Large Scale Evolving Graphs with Burst Detection Yifeng Zhao, Xiangwei Wang, Hongxia Yang, Le Song and Jie Tang
BurstGraph
2019 ICLR DyRep: Learning Representations over Dynamic Graphs Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal and Hongyuan Zha
DyRep
2016 Structured sequence modeling with graph convolutional recurrent networks Youngjoo Seo, Michael Defferrard, Pierre Vandergheynst and Xavier Bresson
2017 Dynamic graph convolutional networks Franco Manessia, Alessandro Rozza and Mario Manzo
2018 Learning graph dynamics using deep neural networks Apurva Narayan and Peter H. O’N Roe
2019 EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler and Charles E. Leisersen