Dual-Primal Graph Convolutional Networks
Federico Monti1 , Oleksandr Shchur2 , Aleksandar Bojchevski2 , Or Litany4 ,Stephan Günnemann2 , and Michael Bronstein1,3
1

2

USI Lugano
Technical University of Munich
3
Imperial College London
4
Facebook AI Research

Abstract. In recent years, there has been a surge of interest in developing
deep learning methods for non-Euclidean structured data such as graphs.
In this paper, we propose Dual-Primal Graph CNN, a graph convolutionalarchitecture that alternates convolution-like operations on the graph andits dual. Our approach allows to learn both vertex- and edge featuresand generalizes the previous graph attention (GAT) model. We provide
extensive experimental validation showing state-of-the-art results on avariety of tasks tested on established graph benchmarks, including CORA
and Citeseer citation networks as well as MovieLens, Flixter, Douban
and Yahoo Music graph-guided recommender systems.

1

Introduction

Recently, there has been an increasing interest in developing deep learning
architectures for data with non-Euclidean structure, such as graphs or manifolds.
Such methods, known under the name geometric deep learning [6], have been
applied in a variety of applications, from computer graphics, vision [27,5,24,38],
and medicine [33,43] to chemistry [12,13] and high energy physics [17].
One of the drawbacks of graph CNNs described above is that the convolution
operations are only applied to vertex features and the underlying domain isconsidered as fixed. In many situations, this can be a major disadvantage, as thegraph can be noisy or only known approximately (e.g. in recommender systems kNN graphs are typically computed a priori based on additional meta-information,
which does not necessarily represent the true social relationships existing amongusers). Furthermore, while vertex features can be informative, there is no clean
mechanism to take advantage of edge features that are more complex than scalars.
The key contribution of our paper is an extension of the graph attention
mechanism to edges using the dual graph, whose vertices correspond to theedges of the original graph. The proposed Dual-Primal Graph CNN (DPGCNN)
addresses the aforementioned issues and achieves superior performance on abroad range of tasks.

22Monti et al.

Graph Convolutional Networks

Definitions. Let G = {V, E, A} be a given weighted undirected graph withvertices V = {1, . . . , n}, edges E ⊆ V × V s.t. (i, j) ∈ E iff (j, i) ∈ E, and edge
weights aij = aji ≥ 0 for (i, j) ∈ E and zero otherwise. We denote by Ni
a neighborhood of vertex i; Nip denotes the p-hop neighborhood. The graphstructure is represented by the n × n symmetric adjacency matrix A = (aij ).
We definegraph Laplacian ∆ = I − D−1/2 AD−1/2 , where D =P the normalizedP
diag( j6=1 a1j , . . . , j6=n anj ) denotes the degree matrix. In the above setting, theLaplacian is a symmetric matrix admitting an eigendecomposition ∆ = ΦΛΦ>>with orthonormal eigenvectors Φ = (φ>1 , . . . , φn ) and non-negative eigenvalues
0 = λ1 ≤ λ2 ≤ . . . λn arranged into a diagonal matrix Λ = diag(λ1 , . . . , λn ).
We are interested in manipulating functions f : V → R defined on the verticesof the graph, which can be represented as vectors f ∈ Rn . The space of suchfunctions is a Hilbert space with the standard inner product hf , gi = f > g. The
eigenvectors of the Laplacian form an orthonormal basis in the aforementioned
Hilbert space, allowing a Fourier decomposition of the form f = ΦΦ> f , wheref̂ = Φ> f is the graph Fourier transform of f . The Laplacian eigenvectors thus
play the role of the standard Fourier atoms and the corresponding eigenvalues
that of the respective frequencies. Finally, a convolution operation can be definedin the spectral domain by analogy to the Euclidean case as f ? g = Φ(f̂ · ĝ) =Φ(Φ> f ) · (Φ> g).
Spectral graph CNNs. Bruna et al. [7] exploited the above formulation for
designing graph convolutional neural networks, in which a spectral convolution
operation has the following form:
f 0 = ΦĜΦ> f ,(1)

where Ĝ = diag(ĝ1 , . . . , ĝn ) is a diagonal matrix of spectral multipliers representing the filter and f 0 is the filter output. Here, for the sake of simplicity, we
assume a scalar input, though like in classical CNNs, the basic spectral convolution operation (1) can be applied in combination with linear transformations of
input and output features, non-linearities, and pooling layers (implemented asgraph coarsening). Note that this formulation explicitly assumes the graph to be
undirected, since the orthogonal eigendecomposition of the Laplacian requires asymmetric adjacency matrix.
ChebNet. Defferrard et al. [10] considered the spectral CNN framework
with
Pppolynomial filters represented in the Chebyshev basis, τθ (λ) = j=0 θj Tj (λ),
where Tj (λ) = 2λTj−1 (λ) − Tj−2 (λ) denotes the Chebyshev polynomial of degreej, with T1 (λ) = λ and T0 (λ) = 1. A single filter of this form can be efficiently
computed by applying powers of the graph Laplacian to the feature vector,
f0 = Φ

pX
j=0

θj Tj (Λ̃)Φ> f =

p
X

˜ ,
θj Tj (∆)f

(2)

j=0

thus avoiding its eigendecomposition altogether. Here λ̃ is a frequency rescaled in
˜ = 2λ−1 ∆−I is the rescaled Laplacian with eigenvalues Λ̃ = 2λ−1 Λ−I.
[−1, 1], ∆nnDual-Primal Graph Convolutional Networks

3

The computational complexity thus drops from O(n2 ) as in the case of spectral
CNNs to O(|E|), and if the graph is sparsely connected (with maximum degree ofO(1)), to O(n). Furthermore, the graph can now be directed, as the framework
does not rely on explicit eigendecomposition.
Several follow-up works refined and extended this scheme. Kipf and Welling[22] proposed a simplification of ChebNet (referred to as Graph Convolutional
Network or GCN) by limiting the order of the polynomial to p = 1 and using a
re-normalization of the Laplacian to avoid numerical instability.
Levie et al. [23] replaced the polynomial filter functions by rational functions
based on the complex Cayley transform (CayleyNet), allowing to achieve better
spectral resolution of the filters, especially relevant for graphs with communities.
Monti et al. [32] proposed using graph motifs [29,3] to create anisotropic kernels(MotifNet). Finally, Monti et al. [31] proposed an extension of ChebNet to multiple
graphs (Multi-Graph CNN or MGCNN) in the context of graph-guided matrix
completion and recommender systems.
Mixture Model Networks (MoNet). Monti et al. [30] proposed a spatialdomain Graph CNN (MoNet) generalizing the notion of ‘patches’ to graphs. The
neighbors of each vertex i are assigned local pseudo-coordinates uij ∈ Rd , j ∈ Ni .
The analogue of a convolution is then defined as a Gaussian mixture in thesecoordinates,
fi0 =

M
X

>

wm

m=1

−1

e−(uij −µm ) Σm (uij −µm )

X
P
j∈Ni

k∈Ni e−(uik −µm )> Σ−1m (uik −µm )

fj ,

(3)

where µ1 , . . . , µM ∈ Rd and Σ1 , . . . , , ΣM ∈ Sd+ are learnable parameters of theGaussians. The Gaussians define local weights extracting a local representationof f around i that generalizes the notion of a ‘patch’; the additional learnable
parameters w1 , . . . , wM correspond to filter coefficients in classical convolution.
Graph Attention Networks (GAT). Veličkovic̀ et al. [37] proposed an
attention mechanism for learning the relevance of each neighbor. The convolution
operation with attention has the form:
fi0 =

X
j∈Ni1

αij fj ,eη(a([fi , fj ]))η(a([fi , fk ]))k∈N 1 eαij = P

(4)iwhere η denotes the Leaky ReLU, and a([fi , fj ]) is some transformation of theconcatenated features at vertices i and j, implemented in [37] as a fully connected(linear) layer.
Performing this process multiple times with different transformations (multiple
heads) produces filters capable of focusing on different classes of vertices in aneighborhoods. We note that GAT can be considered as a particular instance of
MoNet (3), where the pseudo-coordinates uij are just the features of the nodes iand j.

4

Monti et al.
1

0,4

2

0,1

2,3

0,2

0
4

3

0,3

1,2

Fig. 1. Primal (left) and dual (right) graphs. For clarity, only the ego graph of primaledge (0, 2) is shown for the dual.

3

Learning on dual/primal graphs

Dual graphs. Let G = (V, E) be a given directed graph, to which we refer as
the primal graph. The dual (also known in graph theory as the line (di)graph oradjoint graph) of G, denoted by G̃ = (Ṽ = E, Ẽ), is constructed as follows [16]:each dual vertex (i, j) ∈ Ṽ corresponds to a primal edge (i, j) ∈ E, two dual
vertices (i, j), (i0 , j 0 ) ∈ Ṽ are connected by an edge in G̃ if they share direction andat least an endpoint in G. Figure 1 provides an illustration of this construction
for an undirected graph.
We summarize the properties of dual graphs and refer the reader to [16,15,14]
for additional details. If the primal graph G is connected, so is its dual G̃. The
dual graph has Pñ = |Ṽ| = |E| vertices. If G is undirected, the number of dualnedges is |Ẽ| = 12 i=1 d2i − |E|, where di denotes the degree of primal vertex i. If
Pnout− |E| edges [1], where din and
G is directed, the dual contains |Ẽ| = i=1 din
i di
out
d
denote the in- and out-degrees, respectively. The complexity of constructingout
out
the dual graph is O(|E|doutis the maximummax ), where dmax = maxi=1,...,n divertex out-degree in the primal graph. While the worst-case complexity is O(n3 )for fully-connected graphs, for sparsely-connected graphs encountered in practicethe cost is linear in n.
In a concurrent work, [9] use dual graphs in GNNs for supervised community
detection, which is different from the tasks considered in this paper (classification& matrix completion).
3.1

Dual-Primal GCNN

We propose a Dual-Primal Graph CNN (DPGCNN) architecture, which alternates
between dual and primal convolutional layers. The dual convolutional layer
applies a GAT on the dual graph to produce features on the edges of the primal
graph. These primal edge features are used in the primal convolutional layer tocompute attention scores for another GAT, producing primal vertex features.
The implementation of both layers are detailed in the following.
Dual convolution. Let F denote the n × q matrix of input primal vertex
features, where each row corresponds to a vertex in the primal graph G. The dual
vertex features (or equivalently, primal edge features) f̃ij = [fi , fj ] are constructedDual-Primal Graph Convolutional Networks

5

by concatenating the respective primal vertex features (row vectors fi , fj ), foreach (i, j) ∈ E. We denote by F̃ the ñ × 2q matrix of all the dual vertex features
arranged row-wise. To avoid ambiguity, for undirected graphs we construct two
nodes in the dual for every undirected edge {i, j}, namely (i, j), (j, i) ∈ Ṽ, andwe connect a dual node (i, j) to all the nodes corresponding to edges pointing toi or departing from j. This avoids establishing an order among vertices which
otherwise would be required to define edge features (if one edge (i, j) is represented
by one dual node, one needs to define whether the features of i or j comes firstin the concatenation).
Applying GAT to the dual graph G̃ with features F̃ has the form
0f̃ij
= ξd 

Xr∈Ni

α̃ij,ik = Xr∈Niα̃ij,ir f̃ir W̃ +X

α̃ij,tj f̃tj W̃ ,

(5)

t∈Nj

eη(ã([f̃ij W̃, f̃ik W̃]))X
eη(ã([f̃ij W̃, f̃tj W̃]))eη(ã([f̃ij W̃, f̃ir W̃])) +

(6)

t∈Nj

0
where f̃ij
denotes the q̃-dimensional output feature of a dual vertex (i.e., primaledge) (i, j), α̃ij,ik are the dual attention scores, W̃ is a 2q × q̃ learnable weightmatrix, ã is a linear layer mapping 2q̃-dimensional input to a scalar output, ξd isthe dual layer activation function (typically, a ReLU) and η is the Leaky ReLU.

The dual convolution on G̃ is equivalent to exchanging information acrossprimal edges which share common directions. In particular, primal edge (i, j)
exchanges information only with edges that income to primal vertex i or outgo
from from primal vertex j. This additional diffusion naturally allows to bettercharacterize the behavior of each single connection, as every edge (i, j) is now
not only represented by the features associated with the corresponding incident
vertices but also by an aggregated representation of all the edges that present
common spreading patterns (i.e., that bring information to i or spread informationfrom j). This naturally allows to predict better attention scores. Note that suchdescription could not be achieved with two GAT layers as our aggregation stepin equations (5)-(6) depends on dual connectivity plus the concatenation of
the features of incident vertices and not on the features of the single vertices
themselves. For a concrete example, consider Figure 2. Since vertices 2 and 3 havethe same attribute vectors (f2 = f3 ), primal GAT will produce the same attention
scores for edges (1, 2) and (1, 3). In contrast, dual GAT (our dual convolutional
layer) is able to differentiate between them by aggregating different edge features
for the two different edges.
Primal convolution. The convolution on the primal graph is applied usinga GAT on the primal vertex features F. The key difference compared to thesimple GAT (4) is that primal attention scores are computed using the dual

6Monti et al.

vertex features F̃0 produced by the dual convolution,!
0Xeη(a(f̃ij ))0,fi = ξp
αij fi W ,αij = X0eη(a(f̃ik ))
r∈Ni

(7)

k∈Ni

where fi0 denotes the q 0 -dimensional output features at primal vertex i, αij are
the primal attention scores, ξp is the primal layer activation function, W is aq × q 0 learnable weight matrix, and a is a linear layer mapping q̃-dimensional
input to a scalar output.
3.2

Architecture Variants

GAT as an instance of DPGCNN. The primal and dual convolutional layers
can be used as building blocks of graph CNNs. The dual convolution precedes one
or more primal convolutional layers; multiple layers can be used to obtain deepneural networks. GAT is a particular setting of DPGCNN obtained by setting
the dual attention scores α̃ij,ik = 0 for k 6= j and 1 otherwise.
DPGCNN with polynomial filters. Convolution with polynomials of normalized adjacency matrices are obtained with DPGCNN by computing different
attention scores for different orders:
!
p
X
(l)
0
fi = ξ
fi Θl ,
(8)
(k)
fi =

l=0
(k) (k−1)
αij fj
,
j∈Ni

X

(0)

fi

= fi

(9)

where Θl denote polynomial coefficients and the recursive definition is similar(k)
to [32]. αij is obtained as described in Eq. 6 or 7 if operating on the primal or
dual respectively. Such an approach can be exploited in Eq. 5 or 7 to further
enrich the filters on both primal and dual graphs.
Arbitrary edge features. We have so far assumed for simplicity that theedge features are derived from vertex features, fij = [fi , fj ]. Our framework
naturally allows to apply dual convolutional layers to arbitrary edge features,
both vector- or scalar-valued.
 0f2 1
1
2

1

3  
0
f3 1
1

Fig. 2. Unlike GAT, DPGCNN is able to distinguish edges (1, 2) and (1, 3), even thoughnodes (1) and (2) have the same feature vectors f2 = f3 .

Dual-Primal Graph Convolutional Networks

4

Experiments

4.1

Citation Networks

7

Vertex Classification. The first task we consider is a semi-supervised (transductive) learning problem on two citation networks (CORA and Citeseer [36]),
following the experimental setup from [41,21,30,37]. The vertices of the citationgraph represent scientific papers and edges are citations. The task is to classify
each vertex in the graph according to its publication field. CORA contains 2708
vertices, 5429 edges, 7 different categories and 1433 binary features per vertex;
Citeseer contains 3327 vertices, 4732 edges, 6 different classes and 3703 features
per vertex.
For each dataset we repeat verbatim the experiments presented in [21,30,37].
As training set, we use 140 vertices sampled from CORA and 120 from Citeseer,using the split from [41]. We use the architecture of [37] (i.e. 2 convolutional
layers, 8 heads for first layer with 8 features as output per head, 1 head for thesecond layer with # classes as output) with one head and 32 features as output
when convolving on the dual graph. Training settings, including dropout, weightdecay and learning rate are as in [37]. Table 1 summarizes the results, averaged
over 100 runs to account for different random initializations. DPGCNN beats all
the competing architectures, albeit by a small margin.
Table 1. Vertex classification accuracy on CORA and Citeseer citation networks,
averaged over 100 runs.
Method

Cora

MLP
51.1%
ManiReg [2] 59.5%
SemiEmb [39] 59.0%
LP [42]68.0%
DeepWalk [34] 67.2%
ICA [25]
75.1%
Planetoid [41] 75.7%
ChebNet [10]GCN [21]
MoNet [30]
GAT [37]
DPGCNN

Citeseer
46.5%
60.1%
59.6%
45.3%
43.2%
69.1%
64.7%

81.2%
69.8%
81.5%
70.3%
81.7 ± 0.5% –83.0 ± 0.7% 72.5 ± 0.7%
83.3 ± 0.5% 72.6 ± 0.8%

We further reproduced a different setting of the same experiment reported
in [23], in which 500 vertices were sampled from CORA for training5 . We used5

Training/validation/test indices together with CayleyNet performance have beenobtained by the authors of the paper, scaled unnormalized laplacian has been used
for the reported CayleyNet’s accuracies.

8

Monti et al.

an architecture with two convolutional layers and 16 features as output fromconvolutional layers on both primal and dual graphs (realized as described inequation (8) with monomial bases and attention). Dual convolution was applied
only in the second layer, in order to reduce the overall number of parameters.
Attention with one head was used on both primal and dual to provide a faircomparison with CayleyNet [23]. Dropout, weight decay and learning rate wereas in [23]. We compare our results to CayleyNet [23] and GAT [37] with the samearchitecture, using polynomial filters of different order (GAT with polynomial
filters was implemented according to equation 8, using primal graph only). Table 2reports the performance averaged on 20 runs. Our DPGCNN beats the competingarchitectures.
Table 2. Number of parameters / Vertex classification accuracy on CORA citation
network (500 training samples) using polynomial filters of different order.
Order p
1
2
3
4
5
6

CayleyNet

GAT

DPGCNN

46K / 88.1 ± 0.6% 46K / 88.65 ± 0.58% 47K / 88.92 ± 0.51%
69K / 88.0 ± 0.5% 69K / 88.00 ± 0.39% 71K / 88.22 ± 0.41%
92K / 87.6 ± 0.6% 92K / 87.54 ± 0.52% 95K / 87.69 ± 0.42%
115K / 86.4 ± 0.8% 115K / 87.06 ± 0.42% 118K / 87.30 ± 0.50%
138K / 86.5 ± 0.8% 138K / 86.67 ± 0.52% 142K / 86.68 ± 0.74%
161K / 86.7 ± 0.7% 161K / 86.38 ± 0.57% 165K / 86.50 ± 0.61%

Link Direction Prediction. The second task we address is to predict thedirection of links, which we cast as a semi-supervised classification problem on
the dual graph. For this experiment, we used a directed version of the CORA
graph [32,4], of which we took a subset containing 1118 vertices (each represented
by a 8710-dimensional feature vector) and 4155 directed edges. All the edges
were turned into undirected; given an undirected edge {i, j}, the goal was topredict the direction of the original edge. The dual graph contains every edge inthe two possible directions i.e. (i, j), (j, i) ∈ Ṽ, link prediction in the primal isthus a binary classification problem on the dual. 10% of edges’ directions wereused for training, 10% for validation, and 10% for testing.
Three different architectures were tested: GAT operating only on the primal
graph (Primal GAT), GAT operating only on the dual graph (Dual GAT), anda DPGCNN operating on both. Three convolutional layers and a final fully
connected layer followed by softmax were used in all the three architectures. The
final FC layer was applied (i) on the concatenation of the features of nodes i andj for Primal GAT since outputs only node features, (ii) on the features of edge(i, j) for Dual GAT, and (iii) on the concatenation of the two for DPGCNN. In
Dual GAT, we had an additional initial dimensionality reduction layer to assure
approximately equal overall number of parameters in all the three models for afair comparison. DPGCNN uses primal and dual convolution in every layer. Eachdual convolutional layer receives as input for each edge the refined edge features

Dual-Primal Graph Convolutional Networks

9

concatenated with the refined vertex features of its incident nodes producedby the previous dual/primal convolutional layer. Edge features were initializedwith the features of incident nodes for both Dual GAT and DPGCNN. Meancross-entropy, dropout with keep probability of 0.9, and learning rate of 10−2
were used for all models. Table 4.1 presents the link prediction results averaged
on 100 runs, showing that DPGCNN outperforms both competitors.
Table 3. Link direction prediction accuracy on directed CORA, averaged over 100
runs.
MethodAccuracy#ParamDual GAT 72.94 ± 1.12% 140K
Primal GAT 74.95 ± 1.38% 140K
DPGCNN 76.45 ± 1.07% 142K

4.2

Graph-Guided Matrix Completion

In our final experiment, we address the problem of item recommendation, formulated as matrix completion problem on user and item graphs [30]. Such problems
are also known under the name of geometric- or graph-guided matrix completion.
The task is, given a sparsely sampled matrix of scores assigned by users (columns)
to items (rows), to fill in the missing scores. The similarities between users anditems are given in the form of column- and row graphs, respectively. Monti et al.
[30] approached this problem as learning with a separable recurrent Multi-Graph
CNN (MGCNN) architecture, using an extension of ChebNets [10] to matrices
defined on multiple graphs in order to extract spatial features from the scorematrix; these features are then fed into an RNN producing a sequential estimationof the missing scores. We repeated verbatim the experiment of [30,23] on several
standard datasets used in the recommender systems literature (MovieLens [28],Flixster [19], Douban [26], and YahooMusic [11]), using different convolutional
layers inside RMGCNN (Chebyshev [10], Cayley [23], GAT [37] and the proposed
Dual-Primal convolution). For reference, we also report the results of some standard matrix completion methods that are not learning-based. For Douban andYahoo Music datasets, only a single user/items graph was used, as described in[31].
Polynomial filters (Eq. 8) of degree p = 4 were used for convolution on the
primal graph; different attention scores were computed according to (Eq. 7) for
every order and for every diffusion iteration. We used 4 heads on the dual forevery dataset besides Douban where just one head has been exploited becauseof overfitting. Eight features have been produced as output for each head on
the dual. GAT hyperparametrs were determined by cross-validation for Flixster
and Yahoo Music; the same hyperparameters were used for DPGCNN. For theremaining datasets, we used hyperparameters from [31]. To make the problem
more tractable with classic GPUs (in our experiments we used Nvidia Titan X

10Monti et al.

with 12GB RAM), randomly sparsified versions of the dual graph were used with
DPGCNN for Movielens (100 neighbors in the dual), Flixster (18 neighbors) andYahoo Music (30 neighbors). Such sparsification was pre-computed and fixed
throughout the entire learning and testing process. Table 4 shows the results fordifferent architectures. DPGCNN outperforms all the competing Graph CNN
architectures on all the considered datasets, and beats by a significant margin thestandard recommendation systems. Table 5 compares the number of parameters
required by MGCNN implemented with GAT and DPGCNN.
Table 4. Performance (RMSE) of several matrix completion methods on the MovieLens,
Flixster, Douban and Yahoo Music datasets (– indicates that the result was not reported
in the original paper). GAT’s performance has been computed in this work.

MGCNN

MethodIMC [18,40]
GMC [20]
MC [8]GRALS [35]MovieLens
1.653
0.996
0.973
0.945

Flixster
–
–
–
1.245

Douban Yahoo
–
–
–
–
–
–
0.833
38.042

0.929
0.922
0.929
0.915

0.926
–
0.931
0.902

0.801
–
0.791
0.789

Chebyshev [31]Cayley [23]GAT [37]
Dual/Primal

22.415–22.10221.970

Table 5. Number of parameters for MGCNN with GAT layers and our DPGCNN.
Note how both solutions present same number of parameters for all considered datasets.
The increased number of parameters for Douban and Yahoo is due to the single graphused for implementing MGCNN.
MethodGAT-MGCNN [37]Dual/Primal-MGCNN

5

MovieLens
23K
25K

Flixster
22K
24K

Douban
41K
42K

Yahoo
41K
42K

Conclusions

We presented a Dual-Primal Graph Convolutional Network able to realize richconvolutional filters by operating on both the primal and the dual graph. Ourarchitecture achieves state-of-the-art performance on vertex classification, link
prediction and matrix completion problems by requiring a small amount of additional parameters. In future works we plan to further investigate the importanceof the dual graph by exploring applications to Computer Vision and Graphics(e.g. point clouds and meshes) as well as analyzing datasets where edge features
are available.

Dual-Primal Graph Convolutional Networks

11

References
1. Aigner, M.: On the linegraph of a directed graph. Mathematische Zeitschrift 102(1),56–61 (1967)
2. Belkin, M., Niyogi, P., Sindhwani, V.: Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. JMLR 7, 2399–2434 (2006)
3. Benson, A.R., Gleich, D.F., Leskovec, J.: Higher-order organization of complex
networks. Science 353(6295), 163–166 (2016)
4. Bojchevski, A., Günnemann, S.: Deep gaussian embedding of attributed graphs:
Unsupervised inductive learning via ranking. arXiv:1707.03815 (2017)
5. Boscaini, D., Masci, J., Rodolà, E., Bronstein, M.M.: Learning shape correspondencewith anisotropic convolutional neural networks. In: Proc. NIPS (2016)
6. Bronstein, M.M., Bruna, J., LeCun, Y., Szlam, A., Vandergheynst, P.: Geometricdeep learning: going beyond euclidean data. IEEE Signal Processing Magazine
34(4), 18–42 (2017)
7. Bruna, J., Zaremba, W., Szlam, A., LeCun, Y.: Spectral networks and locallyconnected networks on graphs. arXiv:1312.6203 (2013)
8. Candès, E., Recht, B.: Exact Matrix Completion via Convex Optimization. Foundations of Computational Mathematics 9(6), 717–772 (2009)
9. Chen, Z., Li, L., Bruna, J.: Supervised community detection with line graph neuralnetworks. ICLR (2018)
10. Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks ongraphs with fast localized spectral filtering. In: Proc. NIPS (2016)
11. Dror, G., Koenigstein, N., Koren, Y., Weimer, M.: The Yahoo! music dataset andKDD-Cup’11. In: KDD Cup (2012)
12. Duvenaud, D.K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., AspuruGuzik, A., Adams, R.P.: Convolutional networks on graphs for learning molecularfingerprints. In: Proc. NIPS (2015)
13. Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., Dahl, G.E.: Neural message
passing for quantum chemistry. arXiv:1704.01212 (2017)
14. Gross, J.L., Yellen, J.: Graph theory and its applications. CRC press (2005)
15. Harary, F.: Graph theory. Addison-Wesley (1969)
16. Harary, F., Norman, R.Z.: Some properties of line digraphs. Rendiconti del Circolo
Matematico di Palermo 9(2), 161–168 (1960)
17. Henrion, I., Brehmer, J., Bruna, J., Cho, K., Cranmer, K., Louppe, G., Rochette,
G.: Neural message passing for jet physics (2018)18. Jain, P., Dhillon, I.S.: Provable inductive matrix completion. arXiv:1306.0626 (2013)
19. Jamali, M., Ester, M.: A matrix factorization technique with trust propagation forrecommendation in social networks. In: Proc. Recommender Systems (2010)
20. Kalofolias, V., Bresson, X., Bronstein, M.M., Vandergheynst, P.: Matrix completionon graphs. arXiv:1408.1717 (2014)
21. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional
networks (2017)
22. Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional
networks. arXiv:1609.02907 (2016)
23. Levie, R., Monti, F., Bresson, X., Bronstein, M.M.: Cayleynets: Graph convolutional
neural networks with complex rational spectral filters. arXiv:1705.07664 (2017)
24. Litany, O., Bronstein, A., Bronstein, M., Makadia, A.: Deformable shape completion
with graph convolutional autoencoders. CVPR (2018)
25. Lu, Q., Getoor, L.: Link-based classification. In: Proc. ICML (2003)

12

Monti et al.

26. Ma, H., Zhou, D., Liu, C., Lyu, M., King, I.: Recommender systems with social
regularization. In: Proc. Web Search and Data Mining (2011)
27. Masci, J., Boscaini, D., Bronstein, M., Vandergheynst, P.: Geodesic convolutional
neural networks on riemannian manifolds. In: Proc. 3dRR (2015)28. Miller, B.N., et al.: MovieLens unplugged: experiences with an occasionally connected recommender system. In: Proc. Intelligent User Interfaces (2003)
29. Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network
motifs: simple building blocks of complex networks. Science 298(5594), 824–827(2002)
30. Monti, F., Boscaini, D., Masci, J., Rodolà, E., Svoboda, J., Bronstein, M.M.:
Geometric deep learning on graphs and manifolds using mixture model CNNs. In:
Proc. CVPR (2017)31. Monti, F., Bronstein, M.M., Bresson, X.: Geometric matrix completion with recurrent multi-graph neural networks. In: Proc. NIPS (2017)32. Monti, F., Otness, K., Bronstein, M.M.: Motifnet: a motif-based graph convolutional
network for directed graphs. arXiv:1802.01572 (2018)33. Parisot, S., Ktena, S.I., Ferrante, E., Lee, M., Moreno, R.G., Glocker, B., Rueckert,
D.: Spectral graph convolutions for population-based disease prediction. In: Proc.
MICCAI (2017)34. Perozzi, B., Al-Rfou, R., Skiena, S.: DeepWalk: Online learning of social representations. In: Proc. KDD (2014)
35. Rao, N., Yu, H.F., Ravikumar, P.K., Dhillon, I.S.: Collaborative filtering with graphinformation: Consistency and scalable methods. In: Proc. NIPS (2015)36. Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., Eliassi-Rad, T.: Collectiveclassification in network data. AI Magazine 29(3), 93 (2008)
37. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graphattention networks. arXiv:1710.10903 (2017)
38. Wang, Y., Sun, Y., Liu, Z., Sarma, S.E., Bronstein, M.M., Solomon, J.M.: Dynamic
graph CNN for learning on point clouds. arXiv:1801.07829 (2018)
39. Weston, J., Ratle, F., Mobahi, H., Collobert, R.: Deep learning via semi-supervised
embedding. In: Neural Networks: Tricks of the Trade, pp. 639–655 (2012)
40. Xu, M., Jin, R., Zhou, Z.H.: Speedup matrix completion with side information:
Application to multi-label learning. In: Proc. NIPS (2013)
41. Yang, Z., Cohen, W., Salakhutdinov, R.: Revisiting semi-supervised learning withgraph embeddings. In: Proc. ICML (2016)
42. Zhu, X., Ghahramani, Z., Lafferty, J., et al.: Semi-supervised learning using gaussian
fields and harmonic functions. In: Proc. ICML (2003)
43. Zitnik, M., Agrawal, M., Leskovec, J.: Modeling polypharmacy side effects withgraph convolutional networks. arXiv:1802.00543 (2018)

Dual-Primal Graph Convolutional Networks

A

13

Visualizations

Fig. 3. Top: primal graph of the CORA citation network. Vertex colors code thegroundtruth classes. Vertex positions are the learned primal vertex features, mapped
to the plane using tSNE. Edge thickness represents the edge attention scores. Bottom:
dual graph of CORA. Edge colors represent the groundtruth classes.

14Monti et al.

Fig. 4. Top: primal graph of the portion of directed CORA used for link prediction. Vertex colors code the ground-truth classes. Bottom: corresponding dual graph. In green/red
are dual vertices (primal edges) that were correctly/wrongly classified, respectively.