A Structural Graph Representation Learning Framework
Ryan A. Rossi
Adobe Research
Nesreen K. Ahmed
Intel Labs
Eunyee Koh
Adobe Research
Sungchul Kim
Adobe Research
Anup Rao
Adobe Research
Yasin Abbasi-Yadkori
VinAI
ABSTRACT
The success of many graph-based machine learning tasks highly
depends on an appropriate representation learned from the graph
data. Most work has focused on learning node embeddings that
preserve proximity as opposed to structural role-based embeddings
that preserve the structural similarity among nodes. These methods
fail to capture higher-order structural dependencies and connectiv-
ity patterns that are crucial for structural role-based applications
such as visitor stitching from web logs. In this work, we formu-
late higher-order network representation learning and describe a
general framework called HONE for learning such structural node
embeddings from networks via the subgraph patterns (network mo-
tifs, graphlet orbits/positions) in a nodes neighborhood. A general
diusion mechanism is introduced in HONE along with a space-
ecient approach that avoids explicit construction of the k-step
motif-based matrices using a k-step linear operator. Furthermore,
HONE is shown to be fast and ecient with a worst-case time
complexity that is nearly-linear in the number of edges. The ex-
periments demonstrate the eectiveness of HONE for a number of
important tasks including link prediction and visitor stitching from
large web log data.
KEYWORDS
Structural node embeddings, role-based embeddings, structural
similarity, roles, network motifs, graphlets, structural embeddings
ACM Reference Format:
Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, Sungchul Kim, Anup Rao,
and Yasin Abbasi-Yadkori. 2020. A Structural Graph Representation Learning
Framework. In The Thirteenth ACM International Conference on Web Search
and Data Mining (WSDM ’20), February 3–7, 2020, Houston, TX, USA. ACM,
New York, NY, USA, 9 pages. https://doi.org/10.1145/3336191.3371843
1 INTRODUCTION
Structural role discovery [
40
] aims to reveal nodes with topologi-
cally similar neighborhoods while being possibly far away in the
graph or even in dierent graphs altogether. Intuitively, two nodes
belong to the same role if they are structurally similar (with re-
spect to the general connectivity and subgraph patterns in a nodes
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for prot or commercial advantage and that copies bear this notice and the full citation
on the rst page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specic permission and/or a
fee. Request permissions from permissions@acm.org.
WSDM ’20, February 3–7, 2020, Houston, TX, USA
© 2020 Association for Computing Machinery.
ACM ISBN 978-1-4503-6822-3/20/02.. . $15.00
https://doi.org/10.1145/3336191.3371843
neighborhood). Roles may represent higher-order subgraph pat-
terns (network motifs) such as star-center (hub) nodes, star-edge
nodes, near-cliques or bridge nodes connecting dierent regions of
the graph. Most work on embeddings have focused on preserving
the notion of proximity (closeness) as opposed to the notion of
structural similarity proposed in [
40
]. As such, two nodes with
similar proximity-based embeddings are guaranteed to be near one
another in the graph (a property of communities [
17
]). However,
learning structural role-based embeddings that preserve the notion
of structural similarity are important for many predictive modeling
applications [
41
] such as the visitor stitching task where the goal
is to predict the web sessions that belong to the same user.
To address this problem and learn more appropriate structural
role-based embeddings for such applications, we propose a general
framework called Higher-Order Network Embeddings (HONE) for
learning higher-order structural node embeddings based on net-
work motifs (graphlets). The approach leverages all available motif
counts by deriving a weighted motif graph
W
t
from each network
motif
H
t
∈ H
and uses these as a basis to learn higher-order struc-
tural node embeddings. The HONE framework expresses a new
class of structural node embedding methods based on a set of motif-
based matrices and their powers. We also introduce diusion-based
HONE variants that leverage a general diusion mechanism to im-
prove predictive performance. Furthermore, this work describes a
space-ecient approach to avoid explicit construction of the k-step
motif-based matrices by dening a k-step linear operator. The time
complexity of HONE is shown to be linear in the number of edges
and therefore is fast and scalable for large networks. Empirically,
we investigate the HONE variants and their properties extensively
in Section 4. The experiments demonstrate the eectiveness of
higher-order structural embeddings for link prediction as we achieve
a mean relative gain in AUC of 19% over all embedding methods and
network data sets. In addition, the diusion-based HONE variants
achieve a mean gain of 1
.
97% in AUC over the other HONE variants.
We also demonstrate the eectiveness of HONE for visitor stitching
using two real-world company data sets with known ground-truth.
Finally, HONE is shown to capture roles (structural similarity) as it
successfully uncovers the actual exact role assignments in graphs
with known ground-truth.
Contributions
: This work makes three important contributions.
First, we introduce the problem of higher-order (motif-based) net-
work embedding. Second, we propose a general class of methods for
learning such structural (role-based) embeddings via higher-order
network motifs. The resulting embeddings are shown to be role-
based (structural) and capture the notion of structural similarity
(roles) [
40
] as opposed to proximity/community-based embeddings
