Graph Machine Learning

​​Monday Theory: Logical Expressiveness of Hypergraph GNNs A prominent spotlight ICLR'20 paper by Barcelo et al proved several important expressiveness boundaries for message passing GNNs on graphs with normal binary edges, ie, an edge connects two nodes. Using a well-known mapping of classifying First Order Logic formulae to the WL-test, the authors show that Aggregate-Combine GNNs are bounded by ALCQ - a common Description Logic fragment of FOL. And Aggregate-Combine-Readout (GNNs with global pooling) are bounded by FOC-2 subset for FOL, i.e., First Order Logic with counting quantifiers and at most 2 variables. A new anonymous ICLR'22 submission extends this framework to hypergraphs, ie, the graphs where (hyper)edges are constructed from B > 2 nodes. This time, the authors resort to higher-order k-WL tests and find a natural connection between k-WL and expressiveness of hypergraph networks. Three cool contributions: 1. Hypergraphs with B-ary hyperedges are bounded by FOC-B subset of FOL. That is, a logical formula can have up to B variables now. 2. The framework includes several relational architetures such as Neural Logic Machines, Deep Sets, Transformers, and GNNs 3. The authors estimate theoretical bounds on min depth and arity of hypergraph architectures for common GRL tasks. For instance, identifying bipartiteness of n-nodes graph requires log(n) layers of 3-ary GNNs (or 2-WL kernels) Experiments were conducted on rather toy graphs of 10-80 nodes which is explained by the need to train hypergraph nets on all possible permutations of nodes in hyperedges (and this at the moment has bad scaling properties). Still, most of the hypotheses are confirmed by the experiments, so check out the full paper if you're into logic+GNN studies!

WSDM2022 Challenge from DGL Team A really nice competition by DGL on temporal link prediction on two large-scale graph datasets. The dates are Oct 15 - Jan 20. Prize pool: $3500 + WSDM registration.

Fresh picks from ArXiv This week on ArXiv: GNNs for imbalanced case, relationships behind KGs, and software optimization of GNNs 💻 If I forgot to mention your paper, please shoot me a message and I will update the post. GNNs * Distance-wise Prototypical Graph Neural Network in Node Imbalance Classification with Tyler Derr * Multi-view Contrastive Graph Clustering NeurIPS 2021 * Learning to Learn Graph Topologies NeurIPS 2021 Studies * What is Learned in Knowledge Graph Embeddings? * Understanding GNN Computational Graph: A Coordinated Computation, IO, and Memory Perspective

Probabilistic Symmetries and Invariant Neural Networks A recent survey on neural networks that are invariant/equivariant under group actions (which GNNs are a special class of). Among others, it does a good job of significant works of 20th century that laid the foundation for invariant neural networks.

MICCAI 2021 graph papers Here is a guest post by Mahsa Ghorbani about applications of graphs to medical images. A few weeks ago, International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI) published the accepted list of papers and their reviews. About 20 of the papers are graph related which shows the impact of graph-based methods in medical applications. Here are two examples of papers: - GKD: Semi-supervised Graph Knowledge Distillation for Graph-Independent Inference Recently, graphs neural networks show great success in analyzing multi-modal medical data (such as demographic and imaging data) associated with a group of patients regarding the disease prediction problem. However, the conventional methods exhibit poor performance when the graph modality is not available during the inference time. GKD proposes a novel semi-supervised method inspired by the knowledge distillation framework to face this issue. The teacher block distills all the available information in training data and then transfers it to the student network trained with input features, not the filtered ones. Therefore, the student works well on the test data without the graph between them. GKD also utilizes a modified label-propagation algorithm in the teacher block to keep a balance between neighborhood features and node features. - Early Detection of Liver Fibrosis Using Graph Convolutional Networks Fibrosis refers to the deposition of collagen in tissue which can lead to organ dysfunction and even to organ failure. Typically, histochemical stains are being used to visualize collagen. Detection of early onset of fibrosis is critical to detecting long-term damage to identify potential loss of organ function. This paper uses a collagen segmentation method to extract a collagen map from an input histopathological image and then decompose it into a set of tiles. Then cluster the tiles and classify the clusters based on a few samples in them (visually). The tiles clustered as dense collagen are used as the centers, and each tile will be connected to the closest center (Voronoi tessellation). After a set of graph convolutional layers, an attention mechanism is used to aggregate the tile features and detect the fibrosis stage of the input image.

Exploring Complexity: How Graph Data Science is pushing new boundaries: panel A panel on the graph data science is available for registration online. See their message below: 🔎 Exploring complexity is a challenge for all of us. The abundance of data still does not help us to make better decisions, we need to unbundle it, understand the context and find the latent relationships. 📣 Missioned to make this process simplified, as OpenCredo, we will be hosting a panel discussion with the leaders on Graph Data Science space to discuss the impacts of Graphs. Whether you are new to this space or listen to inspiring leaders of the community, this is a great opportunity! - Dan McCreary, Distinguished engineer at Optum (he has great blog posts at [https://lnkd.in/eUFZMNh3]) - Paco Nathan, Evil Mad Scientists, a contributor to AI/ML/Graph space (some of his amazing work at [https://derwen.ai/report] - Alessandro Negro, Chief Scientist at GraphAware (recently published Graph Powered Machine Learning [https://lnkd.in/eQycHze2]) 💫 Our CTO/CEO Nicki Watt will be hosting the panel, and we are excited to have a great insight into how Graph is pushing the boundaries.

iGDL 2021: Israeli Geometric Deep Learning Workshop A strong and packed workshop on sets, 3d representation, meshes, and graphs organized by Israeli GDL community.

Fresh picks from ArXiv This week on ArXiv: class-dependent generative models, label-feature propagations, and space-time GNNs 🚀 If I forgot to mention your paper, please shoot me a message and I will update the post. Biology * Pre-training Molecular Graph Representation with 3D Geometry * Molecular Graph Generation via Geometric Scattering * Iterative Refinement Graph Neural Network for Antibody Sequence-Structure Co-design with Regina Barzilay and Tommi Jaakkola * CCGG: A Deep Autoregressive Model for Class-Conditional Graph Generation GNNs * Graph Neural Networks with Learnable Structural and Positional Representations with Yoshua Bengio and Xavier Bresson * ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network with Philip S. Yu * Training Stable Graph Neural Networks Through Constrained Learning with Alejandro Ribeiro * Space-Time Graph Neural Networks with Alejandro Ribeiro * Equivariant Subgraph Aggregation Networks with Michael M. Bronstein and Haggai Maron KG * A Survey on State-of-the-art Techniques for Knowledge Graphs Construction and Challenges ahead LP * Label-Wise Message Passing Graph Neural Network on Heterophilic Graphs * Why Propagate Alone? Parallel Use of Labels and Features on Graphs * Label Propagation across Graphs: Node Classification using Graph Neural Tangent Kernels

Monday Theory: Reconstruction Conjecture + GRL🏗 A few months back in this channel we discussed the Reconstruction Conjecture as one of the grand challenges still open in graph theory. In simple words, the conjecture says that two graphs are the same iff their decks (one-vertex-deleted subgraphs) are the same. Does it have something to do with GNNs, you ask? It certainly has! A recently accepted NeurIPS'21 paper Reconstruction for Powerful Graph Representations is dedicated exactly to this connection. We invited the first authors, Leonardo Cotta and Christopher Morris, to explain below the main intuition and experimental results of this wonderful work. Although GNNs are extremely popular right now, they have clear limitations. Their expressive power is limited by the 1-Weisfeiler-Leman algorithm, a simple heuristic for the graph isomorphism problem. For example, GNNs cannot approximate graph properties such as diameter, radius, girth, and subgraph counts, inspiring architectures based on the more powerful k-dimensional Weisfeiler-Leman algorithm (k-WL). However, such architectures do not scale to large graphs. Hence, it remains an open challenge to design more expressive architectures that scale to large graphs while generalizing to unseen areas. In our work, we first show how the k-reconstruction of graphs—reconstruction from induced k-vertex subgraphs—induces a natural class of expressive GRL architectures for supervised learning with graphs, denoted k-Reconstruction Neural Networks. We then show how several existing works have their expressive power limited by k-reconstruction. Further, we show how the reconstruction conjecture’s insights lead to a provably most-expressive representation of graphs. To make our models scalable, we propose k-Reconstruction GNNs, a general tool for boosting the expressive power and performance of GNNs with graph reconstruction. Theoretically, we characterize their expressive power showing that k-Reconstruction GNNs can distinguish graph classes that the 1-WL and 2-WL cannot, such as cycle graphs and strongly regular graphs, respectively. Further, to explain gains in real-world tasks, we show how reconstruction can act as a lower-variance estimator of the risk when the graph-generating distribution is invariant to vertex removals. Empirically, we show that reconstruction enhances GNNs’ expressive power, making them solve multiple synthetic graph property tasks in the literature not solvable by the original GNN. On real-world datasets, we show that the increase in expressive power coupled with the lower-variance risk estimator boosts GNN’s performance up to 25%. Our theoretical and empirical results combined make another important connection between graph theory and GRL.

TorchDrug Workshop Tomorrow, October 14th, Jian Tang (Mila) will conduct a workshop “TorchDrug: A powerful and flexible machine learning platform for drug discovery.” presenting a recently released new drug discovery library, TorchDrug] (already 450+ stars on GitHub). TorchDrug employs GNNs, KG embedding algorithms, custom CUDA kernels and all fresh advancements of Geometric DL. Participation is free, the workshop starts at 11am EDT (5pm EU time)

ICLR 2022 Submissions Attached is the list of all submissions for ICLR 2022. In total there are 3712 submissions, while there are ~270 graph papers. About 40% are resubmissions from previous conferences and 75% have first author as student.

Graph Neural Network for Lagrangian Simulation: video A presentation by Zijie Li (CMU) on modeling fluid dynamics with GNNs.