送你200+篇论文,学习图或图神经网络必读!(附下载)

2019 年 7 月 23 日 数据派THU
送你200+篇论文,学习图或图神经网络必读!(附下载)

来源:机器之心

本文2300字,建议阅读5分钟

这篇文章将介绍你需要的图建模论文,当然它们都有配套实现的。


图是一种非常神奇的表示方式,生活中绝大多数的现象或情境都能用图来表示,例如人际关系网、道路交通网、信息互联网等等。正如马哲介绍事物具有普遍联系性,而图正好能捕捉这种联系,所以用它来描述这个世界是再好不过的方法。


但图这种结构化数据有个麻烦的地方,我们先要有图才能进行后续的计算。但图的搭建并不简单,目前也没有比较好的自动化方法,所以第一步还是需要挺多功夫的。只要各节点及边都确定了,那么图就是一种非常强大且复杂的工具,模型也能推断出图中的各种隐藏知识。



不同时期的图建模


其实,我们可以将图建模分为图神经网络与传统的图模型。其中以前的图建模主要借助 Graph Embedding 为不同的节点学习低维向量表征,这借鉴了 NLP 中词嵌入的思想。而图神经网络借助深度学习进行更强大的图运算与图表征。


Graph Embedding 算法聚焦在如何对网络节点进行低维向量表示,相似的节点在表征空间中更加接近。相比之下,GNN 最大的优势在于它不只可以对一个节点进行语义表示。


例如 GNN 可以表示子图的语义信息,将网络中一小部分节点构成的语义表示出来,这是以前 Graph Embedding 不容易做到的。GNN 还可以在整个图网络上进行信息传播、聚合等建模,也就是说它可以把图网络当成一个整体进行建模。此外,GNN 对单个节点的表示也可以做得更好,因为它可以更好地建模周围节点丰富信息。


在传统图建模中,随机游走、最短路径等图方法会利用符号知识,但这些方法并没有办法很好地利用每个节点的语义信息。而深度学习技术更擅长处理非结构文本、图像等数据。简言之,我们可以将 GNN 看做将深度学习技术应用到符号表示的图数据上,或者说是从非结构化数据扩展到了结构化数据。GNN 能够充分融合符号表示和低维向量表示,发挥两者优势。


图建模论文与代码


在 GitHub 的一项开源工作中,开发者收集了图建模相关的论文与实现,并且从经典的 Graph Embedding、Graph Kernel 到图神经网络都有涉及。它们在图嵌入、图分类、图表征等领域都是非常重要的论文。


项目地址:

https://github.com/benedekrozemberczki/awesome-graph-classification


该项目主要收集的论文领域如下所示:


  1. Factorization

  2. Spectral and Statistical Fingerprints

  3. Graph Neural Network

  4. Graph Kernels


因式分解法


  • Learning Graph Representation via Frequent Subgraphs (SDM 2018)

    • Dang Nguyen, Wei Luo, Tu Dinh Nguyen, Svetha Venkatesh, Dinh Phung

    • Paper:

      https://epubs.siam.org/doi/10.1137/1.9781611975321.35

    • Python:

      https://github.com/nphdang/GE-FSG

  • Anonymous Walk Embeddings (ICML 2018)

    • Sergey Ivanov and Evgeny Burnaev

    • Paper:

      https://arxiv.org/pdf/1805.11921.pdf

    • Python:

      https://github.com/nd7141/AWE

  • Graph2vec (MLGWorkshop 2017)

    • Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, and Santhoshkumar Saminathan

    • Paper:

      https://arxiv.org/abs/1707.05005

    • Python High Performance:

      https://github.com/benedekrozemberczki/graph2vec

    • Python Reference:

      https://github.com/MLDroid/graph2vec_tf

  • Subgraph2vec (MLGWorkshop 2016)

    • Annamalai Narayanan, Mahinthan Chandramohan, Lihui Chen, Yang Liu, and Santhoshkumar Saminathan

    • Paper:

      https://arxiv.org/abs/1606.08928

    • Python High Performance:

      https://github.com/MLDroid/subgraph2vec_gensim

    • Python Reference:

      https://github.com/MLDroid/subgraph2vec_tf

  • Rdf2Vec: RDF Graph Embeddings for Data Mining (ISWC 2016)

    • Petar Ristoski and Heiko Paulheim

    • Paper:

      https://link.springer.com/chapter/10.1007/978-3-319-46523-4_30

    • Python Reference:

      https://github.com/airobert/RDF2VecAtWebScale

  • Deep Graph Kernels (KDD 2015)

    • Pinar Yanardag and S.V.N. Vishwanathan

    • Paper:

      https://dl.acm.org/citation.cfm?id=2783417

    • Python Reference:

      https://github.com/pankajk/Deep-Graph-Kernels


Spectral and Statistical Fingerprints


  • A Simple Yet Effective Baseline for Non-Attribute Graph Classification (ICLR RLPM 2019)

    • Chen Cai, Yusu Wang

    • Paper:

      https://arxiv.org/abs/1811.03508

    • Python Reference:

      https://github.com/Chen-Cai-OSU/LDP

  • NetLSD (KDD 2018)

    • Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alex Bronstein, and Emmanuel Müller

    • Paper:

      https://arxiv.org/abs/1805.10712

    • Python Reference:

      https://github.com/xgfs/NetLSD

  • A Simple Baseline Algorithm for Graph Classification (Relational Representation Learning, NIPS 2018)

    • Nathan de Lara and Edouard Pineau

    • Paper:

      https://arxiv.org/pdf/1810.09155.pdf

    • Python Reference:

      https://github.com/edouardpineau/A-simple-baseline-algorithm-for-graph-classification

  • Multi-Graph Multi-Label Learning Based on Entropy (Entropy NIPS 2018)

    • Zixuan Zhu and Yuhai Zhao

    • Paper:

      https://github.com/TonyZZX/MultiGraph_MultiLabel_Learning/blob/master/entropy-20-00245.pdf

    • Python Reference:

      https://github.com/TonyZZX/MultiGraph_MultiLabel_Learning

  • Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs (NIPS 2017)

    • Saurabh Verma and Zhi-Li Zhang

    • Paper:

      https://papers.nips.cc/paper/6614-hunt-for-the-unique-stable-sparse-and-fast-feature-learning-on-graphs.pdf

    • Python Reference:

      https://github.com/vermaMachineLearning/FGSD

  • Joint Structure Feature Exploration and Regularization for Multi-Task Graph Classification (TKDE 2015)

    • Shirui Pan, Jia Wu, Xingquan Zhuy, Chengqi Zhang, and Philip S. Yuz

    • Paper:

      https://ieeexplore.ieee.org/document/7302040

    • Java Reference:

      https://github.com/shiruipan/MTG

  • NetSimile: A Scalable Approach to Size-Independent Network Similarity (arXiv 2012)

    • Michele Berlingerio, Danai Koutra, Tina Eliassi-Rad, and Christos Faloutsos

    • Paper:

      https://arxiv.org/abs/1209.2684

    • Python:

      https://github.com/kristyspatel/Netsimile


图神经网络


  • Self-Attention Graph Pooling (ICML 2019)

    • Junhyun Lee, Inyeop Lee, Jaewoo Kang

    • Paper:

      https://arxiv.org/abs/1904.08082

    • Python Reference:

      https://github.com/inyeoplee77/SAGPool

  • Variational Recurrent Neural Networks for Graph Classification (ICLR 2019)

    • Edouard Pineau, Nathan de Lara

    • Paper:

      https://arxiv.org/abs/1902.02721

    • Python Reference:

      https://github.com/edouardpineau/Variational-Recurrent-Neural-Networks-for-Graph-Classification

  • Crystal Graph Neural Networks for Data Mining in Materials Science (Arxiv 2019)

    • Takenori Yamamoto

    • Paper:

      https://storage.googleapis.com/rimcs_cgnn/cgnn_matsci_May_27_2019.pdf

    • Python Reference:

      https://github.com/Tony-Y/cgnn

  • Explainability Techniques for Graph Convolutional Networks (ICML 2019)

    • Federico Baldassarre, Hossein Azizpour

    • Paper:

      https://128.84.21.199/pdf/1905.13686.pdf

    • Python Reference:

      https://github.com/gn-exp/gn-exp

  • Semi-Supervised Graph Classification: A Hierarchical Graph Perspective (WWW 2019)

    • Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, and Junzhou Huang

    • Paper:

      https://arxiv.org/pdf/1904.05003.pdf

    • Python Reference:

      https://github.com/benedekrozemberczki/SEAL-CI

  • Capsule Graph Neural Network (ICLR 2019)

    • Zhang Xinyi and Lihui Chen

    • Paper:

      https://openreview.net/forum?id=Byl8BnRcYm

    • Python Reference:

      https://github.com/benedekrozemberczki/CapsGNN

  • How Powerful are Graph Neural Networks? (ICLR 2019)

    • Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka

    • Paper:

      https://arxiv.org/abs/1810.00826

    • Python Reference:

      https://github.com/weihua916/powerful-gnns

  • Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks (AAAI 2019)

    • Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    • Paper:

      https://arxiv.org/pdf/1810.02244v2.pdf

    • Python Reference:

      https://github.com/k-gnn/k-gnn

  • Capsule Neural Networks for Graph Classification using Explicit Tensorial Graph Representations (Arxiv 2019)

    • Marcelo Daniel Gutierrez Mallea, Peter Meltzer, and Peter J Bentley

    • Paper:

      https://arxiv.org/pdf/1902.08399v1.pdf

    • Python Reference:

      https://github.com/BraintreeLtd/PatchyCapsules

  • Three-Dimensionally Embedded Graph Convolutional Network for Molecule Interpretation (Arxiv 2018)

    • Hyeoncheol Cho and Insung. S. Choi

    • Paper:

      https://arxiv.org/abs/1811.09794

    • Python Reference:

      https://github.com/blackmints/3DGCN

  • Learning Graph-Level Representations with Recurrent Neural Networks (Arxiv 2018)

    • Yu Jin and Joseph F. JaJa

    • Paper:

      https://arxiv.org/pdf/1805.07683v4.pdf

    • Python Reference:

      https://github.com/yuj-umd/graphRNN

  • Graph Capsule Convolutional Neural Networks (ICML 2018)

    • Saurabh Verma and Zhi-Li Zhang

    • Paper:

      https://arxiv.org/abs/1805.08090

    • Python Reference:

      https://github.com/vermaMachineLearning/Graph-Capsule-CNN-Networks

  • Graph Classification Using Structural Attention (KDD 2018)

    • John Boaz Lee, Ryan Rossi, and Xiangnan Kong

    • Paper:

      http://ryanrossi.com/pubs/KDD18-graph-attention-model.pdf

    • Python Pytorch Reference:

      https://github.com/benedekrozemberczki/GAM

  • Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation (NIPS 2018)

    • Jiaxuan You, Bowen Liu, Rex Ying, Vijay Pande, and Jure Leskovec

    • Paper:

      https://arxiv.org/abs/1806.02473

    • Python Reference:

      https://github.com/bowenliu16/rl_graph_generation

  • Hierarchical Graph Representation Learning with Differentiable Pooling (NIPS 2018)

    • Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton and Jure Leskovec

    • Paper:

      http://papers.nips.cc/paper/7729-hierarchical-graph-representation-learning-with-differentiable-pooling.pdf

    • Python Reference:

      https://github.com/rusty1s/pytorch_geometric

  • Contextual Graph Markov Model: A Deep and Generative Approach to Graph Processing (ICML 2018)

    • Davide Bacciu, Federico Errica, and Alessio Micheli

    • Paper:

      https://arxiv.org/pdf/1805.10636.pdf

    • Python Reference:

      https://github.com/diningphil/CGMM

  • MolGAN: An Implicit Generative Model for Small Molecular Graphs (ICML 2018)

    • Nicola De Cao and Thomas Kipf

    • Paper:

      https://arxiv.org/pdf/1805.11973.pdf

    • Python Reference:

      https://github.com/nicola-decao/MolGAN

  • Deeply Learning Molecular Structure-Property Relationships Using Graph Attention Neural Network (2018)

    • Seongok Ryu, Jaechang Lim, and Woo Youn Kim

    • Paper:

      https://arxiv.org/abs/1805.10988

    • Python Reference:

      https://github.com/SeongokRyu/Molecular-GAT

  • Compound-protein Interaction Prediction with End-to-end Learning of Neural Networks for Graphs and Sequences (Bioinformatics 2018)

    • Masashi Tsubaki, Kentaro Tomii, and Jun Sese

    • Paper:

      https://academic.oup.com/bioinformatics/article/35/2/309/5050020

    • Python Reference:

      https://github.com/masashitsubaki/CPI_prediction

    • Python Reference:

      https://github.com/masashitsubaki/GNN_molecules

    • Python Alternative:

      https://github.com/xnuohz/GCNDTI

  • Learning Graph Distances with Message Passing Neural Networks (ICPR 2018)

    • Pau Riba, Andreas Fischer, Josep Llados, and Alicia Fornes

    • Paper:

      https://ieeexplore.ieee.org/abstract/document/8545310

    • Python Reference:

      https://github.com/priba/siamese_ged

  • Edge Attention-based Multi-Relational Graph Convolutional Networks (2018)

    • Chao Shang, Qinqing Liu, Ko-Shin Chen, Jiangwen Sun, Jin Lu, Jinfeng Yi and Jinbo Bi

    • Paper:

      https://arxiv.org/abs/1802.04944v1

    • Python Reference:

      https://github.com/Luckick/EAGCN

  • Commonsense Knowledge Aware Conversation Generation with Graph Attention (IJCAI-ECAI 2018)

    • Hao Zhou, Tom Yang, Minlie Huang, Haizhou Zhao, Jingfang Xu and Xiaoyan Zhu

    • Paper:

      http://coai.cs.tsinghua.edu.cn/hml/media/files/2018_commonsense_ZhouHao_3_TYVQ7Iq.pdf

    • Python Reference:

      https://github.com/tuxchow/ccm

  • Residual Gated Graph ConvNets (ICLR 2018)

    • Xavier Bresson and Thomas Laurent

    • Paper:

      https://arxiv.org/pdf/1711.07553v2.pdf

    • Python Pytorch Reference:

      https://github.com/xbresson/spatial_graph_convnets

  • An End-to-End Deep Learning Architecture for Graph Classification (AAAI 2018)

    • Muhan Zhang, Zhicheng Cui, Marion Neumann and Yixin Chen

    • Paper:

      https://www.cse.wustl.edu/~muhan/papers/AAAI_2018_DGCNN.pdf

    • Python Tensorflow Reference:

      https://github.com/muhanzhang/DGCNN

    • Python Pytorch Reference:

      https://github.com/muhanzhang/pytorch_DGCNN

    • MATLAB Reference:

      https://github.com/muhanzhang/DGCNN

    • Python Alternative:

      https://github.com/leftthomas/DGCNN

    • Python Alternative:

      https://github.com/hitlic/DGCNN-tensorflow

  • SGR: Self-Supervised Spectral Graph Representation Learning (KDD DLDay 2018)

    • Anton Tsitsulin, Davide Mottin, Panagiotis Karra, Alex Bronstein and Emmanueal Müller

    • Paper:

      https://arxiv.org/abs/1807.02839

    • Python Reference:

      http://mott.in/publications/others/sgr/

  • Deep Learning with Topological Signatures (NIPS 2017)

    • Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl

    • paper:

      https://arxiv.org/abs/1707.04041

    • Python Reference:

      https://github.com/c-hofer/nips2017

  • Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs (CVPR 2017)

    • Martin Simonovsky and Nikos Komodakis

    • paper:

      https://arxiv.org/pdf/1704.02901v3.pdf

    • Python Reference:

      https://github.com/mys007/ecc

  • Deriving Neural Architectures from Sequence and Graph Kernels (ICML 2017)

    • Tao Lei, Wengong Jin, Regina Barzilay, and Tommi Jaakkola

    • Paper:

      https://arxiv.org/abs/1705.09037

    • Python Reference:

      https://github.com/taolei87/icml17_knn

  • Protein Interface Prediction using Graph Convolutional Networks (NIPS 2017)

    • Alex Fout, Jonathon Byrd, Basir Shariat and Asa Ben-Hur

    • Paper:

      https://papers.nips.cc/paper/7231-protein-interface-prediction-using-graph-convolutional-networks

    • Python Reference:

      https://github.com/fouticus/pipgcn

  • Graph Classification with 2D Convolutional Neural Networks (2017)

    • Antoine J.-P. Tixier, Giannis Nikolentzos, Polykarpos Meladianos and Michalis Vazirgiannis

    • Paper:

      https://arxiv.org/abs/1708.02218

    • Python Reference:

      https://github.com/Tixierae/graph_2D_CNN

  • CayleyNets: Graph Convolutional Neural Networks with Complex Rational Spectral Filters (IEEE TSP 2017)

    • Ron Levie, Federico Monti, Xavier Bresson, Michael M. Bronstein

    • Paper:

      https://arxiv.org/pdf/1705.07664v2.pdf

    • Python Reference:

      https://github.com/fmonti/CayleyNet

  • Semi-supervised Learning of Hierarchical Representations of Molecules Using Neural Message Passing (2017)

    • Hai Nguyen, Shin-ichi Maeda, Kenta Oono

    • Paper:

      https://arxiv.org/pdf/1711.10168.pdf

    • Python Reference:

      https://github.com/pfnet-research/hierarchical-molecular-learning

  • Kernel Graph Convolutional Neural Networks (2017)

    • Giannis Nikolentzos, Polykarpos Meladianos, Antoine Jean-Pierre Tixier, Konstantinos Skianis, Michalis Vazirgiannis

    • Paper:

      https://arxiv.org/pdf/1710.10689.pdf

    • Python Reference:

      https://github.com/giannisnik/cnn-graph-classification

  • Deep Topology Classification: A New Approach For Massive Graph Classification (IEEE Big Data 2016)

    • Stephen Bonner, John Brennan, Georgios Theodoropoulos, Ibad Kureshi, Andrew Stephen McGough

    • Paper:

      https://ieeexplore.ieee.org/document/7840988/

    • Python Reference:

      https://github.com/sbonner0/DeepTopologyClassification

  • Learning Convolutional Neural Networks for Graphs (ICML 2016)

    • Mathias Niepert, Mohamed Ahmed, Konstantin Kutzkov

    • Paper:

      https://arxiv.org/abs/1605.05273

    • Python Reference:

      https://github.com/tvayer/PSCN

  • Gated Graph Sequence Neural Networks (ICLR 2016)

    • Yujia Li, Daniel Tarlow, Marc Brockschmidt, Richard Zemel

    • Paper:

      https://arxiv.org/abs/1511.05493

    • Python TensorFlow:

      https://github.com/bdqnghi/ggnn.tensorflow

    • Python PyTorch:

      https://github.com/JamesChuanggg/ggnn.pytorch

    • Python Reference:

      https://github.com/YunjaeChoi/ggnnmols

  • Convolutional Networks on Graphs for Learning Molecular Fingerprints (NIPS 2015)

    • David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguirre, Rafael Gómez-Bombarelli, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams

    • Paper:

      https://papers.nips.cc/paper/5954-convolutional-networks-on-graphs-for-learning-molecular-fingerprints.pdf

    • Python Reference:

      https://github.com/fllinares/neural_fingerprints_tf

    • Python Reference:

      https://github.com/jacklin18/neural-fingerprint-in-GNN

    • Python Reference:

      https://github.com/HIPS/neural-fingerprint

    • Python Reference:

      https://github.com/debbiemarkslab/neural-fingerprint-theano

Graph Kernels


  • Message Passing Graph Kernels (2018)

    • Giannis Nikolentzos, Michalis Vazirgiannis

    • Paper:

      https://arxiv.org/pdf/1808.02510.pdf

    • Python Reference:

      https://github.com/giannisnik/message_passing_graph_kernels

  • Matching Node Embeddings for Graph Similarity (AAAI 2017)

    • Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis

    • Paper:

      https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14494

  • Global Weisfeiler-Lehman Graph Kernels (2017)

    • Christopher Morris, Kristian Kersting and Petra Mutzel

    • Paper:

      https://arxiv.org/pdf/1703.02379.pdf

    • C++ Reference:

      https://github.com/chrsmrrs/glocalwl

  • On Valid Optimal Assignment Kernels and Applications to Graph Classification (2016)

    • Nils Kriege, Pierre-Louis Giscard, Richard Wilson

    • Paper:

      https://arxiv.org/pdf/1606.01141.pdf

    • Java Reference:

      https://github.com/nlskrg/optimal_assignment_kernels

  • Efficient Comparison of Massive Graphs Through The Use Of ‘Graph Fingerprints’ (MLGWorkshop 2016)

    • Stephen Bonner, John Brennan, and A. Stephen McGough

    • Paper:

      http://dro.dur.ac.uk/19773/1/19773.pdf?DDD10+lzdh59+d700tmt

    • python Reference:

      https://github.com/sbonner0/GraphFingerprintComparison

  • The Multiscale Laplacian Graph Kernel (NIPS 2016)

    • Risi Kondor and Horace Pan

    • Paper:

      https://arxiv.org/abs/1603.06186

    • C++ Reference:

      https://github.com/horacepan/MLGkernel

  • Faster Kernels for Graphs with Continuous Attributes (ICDM 2016)

    • Christopher Morris, Nils M. Kriege, Kristian Kersting and Petra Mutzel

    • Paper:

      https://arxiv.org/abs/1610.00064

    • Python Reference:

      https://github.com/chrsmrrs/hashgraphkernel

  • Propagation Kernels: Efficient Graph Kernels From Propagated Information (Machine Learning 2016)

    • Neumann, Marion and Garnett, Roman and Bauckhage, Christian and Kersting, Kristian

    • Paper:

      https://link.springer.com/article/10.1007/s10994-015-5517-9

    • Matlab Reference:

      https://github.com/marionmari/propagation_kernels

  • Halting Random Walk Kernels (NIPS 2015)

    • Mahito Sugiyama and Karsten M. Borgward

    • Paper:

      https://pdfs.semanticscholar.org/79ba/8bcfbf9496834fdc22a1f7c96d26d776cd6c.pdf

    • C++ Reference:

      https://github.com/BorgwardtLab/graph-kernels

  • Scalable Kernels for Graphs with Continuous Attributes (NIPS 2013)

    • Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne and Karsten Borgwardt

    • Paper:

      https://papers.nips.cc/paper/5155-scalable-kernels-for-graphs-with-continuous-attributes.pdf

  • Subgraph Matching Kernels for Attributed Graphs (ICML 2012)

    • Nils Kriege and Petra Mutzel

    • Paper:

      https://arxiv.org/abs/1206.6483

    • Python Reference:

      https://github.com/mockingbird2/GraphKernelBenchmark

  • Nested Subtree Hash Kernels for Large-Scale Graph Classification over Streams (ICDM 2012)

    • Bin Li, Xingquan Zhu, Lianhua Chi, Chengqi Zhang

    • Paper:

      https://ieeexplore.ieee.org/document/6413884/

    • Python Reference:

      https://github.com/benedekrozemberczki/NestedSubtreeHash

  • Weisfeiler-Lehman Graph Kernels (JMLR 2011)

    • Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt

    • Paper:

      http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf

    • Python Reference:

      https://github.com/jajupmochi/py-graph

    • Python Reference:

      https://github.com/deeplego/wl-graph-kernels

    • C++ Reference:

      https://github.com/BorgwardtLab/graph-kernels

  • Fast Neighborhood Subgraph Pairwise Distance Kernel (ICML 2010)

    • Fabrizio Costa and Kurt De Grave

    • Paper:

      https://icml.cc/Conferences/2010/papers/347.pdf

    • C++ Reference:

      https://github.com/benedekrozemberczki/awesome-graph-classification/blob/master/www.bioinf.uni-freiburg.de/~costa/EDeNcpp.tgz

    • Python Reference:

      https://github.com/fabriziocosta/EDeN

  • A Linear-time Graph Kernel (ICDM 2009)

    • Shohei Hido and Hisashi Kashima

    • Paper:

      https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5360243

    • Python Reference:

      https://github.com/hgascon/adagio

  • Weisfeiler-Lehman Subtree Kernels (NIPS 2009)

    • Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt

    • Paper:

      http://papers.nips.cc/paper/3813-fast-subtree-kernels-on-graphs.pdf

    • Python Reference:

      https://github.com/jajupmochi/py-graph

    • Python Reference:

      https://github.com/deeplego/wl-graph-kernels

    • C++ Reference:

      https://github.com/BorgwardtLab/graph-kernels

  • Fast Computation of Graph Kernels (NIPS 2006)

    • S. V. N. Vishwanathan, Karsten M. Borgwardt, and Nicol N. Schraudolph

    • Paper:

      http://www.dbs.ifi.lmu.de/Publikationen/Papers/VisBorSch06.pdf

    • Python Reference:

      https://github.com/jajupmochi/py-graph

    • C++ Reference:

      https://github.com/BorgwardtLab/graph-kernels

  • Shortest-Path Kernels on Graphs (ICDM 2005)

    • Karsten M. Borgwardt and Hans-Peter Kriegel

    • Paper:

      https://www.ethz.ch/content/dam/ethz/special-interest/bsse/borgwardt-lab/documents/papers/BorKri05.pdf

    • C++ Reference:

      https://github.com/KitwareMedical/ITKTubeTK

  • Cyclic Pattern Kernels For Predictive Graph Mining (KDD 2004)

    • Tamás Horváth, Thomas Gärtner, and Stefan Wrobel

    • Paper:

      http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.332.6158&rep=rep1&type=pdf

    • Python Reference:

      https://github.com/jajupmochi/py-graph

  • Extensions of Marginalized Graph Kernels (ICML 2004)

    • Pierre Mahe, Nobuhisa Ueda, Tatsuya Akutsu, Jean-Luc Perret, and Jean-Philippe Vert

    • Paper:

      http://members.cbio.mines-paristech.fr/~jvert/publi/04icml/icmlMod.pdf

    • Python Reference:

      https://github.com/jajupmochi/py-graph

  • Marginalized Kernels Between Labeled Graphs (ICML 2003)

    • Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi

    • Paper:

      https://pdfs.semanticscholar.org/2dfd/92c808487049ab4c9b45db77e9055b9da5a2.pdf

    • Python Reference:

      https://github.com/jajupmochi/py-graph


      编辑:于腾凯

      校对:林亦霖


登录查看更多
14

相关内容

图神经网络 (GNN) 是一种连接模型,它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是,图神经网络保留了一种状态,可以表示来自其邻域的具有任意深度的信息。近年来,图神经网络(GNN)在社交网络、知识图、推荐系统、问答系统甚至生命科学等各个领域得到了越来越广泛的应用。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等

【导读】以图神经网络为代表的图机器学习在近两年成为研究热点之一。近日,图机器学习专家 Sergei Ivanov 为我们解读了他总结出来的 2020 年图机器学习的四大热门趋势,包括

Sergei Ivanov在这个领域已经工作了几年,很高兴看到这个领域发展很快,经常有非常有趣的想法出现。在这篇综述中,我分析了提交给ICLR 2020的150篇论文,ICLR 2020是机器学习的主要会议之一。我读了大部分的论文,试图了解什么会对这一领域的发展产生重大影响。趋势列表是我自己的,但是我很想知道你是否知道我最近错过的有趣的论文,所以请在下面评论。

2020年才刚刚开始,我们已经可以在最新的研究论文中看到图机器学习(GML)的发展趋势。以下是我对2020年GML的重要内容的看法以及对这些论文的讨论。

概述

本文写作目的并非介绍图机器学习的基本概念,如图神经网络(Graph Neural Network,GNN),而是揭示我们可以在顶级学术会议上看到的前沿研究。首先,我把在图机器学习的研究成果的论文提交到 ICLR 2020阐述了GNN的论文情况

49篇ICLR2020高分「图机器学习GML」接受论文及代码

有 150 篇论文涉及图机器学习,其中三分之一的论文已被接受。这大约相当于所有被接受论文的 10%。

在阅读了大部分关于图机器学习的论文之后,我整理出了 2020 年图机器学习的趋势,如下所列:

    1. 对图神经网络将有更深入的理论理解;
    1. 图神经网络将会有更酷的应用;
    1. 知识图谱将会变得更为流行;
    1. 新的图嵌入框架将出现。

让我们来看看这些趋势。

1. 图神经网络的理论理解

从目前发展趋势看,图机器学习的领域在进展迅速,但是图神经网络还有很多工作要做。但关于图神经网络的工作原理,已经有了一些重要的研究结果! 洛桑联邦理工学院 Andreas Loukas 的这篇论文《What graph neural networks cannot learn: depth vs width》,无论在影响力、简洁性还是对理论理解的深度上,无疑是论文中的代表作。

论文表明,如果我们希望图神经网络能够计算一个流行的图问题(如循环检测、直径估计、顶点覆盖等等),那么节点嵌入的维数(网络宽度 w)乘以层数(网络深度 d) 应与图 n 的大小成正比,即 dw=O(n)。 但现实是当前的GNN的许多实现都无法达到此条件,因为层数和嵌入的尺寸与图的大小相比还不够大。另一方面,较大的网络在实际操作中不合适的,这会引发有关如何设计有效的GNN的问题,当然这个问题也是研究人员未来工作的重点。需要说明的是,这篇论文还从80年代的分布式计算模型中汲取了灵感,证明了GNN本质上是在做同样的事情。

与此类似,Oono 与 Suzuki、Barcelo 等人的另外两篇论文也研究了图神经网络的威力。在第一篇论文《图神经网络在节点分类的表达能力呈指数级下降》(Graph Neual Networks Exponentially Lose Expressive Power for Node Classification)中,论文指出:

在一定的权重条件下,当层数增加时,GCN 只能学习节点度和连通分量(由拉普拉斯谱(the spectra of the Laplacian)确定),除此之外什么也学不到。

这个结果推广了马尔科夫过程(Markov Processes)收敛到唯一平衡点的著名性质,其中收敛速度由转移矩阵的特征值决定。

在第二篇论文《图神经网络的逻辑表达》(The Logical Expressiveness of Graph Neural Network)中,作者展示了图神经网络和它们可以捕获的节点分类器类型之间的联系。我们已经知道,一些图神经网络和图同构的威斯费勒 - 莱曼(Weisfeiler-Leman,WL)算法一样强大,也就是说,当且仅当两个节点被图神经网络分类为相同时,威斯费勒 - 莱曼算法才会将它们着色为相同的颜色。但是,图神经网络可以捕获其他分类函数吗?例如,假设一个布尔函数,当且仅当一个图有一个孤立的顶点时,该函数才会将 ture 赋值给所有的节点。图神经网络能捕捉到这一逻辑吗?从直观上来看是不能,因为图神经网络是一种消息传递机制,如果图的一部分和另一部分(两个连接的组件)之间没有链接,那么这两者之间将不会传递消息。因此,一个建议的简单解决方案是在邻域聚合之后添加一个读出操作,这样当每个节点更新所有特性时,它就拥有了关于图中所有其他节点的信息。

理论方面的其他工作包括 Hou 等人的图神经网络测量图信息的使用,以及 Srinivasan 与 Ribeiro 提出的基于角色和基于距离的节点嵌入的等价性。

2. 图神经网络的更多应用

在过去的一年中,GNN已经在一些实际任务中进行了应用。包括修复 JavaScript 中的 Bug、玩游戏、回答类似 IQ 的测试、优化 TensorFlow 计算图、分子生成以及对话系统中的问题生成。

在论文中,作者其提出了一种在Javascript代码中同时检测和修复错误的方法(HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS)。具体操作是将代码转换为抽象语法树,然后让GNN进行预处理以便获得代码嵌入,再通过多轮图形编辑运算符(添加或删除节点,替换节点值或类型)对其进行修改。为了理解图形的哪些节点应该修改,论文作者使用了一个指针网络(Pointer network),该网络采用了图形嵌入来选择节点,以便使用LSTM网络进行修复。当然,LSTM网络也接受图形嵌入和上下文编辑。 类似的应用还体现在上面这篇论文中《LambdaNet: Probabilistic Type Inference using Graph Neural Networks》。来自得克萨斯大学奥斯汀分校的作者研究了如何推断像Python或TypeScript此类语言的变量类型。更为具体的,作者给出了一个类型依赖超图(type dependency hypergraph),包含了程序作为节点的变量以及它们之间的关系,如逻辑关系、上下文约束等;然后训练一个GNN模型来为图和可能的类型变量产生嵌入,并结合似然率进行预测。 在智商测试类的应用中,上面这篇论文《Abstract Diagrammatic Reasoning with Multiplex Graph Networks》展示了GNN如何进行IQ类测试,例如瑞文测验(RPM)和图三段论(DS)。具体的在RPM任务中,矩阵的每一行组成一个图形,通过前馈模型为其获取边缘嵌入,然后进行图形汇总。由于最后一行有8个可能的答案,因此将创建8个不同的图,并将每个图与前两行连接起来,以通过ResNet模型预测IQ得分。如下图所示:

DeepMind 的一篇论文《用于优化计算图的增强遗传算法学习》(Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs)提出了 一种强化学习算法,可以优化 TensorFlow 计算图的成本。这些图是通过标准的消息传递图神经网络来处理的,图神经网络生成与图中每个节点的调度优先级相对应的离散化嵌入。这些嵌入被输入到一个遗传算法 BRKGA 中,该算法决定每个节点的设备放置和调度。通过对该模型进行训练,优化得到的 TensorFlow 图的实际计算成本。

类似的炫酷应用还有Chence Shi的分子结构生成《Graph Convolutional Reinforcement Learning》和Jiechuan Jiang玩游戏以及Yu Chen的玩游戏等等《Reinforcement Learning Based Graph-to-Sequence Model for Natural Question Generation》。

3. 知识图谱将会变得更为流行

在ICLR2020会议上,有很多关于知识图谱推理的论文。从本质上讲,知识图谱是一种表示事实的结构化方法。与一般的图不同,知识图谱中的节点和边实际上具有某种意义,例如,演员的名字或在电影中的表演(见下图)。知识图谱的一个常见问题是回答一些复杂的查询,例如“在 2000 年前,Steven Spielberg 的哪些电影获得了奥斯卡奖?”可以将其转换成逻辑查询 ∨ {Win(Oscar, V) ∧ Directed(Spielberg, V) ∧ ProducedBefore(2000, V) }。

知识图谱例子

在 斯坦福大学Ren 等人的论文《Query2box:基于框嵌入的向量空间中知识图谱的推理》(Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings)中,作者建议 将查询嵌入到潜在空间中作为矩形框形式,而不是作为单点形式。这种方法允许执行自然的相交操作,即合取 ∧,因为它会产生新的矩形框。但是,对联合(即析取 ∨)进行建模并不是那么简单,因为它可能会导致不重叠的区域。此外,为了精确建模任何带有嵌入的查询,用 VC 维(Vapnik-Chervonenkis Dimension)度量的嵌入之间的距离函数的复杂度应与图中实体的数量成正比。取而代之的一个很好的技巧是,将一个析取式查询替换为 DNF 形式,其中只有在计算图的末尾才会出现联合,这可以有效地减少对每个子查询的简单举例计算。

Query2Box 推理框架

在类似的主题中,Wang 等人在题为《知识图谱中数字规则的可微学习》(Differentiable Learning of Numerical Rules in Knowledge Graphs)中,提出了一种使用处理数值实体和规则的方法。例如,对于引用知识图谱,可以有一个规则 influences(Y,X) ← colleagueOf(Z,Y) ∧ supervisorOf(Z,X) ∧ hasCitation>(Y,Z),它指出,学生 X 通常会受到他们的导师 Z 的同事 Y 的影响,后者被引用的次数更多。这个规则右边的每个关系都可以表示为一个矩阵,寻找缺失链接的过程可以通过实体向量的连续矩阵乘法,这一过程称为规则学习(Rule Learning)。由于矩阵的构造方式,神经方法只能在诸如 colleagueOf(z,y) 这样的分类规则下工作。该论文作者的贡献在于,他们提出了一种新颖的方法,通过显示实际上无需显式地物化这样的矩阵,显著地减少了运行时间,从而有效地利用 hasCitation(y,z) 和否定运算符等数值规则。

引用知识图谱(Citation KG)示例

在今年的图神经网络(或者说机器学习)中经常出现的一个研究方向是:对现有模型的重新评估,以及在一个公平环境中进行测评。

上面这篇文章即是其中一个,他们的研究表明,新模型的性能往往取决于试验训练中的“次要”细节,例如损失函数的形式、正则器、采样的方案等。在他们进行的大型消融研究中,作者观察到将旧的方法(例如RESCAL模型)的超参数进行适当调整就可以获得SOTA性能。

当然在这个领域还有许多其他有趣的工作,Allen et al. 基于对词嵌入的最新研究,进一步探究了关系与实体的学习表示的隐空间。Asai et al. 则展示了模型如何在回答给定query的Wikipedia图谱上检索推理路径。Tabacof 和 Costabello 讨论了图嵌入模型的概率标定中的一个重要问题,他们指出,目前流行的嵌入模型TransE 和ComplEx(通过将logit函数转换成sigmoid函数来获得概率)均存在误校,即对事实的存在预测不足或预测过度。

4. 新的图嵌入框架将出现

图嵌入是图机器学习的一个长期的研究主题,今年有一些关于我们应该如何学习图表示的新观点出现。

康奈尔的Chenhui Deng等人的《GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》提出了一种改善运行时间和准确率的方法,可以应用到任何无监督嵌入方法的节点分类问题。

这篇文章的总体思路是,首先将原始图简化为更小的图,这样可以快速计算节点嵌入,然后再回复原始图的嵌入。

最初,根据属性相似度,对原始图进行额外的边扩充,这些便对应于节点的k近邻之间的链接。随后对图进行粗化:通过局部谱方法将每个节点投影到低维空间中,并聚合成簇。任何无监督的图嵌入方法(例如DeepWalk、Deep Graph Infomax)都可以在小图上获得节点嵌入。在最后一步,得到的节点嵌入(本质上表示簇的嵌入)用平滑操作符迭代地进行广播,从而防止不同节点具有相同的嵌入。在实验中,GraphZoom框架相比node2vec和DeepWalk,实现了惊人的 40 倍的加速,准确率也提高了 10%。 已有多篇论文对图分类问题的研究成果进行了详细的分析。比萨大学的Federico Errica 等人提出《A Fair Comparison of Graph Neural Networks for Graph Classification 》在图分类问题上,对GNN模型进行了重新评估。

他们的研究表明,一个不利用图的拓扑结构(仅适用聚合节点特征)的简单基线能获得与SOTA GNN差不多的性能。事实上,这个让人惊讶的发现,Orlova等人在2015年就已经发表了,但没有引起大家的广泛关注。 Skolkovo 科学技术研究院的Ivanov Sergey等人在《Understanding Isomorphism Bias in Graph Data Sets》研究中发现,在MUTAG和IMDB等常用数据集中,即使考虑节点属性,很多图也都会具有同构副本。而且,在这些同构图中,很多都有不同的target标签,这自然会给分类器引入标签噪声。这表明,利用网络中所有可用的元信息(如节点或边属性)来提高模型性能是非常重要的。 另外还有一项工作是UCLA孙怡舟团队的工作《Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification 》。这项工作显示如果用一个线性近邻聚合函数取代原有的非线性近邻聚合函数,模型的性能并不会下降。这与之前大家普遍认为“图数据集对分类的影响并不大”的观点是相反的。同时这项工作也引发一个问题,即如何为此类任务找到一个合适的验证框架。

结论

随着顶会的论文提交量的增长,我们可以预计,2020 年图机器学习领域将会涌现许多有趣的成果。我们已经目睹这一领域的转变,从图的深度学习的启发式应用,到更合理的方法和关于图波形范围的基本问题。图神经网络找到了它的位置,作为一个有效的解决许多实际问题的方法,这些问题可以用图来表达,但我认为,总体而言,图机器学习只不过是触及了我们可以实现的图论和机器学习的交叉点上所能取得的成果的皮毛,我们应该继续关注即将到来的结果。

参考链接:

  1. https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3

  2. AI前线:2020 年图机器学习的热门趋势

    https://mp.weixin.qq.com/s/3hXVJS5uLi0UV_cwvEwbHg

  3. AI科技评论 火爆的图机器学习,2020年将有哪些研究趋势?

    https://mp.weixin.qq.com/s/BYkMRZUOcHfIpVE291QZTQ

成为VIP会员查看完整内容
0
124

介绍

图(graphs)与我们的日常生活紧密相关,从我们的社交网络到最近十分流行的知识图谱(KG)都充斥着图的身影。图是最富表现力的数据结构之一,已被用于建模各种问题。事实上,知识图谱(KG)就是图的结构化表示,其中节点表示实体,边表示实体之间的关系。然而,卷积神经网络(CNN)和递归神经网络(RNN)这些传统的神经网络只适合处理欧几里得数据。面对这种困境,图卷积网络(GCN)顺势而生,被用来解决上面提到的问题并且已经成功的应用到了一些问题上。

作者对GCN的研究

(1)NeuralDater模型,一种基于图卷积网络(GCN)的文献年代测定方法。这是GCN和基于深度神经网络的方法首次应用于文档年代测定问题。

(2)SynGCN模型,该方法是一种灵活的基于图卷积的词嵌入学习方法,该方法利用词对上下文的依赖性而不是线性上下文来学习更加有意义的词嵌入表示。

目前GCN方法的局限性

(1)当前标准的邻域聚合方法对节点数量没有限制,但是过多的节点数量会影响目标节点的表示,这使得几跳(few hops)之后,hub-nodes的词表示就会覆盖几乎覆盖整张图,进而导致hub-nodes的词表示包含了大量的噪声。为解决这个问题,作者相应的提出了ConfGCN模型。

(2)目前大多数的GCN方法都只能够处理无向图。然而,现实生活中更为普遍的一种图是关系图,其中每条边都有一个与之关联的标签和方向。目前处理这些图的方法都饱受过量参数的困扰,而且这些方法仅限于学习节点的表示。为了解决这个问题,作者提出了CompGCN 方法。

成为VIP会员查看完整内容
2
65

【导读】CIKM 2019 (International Conference on Information and Knowledge Management),今年会议主题是 "AI for Future Life"。CIKM是数据库、数据挖掘与内容检索领域的旗舰会议。CIKM 2019共计收到1030篇长文有效投稿,其中200篇论文被大会录用,总录用率约19.4%。图神经网络(GNN)相关的论文依然很火爆,小编在官网上查看了,CIKM专门有专题,大约10篇长文接受为GNN专题论文。为此,专知小编提前为大家筛选了六篇GNN 长文论文供参考和学习!

  1. Fi-GNN: Modeling Feature Interactions via Graph Neural Networks for CTR Prediction

作者:Zekun Li,Zeyu Cui,Shu Wu,Xiaoyu Zhang,Liang Wang;

摘要:点击率(CTR)预测是在线广告和推荐系统等网络应用中的一项重要任务,其特点是多领域的。该任务的关键是对不同特征field之间的特征交互进行建模。最近提出的基于深度学习的模型遵循了一种通用的范式:首先将原始的稀疏输入multi-filed特征映射到密集的field嵌入向量中,然后简单地将其连接到深度神经网络(DNN)或其他专门设计的网络中,以学习高阶特征交互。然而,特征field的简单非结构化组合将不可避免地限制以足够灵活和显式的方式建模不同field之间复杂交互的能力。 在这项工作中,我们提出在一个图结构中直观地表示multi-field的特征,其中每个节点对应一个特征field,不同的field可以通过边进行交互。因此,建模特征交互的任务可以转换为对相应图上的节点交互进行建模。为此,我们设计了一个新的模型-Feature Interaction Graph Neural Networks (Fi-GNN)。利用图的强表征性,我们的模型不仅可以灵活、明确地对复杂的特征交互进行建模,而且可以为CTR预测提供良好的模型解释。在两个真实数据集上的实验结果显示了它的优越性。

网址: https://www.zhuanzhi.ai/paper/4d6897c6a057a33539d3e6758c223a9c

2、Graph Convolutional Networks with Motif-based Attention

作者:John Boaz Lee,Ryan A. Rossi,Xiangnan Kong,Sungchul Kim,Eunyee Koh,Anup Rao;

摘要:深度卷积神经网络在计算机视觉和语音识别领域的成功,使得研究人员开始研究该体系结构对图结构数据的泛化。最近提出的一种称为图卷积网络的方法能够在节点分类方面取得最新的成果。然而,由于所提出的方法依赖于spectral图卷积的局部一阶近似,因此无法捕获图中节点间的高阶相互作用。在这项工作中,我们提出了一个motif-based的图注意力模型,称为Motif Convolutional Networks,它通过使用加权多跳motif邻接矩阵来捕获高阶邻域,从而泛华了过去的方法。一个新的注意力机制被用来允许每个单独的节点选择最相关的邻居来应用它的过滤器。我们在不同领域(社会网络和生物信息学)的图上评估了我们的方法,结果表明它能够在半监督节点分类任务上胜过一组有竞争力的基准方法。其他结果证明了attention的有用性,表明不同的节点对不同的高阶邻域进行了优先排序。

网址: https://www.zhuanzhi.ai/paper/ecff4bfc2cc3a0a44307556c0cee2443

  1. Gravity-Inspired Graph Autoencoders for Directed Link Prediction

作者:Guillaume Salha,Stratis Limnios,Romain Hennequin,Viet Anh Tran,Michalis Vazirgian;

摘要:图自编码器(AE)和变分自编码器(VAE)是近年来出现的强有力的节点嵌入方法。特别是利用图AE和VAE成功地解决了具有挑战性的链路预测问题,目的是找出图上的一些节点对是否被未观察到的边所连接。然而,这些模型侧重于无向图,因此忽略了链接的潜在方向,这限制了许多实际应用程序。在本文中,我们扩展了graph AE和VAE框架来解决有向图中的链路预测问题。我们提出了一种新的gravity-inspired的解码器方案,可以有效地从节点嵌入中重建有向图。我们对标准graph AE和VAE表现较差的三种不同定向链路预测任务进行了实证评价。我们在三个真实世界的图上获得了具有竞争力的结果,超过了几个流行的baseline。

网址: https://www.zhuanzhi.ai/paper/7ac17bf2659eff0cfb0458ded56dcbb4

4、Hashing Graph Convolution for Node Classification

作者:Wenting Zhao, Zhen Cui, Chunyan Xu, Chengzheng Li, Tong Zhang,Jian Yang;

摘要:图数据卷积在non-gridded数据中的应用引起了人们的极大兴趣。为了克服相邻节点的排序和数量的影响,在以往的研究中,往往对局部接受域进行summing/average diffusion/aggregation。然而,这种压缩成一个节点的方法容易造成节点间的signal entanglement,导致次优特征信息,降低了节点的可分辨性。针对这一问题,本文提出了一种简单而有效的哈希图卷积(HGC)方法,该方法通过在节点聚合中使用全局哈希和局部投影来进行节点分类。与传统的完全collision聚合相比,hash-projection可以大大降低相邻节点聚合时的collision概率。我们认为基于hash-projection的方法可以更好地保持甚至增加局部区域的原始差异,并得到进一步的改进。hash-projection的另一个附带效果是将每个节点的接受域归一化为一个共同大小的bucket空间,不仅避免了大小不同的邻居节点及其顺序的麻烦,而且使图卷积运行起来就像标准的shape-girded卷积一样。考虑到训练样本较小,我们在HGC中引入预测一致性正则化项来约束图中未标记节点的得分一致性。HGC在transductive和inductive实验环境下进行评估。在节点分类任务上的大量实验表明,hash-projection确实可以提高性能,我们的HGC在所有实验数据集上都取得了最新最好的结果。

网址: https://easychair.org/publications/preprint/lhT3

5、Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach

作者:Changjun Fan,Li Zeng,Yuhui Ding,Muhao Chen,Yizhou Sun,Zhong Liu;

摘要: Betweenness centrality (BC)是网络分析中广泛使用的一种中心性度量,它试图通过最短路径的比例来描述网络中节点的重要性。它是许多有价值的应用的关键,包括社区检测和网络拆除。由于时间复杂度高,在大型网络上计算BC分数在计算上具有挑战性。许多基于采样的近似算法被提出以加速BC的估计。然而,这些方法在大规模网络上仍然需要相当长的运行时间,并且它们的结果对网络的微小扰动都很敏感。 在这篇论文中,我们主要研究如何有效识别图中BC最高的top k节点,这是许多网络应用程序所必须完成的任务。与以往的启发式方法不同,我们将该问题转化为一个学习问题,并设计了一个基于encoder-decoder的框架作为解决方案。具体来说,encoder利用网络结构将每个节点表示为一个嵌入向量,该嵌入向量捕获节点的重要结构信息。decoder将每个嵌入向量转换成一个标量,该标量根据节点的BC来标识节点的相对rank。我们使用pairwise ranking损失来训练模型,以识别节点的BC顺序。通过对小规模网络的训练,该模型能够为较大网络的节点分配相对BC分数,从而识别出高排名的节点。在合成网络和真实世界网络上的实验表明,与现有的baseline相比,我们的模型在没有显著牺牲准确性的情况下大大加快了预测速度,甚至在几个大型真实世界网络的准确性方面超过了最先进的水平。

网址: https://www.zhuanzhi.ai/paper/7bde1414600ac4f4c33493994e3f80fc

6、Relation-Aware Graph Convolutional Networks for Agent-Initiated Social E-Commerce Recommendation

作者:Fengli Xu,Jianxun Lian,Zhenyu Han,Yong Li,Yujian Xu,Xing Xie;

摘要:近年来,agent-initiated社交电子商务模式取得了巨大的成功,这种模式鼓励用户成为销售代理商,通过他们的社交关系来推广商品。这种类型的社交电子商务中的复杂交互可以表述为异构信息网络(HIN),其中三种节点之间的关系有多种类型,分别为用户、销售代理和商品。学习高质量的节点嵌入是研究的重点,图卷积网络(GCNs)是近年来发展起来的最先进的表示学习方法。然而,现有的GCN模型在建模异构关系和有效地从大量邻域中采样相关接收域方面都存在基本的局限性。为了解决这些问题,我们提出了RecoGCN(a RElation-aware CO-attentive GCN model)来有效地聚合HIN中的异构特征。它弥补了目前GCN在使用关系感知聚合器建模异构关系方面的局限性,并利用语义感知元路径为每个节点开辟简洁和相关的接受域。为了有效地融合从不同元路径中学习到的嵌入,我们进一步提出了一种co-attentive机制,通过关注用户、销售代理和商品之间的三种交互来动态地为不同的元路径分配重要性权重。在真实数据集上的大量实验表明,RecoGCN能够学习HIN中有意义的节点嵌入,并且在推荐任务中始终优于baseline方法。

网址: https://www.zhuanzhi.ai/vip/4e1f4ba54086e64b3cb8e47b0c7f9ca3

成为VIP会员查看完整内容
0
31
小贴士
相关论文
Wenwu Zhu,Xin Wang,Peng Cui
19+阅读 · 2020年1月2日
Wenqi Fan,Yao Ma,Qing Li,Yuan He,Eric Zhao,Jiliang Tang,Dawei Yin
14+阅读 · 2019年11月23日
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang,Yuesong Zou,Jian Ma
12+阅读 · 2019年11月6日
Boris Knyazev,Graham W. Taylor,Mohamed R. Amer
3+阅读 · 2019年10月28日
Rik Koncel-Kedziorski,Dhanush Bekal,Yi Luan,Mirella Lapata,Hannaneh Hajishirzi
32+阅读 · 2019年4月4日
Fengwen Chen,Shirui Pan,Jing Jiang,Huan Huo,Guodong Long
14+阅读 · 2019年4月4日
Generative Graph Convolutional Network for Growing Graphs
Da Xu,Chuanwei Ruan,Kamiya Motwani,Evren Korpeoglu,Sushant Kumar,Kannan Achan
3+阅读 · 2019年3月6日
dynnode2vec: Scalable Dynamic Network Embedding
Sedigheh Mahdavi,Shima Khoshraftar,Aijun An
9+阅读 · 2018年12月6日
Joint Embedding of Meta-Path and Meta-Graph for Heterogeneous Information Networks
Lichao Sun,Lifang He,Zhipeng Huang,Bokai Cao,Congying Xia,Xiaokai Wei,Philip S. Yu
4+阅读 · 2018年9月11日
Bryan Perozzi,Rami Al-Rfou,Steven Skiena
7+阅读 · 2014年6月27日
Top