Link Prediction
Given network-structured data, predict whether a link exists between two nodes.
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.
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
- 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 .
- 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 .
- A Gentle Introduction to Graph Neural Networks. Benjamin Sanchez-Lengeling; Emily Reif; Adam Pearce; Alexander B. Wiltschko. distill.pub . Accessed Jan 11, 2022.
- 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 .
- Hypergraph - Wikipedia. en.wikipedia.org . Accessed Jan 13, 2022.
- 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 .
- Feature Learning - Wikipedia. en.wikipedia.org . Accessed Jan 15, 2022.
- Heterogeneous Network - Wikipedia. en.wikipedia.org . Accessed Jan 15, 2022.
- 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 .
- Pinduoduo | World's Largest Agri-Focused Tech Platform. stories.pinduoduo-global.com . en.wikipedia.org . Accessed Jan 15, 2022.
- Social selling startup Beidian raises RMB 860 million, challenges Pinduoduo ยท TechNode. Jill Shen. technode.com . May 10, 2019. Accessed Jan 15, 2022.
- 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.
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?).