Journal Reviews

Dated Jan 11, 2022; last modified on Sun, 12 Feb 2023

Given network-structured data, predict whether a link exists between two nodes.

General types of prediction tasks on graphs: graph-level (e.g. will a molecule bind to a receptor implicated in a disease?), node-level (e.g. what is the identity of each node?), and edge-level (e.g. does this edge exist; what value does it have?).

Applications include: predicting drug-drug interactions (common in treating patients with complex/co-existing diseases) as they may cause changes in the drugs' pharmacological activity .

Is this why doctors ask if you have any known allergens, or have reacted negatively to some prior medication?

Traditional approaches embed (usually via hashing) each node into a low-dimensional space, and explicitly compute similarity. There’s a tradeoff between the inaccuracies of randomized hashing, and the efficiency/resource cost of learning to hash via GNNs . propose #GNNs, which uses randomized hashing for message passing , and captures high-order proximity in the GNNs framework. #GNNs’s is scalable, faster than learning-based algorithms, comparably as accurate as learning-based algorithms, more accurate than the randomized algorithm.

Previous methods for predicting Drug-Drug Interactions (DDI) exploit the inter-view drug molecular structure and ignore the drug’s intra-view interaction relationship. ’s MIRACLE treats the DDI network as a multi-view graph where each node is a drug molecular graph instance. In MIRACLE’s learning stage, they use GCN to encode DDI relationships, and use a bond-aware attentive message propagating method to capture drug molecular structure information. They also propose a learning component to balance and integrate the multi-view information.

A toy example of the multi-view graph. Credits: Wang2021
A toy example of the multi-view graph. Credits: Wang2021

Adapting GNNs to more complex graph structures (e.g. multi-graphs, hypergraphs, hyper-nodes, hierarchical graphs) is mostly about defining how information is passed and updated by new graph attributes.

Previous works predict unobserved links using GNNs to learn node embeddings upon pair-wise relations. However, these models are not performant when there are few observed links, as they only focus on the smoothness of node representations on pair-wise relations. learn a method to generate hypergraphs whose hyperedges are hierarchical and follow a power-law distribution. Their hypergraph neural network (HNN) makes node embeddings smooth on hyper-edges outperform baselines, especially when there are few observed links.

The term “hierarchical edge” seems equivalent to “directed edge”.

Previous representation learning methods for heterogenous networks obtain a static vector representation for a node in a way that is agnostic to the downstream application. brings together structural information from the entire graph, and learns deep representations of higher-order relations in arbitrary context subgraphs. Unlike previous methods that aggregate information from direct neighbors or semantic neighbors connected via pre-defined metapaths, learns the composition of different metapaths that characterize the context for a specific task. The proposed model outperforms several baselines for the link prediction task.

set out to predict the value of a community formed by closely connected users in social networks, as such information is valuable to social e-commerce platforms. They use a novel masked propagation mechanism to model peer influence, capture critical community structures, and model inter-community connections by distinguishing intra-community edges from inter-community edges. Their method outperforms baselines.

Social e-commerce platforms facilitate group buying (e.g. Pinduoduo, Groupon) or promote customer referrals (e.g. Beidian, Yunji).

is a Chinese company whose platform connects producers (most notably farmers) and distributors directly to consumers. Looks like a pretty nifty platform. I wonder if it can work in Kenya where a large number of people practice subsistence farming.

China’s social e-commerce space is more active than that of the west. Beidian hopes to upend Pinduoduo by focusing on product authenticity - an area that Pinduoduo has a poor reputation at. However, sometimes the social aspect can veer too far into pyramid selling territory, which is banned in China; Yunji was once fined for pyramid selling and had to revamp its marketing strategy.

Glossary

Graph Neural Networks (GNNs)
Neural networks that accept a graph as input, with information loaded into its nodes, edges and global context, and progressively transform these embeddings without changing the connectivity of the input graph.
Heterogeneous Network
In computer networking, a heterogeneous network is a network connecting devices that have different operating systems and protocols, e.g. a network that has Windows, Linux and macOS computers.
Hypergraph
A generalization of a graph in which an edge can join any number of vertices. Such edges are called hyperedges.
Message Passing
To make more sophisticated predictions, neighboring nodes or edges exchange information and influence each other's updated embeddings.
Representation Learning / Feature Learning
A set of techniques for automatically discovering the representations needed for feature detection or classification from raw data. Replaces manual feature engineering. Allows a machine to both learn the features and use them to perform a specific task.

References

  1. Hashing-Accelerated Graph Neural Networks for Link Prediction. Wei Wu; Bin Li; Chuan Luo; Wolfgang Nejdl. The Web Conference, Proceedings of 2021, pp. 2910-2920. doi.org . scholar.google.com .
  2. Multi-view Graph Contrastive Representation Learning for Drug-Drug Interaction Prediction. Wang, Yingheng; Yaosen Min; Xin Chen; Ji Wu. The Web Conference, 2021, pp. 2921-2933. doi.org . scholar.google.com .
  3. A Gentle Introduction to Graph Neural Networks. Benjamin Sanchez-Lengeling; Emily Reif; Adam Pearce; Alexander B. Wiltschko. distill.pub . Accessed Jan 11, 2022.
  4. Multi-level Hyperedge Distillation for Social Linking Prediction on Sparsely Observed Networks. Sun, Xiangguo; Hongzhi Yin; Bo Liu; Hongxu Chen; Qing Meng; Wang Han; Jiuxin Cao. The Web Conference, 2021, pp. 2934-2945.. doi.org . scholar.google.com .
  5. Hypergraph - Wikipedia. en.wikipedia.org . Accessed Jan 13, 2022.
  6. Self-Supervised Learning of Contextual Embeddings for Link Prediction in Heterogeneous Networks. Wang, Ping; Khushbu Agarwal; Colby Ham; Sutanay Choudhury; Chandan K. Reddy. The Web Conference, 2021, pp. 2946-2957. doi.org . scholar.google.com .
  7. Feature Learning - Wikipedia. en.wikipedia.org . Accessed Jan 15, 2022.
  8. Heterogeneous Network - Wikipedia. en.wikipedia.org . Accessed Jan 15, 2022.
  9. Community Value Prediction in Social E-commerce. Zhang, Guozhen; Yong Li; Yuan Yuan; Fengli Xu; Hancheng Cao; Yujian Xu; Depeng Jin. The Web Conference, 2021, pp. 2958-2967. doi.org . scholar.google.com .
  10. Pinduoduo | World's Largest Agri-Focused Tech Platform. stories.pinduoduo-global.com . en.wikipedia.org . Accessed Jan 15, 2022.
  11. Social selling startup Beidian raises RMB 860 million, challenges Pinduoduo ยท TechNode. Jill Shen. technode.com . May 10, 2019. Accessed Jan 15, 2022.
  12. Yunji, a startup that enables social commerce via WeChat, files for $200M US IPO | TechCrunch. Rita Liao. techcrunch.com . Mar 25, 2019. Accessed Jan 15, 2022.