§ ACKNOWLEDGMENTS

The authors appreciate the fruitful discussions with
Karl Pertsch, Youngwoon Lee, Ayush Jain, and Grace Zhang.
The authors would like to thank Ting-Yu S. Su for contributing to the learned program embedding spaces visualizations.
The authors are grateful to Sidhant Kaushik, Laura Smith, and Siddharth Verma
for offering their time to participate in the human debugging interpretability experiment.

§ FUNDING TRANSPARENCY STATEMENT

This project was partially supported by USC startup funding and by
NAVER AI Lab.

[Mnih et al., 2015]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness,
Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland,
Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis
Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and
Demis Hassabis.
Human level control through deep reinforcement learning.
Nature, 2015a.

[Silver et al., 2016]
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George
Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda
Panneershelvam, Marc Lanctot, et al.
Mastering the game of go with deep neural networks and tree search.
Nature, 2016.

[Silver et al., 2018]
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew
Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore
Graepel, et al.
A general reinforcement learning algorithm that masters chess, shogi,
and go through self-play.
Science, 2018.

[Vinyals et al., 2019]
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu,
Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds,
Petko Georgiev, et al.
Grandmaster level in starcraft ii using multi-agent reinforcement
Nature, 2019.

[Campeau-Lecours et al., 2019]
Alexandre Campeau-Lecours, Hugo Lamontagne, Simon Latour, Philippe Fauteux,
Véronique Maheu, François Boucher, Charles Deguire, and
Louis-Joseph Caron L'Ecuyer.
Kinova modular robot arms for service robotics applications.
In Rapid Automation: Concepts, Methodologies, Tools, and
Applications. 2019.

[Gu et al., 2017]
Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine.
Deep reinforcement learning for robotic manipulation with
asynchronous off-policy updates.
In International Conference on Robotics and Automation, 2017.

[Andrychowicz et al., 2020]
OpenAI: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Jozefowicz, Bob
McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex
Ray, et al.
Learning dexterous in-hand manipulation.
The International Journal of Robotics Research, 2020.

[Hafner et al., 2020]
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi.
Dream to control: Learning behaviors by latent imagination.
In International Conference on Learning Representations, 2020.

[Yamada et al., 2020]
Jun Yamada, Youngwoon Lee, Gautam Salhotra, Karl Pertsch, Max Pflueger,
Gaurav S Sukhatme, Joseph J Lim, and Peter Englert.
Motion planner augmented reinforcement learning for robot
manipulation in obstructed environments.
In Conference on Robot Learning, 2020.

[Zhang et al., 2021]
Grace Zhang, Linghan Zhong, Youngwoon Lee, and Joseph J Lim.
Policy transfer across visual and dynamics domain gaps via iterative
In Robotics: Science and Systems, 2021.

[Lee et al., 2019]
Youngwoon Lee, Edward S Hu, Zhengyu Yang, and Joseph J Lim.
To follow or not to follow: Selective imitation learning from
In Conference on Robot Learning, 2019a.

[Bastani et al., 2018]
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama.
Verifiable reinforcement learning via policy extraction.
In Neural Information Processing Systems, 2018.

[Inala et al., 2020]
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-Lezama.
Synthesizing programmatic policies that inductively generalize.
In International Conference on Learning Representations, 2020.

[Verma et al., 2018]
Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat
Programmatically interpretable reinforcement learning.
In International Conference on Machine Learning, 2018.

[Verma et al., 2019]
Abhinav Verma, Hoang Le, Yisong Yue, and Swarat Chaudhuri.
Imitation-projected programmatic reinforcement learning.
In Neural Information Processing Systems, 2019.

[Devlin et al., 2017]
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman
Mohamed, and Pushmeet Kohli.
Robustfill: Neural program learning under noisy i/o.
In International Conference on Machine Learning,

[Bunel et al., 2018]
Rudy R Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet
Leveraging grammar and reinforcement learning for neural program
In International Conference on Learning Representations, 2018.

[Chen et al., 2019]
Xinyun Chen, Chang Liu, and Dawn Song.
Execution-guided neural program synthesis.
In International Conference on Learning Representations,

[Shin et al., 2018]
Eui Chul Shin, Illia Polosukhin, and Dawn Song.
Improving neural program synthesis with inferred execution traces.
In Neural Information Processing Systems, 2018a.

[Lázaro-Gredilla et al., 2019]
Miguel Lázaro-Gredilla, Dianhuan Lin, J Swaroop Guntupalli, and Dileep
Beyond imitation: Zero-shot task transfer on robots by learning
concepts as cognitive programs.
Science Robotics, 2019.

[Sun et al., 2018]
Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim.
Neural program synthesis from diverse demonstration videos.
In International Conference on Machine Learning, 2018.

[Dang-Nhu, 2020]
Raphaël Dang-Nhu.
Plans: Neuro-symbolic program learning from videos.
In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin,
editors, Neural Information Processing Systems, 2020.

[Pattis, 1981]
Richard E Pattis.
Karel the robot: a gentle introduction to the art of
John Wiley & Sons, Inc., 1981.

[Xu et al., 2018]
Danfei Xu, Suraj Nair, Yuke Zhu, Julian Gao, Animesh Garg, Li Fei-Fei, and
Silvio Savarese.
Neural task programming: Learning to generalize across hierarchical
In International Conference on Robotics and Automation, 2018.

[Devlin et al., 2017]
Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet
Neural program meta-induction.
In Advances in Neural Information Processing Systems,

[Neelakantan et al., 2015]
Arvind Neelakantan, Quoc V Le, and Ilya Sutskever.
Neural programmer: Inducing latent programs with gradient descent.
In International Conference on Learning Representations, 2015.

[Graves et al., 2014]
Alex Graves, Greg Wayne, and Ivo Danihelka.
Neural turing machines.
arXiv preprint arXiv:1410.5401, 2014.

[Kaiser and Sutskever, 2016]
Łukasz Kaiser and Ilya Sutskever.
Neural gpus learn algorithms.
In International Conference on Learning Representations, 2016.

[Gaunt et al., 2017]
Alexander L. Gaunt, Marc Brockschmidt, Nate Kushman, and Daniel Tarlow.
Differentiable programs with neural libraries.
In International Conference on Machine Learning, 2017.

[Reed and De Freitas, 2016]
Scott Reed and Nando De Freitas.
Neural programmer-interpreters.
In International Conference on Learning Representations, 2016.

[Cai et al., 2017]
Jonathon Cai, Richard Shin, and Dawn Song.
Making neural programming architectures generalize via recursion.
In International Conference on Learning Representations, 2017.

[Xiao et al., 2018]
Da Xiao, Jo-Yu Liao, and Xingyuan Yuan.
Improving the universality and learnability of neural
programmer-interpreters with combinator abstraction.
In International Conference on Learning Representations, 2018.

[Burke et al., 2019]
Michael Burke, Svetlin Penkov, and Subramanian Ramamoorthy.
From explanation to synthesis: Compositional program induction for
learning from demonstration.
arXiv preprint arXiv:1902.10657, 2019.

[Yan et al., 2020]
Yujun Yan, Kevin Swersky, Danai Koutra, Parthasarathy Ranganathan, and Milad
Neural execution engines: Learning to execute subroutines.
In Neural Information Processing Systems, 2020.

[Li et al., 2020]
Yujia Li, Felix Gimeno, Pushmeet Kohli, and Oriol Vinyals.
Strong generalization and efficiency in neural programs.
arXiv preprint arXiv:2007.03629, 2020a.

[Huang et al., 2019]
De-An Huang, Suraj Nair, Danfei Xu, Yuke Zhu, Animesh Garg, Li Fei-Fei, Silvio
Savarese, and Juan Carlos Niebles.
Neural task graphs: Generalizing to unseen tasks from a single video
In IEEE Conference on Computer Vision and Pattern Recognition,

[Bošnjak et al., 2017]
Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian
Programming with a differentiable forth interpreter.
In International Conference on Machine Learning, 2017.

[Parisotto et al., 2017]
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong
Zhou, and Pushmeet Kohli.
Neuro-symbolic program synthesis.
In International Conference on Learning Representations, 2017.

[Shin et al., 2018]
Richard Shin, Illia Polosukhin, and Dawn Song.
Improving neural program synthesis with inferred execution traces.
In Neural Information Processing Systems, 2018b.

[Liu et al., 2019]
Yunchao Liu, Jiajun Wu, Zheng Wu, Daniel Ritchie, William T. Freeman, and
Joshua B. Tenenbaum.
Learning to describe scenes with programs.
In International Conference on Learning Representations, 2019.

[Lin et al., 2018]
Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D Ernst.
Nl2bash: A corpus and semantic parser for natural language interface
to the linux operating system.
In International Conference on Language Resources and
Evaluation, 2018.

[Liao et al., 2019]
Yuan-Hong Liao, Xavier Puig, Marko Boben, Antonio Torralba, and Sanja Fidler.
Synthesizing environment-aware activities via activity sketches.
In IEEE Conference on Computer Vision and Pattern Recognition,

[Ellis et al., 2019]
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando
Write, execute, assess: Program synthesis with a repl.
In Neural Information Processing Systems, 2019.

[Ellis et al., 2020]
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas
Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum.
Dreamcoder: Growing generalizable, interpretable knowledge with
wake-sleep bayesian program learning.
arXiv preprint arXiv:2006.08381, 2020.

[Balog et al., 2017]
Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and
Daniel Tarlow.
Deepcoder: Learning to write programs.
In International Conference on Learning Representations, 2017.

[Liskowski et al., 2020]
Paweł Liskowski, Krzysztof Krawiec, Nihat Engin Toklu, and Jerry Swan.
Program synthesis as latent continuous optimization: Evolutionary
search in neural embeddings.
In Genetic and Evolutionary Computation Conference, 2020.

[Abolafia et al., 2018]
Daniel A Abolafia, Mohammad Norouzi, Jonathan Shen, Rui Zhao, and Quoc V Le.
Neural program synthesis with priority queue training.
arXiv preprint arXiv:1801.03526, 2018.

[Hong et al., 2021]
Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer.
Latent programmer: Discrete latent codes for program synthesis.
In International Conference on Machine Learning,

[Silver et al., 2020]
Tom Silver, Kelsey R Allen, Alex K Lew, Leslie Pack Kaelbling, and Josh
Few-shot bayesian imitation learning with logical program policies.
In Association for the Advancement of Artificial Intelligence,

[Wu et al., 2017]
Jiajun Wu, Joshua B Tenenbaum, and Pushmeet Kohli.
Neural scene de-rendering.
In IEEE Conference on Computer Vision and Pattern Recognition,

[Chen et al., 2021]
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan,
Harri Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, et al.
Evaluating large language models trained on code.
arXiv preprint arXiv:2107.03374, 2021a.

[Alet et al., 2021]
Ferran Alet, Javier Lopez-Contreras, James Koppel, Maxwell Nye, Armando
Solar-Lezama, Tomas Lozano-Perez, Leslie Kaelbling, and Joshua Tenenbaum.
A large-scale benchmark for few-shot program induction and synthesis.
In International Conference on Machine Learning, 2021.

[Chen et al., 2021]
Xinyun Chen, Dawn Song, and Yuandong Tian.
Latent execution for neural program synthesis beyond domain-specific
arXiv preprint arXiv:2107.00101, 2021b.

[Austin et al., 2021]
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski,
David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al.
Program synthesis with large language models.
arXiv preprint arXiv:2108.07732, 2021.

[Hong et al., 2021]
Joey Hong, David Dohan, Rishabh Singh, Charles Sutton, and Manzil Zaheer.
Latent programmer: Discrete latent codes for program synthesis.
In International Conference on Machine Learning,

[Wong et al., 2021]
Catherine Wong, Kevin Ellis, Joshua B Tenenbaum, and Jacob Andreas.
Leveraging language to learn program abstractions and search
In International Conference on Machine Learning, 2021.

[Chen et al., 2021]
Xinyun Chen, Petros Maniatis, Rishabh Singh, Charles Sutton, Hanjun Dai, Max
Lin, and Denny Zhou.
Spreadsheetcoder: Formula prediction from semi-structured context.
In International Conference on Machine Learning,

[Nye et al., 2021]
Maxwell Nye, Yewen Pu, Matthew Bowers, Jacob Andreas, Joshua B. Tenenbaum, and
Armando Solar-Lezama.
Representing partial programs with blended abstract semantics.
In International Conference on Learning Representations, 2021.

[Choi and Langley, 2005]
Dongkyu Choi and Pat Langley.
Learning teleoreactive logic programs from problem solving.
In International Conference on Inductive Logic Programming,

[Winner and Veloso, 2003]
Elly Winner and Manuela Veloso.
Distill: Learning domain-specific planners by example.
In International Conference on Machine Learning, 2003.

[Landajuela et al., 2021]
Mikel Landajuela, Brenden K Petersen, Sookyung Kim, Claudio P Santiago, Ruben
Glatt, Nathan Mundhenk, Jacob F Pettit, and Daniel Faissol.
Discovering symbolic policies with deep reinforcement learning.
In International Conference on Machine Learning, 2021.

[Kingma and Welling, 2014]
Diederik P Kingma and Max Welling.
Auto-encoding variational bayes.
In International Conference on Learning Representations, 2014.

[Higgins et al., 2016]
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot,
Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner.
beta-vae: Learning basic visual concepts with a constrained
variational framework.
In International Conference on Learning Representations, 2016.

[Williams, 1992]
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist
reinforcement learning.
Machine learning, 1992.

[Rubinstein, 1997]
Reuven Y Rubinstein.
Optimization of computer simulation models with rare events.
European Journal of Operational Research, 1997.

[Ross et al., 2011]
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell.
A reduction of imitation learning and structured prediction to
no-regret online learning.
In International Conference on Artificial Intelligence and
Statistics, 2011.

[Schulman et al., 2017]
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.
Proximal policy optimization algorithms.
arXiv preprint arXiv:1707.06347, 2017.

[Haarnoja et al., 2018]
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine.
Soft actor-critic: Off-policy maximum entropy deep reinforcement
learning with a stochastic actor.
In International Conference on Machine Learning, 2018.

[Lipton, 2016]
Zachary C Lipton.
The mythos of model interpretability.
In ICML Workshop on Human Interpretability in Machine
Learning, 2016.

[Shen, 2020]
Owen Shen.
Interpretability in ml: A broad overview, 2020.
URL <https://mlu.red/muse/52906366310>.

[Zhang et al., 2020]
Jesse Zhang, Brian Cheung, Chelsea Finn, Sergey Levine, and Dinesh Jayaraman.
Cautious adaptation for reinforcement learning in safety-critical
In International Conference on Machine Learning, 2020.

[Hewing et al., 2019]
Lukas Hewing, Juraj Kabzan, and Melanie N. Zeilinger.
Cautious model predictive control using gaussian process regression.
IEEE Transactions on Control Systems Technology, 2019.

[Fisac et al., 2018]
Jaime F Fisac, Anayo K Akametalu, Melanie N Zeilinger, Shahab Kaynama, Jeremy
Gillula, and Claire J Tomlin.
A general safety framework for learning-based control in uncertain
robotic systems.
IEEE Transactions on Automatic Control, 2018.

[Hakobyan et al., 2019]
A. Hakobyan, G. C. Kim, and I. Yang.
Risk-aware motion planning and control using cvar-constrained
IEEE Robotics and Automation Letters, 2019.

[Sadigh and Kapoor, 2016]
Dorsa Sadigh and Ashish Kapoor.
Safe control under uncertainty with probabilistic signal temporal
In Proceedings of Robotics: Science and Systems, 2016.

[Berkenkamp et al., 2017]
Felix Berkenkamp, Matteo Turchetta, Angela P. Schoellig, and Andreas Krause.
Safe model-based reinforcement learning with stability guarantees.
In Advances in Neural Information Processing Systems, 2017.

[Thananjeyan et al., 2020]
Brijen Thananjeyan, Ashwin Balakrishna, Ugo Rosolia, Felix Li, Rowan
McAllister, Joseph E. Gonzalez, Sergey Levine, Francesco Borrelli, and Ken
Safety augmented value estimation from demonstrations (saved): Safe
deep model-based rl for sparse cost robotic tasks.
IEEE Robotics and Automation Letters, 2020.

[Aswani et al., 2013]
Anil Aswani, Humberto Gonzalez, S Shankar Sastry, and Claire Tomlin.
Provably safe and robust learning-based model predictive control.
Automatica, 2013.

[Andreas et al., 2017]
Jacob Andreas, Dan Klein, and Sergey Levine.
Modular multitask reinforcement learning with policy sketches.
In International Conference on Machine Learning, 2017.

[Oh et al., 2017]
Junhyuk Oh, Satinder Singh, Honglak Lee, and Pushmeet Kohli.
Zero-shot task generalization with multi-task deep reinforcement
In International Conference on Machine Learning, 2017.

[Sun et al., 2020]
Shao-Hua Sun, Te-Lin Wu, and Joseph J. Lim.
Program guided agent.
In International Conference on Learning Representations, 2020.

[Yang et al., 2021]
Yichen Yang, Jeevana Priya Inala, Osbert Bastani, Yewen Pu, Armando
Solar-Lezama, and Martin Rinard.
Program synthesis guided reinforcement learning.
arXiv preprint arXiv:2102.11137, 2021.

[Lee et al., 2019]
Youngwoon Lee, Shao-Hua Sun, Sriram Somasundaram, Edward Hu, and Joseph J. Lim.
Composing complex skills by learning transition policies.
In International Conference on Learning Representations,

[Zhao et al., 2021]
Zelin Zhao, Karan Samel, Binghong Chen, and Le Song.
Proto: Program-guided transformer for program-guided tasks.
arXiv preprint arXiv:2110.00804, 2021.

[Teh et al., 2017]
Yee Whye Teh, Victor Bapst, Wojciech Marian Czarnecki, John Quan, James
Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu.
Distral: Robust multitask reinforcement learning.
arXiv preprint arXiv:1707.04175, 2017.

[Tianmin Shu, 2018]
Richard Socher Tianmin Shu, Caiming Xiong.
Hierarchical and interpretable skill acquisition in multi-task
reinforcement learning.
International Conference on Learning Representations, 2018.

[Sohn et al., 2018]
Sungryull Sohn, Junhyuk Oh, and Honglak Lee.
Hierarchical reinforcement learning for zero-shot generalization with
subtask dependencies.
In Advances in Neural Information Processing Systems, 2018.

[Jain et al., 2020]
Ayush Jain, Andrew Szot, and Joseph Lim.
Generalization to new actions in reinforcement learning.
In Hal Daumé III and Aarti Singh, editors, Proceedings of the
37th International Conference on Machine Learning, volume 119 of
Proceedings of Machine Learning Research, pages 4661–4672. PMLR,
13–18 Jul 2020.
URL <https://proceedings.mlr.press/v119/jain20b.html>.

[Pertsch et al., 2020]
Karl Pertsch, Youngwoon Lee, and Joseph J. Lim.
Accelerating reinforcement learning with learned skill priors.
In Conference on Robot Learning, 2020.

[Snell et al., 2017]
Jake Snell, Kevin Swersky, and Richard Zemel.
Prototypical networks for few-shot learning.
In Advances in Neural Information Processing Systems. 2017.

[Vuorio et al., 2019]
Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim.
Multimodal model-agnostic meta-learning via task-aware modulation.
In Neural Information Processing Systems, 2019.

[Vinyals et al., 2016]
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Daan Wierstra, et al.
Matching networks for one shot learning.
In Advances in Neural Information Processing Systems, 2016.

[Finn et al., 2017]
Chelsea Finn, Pieter Abbeel, and Sergey Levine.
Model-Agnostic Meta-Learning for Fast Adaptation of Deep
In International Conference on Machine Learning, 2017.

[Vuorio et al., 2018]
Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim.
Toward multimodal model-agnostic meta-learning.
arXiv preprint arXiv:1812.07172, 2018.

[Chen et al., 2019]
Wei-Yu Chen, Yen-Cheng Liu, Zsolt Kira, Yu-Chiang Frank Wang, and Jia-Bin
A closer look at few-shot classification.
In International Conference on Learning Representations,

[Lee and Choi, 2018]
Yoonho Lee and Seungjin Choi.
Gradient-Based Meta-Learning with Learned Layerwise
Metric and Subspace.
In International Conference on Machine Learning, 2018.

[Nichol and Schulman, 2018]
Alex Nichol and John Schulman.
Reptile: a scalable metalearning algorithm.
arXiv preprint arXiv:1803.02999, 2018.

[Pruthi et al., 2020]
Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan.
Estimating training data influence by tracing gradient descent.
In Neural Information Processing Systems, 2020.

[Chen et al., 2020]
Yun-Chun Chen, Chao-Te Chou, and Yu-Chiang Frank Wang.
Learning to learn in a semi-supervised fashion.
In European Conference on Computer Vision, 2020.

[Jolliffe, 1986]
I.T. Jolliffe.
Principal Component Analysis.
Springer Verlag, 1986.

[Bakator and Radosav, 2018]
Mihalj Bakator and Dragica Radosav.
Deep learning and medical diagnosis: A review of literature.
Multimodal Technologies and Interaction, 2018.

[Shen et al., 2017]
Dinggang Shen, Guorong Wu, and Heung-Il Suk.
Deep learning in medical image analysis.
Annual review of biomedical engineering, 2017.

[Ghoshal and Tucker, 2020]
Biraja Ghoshal and Allan Tucker.
Estimating uncertainty and interpretability in deep learning for
coronavirus (covid-19) detection.
arXiv preprint arXiv:2003.10769, 2020.

[Chang et al., 2021]
Chia-Jung Chang, Wei Guo, Jie Zhang, Jon Newman, Shao-Hua Sun, and Matt Wilson.
Behavioral clusters revealed by end-to-end decoding from
microendoscopic imaging.
bioRxiv, 2021.

[Singh et al., 2020]
Amitojdeep Singh, Sourya Sengupta, and Vasudevan Lakshminarayanan.
Explainable deep learning models in medical image analysis.
Journal of Imaging, 2020.

[Levenshtein, 1966]
Vladimir Iosifovich Levenshtein.
Binary codes capable of correcting deletions, insertions and
Soviet Physics Doklady, 1966.

[Yasunaga and Liang, 2020]
Michihiro Yasunaga and Percy Liang.
Graph-based, self-supervised program repair from diagnostic feedback.
In International Conference on Machine Learning, 2020.

[Nguyen et al., 2013]
Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra.
Semfix: Program repair via semantic analysis.
In Conference on Software Engineering, 2013.

[Jiang et al., 2018]
Jiajun Jiang, Yingfei Xiong, Hongyu Zhang, Qing Gao, and Xiangqun Chen.
Shaping program repair space with existing patches and similar code.
In ACM SIGSOFT International Symposium on Software Testing and
Analysis, 2018.

[Xin and Reiss, 2017]
Qi Xin and Steven P Reiss.
Leveraging syntax-related code for automated program repair.
In International Conference on Automated Software Engineering,

[Goues et al., 2019]
Claire Le Goues, Michael Pradel, and Abhik Roychoudhury.
Automated program repair.
Communications of the ACM, 2019.

[Schulte et al., 2010]
Eric Schulte, Stephanie Forrest, and Westley Weimer.
Automated program repair through the evolution of assembly code.
In International Conference on Automated Software Engineering,

[Koyuncu et al., 2020]
Anil Koyuncu, Kui Liu, Tegawendé F Bissyandé, Dongsun Kim, Jacques
Klein, Martin Monperrus, and Yves Le Traon.
Fixminer: Mining relevant fix patterns for automated program repair.
Empirical Software Engineering, 2020.

[Durieux and Monperrus, 2016]
Thomas Durieux and Martin Monperrus.
Dynamoth: dynamic code synthesis for automatic program repair.
In International Workshop on Automation of Software Test,

[Li et al., 2020]
Yi Li, Shaohua Wang, and Tien N Nguyen.
Dlfix: Context-based code transformation learning for automated
program repair.
In International Conference on Software Engineering,

[Chen et al., 2017]
Liushan Chen, Yu Pei, and Carlo A Furia.
Contract-based program repair without the contracts.
In International Conference on Automated Software Engineering,

[White et al., 2019]
Martin White, Michele Tufano, Matias Martinez, Martin Monperrus, and Denys
Sorting and transforming program repair ingredients via deep learning
code similarities.
In IEEE International Conference on Software Analysis,
Evolution and Reengineering, 2019.

[Gupta et al., 2017]
Rahul Gupta, Soham Pal, Aditya Kanade, and Shirish Shevade.
Deepfix: Fixing common c language errors by deep learning.
In Association for the Advancement of Artificial Intelligence,

[Wang et al., 2017]
Ke Wang, Rishabh Singh, and Zhendong Su.
Dynamic neural program embedding for program repair.
arXiv preprint arXiv:1711.07163, 2017.

[Mesbah et al., 2019]
Ali Mesbah, Andrew Rice, Emily Johnston, Nick Glorioso, and Edward Aftandilian.
Deepdelta: learning to repair compilation errors.
In ACM Joint Meeting on European Software Engineering
Conference and Symposium on the Foundations of Software Engineering, 2019.

[Zhu et al., 2019]
He Zhu, Zikang Xiong, Stephen Magill, and Suresh Jagannathan.
An inductive synthesis framework for verifiable reinforcement
In ACM SIGPLAN Conference on Programming Language Design and
Implementation, 2019.

[Long et al., 2015]
Jonathan Long, Evan Shelhamer, and Trevor Darrell.
Fully convolutional networks for semantic segmentation.
In IEEE Conference on Computer Vision and Pattern Recognition,

[Hausman et al., 2018]
Karol Hausman, Jost Tobias Springenberg, Ziyu Wang, Nicolas Heess, and Martin
Learning an embedding space for transferable robot skills.
In International Conference on Learning Representations, 2018.

[Mnih et al., 2015]
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness,
Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg
Ostrovski, et al.
Human-level control through deep reinforcement learning.
Nature, 2015b.


# A note on directional Lipschitz continuity in the Euclidean plane

David Hruška  Leipzig University, Faculty of Mathematics and Computer Science,
Institute of Mathematics, Augustusplatz 10, 04 109 Leipzig, Germany
<EMAIL_ADDRESS>
###### Abstract.

We prove a stronger version of a conjecture stated in a paper from 2017 by J.
M. Ash and S. Catoiu concerning relations between various notions of the
Lipschitz property and differentiability in the Euclidean plane. We also
provide an improved version of the main result of that paper.

##  1\. Introduction and main results

In the conclusion of [1] (Conjecture 7 therein) the authors suggest the
following might hold (see the next section for the definitions):

######  Conjecture 1.

Let $f:\mathbb{R}^{2}\to\mathbb{R}$ and
$E=\bigl{\\{}\boldsymbol{x}\in\mathbb{R}^{2}:f\text{~{}is Lipschitz
at~{}}\boldsymbol{x}\text{~{}in every direction}\bigr{\\}}$. Then

$F=\bigl{\\{}\boldsymbol{x}\in E:f\text{~{}is not Lipschitz
at~{}}\boldsymbol{x}\text{~{}relative to~{}}E\bigr{\\}}$

is a null set.

In order to put this statement in context, consider the following heuristic
principle (cf. also the discussion concluding the first section of [1]):

(1) $\displaystyle\begin{split}&\text{If $f:\mathbb{R}^{d}\to\mathbb{R}$ is
any function and $E$ denotes the set of points where $f$ is
\emph{smooth}}~{}\text{in}\\\ &\text{\emph{many directions}, then $f$ is
Lipschitz relative to $E$ on a~{}\emph{large subset} of $E$ (or
$\mathbb{R}^{d}$).}\end{split}$

The main result of [1], Theorem 4, disproves a variant of this principle with
$d=2$ and the emphasized parts replaced by _differentiable_ , _almost every
direction_ and _a subset of $E$ of full measure_, respectively. Conjecture 1
then concerns with another precise version of (1).

This paper contributes to investigation of the principle (1) in two ways. On
one hand, we confirm Conjecture 1 in a stronger form. Namely, we prove

######  Theorem 1.

Let $f:\mathbb{R}^{2}\to\mathbb{R}$ and define

$E=\bigl{\\{}\boldsymbol{x}\in\mathbb{R}^{2}:f\text{~{}is Lipschitz
at~{}}\boldsymbol{x}\text{~{}in residual many directions}\bigr{\\}}.$

Then the set

$F=\bigl{\\{}\boldsymbol{x}\in E:f\text{~{}is not Lipschitz
at~{}}\boldsymbol{x}\text{~{}relative to~{}}E\bigr{\\}}$

is $\sigma$-porous.

On the other hand, we have

######  Theorem 2.

There exist sets $Z\subset\mathbb{R}^{2}$ and $E\subset\mathbb{R}^{2}$ such
that $\left|{\mathbb{R}^{2}\setminus E}\right|=0$ and $\chi_{Z}$ (the
characteristic function of $Z$) is at each point of $E$ differentiable in
almost every direction, but $\chi_{Z}$ is nowhere Lipschitz relative to $E$.

This construction refines Theorem 4 from [1] and, consequently, further
restricts the extent to which the principle (1) can possibly be valid.

###  1.1. Preliminaries

Let us start with some useful notation conventions and necessary definitions.

######  Notation.

The Euclidean norm on $\mathbb{R}^{d}$ will be denoted by
$\left\lVert{\cdot}\right\rVert$ and the corresponding unit sphere by
$\mathbb{S}^{d-1}$. For $\boldsymbol{x}\in\mathbb{R}^{d}$ and $r>0$ we write
$B(\boldsymbol{x},r)$ for the open ball centered at $\boldsymbol{x}$ with
radius $r$. For $k>0$ we define $k*B(\boldsymbol{x},r)=B(\boldsymbol{x},kr)$.
When $A\subset X$ is measurable with respect to an implicitly given measure
$\mu$, we write $\left|{A}\right|=\mu(A)$. If $\mathcal{A}$ is a countable
system of sets we write

$\bigcup\mathcal{A}=\\{x:x\in A\text{~{}for
some~{}}A\in\mathcal{A}\\}\text{~{}and~{}}\limsup\mathcal{A}=\\{x:x\in
A\text{~{}for infinitely many~{}}A\in\mathcal{A}\\}.$

######  Definition 1 ($\sigma$-porosity in $\mathbb{R}^{d}$).

We say that a set $A\subset\mathbb{R}^{d}$ is _porous at_
$\boldsymbol{x}\in\mathbb{R}^{d}$, if there is $0<p<1$ such that for every
$\varepsilon>0$ there exists $\boldsymbol{y}\in B(\boldsymbol{x},\varepsilon)$
such that $\boldsymbol{x}\neq\boldsymbol{y}$ and
$B(\boldsymbol{y},p\\!\left\lVert{\boldsymbol{x}-\boldsymbol{y}}\right\rVert)\cap
A=\emptyset$. If $A$ is porous at $\boldsymbol{x}$ for all $\boldsymbol{x}\in
A$ we say that $A$ is _porous_. A subset of $\mathbb{R}^{d}$ is called
_$\sigma$ -porous_ if it is a countable union of porous sets.

######  Definition 2 (Directional and relative Lipschitz property).

Let $G\subset\mathbb{R}^{d}$ be an open set, ${f:G\to\mathbb{R}}$ a function
and $\boldsymbol{u}\in\mathbb{S}^{d-1}$. We say that $f$ is _Lipschitz at
$\boldsymbol{x}\in G$ in direction $\boldsymbol{u}$_ if

$\limsup_{h\to
0+}\frac{\left|{f(\boldsymbol{x}+h\boldsymbol{u})-f(\boldsymbol{x})}\right|}{h}<\infty.$

We say that $f$ is _Lipschitz_ at $\boldsymbol{x}$ _in residual many
directions_ (resp. _in almost every direction_) if the set

$\left\\{u\in\mathbb{S}^{d-1}:f\text{~{}is not Lipschitz
at~{}}\boldsymbol{x}\text{~{}in direction~{}}\boldsymbol{u}\right\\}$

is of the first Baire category (resp. of zero Hausdorff measure
$\mathcal{H}^{d-1}$) in $\mathbb{S}^{d-1}$.

Differentiability at $\boldsymbol{x}\in G$ in direction
$\boldsymbol{u}\in\mathbb{S}^{d-1}$ and in almost every direction is defined
analogously.

We say that $f$ is _Lipschitz_ at $\boldsymbol{x}\in G$ _relative to_
$M\subset G$ if $\boldsymbol{x}$ is not a limit point of $M$ or

$\limsup_{\boldsymbol{y}\to\boldsymbol{x},\,\boldsymbol{y}\in
M}\frac{\left|{f(\boldsymbol{y})-f(\boldsymbol{x})}\right|}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}<\infty.$

######  Definition 3 (Circular sector).

For $d\geq 2$, $\boldsymbol{x}\in\mathbb{R}^{d}$,
$\boldsymbol{u}\in\mathbb{S}^{d-1}$ and $\delta,r>0$ we define an _open
circular sector_ with vertex $\boldsymbol{x}$, axis $\boldsymbol{u}$, opening
parameter $\delta$ and radius $r$ by

$C(\boldsymbol{x},\boldsymbol{u},\delta,r)=\left\\{\boldsymbol{x}\neq\boldsymbol{y}\in\mathbb{R}^{d}:\left\lVert{\frac{\boldsymbol{y}-\boldsymbol{x}}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}-\boldsymbol{u}}\right\rVert<\delta\right\\}\cap
B(\boldsymbol{x},r).$

##  2\. Proof of the positive result

The proof of Theorem 1 relies on the following variant of Proposition 3.1.
from [2].

######  Lemma 1.

Let $d\geq 2$, $f:\mathbb{R}^{d}\to\mathbb{R}$ be any function and
$M\subset\mathbb{R}^{d}$ any set. Let $A$ be the set of all points
$\boldsymbol{x}\in M$ for which there exists an open circular sector
$C=C(\boldsymbol{x},\boldsymbol{u},\delta,r)$ such that $f$ is Lipschitz at
$\boldsymbol{x}$ relative to $M\cap C$ but $f$ is not Lipschitz at
$\boldsymbol{x}$ relative to $M$. Then $A$ is $\sigma$-porous.

Before we provide the proof (a slight modification of that given in [2]), let
us recall the following elementary fact (see e.g. Lemma 5.1 in [3]).

######  Proposition 1.

If $\boldsymbol{u}$,
$\boldsymbol{v}\in\mathbb{R}^{d}\setminus\\{\boldsymbol{0}\\}$, then
$\left\lVert{\frac{\boldsymbol{u}}{\left\lVert{\boldsymbol{u}}\right\rVert}-\frac{\boldsymbol{v}}{\left\lVert{\boldsymbol{v}}\right\rVert}}\right\rVert\leq\frac{2}{\left\lVert{\boldsymbol{v}}\right\rVert}\left\lVert{\boldsymbol{u}-\boldsymbol{v}}\right\rVert$.

###### Proof of Lemma 1.

Let $\\{\boldsymbol{v}_{n}:n\in\mathbb{N}\\}$ be a dense subset of
$\mathbb{S}^{d-1}$. For positive integers $k$, $p$, $n$, $m$ we denote by
$A_{k,p,n,m}$ the set of all points $\boldsymbol{x}\in A$ such that

(2)
$\frac{\left|{f(\boldsymbol{y})-f(\boldsymbol{x})}\right|}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}<k\
\ \text{whenever}\ \
0<\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert<\frac{1}{p},\
\boldsymbol{y}\in M\ \text{and}\ \
\left\|\frac{\boldsymbol{y}-\boldsymbol{x}}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}-\boldsymbol{v}_{n}\right\|<\frac{1}{m}.$

Since $A$ is clearly the (countable) union of all sets $A_{k,p,n,m}$, it is
sufficient to prove that for given $k$, $p$, $n$, $m\in\mathbb{N}$ the set
$A_{k,p,n,m}$ is porous at any $\boldsymbol{x}\in A_{k,p,n,m}$. To this end,
find a sequence $\boldsymbol{y}_{i}\xrightarrow{i\to\infty}\boldsymbol{x}$
such that for each $i\in\mathbb{N}$ we have
$\boldsymbol{y}_{i}\neq\boldsymbol{x}$, $\boldsymbol{y}_{i}\in M$ and

(3)
$\frac{\left|{f(\boldsymbol{y}_{i})-f(\boldsymbol{x})}\right|}{\left\lVert{\boldsymbol{y}_{i}-\boldsymbol{x}}\right\rVert}>k(12m+4)$

Set $r_{i}=\left\lVert{\boldsymbol{y}_{i}-\boldsymbol{x}}\right\rVert$ and
$\boldsymbol{x}_{i}=\boldsymbol{x}-6mr_{i}\boldsymbol{v}_{n}$. It is
sufficient to prove that there exists $i_{0}\in\mathbb{N}$ such that

(4) $B(\boldsymbol{x}_{i},r_{i})\cap A_{k,p,n,m}=\emptyset\ \ \ \text{for
each}\ \ \ i\geq i_{0}.$

Consider $\boldsymbol{z}_{i}\in B(\boldsymbol{x}_{i},r_{i})\cap A_{k,p,n,m}$
for some $i\in\mathbb{N}$ and observe that

$6mr_{i}-r_{i}\leq\left\lVert{\boldsymbol{x}-\boldsymbol{x}_{i}}\right\rVert-\left\lVert{\boldsymbol{x}_{i}-\boldsymbol{z}_{i}}\right\rVert\leq\left\lVert{\boldsymbol{x}-\boldsymbol{z}_{i}}\right\rVert\leq\left\lVert{\boldsymbol{x}-\boldsymbol{x}_{i}}\right\rVert+\left\lVert{\boldsymbol{x}_{i}-\boldsymbol{z}_{i}}\right\rVert\leq
6mr_{i}+r_{i}$

and thus

$6mr_{i}-2r_{i}\leq\left\lVert{\boldsymbol{x}-\boldsymbol{z}_{i}}\right\rVert-
r_{i}\leq\left\lVert{\boldsymbol{y}_{i}-\boldsymbol{z}_{i}}\right\rVert\leq\left\lVert{\boldsymbol{x}-\boldsymbol{z}_{i}}\right\rVert+r_{i}\leq
6mr_{i}+2r_{i}.$

These inequalities imply that there exists $i_{0}\in\mathbb{N}$, which we fix,
such that

(5) $0<\left\lVert{\boldsymbol{x}-\boldsymbol{z}_{i}}\right\rVert<\frac{1}{p}\
\ \text{and}\ \
0<\left\lVert{\boldsymbol{y}_{i}-\boldsymbol{z}_{i}}\right\rVert<\frac{1}{p}\quad\text{for
every}\ \ i\geq i_{0}.$

Proposition 1 yields

(6)
$\left\|\frac{\boldsymbol{x}-\boldsymbol{z}_{i}}{\|\boldsymbol{x}-\boldsymbol{z}_{i}\|}-\boldsymbol{v}_{n}\right\|=\left\|\frac{\boldsymbol{x}-\boldsymbol{z}_{i}}{\|\boldsymbol{x}-\boldsymbol{z}_{i}\|}-\frac{\boldsymbol{x}-\boldsymbol{x}_{i}}{\|\boldsymbol{x}-\boldsymbol{x}_{i}\|}\right\|\leq
2\frac{\|\boldsymbol{x}_{i}-\boldsymbol{z}_{i}\|}{\|\boldsymbol{x}-\boldsymbol{x}_{i}\|}<\frac{2r_{i}}{6mr_{i}}<\frac{1}{m}$

and analogously

(7)
$\left\|\frac{\boldsymbol{y}_{i}-\boldsymbol{z}_{i}}{\|\boldsymbol{y}_{i}-\boldsymbol{z}_{i}\|}-\boldsymbol{v}_{n}\right\|=\left\|\frac{\boldsymbol{y}_{i}-\boldsymbol{z}_{i}}{\|\boldsymbol{y}_{i}-\boldsymbol{z}_{i}\|}-\frac{\boldsymbol{x}-\boldsymbol{x}_{i}}{\|\boldsymbol{x}-\boldsymbol{x}_{i}\|}\right\|\leq
2\frac{\|\boldsymbol{y}_{i}-\boldsymbol{x}\|+\|\boldsymbol{x}_{i}-\boldsymbol{z}_{i}\|}{\|\boldsymbol{x}-\boldsymbol{x}_{i}\|}<\frac{4r_{i}}{6mr_{i}}<\frac{1}{m}.$

Since $\boldsymbol{x}$, $\boldsymbol{y}_{i}\in M$, conditions (2), (5), (6)
and (7) imply that if $i\geq i_{0}$, then

$\frac{\left|{f(\boldsymbol{x})-f(\boldsymbol{z}_{i})}\right|}{\|\boldsymbol{x}-\boldsymbol{z}_{i}\|}<k\
\ \ \text{and}\ \ \
\frac{\left|{f(\boldsymbol{y}_{i})-f(\boldsymbol{z}_{i})}\right|}{\|\boldsymbol{y}_{i}-\boldsymbol{z}_{i}\|}<k.$

Using also inequality (3), we obtain for every $i\geq i_{0}$ that

$\displaystyle r_{i}k(12m+4)$
$\displaystyle<\left|{f(\boldsymbol{x})-f(\boldsymbol{y}_{i})}\right|\leq\left|{f(\boldsymbol{x})-f(\boldsymbol{z}_{i})}\right|+\left|{f(\boldsymbol{y}_{i})-f(\boldsymbol{z}_{i})}\right|$
$\displaystyle<k\|\boldsymbol{x}-\boldsymbol{z}_{i}\|+k\|\boldsymbol{y}_{i}-\boldsymbol{z}_{i}\|\leq
k(6mr_{i}+r_{i}+6mr_{i}+2r_{i}),$

which is impossible. We have thus proved (4). ∎

The proof of Theorem 1 now boils down to fulfilling the assumptions of Lemma
1.

###### Proof of Theorem 1.

Choose $\boldsymbol{x}\in E$ arbitrarily and define

$S_{n}=\left\\{\boldsymbol{u}\in\mathbb{S}^{1}:\frac{\left|{f(\boldsymbol{x}+h\boldsymbol{u})-f(\boldsymbol{x})}\right|}{h}<n\text{~{}for
all~{}}0<h<\frac{1}{n}\right\\}.$

The definition of $E$ then yields
$\mathbb{S}^{1}=S_{0}\cup\bigcup_{n=1}^{\infty}S_{n}$ where
$S_{0}\subset\mathbb{S}^{1}$ is of the first category in $\mathbb{S}^{1}$
(which is a complete metric space). The Baire category theorem shows that
there exists $n\in\mathbb{N}$ such that $S_{n}$ is dense in a nonempty open
subset of $\mathbb{S}^{1}$. Hence there exists
$\boldsymbol{v}\in\mathbb{S}^{1}$ and $\delta>0$ such that

(8)
$\\{\boldsymbol{u}\in\mathbb{S}^{1}:\left\lVert{\boldsymbol{u}-\boldsymbol{v}}\right\rVert<\delta\\}\subset\overline{S_{n}}.$

In other words, using Definition 3, the union of open segments
$U=\bigcup_{\boldsymbol{u}\in
S_{n}}\left\\{\boldsymbol{x}+t\boldsymbol{u}:t\in\left(0,\frac{1}{n}\right)\right\\}$
is dense in
$C=C\left(\boldsymbol{x},\boldsymbol{v},\delta,\frac{1}{n}\right)$.

Consider any $\boldsymbol{y}\in C\cap E$. Due to the definition of $E$ the set
of directions $\boldsymbol{u}\in\mathbb{S}^{1}$ such that $f$ is Lipschitz at
$\boldsymbol{y}$ in direction $\boldsymbol{u}$ is residual in
$\mathbb{S}^{1}$. Let us pick such $\boldsymbol{u}$ which is moreover
different from
$\pm\frac{\boldsymbol{y}-\boldsymbol{x}}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}$
and observe that, since every two non-parallel lines in $\mathbb{R}^{2}$
intersect each other, it follows from condition (8) that there is a sequence
$\left(t_{i}\right)_{i=1}^{\infty}$ of positive numbers such that
$\boldsymbol{y}+t_{i}\boldsymbol{u}\in U$ for all $i\in\mathbb{N}$ and
$t_{i}\xrightarrow{i\to\infty}0+$. Since $f$ is continuous at $\boldsymbol{y}$
in direction $\boldsymbol{u}$ it follows that

$\frac{\left|{f(\boldsymbol{y})-f(\boldsymbol{x})}\right|}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}=\lim_{i\to\infty}\frac{\left|{f(\boldsymbol{y}+t_{i}\boldsymbol{u})-f(\boldsymbol{x})}\right|}{\left\lVert{\boldsymbol{y}+t_{i}\boldsymbol{u}-\boldsymbol{x}}\right\rVert}\leq
n.$

We have proved that for every $\boldsymbol{x}\in E$ there is an open circular
sector $C$ with vertex at $\boldsymbol{x}$ such that $f$ is Lipschitz at
$\boldsymbol{x}$ relative to $E\cap C$. To finish the proof, apply Lemma 1
with $M=E$ from which it follows that $A=F$. ∎

######  Remark.

Since Theorem 4 from [1] does not essentially depend on dimension $d\geq 2$ it
is natural to investigate the principle (1) in higher dimensions. However,
although Lemma 1 works for all $d\geq 2$, our proof of Theorem 1 makes use of
a specific property of the Euclidean plane, namely that every two lines are
either parallel or have a common point, and hence this proof cannot be
directly generalized to higher dimensions. It is not known to the author
whether such a generalization of Theorem 1 holds without further assumptions
on $f$.

##  3\. Proof of the negative result

Our construction further exploits the ideas introduced in the proof of Theorem
4 from [1] and, in addition, employs an iterative argument. We start by
stating two useful facts proven in [1].

######  Proposition 2.

Let $B=B(\boldsymbol{x},r)$ and
$\boldsymbol{y}\in\mathbb{R}^{2}\setminus\overline{B}$. Then the angle
$\theta$ that $B$ subtends when viewed from $\boldsymbol{y}$ satisfies
$\theta<\pi\frac{r}{\left\lVert{\boldsymbol{y}-\boldsymbol{x}}\right\rVert}$.

######  Proposition 3 (Borel-Cantelli lemma).

If $\mathcal{A}=\left\\{A_{i}:i\in\mathbb{N}\right\\}$ is a system of
measurable sets satisfying $\sum_{i=1}^{\infty}\left|{A_{i}}\right|<\infty$,
then $\left|{\limsup\mathcal{A}}\right|=0$.

###### Proof of Theorem 2.

We proceed in three steps. The first step generalizes the construction from
Paragraph 3.2 of [1] to arbitrary open subset of $\mathbb{R}^{2}$ and defines
the set $Z$ by iterating this construction. In the second step we define the
“good” set $E$ and prove that it has full measure in $\mathbb{R}^{2}$. The
third step shows that $\chi_{Z}$ is nowhere Lipschitz (even continuous)
relative to $E$.

Step 1. Given any non-empty open set $G\subset\mathbb{R}^{2}$, let
$\left\\{\boldsymbol{x}_{i}:i\in\mathbb{N}\right\\}$ be a dense subset of $G$.
Set $n_{1}=1$ and take an open ball $B_{1}=B(\boldsymbol{x}_{1},r_{1})$ such
that $B_{1}\subset G$ and

(9)
$r_{1}\leq\min\left\\{\frac{1}{4},\frac{\mathop{}\mathrm{diam\,}G}{8}\right\\}.$

For $k\in\mathbb{N}$ and pairwise disjoint open discs $B_{1},\dots,B_{k}$ let
$n_{k+1}$ be the smallest $n\in\mathbb{N}$ such that
$\boldsymbol{x}_{n}\notin\overline{\bigcup_{i=1}^{k}B_{i}}$, define

(10)
$r_{k+1}=\min\left\\{\frac{\min\left\\{1,\frac{1}{2}\mathop{}\mathrm{diam\,}{G}\right\\}}{4^{k+1}},\frac{1}{2}\mathrm{dist}\left({\boldsymbol{x}_{n_{k+1}}},{\left(\mathbb{R}^{2}\setminus
G\right)\cup\bigcup_{i=1}^{k}B_{i}}\right)\right\\}$

and finally let $B_{k+1}=B(\boldsymbol{x}_{n_{k+1}},r_{k+1})$. It is easy to
see that this inductive procedure continues beyond any finite number of steps
($n_{k+1}$ always exists and $r_{k+1}>0$ is well defined) and yields a
countable system

$\mathcal{S}(G)=\left\\{B_{i}:i\in\mathbb{N}\right\\}$

of pairwise disjoint open discs contained in $G$ such that its union is dense
in $G$. Next, we define the corresponding system of enlarged closed discs

$\mathcal{E}(G)=\left\\{\overline{2^{i}*B_{i}}:i\in\mathbb{N}\right\\}.$

Note that it follows from conditions (9) and (10) that
$2^{i}r_{i}\leq\frac{1}{2^{i}}$ for all $i\in\mathbb{N}$ and any non-empty
open set $G\subset\mathbb{R}^{2}$ thus satisfies

(11)
$\sum_{B\in\mathcal{S}(G)}\left|{B}\right|\leq\sum_{B\in\mathcal{E}(G)}\left|{B}\right|\leq\pi\sum_{i=1}^{\infty}\left(\frac{1}{2^{i}}\right)^{2}<\infty.$

For any disc $B$ of radius $R>0$ conditions (9) and (10) similarly imply

(12) $\left|{\bigcup\mathcal{S}(B)}\right|\leq\pi
R^{2}\sum_{i=1}^{\infty}\left(\frac{1}{4^{i}}\right)^{2}<\frac{1}{2}\left|{B}\right|$

which in particular shows that

(13) $B\setminus\bigcup\mathcal{S}(B)\text{~{}is a Borel set of positive
measure}.$

Set $\mathcal{D}_{1}=\mathcal{S}(\mathbb{R}^{2})$ and for $k\in\mathbb{N}$
define inductively
$\mathcal{D}_{k+1}=\bigcup_{B\in\mathcal{D}_{k}}\mathcal{S}(B)$. Finally, let
us set

(14)
$Z=\bigcup_{m=1}^{\infty}\left(\bigcup\mathcal{D}_{2m-1}\setminus\bigcup\mathcal{D}_{2m}\right).$

In terms of $\chi_{Z}$, this construction starts with the zero function,
changes its value to one on discs forming system $\mathcal{D}_{1}$, then
changes it back to zero on all the subsystems forming $\mathcal{D}_{2}$, etc.

Step 2. First define

$E=\left\\{\boldsymbol{x}\in\mathbb{R}^{2}:\chi_{Z}\text{~{}is differentiable
in almost every direction at~{}}\boldsymbol{x}\right\\}.$

Note that the set
$C=\bigcup_{k\in\mathbb{N}}\bigcup_{B\in\mathcal{D}_{k}}\partial B$ has zero
Lebesgue measure. Using Proposition 3 it follows from (11) that

(15) $N_{0}=C\cup\limsup\mathcal{E}(\mathbb{R}^{2})$

is also a null set.

Let us denote the angle subtended by a disc $D$ when viewed from point
$\boldsymbol{y}\notin\overline{D}$ by $\theta_{D}$ and take any
$\boldsymbol{y}\in\mathbb{R}^{2}\setminus\left(\bigcup\mathcal{D}_{1}\cup
N_{0}\right)$. Definition (15) implies that
$\displaystyle\boldsymbol{y}\notin\overline{B}$ whenever $B\in\mathcal{D}_{1}$
and if $B=2^{j}*B_{j}\in\mathcal{E}(\mathbb{R}^{2})$, then
$\boldsymbol{y}\in\overline{B}$ only if $j\in F$ for some finite set
$F\subset\mathbb{N}$. Proposition 2 yields

$\sum_{D\in\mathcal{D}_{1}\setminus\left\\{B_{j}:j\in
F\right\\}}\theta_{D}\leq\pi\sum_{i=1}^{\infty}\frac{1}{2^{i}}<\infty$

and Proposition 3 (now for the Hausdorff measure $\mathcal{H}^{1}$ on
$\mathbb{S}^{1}$) then shows that the set of directions
$\boldsymbol{u}\in\mathbb{S}^{1}$, such that the ray
$\left\\{\boldsymbol{y}+t\boldsymbol{u}:t\in(0,\infty)\right\\}$ intersects
infinitely many discs from $\mathcal{D}_{1}$, is null in $\mathbb{S}^{1}$. It
follows that in all the other directions $\chi_{Z}$ is identically zero in a
positive distance from $\boldsymbol{y}$ and we conclude that
$\mathbb{R}^{2}\setminus\left(\bigcup\mathcal{D}_{1}\cup N_{0}\right)\subset
E$.

For any $m\in\mathbb{N}$ we define

$N_{m}=C\cup\bigcup_{B\in\mathcal{D}_{m}}\left(B\cap\limsup\mathcal{E}(B)\right).$

Since $\mathcal{D}_{m}$ consists of pairwise disjoint open discs and set
$N_{m}$ has zero measure, analogous arguments as above show that for every
$\boldsymbol{y}\in\left(\bigcup\mathcal{D}_{m}\right)\setminus(\bigcup\mathcal{D}_{m+1}\cup
N_{m})$ the function $\chi_{Z}$ is constant in almost every direction in a
positive distance from $\boldsymbol{y}$. Hence
${\left(\bigcup\mathcal{D}_{m}\right)\setminus(\bigcup\mathcal{D}_{m+1}\cup
N_{m})\subset E}$ for every $m\in\mathbb{N}$ and altogether we end up with

$\mathbb{R}^{2}\setminus
E\subset\left(\bigcup_{i=0}^{\infty}N_{i}\right)\,\cup\,\left(\bigcap_{m=1}^{\infty}\bigcup\mathcal{D}_{m}\right).$

Conditions (11) and (12) together with the definition of $\mathcal{D}_{m}$
imply $\left|{\bigcup\mathcal{D}_{m}}\right|\xrightarrow{m\to\infty}0$ and we
conclude that $\left|{\mathbb{R}^{2}\setminus E}\right|=0$.

Step 3. Observe that since $E\subset\mathbb{R}^{2}$ has full measure, it
follows from assertion (13) that for every $m\in\mathbb{N}$ and
$B\in\mathcal{D}_{m}$ the set
$\left(B\setminus\bigcup\mathcal{S}(B)\right)\cap E$ is non-empty. In
particular, it follows that

(16) $\text{~{}for any odd~{}}m\in\mathbb{N}\text{~{}and
disc~{}}B\in\mathcal{D}_{m},\text{~{}the equality~{}}\chi_{Z}=1\text{~{}holds
somewhere in~{}}E\cap B.$

Take any $\boldsymbol{x}\in\mathbb{R}^{2}\setminus\bigcup\mathcal{D}_{1}$ and
$\varepsilon>0$. Then $\chi_{Z}(\boldsymbol{x})=0$ and note that it follows
from condition (10) that the pairwise disjoint discs forming $\mathcal{D}_{1}$
do not touch (i.e. their boundary circles are pairwise disjoint as well). Thus
there is at most one disc $D\in\mathcal{D}_{1}$ such that
$\boldsymbol{x}\in\partial D$. For the same reason, union of any finite
subsystem $\mathcal{D}^{\prime}\subset\mathcal{D}_{1}$ not containing $D$ has
a positive distance from $D\cap B(\boldsymbol{x},\frac{\varepsilon}{2})$ (or
simply to $\\{\boldsymbol{x}\\}$ when there is no such $D$). In both cases the
density of $\bigcup\mathcal{D}_{1}$ in $\mathbb{R}^{2}$ implies that there
must be infinitely many discs from $\mathcal{D}_{1}$ intersecting
$B(\boldsymbol{x},\frac{\varepsilon}{2})$ and due to the decay of their radii
implied by formula (10) we can find one contained in
$B(\boldsymbol{x},\varepsilon)$. Assertion (16) then yields a point
$\boldsymbol{y}\in B(\boldsymbol{x},\varepsilon)\cap E$ such that
$\chi_{Z}(\boldsymbol{y})=1$. Since $\varepsilon>0$ was arbitrary, we conclude
that $\chi_{Z}$ is not continuous at $\boldsymbol{x}$ relative to $E$.

Analogous arguments work for any $m\in\mathbb{N}$, $B\in\mathcal{D}_{m}$ and
$\boldsymbol{x}\in
B\setminus\bigcup\mathcal{D}_{m+1}=B\setminus\bigcup\mathcal{S}(B)$ (recall
that elements of $\mathcal{D}_{m}$ are pairwise disjoint) with the only
modification being that for odd $m$ the roles of values $0$ and $1$ of
$\chi_{Z}$ interchange.

Finally, for any
$\boldsymbol{x}\in\bigcap_{m=1}^{\infty}\bigcup\mathcal{D}_{m}$ and
$\varepsilon>0$ observe that $\chi_{Z}(\boldsymbol{x})=0$ and conditions (9)
and (10) imply
$\sup_{B(\boldsymbol{z},r)\in\mathcal{D}_{k}}r\xrightarrow{k\to\infty}0$.
Hence there are index $i\in\mathbb{N}$ and disc $D\in\mathcal{D}_{2i-1}$ such
that $\boldsymbol{x}\in D\subset B(\boldsymbol{x},\varepsilon)$ and again by
observation (16) we find a point $\boldsymbol{y}\in D\cap E$ such that
$\chi_{Z}(\boldsymbol{y})=1$. As $\varepsilon>0$ was arbitrary, the conclusion
follows. ∎

## References

  * [1] Ash, J., & Catoiu, S. (2017). Directional Differentiability in the Euclidean Plane. Real Analysis Exchange, 42(1), 185-192. doi:10.14321/realanalexch.42.1.0185
  * [2] Zajíček, L. (2015). Hadamard differentiability via Gâteaux differentiability. Proc. Amer. Math. Soc. 143 (2015), 279-288. https://doi.org/10.1090/S0002-9939-2014-12228-3
  * [3] Massera, J., & Schaffer, J. (1958). Linear Differential Equations and Functional Analysis, I. Annals of Mathematics, 67(3), second series, 517-573. doi:10.2307/1969871


11institutetext: Bar-Ilan University, Israel

# Quadratic GCN for Graph Classification

Omer Nagar  Shoval Frydman  Ori Hochman  Yoram Louzoun<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Graph Convolutional Networks (GCNs) have been extensively used to classify
vertices in graphs and have been shown to outperform other vertex
classification methods. GCNs have been extended to graph classification tasks
(GCT). In GCT, graphs with different numbers of edges and vertices belong to
different classes, and one attempts to predict the graph class. GCN based GCT
have mostly used pooling and attention-based models. The accuracy of existing
GCT methods is still limited. We here propose a novel solution combining GCN,
methods from knowledge graphs, and a new self-regularized activation function
to significantly improve the accuracy of the GCN based GCT. We present
quadratic GCN (QGCN) - A GCN formalism with a quadratic layer. Such a layer
produces an output with fixed dimensions, independent of the graph vertex
number. We applied this method to a wide range of graph classification
problems, and show that when using a self regularized activation function,
QGCN outperforms the state of the art methods for all graph classification
tasks tested with or without external input on each graph. The code for QGCN
is available at:
https://github.com/Unknown-Data/QGCN.

###### Keywords:

Machine Learning GCN Quadratic activation graph classification activation
function

##  1 Introduction

Information is often represented through relations between entities. A
standard formalism to represent such relations are graphs, where relations are
represented by edges that can be directed and weighted. Such graphs are often
used for vertex classification tasks, where one aims to classify the vertices
of a given graph. For example, given citations between papers, one could
attempt to classify the paper domain [28]. Such tasks are often performed
through information diffusion in the network, following the assumption that
neighboring vertices have similar classes [5, 46, 2]. Recently more complex
approaches have been proposed to use the network topology [39, 32, 15] or the
propagation of external information [20, 44]. A dominant approach for such
classifications (either supervised or semi-supervised) is Graph Convolutional
Networks (GCN) [22]. GCNs are based on weighting a signal propagated through
first neighbors in the graph in each layer of the neural network. The general
formalism of a layer in GCNs is:

$X_{k}=\sigma(X_{k-1}*\tilde{A}*W_{k}),$ (1)

where $A$ is a matrix derived from the adjacency matrix. Often, the symmetric
and normalized adjacency matrix in addition to the identity is used:

$\tilde{A}=D^{-1/2}[A+A^{T}+I]D^{-1/2}.$ (2)

$W_{k}$ and $X_{k}$ are weights and input values of the $k^{th}$ layer, where
the input to the first layer is the available information on vertices. The
output layer has dimensions of the vertex number by the number of classes. A
large number of extensions and applications of GCN have been published in
combination with many other learning methods, including, among others,
combinations of GCN with recurrent neural networks [27], with GANs [25] and
with active learning [1].

A related, but much less studied task is the Graph Classification Task (GCT),
where each graph belongs to one of $N_{C}$ different classes. For example,
proteins can be classified based on their molecular interaction graphs,
organizations can be grouped based on their communication graphs. GCT pose a
challenge to GCN based approaches since those produce a projection for each
vertex. As such their output dimension is determined by the number of
vertices. Current approaches for reducing the output dimension to a fixed
value are based on statistical properties of the vertex projection or the
network itself [36, 35], or pooling [53]. We here propose a direct approach,
adopted from knowledge graphs [16] \- an additional quadratic layer to the GCN
:

$X_{end}=\sigma(V_{1}^{T}*F(X_{k_{i}})^{T}*\tilde{A}*X_{k}*V_{2}),$ (3)

where $V_{1}$ and $V_{2}$ are different weight matrices, and $X_{k}$ is the
input values to the $k$ layer. $F(X_{k_{i}})$ is some combination of the input
to the different layers (e.g. concatenation of the input to different layers).
Such a formalism outputs a result of fixed dimensions equal to the external
dimensions of $V_{1}$ and $V_{2}$. We here propose that using such a formalism
with an output vector of the size of the number of classes can be directly
used to classify networks. We denote this formalism Quadratic GCN (QGCN). QGCN
produces for each network, through a soft-max, a probability for each of the
possible classes. We further propose to use as input to the first layer of the
QGCN a set of basic topological features, such as the degree, or the number of
triangles around each vertex. A limitation of such inputs is that their
distribution is often imbalanced, with a large number of vertices with a zero
input. We propose a novel activation function to treat such input.

##  2 Relation to Previous Work

GCTs have emerged in multiple independent domains, including Graph kernel
analysis, GCN, chemoinformatics, attention-based methods, and self-supervised
based methods.

In chemoinformatics, the function of molecules is predicted from their
structure and composition. Each molecule is represented as a network of atoms
or amino acids, and each vertex is associated with biochemical properties,
such as its molecular weight, charge. etc. Edges can also be associated with
the physical distance between the vertices, or the type of molecular bond. We
have here tested three datasets of such molecules, including the
classification of protein groups [7], the classification of mutagens [21] and
the classification of molecules that can be used as drugs [13].

GCTs have been performed using kernel approaches. Graph kernels exploit
compare graphs through the frequency of subgraphs. Kernel methods typically
restrict themselves to comparing substructures computable in a polynomial
time. Many graph kernels have been defined, such as random walks [19, 12],
shortest paths [3], limited size graphlets (also denoted motifs) [41] and
subtrees [38]. [49] proposed a general smoothing framework for graph kernels
by taking structural similarity into account, and apply it to derive smoothed
variants of popular graph kernels. [23] gives a full survey of these methods.
Note that once a distance between graphs has been defined, the classification
itself is straightforward using distance-based classification methods.

GCNs have been also extended to GCT. Important efforts in this direction
include DIFFPOOL, a differentiable graph pooling module that can generate
hierarchical representations of graphs and use this hierarchy of vertex groups
to classify graphs [50]. Zhang et al. [53] have used a formalism very similar
to the Kipf and Welling formalism but added a pooling strategy to the last
layer with a SortPooling layer. Pan et al. have produced a couple of
algorithms of Multi-Task Learning (MTL). MTL jointly discovers discriminative
subgraph features across different tasks and uses them to classify graphs [36,
35]. As such, their work may be seen as an extension of kernel methods.
StructPool [51] considers the graph pooling as a vertex clustering problem,
which requires the learning of a cluster assignment matrix. EigenGCN [30]
proposes a pooling operator EigenPooling based on graph Fourier transform,
which can utilize the vertex features and local structures during the pooling
process. Other pooling include among many others are [48, 10, 57, 29].

Attention and self-attention based methods have also been extended to GCT. A
pooling method based on self-attention has been proposed in [24]. Self-
attention using graph convolution allows the pooling method to consider both
vertex features and graph topology. DAGCN [8] added an attention graph
convolution layer to a regular GCN to learn automatically the importance of
neighbors at different distances, then employed a second attention component,
a self-attention pooling layer, to generalize the graph representation from
the various aspects of a matrix graph embedding. [17] is a unified graph
neural net architecture that utilizes message-passing relay and attention
mechanism for multiple prediction tasks, including GCT. More attention-based
methods are [34, 55].

GCT has also been expanded to self-supervised learning. In many real-world
problems, the number of labeled graphs available for training classification
models is limited, which renders these models prone to overfitting. [52]
proposed two approaches based on contrastive self-supervised learning (CSSL)
to alleviate overfitting. One uses CSSL to pre-train graph encoders on widely-
available unlabeled graphs, while in the other a regularizer based on CSSL is
developed. Other approaches such as [45] and [37] have focused on learning
representations of local elements in graphs, such as nodes and subgraphs, but
can also be extended to graph classification.

We here propose to adapt from knowledge graphs quadratic layers and merge them
with a GCN formalism to classify graphs. A knowledge graph (KG) is a multi-
digraph with labeled edges, where the label represents the type of the
relationship. Such graphs have been used in multiple GCTs. A general framework
for KG is first an encoder to project the vertices, and then a decoder that
compresses vertex representations into a single representation. Then, to
classify full graphs, Duvenaud et al. [11] averaged all the vertex
projections. Gilmer et al. [14] used a DeepSet aggregation. Li et al. [26]
added a new virtual vertex and connected it to all the vertices. They then
used the representation of the virtual vertex as the representation of the
graph. However, our interest in KG is in the bilinear decoders proposed for
link predictions [47]. We here propose to merge bilinear decoders with GCN to
produce graph classifiers.

##  3 Novelty

The three main novel aspects of this work are:

  * •

A quadratic formalism for GCT that is a direct extension of GCNs. This
formalism is a GCN on all but the last layer, followed by a bilinear GCN last
layer. This formalism produces a fixed size output for graphs of different
sizes.

  * •

A significant improvement in classification accuracy over previously studied
GCT, either binary or multi-class.

  * •

A new method to classify graphs in the absence of external information (beyond
the adjacency matrix) using topological features of each vertex as an input to
each vertex in the GCN.

  * •

A novel self-regularized activation function to handle inputs that are
imbalanced with a large number of zero inputs.

##  4 Model

Each vertex is assigned an input vector $x_{0}(i)$ defined to be either
external information on each vertex or topological features of the vertex
[39]. The values of the following layers are computed as in Eq. 4, with a
distinction between the internal layer and the last layer.

$\displaystyle\tilde{A}=D^{-1/2}[A+A^{T}+I]D^{-1/2}\>or\>\tilde{A}=[A+A^{T}+I]$
(4) $\displaystyle
X_{k}=\sigma_{1}(X_{k-1}*\tilde{A}*W_{k})\quad\quad\quad\quad\quad\quad$
$\displaystyle
X_{end}=\sigma(V_{1}^{T}*F({X_{i}})^{T}*\tilde{A}*X_{k}*V_{2}),\quad\quad$

The non-linearity in the intermediate layers is:

$\sigma_{1}(x)=1-\frac{2}{x^{2}+1}.$ (5)

This activation function will be further discussed. The activation function in
the last layer is $\sigma(x)=\frac{1}{1+e^{-x}}$ for the binary cases, and a
softmax otherwise. $F$ is a function of the input to all layers, including the
first layer.

The formalism above translates each graph into a constant size output (Figure
1). As such, it is not sensitive to the graph size. The output is directly
amenable to standard loss minimization for graph classification problems by
comparing the fixed size output with the expected classification of the graph.
Here, a binary cross-entropy loss was used, and an ADAM optimizer.

Figure 1: Model description. Graphs of different sizes are passed through GCN
layers. The output size of each GCN layer is proportional to the number of
vertices in the current graph. The last layer is a quadratic layer with input
size proportional to the graph number of vertices and constant size output
size. Note that the dimension of the weights of the QGCN are not affected by
the graph vertex number, and as such can be learned on all graphs
simultaneously.

The model’s input consists of: A) The normalized adjacency matrix of the graph
$\tilde{A}=D^{-0.5}*[A+A^{T}+I]*D^{-0.5}$. We have tested other normalization
methods for the adjacency, but all led to significantly lower accuracy in the
training sets. B) A topological input matrix $x_{0}\in R^{n*d}$ for each
graph, where $n$ is the number of vertices in the graph. The features used
were: In/Out degree (or just degree if the graph is undirected), Centrality
and first and second moments of the distance distribution of each vertex to
all other vertices in the graph [4]. When supplied with the graphs, an
embedding vector for each vertex was used, instead of the topology.

##  5 Implementation

We compared the accuracy of QGCN using different datasets, as measured by
accuracy score. Each dataset was shuffled and split according to the split
ratio of the compared experiments. The weights were trained to minimize the
loss function over all studied networks in the training set, with equal
weights to all networks, independently of their vertex number.

Minimal hyper-parameter tuning was performed. The regularization was a weak
L2-regularization with coefficients of [1e-7, 1.e-8, 1.e-9, or 0]. The
normalization of the input was either z-scoring or standardization of the
input to the $0-1$ (further denoted Min-Max normalization). Two version of the
normalized adjacency matrix $\tilde{A}$ were used, as in equation 4, and the
input features to be used (see details in Table 2). Finally batch sizes
between $32$ and $128$ in jumps of $2$ were tested. The test set was not used
for any of the parameter tuning steps (See Table 2 for hyper-parameters).

###  5.1 Datasets Studied

We studied multiple previously tested datasets and compared our results on
those to the state of the art GCT algorithms. The datasets properties are
summarized in Table 1.

HIV (Aids) related molecules [13]. Each graph represents a molecular compound.
Each compound is classified as active or inactive. The labels indicate whether
a molecular compound is active against HIV or not. The vertices and the edges
of the graphs represent atoms and their covalent bounds respectively. The
dataset also contains non-topological information about the vertices of the
graph such as the chemical compound and the charge of the atom.

Mutagens [21]. As in the HIV dataset, molecules are converted to graphs, and
each graph is labeled as mutagen or non-mutagen.

Proteins classification Dataset [9]. PROTEINS is a protein graph dataset,
where vertices represent the amino acids and two vertices are connected by an
edge if they are less than 6 Angstroms apart. The label indicates whether or
not a protein is an enzyme.

Grec drawing classification. [33]. The dataset consists of graphs that were
produced by symbols from architectural and electronics drawings. The images
occur in five different distortion levels and the graphs are extracted from
the resulting de-noised images by tracing the lines from end to end and
detecting intersections as well as corners. the dataset contains 1,100 graphs
uniformly distributed over 22 classes.

NCI1 and NCI109 [40] are two balanced biological datasets screened for
activity against non-small cell lung cancer and ovarian cancer cell lines,
where each graph is a chemical compound with vertices and edges representing
atoms and chemical bonds, respectively.

The HIV, Mutagens, and Grec datasets contain information about each vertex,
while Proteins, NCI1, and NCI109 do not.

Table 1: Datasets Statistics Dataset | Num graphs | Avg vertices | Avg edges | Classes
---|---|---|---|---
Mutagencity | 188 | 17.93 | 19.79 | 2
NCI109 | 4127 | 29.68 | 32.13 | 2
NCI1 | 4110 | 29.87 | 32.30 | 2
Grec | 1100 | - | - | 22
Protein | 1113 | 39.06 | 72.82 | 2
Aids | 2000 | 15.69 | 16.20 | 2

###  5.2 Batch Optimization of QGCN

In order to run QGCN in a parallel batch form to allow for GPU based
processing, one must have input of equal size. While the weights matrices are
not affected by the graphs number of edges and vertices, the matrix product of
$\tilde{A}$ and $X_{k}$ is, preventing a tensor representation of the loss
computation and the resulting back propagation. To improve batch based
computation, QGCN uses a padding technique that allows it to stack the
$\tilde{A}$ of all graphs into one single tensor that has no effect on the
outcome. Zero padding from the right (and bottom) of both $\tilde{A}$ and
$X_{k}$ has no effect on the resulting $\tilde{A}X_{k}$ computation for all
layers, except for changing the output size. However, since the last layer
output size is constant, this is of no importance. We thus compute for each
batch the maximal vertex number, and zero pad the other graphs to this size.
At the current stage, QGCN does not handle sparse matrices.

Table 2: Fine-tuned hyperparamters. For all datasets: train-validation-test split is 0.675-0.125-0.2, learning rate is 1e-4, an Adam optimizer is used, 2 layers of GCN in size 250 each are applied and dropout=0. The hyperparameters that are different for each dataset are summarized here. NR corresponds to Norm reduced normalization of the adjacency matrix, while NRS is the symmetric normalization. In features, B is BFS, C is centrality and D is degree. Hyperparameter | Mutagencity | NCI109 | NCI1 | Grec | Proteins | Aids
---|---|---|---|---|---|---
Batch size | 128 | 128 | 32 | 32 | 128 | 128
L2 regularization | 1e-7 | 1e-9 | 1e-7 | 1e-9 | 1e-9 | 0
Standardization | z-score | z-score | min-max | min-max | min-max | z-score
Adjacency norm | NR | NR | NRS | NRS | NRS | NR
Features | C, D | B, C, D | B, C, D | B, C, D | B, C, D | B, C, D

##  6 Results

We tested the accuracy of the QGCN on the datasets above, as measured by the
test accuracy and compared it to several baselines that can be divided into
four groups: Graph Kernel Methods. Shortest-Path Kernel (SP) [6], Weisfeiler-
Lehman Kernel (WL) [40] and GRAPHLET [43]. Graph Pooling Models. Models that
combine GNNs with pooling operator for graph level representation learning:
HaarPool [48], HPG-SL [57], G-Inception [59], WKPI [58], EigenGCN [30] and
DGCNN [54].Attention based methods. DAGCN [8], SAG-Pool [24] and GAT-GC [56].
Self-supervised Methods. CSSL [52].

Table 3 presents the accuracy of QGCN on graph classification task compared to
the above baselines. Here, the quadratic layer (last layer of the GCN) is
calculated with $F(X_{k_{i}})=X_{0}$ where $X_{0}$ is the input layer of the
GCN. We have performed for each training set fraction, 20 trainings of the
model (for the same training/validation/test division and the same
parameters), and used the one providing the highest accuracy on the validation
set. In all datasets, both binary and multi-binary, QGCN reached a much higher
test-set accuracy than all previously published algorithms, with an
improvement that can reach $0.05$ vs the top competing algorithm. In the Aids
(HIV) reaction and Grec, we even obtain a prefect classification accuracy. The
results are not very sensitive to the hyperparameters used, with three
exceptions. The internal non-linearity function is crucial, a low
regularization must be used, and the $F(X_{k_{i}})$ should simply be the input
to the graph.

Table 4 shows QGCN performance on GCT where $F(X_{k_{i}})=C$ where $C$ is the
concatenation of the input to the different layers, or $F(X_{k_{i}})=X_{k-1}$
where $X_{k-1}$ is the last layer of the GCN (hyperparameters are described in
Table 2), or as is used in the tables above $F(X_{k_{i}})=X_{0}$. The
performance of QGCN is maximal when using the input layer as $F(X_{k_{i}})$.
For Mutagencity, the results are quite similar when one combines all input
layers, while for the other datasets they are lower. Furthermore, when using a
fully quadratic layer, the accuracy is even much lower. Note that more complex
functions, such as polynomials of the same matrices could be used. However,
here the simplest input layer seems to be the best choice.

Table 3: Accuracy comparison for graph classification tasks (accuracy score). In this and all tables, the standard error is the standard error on the test on 20 train-validation splits. The result presented is the test accuracy on the run with the best validation accuracy. The same holds for all following tables. Categories | Method | Mutagencity | NCI109 | NCI1 | Grec | Proteins | Aids
---|---|---|---|---|---|---|---
| SP |  80.10$\pm$0.20 |  77.60$\pm$0.30 |  79.30$\pm$0.40 | - |  75.90$\pm$0.40 |  99.70$\pm$0.00
Kernels | WL |  84.50$\pm$0.30 |  86.00$\pm$0.30 |  86.20$\pm$0.10 | - |  75.50$\pm$0.3 |  99.70$\pm$0.00
| GRAPHLET |  56.65$\pm$1.74 |  60.96$\pm$2.37 |  62.48$\pm$2.11 | - |  72.23$\pm$4.49 | -
| HGP-SL |  82.15$\pm$0.58 |  80.67$\pm$1.16 |  78.45$\pm$0.77 | - |  84.91$\pm$1.62 | -
| G Inception |  95.00$\pm$4.61 |  80.32$\pm$1.73 | - | - | - | -
Pooling | WKPI |  88.30$\pm$2.60 |  87.40$\pm$0.3 |  87.50$\pm$0.50 | - |  78.50$\pm$0.40 | -
| HaarPool |  90.00$\pm$3.60 |  75.60$\pm$1.20 |  78.60$\pm$0.50 | - |  80.40$\pm$1.80 | -
| DGCNN |  80.41$\pm$1.02 |  78.23$\pm$1.31 |  74.08$\pm$2.19 | - |  79.99$\pm$0.44 | -
| EigenGCN | 79.50 | 74.90 | 77.00 | - | 76.60 | -
| SAGPool | - |  74.06$\pm$0.78 |  74.18$\pm$1.20 | - |  71.86$\pm$0.97 | -
Attention | GAT-GC |  90.44$\pm$6.44 | - |  82.28$\pm$1.81 | - |  76.81$\pm$3.77 | -
| DAGCN | 87.22 | 81.46 | 81.68 | - | 76.33 | -
Self-Supervised | CSSL |  82.64$\pm$0.83 |  81.16$\pm$1.42 |  80.09$\pm$1.07 | - |  85.80$\pm$1.01 | -
Proposed | QGCN | 95.57$\pm$0.02 | 90.28$\pm$0.09 | 91.81$\pm$0.03 | 100.00$\pm$0.00 | 87.23$\pm$0.06 | 100.00$\pm$0.00
Table 4: Accuracy of QGCN on GCT with different $F(X_{k_{i}})$ $f(X_{k_{i}})$ | Mutagencity | NCI109 | NCI1 | Grec | Proteins | Aids
---|---|---|---|---|---|---
$C$ |  93.30$\pm$0.05 |  66.18$\pm$0.07 |  71.58$\pm$0.09 |  100.00$\pm$0.00 |  70.55$\pm$0.09 |  100.00$\pm$0.00
$X_{k-1}$ |  90.50$\pm$0.02 |  60.97$\pm$0.09 |  65.89$\pm$0.08 |  100.00$\pm$0.00 |  63.77$\pm$0.08 |  100.00$\pm$0.00
$X_{0}$ |  95.57$\pm$0.02 |  90.28$\pm$0.09 |  91.81$\pm$0.03 |  100.00$\pm$0.00 |  87.23$\pm$0.06 |  100.00$\pm$0.00

##  7 Self-Regularized Symetric Sigmoid - SRSS

A problem arising in the context of QGCN is that the input to many vertices is
0. Thus a dual input distribution often emerges, with a large fraction of zero
inputs, and a continuous distribution for other vertices. This happens, since
for many vertices, either the topological input or the external features input
is null. Moreover, when further multiplied by the adjacency matrix, a position
with a very low degree can obtain a value of 0 for the input from its
neighbors (Figure 2A). Thus, it may be more important to distinguish between
zero and non-zero values, than differentiating between positive and negative
values. We thus propose a non-linearity that has a minimum at zero to
distinguish between zero and non-zero values. We use this function for the
QGCN inner layers (the regular GCN layers). In classical activation functions,
such as Relu and Tanh, zero has no special value. We propose a continuous
smooth differentiable function:

$f(x)=G(x)-\frac{2}{x^{2}+1},$ (6)

where $G(x)$ is any existing activation function, and $x$ is the input value.
Figure 2B shows the function graph with $G(x)=1$, as used here. This function
is equivalent to:

$\sigma(log|X|);\sigma(x)=\frac{e^{x}-e^{-x}}{e^{x}+e^{-x}}.$ (7)

Similar functions were studied in the context of self-regularized non-
monotonic activation function [31]. A general conclusion obtained for
functions with non-monotonic nonlinearities at 0 is that such functions may
act as a regularizer. Therefore, we propose to use very limited regularization
if any.

(a)

(b)

Figure 2: The first figure is a histogram of the seventh dimension of the
output of the first layer of GCN. It can be seen that most values are zero or
close to zero. The figure beneath it presents SRSS with G(X)=1

Table 5 shows the Accuracy of QGCN in graph classification task with SRSS
against known activation functions such as Relu, Sigmoid, and Tanh. One can
see that using SRSS in the inner layers (i.e. in the GCN layers) improves
significantly the accuracy of the results. The accuracy of QGCN with other
non-linearity is significantly below the accuracy of existing methods.

Table 5: QGCN performance in GCT, with different activation functions (accuracy score) Activation Function | Mutagencity | NCI109 | NCI1 | Grec | Proteins | Aids
---|---|---|---|---|---|---
Relu | 55.07 | 50.91 | 52.01 | 97.29 | 74.90 | 80.00
Tanh | 57.72 | 50.09 | 50.12 | 92.09 | 69.51 | 99.72
Sigmoid | 64.17 | 52.12 | 62.09 | 90.50 | 73.54 | 99.30
SRSS | 95.57 | 93.28 | 94.81 | 100.00 | 87.23 | 100.00

The bimodal input distribution is also frequent in regular GCN. To further
explore the applicability of SRSS, beyond QGCN, we tested on vertex
classification task in GCN. [18] is currently the state-of-the-art GCN which
yields the best performance on vertex classification task on known citation
datasets such as Citeseer. They use Relu as their activation function. To
compare known activation functions and SRSS, we have repeated the experiments
in [18] for each activation function for three citation datasets: Pubmed,
Citeseer, and Cora, using the reported hyperparameters. Table 6 shows the
results for different activation functions. SRSS yields the same performance
as the currently used non-linearities. While the focus here is on GCT, SRSS
may be an important tool for other cases with a distinction between the zero
values and all other values.

Table 6: GCN performance in node classification task, with different activation functions Activation Function | Cora | Citeseer | Pubmed |
---|---|---|---|---
Relu | 90.16 | 80.11 | 87.84 |
Tanh | 88.48 | 78.91 | 88.57 |
Sigmoid | 89.86 | 76.70 | 87.02 |
SRSS | SRSS | 89.54 | 80.52 | 88.49

##  8 Discussion

Methods to compare graphs have been developed in many domains, including
chemoinformatics [19, 12], sub-graph isomorphism [42], graph classification
tasks [26] and many others. Many of these methods were kernel-based, where
properties of the graph were defined and graphs were compared based on the
similarity between graph properties. A simple example would be the frequency
of specific subgraphs. An alternative approach is to project the graph and
compare the properties of the projection. Generally, all such methods define a
distance matrix between graphs, based on a constant sized representation of
the graph. Once such a distance is defined, supervised and unsupervised
distance-based approaches can be applied to a set of graphs.

However, such approaches require a pre-definition of the features to be
compared. As such, they require adaptation to different types of graphs. In
vertex classification tasks, GCNs have been shown to obtain better accuracies
than tailored methods. We here proposed to extend the same logic to GCT. GCN
can be viewed as a projection of vertices into a real matrix whose dimensions
are the number of vertices and a constant representation dimension. Previous
extensions of GCN to graph classification have been proposed based on either
pooling methods or through hierarchical approaches. We here suggested an
alternative approach based on a quadratic layer, and have shown that combined
with a self-regularized activation function, it produced much higher accuracy
values than the state of the art methods on all tested GCT.

Instead of pre-defining the properties of graph projections to best classify
them, these properties are learned through a combination of weight multiplying
different projections of the graphs using a quadratic product. Such products
have been previously proposed in multiple contexts, but mainly knowledge
graphs. Its extension to regression problems or semi-supervised approaches is
straightforward.

The QGCN can be considered as an attention mechanism on the graph vertices,
where one layer servers as the attention and one layer as the projection.
Interestingly, the layer producing the highest accuracy is simply the input
layer (multiplied by a weight matrix that can be treated as the directions of
interest). As such, one may consider choosing an input layer optimized for
such attention.

Beyond its usage in the context of GCN, the SRSS function proposed here can
have a wide range of applications with bimodal input distributions, where it
may be more important to distinguish zero from non-zero-values than positive
from negative values. We have here shown that in QGCN, it drastically improves
performance and that it can also be used in GCN. We propose this self
regularizing function as a basic building tool, at least in the input layer
when zero and non-zero values should be separated.

## References

  * [1] Abel, R., Louzoun, Y.: Regional based query in graph active learning. arXiv preprint arXiv:1906.08541 (2019)
  * [2] Angelova, R., Weikum, G.: Graph-based text classification: learn from your neighbors. In: Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. pp. 485–492. ACM (2006)
  * [3] Aßfalg, J., Borgwardt, K.M., Kriegel, H.P.: 3dstring: a feature string kernel for 3d object classification on voxelized data. In: Proceedings of the 15th ACM international Conference on information and Knowledge Management. pp. 198–207. ACM (2006)
  * [4] Benami, I., Cohen, K., Nagar, O., Louzoun, Y.: Topological based classification of paper domains using graph convolutional networks. arXiv preprint arXiv:1904.07787 (2019)
  * [5] Bhagat, S., Cormode, G., Muthukrishnan, S.: Node classification in social networks. In: Social network data analytics, pp. 115–148. Springer (2011)
  * [6] Borgwardt, K.M., Kriegel, H.P.: Shortest-path kernels on graphs. ICDM (2005)
  * [7] Borgwardt, K.M., Ong, C.S., Schönauer, S., Vishwanathan, S., Smola, A.J., Kriegel, H.P.: Protein function prediction via graph kernels. Bioinformatics 21(suppl_1), i47–i56 (2005)
  * [8] Chen, F., Pan, S., Jiang, J., Huo, H., Long, G.: Dagcn: Dual attention graph convolutional networks. IJCNN 2019. International Joint Conference on Neural Networks. Budapest, Hungary. 14-19 July 2019 (2019)
  * [9] D.Dobson, P., J.Doig, A.: Distinguishing enzyme structures from non-enzymes without alignments. Science Direct pp. 771–783 (2003)
  * [10] Diehl, F.: Edge contraction pooling for graph neural networks. arXiv preprint arXiv:1905.10990 (2019)
  * [11] Duvenaud, D.K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., Adams, R.P.: Convolutional networks on graphs for learning molecular fingerprints. In: Advances in neural information processing systems. pp. 2224–2232 (2015)
  * [12] Gärtner, T., Flach, P., Wrobel, S.: On graph kernels: Hardness results and efficient alternatives. In: Learning theory and kernel machines, pp. 129–143. Springer (2003)
  * [13] Gaüzere, B., Brun, L., Villemin, D.: Two new graphs kernels in chemoinformatics. Pattern Recognition Letters 33(15), 2038–2047 (2012)
  * [14] Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message passing for quantum chemistry. In: Proceedings of the 34th International Conference on Machine Learning-Volume 70. pp. 1263–1272. JMLR. org (2017)
  * [15] Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 855–864. ACM (2016)
  * [16] Hamilton, W.L., Ying, R., Leskovec, J.: Representation learning on graphs: Methods and applications. arXiv preprint arXiv:1709.05584 (2017)
  * [17] Haonan, L., Huang, S.H., Ye, T., Xiuyan, G.: Graph star net for generalized multi-task learning. arXiv preprint arXiv:1906.12330v1 (2019)
  * [18] Izadi, M.R., Fang, Y., Stevenson, R., Lin, L.: Optimization of graph neural networks with natural gradient descent. arXiv preprint arXiv:2008.09624v1 (2020)
  * [19] Kashima, H., Tsuda, K., Inokuchi, A.: Kernels for graphs. Kernel methods in computational biology 39(1), 101–113 (2004)
  * [20] Kato, T., Kashima, H., Sugiyama, M.: Robust label propagation on multiple networks. IEEE Transactions on Neural Networks 20(1), 35–44 (2009)
  * [21] Kazius, J., McGuire, R., Bursi, R.: Derivation and validation of toxicophores for mutagenicity prediction. Journal of medicinal chemistry 48(1), 312–320 (2005)
  * [22] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)
  * [23] Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Applied Network Science (2020)
  * [24] Lee, J., Lee, I., Kang, J.: Self-attention graph pooling. arXiv preprint arXiv:1904.08082 (2019)
  * [25] Lei, K., Qin, M., Bai, B., Zhang, G., Yang, M.: Gcn-gan: A non-linear temporal link prediction model for weighted dynamic networks. In: IEEE INFOCOM 2019-IEEE Conference on Computer Communications. pp. 388–396. IEEE (2019)
  * [26] Li, Y., Tarlow, D., Brockschmidt, M., Zemel, R.: Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493 (2015)
  * [27] Ling, H., Gao, J., Kar, A., Chen, W., Fidler, S.: Fast interactive object annotation with curve-gcn. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 5257–5266 (2019)
  * [28] Lu, Q., Getoor, L.: Link-based classification. In: Proceedings of the 20th International Conference on Machine Learning (ICML-03). pp. 496–503 (2003)
  * [29] Luzhnica, E., Day, B., Lio, P.: Clique pooling for graph classification. RLGM, ICLR 2019 (2019)
  * [30] Ma, Y., Wang, S., Aggarwal, C.C., Tang, J.: Graph convolutional networks with eigenpooling. Association for Computing Machinery (2019)
  * [31] Misra, D., Landskape: Mish: A self regularized non-monotonic activation function. arXiv preprint arXiv:1908.08681v3 (2020)
  * [32] Naaman, R., Cohen, K., Louzoun, Y.: Edge sign prediction based on a combination of network structural topology and sign propagation. Journal of Complex Networks 7(1), 54–66 (2018)
  * [33] Nene, S., Nayar, S., Murase, H.: Columbia Object Image Library: COIL-100. Tech. rep., Department of Computer Science, Columbia University, New York (1996)
  * [34] Nguyen, D.Q., Nguyen, T.D., Phung, D.: Universal graph transformer self-attention networks. arXiv preprint arXiv:1909.11855v9 (2020)
  * [35] Pan, S., Wu, J., Zhu, X., Long, G., Zhang, C.: Task sensitive feature exploration and learning for multitask graph classification. IEEE transactions on cybernetics 47(3), 744–758 (2016)
  * [36] Pan, S., Wu, J., Zhu, X., Zhang, C., Philip, S.Y.: Joint structure feature exploration and regularization for multi-task graph classification. IEEE Transactions on Knowledge and Data Engineering 28(3), 715–728 (2015)
  * [37] Qiu, J., Chen, Q., Dong, Y., Zhang, J., Yang, H., Ding, M., Wang, K., Tang, J.: Gcc: Graph contrastive coding for graph neural network pre-training. arXiv preprint arXiv:2006.09963v3 (2020)
  * [38] Ramon, J., Gärtner, T.: Expressivity versus efficiency of graph kernels. In: First international workshop on mining graphs, trees and sequences. pp. 65–74. Citeseer (2003)
  * [39] Rosen, Y., Louzoun, Y.: Topological similarity as a proxy to content similarity. Journal of Complex Networks 4(1), 38–60 (2015)
  * [40] Shervashidze, N., Schweitzer, P., van Leeuwen, E.J., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12 (2011) pp. 2539–2561 (2011)
  * [41] Shervashidze, N., Schweitzer, P., Leeuwen, E.J.v., Mehlhorn, K., Borgwardt, K.M.: Weisfeiler-lehman graph kernels. Journal of Machine Learning Research 12(Sep), 2539–2561 (2011)
  * [42] Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics. pp. 488–495 (2009)
  * [43] Shervashidze, N., Vishwanathan, S., Petri, T.H., Mehlhorn, K., Borgwardt, K.M.: Efficient graphlet kernels for large graph comparison. Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS) pp. 488–496 (2009)
  * [44] Speriosu, M., Sudan, N., Upadhyay, S., Baldridge, J.: Twitter polarity classification with label propagation over lexical links and the follower graph. In: Proceedings of the First workshop on Unsupervised Learning in NLP. pp. 53–63. Association for Computational Linguistics (2011)
  * [45] Sun, F.Y., Hoffmann2, J., Verma, V., Tang, J.: Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. ICLR2020 (2020)
  * [46] Tang, L., Liu, H.: Leveraging social media networks for classification. Data Mining and Knowledge Discovery 23(3), 447–478 (2011)
  * [47] Wang, Y., Gemulla, R., Li, H.: On multi-relational link prediction with bilinear models. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)
  * [48] Wang, Y.G., Li, M., Ma, Z., Montufar, G., Zhuang, X., Fan, Y.: Haar graph pooling. Proceedings of the 37th international conference on machine learning (2020)
  * [49] Yanardag, P., Vishwanathan, S.: A structural smoothing framework for robust graph-comparison. Advances in Neural Information Processing Systems 28 (NIPS 2015) (2015)
  * [50] Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. In: Advances in Neural Information Processing Systems. pp. 4800–4810 (2018)
  * [51] Yuan, H., Ji, S.: Structpool: Structured graph pooling via conditional random fields. ICLR 2020 (2020)
  * [52] Zeng, J., Xie, P.: Contrastive self-supervised learning for graph classification. arXiv preprint arXiv:2009.05923v1 (2020)
  * [53] Zhang, M., Cui, Z., Neumann, M., Chen, Y.: An end-to-end deep learning architecture for graph classification. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)
  * [54] Zhang, M., Cui, Z., Neumann, M., Chen, Y.: An end-to-end deep learning architecture for graph classification. Association for the Advancement of Artificial Intelligence (2018)
  * [55] Zhang, S., Xie, L.: Improving attention mechanism in graph neural networks via cardinality preservation. arXiv preprint arXiv:1907.02204v4 (2020)
  * [56] Zhang, S., Xie, L.: Improving attention mechanism in graph neural networks via cardinality preservation. arXiv preprint arXiv:1907.02204v4 (2020)
  * [57] Zhang, Z., Bu, J., Ester, M., Zhang, J., Yao, C., Yu, Z., Wang, C.: Hierarchical graph pooling with structure learning. arXiv preprint arXiv:1911.05954 (2019)
  * [58] Zhao, Q., Wang, Y.: Learning metrics for persistence-based summaries and applications for graph classification. arXiv preprint arXiv:1904.12189v2 (2019)
  * [59] Zhao, W., Xu, C., Cui, Z., Zhang, T., Jiang, J., Zhang, Z., Yang, J.: When work matters: Transforming classical network structures to graph cnn. arXiv preprint arXiv:1807.02653v1 (2018)