Computer Science 2021 Hari Sundaram Associate Professor Hari Sundaram, Chair
Professor Jiawei Han
Associate Professor Hanghang Tong
Dr. Neil Shah, Senior Research Scientist at Snap Inc.

# Sparsity-Aware Neural User Behavior Modeling in Online Interaction Platforms

Aravind Sankar

###### Abstract

Modern online platforms offer users an opportunity to participate in a variety
of content-creation, social networking, and shopping activities. With the
rapid proliferation of such online services, learning data-driven user
behavior models is indispensable to enable personalized user experiences.
Recently, representation learning has emerged as an effective strategy for
user modeling, powered by neural networks trained over large volumes of
interaction data. Despite their enormous potential, we encounter the unique
challenge of data sparsity for a vast majority of entities, e.g., sparsity in
ground-truth labels for entities and in entity-level interactions (cold-start
users, items in the long-tail, and ephemeral groups).

In this dissertation, we develop generalizable neural representation learning
frameworks for user behavior modeling designed to address different sparsity
challenges across applications. Our problem settings span transductive and
inductive learning scenarios, where transductive learning models entities seen
during training and inductive learning targets entities that are only observed
during inference. We leverage different facets of information reflecting user
behavior (e.g., interconnectivity in social networks, temporal and attributed
interaction information) to enable personalized inference at scale. Our
proposed models are complementary to concurrent advances in neural
architectural choices and are adaptive to the rapid addition of new
applications in online platforms.

First, we examine two transductive learning settings: inference and
recommendation in graph-structured and bipartite user-item interactions. In
chapter 3, we formulate user profiling in social platforms as semi-supervised
learning over graphs given sparse ground-truth labels for node attributes. We
present a graph neural network framework that exploits higher-order
connectivity structures (network motifs) to learn attributed structural roles
of nodes that identify structurally similar nodes with co-varying local
attributes. In chapter 4, we design neural collaborative filtering models for
few-shot recommendations over user-item interactions. To address item
interaction sparsity due to heavy-tailed distributions, our proposed meta-
learning framework learns-to-recommend few-shot items by knowledge transfer
from arbitrary base recommenders. We show that our framework consistently
outperforms state-of-art approaches on overall recommendation (by 5% Recall)
while achieving significant gains (of 60-80% Recall) for tail items with fewer
than 20 interactions.

Next, we explored three inductive learning settings: modeling spread of user-
generated content in social networks; item recommendations for ephemeral
groups; and friend ranking in large-scale social platforms. In chapter 5, we
focus on diffusion prediction in social networks where a vast population of
users rarely post content. We introduce a deep generative modeling framework
that models users as probability distributions in the latent space with
variational priors parameterized by graph neural networks. Our approach
enables massive performance gains (over 150% recall) for users with sparse
activities, while being faster than state-of-the-art neural models by an order
of magnitude. In chapter 6, we examine item recommendations for ephemeral
groups with limited or no historical interactions together. To overcome group
interaction sparsity, we present self-supervised learning strategies that
exploit the preference co-variance in observed group memberships for group
recommender training. Our framework achieves significant performance gains
(over 30% NDCG) over prior state-of-the-art group recommendation models. In
chapter 7, we introduce multi-modal inference with graph neural networks that
captures knowledge from multiple feature modalities and user interactions for
multi-faceted friend ranking. Our approach achieves notable higher performance
gains for critical populations of less-active and low-degree users.

###### Acknowledgements.

There are so many people who contributed to my Ph.D. journey at the University
of Illinois, Urbana-Champaign (UIUC). First and foremost, I would like to
thank my advisor, Professor Hari Sundaram, whose guidance and encouragement
has been instrumental in shaping this dissertation. I am ever-grateful to Hari
for taking me as a student, his kindness and genuine interest in my mental and
physical well-being meant a lot to me during my initial Ph.D. years. Hari
taught me invaluable art of technical writing – the ability to express
sophisticated concepts in a simplified and accessible language without missing
out on the essential details. His guidance has greatly influenced how I
envision the big picture and impact of a research problem, and enhanced my
ability to relate and connect ideas across different research areas. He has
also been incredibly supportive of my independent research pursuits with other
professors and external collaborators. Over the years, he has been integral in
shaping me into the researcher that I have become, and I would be fortunate to
work with him again in the future. I also want to thank my other thesis
committee members, Professor Jiawei Han, Professor Hanghang Tong, and Dr. Neil
Shah. I would especially like to thank Jiawei for his kind words of
encouragement during my uncertain moments. His courses laid the foundation for
my foray into data mining, and my numerous collaborations with him and other
students from his research group have contributed immensely to different
threads of work in this thesis. I am thankful to Hanghang for his insightful
questions and feedback during my thesis proposal, which were greatly
instructive and helpful in the direction of this work. I am also immensely
grateful to Neil Shah for his guidance during my internship at Snap, which
motivated me to explore practically impactful implications of my research
beyond publishing objectives. Despite the fully remote internship experience,
I had an awesome time working with Neil, and got to know how much fun research
in the industry can be. I would also like to thank Yanhong Wu for his guidance
and encouragement during my two summers that I spent at Visa Research. Yanhong
went above and beyond his mandated responsibilities to mentor me, and spent
countless hours outside of his regular work schedule to assist me with
additional experiments and paper writing after the end of my internship. I’m
extremely fortunate to have been advised by my undergraduate thesis advisors
Professors Sayan Ranu and Karthik Raman at Indian Institute of Technology
Madras (IIT-Madras). Even after I moved to the U.S. for my Ph.D. studies, they
actively continued mentoring me to ensure that our work reached its best
possible conclusion with a publication in a top bioinformatics journal.
Without their efforts in instructing and mentoring me at different levels, I
could not have possibly had the opportunities that led me to UIUC. I would
also like to acknowledge my colleagues at Crowd Dynamics Lab for their
numerous research discussions, constructive feedback, and collaborations that
have shaped my work. A big shout out to my research collaborators Junting
Wang, Adit Krishnan, and Xinyang Zhang, who have closely worked with me on
several projects. Finally, I am forever indebted to my parents, sister, and
brother-in-law for their unwavering love and support through the ups and downs
of my Ph.D. journey.

###### Contents

  1. 1 Introduction
    1. 1.1 Introduction
    2. 1.2 Technical Challenges
    3. 1.3 Transductive User Behavior Modeling
      1. 1.3.1 Higher-Order Structures in Graph-based Interactions
      2. 1.3.2 Few-shot Collaborative Filtering via Meta-Transfer
    4. 1.4 Inductive User Behavior Modeling
      1. 1.4.1 Social Regularization to Predict Information Diffusion
      2. 1.4.2 Self-supervised Ephemeral Group Interaction Modeling
      3. 1.4.3 Multi-Faceted Friend Ranking in Social Platforms
    5. 1.5 Thesis Organization
  2. 2 Literature Review
    1. 2.1 Social Network Mining
      1. 2.1.1 Static Graph Representation Learning
      2. 2.1.2 Temporal User Behavior Modeling
    2. 2.2 Recommender Systems
      1. 2.2.1 Collaborative Filtering
      2. 2.2.2 Group Recommendation
    3. 2.3 Relevant Machine Learning Paradigms
      1. 2.3.1 Semi-supervised Learning
      2. 2.3.2 Deep Generative Modeling
      3. 2.3.3 Self-supervised Learning
      4. 2.3.4 Few-shot Learning and Meta-Learning
  3. 3 InfoMotif: Higher-Order Structures in Graph-based Interactions
    1. 3.1 Introduction
    2. 3.2 Preliminaries
      1. 3.2.1 Problem Definition
      2. 3.2.2 Graph Neural Networks
      3. 3.2.3 Network Motifs
      4. 3.2.4 Model Regularization
    3. 3.3 InfoMotif Framework
      1. 3.3.1 Motivating Insights: Attributed Structural Roles
      2. 3.3.2 Self-supervised Single Motif Regularization
      3. 3.3.3 Multi-Motif Regularization Framework
    4. 3.4 Model Details
      1. 3.4.1 Motif Gating
      2. 3.4.2 Motif Instance Encoder
      3. 3.4.3 Motif Readout
      4. 3.4.4 Motif Discriminator
    5. 3.5 Experiments
      1. 3.5.1 Datasets
      2. 3.5.2 Baselines
      3. 3.5.3 Experimental Setup
      4. 3.5.4 Homogeneous Graphs ($\text{RQ}_{1}$)
      5. 3.5.5 Heterogeneous Graphs ($\text{RQ}_{2}$)
      6. 3.5.6 Model Ablation Study ($\text{RQ}_{3}$)
      7. 3.5.7 Qualitative Analysis ($\text{RQ}_{4}$)
      8. 3.5.8 Parameter Sensitivity
      9. 3.5.9 Efficiency Analysis
    6. 3.6 Discussion
    7. 3.7 Related Work
    8. 3.8 Conclusion
  4. 4 ProtoCF: Few-shot Collaborative Filtering via Meta-Transfer
    1. 4.1 Introduction
    2. 4.2 Problem Definition
    3. 4.3 Related Work
    4. 4.4 ProtoCF Framework
      1. 4.4.1 Neural Base Recommender
      2. 4.4.2 Few-shot Item Recommendation
      3. 4.4.3 Model Details
    5. 4.5 Experiments
      1. 4.5.1 Datasets
      2. 4.5.2 Baselines
      3. 4.5.3 Experimental Setup
      4. 4.5.4 Overall Recommendation Results ($\text{RQ}_{1}$)
      5. 4.5.5 Few-Shot Recommendation Results ($\text{RQ}_{2}$)
      6. 4.5.6 Model Ablation Study ($\text{RQ}_{3}$)
      7. 4.5.7 Parameter Sensitivity ($\text{RQ}_{4}$)
      8. 4.5.8 Discussion
    6. 4.6 Conclusion
  5. 5 InfVAE: Social Regularization to Predict Information Diffusion
    1. 5.1 Introduction
    2. 5.2 Related Work
    3. 5.3 Problem Definition
    4. 5.4 InfVAE Framework
      1. 5.4.1 Generative Model Description
      2. 5.4.2 Model Likelihood
      3. 5.4.3 Neural Graph Autoencoder Details
      4. 5.4.4 Model Inference
      5. 5.4.5 Model Objective Derivation
    5. 5.5 Experiments
      1. 5.5.1 Baselines
      2. 5.5.2 Experimental Setup
      3. 5.5.3 Evaluation Metric Definitions
      4. 5.5.4 Experimental Results
      5. 5.5.5 Impact of Social and Interaction Sparsity
      6. 5.5.6 Model Analysis
    6. 5.6 Acknowledgements
    7. 5.7 Conclusion
  6. 6 GroupIM: Self-supervised Ephemeral Group Interaction Modeling
    1. 6.1 Introduction
    2. 6.2 Related Work
    3. 6.3 Preliminaries
      1. 6.3.1 Problem Definition
      2. 6.3.2 Base Neural Group Recommender
      3. 6.3.3 Motivation
    4. 6.4 GroupIM Framework
      1. 6.4.1 Mutual Information Maximization.
      2. 6.4.2 User-Group MI Maximization.
      3. 6.4.3 Contextual User Preference Weighting
      4. 6.4.4 Model Details
    5. 6.5 Experiments
      1. 6.5.1 Datasets
      2. 6.5.2 Baselines
      3. 6.5.3 Experimental Setup
      4. 6.5.4 Experimental Results
      5. 6.5.5 Model Analysis
      6. 6.5.6 Impact of Group Characteristics
      7. 6.5.7 Qualitative MI Discriminator Analysis
      8. 6.5.8 Sensitivity Analysis
      9. 6.5.9 Limitations
    6. 6.6 Conclusion
  7. 7 GraFRank: Multi-Faceted Friend Ranking in Social Platforms
    1. 7.1 Introduction
    2. 7.2 Related Work
    3. 7.3 Preliminaries
      1. 7.3.1 Problem Formulation
      2. 7.3.2 Background on GNNs
    4. 7.4 Graph Neural Friend Ranking
      1. 7.4.1 Motivating Insight: Modality Analysis
      2. 7.4.2 GraFRank: Multi-Faceted Friend Ranking
      3. 7.4.3 Model Training
    5. 7.5 Experiments
      1. 7.5.1 Experimental Setup
      2. 7.5.2 Baselines
      3. 7.5.3 Experimental Results
      4. 7.5.4 Ablation Study ($\text{RQ}_{3}$)
      5. 7.5.5 Training and Sensitivity Analysis ($\text{RQ}_{4}$)
      6. 7.5.6 User Cohort Analysis ($\text{RQ}_{5}$)
    6. 7.6 Conclusion
  8. 8 Conclusions and Future Directions
    1. 8.1 Research Contributions
      1. 8.1.1 Technical Challenges
      2. 8.1.2 Transductive User Behavior Modeling
      3. 8.1.3 Inductive User Behavior Modeling
      4. 8.1.4 Summary of Learning Paradigms
    2. 8.2 Future Work
      1. 8.2.1 Extensions to our Frameworks
      2. 8.2.2 Broader Research Challenges beyond Sparsity

##  Chapter 1 Introduction

###  1.1 Introduction

In recent times, users participate in a multitude of content-creation, social
networking and e-commerce platforms, with diverse interactional settings. User
behavior is characterized by their activities and interactions with other
users and functionalities within the platform. For instance, users in social
networking platforms (such as Facebook and Snapchat) form friendships where
they communicate with friends, post or re-share user-generated content, and
interact in diverse groups. In e-commerce platforms (such as Amazon and
Walmart), users browse, view, and purchase products and often create product
reviews. With the rapid growth and pervasiveness of such online platforms,
learning data-driven models of user behavior is indispensable to enable highly
personalized user experiences.

Modeling user behavior in online interactional platforms poses exciting new
challenges in handling behavioral data at the scale of over millions of
entities (e.g., users, content, groups, etc.). First, data sparsity, despite
the enormous potential to learn nuanced behavioral patterns from massive
interaction logs, a fundamental challenge is data sparsity for a vast majority
of entities towards model learning. Second, interaction heterogeneity, users
participate in diverse interactional scenarios, including structural graph
connectivity in social networks, bipartite user-item interactions in
e-commerce platforms, and multipartite user-group-item interactions in group
activities. Sparsity challenges manifest in a variety of different ways, e.g.,
a substantial fraction of users in social networks are inactive with limited
structural and engagement information [1]; further, ground-truth labels are
typically very limited and expensive to obtain in large-scale platforms.
Similarly, we encounter interaction sparsity for a large proportion of the
item inventory in rapidly expanding e-commerce platforms [2]. Modeling user
behavior in the face of sparsity challenges across different interactional
scenarios, is critical to personalize experiences for diverse user
populations.

Recently, neural representation learning, powered by deep neural network
architectures, has emerged as one of the most promising approaches for user
modeling, with state-of-the-art performance in several established benchmarks
and widespread adoption in various industrial settings, e.g., video
recommendations on YouTube [3], personalized search ranking and listing
recommendations at AirBnb [4], related pin recommendations on Pinterest [5, 6]
etc. Neural networks have the representational capacity to learn sophisticated
behavioral patterns from extensive volumes of data without the need for manual
feature engineering. However, developing sparsity-aware neural user modeling
frameworks to enable personalized inference at scale is important,
challenging, and has remained largely beyond reach.

In this thesis, we develop neural representation learning frameworks to
characterize user behavior in online interactional platforms, broadly divided
into transductive and inductive learning scenarios. Transductive learning
involves behavior modeling and prediction for entities seen during model
training, while inductive learning concerns unseen entities that are only
observed during inference. We design neural user modeling frameworks with two
desirable properties, sparsity-awareness: we leverage different facets of
information reflecting user behavior (e.g., interconnectivity in social
networks, temporal and attributed interaction information) to enable
personalized behavior inference at scale in the face of interaction sparsity;
generalizability: we present architecture-agnostic frameworks with
generalizable learning strategies; our models are complementary to concurrent
advances in neural architectural choices and are adaptive to the rapid
addition of new applications in online platforms.

###  1.2 Technical Challenges

Designing neural user modeling frameworks poses several technical challenges
in handling the massive scale of behavioral data and the diversity of
interaction types involving over millions of entities. Despite the potential
to learn neural models that harness massive interaction logs, a central theme
of this dissertation is addressing data sparsity challenges that manifest in
different ways across applications, which are briefly summarized below:

Ground-truth Label Sparsity: In large-scale online platforms, we typically
have access to very limited ground-truth labels for entity attributes, e.g.,
age, gender of users in social networks or aspect ratings of products in
e-commerce platforms.

Entity-level Interaction Sparsity: Heavy-tailed distributions in user
interests and interaction patterns are commonly observed in user behavioral
data [7] across several online platforms. Despite the availability of
behavioral data at massive scales, we have very limited historical records at
the granularity of individual entities due to the highly skewed interaction
distribution. Thus, learning meaningful trends or insights for a vast majority
of entities is challenging due to entity-level interaction sparsity.

Feature Diversity and Skew: In inductive learning applications, entities are
often represented using a combination of diverse features, e.g., user features
in social networking platforms may include static profile attributes, dynamic
communication and engagement activities, while item features in e-commerce
platforms may include textual descriptions, product reviews, and other
attributes (such as brand or price). Here, the key modeling challenges are
feature heterogeneity and skew: the features often belong to different
modalities and exhibit non-trivial correlations; we also observe skewed
occurrences of features across different entities.

In this dissertation, we primarily develop architecture-agnostic frameworks
for user behavior modeling, with generalizable learning strategies that are
targeted towards addressing the aforementioned sparsity challenges. Our
learning frameworks enable personalized inference at scale for broad
application scenarios across diverse platforms. Furthermore, we also present
an example of a specific deep learning architecture design that effectively
handles sparsity concerns in a large-scale industrial application.

Our problem settings span transductive and inductive learning scenarios, where
transductive learning models behavior of entities seen during training and
inductive learning targets unseen entities that are only observed during
inference. Thus, our key research contributions are also organized below into
transductive and inductive user behavior modeling applications.

###  1.3 Transductive User Behavior Modeling

In this part, we explore two fundamental transductive interactional scenarios
with access to interactions/connectivity information of all participating
entities during model training.

First, we consider a graph-structured data representation to model
interactions between various entities, such as how users connect and
communicate with each other in social networks, or how they purchase and rate
products in e-commerce platforms. We examine transductive or semi-supervised
learning given structural graph connectivity between the interacting entities
and a few manually labeled examples. This is a natural way to formulate user
profiling in online platforms given sparse ground-truth labels for a certain
attribute (e.g., age, gender), and the goal is to exploit the graph-structured
interactions to infer the attribute for the remaining users. In Chapter 3, we
leverage higher-order network structures to develop a semi-supervised learning
framework (InfoMotif) over graphs.

We then investigate the bipartite user-item interactional setting, which is
the foundation for a wide variety of Collaborative Filtering (CF) methods [8]
that personalize item recommendations based on historical user interactions. A
close examination of prior neural recommendation models reveals poor accuracy
levels for the vast majority of items (with sparse interactions) in the item
inventory [9, 2]. In Chapter 4, we introduce a few-shot learning framework
(ProtoCF) that extracts and transfers meta-knowledge from data-rich head
entities (such as popular items), to enable accurate personalized
recommendations for data-poor tail entities (such as long-tail items) with
severe interaction sparsity.

####  1.3.1 Higher-Order Structures in Graph-based Interactions

Graph Neural Networks (GNNs) have emerged as a popular paradigm for semi-
supervised learning on graphs given a few labeled examples, and have recently
enabled substantial advances due to their ability to learn node
representations combining graph structure and node/link attributes. Localized
message passing between neighboring nodes is the basis of node representation
learning in graphs, including the popular GNN models. We identify two key
imitations due to localized message passing: over-smoothing (poor resolution
in distinguishing structural node neighborhoods) and localization ($k$-layer
message-passing is restricted to the $k$-hop neighborhood of the labeled
training nodes), which degrade performance of prior GNNs due to limited
availability of labeled information.

To address the limitations of localized message passing, we propose the novel
concept of attributed structural roles, grounded on network motifs, to
regularize arbitrary GNN models for semi-supervised learning. Network motifs
are a general class of higher-order structures (such as dense subgraphs and
cliques) that indicate connectivity patterns between nodes, are crucial for
understanding the organization and properties of complex networks [10]. Our
key hypothesis is that leveraging the higher-order connectivity structures
between nodes is critical to accurately label the nodes, effectively
compensating the lack of sufficient labeled information in the local
neighborhoods. Attributed structural roles identify structurally similar nodes
with co-varying local attributes, independent of network proximity.

In this work, we propose an architecture-agnostic framework (InfoMotif) to
capture attributed structural roles by dynamically prioritizing multiple
motifs in the learning process without relying on distributional assumptions
in the underlying graph or the learning task. Our experiments across a wide
variety of assortative and disassortative networks, indicate significant gains
(3-10% accuracy) for InfoMotif over prior approaches, with stronger gains for
nodes with sparse training labels and diverse attributes in local neighborhood
structures.

####  1.3.2 Few-shot Collaborative Filtering via Meta-Transfer

Neural Collaborative Filtering (NCF) methods have recently revolutionized
modern recommender systems with impressive gains over conventional
collaborative filtering approaches. However, a closer analysis of prior neural
recommendation models reveals skewed performance gains towards popular items
with abundant historical interactions, with poor accuracy levels for a
significant chunk of long-tail (niche) items in the inventory [9, 2].
Moreover, we empirically show that prior neural recommenders lack the
resolution power to accurately rank relevant items within the long-tail owing
to severe interaction sparsity. This restricts personalization and impedes
suppliers of long-tail items in under-represented categories (genres or
styles). Targeting long-tail items can enhance recommendation diversity and
bring relatively larger revenues compared to popular items with competitive
markets.

In this work, we focus on learning to accurately recommend few-shot items with
interaction sparsity. We formulate few-shot item recommendation as a metric-
based meta-learning problem of learning-to-embed items with few interactions.
Our key insight is episodic training to eliminate the interaction distribution
inconsistency between head items (with abundant interactions) and tail items
(with sparse interactions); we enable few-shot generalization by sub-sampling
interactions from head items to mimic tail items during model training.

We propose a meta-learning framework (ProtoCF) that extracts, relates, and
transfers the meta-knowledge learned by a neural base recommender over head
items to learn robust and discriminative latent representations for tail
items. Our experimental results indicate significant gains (Recall@50 gains of
4-20%) for ProtoCF on few-shot personalized item recommendations (with over
70% of the item inventory in the tail) over state-of-art models.

###  1.4 Inductive User Behavior Modeling

In this part, we consider a few diverse inductive interactional scenarios
where modeling user behavior entails new entities that are only observed
during model inference.

First, we examine content re-sharing behavior of users in social micro-
blogging platforms (such as Twitter and Tumblr) where user-generated content
is often noisy and transient with a short lifespan. The spread or diffusion of
user-generated content in social platforms hinges primarily on the contextual
influence of recent re-shares and the extent of social connectivity. In
Chapter 5, we present a social regularization framework (InfVAE) to carefully
model the co-variance of temporal context (recent posting activities) with
structural graph connectivity information, for predicting spread of user-
generated content in social networks.

Next, we study multipartite user interactions (users, groups, items) in
ephemeral group activities where groups have dynamic memberships and sparse
item interactions. Group interactions are becoming increasingly popular in a
variety of contemporary social platforms such as Meetup, Facebook and Snapchat
groups, etc. In Chapter 6, we introduce a self-supervised learning framework
(GroupIM) to generate personalized item recommendations tailored to ephemeral
groups with no previous interactions together.

Finally, we explore multi-faceted user interactions in an industrial social
networking setting with rich multi-modal individual (such as interests,
demographics, etc.) and pairwise attributes (such as communications). This is
common in modern online platforms that routinely track many aspects of user
behavior across different functionalities to gain multi-faceted insights. In
Chapter 7, we present our inductive learning approach (GraFRank) that
incorporates multi-modal features to successfully overcome sparsity challenges
for less-active and low-degree users, in the industrially ubiquitous
application of friend suggestion in social platforms. We briefly summarize our
key technical contributions below.

####  1.4.1 Social Regularization to Predict Information Diffusion

Modeling the spread or diffusion of information through content posting or re-
sharing on social media platforms (such as Twitter, Facebook, etc.) has
widespread applications, including news feed ranking, limiting misinformation
spread, viral marketing, etc. To predict the set of influenced users who re-
share a piece of user-generated content, prior work mainly consider the impact
of temporal user-user influence learned from historical posting activities;
this results in poor predictions for the vast population of passive users who
seldom post content. Incorporating knowledge of social graph connectivity
structures is crucial to overcome sparsity challenges for users with sparse
diffusion interactions.

Social regularization builds on correlation theories such as homophily and
influence. Social homophily [11] suggests stronger ties between users with
shared latent interests, inducing similar behaviors without direct causal
influence; in contrast, temporal influence captures direct peer-to-peer
effects, resulting in temporally correlated diffusion behaviors [12].
Homophily and Influence are fundamentally confounded in observational studies
of diffusion processes [13], which makes it challenging to contextually model
the impact of both factors.

In this work, we propose a social regularization framework (InfVAE) to model
the co-variance of social homophily (indicated by graph connectivity) and
temporal influence (recent posting activities), for predicting diffusion
behaviors. We differentiate diffusion roles of users (influential versus
susceptible) and adopt variational priors to regularize the latent space of
user representations via graph autoencoders designed to preserve structural
connectivity information. Our experiments show significant gains (22% MAP@10)
for InfVAE over state-of-the-art models, with massive gains for users with
sparse diffusion interactions.

####  1.4.2 Self-supervised Ephemeral Group Interaction Modeling

With the emergence of social networking platforms such as Meetup and Facebook
Event, social group activities have gained popularity; it is essential to
provide groups with relevant item recommendations (e.g., restaurant or a
concert). Existing studies target persistent groups which are fixed, stable
groups (e.g., families watching movies) where the members have interacted with
numerous items together as a group. We examine interactions of ephemeral
groups casually formed by ad-hoc users with limited or no historical
interactions together. Ephemeral group interactions are pervasive in several
real-world scenarios, including dining with strangers, traveling in group
tours, and attending social events.

To address group interaction sparsity, our key technical insight is to exploit
the preference covariance among group members and contextually prioritize
their individual preferences, to make group recommendations. In contrast to
prior work that design customized group preference aggregators, we achieve
inductive generalization to ephemeral groups by designing self-supervised
learning objectives to regularize base neural group recommenders with
arbitrary individual preference encoders and group preference aggregators.

In this work, we present a self-supervised learning framework (GroupIM) that
relies on mutual information estimation and maximization over group
memberships, to overcome group interaction sparsity for ephemeral group
recommendation. Empirically, GroupIM achieves significant performance gains
(31-62% NDCG@20) over state-of-the-art group recommendation models, and is
particularly effective for large and diverse groups.

####  1.4.3 Multi-Faceted Friend Ranking in Social Platforms

Graph Representation Learning methods (including GNNs), have recently advanced
graph learning in multiple prominent academic applications, such as link
prediction, community discovery, and node classification. Most prior
transductive learning approaches directly learn latent representations per
node, resulting in prohibitive model sizes for large-scale social networks
with over multiple millions of users. It is vital to develop inductive
learning techniques for large-scale social modeling applications where users
interact with different functionalities, communicate with diverse groups, and
have multifaceted interaction patterns.

In this work, we consider the industrially ubiquitous application of friend
suggestions (recommending new candidate users to befriend) in social
platforms. Compared to academic datasets, sparsity challenges are also
typically exacerbated in industrial settings owing to the significant fraction
of inactive users with limited structural and engagement information. To
overcome structural and interactional sparsity, we exploit the rich knowledge
of in-platform user actions to formulate friend suggestion as multi-faceted
friend ranking on an evolving friendship graph, with multi-modal user features
and link communication features.

We design a graph neural network architecture (GraFRank) that captures
knowledge from multiple correlated feature modalities and user-user
interactions to learn multi-faceted user representations for friend ranking.
GraFRank outperforms state-of-the-art baselines on friend candidate retrieval
(by 30% MRR) and ranking (by 20% MRR) tasks. Notably, GraFRank achieves higher
gains for the critical population of less-active and low-degree users, and is
currently being implemented by Snapchat to enhance their quick-add feature.

###  1.5 Thesis Organization

This thesis is organized in two parts: transductive and inductive user
behavior modeling.

In the first part, we model user behavior in transductive interactional
scenarios where we have access to historical interactions and connectivities
among all participating entities during model training, and the goal is to
infer their missing properties (e.g., profile attributes) or predict future
behaviors (e.g., item purchases) during model inference.

In the second part, we examine inductive interactional scenarios with real-
time behavior prediction for new entities that are only observed during model
inference. This scenario is common when dealing with user-generated content
and new users in social media platforms and ephemeral group interactions with
dynamic memberships (whose members may be together for the first time). Our
primary focus here is the design of efficient sparsity-aware models that
inductively generalize to new transient entities with limited interaction
data. Table 1.1 provides a brief overview of different chapters in this
thesis.

Table 1.2 summarizes the interaction types of user interactions in each
chapter and their associated technical challenges. In chapter 3, we examine
semi-supervised learning over graphs with sparse ground-truth training labels.
We handle entity-level interaction sparsity challenges in Chapter 4 (long-
tailed items), Chapter 5 (long-tailed users), and Chapter 6 (ephemeral
groups). In chapter 7, we further incorporate multi-faceted features and
interactions across different modalities, with skewed distributions across
different users.

Part |  Chapter |  Chapter Title
---|---|---
Transductive User Modeling (Part I) |  Chapter 3 |  Higher-Order Structures in Graph-based Interactions
Chapter 4 |  Few-shot Collaborative Filtering via Meta-Transfer
Inductive User Modeling (Part II) |  Chapter 5 |  Social Regularization to Predict Information Diffusion
Chapter 6 |  Self-supervised Ephemeral Group Interaction Modeling
Chapter 7 |  Multi-Faceted Friend Ranking in Social Platforms
Table 1.1: Thesis Organization into transductive and inductive user modeling.

In this thesis, our user modeling applications operate on a variety of
interaction types, including bipartite user-item interactions (Chapter 4),
multipartite user-group-item interactions (Chapter 6), and graph-structured
interactions (Chapters 3, 5, and 7).

In particular, our graph-based user modeling frameworks, although primarily
targeted at social networks, generalize to a broad class of graphs that
satisfy two key structural properties: scale-free graphs and homophily. These
assumptions directly stem from the inherent nature of human interactions; we
typically expect skewed distributions to be present in interaction data
produced by human activity, resulting in graphs that exhibit a power law
distribution (scale-free); in most user-user interactions networks, similar
users are expected to form social connections (homophily).

However, we note that general graphs that arise in non-social contexts, (e.g.,
transportation networks or brain networks) may exhibit different structural
properties. In such a scenario, it is critical to revisit the inductive biases
in designing graph learning models (e.g., graph embedding methods and graph
neural networks).

Part |  Chapter |  Data Type |  Technical Challenge
---|---|---|---
Transductive User Modeling (Part I) |  Chapter 3 |  Graph Connectivity |  Ground-truth Label Sparsity
Chapter 4 |  Bipartite Interactions |  Entity Interaction Sparsity
Inductive User Modeling (Part II) |  Chapter 5 |  Graph Connectivity |  Entity Interaction Sparsity
Chapter 6 |  Multipartite Interactions |  Entity set Interaction Sparsity
Chapter 7 |  Graph Connectivity |  Entity Interaction Sparsity and Feature Diversity
Table 1.2: Comparison of various technical challenges and data characteristics
across the different thesis chapters.

##  Chapter 2 Literature Review

In this chapter, we provide a broad overview of prior work in user inference
tasks and recommendation methodologies and applications in different
interaction contexts.

First, we discuss related work on user modeling approaches centered around
addressing sparsity challenges in social network analysis and mining
applications. Then, we discuss prior sparsity-aware approaches research
directions in a variety of different recommender systems applications.
Finally, we discuss related work on various learning paradigms, including
semi-supervised learning, deep generative modeling, self-supervised learning,
few-shot learning, and meta-learning, that tackle sparsity challenges in
diverse machine learning domains.

###  2.1 Social Network Mining

There has been a lot of interest in the past on analyzing, characterizing, and
predicting user behavior in online social networking platforms. In this
dissertation, we primarily focus on machine learning techniques for modeling
(understanding and predicting) user behavior in social networks, which are
based on recent advances in representation learning over graphs.

We first briefly review prior work on unsupervised and semi-supervised graph
representation learning techniques, which are targeted at node-level property
inference and link prediction (or completion) applications in static graphs.
Then, we review related work on modeling different kinds of temporally
evolving user behaviors in social networks, including friendship creation,
inter-user interactions, and content-sharing activities.

####  2.1.1 Static Graph Representation Learning

Graph embedding methods learn latent node representations in graphs to capture
the structural properties of a node and its local neighborhoods. Broadly, they
fall into two categories: the first is unsupervised graph embedding models
that learn universal node representations that capture different structural
graph properties (e.g., community, roles, etc.); the second is the class of
semi-supervised learning models that further exploit supervision (e.g.,
ground-truth labels for nodes or links) to learn task-driven graph embeddings.

Unsupervised Graph Representation Learning: There are a number of techniques
that have been proposed to learn unsupervised latent node embeddings. The
earliest techniques such as Principal component analysis [14] and Laplacian
Eigenmaps [15] were based on dimensionality reduction, optimize an objective
over an affinity matrix of the entire graph to maximizes the variance of the
latent representations. Inspired by advances in neural language models such as
word2vec [16], stochastic graph embedding techniques such as Deepwalk [17] and
node2vec [18] learn unsupervised embeddings to maximize the likelihood of co-
occurrence of nodes in fixed-length random walks. A related approach is the
design of learning objectives to learn node embeddings that capture different
orders of proximity between nodes in a graph [19, 20, 21].

As an alternative to proximity-preserving objectives to learn graph
embeddings, some methods learn role-aware embeddings that embed structurally
similar nodes close in the latent space, independent of network position [22,
23]; such methods typically utilize structural node features (e.g., node
degrees, motif count statistics) to extend classical proximity-preserving
embedding methods based on random walks [24] and matrix factorization [25].

Neural graph embedding techniques were first introduced in SDNE [26] which
utilized graph autoencoders to learn node embeddings that preserve both local
and graph measures of graph proximity. More generally, the class of graph
autoencoders [26, 27, 28] employ various encoding and decoding architectures
to embed graph structure and learn node embeddings through a variety of
unsupervised training objectives. A few methods extended the above techniques
to also incorporate knowledge of node features (or attributes) in the
embedding learning process [29, 30, 31].

Semi-supervised Graph Representation Learning: Graph-based semi-supervised
learning is a well-studied problem, where the goal is to classify nodes in a
graph given a small set of labeled examples [32]. Traditional methods
propagate labels through linked nodes in the graph based on different
smoothness assumptions [33]. Collective classification techniques [34]
generalize label propagation by further utilizing node features and allowing
more flexible local updates. Semi-supervised variants of graph embedding
techniques include label information in the learning process through
supervised training objectives [35, 36].

Graph Neural Networks: Graph Neural Networks are neural networks over graphs
designed to learn node-level or graph-level representations towards a variety
of learning tasks. Initial GNNs generalized Convolutional Neural Networks
(CNNs) to graphs in the spectral domains; spectral GNNs [37, 38] defined graph
convolutions through the Graph Fourier Transform described by eigenvectors of
the Graph Laplacian. However, spectral methods (being a function of the graph
Laplacian) cannot generalize to graphs with different structural properties.

Message-passing GNNs (spatial) generalize label propagation through localized
message passing over node neighborhoods; they learn node representations by
recursively propagating features (i.e., message passing) from local
neighborhoods through the use of aggregation and activation functions [39].
Graph Convolutional Networks (GCNs) [39] learn degree-weighted neighborhood
aggregators, which can be interpreted as a form of Laplacian smoothing. Many
models generalize GCN with a variety of learnable neighborhood aggregators,
e.g., self-attentions [40], mean and max pooling functions [41]; these
approaches have consistently outperformed proximity-preserving graph embedding
techniques on several benchmarks.

In this dissertation, we identify two key limitations in prior message-passing
GNN architectures: k-hop localization and over-smoothing. A few recent methods
have attempted to address either of these issues. To handle localization, non-
local GNN variants incorporate information from nodes in different localities
via varying influence radii [42], shortest paths [43], and global summaries
[44]. To address over-smoothing, a few methods design structural GCNs via
degree-aware [45] and motif-based aggregators [46, 47]; however, such methods
are highly localized. In chapter 3, we design a learning framework over GNNs
to learn attributed structural roles based on the co-variance of features in
motifs (higher-order connectivity structures), thus simultaneously enhancing
the distinguishability of node representations and identifying structurally
similar nodes independent of graph proximity.

Heterogeneous Graphs: Recent work generalize graph embedding techniques and
graph neural networks to heterogeneous graphs containing nodes and edges of
different types. The key idea is to incorporate structural and semantic
information indicated by meta-path or meta-graph structures. A few popular
heterogeneous graph embedding approaches capture proximity between nodes
connected via meta-paths [48], meta-graphs [49, 50], and meta-path guided
random walks [51, 52]. Heterogeneous graph neural networks conduct message-
passing aggregation over local neighborhoods induced by specific node types
[53, 54], meta-paths [55, 56, 57] and meta-graphs [58]. Despite advances in
modeling rich heterogeneous semantics into message-passing, the key limitation
of localization remains. In our work in chapter 3, we also demonstrate the
benefits of structure role learning (via typed motif structures) in our
framework for heterogeneous graph mining applications.

In addition to reviewing prior graph representation learning models designed
for node property inference or link prediction applications in static graphs,
we also discuss prior work related to modeling temporally evolving user
behaviors in social networks.

####  2.1.2 Temporal User Behavior Modeling

In modern social platforms (such as Facebook, Twitter, and Snapchat), users
participate in a wide variety of temporally evolving interactions, e.g., form
friendships and following connections, post or re-share user-generated
content, communicate with other users, and interact with a variety of
different functionalities within the platform.

In this dissertation, we examine two central applications: modeling temporal
friendship formation (or broadly, temporal link evolution) and the spread (or
diffusion) of user-generated content in social networks. We now review prior
work on these research directions.

Temporal Link Evolution: The earliest methods designed for modeling friendship
formation in social networks were motivated by the principles of homophily
[11] and triadic closure [59]. Initial methods include carefully designed
heuristics to model user-proximity, e.g., path-based Katz centrality [60] or
common neighbor-based Adamic/Adar [61] and learning techniques that exploit
such pairwise features for link ranking [62]. However, heuristic feature
extraction for each potential link is infeasible in large-scale time-evolving
social networks.

Recent methods introduced graph representation learning models over dynamic
graphs, which are commonly represented as a sequence of evolving graph
snapshots at multiple discrete time steps. Such techniques broadly fall into
two categories: the first category includes temporal smoothness methods that
ensure node embedding stability across consecutive time-steps, guided by
triadic closure [63, 64] and incremental models that update embeddings from
the previous time step [65]. However, these methods cannot capture long-range
variations in graph structure, and are inadequate when nodes exhibit vastly
differing evolutionary behaviors. The second category includes dynamic graph
neural networks that model temporal graph evolution; popular approaches
include recurrent methods [66, 67] that capture temporal dynamics via hidden
states to summarize historical snapshots, and self-attentional models [68]
that flexibly weight historical representations.

Despite the recent advances in dynamic GNN architectures, they remain
unexplored for large-scale user-user social modeling applications (such as
friend suggestion) where users exhibit multifaceted behaviors. In chapter 7,
we design dynamic GNNs for the important application of friend suggestion,
through a novel multi-faceted friend ranking formulation with multi-modal user
features and link communication features.

Information Diffusion Modeling: Prior diffusion models in social networks were
designed towards one or more objectives: microscopic diffusion prediction,
which learns a model from social graph connectivity and diffusion cascade
sequences, to predict the next (or final set of) influenced user(s) given a
sequence of initial activated seed users; and macroscopic cascade prediction,
which predicts global properties of information spreading in the social
network, including size, growth, and shape of cascades over time [69]. In this
dissertation, our main focus is modeling individual user behavior; thus, we
focus on microscopic diffusion modeling.

Historically, modeling spread of user-generated content in social networks has
been studied through two seminal diffusion models: Independent Cascade (IC)
[70] and Linear Threshold (LT) [71]; IC models information spreading as
cascades of activations over the network, while LT determines user activations
according to thresholds on incoming neighbor influence. The earliest data-
driven diffusion models extend IC and LT via probabilistic generative models
to incorporate knowledge of topics [72], continuous timestamps [73], user
profiles [74], and community structures [75, 76]. A key limitation of such
methods is the reliance on extensive feature engineering and the limited
modeling capacity of the chosen probability distributions.

Recently, representation learning models have incorporated user influencing
capability and susceptibility in diffusion to learn latent user embeddings
from ordered pairwise co-occurrences in diffusion cascades and social graph
connectivity structures [77, 78, 79, 80]. To handle time-stamped diffusion
cascade sequences, neural diffusion models have generalized sequential models
(such as RNNs and LSTMs) to consider DAG propagation structures by projecting
cascades onto local social neighborhoods [81, 82, 83]. As such, prior
diffusion models capture the temporal correlation in diffusion behaviors based
on activations observed in the cascades, which may be inadequate for the vast
majority of users that seldom post content and appear in very few cascades
(sparse diffusion interactions).

In our work in chapter 5, we address the key challenge of diffusion
interaction sparsity by utilizing variational priors to regularize latent user
representations in diffusion models via variational graph autoencoders
designed to preserve structural connectivity information. By parameterizing
latent space priors through flexible deep generative models, our framework
also generalizes classical probabilistic generative modeling approaches.

###  2.2 Recommender Systems

Recommender systems appear in a variety of e-commerce, advertising, and social
networking applications. This has led to several recent advances in developing
neural recommendation models designed to handle the massive scale and
diversity in user interactions. Our key focus is motivated by the fundamental
data sparsity challenge for the vast majority of entities towards model
learning (owing to heavy-tailed interaction distributions).

In this dissertation, we examine few-shot recommendation settings targeted at
entities with very few interactions. Specifically, we explore sparsity
challenges in personalized item recommendations to users (collaborative
filtering), and groups of users (group recommendation). Below, we review prior
work on collaborative filtering and group recommendation.

####  2.2.1 Collaborative Filtering

Collaborative Filtering (CF) is one of the most popular techniques for user
modeling in recommender systems. First, we briefly discuss classical CF
models, followed by recent advances in neural CF models and techniques that
address interaction sparsity challenges.

Classical Collaborative Filtering: Classical CF models operated on the
explicit feedback setting by formulating a matrix completion problem to infer
the unknown user-item ratings; the key idea towards rating inference is to
derive knowledge from those of “similar” items or “similar” users. There are
two broad classes of techniques: neighborhood based collaborative filtering
[84] and latent-factor matrix factorization [85] models. Neighborhood based CF
models determine similar items (or users) based on their rating similarity or
co-occurrence, and estimate unknown ratings by a weighted average of ratings
over the similar items. Matrix factorization models decompose the user-item
rating matrix into user and item specific latent factors, which are later used
to infer missing ratings via inner products between the user and item latent
factors. The earliest methods designed for implicit feedback data (commonly
observed in massive online interactions), extended matrix factorization models
with different pointwise and pairwise ranking objectives that were designed to
handle missing data using sample re-weighting [86] or negative sampling [87].

Neural Collaborative Filtering: Neural CF models generalize matrix
factorization to parameterize users and items with vectorized representations
and interaction functions that are powered by deep neural networks. To enhance
the embedding layer that generates user and item representations, much effort
has been devoted to examine several modeling choices including latent
embeddings [88], denoising [89] and variational autoencoders [90] and graph
neural networks [5, 91]. Other recent efforts to improve the interaction
function exploit deep learning techniques such as nonlinear neural networks
[88], memory networks [92], factorization machines [93], and euclidean
distance metrics [94], to capture non-linear feature interactions between
users and items. While these neural models learn expressive models to
significantly outperform conventional CF approaches, sparsity concerns owing
to long-tail items and cold-start users remain a critical challenge.

Few-shot and Cold-start Recommendation: Few-shot and cold-start recommendation
are two important and related sub-problems that have received attention in
prior research. Most neural recommendation models do not learn meaningful
latent item (or user) representations in the cold-start and few-shot settings,
where new items (or users) provide either no interactions or a handful of
interactions, respectively. We briefly review prior work in both the few-shot
(commonly known as long-tail) and cold-start recommendation scenarios.

Long-tail challenges in recommender systems arise due to interaction sparsity
for the vast majority of items (and users). Clustering is one popular way to
address interaction sparsity by exploiting modeling group-level information to
account for the lack of entity-level interactions; early methods generate
recommendations over tail items at the granularity of item/user clusters,
e.g., cluster-based smoothing [95], user-item co-clustering [96] and joint
clustering and collaborative filtering [97]. Other efforts leverage item-item
co-occurrence statistics to regularize recommenders, e.g., joint factorization
of an item co-occurrence matrix that shares latent factors with a CF model. In
a few neural recommenders, variational auto-encoders (VAEs) [90, 98] employ
distributional regularization via Gaussian priors on the latent space, and
have effectively alleviated sparsity challenges. Another recent strategy to
alleviate sparsity is data augmentation for items (or users) in the tail via
adversarial regularization [9] or rating generation [99] techniques. However,
adversarial learning is often computationally expensive and does not scale to
massive online platforms. While the few-shot learning problem also appears in
other prediction problems with few-shot classes [100, 101] (given a handful of
samples), the massive scale of interaction data (note that each user/item is a
few-shot instance, unlike few-shot classes) renders these solutions
inapplicable.

In chapter 4, we formulate long-tail item recommendations in the most general
user-item interaction setting, as a few-shot learning problem of learning-to-
recommend few-shot items with very few interactions [102]. Our proposed meta-
learning framework is complementary to advances in neural recommender
architectures and enables flexible adaptation to the tail.

Cold-start recommendation is a related problem that specifically targets new
users or new items with no historical interactions. In such a scenario, the
key idea is to rely on auxiliary side information, e.g., item content [103],
textual reviews [104], contextual factors [105], social connections [106], and
external knowledge graphs [107]. A wide variety of techniques have been
proposed for each of the sub-problems, i.e., content-based collaborative
filtering, review-based recommendation, context-aware recommendation, social
recommendation, and knowledge-aware recommendation respectively. Generalizable
techniques include randomized feature dropouts to enable generalization to
missing inputs [108, 109], and meta-learning frameworks for zero-shot (cold-
start) recommendation. Meta-learning methods for cold-start recommendation
utilize gradient-based parameter adaptation [110, 111, 112, 113, 114], hyper-
parameter initialization [115], and shared layers with user-specific (or item)
parameter adaptation [116, 117, 118]. In this dissertation, we focus on the
few-shot setting without requiring access to any side information to ensure
generalizability; a deeper exploration of different cold-start recommendation
scenarios is an important future direction.

####  2.2.2 Group Recommendation

Group interactions have become increasingly prevalent in a variety of
contemporary social networking platforms such as Meetup, Facebook, and
Snapchat. Prior literature on developing recommender systems to suggest items
relevant to groups of users, can be broadly divided into two categories based
on group types: persistent and ephemeral. Persistent groups have stable
members with rich activity history together, while ephemeral groups comprise
users who interact with very few items together and may appear only during
inference time.

Persistent Group Recommendation: Since persistent groups have stable groups
with rich historical interactions together, previous studies treat groups as
virtual users, and adopt conventional personalized recommendation techniques
to make group recommendations. A few key approaches include genetic algorithm-
based group interaction modeling [119], power balance between group members
towards content selection [120], and deep neural architectures modeling
individual choices and group decisions [121]. applied. However, such methods
cannot handle new groups that are only observed during inference time.

Ephemeral Group Recommendation: Prior efforts focus on investigating different
strategies for aggregating individual preferences and modeling group
interactions. To generate ephemeral group recommendations, they either
aggregate recommendation results (or item scores) for each member, or
aggregate individual member preferences, thus falling into two classes: score
(or late) aggregation [122] and preference (or early) aggregation [123].

The score (or late) aggregation strategies first generate recommendation
results for each group member, and then generate group recommendations by
aggregating these individual results based on static predefined aggregation
strategies. Popular score aggregation strategies include least misery [122],
average [124], maximum satisfaction [125], and relevance and disagreement
[126], inspired by social choice theories [127]. An empirical comparison of
different heuristic strategies [122] has demonstrated the absence of a clear
winner, especially with the variance in group sizes and coherence levels.
However, the hand-crafted heuristics are static modeling hypotheses that
overlook real-world group interactions.

The preference (or early) aggregation strategies first aggregate the
preferences of group members, which are then utilized to produce group
recommendations. The first approaches in this category fuse the profiles (raw
item histories) of members into a group profile and utilize conventional
recommenders to generate group recommendations [128]. Recent approaches
introduced latent-factor models based on probabilistic generative models and
deep neural networks. Probabilistic methods [123, 129] model the group
generative process by considering both the personal preferences and relative
influence of group members, to differentiate their contributions towards group
decisions. Neural methods explore attention mechanisms [130] to learn data-
driven preference aggregators [131, 132, 133] jointly from individual and
group interactions; yet, these models severely suffer from the interaction
sparsity challenges for ephemeral groups, which often results in degenerate
solutions.

In chapter 6, we address interaction sparsity for ephemeral group
recommendation by designing self-supervised learning strategies based on
mutual information estimation and maximization, to regularize arbitrary neural
base group recommenders. In the following section, we review machine learning
paradigms that are relevant to the proposed user behavior modeling approaches
in this dissertation.

###  2.3 Relevant Machine Learning Paradigms

In this dissertation, we address different sparsity challenges that manifest
in online user interactions. Our proposed frameworks and models have deeper
connections to broader machine learning paradigms and their applications in
other domains, including computer vision and natural language. We briefly
review relevant work in semi-supervised learning, deep generative modeling,
self-supervised learning, and few-shot and meta-learning paradigms.

####  2.3.1 Semi-supervised Learning

To account for lack of labeled data in supervised learning tasks, semi-
supervised learning leverages large amounts of unlabeled data to learn
additional structure about the input distribution, with the goal of enhancing
model performance on the learning task. Different modeling assumptions have
been examined in prior work, including label smoothness, low-density (or
clustering), and manifold regularization [32, 134]. One popular approach is
transductive learning that constructs a large graph connecting neighboring
objects (similar data points are connected by an edge), and propagates labels
from the initial labeled set to the unlabeled objects (following label
smoothness assumptions). More recently, graph neural networks [39] generalize
classical label propagation techniques through trainable neighbor aggregation
over feature-rich local node neighborhoods in attributed graphs.

Graph-based semi-supervised learning has enormous potential for social
interaction modeling tasks where users are already connected and typically
satisfy homophily assumptions along several attributes. In this dissertation,
we have designed novel graph neural network frameworks for semi-supervised
learning and ranking over graphs in chapters 3 and 7.

####  2.3.2 Deep Generative Modeling

Deep Generative Models are a powerful class of neural networks that aim to
approximate any kind of data distribution. Variational Autoencoders (VAEs)
[135] and Generative Adversarial Networks (GANs) [136] are the most popular
frameworks for deep generative modeling, and have achieved tremendous success
in several computer vision and natural language processing applications,
including image and video generation [137, 138], editing [139], and
enhancement [140], and text synthesis [141] and summarization [142]. Deep
generative models have recently been examined in graph mining and recommender
systems applications to address sparsity challenges via data augmentation
[99], enhanced hard negative mining [143], and distributional priors on the
latent space [90].

Flexible distribution-aware and data-driven prior regularization enables
better characterization of long-tail and cold-start entities. In chapter 5, we
explored deep generative models for robust behavior modeling in social
networks with sparse user interactions.

####  2.3.3 Self-supervised Learning

To further alleviate sparsity challenges, the recently emerging paradigm of
self-supervised learning defines auxiliary (pretext) tasks which are
formulated using only unlabeled data; solving the pretext task learns
effective latent representations that can benefit a variety of different
learning tasks. The most effective framework is contrastive learning, which
aims to maximizes the agreement between different views of the data, by
contrasting against negative samples. Contrastive learning techniques have
benefited a broad range of computer vision tasks by formulating pretext tasks
directly from local-global contrast [144] or by rotating, cropping, or
colorizing images [145, 146]. Self-supervised learning has also been
effectively utilized in recent natural language representation learning models
by carefully designing pretext texts, e.g., masked word prediction and next
sentence prediction in BERT [147], sentence order prediction in ALBERT [148],
sentence permutation in BART [149] etc.

Despite promising recent advances in self-supervised learning techniques
across computer vision and natural language processing applications, this
paradigm is relatively unexplored in the graph mining and recommendation
domains. In chapter 3, we explore self-supervised learning strategies to train
graph neural networks by exploiting higher-order structures (via network
motifs) to formulate pretext tasks. In chapter 6, we presented a self-
supervised learning framework that utilized group membership structure
learning to overcome group interaction sparsity for ephemeral group
recommendation.

####  2.3.4 Few-shot Learning and Meta-Learning

Few-shot learning is the paradigm of designing models capable of learning new
tasks (e.g., classification tasks) rapidly given a limited number of training
examples; such techniques are useful when training examples are hard to find,
or where the cost of data labeling is high [150]. Recently, meta-learning
(learning to learn) framework has emerged as an effective approach for few-
shot learning. In the meta-learning framework, we learn how to learn (e.g., to
classify) given a set of training tasks with the expectation of generalization
to new tasks that have never been encountered during training time. The
adaptation process is a mini learning session that occurs during inference
time with limited exposure to the new task configurations. There are three
common prior meta-learning modeling approaches: (a) learning an efficient
distance metric (metric-based) [101]; (b) deep neural network (e.g.,
recurrent) with external or internal memory (model-based) [151]; (c) optimize
the model parameters explicitly for fast learning (optimization-based) [152].

Designing meta-learning frameworks to handle interaction sparsity in
recommendation settings poses unique scaling challenges. In chapter 4, we
introduce metric-based meta-learning frameworks for few-shot item
recommendations.

##  Chapter 3 InfoMotif: Higher-Order Structures in Graph-based Interactions

###  3.1 Introduction

In this chapter, we propose a new class of motif-regularized graph neural
networks (GNNs); GNNs have emerged as a popular paradigm for semi-supervised
learning on graphs due to their ability to learn representations combining
topology and attributes, without relying on expensive feature engineering.
GNNs are typically formulated as a message passing framework [153], where the
representation of a node is computed by a GNN layer aggregating features from
its graph neighbors via learnable aggregators. Long-range dependencies are
captured by using $k$ layers to incorporate features from $k$-hop
neighborhoods. GNNs have demonstrated promising results in several application
domains spanning homogeneous graphs (e.g., user-user friendship networks)
comprising nodes and edges of a single type, and heterogeneous graphs (e.g.,
academic citation networks) containing nodes and edges of different types. In
particular, GNNs have achieved state-of-the-art results in several
applications including node classification [39], link prediction [154], and
personalized recommendation [5].

Localized message passing limitations:  We illustrate two key limitations of
prior $k$-layer GNN architectures: $k$-hop localized and over-smoothed
representations (Figure 3.1).

  1. 1.

GNNs, while highly expressive, are inherently localized: a $k$-layer GNN
cannot utilize features of nodes that lie outside the $k$-hop neighborhood of
the labeled training nodes. In Figure 3.1, nodes $a$ and $b$ belong to
different classes. A 2-layer GNN sees unlabeled node $c$ within the
aggregation range of $a$ (class 1) and outside the influence of $b$ (class 2
and more than 2 hops away). Thus, a GNN will more likely label $c$ with class
1 (than class 2). However, in reality, $c$ and $b$ display identical
attributes (node color) in the local structure; a localized GNN fails to
incorporate this factor.

  2. 2.

GNNs with multiple layers learn over-smoothed node representations by
iteratively aggregating neighbor features [155]. In Figure 3.1, nodes $c$ and
$a$ share the same number of neighbors with blue and green attributes;
however, green neighbors of node $a$ form triangles, while blue neighbors of
node $b$ (and $c$) form triangles. Considering local nodal attribute
arrangements, node $c$ is more similar to $b$ than to $a$. The over-smoothing
effect in GNNs obscures this attribute co-variation difference when
classifying node $c$.

Thus, we require a new learning framework over graphs, to overcome the above
key limitations due to localized message passing in popular GNN models.

Figure 3.1: Localized message passing limitations:  A stylized example in a
homogeneous graph with a 2-layer GNN model (node colors indicate node
attributes). Node $a$ is in the 2-hop range of node $c$. Node $c$ does not
receive gradient updates from node $b$ (class 2) since node $b$ is more than 2
hops away. A 2-layer GNN will likely label node $c$ as class 1. Notice that
$c$ is in class 2 since $c$ and $b$ have identical local structure and
attribute co-variation.

One way to overcome these limitations is the paradigm of role discovery [156]
that identifies nodes with structurally similar neighborhoods. In contrast to
the notion of communities defined by network proximity, structural roles
characterize nodes by their local connectivity and subgraph patterns
independent of their location in the network [22]; thus, two nodes with
similar roles may lie in different parts of the graph. Prior role-aware models
learn similar representations for structurally similar nodes while ignoring
nodal attributes [24], i.e., they will assign the same role to nodes $a$ and
$b$ in Figure 3.1 with topologically identical local structures; however,
nodes $a$ and $b$ differ in their local attribute arrangements (blue vs. green
attributes in triangles), and thus belong to different classes. Furthermore,
structural role learning is relatively unexplored in heterogeneous graphs with
typed nodes and edges.

Present Work:  To enable the expressivity to distinguish attributed
structures, we propose the concept of attributed structural roles that
identify structurally similar nodes with co-varying attributes, independent of
network proximity. We ground structural roles on network motifs111The terms
network motif, graphlet, and induced subgraph are used interchangeably in
literature, which are induced subgraph structures over a few nodes (e.g.,
triangles). Networks motifs are a broad class of higher-order structures that
indicate connectivity patterns between nodes, and are crucial for
understanding the organization and properties of complex networks [10]. In
addition, network motifs can be easily generalized to capture type semantics
in rich heterogeneous graphs through heterogeneous (typed) higher-order
structures [157] (also known as metagraphs). Leveraging higher-order
connectivity structures between nodes is extremely valuable to overcome the
lack of sufficient training labels in local neighborhoods during semi-
supervised learning. We define two nodes as sharing attributed structural
roles if they participate in topologically similar motif instances over co-
varying sets of attributes. We note that attribute co-variance permits for
multiple discrete and continuous attributes, rather than stricter notions such
as regular equivalence [22].

We propose InfoMotif, a GNN architecture-agnostic regularization framework
that exploits the co-variance of attributes and motif structures. InfoMotif
learns regularizers based on a set of network motifs, which vary in their
task-specific significance. Specifically, across instances of the same motif
(e.g., a triangle structure), we learn discriminative attribute correlations
to regularize the underlying GNN node representations; this encourages the GNN
to learn statistical correspondences between distant nodes that participate in
similarly attributed instances of that motif. We propose a novel training
curriculum to integrate multiple motif regularizers while attending to motif
types and skewed motif distributions. We summarize our key contributions
below:

Attributed Structural Role Learning: We propose the novel concept of
attributed structural roles to regularize GNN models for semi-supervised
learning over graphs. In contrast to prior role discovery work that identify
structurally similar nodes agnostic to attributes [24], we adopt the paradigm
of self-supervised learning to regularize node representations to capture
attribute correlations in motif structures. Our framework InfoMotif unifies
the expressive local neighborhood aggregation power of message-passing GNNs
with the paradigm of structural role discovery.

Architecture-agnostic Regularization Framework: To the best of our knowledge,
InfoMotif is the first to address the limitations of localized message passing
in GNNs through an architecture-agnostic framework. Unlike prior attempts that
design new aggregators [45, 42], we achieve architecture independence by
modulating the node representations learned by the base GNN through motif-
based mutual information maximization, to capture attributed structural roles.
We regularize three state-of-the-art GNNs within our framework to demonstrate
significant performance gains.

Distribution-agnostic Multi-Motif Curriculum: We propose two learning progress
indicators, task-driven utility and distributional novelty, to integrate
multiple motif regularizers within our InfoMotifframework. Unlike prior
strategies [33, 158] that incorporate regularizers via tunable hyper-
parameters, our training curriculum dynamically prioritizes different motifs
in the learning process without relying on any distributional assumptions on
the underlying graph or on the learning task.

We regularize three state-of-the-art GNN models in our InfoMotif framework for
semi-supervised node classification. Our experiments are conducted on a wide
variety of real-world datasets spanning homogeneous and heterogeneous
networks. In homogeneous graphs, our experimental results indicate significant
gains (3-10% accuracy) for InfoMotif over prior approaches on two diverse
classes of datasets: assortative citation networks that exhibit strong
homophily and dis-assortative air-traffic networks that depend on structural
roles. We also demonstrate the utility of our framework in three heterogeneous
graph datasets where InfoMotif outperforms a number of state-of-the-art
methods with significant performance gains (5% accuracy) on average. Our
qualitative analysis indicates stronger gains for nodes with sparse training
labels and diverse attributes in local neighborhood structures.

We organize the rest of the chapter as follows. In Section 3.2, we present the
problem formulation, and introduce preliminaries on graph neural networks and
network motifs. We describe our proposed framework InfoMotif in Sections 3.3
and 3.4, present experimental results in Section 3.5, discuss limitations in
Section 3.6, finally concluding in Section 3.8.

###  3.2 Preliminaries

In this section, we formalize semi-supervised node classification on graphs
via graph neural networks and introduce network motifs in homogeneous and
heterogeneous graphs.

####  3.2.1 Problem Definition

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be an attributed graph, with nodes
$\mathcal{V}$ and edges $\mathcal{E}\in\mathcal{V}\times\mathcal{V}$. Note,
$\mathcal{V}=\mathcal{V}_{L}\cup\mathcal{V}_{U}$, the sets of labeled
($\mathcal{V}_{L}$) and unlabeled ($\mathcal{V}_{U}$) nodes in the graph. Let
$\mathcal{N}(v)$ denote the neighbor set of node $v\in\mathcal{V}$ in
$\mathcal{G}$, and $\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times F}$ denotes
the attribute matrix with rows $\mathbf{x}_{v}\in\mathbb{R}^{F}$ for node
$v\in\mathcal{V}$. In our work, the graph may be heterogeneous with multiple
types of nodes and edges; in such a scenario, we have a node type mapping
$\psi:{\mathcal{V}}\mapsto{\mathcal{T}}_{V}$ where ${\mathcal{T}}_{V}$ is the
set of $T_{V}$ node types that identifies each node in ${\mathcal{V}}$ with a
type in ${\mathcal{T}}_{V}$, and a corresponding edge type mapping
$\xi:{\mathcal{E}}\mapsto{\mathcal{T}}_{E}$ where ${\mathcal{T}}_{E}$ is the
set of $T_{E}$ edge types. Each labeled node $v\in\mathcal{V}_{L}$ belongs to
one of $C$ classes, encoded by a one-hot vector
$\mathbf{y}_{v}\in\mathbb{B}^{C}$ ($\mathbb{B}=\\{0,1\\}$). Our goal is to
predict the labels of the unlabeled nodes $v\in\mathcal{V}_{U}$. This is the
familiar transductive or semi-supervised learning setup for node
classification in large-scale graphs [33].

####  3.2.2 Graph Neural Networks

Graph Neural Networks (GNNs) use multiple message-passing layers to learn node
representations. At each layer $l>0$, where $0$ is the input layer, GNNs
compute a representation for node $v$ by aggregating features from its local
neighborhood, through a learnable aggregator function $f_{\theta,l}$ per
layer. Using $k$ layers allows for the $k$-hop neighborhood of a node to
influence its representation. Let $\mathbf{h}_{v,l-1}\in\mathbb{R}^{D}$ denote
the representation of node $v$ in layer $l-1$. The $l$-th layer of the GNN
follows a message passing rule given by:

$\mathbf{h}_{v,l}=f_{\theta,l}\Big{(}\mathbf{h}_{v,l-1},\\{\mathbf{h}_{u,l-1}\\}\Big{)},\quad
u\in\mathcal{N}_{v}$ (3.1)

Equation 3.1 says that the node embedding $\mathbf{h}_{v,l}\in\mathbb{R}^{D}$
for node $v$ at the $l$-th layer is a non-linear aggregation $f_{\theta,l}$ of
the embeddings from layer $l-1$ of node $v$ and the embeddings of immediate
network neighbors $u\in\mathcal{N}(v)$ of node $v$. The function
$f_{\theta,l}$ defines the message passing mechanism at layer $l$ and we can
use a variety of aggregator architectures, including graph convolution [39],
graph attention [40], and pooling [41] to instantiate $f_{\theta,l}$. The node
representation for $v$ at the input layer is denoted by $\mathbf{h}_{v,0}$
(i.e., $l=0$), where $\mathbf{h}_{v,0}={\mathbf{x}}_{v}$ and
${\mathbf{x}}_{v}\in\mathbb{R}^{F}$. We designate the representation of node
$v$ at the final GNN layer ${\mathbf{h}}_{v}\in{\mathbb{R}}^{D}$, as its base
GNN representation. In this work, we use GNNs as a collective term for neural
networks that operate over graphs using localized message passing [159], as
opposed to spectral methods [37] that learn convolutional filters from the
entire graph.

####  3.2.3 Network Motifs

Network motifs are a general class of higher-order connectivity patterns, with
a history of use in network science [10, 160]. A motif has several
topologically equivalent appearances in the network called motif instances.
Prior work [161, 162] shows how to efficiently compute motif instances for
large graphs.

Figure 3.2: Topologically distinct, directed ($M_{1}$ to $M_{5}$) and
undirected ($M_{6}$ to $M_{7}$) connected, network motifs over three nodes.

######  Definition 3.1 (Network Motif).

A network motif $M_{t}=({\mathcal{V}}_{t},{\mathcal{E}}_{t})$ is a connected,
induced subgraph consisting of a subset $\mathcal{V}_{t}\subset\mathcal{V}$
and $\mathcal{E}_{t}=\\{e\in\mathcal{E}\mid e=(u,v),u,v\in\mathcal{V}_{t}\\}$.
Let $k_{t}$ denote the number of nodes in network motif $M_{t}$; that is,
$k_{t}=|\mathcal{V}_{t}|$.

Here, we consider 3-node connected network motifs, e.g., Figure 3.2 shows all
3-node, topologically distinct, directed (e.g., citations) and undirected,
connected network motifs.

In a heterogeneous graph, nodes/edges are of many different types which makes
it essential to explicitly (and jointly) model the connectivity patterns and
the participating types. We define typed network motifs that generalize
network motifs through additional constraints on the types of participating
nodes, which are formally described below as:

######  Definition 3.2 (Typed Network Motif).

A typed network motif
$M_{t}=({\mathcal{V}}_{t},{\mathcal{E}}_{t},\psi_{t},\xi_{t})$ is a connected,
induced subgraph consisting of a subset $\mathcal{V}_{t}\subset\mathcal{V}$
and $\mathcal{E}_{t}=\\{e\in\mathcal{E}\mid e=(u,v),u,v\in\mathcal{V}_{t}\\}$
such that node and edge type mappings $\psi_{t}=\psi|_{{\mathcal{E}}_{t}}$ and
$\xi_{t}|_{{\mathcal{V}}_{t}}$ are restrictions of $\psi$ and $\xi$ to
${\mathcal{V}}_{t}$ and ${\mathcal{E}}_{t}$ respectively, and
$k_{t}=|\mathcal{V}_{t}|$ is the number of nodes in $M_{t}$.

We assume that the given graph ${\mathcal{G}}$ has a set of unique network
motifs $\mathcal{M}=\\{M_{1},\dots,M_{T}\\}$.

(a) Schema of DBLP

(b) Examples of typed 3-node motifs in DBLP

Figure 3.3:  (a) Heterogeneous network schema of academic citation network
DBLP with three node types: Author (A), Paper (P) and Venue (V) and three edge
types $A-P,P-V$ and $P-A$. (b) Examples of 3-node connected typed network
motifs.

######  Definition 3.3 (Motif Instance).

Let $I_{t}$ be an induced subgraph of ${\mathcal{G}}$. We define $I_{t}$ to be
a motif instance of $M_{t}$ if $I_{t}$ is isomorphic to $M_{t}$. A motif
$M_{t}$ can have several motif instances in ${\mathcal{G}}$. While each such
motif instance has a unique node set, two motif instances can share nodes. We
denote the set of unique instances of $M_{t}$ in $\mathcal{G}$ that contain
node $v$ as $\mathcal{I}_{v}(M_{t})$.

####  3.2.4 Model Regularization

We plan to use these local structural properties (i.e., network motifs) to
regularize the graph neural network model during training. Typically, we train
GNNs by minimizing the cross-entropy loss $L_{B}$, between model predictions
$\mathbf{\hat{y}}_{v}\in\mathbb{R}^{C}$ and ground-truth labels
$\mathbf{y}_{v}\in\mathbb{B}^{C}$ of labeled training nodes in
$v\in\mathcal{V}_{L}$, which is defined below:

$L_{B}=-\sum\limits_{v\in\mathcal{V}_{L}}\sum\limits_{c=1}^{C}y_{v,c}\log\hat{y}_{v,c}$
(3.2)

where the $c$-th index of the one-hot vector $\hat{y}_{v,c}$ is the
probability that $v$ belongs to the true class $c$. Notice that the loss
$L_{B}$ is agnostic to any local structural properties (e.g., mixing patterns
in social networks [163]) that may be indicative of the true node class. Thus,
we develop a modified loss $L^{\prime}_{B}=L_{B}+\lambda L_{R}$, where $L_{R}$
is the regularization loss that incorporates attributed motif structure and
$\lambda$ is a constant. Our goal is to design $L_{R}$ to overcome the two
limitations of message-passing models: localized and over-smoothed node
representations.

Symbol | Description
---|---
$\mathcal{M}$ | Set $\\{M_{1},\dots,M_{T}\\}$ of $T$ network motifs
$\mathcal{I}_{v}(M_{t})$ | Set of instances of motif $M_{t}$ in $\mathcal{G}$ that contain node $v$
$\mathbf{h}_{v,l}$ | Representation of node $v$ at layer $l$ of GNN
$\mathbf{h}_{v}$ | Base GNN representation of node $v$ (final layer)
$\mathbf{h}^{t}_{v}$ | Motif-gated representation of node $v$ for motif $M_{t}$
$\mathbf{e}_{v,I_{t}}$ | Instance-specific representation of $v$ in $I_{t}\in\mathcal{I}_{v}(M_{t})$
$\mathbf{s}_{v,t}$ | Motif-level representation of node $v$ for motif $M_{t}$
$\mathbf{z}_{v}$ | Final Representation of node $v$
$\alpha_{vt}$ | Task-specific importance of motif $M_{t}$ to node $v$
$\beta_{v}$ | Novelty score for training node $v\in{\mathcal{V}}_{L}$
Table 3.1: Notation

###  3.3 InfoMotif Framework

In this section, we first discuss the structural properties of GNNs to
motivate the notion of attributed structural roles. In section 3.3.2, we
present our motif-based self-supervised learning framework InfoMotif to
regularize GNNs based on a single motif. Finally, in section 3.3.3, we
introduce our overall framework with a novel multi-motif training curriculum.

####  3.3.1 Motivating Insights: Attributed Structural Roles

A $k$-layer GNN computes a localized representation $\mathbf{h}_{v,k}$ for
each node $v$ that incorporates information from its $k$-hop neighborhood,
denoted by $\mathcal{N}_{k}(v)$. For a node set $S\subseteq{\mathcal{V}}$, let
$\mathcal{N}_{k}(S)=\bigcup_{v\in S}{\mathcal{N}}_{k}(v)$ define its $k$-hop
neighborhood, and ${\bm{X}}(S)$ denote its set of input node features. Let
${\bm{Y}}({\mathcal{V}}_{L})$ comprise the training labels of nodes in the
labeled set ${\mathcal{V}}_{L}$. For a $k$-layer GNN trained on
${\mathcal{V}}_{L}$ using loss $L_{B}$ (Equation 3.2), let
$\Theta^{*}=\\{\Theta_{1},\dots,\Theta_{k}\\}$ be the optimal parameters
computed by its training algorithm. Now, we have the following proposition.

######  Proposition 3.1.

The optimal parameter set $\Theta^{*}$ is a function of
${\bm{X}}(\mathcal{N}_{k}({\mathcal{V}}_{L}))$ and
${\bm{Y}}({\mathcal{V}}_{L})$; further, any changes in inputs
${\bm{X}}({\mathcal{V}}\setminus\mathcal{N}_{k}({\mathcal{V}}_{L}))$ do not
affect $\Theta^{*}$.

Proof Sketch. By an induction argument, the supervised loss $L_{B}$ can be
written as
$g(\Theta_{1},\dots,\Theta_{k},{\bm{Y}}({\mathcal{V}}_{L}),{\bm{X}}(\mathcal{N}_{k}({\mathcal{V}}_{L}))$
for some function $g(\cdot)$. Thus, when the GNN is trained on $L_{B}$ using
gradient updates, the optimal $\Theta^{*}$ must be independent of
${\bm{X}}({\mathcal{V}}\setminus\mathcal{N}_{k}({\mathcal{V}}_{L}))$.

Notice that the addition of a standard regularization term (e.g., $L_{1}$ or
$L_{2}$ regularization) only impacts $\\{\Theta_{1},\dots,\Theta_{k}\\}$;
thus, the overall loss function still remains independent of
${\mathcal{V}}\setminus\mathcal{N}_{k}({\mathcal{V}}_{L})$, satisfying
proposition 3.1.

Hence, the optimal parameters $\Theta^{*}$ of a $k$-layer GNN are only
affected by node features in the $k$-hop neighborhood
${\mathcal{N}}_{k}({\mathcal{V}}_{L})$ of the labeled set ${\mathcal{V}}_{L}$,
i.e., the features and structural connectivities of nodes in
${\mathcal{V}}\setminus\mathcal{N}_{k}({\mathcal{V}}_{L})$ are ignored during
the training process.

Let the $k$-hop neighborhood of class $c$ be
${\mathcal{N}}_{k}({\mathcal{V}}_{L}(c))$ where
${\mathcal{V}}_{L}(c)=\\{v\in{\mathcal{V}}_{L}:y_{vc}=1\\}$ is the set of
nodes labeled with class $c$. Let $L_{B}(c)$ denote the supervised loss term
specific to class $c$. Now, the corollary directly follows from proposition
3.1:

######  Corollary 3.1.

If node $v\not\in{\mathcal{N}}_{k}({\mathcal{V}}_{L}(c))$, the $k$-hop
neighborhood of class $c$, then the supervised loss term $L_{B}(c)$ for class
$c$ is independent of $v$.

The above corollary states that gradients from the supervised loss $L_{B}(c)$
for class $c$ cannot reach nodes that lie outside the $k$-hop neighborhood of
class $c$, i.e., ${\mathcal{N}}_{k}({\mathcal{V}}_{L}(c))$. To illustrate its
implications, we revisit Figure 3.1. Since node $c$ lies beyond the $2$-hop
neighborhood of node $b$, node $c$ does not affect the training loss at node
$b$ (which belongs to class 2). Thus, despite nodes $c$ and $b$ having
identical co-variation of attributes and structure (blue neighbors form
triangles), node $c$ does not influence the training loss for nodes with class
2.

Figure 3.4: Neural architecture diagram of InfoMotif depicting the different
model components: base GNN $f_{\theta,l}$ with $k$ layers (bottom left),
motif-based mutual information maximizing regularizers $L^{t}_{MI}$ (top
right), and motif-attention module to compute final node representations
${\mathbf{z}}_{v}$ (bottom right). Instances of motif $M_{1}$ are shown in the
graph (top left) with textured lines and colors indicate node attributes.

####  3.3.2 Self-supervised Single Motif Regularization

In this section, we introduce InfoMotif, a framework to regularize node
representations of the base GNN by exploiting the co-variance of node
attributes and motif structures. We define attributed structural roles by
assigning the same role to nodes that participate in motif instances over co-
varying sets of attributes. Compared to prior role-aware models [24] that
discover structurally similar nodes agnostic to attributes, we define roles
based on attribute occurrence in higher-order connectivity structures. In
heterogeneous graphs, attributed structural roles further incorporate the
semantics of node and edge types described by the connectivity structures of
typed network motifs.

Now, we describe our self-supervised learning strategy to learn attribute co-
variance for a single motif. In the next section, we extend these formulations
to handle multiple motifs.

##### Motif-based Mutual Information

We first consider a single network motif type $M_{t}\in\mathcal{M}$ and a
specific node $v\in{\mathcal{V}}$ to learn attribute co-variance across
instances $\mathcal{I}_{v}(M_{t})$ that contain $v$ in the graph. To learn
attributed structural roles, it is necessary to contrast the attributed
instances of motif $M_{t}$ against attributed node combinations that are not
present in any instances of $M_{t}$.

We maximize the motif-based mutual information (MI) between a motif-level
representation of $v$ and corresponding instance-specific representations
centered at $v$. By introducing motif-based MI maximization as a regularizer,
the GNN is encouraged to learn discriminative statistical correspondences
between nodes that participate in instances of the same motif. Motif-based MI
maximization is an example of the broader paradigm of self-supervised learning
that derives auxiliary supervision signals from the intrinsic structure (e.g.,
connectivity patterns in a network motif) of the underlying data.

We first adapt the base GNN representation $\mathbf{h}_{v}$ (see Section
3.2.2), specific to motif $M_{t}$ through a motif gating function
$f^{t}_{\textsc{gate}}:\mathbb{R}^{D}\mapsto\mathbb{R}^{D}$ resulting in a
gated embedding $\mathbf{h}_{v}^{t}$. Then, we introduce a motif instance
encoder $f^{t}_{\textsc{enc}}:\mathbb{R}^{D}\times\mathbb{R}^{(k_{t}\times
D)}:\mapsto\mathbb{R}^{D}$ to compute the instance-specific representation
$\mathbf{e}_{v,I_{t}}\in\mathbb{R}^{D}$ of node $v$ conditioned on other co-
occurring nodes in instance $I_{t}\in\mathcal{I}_{v}(M_{t})$. Finally, the
motif-level representation $\mathbf{s}_{v,t}\in\mathbb{R}^{D}$ of node $v$
summarizes the set of instance-specific representations
$\\{\mathbf{e}_{v,I_{t}}\\}_{I_{t}\in\mathcal{I}_{v}(M_{t})}$ through a
permutation-invariant motif readout function $f^{t}_{\textsc{read}}(\cdot)$,
e.g., averaging or pooling functions.

For each node $v\in\mathcal{V}$, we maximize motif-based mutual information
$L^{t}_{MI}$ between its instance-specific representations
$\\{{\mathbf{e}}_{v,I_{t}}\\}_{I_{t}\in\mathcal{I}_{v}(M_{t})}$ and motif-
level representation ${\mathbf{s}}_{v,t}$, by defining $I_{\psi^{t}}$ as a
mutual information estimator for motif $M_{t}$ that is shared across all
nodes. The resulting learning objective is given by:

$L^{t}_{MI}(\theta,\phi^{t},\psi_{t})=\frac{1}{|{\mathcal{V}}|}\sum\limits_{v\in{\mathcal{V}}}\sum\limits_{I_{t}\in{\mathcal{I}}_{v}(M_{t})}I_{\psi_{t}}({\mathbf{e}}_{v,I_{t}};{\mathbf{s}}_{v,t})$
(3.3)

where $\theta$ and $\phi^{t}$ denote the parameters of the layers
$\\{f_{\theta,l}\\}_{l=1}^{k}$, and motif-specific transforms
$\\{f^{t}_{\textsc{gate}},f^{t}_{\textsc{enc}},f^{t}_{\textsc{read}}\\}$
respectively. By maximizing MI across all instances of motif $M_{t}$ in the
graph through a shared MI estimator $I^{t}_{\psi}$, we enable the GNN to learn
correspondences between a pair of potentially distant nodes that participate
in instances of motif $M_{t}$.

##### Mutual Information Maximization

Following prior neural MI estimation methods [164, 144], we model the MI
estimator $I_{\psi^{t}}$ as a discriminator network that learns a decision
boundary to accurately distinguish between positive samples drawn from the
joint distribution and negative samples drawn from the product of marginal
distributions. We train a constrastive discriminator network
${\bm{D}}^{t}_{\psi}:{\mathbb{R}}^{D}\times{\mathbb{R}}^{D}\mapsto{\mathbb{R}}^{+}$,
where ${\bm{D}}_{\psi}^{t}({\mathbf{e}}_{v,I_{t}},{\mathbf{s}}_{v,t})$ denotes
the probability score assigned to this instance-motif pair (higher scores for
observed instances of motif $M_{t}$). The positive samples
$({\mathbf{e}}_{v,I_{t}},{\mathbf{s}}_{v,t})$ for ${\bm{D}}_{\psi}^{t}$ are
the representations ${\mathbf{e}}_{v,I_{t}}$ of observed instances
$I_{t}\in{\mathcal{I}}_{v}(M_{t})$ of motif $M_{t}$ paired with the motif-
level representation ${\mathbf{s}}_{v,t}$. The negative samples
$({\mathbf{e}}_{v,\widetilde{I}_{t}},{\mathbf{s}}_{v,t})$ are derived by
pairing ${\mathbf{s}}_{v,t}$ with the representations
${\mathbf{e}}_{v,\widetilde{I}_{t}}$ of negative instances $\widetilde{I}_{t}$
sampled from a negative sampling distribution
$P_{{\mathcal{N}}}(\widetilde{I}_{t}|M_{t})$. The discriminator network
${\bm{D}}^{t}_{\psi}$ is trained on a noise-contrastive objective $L^{t}_{MI}$
with a binary cross-entropy loss between samples drawn from the joint
distribution (positive pairs), and the product of marginals (negative pairs),
which is defined as in the following objective below:

$\displaystyle
L^{t}_{MI}=\frac{1}{|{\mathcal{V}}|}\sum\limits_{v\in{\mathcal{V}}}L^{t}_{MI}(v)=-\frac{1}{2Q|{\mathcal{V}}|}\sum\limits_{v\in{\mathcal{V}}}\sum\limits_{i=1}^{Q}\Big{[}$
$\displaystyle\mathbb{E}_{I_{t}}\log{\bm{D}}_{\psi}^{t}({\mathbf{e}}_{v,I_{t}},{\mathbf{s}}_{v,t})$
$\displaystyle+\mathbb{E}_{\widetilde{I}_{t}}\log(1-{\bm{D}}_{\psi}^{t}({\mathbf{e}}_{v,\widetilde{I}_{t}},{\mathbf{s}}_{v,t}))\Big{]}$
(3.4)

where $Q$ is the number of observed motif instances sampled per node. The
above objective Equation 3.4 maximizes MI between ${\mathbf{s}}_{v,t}$ and
$\\{\mathbf{e}_{v,I_{t}}\\}_{I_{t}\in\mathcal{I}_{v}(M_{t})}$ based on the
Jensen-Shannon Divergence between their joint distribution and product of
marginals [44].

We design the negative sampling distribution
$P_{{\mathcal{N}}}(\widetilde{I}_{t}|M_{t})$ to learn attribute co-variance in
instances of motif $M_{t}$. For each positive instance $I_{t}$, the generated
negative instance $\widetilde{I}_{t}$ is topologically equivalent but contains
attributes that do not occur in instances of $M_{t}$ in ${\mathcal{G}}$. By
contrasting the observed instances of $M_{t}$ against fake instances with
perturbed attributes, ${\bm{D}}_{\psi}^{t}$ learns attributed structural roles
with respect to network motif $M_{t}$.

####  3.3.3 Multi-Motif Regularization Framework

Now, we extend our framework for any graph that includes a set of motifs
${\mathcal{M}}=\\{M_{1},\dots,M_{T}\\}$. A typical way to include regularizers
(Equation 3.4) from multiple motifs is given by:

$L^{{}^{\prime}}=L_{B}+\lambda
L^{{}^{\prime}}_{MI}=L_{B}+\lambda\cdot\frac{1}{T}\sum\limits_{t=1}^{T}L^{t}_{MI}$
(3.5)

where $\lambda$ is a tunable hyper-parameter to balance the supervised
classification loss $L_{B}$ and motif regularizers. Intuitively, each motif
$M_{t}\in\mathcal{M}$ is a connectivity pattern that can be viewed as defining
one kind of structural role, e.g., bridge nodes. Each motif has a different
significance towards the learning task. Thus, a multi-motif framework should
automatically identify the significance of different motifs without manual
hand tuning.

In addition, real-world networks exhibit heavy-tailed degree and community
distributions [165], which manifest as skewed (imbalanced) motif occurrences
among nodes as well as across motif types. This further complicates the
learning process of incorporating multiple motifs as regularizers. We identify
three key aspects task-oriented, node-sensitive, and skew-aware that are
critical to the design of a multi-motif learning framework:

  * •

Task: Distinguish the significance of different motifs to compute node
representations conditioned on the underlying semi-supervised learning task.

  * •

Node: Expressive power to control the extent of regularization exerted by each
motif at a node-level granularity.

  * •

Skew: Adapt to varying levels of motif occurrence skew without any
distributional assumptions on the input graph.

To address these objectives, we first describe our approach to compute final
node representations conditioned on multiple motifs, followed by two novel
online reweighting strategies.

##### Task-driven Representations

The base GNN is trained by a supervised task loss $L_{B}$ (Equation 3.2) over
the labeled node set ${\mathcal{V}}_{L}$. We instead aggregate the set of
motif-gated representations (${\mathbf{h}}_{v}^{t}$ for motif
$M_{t}\in{\mathcal{M}}$), to compute the final representation
${\mathbf{z}}_{v}\in{\mathbb{R}}^{D}$ for node $v$. We learn attention weights
$\alpha_{vt}$ to characterize the task-driven importance of motif $M_{t}$ to
node $v$ and compute ${\mathbf{z}}_{v}$ through a weighted average, given by:

${\mathbf{z}}_{v}=\sum\limits_{t=1}^{T}\alpha_{vt}{\mathbf{h}}^{t}_{v}\hskip
10.0pt\alpha_{vt}=\frac{\exp\big{(}{\bm{p}}\cdot{\mathbf{h}}^{t}_{v}\big{)}}{\sum\limits_{t^{\prime}=1}^{T}\exp\big{(}{\bm{p}}\cdot{\mathbf{h}}^{t^{\prime}}_{v}\big{)}}$
(3.6)

where ${\bm{p}}\in{\mathbb{R}}^{D}$ defines the attention function and is
learned by optimizing the final representations
$\\{{\mathbf{z}}_{v}\\}_{v\in{\mathcal{V}}_{L}}$ of labeled nodes
${\mathcal{V}}_{L}$ using the supervised loss $L_{B}$ (Equation 3.2). The
final representation ${\mathbf{z}}_{v}$ of each node $v\in{\mathcal{V}}$ is
used for node classification.

##### Node-sensitive Motif Regularization

Instead of using static uniform weights to incorporate motif regularizers
(Equation 3.5), we contextually weight the contributions of different motif
regularization terms $L^{t}_{MI}(v)$ from Equation 3.4 at a node-level
granularity through the attention weights $\alpha_{vt}$ of motif $M_{t}$ for
node $v$. This results in the following motif-regularization loss:

$L_{MI}=\frac{1}{nT}\sum\limits_{t=1}^{T}\sum\limits_{v\in{\mathcal{V}}}\alpha_{vt}L^{t}_{MI}(v)$
(3.7)

The loss $L_{MI}$ varies the extent of regularization per node in proportion
to the task-specific importance $\alpha_{vt}$ of motif $M_{t}$ to node $v$.
Notice that the attention function is learned by training the final
representations ${\mathbf{z}}_{v}$ of labeled nodes $v\in{\mathcal{V}}_{L}$ on
the supervised loss $L_{B}$; in contrast, the motif-regularization loss
$L_{MI}$ (which operates on all nodes) re-weights each motif loss term
$L^{t}_{MI}(v)$ per node $v$ with the estimated attention weight $\alpha_{vt}$
from Equation 3.6.

Algorithm 3.1 The framework of InfoMotif-GNN.

1:Graph ${\mathcal{G}}$, Labeled node set ${\mathcal{V}}_{L}$, Base GNN
$\\{f_{\theta,l}\\}_{l=1}^{k}$

2:Motif-regularized embedding ${\mathbf{z}}_{v}$ for each node
$v\in{\mathcal{V}}$

3:Initialize sample novelty weights
$\beta_{v}=1\;\forall\;v\in{\mathcal{V}}_{L}$

4:while not converged do

5:$\triangleright$ Supervised loss over labeled node set ${\mathcal{V}}_{L}$

6: for each batch of nodes ${\mathcal{V}}_{B}\subseteq{\mathcal{V}}_{L}$ do

7: Fix sample weights $\\{\beta_{v}\\}_{v\in{\mathcal{V}}_{B}}$ and optimize
$L_{S}$ on ${\mathcal{V}}_{B}$ using mini-batch gradient descent (Equation
3.9).

8: Compute motif attention weights $\\{\bm{\alpha_{v}}\\}_{v\in{\mathcal{V}}}$
(Equation 3.6).

9:$\triangleright$ Motif-based InfoMax loss over entire node set
${\mathcal{V}}$

10: for each batch of nodes ${\mathcal{V}}_{B}\subseteq{\mathcal{V}}$ do

11: Fix motif weights $\\{\bm{\alpha}_{v}\\}_{v\in{\mathcal{V}}}$ and optimize
$L_{MI}$ on ${\mathcal{V}}_{B}$ using mini-batch gradient descent (Equation
3.7)

12: Compute sample weights $\\{\beta_{v}\\}_{v\in{\mathcal{V}}_{L}}$ (Equation
3.8).

13:Compute ${\mathbf{z}}_{v}\in{\mathbb{R}}^{D}\;\forall\;v\in{\mathcal{V}}$
(Equation 3.6)

##### Skew-aware Sample Weighting

Prior work in curriculum and meta learning has shown the importance of re-
weighting training examples to overcome training set biases [166]. In
particular, re-weighting strategies that emphasize harder examples are
effective at handling imbalanced data distributions [167]. We propose a
novelty-driven re-weighting strategy to handle skew in motif occurrences
across nodes and motif types.

The novelty $\beta_{v}$ of node $v$ is a function of its motif distribution,
i.e., novel nodes contain uncommon motif types in their neighborhood, which in
turn reflects in their attention weight distribution over motifs. Let
$\bm{\alpha}_{v}\in{\mathbb{R}}^{T}$ denote the vector of attention weights
for a labeled node $v$ over the motif set ${\mathcal{M}}$. Now, the novelty
$\beta_{v}$ of node $v$ is high if its motif distribution $\bm{\alpha}_{v}$
significantly diverges from those of other nodes. We quantify $\beta_{v}$ by
the deviation (measured by euclidean distance) of $\bm{\alpha}_{v}$ from the
mean motif distribution of labeled nodes $v\in{\mathcal{V}}_{L}$.

$\beta_{v}=\frac{exp(\left\lVert\bm{\alpha}_{v}-\bm{\mu}\right\rVert^{2})}{\sum\limits_{u\in{\mathcal{V}}_{L}}\exp(\left\lVert\bm{\alpha}_{u}-\bm{\mu}\right\rVert^{2})}\hskip
10.0pt\bm{\mu}=\frac{1}{|{\mathcal{V}}_{L}|}\sum\limits_{v\in{\mathcal{V}}_{L}}\bm{\alpha}_{v}$
(3.8)

The novelty scores are normalized over ${\mathcal{V}}_{L}$ using a softmax
function, to give non-negative sample weights $0<\beta_{v}\leq 1$. We now
define the novelty-weighted supervised loss $L_{S}$ as:

$L_{S}=-\sum\limits_{v\in\mathcal{V}_{L}}\beta_{v}\sum\limits_{c=1}^{C}y_{vc}\log\hat{y}_{vc}$
(3.9)

In contrast to the original supervised loss $L_{B}$ (Equation 3.2), the re-
weighted objective $L_{S}$ induces a novelty-weighted training curriculum that
progressively focuses on harder samples.

##### Model Training

The overall objective of InfoMotif is composed of two terms, the re-weighted
supervised loss $L_{S}$ (Equation 3.9), and motif regularizers (Equation 3.7),
given by:

$L=L_{S}+\lambda L_{MI}$ (3.10)

We optimize $L_{S}$ and $L_{MI}$ alternatively at each training epoch, which
removes the need to tune balance hyper-parameter $\lambda$. Algorithm 3.1
summarizes the training procedure.

##### Complexity Analysis

On the whole, the complexity of our model is $O({\bm{F}})+O(nTQD+nTD^{2})$
where $O({\bm{F}})$ is the base GNN complexity, $T$ is the number of motifs,
$Q$ is sampled instance count per motif, and $D$ the latent space
dimensionality. Since $T\ll n$ and $Q\ll n$, the added complexity of our
InfoMotif framework scales linearly with respect to the number of nodes.

###  3.4 Model Details

We now discuss the architectural details of our framework: motif instance
encoder, gating, readout, and discriminator.

####  3.4.1 Motif Gating

We design a pre-filter with self-gating units (SGUs) to regulate the flow of
information from the base GNN embedding $\mathbf{h}_{v}$ to the motif-based
regularizer. The SGU for motif $M_{t}$, denoted by
$f^{t}_{\textsc{gate}}(\cdot)$, learns a non-linear gating function to
modulate the input $\mathbf{h}_{v}$ at a feature-wise granularity through
dimension re-weighting. In particular, we define the self-gating unit for
motif $M_{t}$ as:

$\mathbf{h}^{t}_{v}=f^{t}_{\textsc{gate}}(\mathbf{h}_{v})=\mathbf{h}_{v}\odot\sigma(\mathbf{W}_{g}^{t}\mathbf{h}_{v}+\mathbf{b}_{g}^{t})$
(3.11)

where $\mathbf{W}^{t}\in\mathbb{R}^{D\times
D},\mathbf{b}^{t}\in\mathbb{R}^{D}$ are learned parameters, $\odot$ denotes
the element-wise product operation, and $\sigma$ is the sigmoid non-linearity.
The self-gating mechanism effectively serves as a multiplicative skip-
connection [168] that facilitates gradient flow from the motif-based
regularizer to the layers of the base GNN.

####  3.4.2 Motif Instance Encoder

The encoder $f_{\textsc{enc}}(\cdot)$ computes the instance-specific
representation ${\mathbf{e}}_{v,I_{t}}$ for node $v$ conditioned on the gated
representations $\\{{\mathbf{h}}^{t}_{u}\\}_{u\in I_{t}}$ of the nodes in
instance $I_{t}$. We apply self-attentions [169] to compute a weighted average
of the gated node representations $\\{{\mathbf{h}}^{t}_{u}\\}_{u\in I_{t}}$ in
$I_{t}$. Specifically, $f_{\textsc{enc}}$ attends over each node $u\in I_{t}$
to compute attention weight $\alpha_{u}$ by comparing its gated representation
${\mathbf{h}}^{t}_{u}$ with that of node $v$, ${\mathbf{h}}^{t}_{v}$ using an
attention network that is parameterized by a single MLP layer, defined by:

${\mathbf{e}}_{v,I_{t}}=\sum\limits_{u\in
I_{t}}\alpha_{u}{\mathbf{h}}^{t}_{u}\hskip
10.0pt\alpha_{u}=\frac{\exp\big{(}{\bm{a}}^{t}\cdot[{\mathbf{h}}^{t}_{u}||{\mathbf{h}}^{t}_{v}]\big{)}}{\sum\limits_{u^{{}^{\prime}}\in
I_{t}}\exp\big{(}{\bm{a}}^{t}\cdot[{\mathbf{h}}^{t}_{u^{{}^{\prime}}}||{\mathbf{h}}^{t}_{v}]\big{)}}$
(3.12)

where ${\bm{a}}^{t}\in{\mathbb{R}}^{2D}$ is a weight vector parameterizing the
attention function and $||$ denotes concatenation. We empirically find self-
attentional encoders to outperform pooling alternatives.

####  3.4.3 Motif Readout

The motif readout function $f^{t}_{\textsc{read}}(\cdot)$ summarizes the set
of instance-specific representations
$\\{{\mathbf{e}}_{v,I_{t}}\\}_{I_{t}\in{\mathcal{I}}_{v}(M_{t})}$ to compute
the motif-level representation ${\mathbf{s}}_{v,t}$ for motif $M_{t}$. Here,
we use a simple averaging of the instance-specific representations to
formulate the motif readout function $f^{t}_{\textsc{read}}(\cdot)$ as defined
below:

${\mathbf{s}}_{v,t}=f^{t}_{\textsc{read}}\Big{(}\\{{\mathbf{e}}_{v,I_{t}}\\}_{I_{t}\in{\mathcal{I}}_{v}(M_{t})}\Big{)}=\sigma\Big{(}\sum\limits_{I_{t}\in{\mathcal{I}}_{v}(M_{t})}\frac{{\mathbf{e}}_{v,I_{t}}}{|{\mathcal{I}}_{v}(M_{t})|}\Big{)}$
(3.13)

where $\sigma$ is the sigmoid non-linearity. We adopt a batch-wise model
training strategy with motif instance sampling ($\sim$ 20 per node) to compute
the motif-level representation ${\mathbf{s}}_{v,t}$. While we find this simple
readout function to be empirically effective, sophisticated architectures
[170] are likely necessary to handle larger sample sizes.

####  3.4.4 Motif Discriminator

The discriminator $D^{t}_{\psi}$ learns a motif-specific scoring function to
assign higher likelihoods to observed instance-motif pairs relative to
negative examples. Similar to prior work [44, 171], we use a bilinear scoring
function defined by:

${\bm{D}}^{t}_{\psi}({\mathbf{e}}_{v,I_{t}},{\mathbf{s}}^{t}_{v})=\sigma({\mathbf{e}}_{v,I_{t}}\cdot{\bm{W}}_{d}^{t}{\mathbf{s}}^{t}_{v})$
(3.14)

where ${\bm{W}}_{d}^{t}\in{\mathbb{R}}^{D\times D}$ is a trainable scoring
matrix and $\sigma$ is the sigmoid non-linearity to convert raw scores into
probabilities of $({\mathbf{e}}_{v,I_{t}},{\mathbf{s}}^{t}_{v})$ being a
positive example for motif $M_{t}$.

###  3.5 Experiments

We present extensive quantitative and qualitative analyses on multiple diverse
datasets spanning homogeneous and heterogeneous graphs. We first introduce
datasets, baselines, and experimental setup (Section 3.5.1, 3.5.2, and 3.5.3),
followed by node classification results in Sections 3.5.4 and 3.5.5 by
integrating three GNN models in our framework. We propose four research
questions to guide our experiments:

  1. ($\textbf{RQ}_{\textbf{1}}$)

How does InfoMotif compare with state-of-the-art graph neural networks and
embedding learning methods on node classification over homogeneous graphs?

  2. ($\textbf{RQ}_{\textbf{2}}$)

Is InfoMotif effective for node classification on heterogeneous information
networks (multiple types of nodes and edges) compared to state-of-the-art
approaches?

  3. ($\textbf{RQ}_{\textbf{3}}$)

How do the different architectural design choices and training strategies in
InfoMotif impact performance?

  4. ($\textbf{RQ}_{\textbf{4}}$)

What is the impact of node degree, local training label sparsity, and local
attribute diversity, on the classification performance of InfoMotif?

  5. ($\textbf{RQ}_{\textbf{5}}$)

How do the motif-based regularization strategies and associated hyper-
parameters in InfoMotif affect model training time and performance?

| Citation Networks | Air-Traffic Networks
---|---|---
Dataset |  Cora |  Citeseer |  Pubmed |  Brazil |  Europe |  USA
# Nodes |  2,485 |  2,110 |  19,717 |  131 |  399 |  1,190
# Edges |  5,069 |  3,668 |  44,324 |  1,038 |  5,995 |  13,599
# Attributes |  1,433 |  3,703 |  500 |  - |  - |  -
# Classes |  7 |  6 |  3 |  4 |  4 |  4
Table 3.2: Dataset statistics of homogeneous network benchmarks, including three assortative citation [34] networks and three dis-assortative air-traffic [24] networks. Ground-truth classes in citation networks exhibit attribute homophily; ground-truth classes in flight networks indicate node structural roles. Dataset |  DBLP-A |  DBLP-P |  Movie
---|---|---|---
# Nodes |  $11,170$ |  $35,770$ |  $10,441$
# Edges |  $24,846$ |  $131,636$ |  $99,509$
# Attributes |  4,479 |  11,680 |  4,577
# Node Types |  3 |  3 |  4
# Classes |  4 |  10 |  6
Table 3.3: Dataset statistics of three heterogeneous graphs across
bibliographic and movie information networks, with multiple node and edge
types. Networks schemas are shown in Figures 3.3(a) and 3.5(a).

####  3.5.1 Datasets

Our experiments are designed towards semi-supervised node classification on
nine real-world benchmark datasets, divided across homogeneous and
heterogeneous networks. In homogeneous graphs, we experiment on two diverse
types of datasets: citation networks that exhibit strong homophily and air-
traffic networks that depend on structural roles. Table 3.2 presents detailed
statistics for each dataset.

  * •

Citation Networks: We consider three benchmark datasets: Cora, Citeseer, and
PubMed [34], where nodes correspond to documents and edges represent citation
links. Each document is associated with a bag-of-words feature vector and the
task is to classify documents into different research topics.

  * •

Air-Traffic Networks: We use three undirected networks: Brazil, Europe, and
USA [24] where nodes correspond to airports and edges indicate the existence
of commercial flights. Class labels are assigned based on activity level,
measured by the cardinality of flights or people that passed the airports. We
use one-hot indicator vectors as node attributes. Here, class labels are
related to the role played by airports.

We conduct experiments on three real-world datasets over heterogeneous graphs
whose statistics are shown in Table 3.3:

  * •

DBLP-A: This is a bibliographic network composed of 3 node types: author
($A$), paper ($P$) and venue ($V$), connected by three link types:
$P\rightarrow P$, $A\mbox{-}P$ and $P\mbox{-}V$ (Figure 3.3(a)). We use a
subset of DBLP [172] with text attributes of papers to classify authors based
on their research areas.

  * •

DBLP-P: This dataset has the same schema as DBLP-A, but the learning task is
to classify research papers into ten categories, which are obtained from Cora
[173].

  * •

Movie: We use MovieLens [174] with four node types: movie ($M$), user ($U$),
actor ($A$) and tag ($T$) linked by four types: $U\mbox{-}M$, $A\mbox{-}M$,
$U\mbox{-}T$ and $M\mbox{-}T$, with attributes for actors and movies. The
classification task is movie genre prediction.

(a) Schema of Movie

(b) Examples of typed 3-node motifs in MovieLens

Figure 3.5:  (a) Heterogeneous network schema of movie network with four node
types: Actor (A), Movie (M), User (U) and Term (T) and four edge types
$A-M,U-M,T-M$, and $U-T$. (b) Examples of 3-node connected typed network
motifs.

####  3.5.2 Baselines

We first introduce baseline methods designed for learning over homogeneous
graphs, organized into four categories based on whether they are proximity-
based vs. structural; and the paradigm of embedding learning vs. graph neural
networks:

  * •

Proximity-based embedding methods: Conventional methods node2vec [18] that
employs second-order proximity, and motif2vec [175] based on higher-order
proximity.

    * –

node2vec [18]: Skip-gram model to learn unsupervised node representations that
capture node co-occurrences in second-order random walk samples.

    * –

motif2vec [175]: Higher-order extension of skip-gram embedding models to model
higher-order proximity induced by motif structures.

  * •

Structural embedding methods: Structural role-aware embedding learning models
struc2vec [24], GraphWAVE [176], and DRNE [177].

    * –

struc2vec [24]: Learns node representations capturing structural identity by
utilizing degree sequences at different local neighborhoods.

    * –

GraphWAVE [176]: Learns node embeddings that capture structural similarity by
leveraging spectral graph wavelet diffusion patterns.

    * –

DRNE [177]: Deep recursive neural network to learn node embeddings that
preserve the property of regular equivalence.

  * •

Standard Graph Neural Networks: We compare against several state-of-the-art
GNNs based on localized message passing:

    * –

GCN [39]: Graph convolutional networks operating on the graph Laplacian matrix
using degree-weighted neighborhood aggregation.

    * –

GraphSAGE [41]: Scalable graph neural networks with neighborhood sampling and
aggregation using a variety of pooling functions (max, mean, and LSTM)

    * –

GAT [40]: Graph attention networks with self-attentional neighbor aggregation.

    * –

JK-Net [42]: Jumping knowledge networks that use skip-connections to vary the
influence radius (per node) for neighborhood aggregation.

    * –

DGI [44]: Deep Graph Infomax that learns node embeddings by maximizing mutual
information between local and global representations of the same graph.

  * •

Structural Graph Neural Networks: Motif-based GNN models Motif-CNN [46], MCN
[47] and degree-specific DEMO-Net [45].

    * –

Motif-CNN [46]: Motif-based graph convolutional networks with attention-based
cross-motif aggregation.

    * –

MCN [47]: Motif-based graph attentional model that uses weighted multi-hop
motif adjacency matrices to capture higher-order neighborhood information.

    * –

DEMO-Net [45]: Degree-specific graph neural network that uses multi-task graph
convolutions to learn degree-aware node embeddings.

Next, we introduce graph neural networks designed specifically for semi-
supervised learning over heterogeneous graphs.

  * •

Heterogeneous Graph Neural Networks: State-of-the-art metapath-based GNN
models MAGNN [57], HAN [56], and metagraph-aware GNN model Meta-GNN [58].

    * –

MAGNN [57]: Learns heterogeneous node embeddings via intra-metapath
aggregation to incorporate intermediate semantic nodes, and the inter-metapath
aggregation to combine messages from multiple metapaths.

    * –

HAN [56]: Learns metapath-specific node embeddings from different metapath-
based homogeneous graphs using an attention mechanism.

    * –

Meta-GNN [58]: Learns node embeddings to extract and aggregate features from
local metagraph-structured neighborhoods in heterogeneous graphs.

| Data | Cora | Citeseer | PubMed
---|---|---|---|---
Training Ratio |  X |  Y |  20% |  40% |  20% |  40% |  20% |  40%
Proximity-based Graph Embedding Methods
Node2Vec [18] |  |  |  75.7 $\pm$ 0.5 |  76.1 $\pm$ 0.5 |  68.1 $\pm$ 0.5 |  69.1 $\pm$ 0.6 |  80.1 $\pm$ 0.6 |  80.2 $\pm$ 0.6
Motif2Vec [175] |  |  |  79.0 $\pm$ 0.4 |  79.2 $\pm$ 0.4 |  66.6 $\pm$ 0.4 |  67.1 $\pm$ 0.3 |  79.8 $\pm$ 0.2 |  79.8 $\pm$ 0.4
Structural Graph Embedding Methods
Struct2Vec [24] |  |  |  35.4 $\pm$ 1.0 |  37.6 $\pm$ 1.3 |  31.2 $\pm$ 0.8 |  35.1 $\pm$ 0.9 |  48.5 $\pm$ 0.3 |  49.2 $\pm$ 0.4
GraphWave [176] |  |  |  39.5 $\pm$ 2.1 |  41.1 $\pm$ 1.5 |  38.5 $\pm$ 1.2 |  40.6 $\pm$ 0.9 |  43.0 $\pm$ 2.0 |  43.3 $\pm$ 1.3
DRNE [177] |  |  |  34.9 $\pm$ 1.5 |  36.5 $\pm$ 1.5 |  30.8 $\pm$ 1.2 |  32.2 $\pm$ 1.2 |  40.4 $\pm$ 0.7 |  41.6 $\pm$ 0.4
Standard Graph Neural Networks
GCN [39] |  ✓ |  ✓ |  81.6 $\pm$ 0.5 |  82.0 $\pm$ 0.4 |  75.8 $\pm$ 0.5 |  76.6 $\pm$ 0.3 |  85.7 $\pm$ 0.7 |  86.1 $\pm$ 0.5
GAT [40] |  ✓ |  ✓ |  80.9 $\pm$ 0.7 |  81.4 $\pm$ 0.2 |  74.5 $\pm$ 0.7 |  75.5 $\pm$ 0.7 |  83.3 $\pm$ 0.3 |  84.2 $\pm$ 0.3
GraphSAGE [41] |  ✓ |  ✓ |  81.3 $\pm$ 0.3 |  83.5 $\pm$ 0.3 |  72.9 $\pm$ 0.3 |  73.8 $\pm$ 0.2 |  86.6 $\pm$ 0.2 |  87.2 $\pm$ 0.3
JKNet [42] |  ✓ |  ✓ |  81.3 $\pm$ 0.8 |  83.6 $\pm$ 0.8 |  71.5 $\pm$ 0.8 |  72.5 $\pm$ 0.7 |  82.2 $\pm$ 0.4 |  83.8 $\pm$ 0.5
DGI [44] |  ✓ |  |  76.2 $\pm$ 0.8 |  77.3 $\pm$ 0.9 |  74.5 $\pm$ 0.7 |  74.7 $\pm$ 0.7 |  78.2 $\pm$ 0.9 |  78.5 $\pm$ 0.9
Structural Graph Neural Networks
DemoNet [45] |  ✓ |  ✓ |  81.0 $\pm$ 0.6 |  82.4 $\pm$ 0.5 |  67.9 $\pm$ 0.7 |  68.5 $\pm$ 0.6 |  79.5 $\pm$ 0.4 |  80.5 $\pm$ 0.4
Motif-CNN [46] |  ✓ |  ✓ |  81.6 $\pm$ 0.5 |  82.8 $\pm$ 0.5 |  73.4 $\pm$ 0.3 |  76.8 $\pm$ 0.3 |  87.3 $\pm$ 0.1 |  87.5 $\pm$ 0.1
MCN [47] |  ✓ |  ✓ |  81.1 $\pm$ 0.9 |  82.4 $\pm$ 0.8 |  73.2 $\pm$ 0.4 |  75.9 $\pm$ 0.7 |  85.2 $\pm$ 0.6 |  85.9 $\pm$ 0.5
Motif-regularized Graph Neural Networks (InfoMotif)
InfoMotif-GCN |  ✓ |  ✓ |  85.7 $\pm$ 0.4 |  87.4 $\pm$ 0.4 |  77.7 $\pm$ 0.5 |  78.5 $\pm$ 0.5 |  87.5 $\pm$ 0.2 |  88.3 $\pm$ 0.2
InfoMotif-JKNet |  ✓ |  ✓ |  85.5 $\pm$ 0.3 |  86.5 $\pm$ 0.5 |  74.5 $\pm$ 0.8 |  76.7 $\pm$ 0.9 |  87.0 $\pm$ 0.2 |  87.9 $\pm$ 0.3
InfoMotif-GAT |  ✓ |  ✓ |  85.5 $\pm$ 0.3 |  87.2 $\pm$ 0.7 |  76.5 $\pm$ 0.5 |  77.0 $\pm$ 0.4 |  85.9 $\pm$ 0.4 |  86.2 $\pm$ 0.5
Table 3.4: Node classification results (% test accuracy) on assortative
citation networks. $\mathbf{X}$ and $\mathbf{Y}$ denote the use of attributes
and labels respectively. We report mean classification accuracy and standard
deviation over 5 trials. We show GraphSAGE results with the best performing
aggregator (among Max, Mean and LSTM). InfoMotif improves results of all base
GNNs by 3.5% on average across datasets.

####  3.5.3 Experimental Setup

We tested InfoMotif by integrating GCN, JK-Net and GAT as base graph neural
network models within our framework. We only consider the largest connected
component in each dataset and evaluate different train/validation/test splits
to fairly compare different models [178]. We create 10 random data splits per
training ratio and evaluate the mean test classification accuracy along with
standard deviation.

All experiments were conducted on a Tesla K-80 GPU using PyTorch. Our
implementation of InfoMotif is publicly
available222https://github.com/CrowdDynamicsLab/InfoMotif. For citation
networks, we use two-layer base GNNs with layer sizes of 256 each, while using
64 for the smaller air-traffic networks. We train the base JK-Net model using
4 GCN layers and maxpool layer aggregation, while the base GAT model learns 8
attention heads per layer. The model is trained for a maximum of 100 epochs
with a batch size of 256 nodes with Adam optimizer. We also apply dropout with
a rate of 0.5, and tune the learning rate in the range
$\\{10^{-4},10^{-3},10^{-2}\\}$.

####  3.5.4 Homogeneous Graphs ($\text{RQ}_{1}$)

In homogeneous graphs, we train InfoMotif using the set of all directed 3-node
motifs in citation networks and undirected 3-node motifs in air-traffic
networks (Figure 3.2). We evaluate different train/validation/test splits
(training ratios of 20%, and 40%) and report experimental results comparing
InfoMotif with three base GNNs, against competing baselines on citation and
air-traffic networks, in Tables 3.4 and 3.5 respectively.

| Data | USA | Europe | Brazil
---|---|---|---|---
Training Ratio |  X |  Y |  20% |  40% |  20% |  40% |  20% |  40%
Proximity-based Graph Embedding Methods
Node2Vec [18] |  |  |  24.6 $\pm$ 0.9 |  24.8 $\pm$ 0.9 |  36.5 $\pm$ 1.0 |  37.4 $\pm$ 1.1 |  26.3 $\pm$ 1.4 |  30.4 $\pm$ 1.3
Motif2Vec [175] |  |  |  51.3 $\pm$ 1.1 |  54.8 $\pm$ 1.1 |  37.1 $\pm$ 1.2 |  38.1 $\pm$ 1.2 |  27.2 $\pm$ 1.5 |  33.9 $\pm$ 1.5
Structural Graph Embedding Methods
Struct2Vec [24] |  |  |  50.4 $\pm$ 0.8 |  51.3 $\pm$ 0.8 |  42.5 $\pm$ 0.7 |  45.6 $\pm$ 0.8 |  45.8 $\pm$ 1.1 |  51.8 $\pm$ 1.1
GraphWave [176] |  |  |  45.2 $\pm$ 1.4 |  48.0 $\pm$ 1.4 |  38.1 $\pm$ 1.9 |  41.1 $\pm$ 1.6 |  40.2 $\pm$ 2.0 |  43.1 $\pm$ 1.8
DRNE [177] |  |  |  51.3 $\pm$ 1.1 |  52.4 $\pm$ 1.1 |  43.1 $\pm$ 1.7 |  47.6 $\pm$ 1.3 |  46.5 $\pm$ 2.7 |  50.2 $\pm$ 2.3
Standard Graph Neural Networks
GCN [39] |  ✓ |  ✓ |  51.9 $\pm$ 0.9 |  56.0 $\pm$ 0.9 |  37.4 $\pm$ 0.9 |  40.1 $\pm$ 0.8 |  36.5 $\pm$ 1.5 |  38.9 $\pm$ 1.6
GAT [40] |  ✓ |  ✓ |  52.7 $\pm$ 1.0 |  53.5 $\pm$ 0.9 |  31.5 $\pm$ 1.0 |  34.3 $\pm$ 1.0 |  37.3 $\pm$ 1.6 |  37.9 $\pm$ 1.6
GraphSAGE [41] |  ✓ |  ✓ |  45.3 $\pm$ 1.2 |  49.4 $\pm$ 1.2 |  28.8 $\pm$ 1.0 |  32.5 $\pm$ 1.0 |  36.1 $\pm$ 1.6 |  37.5 $\pm$ 1.6
JKNet [42] |  ✓ |  ✓ |  53.8 $\pm$ 1.2 |  56.1 $\pm$ 1.0 |  49.7 $\pm$ 1.1 |  53.8 $\pm$ 1.1 |  55.9 $\pm$ 1.5 |  58.4 $\pm$ 1.8
DGI [44] |  ✓ |  |  46.4 $\pm$ 1.3 |  47.3 $\pm$ 1.2 |  37.5 $\pm$ 1.5 |  39.9 $\pm$ 1.5 |  41.4 $\pm$ 1.6 |  45.2 $\pm$ 1.7
Structural Graph Neural Networks
DemoNet [45] |  ✓ |  ✓ |  58.6 $\pm$ 1.2 |  58.8 $\pm$ 1.1 |  40.4 $\pm$ 1.3 |  46.2 $\pm$ 1.2 |  46.1 $\pm$ 1.4 |  48.9 $\pm$ 1.5
Motif-CNN [46] |  ✓ |  ✓ |  53.6 $\pm$ 1.0 |  54.2 $\pm$ 1.0 |  37.9 $\pm$ 1.0 |  41.1 $\pm$ 1.1 |  28.9 $\pm$ 1.6 |  35.7 $\pm$ 1.7
MCN [47] |  ✓ |  ✓ |  54.8 $\pm$ 1.4 |  54.9 $\pm$ 1.3 |  36.8 $\pm$ 1.2 |  39.6 $\pm$ 1.5 |  42.9 $\pm$ 1.6 |  43.6 $\pm$ 1.4
Motif-regularized Graph Neural Networks (InfoMotif)
InfoMotif-GCN |  ✓ |  ✓ |  59.5 $\pm$ 0.9 |  62.9 $\pm$ 0.7 |  53.5 $\pm$ 0.6 |  56.9 $\pm$ 0.6 |  56.6 $\pm$ 1.2 |  60.7 $\pm$ 1.2
InfoMotif-JKNet |  ✓ |  ✓ |  61.8 $\pm$ 1.6 |  64.3 $\pm$ 1.2 |  53.1 $\pm$ 1.2 |  56.9 $\pm$ 0.6 |  62.7 $\pm$ 1.8 |  67.9 $\pm$ 1.5
InfoMotif-GAT |  ✓ |  ✓ |  58.0 $\pm$ 0.4 |  60.4 $\pm$ 0.3 |  46.0 $\pm$ 1.5 |  50.0 $\pm$ 2.0 |  50.6 $\pm$ 1.3 |  56.3 $\pm$ 1.1
Table 3.5: Node classification results (% test accuracy) on dis-assortative
air-traffic networks. $\mathbf{X}$ and $\mathbf{Y}$ denote the use of
attributes and labels respectively. Structural embedding methods and
structural GNNs typically outperform proximity-based models. InfoMotif JK-Net
achieves significant performance gains of 4% to 14% across different datasets.

In citation network datasets, GNN models generally outperform conventional
embedding methods. Moreover, attribute-agnostic structural embedding methods
perform poorly and structural GNNs perform comparably to standard message-
passing GNNs. Citation networks exhibit strong attribute homophily in local
neighborhoods; thus, structural GNNs do not provide much performance benefits
over state-of-the-art message-passing GNNs. In contrast, our framework
InfoMotif regularizes GNNs to discover distant nodes with similar attributed
structures across the entire graph. InfoMotif achieves consistent average
classification accuracy gains of 3% for all three base GNN variants, with the
GCN model variant achieving best empirical results overall.

In air-traffic networks, structural embedding methods outperform their
proximity-based counterparts. We also observe a similar trend for structural
GNNs over standard message-passing GNNs. Class labels rely more on node
structural roles than the labels of neighbors in air-traffic networks. JK-net
outperforms other competing GNNs, signifying the importance of long-range
dependencies in air-traffic networks. Our framework InfoMotif enables GNNs to
learn structural roles agnostic to network proximity, and achieves significant
gains of 10% on average across all datasets.

| Data | DBLP-A | DBLP-P | Movie
---|---|---|---|---
Training Ratio |  X |  Y |  10% |  20% |  10% |  20% |  10% |  20%
Proximity-based Graph Embedding Methods
Node2Vec [18] |  |  |  63.9 $\pm$ 0.4 |  65.3 $\pm$ 0.6 |  68.5 $\pm$ 0.4 |  70.1 $\pm$ 0.5 |  54.1 $\pm$ 0.3 |  56.7 $\pm$ 0.3
Motif2Vec [175] |  |  |  62.7 $\pm$ 0.7 |  64.5 $\pm$ 0.6 |  68.9 $\pm$ 0.9 |  71.3 $\pm$ 1.1 |  55.0 $\pm$ 0.3 |  57.4 $\pm$ 0.5
Structural Graph Embedding Methods
Struct2Vec [24] |  |  |  34.2 $\pm$ 0.4 |  36.1 $\pm$ 0.4 |  34.9 $\pm$ 0.2 |  35.7 $\pm$ 0.3 |  32.7 $\pm$ 0.4 |  34.9 $\pm$ 0.1
GraphWave [176] |  |  |  34.8 $\pm$ 0.5 |  37.0 $\pm$ 0.6 |  35.6 $\pm$ 0.2 |  36.3 $\pm$ 0.3 |  33.5 $\pm$ 0.4 |  36.0 $\pm$ 0.4
DRNE [177] |  |  |  33.9 $\pm$ 0.3 |  36.5 $\pm$ 0.3 |  35.1 $\pm$ 0.5 |  35.5 $\pm$ 0.4 |  31.0 $\pm$ 0.2 |  35.1 $\pm$ 0.2
Standard Graph Neural Networks
GCN [39] |  ✓ |  ✓ |  65.3 $\pm$ 1.1 |  69.6 $\pm$ 0.9 |  71.3 $\pm$ 0.7 |  73.4 $\pm$ 0.8 |  55.7 $\pm$ 1.0 |  57.3 $\pm$ 0.7
GAT [40] |  ✓ |  ✓ |  67.5 $\pm$ 0.8 |  71.7 $\pm$ 0.8 |  71.9 $\pm$ 0.5 |  73.0 $\pm$ 0.7 |  58.6 $\pm$ 0.9 |  59.9 $\pm$ 1.0
GraphSAGE [41] |  ✓ |  ✓ |  65.3 $\pm$ 0.7 |  69.0 $\pm$ 0.6 |  70.9 $\pm$ 0.8 |  72.7 $\pm$ 0.8 |  55.6 $\pm$ 0.4 |  56.4 $\pm$ 0.8
JKNet [42] |  ✓ |  ✓ |  69.6 $\pm$ 1.0 |  73.2 $\pm$ 1.2 |  69.8 $\pm$ 1.1 |  72.0 $\pm$ 1.3 |  58.3 $\pm$ 0.7 |  60.5 $\pm$ 0.9
DGI [44] |  ✓ |  |  64.7 $\pm$ 0.5 |  68.5 $\pm$ 0.7 |  41.9 $\pm$ 0.8 |  61.1 $\pm$ 0.6 |  38.6 $\pm$ 0.9 |  40.4 $\pm$ 0.9
Structural Graph Neural Networks
DemoNet [45] |  ✓ |  ✓ |  70.7 $\pm$ 1.3 |  72.3 $\pm$ 1.1 |  72.6 $\pm$ 0.9 |  73.5 $\pm$ 0.6 |  59.5 $\pm$ 0.8 |  61.2 $\pm$ 0.8
Motif-CNN [46] |  ✓ |  ✓ |  66.4 $\pm$ 1.1 |  70.1 $\pm$ 1.3 |  71.5 $\pm$ 0.8 |  72.2 $\pm$ 0.6 |  54.3 $\pm$ 0.3 |  56.9 $\pm$ 0.5
MCN [47] |  ✓ |  ✓ |  67.1 $\pm$ 1.2 |  71.2 $\pm$ 1.1 |  71.9 $\pm$ 0.9 |  72.5 $\pm$ 0.6 |  54.7 $\pm$ 0.4 |  57.2 $\pm$ 0.6
Heterogeneous graph Neural Networks
HAN [56] |  ✓ |  ✓ |  68.2 $\pm$ 1.0 |  72.0 $\pm$ 1.3 |  73.1 $\pm$ 0.9 |  74.0 $\pm$ 0.7 |  60.7 $\pm$ 1.1 |  62.1 $\pm$ 0.8
MAGNN [57] |  ✓ |  ✓ |  68.9 $\pm$ 0.7 |  72.5 $\pm$ 0.7 |  74.7 $\pm$ 0.6 |  75.8 $\pm$ 0.7 |  62.1 $\pm$ 0.9 |  63.0 $\pm$ 0.5
Meta-GNN [58] |  ✓ |  ✓ |  71.3 $\pm$ 1.2 |  73.9 $\pm$ 1.4 |  74.6 $\pm$ 0.6 |  75.8 $\pm$ 0.6 |  61.7 $\pm$ 0.5 |  63.7 $\pm$ 0.7
Motif-regularized Graph Neural Networks (InfoMotif)
InfoMotif-GCN |  ✓ |  ✓ |  73.7 $\pm$ 1.2 |  77.4 $\pm$ 1.1 |  78.8 $\pm$ 0.4 |  79.0 $\pm$ 0.7 |  64.7 $\pm$ 0.8 |  65.0 $\pm$ 1.1
InfoMotif-JKNet |  ✓ |  ✓ |  75.6 $\pm$ 0.9 |  79.9 $\pm$ 0.8 |  75.5 $\pm$ 1.0 |  76.3 $\pm$ 1.2 |  60.7 $\pm$ 0.6 |  62.0 $\pm$ 0.6
InfoMotif-GAT |  ✓ |  ✓ |  72.4 $\pm$ 1.0 |  75.3 $\pm$ 1.4 |  77.1 $\pm$ 0.7 |  77.9 $\pm$ 0.6 |  62.8 $\pm$ 0.5 |  64.2 $\pm$ 0.5
Table 3.6: Node classification results (% test accuracy) on heterogeneous
graphs from bibliographic and movie networks, with schemas shown in figures
3.3(a) and 3.5(a). $\mathbf{X}$ and $\mathbf{Y}$ denote the use of node
attributes and training labels respectively. Heterogeneous GNN models (MAGNN,
Meta-GNN) typically outperform structural GNNs (DemoNet, Motif-CNN, MCN) and
type-agnostic message-passing GNNs (GCN, GraphSAGE, GAT). Our framework
InfoMotif (with typed network motif regularization) achieves consistent and
significant performance gains of 5% on average across the three heterogeneous
network datasets.

####  3.5.5 Heterogeneous Graphs ($\text{RQ}_{2}$)

In heterogeneous graphs, we train InfoMotif and other baselines that use
motifs/metagraphs using typed 3-node network motifs (shown in Figures 3.3(b)