summaries: This work studied the task of detecting online drug trafficking using social media data. In particular, the authors proposed to use graph convolutional networks to model various types of entities in social media and the relations between them. Also, a meta-learning algorithm is used for the model optimization.

summaries: The paper proposes a novel model MetaHG to automatically detect illicit drug traffickers on social media. It firstly builds a heterogeneous graph based on post content and relational structure information on social media to characterize the drug trafficking system. Then it integrates graph structure learning and relational-based GCN to learn robust node embedding on HG. Afterwards, it leverages meta-learning and knowledge distillation to optimize model parameters and further to detect drug traffickers on social media. Finally, it conducts extensive experiments to validate the effectiveness of the framework.

summaries: This paper presents a novel heterogeneous graph learning model for automatically detecting illicit drug trafﬁckers on Instagram. The proposed model addresses two challenges: 1) sparse graph structure, and 2) limited labeled samples for model training. The authors also collected a large social media dataset from Instagram and conducted a lot of experiments to evaluate the proposed model.

summaries: This paper propose a novel framework MetaHG based on R-GCN for illicit drug trafficker detection on social media. A series of methods including meta learning(MAML), self-supervised learning(AS-SSL) and knowledge distillation(KD) are used to MetaHG, and obtain better metrics than traditional models with few labeled samples. In addition, the paper also creates a new dataset from Instagram for the task.

summaries: Summary:  The authors propose a model to detect drug-trafficker profiles on Instagram. The model consists of many steps and phases, but in short: they create a heterogeneous graph from users, keywords, and posts, and in addition to the regular cross-entropy loss they propose to add multiple regularizer terms extracted from several stages of their algorithm (i.e., a term to build the graph, a term to learn the node representations, and a term to distill the knowledge from an out-of-domain model).  To evaluate their model, the authors created a dataset and compared their model with many baselines and their combinations. They also reported several experiments, including user visualization and a case study.

abstractText: Driven by the considerable profits, the crime of drug trafficking (a.k.a. illicit drug trading) has co-evolved with modern technologies, e.g., social media such as Instagram has become a popular platform for marketing and selling illicit drugs. The activities of online drug trafficking are nimble and resilient, which call for novel techniques to effectively detect, disrupt, and dismantle illicit drug trades. In this paper, we propose a holistic framework named MetaHG to automatically detect illicit drug traffickers on social media (i.e., Instagram), by tackling the following two new challenges: (1) different from existing works which merely focus on analyzing post content, MetaHG is capable of jointly modeling multimodal content and relational structured information on social media for illicit drug trafficker detection; (2) in addition, through the proposed meta-learning technique, MetaHG addresses the issue of requiring sufficient data for model training. More specifically, in our proposed MetaHG, we first build a heterogeneous graph (HG) to comprehensively characterize the complex ecosystem of drug trafficking on social media. Then, we employ a relation-based graph convolutional neural network to learn node (i.e., user) representations over the built HG, in which we introduce graph structure refinement to compensate the sparse connection among entities in the HG for more robust node representation learning. Afterwards, we propose a meta-learning algorithm for model optimization. A self-supervised module and a knowledge distillation module are further designed to exploit unlabeled data for improving the model. Extensive experiments based on the real-world data collected from Instagram demonstrate that the proposed MetaHG outperforms state-of-the-art methods.

authors:
Antreas Antoniou
Harrison Edwards
Amos Storkey

title: How to train your maml

venue: In ICLR,

authors:
Roderic Broadhurst
Matthew Ball
Harshit Trivedi

title: Fentanyl availability on darknet markets

venue: Trends and issues in crime and criminal justice,

authors:
Julian Broséus
Damien Rhumorbarbe
Caroline Mireault
Vincent Ouellette
Frank Crispino
David Décary-Hétu

title: Studying illicit drug trafficking on darknet markets: structure and organisation from a canadian perspective

venue: Forensic Science International,

authors:
Jiaxin Chen
Li-Ming Zhan
Xiao-Ming Wu
Fu-lai Chung

title: Variational metric scaling for metric-based meta-learning

venue: In AAAI,

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova. Bert

title: Pre-training of deep bidirectional transformers for language understanding

venue: arXiv preprint arXiv:1810.04805,

authors:
Yuxiao Dong
Nitesh V Chawla
Ananthram Swami

title: metapath2vec: Scalable representation learning for heterogeneous networks

venue: In KDD,

authors:
Alireza Fallah
Aryan Mokhtari
Asuman Ozdaglar

title: On the convergence theory of gradientbased model-agnostic meta-learning algorithms

venue: In AISTATS,

authors:
Yujie Fan
Yanfang Ye
Qian Peng
Jianfei Zhang
Yiming Zhang
Xusheng Xiao
Chuan Shi
Qi Xiong
Fudong Shao
Liang Zhao

title: Metagraph aggregated heterogeneous graph neural network for illicit traded product identification in underground market

venue: In ICDM,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In ICML,

authors:
Chelsea Finn
Kelvin Xu
Sergey Levine

title: Probabilistic model-agnostic meta-learning

venue: In NeurIPS,

authors:
William L Hamilton
Rex Ying
Jure Leskovec

title: Inductive representation learning on large graphs

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

authors:
Wei Jin
Tyler Derr
Haochen Liu
Yiqi Wang
Suhang Wang
Zitao Liu
Jiliang Tang

title: Self-supervised learning on graphs: Deep insights and new direction

authors:
Wei Jin
Yao Ma
Xiaorui Liu
Xianfeng Tang
Suhang Wang
Jiliang Tang

title: Graph structure learning for robust graph neural networks

authors:
Thomas N Kipf
Max Welling

title: Semi-supervised classification with graph convolutional networks

authors:
Gregory Koch
Richard Zemel
Ruslan Salakhutdinov

title: Siamese neural networks for one-shot image recognition

authors:
Yoonho Lee
Seungjin Choi

title: Gradient-based meta-learning with learned layerwise metric and subspace

authors:
Jiawei Li
Qing Xu
Neal Shah
Tim K Mackey

title: A machine learning approach for the detection and characterization of illicit drug dealers on instagram: model evaluation study

venue: Journal of medical Internet research,

authors:
Tim Mackey
Janani Kalyanam
Josh Klugman
Ella Kuzmenko
Rashmi Gupta

title: Solution to detect, classify, and report illicit online marketing and sales of controlled substances via twitter: using machine learning and web forensics to combat digital opioid access

venue: Journal of Medical Internet Research,

authors:
Tim K Mackey
Janani Kalyanam

title: Detection of illicit online sales of fentanyls via twitter

authors:
Tim K Mackey
Janani Kalyanam
Takeo Katsuki
Gert Lanckriet

title: Twitter-based detection of illegal online sale of prescription opioid

venue: American Journal of Public Health,

authors:
Qi Mao
Li Wang
Steve Goodison
Yijun Sun

title: Dimensionality reduction via graph structure learning

authors:
Tu Dinh Nguyen
Dinh Phung

title: Unsupervised universal self-attention network for graph classification

venue: arXiv preprint arXiv:1909.11855,

authors:
Alex Nichol
Joshua Achiam
John Schulman

title: On first-order meta-learning algorithms

venue: arXiv preprint arXiv:1803.02999,

authors:
Boris N Oreshkin
Pau Rodriguez
Alexandre Lacoste

title: Tadam: task dependent adaptive metric for improved few-shot learning

authors:
Bryan Perozzi
Rami Al-Rfou
Steven Skiena

title: Deepwalk: Online learning of social representations

authors:
Yiyue Qian
Yiming Zhang
Yanfang Ye
Chuxu Zhang

title: Adapting meta knowledge with heterogeneous information network for covid-19 themed malicious repository detection

venue: In IJCAI,

title: Em algorithms for pca and spca

authors:
Michael Schlichtkrull
Thomas N Kipf
Peter Bloem
Rianne Van Den Berg
Ivan Titov
Max Welling

title: Modeling relational data with graph convolutional networks

venue: In ESWC,

authors:
Chao Shang
Yun Tang
Jing Huang
Jinbo Bi
Xiaodong He
Bowen Zhou

title: End-to-end structure-aware convolutional networks for knowledge base completion

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

authors:
Jake Snell
Kevin Swersky
Richard Zemel

title: Prototypical networks for few-shot learning

title: A general regression neural network

venue: IEEE Transactions on Neural Networks,

authors:
Pinzhuo Tian
Zhangkai Wu
Lei Qi
Lei Wang
Yinghuan Shi
Yang Gao

title: Differentiable meta-learning model for few-shot semantic segmentation

authors:
Petar Veličković
Guillem Cucurull
Arantxa Casanova
Adriana Romero
Pietro Lio
Yoshua Bengio

title: Graph attention networks

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
Daan Wierstra

title: Matching networks for one shot learning

title: A growing crisis: Drug overdose deaths in america, 2021

title: instagram statistics and facts for 2021

authors:
Xiao Wang
Houye Ji
Chuan Shi
Bai Wang
Yanfang Ye
Peng Cui
Philip S Yu

title: Heterogeneous graph attention

authors:
Chengfeng Xu
Pengpeng Zhao
Yanchi Liu
Victor S Sheng
Jiajie Xu
Fuzhen Zhuang
Junhua Fang
Xiaofang Zhou

title: Graph contextualized self-attention network for session-based recommendation

authors:
Chuxu Zhang
Dongjin Song
Chao Huang
Ananthram Swami
Nitesh V Chawla

title: Heterogeneous graph neural network

authors:
Yiming Zhang
Yujie Fan
Wei Song
Shifu Hou
Yanfang Ye
Xin Li
Liang Zhao
Chuan Shi
Jiabin Wang
Qi Xiong

title: Your style your identity: Leveraging writing and photography styles for drug trafficker identification in darknet markets over attributed heterogeneous information

authors:
Yiming Zhang
Yiyue Qian
Yujie Fan
Yanfang Ye
Xin Li
Qi Xiong
Fudong Shao

title: dstyle-gan: Generative adversarial network based on writing and photography styles for drug identification in darknet markets

venue: In ACSAC,

authors:
Panpan Zheng
Shuhan Yuan
Xintao Wu
Yubao Wu

title: Identifying hidden buyers in darknet markets via dirichlet hawkes process

venue: arXiv preprint arXiv:1911.04620,

heading: 1 Introduction

text:
As the market of illicit drugs (e.g., heroin, synthetic opioids such as Fentanyl) is considerably lucrative, the crime of drug trafficking (a.k.a. illicit drug trading) has never stopped but co-evolved with the advance of modern technologies, e.g., the practice of illicit drug trade has transformed from the physical world to online platforms. It has been shown that major social media platforms, including Instagram, Twitter, Snapchat, and Facebook, have become direct-to-consumer marketing mediums for illicit drug traffickers [25]. As illustrated in Figure 1, due to the convenience and popularity, drug traffickers can easily create accounts on these platforms to advertise and sell drugs by posting codewords (e.g., street name) and images of drugs that are in stock (shown in Figure 1.(a)); they can also post their drug sale websites and utilize social media platforms for promotion (shown in Figure 1.(b)). Buyers can access illicit drugs and trade with vendors easily through these social media platforms.
∗Corresponding authors.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Illegal drug trading has turn into a global concern due to its catastrophic consequences on society, from violent crimes to public health (e.g., over 87,000 people died from drug overdose in 2020 in the U.S. and it broke the record with a 20% increase in a year [41]).
Despite the persistent effort by law enforcement agencies, due to the considerable profits, activities of online drug trafficking are nimble and resilient: as shown in Figure 1.(c), to avoid being banned, skilled drug traffickers (e.g., with 1,002 followers, and 118 followings) rarely post drug description or images on social media, but instead, they advertise drugs implicitly using the slang (e.g., using “KET” to refer ketamine) and leave encrypted chat tool contact information (e.g., Kik Messenger) through their comments
to other users’ posts. To combat online drug trafficking, there is an imminent need to develop novel techniques for effective detection of drug traffickers on social media and thus enable law enforcement for proactive interventions to disrupt and dismantle illicit drug trades.
To tackle the above problem, there have been many research efforts on the investigation of online drug trafficking. Some existing works focus on analyzing the drug trafficking activities on darknet markets [46, 47, 9], while some methods have been proposed for detecting illicit drug trading activities on social media [20, 21, 22]. Most of these works usually rely on a single type of content feature (e.g., text or image) while ignoring the structured relationship information among entities on social media. For instance, Instagram monitors drug traffickers simply by filtering drug-related keyword hashtags (e.g., weed4sale) [14]. Unfortunately, as illustrated in Figure 1.(c), drug traffickers may always invent new tactics to evade detection. Those methods that fail to consider multi-modal features (e.g., both text and image) and the structural relationships among entities (e.g., users and posts) could limit the effectiveness of detecting drug trafficking activities. Additionally, most recent works [22, 23, 20] require sufficient labeled samples to train the model for the detection of drug trafficking. For example, Mackey et al. [23] collected almost 612,000 posts on Twitter and only found 1,778 drug trafficking-related posts. Obtaining labeled samples on social media is always expensive, and existing models may suffer from the constraint of few labeled data to detect drug traffickers.
To address the above challenges, in this paper, we propose a holistic framework named MetaHG (as shown in Figure 3) to automatically detect illicit drug traffickers on social media (i.e., using Instagram as a showcase). First, to overcome the shortcomings of merely analyzing a single type of content information (e.g., text or image), we propose to consider the multi-modal content features (i.e., both text and image) and introduce a heterogeneous graph (HG) to model the relationships among three types of entities (i.e., user, post, and keyword). The constructed HG is able to comprehensively characterize the complex ecosystem of drug trafficking on social media. And then we exploit relationbased graph convolutional neural networks (R-GCNs) [32] to fuse both relational information among entities and content features to obtain initial node embeddings over the built HG. Due to spare relational connections among some entities, we further introduce graph structure refinement (GSR) [24, 16] to learn more robust node representations on the HG. Furthermore, to address the few labeled data issue, we propose a meta-learning framework to transfer knowledge from training tasks and effectively adapt them to testing tasks (e.g., new types of drug traffickers with few labeled samples). More specifically, to exploit unlabeled information for better performance, our proposed model consists of two additional modules: an embedding similarity-based self-supervised learning module to augment R-GCNs for node representation refinement, and a knowledge distillation module to facilitate better model optimization. In summary, the major contributions of our work include:
• We study the illicit drug trafficker detection on social media and create a new dataset on Instagram (including text, image and relation information) for the problem, which is novel and urgent.
• To solve the problem, we develop a holistic yet novel framework (i.e., MetaHG) to jointly model both structured relations and unstructured content information for illicit drug trafficker detection, accounting for the constraints of graph sparsity and limited labeled data for model training.
• Comprehensive experiments on the real-world dataset demonstrate the outstanding performance of MetaHG by comparison with the state-of-arts methods. To the best of our knowledge, MetaHG is the first work that automatically detects drug traffickers on social media using few labeled data.
• As drug overdose deaths have continued to increase over the past decade across the country, our proposed technique will have a significant societal impact to help address this critical issue.

heading: 2 Related Work

text:
In this section, we briefly introduce relevant studies in three aspects: drug trafficker detection, graph neural networks, and meta-learning.
Drug Trafficker Detection. Most existing works analyze drug traffickers on darknet markets [2, 3, 46, 47, 48]. For instance, Zhang et al. [46] developed a system by leveraging user’s styles to detect drug traffickers on darknet markets. As drug trafficking appears on the surface web dramatically recently, some recent works [20, 22, 23] detect illicit drug traffickers on social media platforms by analyzing the single type of text information or image information of posts. For example, Li et al. [20] used a RNN model to learn the text pattern of posts to detect drug dealers on Instagram. However, these methods seldom consider multi-modal features and the relational information among entities. Different from existing works, we detect these illicit drug traffickers on social media by incorporating structural relation and unstructured multi-modal content information.
Graph Neural Networks. Most existing graph neural networks (GNNs) learn the node embedding by aggregating the features of neighborhood nodes [12, 17, 39, 44]. GCN [17] implements layer-wise propagation rule to learn the node embedding, and GAT[39] proposes to learn different attention scores for neighbors when aggregating neighborhood information. However, most of these existing models work with homogeneous graphs. Some recent models [32, 34, 43, 45] are proposed to deal with heterogeneous graphs which are more practical in reality. Inspired by GCN, Weighted-GCN [34] and R-GCNs [32] propose to learn node embedding based on multiple relational neighborhoods. Additionally, inspired by GAT, HAN [43] leverages the attention mechanism to learn the importance between nodes and meta-path simultaneously in heterogeneous graphs. Motivated by these studies, we employ R-GCNs as our base model to learn the node embedding in HG.
Meta-Learning. Recent meta-learning models generally can be divided into two groups: metricbased meta-learning [4, 18, 28, 36, 40] and gradient-based meta-learning [1, 8, 10, 11, 19, 27]. For metric-based models, they implement a generalized metric and matching functions from training tasks to train the model. For instance, Matching Networks [40] learns a network that maps the labeled support set and an unlabelled example to the label in support set. Prototypical networks [36] learns a metric space in which classification can be performed by computing distances to prototype representations of each class. For gradient-based models, they employ existing tasks data to learn well initialized model parameters that can be fast updated to new tasks with few data [11] or directly implement a meta-optimizer to learn the optimization process [38]. For example, Finn et al. [10] proposed MAML, in which the parameters of the model are explicitly trained such that several gradient steps with few training data from a new task will produce good generalization performance on that task. In this paper, motivated by MAML, we introduce a meta-learning framework to address small labeled data challenge of illicit drug traffickers detection.

heading: 3 Preliminary

heading: 3.1 Problem Definition

text:
Given a social media dataset, we build a heterogeneous graph (HG) to comprehensively depict the rich information among the dataset for learning the user embedding. Let G = (V, E ,X ) denote a HG, where V is the set of different types of nodes, E ⊆ V × V is the set of edges, and X is the node attributes (features) set. Specifically, there are three types of nodes (user, post, and keyword) and eight types of relations (e.g., user-reply-post) in HG (see Figure 2). A node can be regarded as any type of entities and an edge can be regarded as any type of relations between two nodes. The node attribute can be considered as the feature applied to the node. The goal is to learn the user embedding which can be fed to a classifier for drug trafficker detection. Given the features of all user nodes Xr = (x1, . . . , xN ) (N : number of users) and their binary labels Y = (y1, . . . , yN ) (yi = 1 denotes drug trafficker and yi = 0 represents regular user), we target learning a mapping function (detection function) Uϕ : Xr → Y (with parameter ϕ). Unlike existing works that use sufficient
samples for model training, as the number of drug trafficker samples collected from social media is limited, we consider a more practical scenario that only few labeled data are available. Following the definition of few-shot learning [10], given the labeled data of existing different types of drug traffickers (e.g., stimulants trafficker (refer to the Supplementary Material 1.1)), we aim to build a classifier that can effectively detect drug traffickers of new types with few labeled data (e.g., opioid trafficker). Formally, the problem is defined as follows. Problem 1. Drug Trafficker Detection on Social Media. Given a social media data denoted as HG G and a set of different types of drug traffickers with their features Xr = (x1, . . . , xN ) and corresponding labels Y = (y1, . . . , yN ) (training data), the problem is to build a machine learning model to detect illicit drug traffickers of new types that only have few labeled samples (testing data).

heading: 3.2 Relational Graph Convolutional Networks

text:
Relational graph convolutional networks (R-GCNs) [32] has been proved to be powerful for learning the node representation in HG. Different from GCN, R-GCNs considers the different types of relationships between two nodes when aggregating features from neighborhoods. Thus, we employ R-GCNs as the base model to learn user representations in HG. According to the definition of R-GCNs, The layer-wise propagation rule can be formulated as follows:
hl+1i = σ( ∑ r∈R ∑ j∈N ri 1 |Nri | W lrh l j +W l 0h l i), (1)
where hl+1i denotes the representation of node i at l + 1 layer, W l is learnable weight, Nri denotes the set of neighbors of node i under relation r ∈ R, andR is the set of relation type in HG. For simplicity, we use Z = R-GCNs(X,A,R) to denote a R-GCNs model where Z is the node embedding, X is the attribute feature matrix, and A is the adjacency matrix based onR.
4 Methodology
In this section, we present the details of our proposed model MetaHG (Figure 3). At first, we construct a HG to depict both relation and multi-modal content information on social media, and introduce graph structure refinement (GSR) to generate a refined HG for compensating the spare connection among some entities. Then we utilize R-GCNs over the learned graph to learn node embedding and augment the model by an embedding similarity based self-supervised learning module (SSL). Lastly, we design a meta-learning algorithm for model optimization, which is further enhanced by a knowledge distillation module (KD).

heading: 4.1 HG Construction on Social Media

text:
To comprehensively describe illicit drug traffickers on social media, besides text and image content, we also consider the structural relation on social media. As shown in Figure 2, we build a HG with three types of entities (user, post, and keyword) and eight types of relations as well as features of each node, such that both content and relation information can be exploited simultaneously. Next, we introduce the content feature and relation information in detail.
Content Feature. Most users on social media post images and text simultaneously. Thus, we consider both text feature and image feature of posts and users. Text Feature: we first merge all of text information as the corpus to fine-tune the pre-trained language model BERT [5] and convert all of the
text information for each node to a fixed-length feature vector (dimension = 200). Particularly, for keyword nodes in HG, we first extract keywords from the corpus and then select a set of illicitoriented keywords based on word frequency. Furthermore, for each keyword node in HG, we feed the keyword to BERT to obtain the feature vector. Image Feature: we employ the pre-trained image model VGG19 [35] to acquire the image feature vector (dimension = 1000) for each image and then implement PCA [31] to decrease the dimension from 1000 to 200. Note that the image feature for a user node is the image feature vector of the user profile image, and the image feature for a post node is the image feature vector of the post image. For all keyword nodes, the image feature is set as zero. Finally, both text and image features are concatenated as the attribute applied to each node.
Relation. To determine whether a user is a drug trafficker on social media, we not only consider the content-based features (text and image features), but also the complex relationships among users, posts, and keywords. To characterize the relatedness of two nodes, we consider eight kinds of relationships (R1-R8 in Table 1) as follows: R1: user-follow/followed-user denotes that a user is following or followed by another user; R2: user-tagger-user denotes that a user tags another user; R3: user-reply-post denotes that a user replies to a post; R4: user-mention-post denotes that a user mentions another user in a post; R5: user-have-post denotes that a post belongs to the user; R6: user-profile-keyword denotes that the profile description of a user contains the keyword; R7: post-include-keyword denotes that the post content includes a certain keyword; R8: post-tag-keyword denotes that the content of a post has the hashtag keyword.

heading: 4.2 HG Structure Refinement via Metric Learning

text:
As some users appear to be inactive on social media, the HG constructed in the previous step is sparse in connections among some nodes. That is, the original HG is not optimal for detecting drug traffickers on social media. To address this problem, we propose to generate a better HG by graph structure refinement with metric learning (GSR). Specifically, we first calculate the similarities between node features to infer the potential connections between nodes by metric learning and obtain the feature similarity graph (FSG). Then, the original HG and FSG are combined to obtain a new and refined graph (see Figure 3.(b)). The generation process of FSG is described as below.
Feature Similarity Graph. Since the dimension of different types of node features is different, we first adopt a type-specific mapping layer to project all of the node features X to a common feature space:
X ′
i = σ(Xi ·Wk + bk), (2) where σ is the sigmoid activation function, Xi is the feature vector of node vi, Wk and bk denote the projection matrix and the bias vector for node type k respectively. Afterwards, we implement metric learning on node features in the common space and obtain a FSG G′ where the edge between node pair vi and vj is obtained by:
E ′i,j = { 1 E(X ′ i , X ′
j) ≥ ϵ 0 otherwise , (3)
where ϵ ∈ [0, 1] is the threshold value controlling the density of the generated FSG. E(X ′i , X ′
j) is a parameterized function to calculate the similarity between two nodes:
E(X ′ i , X ′ j) = Γ(Ws1 ⊙X ′ i ,Ws2 ⊙X ′ j), (4)
where Γ denotes a similarity function (cosine similarity in this work), Ws1 and Ws2 are the parameters which measure the importance of different feature dimensions, and ⊙ denotes the Hadamard product. The refined graph Gl is obtained by combining the original HG G and the generated FSG G′. In order to make Gl be relatively sparse and avoid overfitting for the downstream task, we introduce a structure sparsity regularizer via L1 norms:
Lgsr = ∥∥Al∥∥ , (5)
where Al is the adjacency matrix of Gl.

heading: 4.3 HG Representation Learning with Self-Supervised Augmentation

text:
With the refined graph Gl obtained in the previous step, we implement R-GCNs to learn node (i.e., user) embedding for drug trafficker detection. In particular, we stack R-GCNs layers to generate node embedding (Equation 1). For each user node vi ∈ Vc, we feed hi into a fully-connected layer and softmax function to predict illegal value of drug trafficker, i.e., Ŷi = hiWc. The objective is to jointly optimize the drug trafficker detection loss (i.e., the cross-entropy loss between the given drug trafficker labels Y and the predicted results Ŷ ) and the GSR loss Lgsr:
L = Lc + λgsrLgsr = − ∑ i∈Vc Yi log(Ŷi) + λgsr ∥∥Al∥∥ , (6)
where Vc is the node set of labeled users in HG, Y is the user label set, and λgsr is a trade-off weight. Self-Supervised Augmentation. Existing GNNs [17, 12, 26, 30] utilize the local neighborhood information and feature content to generate the node embedding. However, the representation learning in most GNNs is mainly dominated by local neighborhood information [15]. We wish to achieve a balance among the importance of local neighborhood and node features. Hence, we introduce a node embedding similarity based self-supervised module (SSL) using unlabeled data to enhance the HG representation learning (see Figure 3.(c)). Specifically, given a node vi, we define two sets of nodes Vhi and V li having the M highest similarities and M lowest similarities with vi respectively. Based on the similarity (cosine similarity) among pairs of original node features, we can define node pairs in Vhi as positive samples while node pairs in V li as negative samples. We wish that the embedding of node pairs in Vhi should be more similar while the embedding of node pairs in V li should be less similar. Hence, in each training epoch, we concatenate the embedding of each node pair (vi, vq) (i ̸= q) in Vhi and V li respectively denoted as Xiq , and assign each pair with label Yiq . Yiq = 1 when vq ∈ Vhi otherwise Yiq = 0 when vq ∈ V li . Afterwards, we feed the node pair embedding Xiq into a fully-connected neural network, i.e., Ŷiq = XiqWssl, to obtain the predicted label. Finally, the final objective of node representation learning is to minimize the joint loss including drug trafficker detection loss, the SSL loss, and the GSR loss:
Ljoint = Lc+λsslLssl+λgsrLgsr = − ∑ i∈Vc Yi log(Ŷi)−λssl ∑ i∈V ∑ q∈Vsi Yiq log(Ŷiq)+λgsr ∥∥Al∥∥ , (7) where Vsi = Vhi ∪ V li and λgsr is the hyper-parameters of SSL. By minimizing Ljoint, parameters of R-GCNs, SSL, and GSR are optimized jointly for downstream drug trafficker classification task.

heading: 4.4 Model Optimization with Meta-Learning

text:
We propose to leverage the meta-learning technique [10] for model optimization since the labeled data of drug traffickers is limited. In particular, it applies the gradient-based algorithm that learns well initialized model parameters (using training tasks data) which can be quickly adapted to unseen new tasks. In this paper, given a set of tasks T defined as drug trafficker detection problem (binary classification) of different trafficker types, we choose three drug trafficker types with a relatively large number of samples (e.g., stimulants trafficker) as meta-training tasks and the other two types with few
Algorithm 1 Training Procedure of MetaHG Require X , A,R, ϕ: nodes features, adjacent matrix, node relations, and initial parameters.
Learn a refined graph via Equation 3 and 4. Implement self-supervised learning to augment R-GCNs on the refined graph. while not convergae do
Sample a batch of meta-training tasks τ from T . for each τ do
Sample a support set Sτ and a query set Qτ . Update the parameters ϕ ′
τ via Equation 8. end for Update the parameters ϕ of task-agnostic model via Equation 9. Sample support set Sτ and query set Qτ from meta-testing tasks. Distill the soft knowledge from teacher model using the unlabeled data Qτ via Equation 10. Update the parameters of student model via optimizing Equation 13.
end while Return Optimized ϕ∗
samples (e.g., opioid trafficker) as meta-testing tasks. Then, we divide the data of each task τ ∈ T into support set Sτ and query set Qτ . Afterwards, the classifier is first updated to task-specific model on meta-training tasks with support set Sτ , and is further optimized to task-agnostic model using Qτ of training tasks, which is called meta-training. After sufficient training, the learned model can further adapt to new testing tasks with few data samples in support set, which is called meta-testing. Let ϕ be the set of model parameters. For a certain classification task τ , we begin with feeding Sτ to the model and calculate the loss Lτ on Qτ to update ϕ to ϕ ′ τ through gradient descent: ϕ′τ = ϕ− α▽ϕ Lτ (ϕ), (8) where α is the step size for inner-level meta-training. Later, the model (with parameter ϕ) is further updated in task-agnostic manner:
ϕ←− ϕ− β ▽ϕ ∑ τ∈T Lτ (ϕ′τ ), (9)
where β is the learning rate. After sufficient training over meta-training tasks, the well initialized parameters is further adapted for prediction over meta-testing tasks.
Meta Knowledge Distillation for Model Adaptation. The above optimization strategy directly adapts the classifier learned from the labeled data in meta-training to new testing tasks, while ignoring the the hidden information of unlabeled data during model training. Inspired by the knowledge distillation technique [13], we develop a meta knowledge distillation module (KD) that utilizes the unlabeled data in meta-learning to transfer soft knowledge from the meta-training classifier (teacher model) to the meta-testing model (student model) (Figure 3.(d)). Mimicking teacher’s prediction results enables student model to learn the secondary information that cannot be expressed by the labeled samples in meta-testing data alone. Soft knowledge from teacher model is formulated as the predicted probability of drug traffickers in meta-testing data:
PTl (Zi, t) = Softmax(f(Zi), t)) = exp [fl(Zi/t)]∑1 c=0 exp [fc(Zi/t)] , (10)
where Zi is the embedding of node vi in Qτ for meta-testing task τ , f(Zi) is the score logit that Zi achieves on label l, and t is the temperature index to soften the peaky softmax distribution [13]. Thus, the knowledge distillation loss of teacher model and student model is defined as follows:
Lkd = −t2 ∑
vi∈Qτ
1∑ c=0 PTc (Zi, t) log(P S c (Zi, t)), (11)
where PTc and P S c are the predicted distributions of teacher model and student model respectively. Afterwards, we combine the KD loss Lkd on unlabeled data (query data) and the cross-entropy loss Lce on labeled data (support set):
Ltotal = Lce + λkdLkd, (12)
where λkd is the trade-off weight for balancing the two losses. Taking the model (with parameter ϕ) obtained by Equation 9 as the initial model, the student model for meta-testing tasks are further updated (fine-tuned) as follows:
ϕ∗ = ϕ− α▽ϕ Ltotal(ϕ), (13) where α is the learning rate. Finally, the fine-tuned student model is used to detect drug trafficker in query set of meta-testing tasks. The pseudo-code of MetaHG training procedure is shown in Alogrithm 1.

heading: 5 Experiments

text: In this section, we first create a novel dataset for the problem. Then we conduct extensive experiments to evaluate the performance of our model. Further analysis is provided to show the effectiveness of each model component, hyper-parameter sensitivity, and model stability.

heading: 5.1 Novel Dataset for Drug Trafficker Detection

text: Existing works of drug trafficker detection on social media merely rely on text or image data and most of the datasets are not publicly accessible. Thus, we create a new dataset crawled from Instagram (a very popular social media platform worldwide [42]) for the problem. Specifically, we first utilize a set of illegal drug related keywords (e.g., weed, LSD, and fentanyl) to crawl the public user profiles and the corresponding posts using the public official Instagram API [7] from Jan 2020 to Jan 2021. Note that all collected data are public and we have anonymized the personal information of public users in our dataset. To obtain the groundtruth labels, we (including 3 groups, 2 annotators in each group) spent two months collecting and manually labeling these users into six groups (regular user, stimulants trafficker, hallucinogens trafficker, opioids trafficker, hidden trafficker, and mixture trafficker) according to the criterion in [33]. In total, we obtain 8,651 users (including 3,242 drug traffickers and 5,409 regular users) and 79,705 posts. Based on the dataset, we construct a HG which has 129,894 nodes (including 8,651 user nodes, 79,705 post nodes, and 41,538 keyword nodes) and 218,039 edges of eight relations (Table 1). Details of this dataset is provided in Supplementary Material 1.1.

heading: 5.2 Baseline Methods

text:
We compare our model with twenty baseline methods spanning several categories:
• Traditional Classification Methods. We take text features (tFeature), image features (iFeature), and the combination of them (cFeature) as the feature vector for each user respectively, and feed them to a generic 4-layer deep neural network [37] (DNN) (B1). We also consider two existing works [20, 22] using tFeature for drug traffickers detection (B2).
• Meta-Learning Models. For meta-learning baseline methods, besides MAML [10], we also employ two popular few-shot learning models, i.e., Matching Network (MatchingNet) [40] and Prototypical Network (ProtoNet) [36] to train a meta-learner with cFeature (B3).
• Graph Representation Learning Models. We take cFeature as node attribute information and apply six popular graph representation learning models to learn user embeddings in HG, i.e., Deepwalk [29], metapath2vec [6], GCN [17], GAT [39], HAN [43], and R-GCNs [32]. The learned user embeddings are further fed to a 4-layer DNN (B4) for classification. In addition, we also apply MAML to train these graph representation learning models (B5).
The details of all models are discussed in Supplementary Material 2.1.

heading: 5.3 Performance Comparison

text:
Table 2 reports the performances of all models. The best performances are highlighted in bold. All baseline models are divided into five groups (B1-B5) and the shot number denotes the support data size in model training and testing. According to the table, we can conclude that (i) The combination of text and image features (cFeature) contributes larger than single text or image features for drug traffickers detection (B1). It shows that both text and image are very indispensable to describe users on social media. (ii) By comparing results in B1 and B4, we find that considering the relationships among
entities can help improve the model performance. (iii) The performance of meta-learning models with combined features (B3) or node embeddings (B5) are much better than traditional classification models (B1 and B2), showing the effectiveness of meta-learning for solving this problem. (iv) In all cases, MetaHG significantly outperforms all baseline methods, demonstrating the strongest capability of our model for drug traffickers detection on social media.
5.4 Ablation Studies
Table 3: Results of different model variants.
Model 1-shot 5-shot 20-shot
ACC F1 ACC F1 ACC F1
MetaHG 0.8489 0.8480 0.8873 0.8758 0.9354 0.9311 – MAML (A1) 0.7247 0.6125 0.7535 0.6457 0.7932 0.6851 – KD (A2) 0.7914 0.7922 0.8356 0.8247 0.8804 0.8689 – GSR (A3) 0.8078 0.8018 0.8457 0.8351 0.8934 0.8857 – SSL (A4) 0.8147 0.8052 0.8561 0.8473 0.9056 0.9005 Our model MetaHG integrates four crucial components, i.e., graph structure refinement (GSR), self-supervised learning in R-GCNs (SSL), meta-learning (MAML), and knowledge distillation (KD). To verify the effectiveness of each component, we conduct ablation studies by removing each of them independently. The results of different model variants are reported in Table 3. We first replace MAML with a 4-layer DNN (A1), which means we implement the node embedding generated from SSL augmented R-GCNs over the refined graph. Similar to the data setting in B1 and B4, all labeled data in meta-training tasks and few-shot labeled data (support set) in meta-testing tasks are for model training, and the rest of data in meta-testing tasks (query set) are for model evaluation. We conclude that MAML has the greatest contribution to MetaHG. Then we remove KD on MAML (A2) and find the performance decrease obviously, showing the effectiveness of KD. Furthermore, we remove GSR (A3) and SSL (A4) from MetaHG respectively and find the performances of A3 and A4 drop almost 4% and 3% respectively compared with MetaHG, validating that both GSR and SSL are effective to enhance the model performance for the detection problem.

heading: 5.5 Hyper-parameter Sensitivity and Model Stability

text:
Figure 4: Hyper-parameter sensitivity (a)-(c) and model performance over different testing tasks (d).
To explore the hyper-parameter sensitivity, we conduct three analysis experiments w.r.t. ϵ on GSR, λssl on SSL, and λkd on meta-learning. Specifically, in Figure 4.(a), we vary ϵ in Eq. 3 to control the density of the generated graph in GSR. We find that the model performance increases with the increment of ϵ and the optimal value is 0.95, while the performance decreases when ϵ goes beyond the optimal value because the graph will be too sparse with a larger simi-
larity threshold. Additionally, in Figure 4.(b), we vary the value of λssl in Eq. 7. By comparing with λssl = 0 (without SSL) and λssl = 5, we can further validate the effectiveness of SSL in enhancing the model performance. The optimal value of λssl is 5 and the performance drops with larger λssl due to the overfitting on the SSL task. Moreover, in Figure 4.(c), we vary the value of λkd in Eq. 12 and the optimal value λkd is 0.01 for our model, indicating that it is necessary to incorporate appropriate distilled knowledge. As shown in Fig. 4.(d), we also analyze the stability of our model by comparing with three baseline methods on different testing tasks (T1: opioids trafficker detection, T2: hidden trafficker detection). MetaHG is obviously more stable and also better than baseline methods on both T1 and T2, showing the robustness and effectiveness of MetaHG.
5.6 Embedding Visualization
5.7 Case Study
We further analyze drug traffickers detected by MetaHG. Figure 6 illustrates the superiority of our model by comparing it with baseline models for real cases. MetaHG is able to detect hidden drug traffickers on social media although they pretend to be regular users or innocent users who seldom post any drug related information to the homepage. In this figure, drug trafficker “se***11” pretends to be an innocent user who does not have any illicit information on his homepage. However, he advertises at least four types of drugs (i.e., LSD, MDMA, DMT, and Shrooms) by leaving the contact information of encrypted chat tools (i.e., WICKR, Kik, and Snapchat) to other user’s posts. These hidden drug traffickers cannot be detected by existing models, while MetaHG can detect these hidden drug traffickers based on the relationships among entities on social media.

heading: 6 Conclusion

text: In this paper, to solve the problem of illicit drug trafficker detection with limited labeled data constraints, we create a new dataset and develop a novel system called MetaHG. Specifically, we first construct a HG to describe the structural relation and multi-modal content information in the dataset, and employ graph structure refinement to learn a refined HG. Then we employ R-GCNs with a self-supervised module to learn the node embedding in HG. Afterwards, we design a meta-learning algorithm to optimize the model. A knowledge distillation module is further introduced to improve model optimization. The extensive results demonstrate the effectiveness of our model by comparison with many baseline models.

heading: 7 Acknowledgment

text: This work is partially supported by the NSF under grants IIS-2107172, IIS-2140785, CNS-1940859, CNS-1814825, IIS-2027127, IIS-2040144, IIS-1951504 and OAC-1940855, the NIJ 2018-75-CX0032.

title: Distilling Meta Knowledge on Heterogeneous Graph for Illicit Drug Trafficker Detection on Social Media


summaries: EDIT: After reading authors' responses, I decided to keep my score as is.  The paper studies the problem of exact representation of continuous functions via neural networks with the ReLU activation. The literature on the approximation power of neural nets is large, however the paper here delves into the less studied question of whether the class of *exactly* representable functions strictly increases when adding more layers (with no restrictions on size).  The authors want to understand the function classes exactly represented by different architectures and a step towards this direction is to analayze the class of functions captured by a depth-d neural net (without width constraints) and how this class of functions changes as we get to depth-d+1 neural nets.  It is obvious that ReLU nets will output continuous piecewise linear functions (CPWL for short) and a non-trivial fact from previous works is that $\log(n+1)$ hidden layers suffice to represent *any* CPWL in n dimensions, via a ReLU net. Let d is a parameter for the depth and and ReLU(d) is all functions representable exactly via ReLU nets of depth at most d. The paper tries to understand ReLU(d) as d goes from 0 to $\log(n+1)$.  The authors put forth two equivalent conjectures about the relations between the class of functions ReLU(d) for different d. Conjecture 1.1 states that every additional layer will indeed be substantial in terms of the representational capabilities of ReLU nets up to $d\le \log(n+1)$ of course, at which point all CPWL are representable. The authors reformulate this with Conjecture 1.2 that is a simple statement about max functions.   The authors then show a special case of Conj. 1.2 that corresponds to showing that the max function on 5 variables cannot be representted with 2 or 3 hidden layers, with the caveat that they need a certain assumption on the breakpoints of the function represented by any intermediate neuron. Along the same lines,  the authors show that the class ReLU(k) contains more functions than just taking the max on $2^k+1$ variables. To achieve this they use the theory of polyhedral complexes associated with CPWL functions.  Finally, the authors find upper bounds on the sizes of the networks needed for expressing arbitrary CPWL functions with p linear pieces, as given in Theorem 4.4, which basically involves depth O(logn) nets with width growing as $p^{n^2}$.

summaries: This paper studies the role of depth in exactly representing real functions by ReLU networks.  Unlike the common ML setting, the focus is on neural nets that are equal in every point to the target function.  Some partial results are given as well as a conjecture that networks of depth k+1 have strictly more expressivity than networks of depth k.

summaries: It is known from the universal approximation theorem that ReLU networks with one hidden layer can approximate any continuous function on compact sets arbitrarily well. Instead of approximations, this paper investigates  the set of functions that can precisely be described by a network of certain depth. For a given input dimension D, a ReLU network with L=ceil[ log2(D+1) ] (or more) hidden layers (and arbitrary width) can describe the entire set of piecewise continuous functions. Here, new insight is provided for networks with having between 1 and L layers. In particular, under an unproven assumption, the paper shows that L is a strict lower limit for the depth and that adding layers to a network strictly increases the set of describable functions. This is achieved by studying a natural candidate function to require a larger number of hidden layers. The candidate function suggests a conjecture on a nice description of ReLU network functions of finite depth, which is shown to not hold true. Finally, the paper derives a bound on the width and depth of networks that can describe any piecewise linear function with fixed number of linear pieces.

summaries: This paper considers the problem of characterizing exact representations for ReLU networks of a given depth, but any width. It was previously shown that the functions represented by ReLU networks of depth logarithmic in dimension is exactly equal to the set of all continuous piecewise linear functions. This work provides some results which suggest that this result is tight. That is, a depth logarithmic in dimension is necessary to exactly represent all piecewise linear functions.   Proposition 1.3 simplifies this conjecture by giving a simple equivalent condition in terms of representing max(0,x_1,\dots,x_n) and proves the conjecture up to dimension 4 under the assumption 2.4 which is unproven. In section 3 it is shown that the set of functions representable by a depth k network is a strict super set of Max(2^k) - i.e, set of all functions which can written as a linear combination of max of 2^k affine functions. This provides further evidence in support of the conjecture.  Section 4 then extends the results of Arora et. al 2018 to provide an upper bound on the width required for a relu network to exactly represent affine function with p pieces. This bound is $p^{O(n^2)}$.

summaries: The authors study the class of functions that can be represented by a fully connected neural network with ReLU activations. First, They conjectured that for any $k\in\mathbb{N}$, $n=2^k$, the function $f_n(x)=\max\{0,x_1,\dots,x_n\}$ cannot be represented by a fully connected network with $k$ hidden layers, and prove this conjecture for $k=2$ under some mild assumption. Second, they proved the class of functions that can be represented by a $(k + 1)$-layer NN is strictly larger than the class of functions that are linear combinations of $2^k$-term max functions. Finally, they provided a bound on the width of the NN required to represent continuous piecewise linear functions.

abstractText: We contribute to a better understanding of the class of functions that is represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning tasks. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). This problem has potential impact on algorithmic and statistical aspects because of the insight it provides into the class of functions represented by neural hypothesis classes. However, to the best of our knowledge, this question has not been investigated in the neural network literature. We also present upper bounds on the sizes of neural networks required to represent functions in these neural hypothesis classes.

authors:
M. Alfarra
A. Bibi
H. Hammoud
M. Gaafar
B. Ghanem

title: On the decision boundaries of deep neural networks: A tropical geometry perspective

venue: arXiv preprint arXiv:2002.08838,

authors:
A.M. Alvarez
Q. Louveaux
L. Wehenkel

title: A machine learning-based approximation of strong branching

venue: INFORMS Journal on Computing,

authors:
R. Anderson
J. Huchette
W. Ma
C. Tjandraatmadja
J.P. Vielma

title: Strong mixed-integer programming formulations for trained neural networks

venue: Mathematical Programming,

authors:
M. Anthony
P.L. Bartlett

title: Neural network learning: Theoretical foundations

authors:
R. Arora
A. Basu
P. Mianjy
A. Mukherjee

title: Understanding deep neural networks with rectified linear units

venue: In International Conference on Learning Representations,

authors:
R. Bagnara
P.M. Hill
E. Zaffanella

title: The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systems

venue: Science of Computer Programming,

title: Universal approximation bounds for superpositions of a sigmoidal function

venue: IEEE Transactions on Information theory,

title: Approximation and estimation bounds for artificial neural networks

venue: Machine learning,

authors:
Y. Bengio
A. Lodi
A. Prouvost

title: Machine learning for combinatorial optimization: a methodological tour d’horizon

venue: European Journal of Operational Research,

authors:
P. Bonami
A. Lodi
G. Zarpellon

title: Learning a classification of mixed-integer quadratic programming problems

venue: In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research,

authors:
D. Boob
S.S. Dey
G. Lan

title: Complexity of training relu neural network

venue: Discrete Optimization,

authors:
V. Charisopoulos
P. Maragos

title: A tropical approach to neural networks with piecewise linear activations

venue: arXiv preprint arXiv:1805.08749,

title: Approximation by superpositions of a sigmoidal function

venue: Mathematics of control, signals and systems,

authors:
S.S. Dey
G. Wang
Y. Xie

title: Approximation algorithms for training one-node relu neural networks

venue: IEEE Transactions on Signal Processing,

title: Algorithms in Combinatorial Geometry

venue: Springer Science & Business Media,

authors:
R. Eldan
O. Shamir

title: The power of depth for feedforward neural networks

venue: In 29th Annual Conference on Learning Theory,

authors:
M. Fischetti
J. Jo

title: Deep neural networks as 0-1 mixed integer linear programs: A feasibility study

venue: arXiv preprint arXiv:1712.06174,

authors:
V. Froese
C. Hertrich
R. Niedermeier

title: The computational complexity of ReLU network training parameterized by data dimensionality

venue: arXiv preprint arXiv:2105.08675,

authors:
M. Gasse
D. Chételat
N. Ferroni
L. Charlin
A. Lodi

title: Exact combinatorial optimization with graph convolutional neural networks

authors:
S. Goel
A.R. Klivans

title: Learning neural networks with two nonlinear layers in polynomial time

venue: In Conference on Learning Theory,

authors:
S. Goel
V. Kanade
A. Klivans
J. Thaler

title: Reliably learning the relu in polynomial time

authors:
S. Goel
A. Klivans
R. Meka

title: Learning one convolutional layer with overlapping patches

venue: In International Conference on Machine Learning,

authors:
S. Goel
A.R. Klivans
P. Manurangsi
D. Reichman

title: Tight hardness results for training depth-2 ReLU networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS ’21), volume 185 of LIPIcs, pages 22:1–22:14

venue: Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

authors:
R. Gribonval
G. Kutyniok
M. Nielsen
F. Voigtlaender

title: Approximation spaces of deep neural networks

venue: Constructive Approximation,

authors:
H. He
H. Daume III
J.M. Eisner

title: Learning to search in branch and bound algorithms

venue: Advances in neural information processing systems,

authors:
J.-B. Hiriart-Urruty
C. Lemaréchal

title: Convex Analysis and Minimization Algorithms II, volume 306 of Grundlehren der mathematischen Wissenschaften

title: Approximation capabilities of multilayer feedforward networks

venue: Neural networks,

title: Essentials of tropical combinatorics

venue: Graduate Studies in Mathematics. American Mathematical Society, Providence, RI,

authors:
E. Khalil
P. Le Bodic
L. Song
G. Nemhauser
B. Dilkina

title: Learning to branch in mixed integer programming

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
E.B. Khalil
B. Dilkina
G.L. Nemhauser
S. Ahmed
Y. Shao

title: Learning to run heuristics in tree search

authors:
M. Kruber
M.E. Lübbecke
A. Parmentier

title: Learning when to use a decomposition

venue: In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems,

authors:
A. Lodi
G. Zarpellon

title: On learning and branching: a survey

authors:
D. Maclagan
B. Sturmfels

title: Introduction to tropical geometry, volume 161 of Graduate Studies in Mathematics

venue: American Mathematical Soc.,

authors:
P. Maragos
V. Charisopoulos
E. Theodosis

title: Tropical geometry and machine learning

venue: Proceedings of the IEEE,

title: Approximation of real functions using neural networks

venue: In Proc. Intl. Conf. Comp. Math.,

title: Neural networks for optimal approximation of smooth and analytic functions

venue: Neural computation,

authors:
H.N. Mhaskar
C.A. Micchelli

title: Degree of approximation by neural and translation networks with a single hidden layer

venue: Advances in applied mathematics,

authors:
G. Montúfar
Y. Ren
L. Zhang

title: Sharp bounds for the number of regions of maxout networks and vertices of minkowski sums

venue: arXiv preprint arXiv:2104.08135,

authors:
G.F. Montúfar
R. Pascanu
K. Cho
Y. Bengio

title: On the number of linear regions of deep neural networks

venue: Advances in Neural Information Processing Systems

authors:
A. Mukherjee
A. Basu

title: Lower bounds over boolean inputs for deep neural networks with relu gates

venue: arXiv preprint arXiv:1711.03073,

authors:
R. Pascanu
G. Montúfar
Y. Bengio

title: On the number of inference regions of deep feed forward networks with piece-wise linear activations

title: Approximation theory of the mlp model

venue: Acta Numerica 1999: Volume

authors:
M. Raghu
B. Poole
J. Kleinberg
S. Ganguli
J.S. Dickstein

title: On the expressive power of deep neural networks

title: The perceptron: a probabilistic model for information storage and organization in the brain

venue: Psychological review,

title: Theory of Linear and Integer Programming

authors:
T. Serra
S. Ramalingam

title: Empirical bounds on linear regions of deep rectifier networks

authors:
T. Serra
C. Tjandraatmadja
S. Ramalingam

title: Bounding and counting linear regions of deep neural networks

authors:
T. Serra
A. Kumar
S. Ramalingam

title: Lossless compression of deep neural networks

venue: In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research,

title: benefits of depth in neural networks

venue: In 29th Annual Conference on Learning Theory, pages 1517–1539,

title: Benefits of depth in neural networks

authors:
G. Vardi
D. Reichman
T. Pitassi
O. Shamir

title: Size and depth separation in approximating benign functions with neural networks

title: General constructive representations for continuous piecewise-linear functions

venue: IEEE Transactions on Circuits and Systems I: Regular Papers,

authors:
S. Wang
X. Sun

title: Generalization of hinging hyperplanes

venue: IEEE Transactions on Information Theory,

authors:
L. Zhang
G. Naitzat
L.-H. Lim

title: Tropical geometry of deep neural networks

heading: 1 Introduction

text:
A core problem in machine learning or statistical pattern recognition is the estimation of an unknown data distribution with access to i.i.d. samples from the distribution. It is well-known that there is a tension between how much prior information one has about the data distribution and how many samples one needs to solve the problem with high confidence (or equivalently, how much variance one has in one’s estimate). This is referred to as the bias-variance trade-off or the bias-complexity trade-off. Neural networks provide a way to turn this bias/complexity knob in a controlled manner that has been studied for decades going back to the idea of a perceptron by Rosenblatt [1958]. This is done by modifying the architecture of a neural network class of functions, which has two parameters: depth and size. As one increases these parameters, the class of functions becomes more expressive. In terms of the bias-variance trade-off, the “bias” decreases as the class of functions becomes more expressive, but the “variance” or “complexity” increases.
So-called universal approximation theorems [Cybenko, 1989, Hornik, 1991, Anthony and Bartlett, 1999] show that even with a single hidden layer, i.e., when the depth of the architecture is the smallest possible value, one can essentially reduce the “bias” as much as one desires, by increasing the size of the network or the number of neurons used in the neural network. Nevertheless, it can be advantageous both theoretically and empirically to increase the depth because a substantial reduction in the size can be achieved; Telgarsky [2016a], Eldan and Shamir [2016], Arora et al. [2018] is a small sample of recent work in this direction. To get a better quantitative handle on these trade-offs,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
it is important to understand what classes of functions are exactly representable by neural networks with a certain architecture. The precise mathematical statements of universal approximation theorems show that single layer networks can approximate arbitrarily well any continuous function (under some additional mild hypotheses). While this suggests that single layer networks are good enough from a learning perspective, from a mathematical perspective, one can ask the question if the class of functions represented by a single layer is a strict subset of the class of function represented by two or more hidden layers. On the question of size, one can ask for precise bounds on the size of the network of a given depth to represent a certain class of functions. We believe that a better understanding of the function classes exactly represented by different architectures will have implications not just for mathematical foundations, but also algorithmic and statistical learning aspects of neural networks. The task of searching for the “best” function in that class can only benefit from a better understanding of the nature of functions in that class. A motivating question behind the results in this paper is to understand the hierarchy of function classes exactly represented by neural networks of increasing depth.
We now introduce more precise notation and terminology to set the stage for our investigations.
Notation. We write [n] := {1, 2, . . . , n} for the set of natural numbers up to n (without zero) and [n]0 := [n] ∪ {0} for the same set including zero. For any n ∈ N, let σ : Rn → Rn be the component-wise rectifier function
σ(x) = (max{0, x1},max{0, x2}, . . . ,max{0, xn}).
For any number of hidden layers k ∈ N, a (k + 1)-layer feedforward neural network with rectified linear units (ReLU NN or simply NN) is given by k affine transformations T (`) : Rn`−1 → Rn` , x 7→ A(`)x+ b(`), for ` ∈ [k], and a linear transformation T (k+1) : Rnk → Rnk+1 , x 7→ A(k+1)x. It is said to compute or represent the function f : Rn0 → Rnk+1 given by
f = T (k+1) ◦ σ ◦ T (k) ◦ σ ◦ · · · ◦ T (2) ◦ σ ◦ T (1). The matrices A(`) ∈ Rn`×n`−1 are called the weights and the vectors b(`) ∈ Rn` are the biases of the `-th layer. The number n` ∈ N is called the width of the `-th layer. The maximum width of all hidden layers max`∈[k] n` is called the width of the NN. Further, we say that the NN has depth k + 1 and size ∑k `=1 n`.
Often, NNs are represented as layered, directed, acyclic graphs where each dimension of each layer (including input layer ` = 0 and output layer ` = k + 1) is one vertex, weights are arc labels, and biases are node labels. Then, the vertices are called neurons.
For a given input x = x(0) ∈ Rn0 , let y(`) := T (`)(x(`−1)) ∈ Rn` be the activation vector and x(`) := σ(y`) ∈ Rn` the output vector of the `-th layer. Further, let y := y(k+1) = f(x) be the output of the NN. We also say that the i-th component of each of these vectors is the activation or the output of the i-th neuron in the `-th layer.
For k ∈ N, we define ReLUn(k) := {f : Rn → R | f can be represented by a (k + 1)-layer NN}, CPWLn := {f : Rn → R | f is continuous and piecewise linear}. By definition, a continuous function f : Rn → R is piecewise linear in case there is a finite set of polyhedra whose union is Rn, and f is affine linear over each such polyhedron. In order to analyze ReLUn(k), we use another function class defined as follows. We call a function g a p-term max function if it can be expressed as maximum of p affine terms, that is, g(x) = max{`1(x), . . . , `p(x)} where `i : Rn → R is affinely linear for i ∈ [p]. Based on that, we define
MAXn(p) := {f : Rn → R | f is a linear combination of p-term max functions}.
If the input dimension n is not important for the context, we sometimes drop the index and use ReLU(k) := ⋃ n∈N ReLUn(k) and MAX(p) := ⋃ n∈N MAXn(p) instead.
Since we deal with polyhedra a lot in this paper, we will use the standard notations convA and coneA for the convex and conic hulls of a set A ⊆ Rn. For an in-depth treatment of polyhedra and (mixed-integer) optimization, we refer to Schrijver [1986].

heading: 1.1 Our Contribution

text:
It is not hard to see that any function expressed by a ReLU network is a continuous and piecewise linear (CPWL) function, because one is composing continuous piecewise linear functions together. Based on a result by Wang and Sun [2005], Arora et al. [2018] show that every CPWL function defined on Rn can be represented by a ReLU neural network with dlog2(n+ 1)e hidden layers. We wish to understand whether one can do better. We believe it is not possible to do better and we pose the following conjecture to better understand the importance of depth in neural networks. Conjecture 1.1. For any n ∈ N, let k∗ := dlog2(n+ 1)e. Then it holds that
ReLUn(0) ( ReLUn(1) ( · · · ( ReLUn(k∗ − 1) ( ReLUn(k∗) = CPWLn . (1)
Conjecture 1.1 claims that any additional layer up to k∗ hidden layers strictly increases the set of representable functions. This would imply that the construction by Arora et al. [2018, Theorem 2.1] is actually depth-minimal.
Observe that in order to prove Conjecture 1.1, it suffices to find a single function f ∈ ReLUn(k∗) \ ReLUn(k∗ − 1) with n = 2k
∗−1 for all k∗ ∈ N. This also implies all remaining strict inclusions ReLUn(i− 1) ( ReLUn(i) for i < k∗ since ReLUn(i− 1) = ReLUn(i) directly implies that ReLUn(i− 1) = ReLUn(i′) for all i′ ≥ i− 1. In fact, there is a canonical candidate for such a function, allowing us to reformulate the conjecture as follows. Conjecture 1.2. For any k ∈ N, n = 2k, the function fn(x) = max{0, x1, . . . , xn} cannot be represented with k hidden layers. Proposition 1.3. Conjecture 1.1 and Conjecture 1.2 are equivalent.
Proof (Sketch). We argued above that Conjecture 1.2 implies Conjecture 1.1. For the other direction, one can argue that, if the specific (n+1)-term max function fn can be represented by k hidden layers, then every other (n+ 1)-term max function as well. The claim then follows via a result by [Wang and Sun, 2005] stating that any f ∈ CPWLn can be written as linear combination of (n+ 1)-term max functions. We provide a detailed argument in Appendix A.
It is known that Conjecture 1.2 holds for k = 1 [Mukherjee and Basu, 2017]. However, the conjecture remains open for k ≥ 2. In this paper, we present the following results as partial progress towards resolving this conjecture.
In Section 2, we resolve Conjecture 1.2 for k = 2, under a natural assumption on the breakpoints of the function represented by any intermediate neuron. We achieve this result by leveraging techniques from mixed-integer programming to analyze the set of functions computable by certain NNs.
It is not hard to see that MAX(2k) ⊆ ReLU(k) for all k ∈ N [Arora et al., 2018], that is, any 2k-term max function (and linear combinations thereof) can be expressed with k hidden layers. One might ask whether the converse is true as well, that is, whether the classes MAX(2k) and ReLU(k) are actually equal. This would not only provide a neat characterization of ReLU(k), but also prove Conjecture 1.2 without any additional assumption since one can show that max{0, x1, . . . , x2k} is not contained in MAX(2k).
In fact, this is true for k = 1, that is, a function is computable with one hidden layer if and only if it is a linear combination of 2-term max functions. However, in Section 3, we show that for k ≥ 2, the class ReLU(k) is a strict superset of MAX(2k). In this section, the key technical ingredient is the theory of polyhedral complexes associated with CPWL functions. This way, we provide important insights concerning the richness of the class ReLU(k).
So far, we have focused on understanding the smallest depth needed to express CPWL functions using neural networks with ReLU activations. In Section 4, we complement these results by upper bounds on the sizes of the networks needed for expressing arbitrary CPWL functions. In particular, Theorem 4.4 shows that any continuous piecewise linear function with p linear/affine pieces on Rn can be expressed by a network with depth at most O(log n) and width at most pO(n2). We arrive at this result by introducing a novel application of recently established interactions between neural networks and tropical geometry.

heading: 1.2 Related Work

text:
Depth versus size. Soon after the original universal approximation theorems [Cybenko, 1989, Hornik, 1991], concrete bounds were obtained on the number of neurons needed in the hidden layer to achieve a certain level of accuracy. The literature on this is vast and we refer to a small representative sample here [Barron, 1993, 1994, Mhaskar, 1993, Pinkus, 1999, Mhaskar, 1996, Mhaskar and Micchelli, 1995]. More recently, work has focused on how deeper networks can have exponentially or super exponentially smaller size compared to shallower networks [Telgarsky, 2016a, Eldan and Shamir, 2016, Arora et al., 2018, Vardi et al., 2021]. See also Gribonval et al. [2021] for another perspective on the relationship between expressivity and architecture, and the references therein. We reiterate that the list of references above is far from complete.
Mixed-integer optimization and machine learning. Over the past decade, a growing body of work has emerged that explores the interplay between mixed-integer optimization and machine learning. On the one hand, researchers have attempted to improve mixed-integer optimization algorithms by exploiting novel techniques from machine learning [Bonami et al., 2018, Gasse et al., 2019, He et al., 2014, Khalil et al., 2016, 2017, Kruber et al., 2017, Lodi and Zarpellon, 2017, Alvarez et al., 2017]; see also Bengio et al. [2020] for a recent survey. On the flip side, mixed-integer optimization techniques have been used to analyze function classes represented by neural networks [Serra et al., 2018, Anderson et al., 2020, Fischetti and Jo, 2017, Serra and Ramalingam, 2020, Serra et al., 2020]. In Section 2 below, we show another new use of mixed-integer optimization tools for understanding function classes represented by neural networks.
Design of training algorithms. We believe that a better understanding of the function classes represented exactly by a neural architecture also has benefits in terms of understanding the complexity of the training problem. For instance, in a paper by Arora et al. [2018], an understanding of single layer ReLU networks enables the design of a globally optimal algorithm for solving the empirical risk minimization (ERM) problem, that runs in polynomial time in the number of data points in fixed dimension. See also Goel et al. [2017, 2018], Goel and Klivans [2019], Dey et al. [2020], Boob et al. [2020], Goel et al. [2021], Froese et al. [2021] for a similar lines of work.
Neural Networks and Tropical Geometry. A recent stream of research involves the interplay between neural networks and tropical geometry. The piecewise linear functions computed by neural networks can be seen as (tropical quotients of) tropical polynomials. Linear regions of these functions correspond to vertices of so-called Newton polytopes associated with these tropical polynomials. Applications of this correspondence include bounding the number of linear regions of a neural network [Zhang et al., 2018, Charisopoulos and Maragos, 2018, Montúfar et al., 2021] and understanding decision boundaries [Alfarra et al., 2020]. In Section 4 we present a novel application of tropical concepts to understand neural networks. We refer to Maragos et al. [2021] for a recent survey of connections between machine learning and tropical geometry, as well as to the textbooks by Maclagan and Sturmfels [2015] and Joswig [2022] for in-depth introductions to tropical geometry and tropical combinatorics.

heading: 2 Conditional Lower Bounds on Depth via Mixed-Integer Programming

text:
In this section, we provide a computer-aided proof that, under a natural, yet unproven assumption, the function f(x) := max{0, x1, x2, x3, x4} cannot be represented by a 3-layer NN. It is worth to note that, to the best of our knowledge, no CPWL function is known for which the non-existence of a 3-layer NN can be proven without additional assumption. For easier notation, we write x0 := 0.
We first prove that we may restrict ourselves to NNs without biases. This holds true independent of our assumption, which we introduce afterwards. Definition 2.1. A function g : Rn → Rm is called positively homogeneous if g(λx) = λg(x) for all λ ≥ 0. Definition 2.2. For an NN given by affine transformations T (`)(x) = A(`)x + b(`), we define the corresponding homogenized NN to be the NN given by T̃ (`)(x) = A(`)x with all biases set to zero. Proposition 2.3. If an NN computes a positively homogeneous function, then the corresponding homogenized NN computes the same function.
Proof. Let g : Rn0 → Rnk+1 be the function computed by the original NN and g̃ the one computed by the homogenized NN. Further, for any 0 ≤ ` ≤ k, let g(`) = T (`+1) ◦σ ◦T (`) ◦ · · ·◦T (2) ◦σ ◦T (1) be the function computed by the sub-NN consisting of the first (` + 1)-layers and let g̃(`) be the function computed by the corresponding homogenized sub-NN. We first show by induction on ` that the norm of ‖g(`)(x)− g̃(`)(x)‖ is bounded by a global constant that only depends on the parameters of the NN but not on x.
For ` = 0, we obviously have ‖g(0)(x) − g̃(0)(x)‖ = ‖b(1)‖ =: C0, settling the induction base. For the induction step, let ` ≥ 1 and assume that ‖g(`−1)(x) − g̃(`−1)(x)‖ ≤ C`−1, where C`−1 only depends on the parameters of the NN. Since component-wise ReLU activation has Lipschitz constant 1, this implies ‖(σ ◦ g(`−1))(x)− (σ ◦ g̃(`−1))(x)‖ ≤ C`−1. Using any matrix norm that is compatible with the Euclidean vector norm, we obtain:
‖g(`)(x)− g̃(`)(x)‖ = ‖b(`+1) +A(`+1)((σ ◦ g(`−1))(x)− (σ ◦ g̃(`−1))(x))‖ ≤ ‖b(`+1)‖+ ‖A(`+1)‖ · C`−1 =: C`
Since the right-hand side only depends on NN parameters, the induction is completed.
Finally, we show that g = g̃. For the sake of contradiction, suppose that there is an x ∈ Rn0 with ‖g(x) − g̃(x)‖ = δ > 0. Let x′ := Ck+1δ x; then, by positive homogeneity, it follows that ‖g(x′)− g̃(x′)‖ = Ck + 1 > Ck, contradicting the property shown above. Thus, we have g = g̃.
Since f = max{0, x1, x2, x3, x4} is positively homogeneous, Proposition 2.3 implies that, if there is a 3-layer NN computing f , then there also is one that has no biases. Therefore, in the remainder of this section, we only consider NNs without biases and assume implicitly that all considered CPWL functions are positively homogeneous. In particular, any piece of such a CPWL function is linear and not only affine linear.
Observe that, for function f , the only points of non-differentiability (a.k.a. breakpoints) are at places where at least two of the five numbers x0 = 0, x1, x2, x3, and x4 are equal. Hence, if some neuron of an NN computing f introduces breakpoints at other places, these breakpoints must be canceled out by other neurons. Therefore, it is a natural assumption that such breakpoints are not introduced at all in the first place.
To make this assumption formal, let Hij = {x ∈ R4 | xi = xj}, for 0 ≤ i < j ≤ 4, be ten hyperplanes in R4 and H = ⋃ 0≤i<j≤4Hij be the corresponding hyperplane arrangement. The regions or cells of H are defined to be the closures of the connected components of R4 \H . It is easy to see that these regions are in one-to-one correspondence to the 5! = 120 possible orderings of the five numbers x0 = 0, x1, x2, x3, and x4. More precisely, for a permutation π of the five indices [4]0 = {0, 1, 2, 3, 4}, the corresponding region is the polyhedron
Cπ := {x ∈ R4 | xπ(0) ≤ xπ(1) ≤ xπ(2) ≤ xπ(3) ≤ xπ(4)}.
We say that a (positively homogeneous) CPWL function g is H-conforming, if it is linear within any of these regions of H , that is, if it only has breakpoints where the relative ordering of the five values x0 = 0, x1, x2, x3, x4 changes. Moreover, an NN is said to be H-conforming if the output of each neuron contained in the NN is H-conforming. Equivalently, this is the case if and only if all intermediate functions σ ◦ T (`) ◦ σ ◦ T (`−1) ◦ · · · ◦ σ ◦ T (1), ` ∈ [k], are H-conforming. Now our assumption can be formally phrased as follows. Assumption 2.4. If there exists a 3-layer NN computing f(x) = max{0, x1, x2, x3, x4}, then there also exists one that is H-conforming.
We use mixed-integer programming to prove the following theorem. Theorem 2.5. Under Assumption 2.4, there does not exist a 3-layer NN that computes the function f(x) = max{0, x1, x2, x3, x4}.
Proof (Outline). We first study some geometric properties of the hyperplane arrangement H . This will show that each of the 120 cells of H is a simplicial polyhedral cone spanned by 4 extreme rays. In total, there are 30 such rays (because rays are used multiple times to span different cones). This implies that the set of H-conforming functions of type R4 → R is a 30-dimensional vector space and
each function is uniquely determined by its values on the 30 rays. We then use linear algebra to show that the space of functions generated by H-conforming two-layer NNs is a 14-dimensional subspace. Moreover, with two hidden layers, at least 29 of the 30 dimensions can be generated and f is not contained in this 29-dimensional subspace. So, it remains the question whether the 14 dimensions producible with the first hidden layer can be combined in such a way that after applying a ReLU activation in the second hidden layer, we do not end up within the 29-dimensional subspace. We model this question as a mixed-interger program (MIP). Solving the MIP yields that we always end up within the 29-dimensional subspace, implying that f cannot be represented by a 3-layer NN. This provides a computational proof of Theorem 2.5. All details can be found in Appendix B.
3 Going Beyond 2k-Term Max Functions with k Layers
In this section we prove the following result: Theorem 3.1. For any k ≥ 2, the class ReLU(k) is a strict superset of MAX(2k).
In order to prove this theorem, we provide a specific function that is in ReLU(k) \MAX(2k) for any number of hidden layers k ≥ 2. The challenging part is to show that the function is in fact not contained in MAX(2k). Proposition 3.2. For any n ≥ 3, the function
f : Rn → R, f(x) = max{0, x1, x2, . . . , xn−3, max{xn−2, xn−1}+ max{0, xn}} (2) cannot be written as a linear combination of n-term max functions.
The above proposition means that it is not possible to write f(x) in the form
f(x) = p∑ i=1 λi max{`i1(x), . . . , `in(x)}
where p ∈ N, λ1, . . . , λp ∈ R, and `ij : Rn → R is an affine linear function for every i ∈ [p] and j ∈ [n]. (Note that max functions with less than n terms are also allowed, as some functions `ij may coincide.)
Before we prove Proposition 3.2, we show that it implies Theorem 3.1.
Proof of Theorem 3.1. For k ≥ 2, let n := 2k. By Proposition 3.2, function f defined in (2) is not contained in MAX(2k). It remains to show that it can be represented using a ReLU NN with k hidden layers. To see this, first observe that any of the n/2 = 2k−1 terms max{0, x1}, max{x2i, x2i+1} for i ∈ [n/2 − 2], and max{xn−2, xn−1} + max{0, xn} can be expressed by a one-hidden-layer NN since all these are (linear combinations of) 2-term max functions. Since f is the maximum of these 2k−1 terms, and since the maximum of 2k−1 numbers can be computed with k − 1 hidden layers [Arora et al., 2018], this implies that f is in ReLU(k).
In order to prove Proposition 3.2, we need the concept of polyhedral complexes. A polyhedral complex P is a finite set of polyhedra such that each face of a polyhedron in P is also in P , and for two polyhedra P,Q ∈ P , their intersection P ∩Q is a common face of P and Q (possibly the empty face). Given a polyhedral complex P in Rn and an integer m ∈ [n], we let Pm denote the collection of all m-dimensional polyhedra in P . For a convex CPWL function f , we define its underlying polyhedral complex as follows: it is the unique polyhedral complex covering Rn (i.e., each point in Rn belongs to some polyhedron in P) whose n-dimensional polyhedra coincide with the domains of the (maximal) affine pieces of f . In particular, f is affinely linear within each P ∈ P , but not within any strict superset of a polyhedron in Pn. Exploiting properties of polyhedral complexes associated with CPWL functions, we prove the following proposition in Appendix C. Proposition 3.3. Let f0 : Rn → R be a convex CPWL function and let P0 be the underlying polyhedral complex. If there exists a hyperplane H ⊆ Rn such that the set
T := ⋃{ F ∈ Pn−10 ∣∣ F ⊆ H}
is nonempty and contains no line, then f0 cannot be expressed as a linear combination of n-term maxima of affine linear functions.
This allows us to prove Proposition 3.2.
Proof of Proposition 3.2. Observe that f (defined in (2)) has the alternate representation
f(x) = max{0, x1, x2, . . . , xn−3, xn−2, xn−1, xn−2 + xn, xn−1 + xn} as a maximum of n+ 2 terms. Let P be its underlying polyhedral complex. Let the hyperplane H be defined by x1 = 0.
Observe that any facet in Pn−1 is a polyhedron defined by two of the n + 2 terms that are equal and at least as large as each of the remaining n terms. Hence, the only facet that could possibly be contained in H is
F := {x ∈ Rn | x1 = 0 ≥ x2, . . . , xn−3, xn−2, xn−1, xn−2 + xn, xn−1 + xn}.
Note that F is indeed an (n− 1)-dimensional facet in Pn−1, because, for example, the full neighborhood of (0,−1, . . . ,−1) ∈ Rn intersected with H is contained in F . Finally, we need to show that F is pointed, that is, it contains no line. A well-known fact from polyhedral theory says if there is any line in F with direction d ∈ Rn \ {0}, then d must satisfy the defining inequalities with equality. However, only the zero vector does this. Hence, F cannot contain a line.
Therefore, when applying Proposition 3.3 to f with underlying polyhedral complex P and hyperplane H , we have T = F , which is nonempty and contains no line. Hence, f cannot be written as linear combination of n-term maxima.

heading: 4 A Width Bound for NNs with Small Depth

text:
While the arguments in Arora et al. [2018] show that CPWLn = ReLUn(dlog2(n + 1)e), they do not provide any bound on the width of the NN required to represent any particular continuous piecewise linear function. The purpose of this section is to prove that for fixed dimension n, the required width for exact, depth-minimal representation of a CPWL function can be polynomially bounded in the number p of affine pieces; in particular pO(n
2). This is closely related to works that bound the number of linear pieces of an NN as a function of the size [Montúfar et al., 2014, Pascanu et al., 2014, Raghu et al., 2017, Montúfar et al., 2021]. It can also be seen as a counterpart, in the context of exact representations, to quantitative universal approximation theorems that bound the number of neurons required to achieve a certain approximation guarantee; see, e.g., Barron [1993, 1994], Mhaskar [1993], Pinkus [1999], Mhaskar [1996], Mhaskar and Micchelli [1995].

heading: 4.1 The Convex Case

text:
We first derive our result for the case of convex CPWL functions and then use this to also prove the general nonconvex case. Our width bound is a consequence of the following theorem about convex CPWL functions, for which we are going to provide a geometric proof later. Theorem 4.1. Let f(x) = max{aTi x + bi | i ∈ [p]} be a convex CPWL function defined on Rn. Then f can be written as
f(x) = ∑ S⊆[p], |S|≤n+1 cS max{aTi x+ bi | i ∈ S}
with coefficients cS ∈ Z, for S ⊆ [p], |S| ≤ n+ 1.
For the convex case, this yields a stronger version of the theorem by Wang and Sun [2005] stating that any (not necessarily convex) CPWL function can be written as a linear combination of (n+ 1)-term maxima. Theorem 4.1 is stronger in the sense that it guarantees that all pieces of the (n+ 1)-term maxima must be pieces of the original function, making it possible to bound the total number of these (n+ 1)-term maxima and, therefore, the size of an NN representing f .
Theorem 4.2. Let f : Rn → R be a convex CPWL function with p affine pieces. Then f can be represented by a ReLU NN with depth dlog2(n+ 1)e+ 1 and width O(pn+1).
Proof. Since the number of possible subsets S ⊆ [p] with |S| ≤ n + 1 is bounded by pn+1, the theorem follows by Theorem 4.1 and the construction from Arora et al. [2018, Theorem 2.1].
Before we present the proof of Theorem 4.1, we show how we can generalize its consequences to the nonconvex case.

heading: 4.2 The General (Nonconvex) Case

text:
It is a well-known fact that every CPWL function can be expressed as a difference of two convex CPWL functions, see, e.g., Wang [2004, Theorem 1]. This allows us to derive the general case from the convex case. What we need, however, is to bound the number of affine pieces of the two convex CPWL functions in terms of the number of pieces of the original function. Therefore, we consider a specific decomposition for which such bounds can easily be achieved.
Proposition 4.3. Let f : Rn → R be a CPWL function with p affine pieces. Then, f can be written as f = g − h where both g and h are convex CPWL functions with at most p2n+1 pieces.
Proof. Suppose the p affine pieces of f are given by x 7→ aTi x + bi, i ∈ [p]. Define the function h(x) := ∑ 1≤i<j≤p max{aTi x+ bi, aTj x+ bj} and let g := f + h. Then, obviously, f = g − h. It remains to show that both g and h are convex CPWL functions with at most p2n+1 pieces.
The convexity of h is clear by definition. Consider the ( p 2 ) = p(p−1)2 < p 2 hyperplanes given by aTi x+ bi = a T j x+ bj , 1 ≤ i < j ≤ p. They divide Rn into at most ( p2
n
) + ( p2 n−1 ) + · · ·+ ( p2 0 ) ≤ p2n
regions (compare Edelsbrunner [1987, Theorem 1.3]) in each of which h is affine. In particular, h has at most p2n ≤ p2n+1 pieces. Next, we show that g = f + h is convex. Intuitively, this holds because each possible breaking hyperplane of f is made convex by adding h. To make this formal, note that by the definition of convexity, it suffices to show that g is convex along each affine line. For this purpose, consider an arbitrary line x(t) = ta+b, t ∈ R, given by a ∈ Rn and b ∈ R. Let f̃(t) := f(x(t)), g̃(t) := g(x(t)), and h̃(t) := h(x(t)). We need to show that g̃ : R→ R is a convex function. Observe that f̃ , g̃, and h̃ are clearly one-dimensional CPWL functions with the property g̃ = f̃ + h̃. Hence, it suffices to show that g̃ is convex locally around each of its breakpoints. Let t ∈ R be an arbitrary breakpoint of g̃. If f̃ is already convex locally around t, then the same holds for g̃ as well since h̃ inherits convexity from h. Now suppose that t is a nonconvex breakpoint of f̃ . Then there exist two distinct pieces of f , indexed by i, j ∈ [p] with i 6= j, such that f̃(t′) = min{aTi x(t′) + bi, aTj x(t′) + bj} for all t′ sufficiently close to t. By construction, h̃(t′) contains the summand max{aTi x(t′)+bi, aTj x(t′)+bj}. Thus, adding this summand to f̃ linearizes the nonconvex breakpoint of f̃ , while adding all the other summands preserves convexity. In total, g̃ is convex locally around t, which finishes the proof that g is a convex function.
Finally, observe that pieces of g = f + h are always intersections of pieces of f and h, for which we have only p · p2n = p2n+1 possibilities.
Having this, we may conclude the following.
Theorem 4.4. Let f : Rn → R be a CPWL function with p affine pieces. Then f can be represented by a ReLU NN with depth dlog2(n+ 1)e+ 1 and width O(p2n 2+3n+1).
Proof. Consider the decomposition f = g − h from Proposition 4.3. Using Theorem 4.2, we obtain that both g and h can be represented with the required depth dlog2(n + 1)e + 1 and with width O((p2n+1)n+1) = O(p2n2+3n+1). Thus, the same holds for f .

heading: 4.3 Extended Newton Polyhedra of Convex CPWL Functions

text:
For our proof of Theorem 4.1, we use a correspondence of convex CPWL functions with certain polyhedra, which are known as (extended) Newton polyhedra in tropical geometry [Maclagan and Sturmfels, 2015]. These relations between tropical geometry and neural networks have previously been applied to investigate expressivity of NNs; compare our references in the introduction.
In order to formalize this correspondence, let CCPWLn ⊆ CPWLn be the set of convex CPWL functions of type Rn → R. For f(x) = max{aTi x + bi | i ∈ [p]} in CCPWLn, we define its so-called extended Newton polyhedron to be
N (f) := conv({(ai, bi) ∈ Rn × R | i ∈ [p]}) + cone({−en+1}) ⊆ Rn+1.
We denote the set of all possible extended Newton polyhedra in Rn+1 as Newtn. That is, Newtn is the set of (unbounded) polyhedra in Rn+1 that emerge from a polytope by adding the negative of the (n+ 1)-st unit vector −en+1 as an extreme ray. Hence, a set P ⊆ Rn+1 is an element of Newtn if and only if P can be written as P = conv({(ai, bi) ∈ Rn × R | i ∈ [p]}) + cone({−en+1}). Conversely, for a polyhedron P ∈ Newtn of this form, let F(P ) ∈ CCPWLn be the function defined by F(P )(x) = max{aTi x+ bi | i ∈ [p]}. There is an intuitive way of thinking about the extended Newton polyhedron P of a convex CPWL function f : it consists of all hyperplane coefficients (a, b) ∈ Rn × R such that aTx+ b ≤ f(x) for all x ∈ Rn. This also explains why we add the extreme ray −en+1: decreasing b obviously maintains the property of aTx+ b being a lower bound on the function f .
We need the notion of the Minkowski sum of two polyhedra P and Q: it is given as the set P +Q = {p+ q | p ∈ P, q ∈ Q}. In fact, there is a one-to-one correspondence between elements of CCPWLn and Newtn, which is nicely compatible with some (functional and polyhedral) operations. This correspondence has been studied before in tropical geometry [Maclagan and Sturmfels, 2015, Joswig, 2022], convex geometry1 [Hiriart-Urruty and Lemaréchal, 1993], as well as neural network literature [Zhang et al., 2018, Charisopoulos and Maragos, 2018, Alfarra et al., 2020, Montúfar et al., 2021]. We summarize the key findings of this correspondence relevant to our work in the following proposition: Proposition 4.5. Let n ∈ N and f1, f2 ∈ CCPWLn. Then it holds that
(i) the functions N : CCPWLn → Newtn and F : Newtn → CCPWLn are well-defined, that is, their output is independent from the representation of the input by pieces or vertices, respectively,
(ii) N and F are bijections and inverse to each other,
(iii) N (max{f1, f2}) = conv(N (f1),N (f2)) := conv(N (f1) ∪N (f2)),
(iv) N (f1 + f2) = N (f1) +N (f2), where the + on the right-hand side is Minkowski addition.
An algebraic way of phrasing this proposition is as follows: N and F are isomorphisms between the semirings (CCPWLn,max,+) and (Newtn, conv,+).

heading: 4.4 Outline of the Proof of Theorem 4.1

text:
We prove Theorem 4.1 in full detail in Appendix D. The rough idea is as follows.
Suppose we have a p-term max function f with p ≥ n + 2. By Proposition 4.5, f corresponds to a polyhedron P ∈ Newtn with at least n + 2 vertices. Applying a classical result from discrete geometry known as Radon’s theorem allows us to carefully decompose P into a “signed”2 Minkowski sum of polyhedra in Newtn whose vertices are subsets of at most p− 1 out of the p vertices of P . Translating this back into the world of CPWL functions by Proposition 4.5 yields that f can be written as linear combination of p′-term maxima with p′ < p, where each of them involves a subset of
1N (f) is the negative of the epigraph of the convex conjugate of f . 2Some polyhedra may occur with “negative” coefficents in that sum, meaning that they are actually added to P instead of the other polyhedra. The corresponding CPWL functions will then have negative coefficients in the linear combination representing f .
the p affine terms of f . We can then obtain Theorem 4.1 by iterating until every occurring maximum expression involves at most n+ 1 terms.

heading: 4.5 Potential Approaches to Show Lower Bounds on the Width

text:
In light of the upper width bounds shown in this section, a natural question to ask is whether also meaningful lower bounds can be achieved. This would mean constructing a family of CPWL functions with p pieces defined on Rn (with different values of p and n), for which we can prove that a large width is required to represent these functions with NNs of depth dlog2(n+ 1)e+ 1. A trivial and not very satisfying answer follows, e.g., from Raghu et al. [2017] or Serra et al. [2018]: for fixed input dimension n, they show that a function computed by an NN with k hidden layers and width w has at most O(wkn) pieces. For our setting, this means that an NN with logarithmic depth needs a width of at least O(p1/(n logn)) to represent a function with p pieces. This is, of course, very far away from our upper bounds.
Similar upper bounds on the number of pieces have been proven by many other authors and are often used to show depth-width tradeoffs [Montúfar et al., 2014, 2021, Pascanu et al., 2014, Telgarsky, 2016b, Arora et al., 2018]. However, there is a good reason why all these results only give rise to very trivial lower bounds for our setting: the focus is always on functions with very many pieces, which then, consequently, need many neurons to be represented (with small depth). However, since the lower bounds we strive for depend on the number of pieces, we would need to construct a family of functions with comparably few pieces that still need very many neurons to be represented. In general, it seems to be a tough task to argue why such functions should exist.
A different approach could leverage methods from complexity theory, in particular from circuit complexity. Neural networks are basically arithmetic circuits with very special operations allowed. In fact, they can be seen as a tropical variant of arithmetic circuits. Showing circuit lower bounds is a notoriously difficult task in complexity theory, but maybe some conditional result (based on common conjectures similar to P 6= NP) could be established. We think that the question whether our bounds are tight, or whether at least some non-trivial lower bounds on the width for NNs with logarithmic depth can be shown, is an exciting question for further research.

heading: 5 Discussion of Future Research Directions

text:
The most obvious and, at the same time, most exciting open research question is to prove or disprove Conjecture 1.1, or equivalently Conjecture 1.2. The first step could be to prove Assumption 2.4. The assumption is intuitive because every breakpoint introduced at other places needs to be canceled out later. Therefore, it is natural to assume that these breakpoints do not have to be introduced in the first place. However, this intuition does not seem to be enough for a formal proof because it could occur that additional breakpoints in intermediate steps, which are canceled out later, also influence the behavior of the function at other places where we allow breakpoints in the end.
Another step towards resolving our conjecture may be to find an alternative proof of Theorem 2.5 not using Assumption 2.4. This might also be beneficial for generalizing our techniques to more hidden layers, since, while theoretically possible, a direct generalization is infeasible due to computational limitations.
In light of our results from Section 3, it would be desirable to provide a complete characterization of the functions contained in ReLU(k). Another potential research goal is improving our upper bounds on the width from Section 4 and/or proving matching lower bounds as discussed in Section 4.5.
Some more interesting research directions are the following: 1. Establishing or strengthening our results for special classes of NNs like recurrent neural networks (RNNs) or convolutional neural networks (CNNs), 2. Using exact representation results to show more drastic depth-width tradeoffs compared to existing results in the literature, 3. Understanding how the class ReLU(k) changes when a polynomial upper bound is imposed on the width of the NN; see related work by Vardi et al. [2021].
Acknowledgments and Disclosure of Funding
Christoph Hertrich gratefully acknowledges funding by DFG-GRK 2434 “Facets of Complexity”. Amitabh Basu gratefully acknowledges support from AFOSR Grant FA95502010341 and NSF Grant CCF2006587. Martin Skutella gratefully acknowledges funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy — The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

title: Towards Lower Bounds on the Depth of ReLU Neural Networks