2nd workshop on Graphs and more Complex structures for Learning and Reasoning

Relationships Between Higher-order Structures and Graph Representation Learning

In this talk, I will describe interesting relationships between graph representation learning and higher-order graph structures. We will see how higher-order structures can help graph neural networks perform an out-of-distribution graph classification task by being counterfactually invariant to graph sizes (which also connects to graph representation learning to graphons). We also see how higher-order structures combined with energy-based models can give graph representations the ability to predict hyperedge properties from dyadic graphs. Finally, we connect the reconstruction conjecture (which conjectures that graphs are determined uniquely by their subgraphs) to a different way to build graph representations for graph classification that can improve accuracy on graph classification tasks.

Discovery and predictions for molecules and crystalline materials using graph-based deep learning models

In recent years, deep learning models lead to significant progress in the field of chemical, biological, and material science community, to solve fundamental domain-specific problems. One of such fundamental problems in chemistry is to discover new plausible drugs, which leads to designing novel molecules with specific properties and it is inherently a time-consuming process. Recent advances in deep generative models lead to significant progress in this direction and aids to make the process very fast. Similarly, rapid and accurate prediction of different properties of crystalline materials is a challenging task and has lots of interest to the materials science community since it is imperative for finding new functional materials. However, there are major challenges like scarcity of tagged data, DFT error bias in existing models, and lack of interpretability and algorithmic transparency, which need to be addressed.

Graph-based representations are a more natural data structure to represent relational and structural information in molecules and crystals and hence we can explore the developments of graph neural networks (GNNs). Chemical graphs are a special category of graphs, where we have 3D atomic structure along with different bond types (single bonds, double and triple bonds), bond distances, atomic chemical properties, periodicity, etc. Incorporating all these structural and feature informations into GNNs is a challenging task.

In this talk, we will discuss how to leverage the power of deep learning framework to learn a robust representation of molecules and crystals, which will be further used for downstream tasks like new molecule generation or crystal property prediction.

Principled Simplicial Neural Networks for Trajectory Prediction

We consider the construction of neural network architectures for data on simplicial complexes. In studying maps on the chain complex of a simplicial complex, we define three desirable properties of a simplicial neural network architecture: namely, permutation equivariance, orientation equivariance, and simplicial awareness. The first two properties respectively account for the fact that the node indexing and the simplex orientations are arbitrary. The last property encodes the desirable feature that the output of the neural network depends on the entire simplicial complex and not on a subset of its dimensions. Based on these properties, we propose a simple convolutional architecture, rooted in tools from algebraic topology, for the problem of trajectory prediction, and show that it obeys all three of these properties when an odd, nonlinear activation function is used. We then demonstrate the effectiveness of this architecture in extrapolating trajectories on synthetic and real datasets, with particular emphasis on the gains in generalizability to unseen trajectories.

Nonbacktracking Eigenvector Method for Hypergraph Community Detection

The hypergraph community detection problem asks us to find groups of related or similar entities in hypergraph data. While there are many approaches to this problem, this talk will focus on a spectral method that utilizes information from the eigenvectors of the nonbacktracking or Hashimoto matrix. The Hashimoto operator can be shown to be related to belief-propagation for statistical inference, and using this relationship we obtain a performant hypergraph community detection algorithm with well-understood regions of success and failure for the hypergraph stochastic block model. The talk will additionally pose some conjectures on the fundamental limits of community detection in hypergraphs.

Presentations for long papers.

Lunch Break.

Scaling Graph Representation Learning Algorithms in an Implementation Agnostic Fashion

Joint work with Jionqian Liang (Google Brain), S. Gurukar (OSU) and Yuntian He (OSU)

Recently there has been a surge of interest in designing graph embedding methods. Few, if any, can scale to a large-sized graph with millions of nodes due to both computational complexity and memory requirements. In this talk, I will present an approach to redress this limitation by introducing the MultI-Level Embedding (MILE) framework – a generic methodology allowing con-temporary graph embedding methods to scale to large graphs. MILE repeatedly coarsens the graph into smaller ones using a hybrid matching technique to maintain the backbone structure of the graph. It then applies existing embedding methods on the coarsest graph and refines the embeddings to the original graph through a graph convolution neural network that it learns. I will then describe an extension to MILE in a distributed setting (DistMILE) to further improve the scalability of graph embedding. DistMILE leverages a novel shared-memory parallel algorithm for graph coarsening and a distributed training paradigm for embedding refinement. With the advantage of high-performance computing techniques, Dist-MILE can smoothly scale different base embedding methods over large networks.

The proposed MILE and Dist-MILE frameworks are agnostic to the underlying graph embedding techniques and can be applied to many existing graph embedding methods without modifying them.

Experimental results on five large-scale datasets demonstrate that MILE significantly boosts the speed (order of magnitude) of graph embedding while generating embeddings of better quality, for the task of node classification. MILE can comfortably scale to a graph with 9 million nodes and 40 million edges, on which existing methods run out of memory or take too long to compute on a modern workstation. Our experiments demonstrate that DistMILE learns representations of similar quality with respect to other baselines while reducing the time of learning embeddings even further (up to 40 x speedup over MILE).

Improving the expressive power of graph neural networks: recursion and eigenspaces

Joint work with Derek Lim, Behrooz Tahmasebi, Joshua Robinson, Lingxiao Zhao, Haggai Maron, Tess Smidt and Suvrit Sra.

“Standard” graph neural networks are known to have limitations in their expressive power - for instance, they fail to encode the presence of structural motifs. Various directions have been explored to increase this expressive power, albeit often at a relatively high computational cost. In this talk, I will discuss new directions for encoding important information and equivariances related to graphs. First, when applied appropriately, the idea of recursion can be surprisingly powerful in allowing to represent structural information. Second, we will look at graphs from a spectral perspective, and at neural networks that use spectral information. Particularly useful are the eigenvectors of the graph Laplacian. But they actually encode subspaces and encoding these demands specific invariances in the model. We explore models with such invariances, their expressive power, and practical utility.

Learning/Reasoning with complex networks: A multidisciplinary challenge

Moderator: Prof. Ginestra Bianconi

Members: TBA

Poster session for short papers / extended abstracts