query: I aim to enhance the expressive power of Graph Neural Networks (GNNs) to differentiate between graphs that are structurally different but possess the same local neighborhood structure, a task they traditionally struggle with. To achieve this, I plan to develop structure-related features that can aid GNNs in representing any set of nodes, thereby increasing their expressive power. Could you suggest some standard graph-distance measures, such as the shortest path distance, that could be used to capture the distance between the node set and each individual node in the graph? Furthermore, I want these features to enhance the ability of GNN nodes to gather information from neighboring nodes for self-updating. Importantly, these features should leverage the sparse structure of the underlying graph, ensuring computational efficiency and scalability. Finally, I intend to demonstrate the advantages of my proposed features by testing them on standard network tasks, such as structural role prediction. Could you also suggest other tasks where these features could be tested?

positive:
Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to
measure the expressive power of graph neural networks (GNN). It was shown that
the popular message passing GNN cannot distinguish between graphs that are
indistinguishable by the 1-WL test (Morris et al. 2018; Xu et al. 2019).
Unfortunately, many simple instances of graphs are indistinguishable by the
1-WL test.
  In search for more expressive graph learning models we build upon the recent
k-order invariant and equivariant graph neural networks (Maron et al. 2019a,b)
and present two results:
  First, we show that such k-order networks can distinguish between
non-isomorphic graphs as good as the k-WL tests, which are provably stronger
than the 1-WL test for k>2. This makes these models strictly stronger than
message passing models. Unfortunately, the higher expressiveness of these
models comes with a computational cost of processing high order tensors.
  Second, setting our goal at building a provably stronger, simple and scalable
model we show that a reduced 2-order network containing just scaled identity
operator, augmented with a single quadratic operation (matrix multiplication)
has a provable 3-WL expressive power. Differently put, we suggest a simple
model that interleaves applications of standard Multilayer-Perceptron (MLP)
applied to the feature dimension and matrix multiplication. We validate this
model by presenting state of the art results on popular graph classification
and regression tasks. To the best of our knowledge, this is the first practical
invariant/equivariant model with guaranteed 3-WL expressiveness, strictly
stronger than message passing models.

positive:
Learning node embeddings that capture a node's position within the broader
graph structure is crucial for many prediction tasks on graphs. However,
existing Graph Neural Network (GNN) architectures have limited power in
capturing the position/location of a given node with respect to all other nodes
of the graph. Here we propose Position-aware Graph Neural Networks (P-GNNs), a
new class of GNNs for computing position-aware node embeddings. P-GNN first
samples sets of anchor nodes, computes the distance of a given target node to
each anchor-set,and then learns a non-linear distance-weighted aggregation
scheme over the anchor-sets. This way P-GNNs can capture positions/locations of
nodes with respect to the anchor nodes. P-GNNs have several advantages: they
are inductive, scalable,and can incorporate node feature information. We apply
P-GNNs to multiple prediction tasks including link prediction and community
detection. We show that P-GNNs consistently outperform state of the art GNNs,
with up to 66% improvement in terms of the ROC AUC score.

positive:
The expressive power of message passing neural networks (MPNNs) is known to
match the expressive power of the 1-dimensional Weisfeiler-Leman graph (1-WL)
isomorphism test. To boost the expressive power of MPNNs, a number of graph
neural network architectures have recently been proposed based on
higher-dimensional Weisfeiler-Leman tests. In this paper we consider the
two-dimensional (2-WL) test and introduce a new type of MPNNs, referred to as
$\ell$-walk MPNNs, which aggregate features along walks of length $\ell$
between vertices. We show that $2$-walk MPNNs match 2-WL in expressive power.
More generally, $\ell$-walk MPNNs, for any $\ell\geq 2$, are shown to match the
expressive power of the recently introduced $\ell$-walk refinement procedure
(W[$\ell$]). Based on a correspondence between 2-WL and W[$\ell$], we observe
that $\ell$-walk MPNNs and $2$-walk MPNNs have the same expressive power, i.e.,
they can distinguish the same pairs of graphs, but $\ell$-walk MPNNs can
possibly distinguish pairs of graphs faster than $2$-walk MPNNs. When it comes
to concrete learnable graph neural network (GNN) formalisms that match 2-WL or
W[$\ell$] in expressive power, we consider second-order graph neural networks
that allow for non-linear layers. In particular, to match W[$\ell$] in
expressive power, we allow $\ell-1$ matrix multiplications in each layer. We
propose different versions of second-order GNNs depending on the type of
features (i.e., coming from a countable set, or coming from an uncountable set)
as this affects the number of dimensions needed to represent the features. Our
results indicate that increasing non-linearity in layers by means of allowing
multiple matrix multiplications does not increase expressive power. At the very
best, it results in a faster distinction of input graphs.

positive:
Graph Neural Networks (GNNs) bring the power of deep representation learning
to graph and relational data and achieve state-of-the-art performance in many
applications. GNNs compute node representations by taking into account the
topology of the node's ego-network and the features of the ego-network's nodes.
When the nodes do not have high-quality features, GNNs learn an embedding layer
to compute node embeddings and use them as input features. However, the size of
the embedding layer is linear to the product of the number of nodes in the
graph and the dimensionality of the embedding and does not scale to big data
and graphs with hundreds of millions of nodes. To reduce the memory associated
with this embedding layer, hashing-based approaches, commonly used in
applications like NLP and recommender systems, can potentially be used.
However, a direct application of these ideas fails to exploit the fact that in
many real-world graphs, nodes that are topologically close will tend to be
related to each other (homophily) and as such their representations will be
similar.
  In this work, we present approaches that take advantage of the nodes'
position in the graph to dramatically reduce the memory required, with minimal
if any degradation in the quality of the resulting GNN model. Our approaches
decompose a node's embedding into two components: a position-specific component
and a node-specific component. The position-specific component models homophily
and the node-specific component models the node-to-node variation. Extensive
experiments using different datasets and GNN models show that our methods are
able to reduce the memory requirements by 88% to 97% while achieving, in nearly
all cases, better classification accuracy than other competing approaches,
including the full embeddings.

positive:
Many tasks that rely on representations of nodes in graphs would benefit if
those representations were faithful to distances between nodes in the graph.
Geometric techniques to extract such representations have poor scaling over
large graph size, and recent advances in Graph Neural Network (GNN) algorithms
have limited ability to reflect graph distance information beyond the first
degree neighborhood. To enable this highly desired capability, we propose a
technique to learn Isometric Graph Neural Networks (IGNN), which requires
changing the input representation space and loss function to enable any GNN
algorithm to generate representations that reflect distances between nodes. We
experiment with the isometric technique on several GNN architectures for
modeling multiple prediction tasks on multiple datasets. In addition to an
improvement in AUC-ROC as high as $43\%$ in these experiments, we observe a
consistent and substantial improvement as high as 400% in Kendall's Tau (KT), a
measure that directly reflects distance information, demonstrating that the
learned embeddings do account for graph distances.

positive:
Message-passing neural networks (MPNNs) are the leading architecture for deep
learning on graph-structured data, in large part due to their simplicity and
scalability. Unfortunately, it was shown that these architectures are limited
in their expressive power. This paper proposes a novel framework called
Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. Our
main observation is that while two graphs may not be distinguishable by an
MPNN, they often contain distinguishable subgraphs. Thus, we propose to
represent each graph as a set of subgraphs derived by some predefined policy,
and to process it using a suitable equivariant architecture. We develop novel
variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph
isomorphism, and prove lower bounds on the expressiveness of ESAN in terms of
these new WL variants. We further prove that our approach increases the
expressive power of both MPNNs and more expressive architectures. Moreover, we
provide theoretical results that describe how design choices such as the
subgraph selection policy and equivariant neural architecture affect our
architecture's expressive power. To deal with the increased computational cost,
we propose a subgraph sampling scheme, which can be viewed as a stochastic
version of our framework. A comprehensive set of experiments on real and
synthetic datasets demonstrates that our framework improves the expressive
power and overall performance of popular GNN architectures.

positive:
Graph Neural Network (GNN) aggregates the neighborhood of each node into the
node embedding and shows its powerful capability for graph representation
learning. However, most existing GNN variants aggregate the neighborhood
information in a fixed non-injective fashion, which may map different graphs or
nodes to the same embedding, reducing the model expressiveness. We present a
theoretical framework to design a continuous injective set function for
neighborhood aggregation in GNN. Using the framework, we propose expressive GNN
that aggregates the neighborhood of each node with a continuous injective set
function, so that a GNN layer maps similar nodes with similar neighborhoods to
similar embeddings, different nodes to different embeddings and the equivalent
nodes or isomorphic graphs to the same embeddings. Moreover, the proposed
expressive GNN can naturally learn expressive representations for graphs with
continuous node attributes. We validate the proposed expressive GNN (ExpGNN)
for graph classification on multiple benchmark datasets including simple graphs
and attributed graphs. The experimental results demonstrate that our model
achieves state-of-the-art performances on most of the benchmarks.

positive:
Numerous works have proven that existing neighbor-averaging Graph Neural
Networks cannot efficiently catch structure features, and many works show that
injecting structure, distance, position or spatial features can significantly
improve performance of GNNs, however, injecting overall structure and distance
into GNNs is an intuitive but remaining untouched idea. In this work, we shed
light on the direction. We first extracting hop-wise structure information and
compute distance distributional information, gathering with node's intrinsic
features, embedding them into same vector space and then adding them up. The
derived embedding vectors are then fed into GATs(like GAT, AGDN) and then
Correct and Smooth, experiments show that the DHSEGATs achieve competitive
result. The code is available at https://github.com/hzg0601/DHSEGATs.

positive:
Graph neural networks (GNNs) have emerged recently as a powerful architecture
for learning node and graph representations. Standard GNNs have the same
expressive power as the Weisfeiler-Leman test of graph isomorphism in terms of
distinguishing non-isomorphic graphs. However, it was recently shown that this
test cannot identify fundamental graph properties such as connectivity and
triangle freeness. We show that GNNs also suffer from the same limitation. To
address this limitation, we propose a more expressive architecture, k-hop GNNs,
which updates a node's representation by aggregating information not only from
its direct neighbors, but from its k-hop neighborhood. We show that the
proposed architecture can identify fundamental graph properties. We evaluate
the proposed architecture on standard node classification and graph
classification datasets. Our experimental evaluation confirms our theoretical
findings since the proposed model achieves performance better or comparable to
standard GNNs and to state-of-the-art algorithms.

positive:
We present our ongoing work on understanding the limitations of graph
convolutional networks (GCNs) as well as our work on generalizations of graph
convolutions for representing more complex node attribute dependencies. Based
on an analysis of GCNs with the help of the corresponding computation graphs,
we propose a generalization of existing GCNs where the aggregation operations
are (a) determined by structural properties of the local neighborhood graphs
and (b) not restricted to weighted averages. We show that the proposed approach
is strictly more expressive while requiring only a modest increase in the
number of parameters and computations. We also show that the proposed
generalization is identical to standard convolutional layers when applied to
regular grid graphs.

positive:
The Transformer architecture has become a dominant choice in many domains,
such as natural language processing and computer vision. Yet, it has not
achieved competitive performance on popular leaderboards of graph-level
prediction compared to mainstream GNN variants. Therefore, it remains a mystery
how Transformers could perform well for graph representation learning. In this
paper, we solve this mystery by presenting Graphormer, which is built upon the
standard Transformer architecture, and could attain excellent results on a
broad range of graph representation learning tasks, especially on the recent
OGB Large-Scale Challenge. Our key insight to utilizing Transformer in the
graph is the necessity of effectively encoding the structural information of a
graph into the model. To this end, we propose several simple yet effective
structural encoding methods to help Graphormer better model graph-structured
data. Besides, we mathematically characterize the expressive power of
Graphormer and exhibit that with our ways of encoding the structural
information of graphs, many popular GNN variants could be covered as the
special cases of Graphormer.

positive:
Graph Neural Networks (GNNs) are versatile, powerful machine learning methods
that enable graph structure and feature representation learning, and have
applications across many domains. For applications critically requiring
interpretation, attention-based GNNs have been leveraged. However, these
approaches either rely on specific model architectures or lack a joint
consideration of graph structure and node features in their interpretation.
Here we present a model-agnostic framework for interpreting important graph
structure and node features, Graph neural networks Including SparSe
inTerpretability (GISST). With any GNN model, GISST combines an attention
mechanism and sparsity regularization to yield an important subgraph and node
feature subset related to any graph-based task. Through a single self-attention
layer, a GISST model learns an importance probability for each node feature and
edge in the input graph. By including these importance probabilities in the
model loss function, the probabilities are optimized end-to-end and tied to the
task-specific performance. Furthermore, GISST sparsifies these importance
probabilities with entropy and L1 regularization to reduce noise in the input
graph topology and node features. Our GISST models achieve superior node
feature and edge explanation precision in synthetic datasets, as compared to
alternative interpretation approaches. Moreover, our GISST models are able to
identify important graph structure in real-world datasets. We demonstrate in
theory that edge feature importance and multiple edge types can be considered
by incorporating them into the GISST edge probability computation. By jointly
accounting for topology, node features, and edge features, GISST inherently
provides simple and relevant interpretations for any GNN models and tasks.

positive:
Graph Neural Networks (GNNs) have been shown to be effective models for
different predictive tasks on graph-structured data. Recent work on their
expressive power has focused on isomorphism tasks and countable feature spaces.
We extend this theoretical framework to include continuous features - which
occur regularly in real-world input domains and within the hidden layers of
GNNs - and we demonstrate the requirement for multiple aggregation functions in
this context. Accordingly, we propose Principal Neighbourhood Aggregation
(PNA), a novel architecture combining multiple aggregators with degree-scalers
(which generalize the sum aggregator). Finally, we compare the capacity of
different models to capture and exploit the graph structure via a novel
benchmark containing multiple tasks taken from classical graph theory,
alongside existing benchmarks from real-world domains, all of which demonstrate
the strength of our model. With this work, we hope to steer some of the GNN
research towards new aggregation methods which we believe are essential in the
search for powerful and robust models.

positive:
The spatial convolution layer which is widely used in the Graph Neural
Networks (GNNs) aggregates the feature vector of each node with the feature
vectors of its neighboring nodes. The GNN is not aware of the locations of the
nodes in the global structure of the graph and when the local structures
corresponding to different nodes are similar to each other, the convolution
layer maps all those nodes to similar or same feature vectors in the continuous
feature space. Therefore, the GNN cannot distinguish two graphs if their
difference is not in their local structures. In addition, when the nodes are
not labeled/attributed the convolution layers can fail to distinguish even
different local structures. In this paper, we propose an effective solution to
address this problem of the GNNs. The proposed approach leverages a spatial
representation of the graph which makes the neural network aware of the
differences between the nodes and also their locations in the graph. The
spatial representation which is equivalent to a point-cloud representation of
the graph is obtained by a graph embedding method. Using the proposed approach,
the local feature extractor of the GNN distinguishes similar local structures
in different locations of the graph and the GNN infers the topological
structure of the graph from the spatial distribution of the locally extracted
feature vectors. Moreover, the spatial representation is utilized to simplify
the graph down-sampling problem. A new graph pooling method is proposed and it
is shown that the proposed pooling method achieves competitive or better
results in comparison with the state-of-the-art methods.

positive:
Graphs can model complicated interactions between entities, which naturally
emerge in many important applications. These applications can often be cast
into standard graph learning tasks, in which a crucial step is to learn
low-dimensional graph representations. Graph neural networks (GNNs) are
currently the most popular model in graph embedding approaches. However,
standard GNNs in the neighborhood aggregation paradigm suffer from limited
discriminative power in distinguishing \emph{high-order} graph structures as
opposed to \emph{low-order} structures. To capture high-order structures,
researchers have resorted to motifs and developed motif-based GNNs. However,
existing motif-based GNNs still often suffer from less discriminative power on
high-order structures. To overcome the above limitations, we propose Motif
Graph Neural Network (MGNN), a novel framework to better capture high-order
structures, hinging on our proposed motif redundancy minimization operator and
injective motif combination. First, MGNN produces a set of node representations
w.r.t. each motif. The next phase is our proposed redundancy minimization among
motifs which compares the motifs with each other and distills the features
unique to each motif. Finally, MGNN performs the updating of node
representations by combining multiple representations from different motifs. In
particular, to enhance the discriminative power, MGNN utilizes an injective
function to combine the representations w.r.t. different motifs. We further
show that our proposed architecture increases the expressive power of GNNs with
a theoretical analysis. We demonstrate that MGNN outperforms state-of-the-art
methods on seven public benchmarks on both node classification and graph
classification tasks.

positive:
Graph Neural Networks (GNNs) rely on the graph structure to define an
aggregation strategy where each node updates its representation by combining
information from its neighbours. A known limitation of GNNs is that, as the
number of layers increases, information gets smoothed and squashed and node
embeddings become indistinguishable, negatively affecting performance.
Therefore, practical GNN models employ few layers and only leverage the graph
structure in terms of limited, small neighbourhoods around each node.
Inevitably, practical GNNs do not capture information depending on the global
structure of the graph. While there have been several works studying the
limitations and expressivity of GNNs, the question of whether practical
applications on graph structured data require global structural knowledge or
not, remains unanswered. In this work, we empirically address this question by
giving access to global information to several GNN models, and observing the
impact it has on downstream performance. Our results show that global
information can in fact provide significant benefits for common graph-related
tasks. We further identify a novel regularization strategy that leads to an
average accuracy improvement of more than 5% on all considered tasks.

positive:
Message passing has evolved as an effective tool for designing Graph Neural
Networks (GNNs). However, most existing methods for message passing simply sum
or average all the neighboring features to update node representations. They
are restricted by two problems, i.e., (i) lack of interpretability to identify
node features significant to the prediction of GNNs, and (ii) feature
over-mixing that leads to the over-smoothing issue in capturing long-range
dependencies and inability to handle graphs under heterophily or low homophily.
In this paper, we propose a Node-level Capsule Graph Neural Network (NCGNN) to
address these problems with an improved message passing scheme. Specifically,
NCGNN represents nodes as groups of node-level capsules, in which each capsule
extracts distinctive features of its corresponding node. For each node-level
capsule, a novel dynamic routing procedure is developed to adaptively select
appropriate capsules for aggregation from a subgraph identified by the designed
graph filter. NCGNN aggregates only the advantageous capsules and restrains
irrelevant messages to avoid over-mixing features of interacting nodes.
Therefore, it can relieve the over-smoothing issue and learn effective node
representations over graphs with homophily or heterophily. Furthermore, our
proposed message passing scheme is inherently interpretable and exempt from
complex post-hoc explanations, as the graph filter and the dynamic routing
procedure identify a subset of node features that are most significant to the
model prediction from the extracted subgraph. Extensive experiments on
synthetic as well as real-world graphs demonstrate that NCGNN can well address
the over-smoothing issue and produce better node representations for
semisupervised node classification. It outperforms the state of the arts under
both homophily and heterophily.

positive:
Distinguishing the automorphic equivalence of nodes in a graph plays an
essential role in many scientific domains, e.g., computational biologist and
social network analysis. However, existing graph neural networks (GNNs) fail to
capture such an important property. To make GNN aware of automorphic
equivalence, we first introduce a localized variant of this concept --
ego-centered automorphic equivalence (Ego-AE). Then, we design a novel variant
of GNN, i.e., GRAPE, that uses learnable AE-aware aggregators to explicitly
differentiate the Ego-AE of each node's neighbors with the aids of various
subgraph templates. While the design of subgraph templates can be hard, we
further propose a genetic algorithm to automatically search them from graph
data. Moreover, we theoretically prove that GRAPE is expressive in terms of
generating distinct representations for nodes with different Ego-AE features,
which fills in a fundamental gap of existing GNN variants. Finally, we
empirically validate our model on eight real-world graph data, including social
network, e-commerce co-purchase network, and citation network, and show that it
consistently outperforms existing GNNs. The source code is public available at
https://github.com/tsinghua-fib-lab/GRAPE.

positive:
Message Passing Neural Networks (MPNNs) are a common type of Graph Neural
Network (GNN), in which each node's representation is computed recursively by
aggregating representations (messages) from its immediate neighbors akin to a
star-shaped pattern. MPNNs are appealing for being efficient and scalable,
how-ever their expressiveness is upper-bounded by the 1st-order
Weisfeiler-Lehman isomorphism test (1-WL). In response, prior works propose
highly expressive models at the cost of scalability and sometimes
generalization performance. Our work stands between these two regimes: we
introduce a general framework to uplift any MPNN to be more expressive, with
limited scalability overhead and greatly improved practical performance. We
achieve this by extending local aggregation in MPNNs from star patterns to
general subgraph patterns (e.g.,k-egonets):in our framework, each node
representation is computed as the encoding of a surrounding induced subgraph
rather than encoding of immediate neighbors only (i.e. a star). We choose the
subgraph encoder to be a GNN (mainly MPNNs, considering scalability) to design
a general framework that serves as a wrapper to up-lift any GNN. We call our
proposed method GNN-AK(GNN As Kernel), as the framework resembles a
convolutional neural network by replacing the kernel with GNNs. Theoretically,
we show that our framework is strictly more powerful than 1&2-WL, and is not
less powerful than 3-WL. We also design subgraph sampling strategies which
greatly reduce memory footprint and improve speed while maintaining
performance. Our method sets new state-of-the-art performance by large margins
for several well-known graph ML tasks; specifically, 0.08 MAE on ZINC,74.79%
and 86.887% accuracy on CIFAR10 and PATTERN respectively.

positive:
We propose a generalization of transformer neural network architecture for
arbitrary graphs. The original transformer was designed for Natural Language
Processing (NLP), which operates on fully connected graphs representing all
connections between the words in a sequence. Such architecture does not
leverage the graph connectivity inductive bias, and can perform poorly when the
graph topology is important and has not been encoded into the node features. We
introduce a graph transformer with four new properties compared to the standard
model. First, the attention mechanism is a function of the neighborhood
connectivity for each node in the graph. Second, the positional encoding is
represented by the Laplacian eigenvectors, which naturally generalize the
sinusoidal positional encodings often used in NLP. Third, the layer
normalization is replaced by a batch normalization layer, which provides faster
training and better generalization performance. Finally, the architecture is
extended to edge feature representation, which can be critical to tasks s.a.
chemistry (bond type) or link prediction (entity relationship in knowledge
graphs). Numerical experiments on a graph benchmark demonstrate the performance
of the proposed graph transformer architecture. This work closes the gap
between the original transformer, which was designed for the limited case of
line graphs, and graph neural networks, that can work with arbitrary graphs. As
our architecture is simple and generic, we believe it can be used as a black
box for future applications that wish to consider transformer and graphs.

positive:
It is not until recently that graph neural networks (GNNs) are adopted to
perform graph representation learning, among which, those based on the
aggregation of features within the neighborhood of a node achieved great
success. However, despite such achievements, GNNs illustrate defects in
identifying some common structural patterns which, unfortunately, play
significant roles in various network phenomena. In this paper, we propose
GraLSP, a GNN framework which explicitly incorporates local structural patterns
into the neighborhood aggregation through random anonymous walks. Specifically,
we capture local graph structures via random anonymous walks, powerful and
flexible tools that represent structural patterns. The walks are then fed into
the feature aggregation, where we design various mechanisms to address the
impact of structural features, including adaptive receptive radius, attention
and amplification. In addition, we design objectives that capture similarities
between structures and are optimized jointly with node proximity objectives.
With the adequate leverage of structural patterns, our model is able to
outperform competitive counterparts in various prediction tasks in multiple
datasets.

positive:
Graph neural networks (GNNs) have achieved great success in many graph-based
tasks. Much work is dedicated to empowering GNNs with the adaptive locality
ability, which enables measuring the importance of neighboring nodes to the
target node by a node-specific mechanism. However, the current node-specific
mechanisms are deficient in distinguishing the importance of nodes in the
topology structure. We believe that the structural importance of neighboring
nodes is closely related to their importance in aggregation. In this paper, we
introduce discrete graph curvature (the Ricci curvature) to quantify the
strength of structural connection of pairwise nodes. And we propose Curvature
Graph Neural Network (CGNN), which effectively improves the adaptive locality
ability of GNNs by leveraging the structural property of graph curvature. To
improve the adaptability of curvature to various datasets, we explicitly
transform curvature into the weights of neighboring nodes by the necessary
Negative Curvature Processing Module and Curvature Normalization Module. Then,
we conduct numerous experiments on various synthetic datasets and real-world
datasets. The experimental results on synthetic datasets show that CGNN
effectively exploits the topology structure information, and the performance is
improved significantly. CGNN outperforms the baselines on 5 dense node
classification benchmark datasets. This study deepens the understanding of how
to utilize advanced topology information and assign the importance of
neighboring nodes from the perspective of graph curvature and encourages us to
bridge the gap between graph theory and neural networks.

positive:
Machine learning on graph-structured data has attracted high research
interest due to the emergence of Graph Neural Networks (GNNs). Most of the
proposed GNNs are based on the node homophily, i.e neighboring nodes share
similar characteristics. However, in many complex networks, nodes that lie to
distant parts of the graph share structurally equivalent characteristics and
exhibit similar roles (e.g chemical properties of distant atoms in a molecule,
type of social network users). A growing literature proposed representations
that identify structurally equivalent nodes. However, most of the existing
methods require high time and space complexity. In this paper, we propose
VNEstruct, a simple approach, based on entropy measures of the neighborhood's
topology, for generating low-dimensional structural representations, that is
time-efficient and robust to graph perturbations. Empirically, we observe that
VNEstruct exhibits robustness on structural role identification tasks.
Moreover, VNEstruct can achieve state-of-the-art performance on graph
classification, without incorporating the graph structure information in the
optimization, in contrast to GNN competitors.

positive:
With the great success of deep learning in various domains, graph neural
networks (GNNs) also become a dominant approach to graph classification. By the
help of a global readout operation that simply aggregates all node (or
node-cluster) representations, existing GNN classifiers obtain a graph-level
representation of an input graph and predict its class label using the
representation. However, such global aggregation does not consider the
structural information of each node, which results in information loss on the
global structure. Particularly, it limits the discrimination power by enforcing
the same weight parameters of the classifier for all the node representations;
in practice, each of them contributes to target classes differently depending
on its structural semantic. In this work, we propose structural semantic
readout (SSRead) to summarize the node representations at the position-level,
which allows to model the position-specific weight parameters for
classification as well as to effectively capture the graph semantic relevant to
the global structure. Given an input graph, SSRead aims to identify
structurally-meaningful positions by using the semantic alignment between its
nodes and structural prototypes, which encode the prototypical features of each
position. The structural prototypes are optimized to minimize the alignment
cost for all training graphs, while the other GNN parameters are trained to
predict the class labels. Our experimental results demonstrate that SSRead
significantly improves the classification performance and interpretability of
GNN classifiers while being compatible with a variety of aggregation functions,
GNN architectures, and learning frameworks.

positive:
While Graph Neural Networks (GNNs) have achieved remarkable results in a
variety of applications, recent studies exposed important shortcomings in their
ability to capture the structure of the underlying graph. It has been shown
that the expressive power of standard GNNs is bounded by the Weisfeiler-Leman
(WL) graph isomorphism test, from which they inherit proven limitations such as
the inability to detect and count graph substructures. On the other hand, there
is significant empirical evidence, e.g. in network science and bioinformatics,
that substructures are often intimately related to downstream tasks. To this
end, we propose "Graph Substructure Networks" (GSN), a topologically-aware
message passing scheme based on substructure encoding. We theoretically analyse
the expressive power of our architecture, showing that it is strictly more
expressive than the WL test, and provide sufficient conditions for
universality. Importantly, we do not attempt to adhere to the WL hierarchy;
this allows us to retain multiple attractive properties of standard GNNs such
as locality and linear network complexity, while being able to disambiguate
even hard instances of graph isomorphism. We perform an extensive experimental
evaluation on graph classification and regression tasks and obtain
state-of-the-art results in diverse real-world settings including molecular
graphs and social networks. The code is publicly available at
https://github.com/gbouritsas/graph-substructure-networks.

positive:
The ability to detect and count certain substructures in graphs is important
for solving many tasks on graph-structured data, especially in the contexts of
computational chemistry and biology as well as social network analysis.
Inspired by this, we propose to study the expressive power of graph neural
networks (GNNs) via their ability to count attributed graph substructures,
extending recent works that examine their power in graph isomorphism testing
and function approximation. We distinguish between two types of substructure
counting: induced-subgraph-count and subgraph-count, and establish both
positive and negative answers for popular GNN architectures. Specifically, we
prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL)
and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count
of substructures consisting of 3 or more nodes, while they can perform
subgraph-count of star-shaped substructures. As an intermediary step, we prove
that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs,
partly answering an open problem raised in Maron et al. (2019). We also prove
positive results for k-WL and k-IGNs as well as negative results for k-WL with
a finite number of iterations. We then conduct experiments that support the
theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure
counting and inspired by Murphy et al. (2019), we propose the Local Relational
Pooling model and demonstrate that it is not only effective for substructure
counting but also able to achieve competitive performance on molecular
prediction tasks.

positive:
Graph Neural Networks (GNNs) have shown advantages in various graph-based
applications. Most existing GNNs assume strong homophily of graph structure and
apply permutation-invariant local aggregation of neighbors to learn a
representation for each node. However, they fail to generalize to heterophilic
graphs, where most neighboring nodes have different labels or features, and the
relevant nodes are distant. Few recent studies attempt to address this problem
by combining multiple hops of hidden representations of central nodes (i.e.,
multi-hop-based approaches) or sorting the neighboring nodes based on attention
scores (i.e., ranking-based approaches). As a result, these approaches have
some apparent limitations. On the one hand, multi-hop-based approaches do not
explicitly distinguish relevant nodes from a large number of multi-hop
neighborhoods, leading to a severe over-smoothing problem. On the other hand,
ranking-based models do not joint-optimize node ranking with end tasks and
result in sub-optimal solutions. In this work, we present Graph Pointer Neural
Networks (GPNN) to tackle the challenges mentioned above. We leverage a pointer
network to select the most relevant nodes from a large amount of multi-hop
neighborhoods, which constructs an ordered sequence according to the
relationship with the central node. 1D convolution is then applied to extract
high-level features from the node sequence. The pointer-network-based ranker in
GPNN is joint-optimized with other parts in an end-to-end manner. Extensive
experiments are conducted on six public node classification datasets with
heterophilic graphs. The results show that GPNN significantly improves the
classification performance of state-of-the-art methods. In addition, analyses
also reveal the privilege of the proposed GPNN in filtering out irrelevant
neighbors and reducing over-smoothing.

positive:
Graph Neural Networks (GNNs) have achieved tremendous success in various
real-world applications due to their strong ability in graph representation
learning. GNNs explore the graph structure and node features by aggregating and
transforming information within node neighborhoods. However, through
theoretical and empirical analysis, we reveal that the aggregation process of
GNNs tends to destroy node similarity in the original feature space. There are
many scenarios where node similarity plays a crucial role. Thus, it has
motivated the proposed framework SimP-GCN that can effectively and efficiently
preserve node similarity while exploiting graph structure. Specifically, to
balance information from graph structure and node features, we propose a
feature similarity preserving aggregation which adaptively integrates graph
structure and node features. Furthermore, we employ self-supervised learning to
explicitly capture the complex feature similarity and dissimilarity relations
between nodes. We validate the effectiveness of SimP-GCN on seven benchmark
datasets including three assortative and four disassorative graphs. The results
demonstrate that SimP-GCN outperforms representative baselines. Further probe
shows various advantages of the proposed framework. The implementation of
SimP-GCN is available at \url{https://github.com/ChandlerBang/SimP-GCN}.

positive:
Graph neural networks (GNNs) emerge as a powerful family of representation
learning models on graphs. To derive node representations, they utilize a
global model that recursively aggregates information from the neighboring
nodes. However, different nodes reside at different parts of the graph in
different local contexts, making their distributions vary across the graph.
Ideally, how a node receives its neighborhood information should be a function
of its local context, to diverge from the global GNN model shared by all nodes.
To utilize node locality without overfitting, we propose a node-wise
localization of GNNs by accounting for both global and local aspects of the
graph. Globally, all nodes on the graph depend on an underlying global GNN to
encode the general patterns across the graph; locally, each node is localized
into a unique model as a function of the global model and its local context.
Finally, we conduct extensive experiments on four benchmark graphs, and
consistently obtain promising performance surpassing the state-of-the-art GNNs.

positive:
Graph data widely exist in many high-impact applications. Inspired by the
success of deep learning in grid-structured data, graph neural network models
have been proposed to learn powerful node-level or graph-level representation.
However, most of the existing graph neural networks suffer from the following
limitations: (1) there is limited analysis regarding the graph convolution
properties, such as seed-oriented, degree-aware and order-free; (2) the node's
degree-specific graph structure is not explicitly expressed in graph
convolution for distinguishing structure-aware node neighborhoods; (3) the
theoretical explanation regarding the graph-level pooling schemes is unclear.
  To address these problems, we propose a generic degree-specific graph neural
network named DEMO-Net motivated by Weisfeiler-Lehman graph isomorphism test
that recursively identifies 1-hop neighborhood structures. In order to
explicitly capture the graph topology integrated with node attributes, we argue
that graph convolution should have three properties: seed-oriented,
degree-aware, order-free. To this end, we propose multi-task graph convolution
where each task represents node representation learning for nodes with a
specific degree value, thus leading to preserving the degree-specific graph
structure. In particular, we design two multi-task learning methods:
degree-specific weight and hashing functions for graph convolution. In
addition, we propose a novel graph-level pooling/readout scheme for learning
graph representation provably lying in a degree-specific Hilbert kernel space.
The experimental results on several node and graph classification benchmark
data sets demonstrate the effectiveness and efficiency of our proposed DEMO-Net
over state-of-the-art graph neural network models.

positive:
Graph Neural Networks (GNNs) are emerging machine learning models on graphs.
Although sufficiently deep GNNs are shown theoretically capable of fully
preserving graph structures, most existing GNN models in practice are shallow
and essentially feature-centric. We show empirically and analytically that the
existing shallow GNNs cannot preserve graph structures well. To overcome this
fundamental challenge, we propose Eigen-GNN, a simple yet effective and general
plug-in module to boost GNNs ability in preserving graph structures.
Specifically, we integrate the eigenspace of graph structures with GNNs by
treating GNNs as a type of dimensionality reduction and expanding the initial
dimensionality reduction bases. Without needing to increase depths, Eigen-GNN
possesses more flexibilities in handling both feature-driven and
structure-driven tasks since the initial bases contain both node features and
graph structures. We present extensive experimental results to demonstrate the
effectiveness of Eigen-GNN for tasks including node classification, link
prediction, and graph isomorphism tests.

positive:
Graph data are pervasive in many real-world applications. Recently,
increasing attention has been paid on graph neural networks (GNNs), which aim
to model the local graph structures and capture the hierarchical patterns by
aggregating the information from neighbors with stackable network modules.
Motivated by the observation that different nodes often require different
iterations of aggregation to fully capture the structural information, in this
paper, we propose to explicitly sample diverse iterations of aggregation for
different nodes to boost the performance of GNNs. It is a challenging task to
develop an effective aggregation strategy for each node, given complex graphs
and sparse features. Moreover, it is not straightforward to derive an efficient
algorithm since we need to feed the sampled nodes into different number of
network layers. To address the above challenges, we propose Policy-GNN, a
meta-policy framework that models the sampling procedure and message passing of
GNNs into a combined learning process. Specifically, Policy-GNN uses a
meta-policy to adaptively determine the number of aggregations for each node.
The meta-policy is trained with deep reinforcement learning (RL) by exploiting
the feedback from the model. We further introduce parameter sharing and a
buffer mechanism to boost the training efficiency. Experimental results on
three real-world benchmark datasets suggest that Policy-GNN significantly
outperforms the state-of-the-art alternatives, showing the promise in
aggregation optimization for GNNs.

positive:
Various recent proposals increase the distinguishing power of Graph Neural
Networks GNNs by propagating features between $k$-tuples of vertices. The
distinguishing power of these "higher-order'' GNNs is known to be bounded by
the $k$-dimensional Weisfeiler-Leman (WL) test, yet their $\mathcal O(n^k)$
memory requirements limit their applicability. Other proposals infuse GNNs with
local higher-order graph structural information from the start, hereby
inheriting the desirable $\mathcal O(n)$ memory requirement from GNNs at the
cost of a one-time, possibly non-linear, preprocessing step. We propose local
graph parameter enabled GNNs as a framework for studying the latter kind of
approaches and precisely characterize their distinguishing power, in terms of a
variant of the WL test, and in terms of the graph structural properties that
they can take into account. Local graph parameters can be added to any GNN
architecture, and are cheap to compute. In terms of expressive power, our
proposal lies in the middle of GNNs and their higher-order counterparts.
Further, we propose several techniques to aide in choosing the right local
graph parameters. Our results connect GNNs with deep results in finite model
theory and finite variable logics. Our experimental evaluation shows that
adding local graph parameters often has a positive effect for a variety of
GNNs, datasets and graph learning tasks.

positive:
Graph neural networks (GNNs) have achieved tremendous success on multiple
graph-based learning tasks by fusing network structure and node features.
Modern GNN models are built upon iterative aggregation of neighbor's/proximity
features by message passing. Its prediction performance has been shown to be
strongly bounded by assortative mixing in the graph, a key property wherein
nodes with similar attributes mix/connect with each other. We observe that real
world networks exhibit heterogeneous or diverse mixing patterns and the
conventional global measurement of assortativity, such as global assortativity
coefficient, may not be a representative statistic in quantifying this mixing.
We adopt a generalized concept, node-level assortativity, one that is based at
the node level to better represent the diverse patterns and accurately quantify
the learnability of GNNs. We find that the prediction performance of a wide
range of GNN models is highly correlated with the node level assortativity. To
break this limit, in this work, we focus on transforming the input graph into a
computation graph which contains both proximity and structural information as
distinct type of edges. The resulted multi-relational graph has an enhanced
level of assortativity and, more importantly, preserves rich information from
the original graph. We then propose to run GNNs on this computation graph and
show that adaptively choosing between structure and proximity leads to improved
performance under diverse mixing. Empirically, we show the benefits of adopting
our transformation framework for semi-supervised node classification task on a
variety of real world graph learning benchmarks.

positive:
Message passing Graph Neural Networks (GNNs) provide a powerful modeling
framework for relational data. However, the expressive power of existing GNNs
is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test,
which means GNNs that are not able to predict node clustering coefficients and
shortest path distances, and cannot differentiate between different d-regular
graphs. Here we develop a class of message passing GNNs, named Identity-aware
Graph Neural Networks (ID-GNNs), with greater expressive power than the 1-WL
test. ID-GNN offers a minimal but powerful solution to limitations of existing
GNNs. ID-GNN extends existing GNN architectures by inductively considering
nodes' identities during message passing. To embed a given node, ID-GNN first
extracts the ego network centered at the node, then conducts rounds of
heterogeneous message passing, where different sets of parameters are applied
to the center node than to other surrounding nodes in the ego network. We
further propose a simplified but faster version of ID-GNN that injects node
identity information as augmented node features. Altogether, both versions of
ID-GNN represent general extensions of message passing GNNs, where experiments
show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy
improvement on challenging node, edge, and graph property prediction tasks; 3%
accuracy improvement on node and graph classification benchmarks; and 15% ROC
AUC improvement on real-world link prediction tasks. Additionally, ID-GNNs
demonstrate improved or comparable performance over other task-specific graph
networks.

positive:
In recent years, graph neural networks (GNNs) have emerged as a powerful
neural architecture to learn vector representations of nodes and graphs in a
supervised, end-to-end fashion. Up to now, GNNs have only been evaluated
empirically -- showing promising results. The following work investigates GNNs
from a theoretical point of view and relates them to the $1$-dimensional
Weisfeiler-Leman graph isomorphism heuristic ($1$-WL). We show that GNNs have
the same expressiveness as the $1$-WL in terms of distinguishing non-isomorphic
(sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on
this, we propose a generalization of GNNs, so-called $k$-dimensional GNNs
($k$-GNNs), which can take higher-order graph structures at multiple scales
into account. These higher-order structures play an essential role in the
characterization of social networks and molecule graphs. Our experimental
evaluation confirms our theoretical findings as well as confirms that
higher-order information is useful in the task of graph classification and
regression.

positive:
In this paper, we propose a spatial graph convolution (GC) to classify
signals on a graph. Existing GC methods are limited to using the structural
information in the feature space. Additionally, the single step of GCs only
uses features on the one-hop neighboring nodes from the target node. In this
paper, we propose two methods to improve the performance of GCs: 1) Utilizing
structural information in the feature space, and 2) exploiting the multi-hop
information in one GC step. In the first method, we define three structural
features in the feature space: feature angle, feature distance, and relational
embedding. The second method aggregates the node-wise features of multi-hop
neighbors in a GC. Both methods can be simultaneously used. We also propose
graph neural networks (GNNs) integrating the proposed GC for classifying nodes
in 3D point clouds and citation networks. In experiments, the proposed GNNs
exhibited a higher classification accuracy than existing methods.

positive:
Graph Neural Networks (GNNs) are deep learning methods which provide the
current state of the art performance in node classification tasks. GNNs often
assume homophily -- neighboring nodes having similar features and labels--, and
therefore may not be at their full potential when dealing with non-homophilic
graphs. In this work, we focus on addressing this limitation and enable Graph
Attention Networks (GAT), a commonly used variant of GNNs, to explore the
structural information within each graph locality. Inspired by the positional
encoding in the Transformers, we propose a framework, termed Graph Attentional
Networks with Positional Embeddings (GAT-POS), to enhance GATs with positional
embeddings which capture structural and positional information of the nodes in
the graph. In this framework, the positional embeddings are learned by a model
predictive of the graph context, plugged into an enhanced GAT architecture,
which is able to leverage both the positional and content information of each
node. The model is trained jointly to optimize for the task of node
classification as well as the task of predicting graph context. Experimental
results show that GAT-POS reaches remarkable improvement compared to strong GNN
baselines and recent structural embedding enhanced GNNs on non-homophilic
graphs.

positive:
Inspired by the immense success of deep learning, graph neural networks
(GNNs) are widely used to learn powerful node representations and have
demonstrated promising performance on different graph learning tasks. However,
most real-world graphs often come with high-dimensional and sparse node
features, rendering the learned node representations from existing GNN
architectures less expressive. In this paper, we propose \textit{Feature
Interaction-aware Graph Neural Networks (FI-GNNs)}, a plug-and-play GNN
framework for learning node representations encoded with informative feature
interactions. Specifically, the proposed framework is able to highlight
informative feature interactions in a personalized manner and further learn
highly expressive node representations on feature-sparse graphs. Extensive
experiments on various datasets demonstrate the superior capability of FI-GNNs
for graph learning tasks.

positive:
Graph Neural Networks (GNNs) are an effective framework for representation
learning of graphs. GNNs follow a neighborhood aggregation scheme, where the
representation vector of a node is computed by recursively aggregating and
transforming representation vectors of its neighboring nodes. Many GNN variants
have been proposed and have achieved state-of-the-art results on both node and
graph classification tasks. However, despite GNNs revolutionizing graph
representation learning, there is limited understanding of their
representational properties and limitations. Here, we present a theoretical
framework for analyzing the expressive power of GNNs to capture different graph
structures. Our results characterize the discriminative power of popular GNN
variants, such as Graph Convolutional Networks and GraphSAGE, and show that
they cannot learn to distinguish certain simple graph structures. We then
develop a simple architecture that is provably the most expressive among the
class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism
test. We empirically validate our theoretical findings on a number of graph
classification benchmarks, and demonstrate that our model achieves
state-of-the-art performance.

positive:
Graph neural networks (GNNs) work well when the graph structure is provided.
However, this structure may not always be available in real-world applications.
One solution to this problem is to infer a task-specific latent structure and
then apply a GNN to the inferred graph. Unfortunately, the space of possible
graph structures grows super-exponentially with the number of nodes and so the
task-specific supervision may be insufficient for learning both the structure
and the GNN parameters. In this work, we propose the Simultaneous Learning of
Adjacency and GNN Parameters with Self-supervision, or SLAPS, a method that
provides more supervision for inferring a graph structure through
self-supervision. A comprehensive experimental study demonstrates that SLAPS
scales to large graphs with hundreds of thousands of nodes and outperforms
several models that have been proposed to learn a task-specific graph structure
on established benchmarks.

positive:
Graph Neural Networks (GNNs) have achieved remarkable performance on
graph-based tasks. The key idea for GNNs is to obtain informative
representation through aggregating information from local neighborhoods.
However, it remains an open question whether the neighborhood information is
adequately aggregated for learning representations of nodes with few neighbors.
To address this, we propose a simple and efficient data augmentation strategy,
local augmentation, to learn the distribution of the node features of the
neighbors conditioned on the central node's feature and enhance GNN's
expressive power with generated features. Local augmentation is a general
framework that can be applied to any GNN model in a plug-and-play manner. It
samples feature vectors associated with each node from the learned conditional
distribution as additional input for the backbone model at each training
iteration. Extensive experiments and analyses show that local augmentation
consistently yields performance improvement when applied to various GNN
architectures across a diverse set of benchmarks. For example, experiments show
that plugging in local augmentation to GCN and GAT improves by an average of
3.4\% and 1.6\% in terms of test accuracy on Cora, Citeseer, and Pubmed.
Besides, our experimental results on large graphs (OGB) show that our model
consistently improves performance over backbones. Code is available at
https://github.com/SongtaoLiu0823/LAGNN.

positive:
Graph neural networks (GNNs) have been widely used in various graph-related
problems such as node classification and graph classification, where superior
performance is mainly established when natural node features are available.
However, it is not well understood how GNNs work without natural node features,
especially regarding the various ways to construct artificial ones. In this
paper, we point out the two types of artificial node features, i.e., positional
and structural node features, and provide insights on why each of them is more
appropriate for certain tasks, i.e., positional node classification, structural
node classification, and graph classification. Extensive experimental results
on 10 benchmark datasets validate our insights, thus leading to a practical
guideline on the choices between different artificial node features for GNNs on
non-attributed graphs. The code is available at
https://github.com/zjzijielu/gnn-positional-structural-node-features.

positive:
Learning graph-structured data with graph neural networks (GNNs) has been
recently emerging as an important field because of its wide applicability in
bioinformatics, chemoinformatics, social network analysis and data mining.
Recent GNN algorithms are based on neural message passing, which enables GNNs
to integrate local structures and node features recursively. However, past GNN
algorithms based on 1-hop neighborhood neural message passing are exposed to a
risk of loss of information on local structures and relationships. In this
paper, we propose Neighborhood Edge AggregatoR (NEAR), a framework that
aggregates relations between the nodes in the neighborhood via edges. NEAR,
which can be orthogonally combined with Graph Isomorphism Network (GIN), gives
integrated information that describes which nodes in the neighborhood are
connected. Therefore, NEAR can reflect additional information of a local
structure of each node beyond the nodes themselves in 1-hop neighborhood.
Experimental results on multiple graph classification tasks show that our
algorithm makes a good improvement over other existing 1-hop based GNN-based
algorithms.

positive:
Graph neural networks (GNNs) achieve remarkable success in graph-based
semi-supervised node classification, leveraging the information from
neighboring nodes to improve the representation learning of target node. The
success of GNNs at node classification depends on the assumption that connected
nodes tend to have the same label. However, such an assumption does not always
work, limiting the performance of GNNs at node classification. In this paper,
we propose label-consistency based graph neural network(LC-GNN), leveraging
node pairs unconnected but with the same labels to enlarge the receptive field
of nodes in GNNs. Experiments on benchmark datasets demonstrate the proposed
LC-GNN outperforms traditional GNNs in graph-based semi-supervised node
classification.We further show the superiority of LC-GNN in sparse scenarios
with only a handful of labeled nodes.

positive:
We consider graph representation learning in a self-supervised manner. Graph
neural networks (GNNs) use neighborhood aggregation as a core component that
results in feature smoothing among nodes in proximity. While successful in
various prediction tasks, such a paradigm falls short of capturing nodes'
similarities over a long distance, which proves to be important for
high-quality learning. To tackle this problem, we strengthen the graph with two
additional graph views, in which nodes are directly linked to those with the
most similar features or local structures. Not restricted by connectivity in
the original graph, the generated views allow the model to enhance its
expressive power with new and complementary perspectives from which to look at
the relationship between nodes. Following a contrastive learning approach, we
propose a method that aims to maximize the agreement between representations
across generated views and the original graph. We also propose a channel-level
contrast approach that greatly reduces computation cost, compared to the
commonly used node level contrast, which requires computation cost quadratic in
the number of nodes. Extensive experiments on seven assortative graphs and four
disassortative graphs demonstrate the effectiveness of our approach.

positive:
We propose a Graph Neural Network with greater expressive power than commonly
used GNNs - not constrained to only differentiate between graphs that
Weisfeiler-Lehman test recognizes to be non-isomorphic. We use a graph
attention network with expanding attention window that aggregates information
from nodes exponentially far away. We also use partially random initial
embeddings, allowing differentiation between nodes that would otherwise look
the same. This could cause problem with a traditional dropout mechanism,
therefore we use a "head dropout", randomly ignoring some attention heads
rather than some dimensions of the embedding.

positive:
Network data can be conveniently modeled as a graph signal, where data values
are assigned to nodes of a graph that describes the underlying network
topology. Successful learning from network data is built upon methods that
effectively exploit this graph structure. In this work, we leverage graph
signal processing to characterize the representation space of graph neural
networks (GNNs). We discuss the role of graph convolutional filters in GNNs and
show that any architecture built with such filters has the fundamental
properties of permutation equivariance and stability to changes in the
topology. These two properties offer insight about the workings of GNNs and
help explain their scalability and transferability properties which, coupled
with their local and distributed nature, make GNNs powerful tools for learning
in physical networks. We also introduce GNN extensions using edge-varying and
autoregressive moving average graph filters and discuss their properties.
Finally, we study the use of GNNs in recommender systems and learning
decentralized controllers for robot swarms.

positive:
Graph neural networks (GNNs) have limited expressive power, failing to
represent many graph classes correctly. While more expressive graph
representation learning (GRL) alternatives can distinguish some of these
classes, they are significantly harder to implement, may not scale well, and
have not been shown to outperform well-tuned GNNs in real-world tasks. Thus,
devising simple, scalable, and expressive GRL architectures that also achieve
real-world improvements remains an open challenge. In this work, we show the
extent to which graph reconstruction -- reconstructing a graph from its
subgraphs -- can mitigate the theoretical and practical problems currently
faced by GRL architectures. First, we leverage graph reconstruction to build
two new classes of expressive graph representations. Secondly, we show how
graph reconstruction boosts the expressive power of any GNN architecture while
being a (provably) powerful inductive bias for invariances to vertex removals.
Empirically, we show how reconstruction can boost GNN's expressive power --
while maintaining its invariance to permutations of the vertices -- by solving
seven graph property tasks not solvable by the original GNN. Further, we
demonstrate how it boosts state-of-the-art GNN's performance across nine
real-world benchmark datasets.

positive:
Graph neural networks (GNNs) are powerful machine learning models for various
graph learning tasks. Recently, the limitations of the expressive power of
various GNN models have been revealed. For example, GNNs cannot distinguish
some non-isomorphic graphs and they cannot learn efficient graph algorithms. In
this paper, we demonstrate that GNNs become powerful just by adding a random
feature to each node. We prove that the random features enable GNNs to learn
almost optimal polynomial-time approximation algorithms for the minimum
dominating set problem and maximum matching problem in terms of approximation
ratios. The main advantage of our method is that it can be combined with
off-the-shelf GNN models with slight modifications. Through experiments, we
show that the addition of random features enables GNNs to solve various
problems that normal GNNs, including the graph convolutional networks (GCNs)
and graph isomorphism networks (GINs), cannot solve.

positive:
Graph Neural Networks (GNNs) have led to state-of-the-art performance on a
variety of machine learning tasks such as recommendation, node classification
and link prediction. Graph neural network models generate node embeddings by
merging nodes features with the aggregated neighboring nodes information. Most
existing GNN models exploit a single type of aggregator (e.g., mean-pooling) to
aggregate neighboring nodes information, and then add or concatenate the output
of aggregator to the current representation vector of the center node. However,
using only a single type of aggregator is difficult to capture the different
aspects of neighboring information and the simple addition or concatenation
update methods limit the expressive capability of GNNs. Not only that, existing
supervised or semi-supervised GNN models are trained based on the loss function
of the node label, which leads to the neglect of graph structure information.
In this paper, we propose a novel graph neural network architecture, Graph
Attention \& Interaction Network (GAIN), for inductive learning on graphs.
Unlike the previous GNN models that only utilize a single type of aggregation
method, we use multiple types of aggregators to gather neighboring information
in different aspects and integrate the outputs of these aggregators through the
aggregator-level attention mechanism. Furthermore, we design a graph
regularized loss to better capture the topological relationship of the nodes in
the graph. Additionally, we first present the concept of graph feature
interaction and propose a vector-wise explicit feature interaction mechanism to
update the node embeddings. We conduct comprehensive experiments on two
node-classification benchmarks and a real-world financial news dataset. The
experiments demonstrate our GAIN model outperforms current state-of-the-art
performances on all the tasks.

positive:
Graph neural networks (GNNs) have become the standard learning architectures
for graphs. GNNs have been applied to numerous domains ranging from quantum
chemistry, recommender systems to knowledge graphs and natural language
processing. A major issue with arbitrary graphs is the absence of canonical
positional information of nodes, which decreases the representation power of
GNNs to distinguish e.g. isomorphic nodes and other graph symmetries. An
approach to tackle this issue is to introduce Positional Encoding (PE) of
nodes, and inject it into the input layer, like in Transformers. Possible graph
PE are Laplacian eigenvectors. In this work, we propose to decouple structural
and positional representations to make easy for the network to learn these two
essential properties. We introduce a novel generic architecture which we call
LSPE (Learnable Structural and Positional Encodings). We investigate several
sparse and fully-connected (Transformer-like) GNNs, and observe a performance
increase for molecular datasets, from 1.79% up to 64.14% when considering
learnable PE for both GNN classes.

positive:
Graph neural networks (GNNs) have shown great power in learning on attributed
graphs. However, it is still a challenge for GNNs to utilize information
faraway from the source node. Moreover, general GNNs require graph attributes
as input, so they cannot be appled to plain graphs. In the paper, we propose
new models named G-GNNs (Global information for GNNs) to address the above
limitations. First, the global structure and attribute features for each node
are obtained via unsupervised pre-training, which preserve the global
information associated to the node. Then, using the global features and the raw
network attributes, we propose a parallel framework of GNNs to learn different
aspects from these features. The proposed learning methods can be applied to
both plain graphs and attributed graphs. Extensive experiments have shown that
G-GNNs can outperform other state-of-the-art models on three standard
evaluation graphs. Specially, our methods establish new benchmark records on
Cora (84.31\%) and Pubmed (80.95\%) when learning on attributed graphs.

positive:
This paper addresses the challenging problem of retrieval and matching of
graph structured objects, and makes two key contributions. First, we
demonstrate how Graph Neural Networks (GNN), which have emerged as an effective
model for various supervised prediction problems defined on structured data,
can be trained to produce embedding of graphs in vector spaces that enables
efficient similarity reasoning. Second, we propose a novel Graph Matching
Network model that, given a pair of graphs as input, computes a similarity
score between them by jointly reasoning on the pair through a new cross-graph
attention-based matching mechanism. We demonstrate the effectiveness of our
models on different domains including the challenging problem of
control-flow-graph based function similarity search that plays an important
role in the detection of vulnerabilities in software systems. The experimental
analysis demonstrates that our models are not only able to exploit structure in
the context of similarity learning but they can also outperform domain-specific
baseline systems that have been carefully hand-engineered for these problems.

positive:
Graph neural networks (GNNs) have drawn increasing attention in recent years
and achieved remarkable performance in many graph-based tasks, especially in
semi-supervised learning on graphs. However, most existing GNNs excessively
rely on topological structures and aggregate multi-hop neighborhood information
by simply stacking network layers, which may introduce superfluous noise
information, limit the expressive power of GNNs and lead to the over-smoothing
problem ultimately. In light of this, we propose a novel Dual-Perception Graph
Neural Network (DPGNN) to address these issues. In DPGNN, we utilize node
features to construct a feature graph, and perform node representations
learning based on the original topology graph and the constructed feature graph
simultaneously, which conduce to capture the structural neighborhood
information and the feature-related information. Furthermore, we design a
Multi-Hop Graph Generator (MHGG), which applies a node-to-hop attention
mechanism to aggregate node-specific multi-hop neighborhood information
adaptively. Finally, we apply self-ensembling to form a consistent prediction
for unlabeled node representations. Experimental results on five datasets with
different topological structures demonstrate that our proposed DPGNN
outperforms all the latest state-of-the-art models on all datasets, which
proves the superiority and versatility of our model. The source code of our
model is available at https://github.com.

positive:
Predicting interactions between structured entities lies at the core of
numerous tasks such as drug regimen and new material design. In recent years,
graph neural networks have become attractive. They represent structured
entities as graphs and then extract features from each individual graph using
graph convolution operations. However, these methods have some limitations: i)
their networks only extract features from a fix-sized subgraph structure (i.e.,
a fix-sized receptive field) of each node, and ignore features in substructures
of different sizes, and ii) features are extracted by considering each entity
independently, which may not effectively reflect the interaction between two
entities. To resolve these problems, we present MR-GNN, an end-to-end graph
neural network with the following features: i) it uses a multi-resolution based
architecture to extract node features from different neighborhoods of each
node, and, ii) it uses dual graph-state long short-term memory networks
(L-STMs) to summarize local features of each graph and extracts the interaction
features between pairwise graphs. Experiments conducted on real-world datasets
show that MR-GNN improves the prediction of state-of-the-art methods.

positive:
Graph neural networks (GNNs) have emerged as a powerful tool for graph
classification and representation learning. However, GNNs tend to suffer from
over-smoothing problems and are vulnerable to graph perturbations. To address
these challenges, we propose a novel topological neural framework of
topological relational inference (TRI) which allows for integrating
higher-order graph information to GNNs and for systematically learning a local
graph structure. The key idea is to rewire the original graph by using the
persistent homology of the small neighborhoods of nodes and then to incorporate
the extracted topological summaries as the side information into the local
algorithm. As a result, the new framework enables us to harness both the
conventional information on the graph structure and information on the graph
higher order topological properties. We derive theoretical stability guarantees
for the new local topological representation and discuss their implications on
the graph algebraic connectivity. The experimental results on node
classification tasks demonstrate that the new TRI-GNN outperforms all 14
state-of-the-art baselines on 6 out 7 graphs and exhibit higher robustness to
perturbations, yielding up to 10\% better performance under noisy scenarios.

positive:
Investigating graph feature learning becomes essentially important with the
emergence of graph data in many real-world applications. Several graph neural
network approaches are proposed for node feature learning and they generally
follow a neighboring information aggregation scheme to learn node features.
While great performance has been achieved, the weights learning for different
neighboring nodes is still less explored. In this work, we propose a novel
graph network layer, known as Node2Seq, to learn node embeddings with
explicitly trainable weights for different neighboring nodes. For a target
node, our method sorts its neighboring nodes via attention mechanism and then
employs 1D convolutional neural networks (CNNs) to enable explicit weights for
information aggregation. In addition, we propose to incorporate non-local
information for feature learning in an adaptive manner based on the attention
scores. Experimental results demonstrate the effectiveness of our proposed
Node2Seq layer and show that the proposed adaptively non-local information
learning can improve the performance of feature learning.

positive:
Graph Neural Networks (GNNs) require a relatively large number of labeled
nodes and a reliable/uncorrupted graph connectivity structure in order to
obtain good performance on the semi-supervised node classification task. The
performance of GNNs can degrade significantly as the number of labeled nodes
decreases or the graph connectivity structure is corrupted by adversarial
attacks or due to noises in data measurement /collection. Therefore, it is
important to develop GNN models that are able to achieve good performance when
there is limited supervision knowledge -- a few labeled nodes and noisy graph
structures. In this paper, we propose a novel Dual GNN learning framework to
address this challenge task. The proposed framework has two GNN based node
prediction modules. The primary module uses the input graph structure to induce
regular node embeddings and predictions with a regular GNN baseline, while the
auxiliary module constructs a new graph structure through fine-grained spectral
clusterings and learns new node embeddings and predictions. By integrating the
two modules in a dual GNN learning framework, we perform joint learning in an
end-to-end fashion. This general framework can be applied on many GNN baseline
models. The experimental results validate that the proposed dual GNN framework
can greatly outperform the GNN baseline methods when the labeled nodes are
scarce and the graph connectivity structure is noisy.

positive:
In complex networks, nodes that share similar structural characteristics
often exhibit similar roles (e.g type of users in a social network or the
hierarchical position of employees in a company). In order to leverage this
relationship, a growing literature proposed latent representations that
identify structurally equivalent nodes. However, most of the existing methods
require high time and space complexity. In this paper, we propose VNEstruct, a
simple approach for generating low-dimensional structural node embeddings, that
is both time efficient and robust to perturbations of the graph structure. The
proposed approach focuses on the local neighborhood of each node and employs
the Von Neumann entropy, an information-theoretic tool, to extract features
that capture the neighborhood's topology. Moreover, on graph classification
tasks, we suggest the utilization of the generated structural embeddings for
the transformation of an attributed graph structure into a set of augmented
node attributes. Empirically, we observe that the proposed approach exhibits
robustness on structural role identification tasks and state-of-the-art
performance on graph classification tasks, while maintaining very high
computational speed.

positive:
Graph neural networks (GNNs) have been demonstrated to be powerful in
modeling graph-structured data. However, training GNNs usually requires
abundant task-specific labeled data, which is often arduously expensive to
obtain. One effective way to reduce the labeling effort is to pre-train an
expressive GNN model on unlabeled data with self-supervision and then transfer
the learned model to downstream tasks with only a few labels. In this paper, we
present the GPT-GNN framework to initialize GNNs by generative pre-training.
GPT-GNN introduces a self-supervised attributed graph generation task to
pre-train a GNN so that it can capture the structural and semantic properties
of the graph. We factorize the likelihood of the graph generation into two
components: 1) Attribute Generation and 2) Edge Generation. By modeling both
components, GPT-GNN captures the inherent dependency between node attributes
and graph structure during the generative process. Comprehensive experiments on
the billion-scale Open Academic Graph and Amazon recommendation data
demonstrate that GPT-GNN significantly outperforms state-of-the-art GNN models
without pre-training by up to 9.1% across various downstream tasks.

positive:
Graph neural network (GNN) has shown convincing performance in learning
powerful node representations that preserve both node attributes and graph
structural information. However, many GNNs encounter problems in effectiveness
and efficiency when they are designed with a deeper network structure or handle
large-sized graphs. Several sampling algorithms have been proposed for
improving and accelerating the training of GNNs, yet they ignore understanding
the source of GNN performance gain. The measurement of information within graph
data can help the sampling algorithms to keep high-value information while
removing redundant information and even noise. In this paper, we propose a
Metric-Guided (MeGuide) subgraph learning framework for GNNs. MeGuide employs
two novel metrics: Feature Smoothness and Connection Failure Distance to guide
the subgraph sampling and mini-batch based training. Feature Smoothness is
designed for analyzing the feature of nodes in order to retain the most
valuable information, while Connection Failure Distance can measure the
structural information to control the size of subgraphs. We demonstrate the
effectiveness and efficiency of MeGuide in training various GNNs on multiple
datasets.

positive:
Social and information networks are gaining huge popularity recently due to
their various applications. Knowledge representation through graphs in the form
of nodes and edges should preserve as many characteristics of the original data
as possible. Some of the interesting and useful applications on these graphs
are graph classification, node classification, link prediction, etc. The Graph
Neural Networks have evolved over the last few years. Graph Neural Networks
(GNNs) are efficient ways to get insight into large and dynamic graph datasets
capturing relationships among billions of entities also known as knowledge
graphs.
  In this paper, we discuss the graph convolutional neural networks graph
autoencoders and spatio-temporal graph neural networks. The representations of
the graph in lower dimensions can be learned using these methods. The
representations in lower dimensions can be used further for downstream machine
learning tasks.

positive:
In order to perform network analysis tasks, representations that capture the
most relevant information in the graph structure are needed. However, existing
methods do not learn representations that can be interpreted in a
straightforward way and that are robust to perturbations to the graph
structure. In this work, we address these two limitations by proposing
node2coords, a representation learning algorithm for graphs, which learns
simultaneously a low-dimensional space and coordinates for the nodes in that
space. The patterns that span the low dimensional space reveal the graph's most
important structural information. The coordinates of the nodes reveal the
proximity of their local structure to the graph structural patterns. In order
to measure this proximity by taking into account the underlying graph, we
propose to use Wasserstein distances. We introduce an autoencoder that employs
a linear layer in the encoder and a novel Wasserstein barycentric layer at the
decoder. Node connectivity descriptors, that capture the local structure of the
nodes, are passed through the encoder to learn the small set of graph
structural patterns. In the decoder, the node connectivity descriptors are
reconstructed as Wasserstein barycenters of the graph structural patterns. The
optimal weights for the barycenter representation of a node's connectivity
descriptor correspond to the coordinates of that node in the low-dimensional
space. Experimental results demonstrate that the representations learned with
node2coords are interpretable, lead to node embeddings that are stable to
perturbations of the graph structure and achieve competitive or superior
results compared to state-of-the-art methods in node classification.

positive:
Structure inference is an important task for network data processing and
analysis in data science. In recent years, quite a few approaches have been
developed to learn the graph structure underlying a set of observations
captured in a data space. Although real-world data is often acquired in
settings where relationships are influenced by a priori known rules, such
domain knowledge is still not well exploited in structure inference problems.
In this paper, we identify the structure of signals defined in a data space
whose inner relationships are encoded by multi-layer graphs. We aim at properly
exploiting the information originating from each layer to infer the global
structure underlying the signals. We thus present a novel method for combining
the multiple graphs into a global graph using mask matrices, which are
estimated through an optimization problem that accommodates the multi-layer
graph information and a signal representation model. The proposed mask
combination method also estimates the contribution of each graph layer in the
structure of signals. The experiments conducted both on synthetic and
real-world data suggest that integrating the multi-layer graph representation
of the data in the structure inference framework enhances the learning
procedure considerably by adapting to the quality and the quantity of the input
data.

positive:
While the celebrated graph neural networks yield effective representations
for individual nodes of a graph, there has been relatively less success in
extending to the task of graph similarity learning. Recent work on graph
similarity learning has considered either global-level graph-graph interactions
or low-level node-node interactions, however ignoring the rich cross-level
interactions (e.g., between each node of one graph and the other whole graph).
In this paper, we propose a multi-level graph matching network (MGMN) framework
for computing the graph similarity between any pair of graph-structured objects
in an end-to-end fashion. In particular, the proposed MGMN consists of a
node-graph matching network for effectively learning cross-level interactions
between each node of one graph and the other whole graph, and a siamese graph
neural network to learn global-level interactions between two input graphs.
Furthermore, to compensate for the lack of standard benchmark datasets, we have
created and collected a set of datasets for both the graph-graph classification
and graph-graph regression tasks with different sizes in order to evaluate the
effectiveness and robustness of our models. Comprehensive experiments
demonstrate that MGMN consistently outperforms state-of-the-art baseline models
on both the graph-graph classification and graph-graph regression tasks.
Compared with previous work, MGMN also exhibits stronger robustness as the
sizes of the two input graphs increase.

positive:
In this paper, we provide a theory of using graph neural networks (GNNs) for
multi-node representation learning (where we are interested in learning a
representation for a set of more than one node, such as link). We know that GNN
is designed to learn single-node representations. When we want to learn a node
set representation involving multiple nodes, a common practice in previous
works is to directly aggregate the single-node representations obtained by a
GNN into a joint node set representation. In this paper, we show a fundamental
constraint of such an approach, namely the inability to capture the dependence
between nodes in the node set, and argue that directly aggregating individual
node representations does not lead to an effective joint representation for
multiple nodes. Then, we notice that a few previous successful works for
multi-node representation learning, including SEAL, Distance Encoding, and
ID-GNN, all used node labeling. These methods first label nodes in the graph
according to their relationships with the target node set before applying a
GNN. Then, the node representations obtained in the labeled graph are
aggregated into a node set representation. By investigating their inner
mechanisms, we unify these node labeling techniques into a single and most
general form -- labeling trick. We prove that with labeling trick a
sufficiently expressive GNN learns the most expressive node set
representations, thus in principle solves any joint learning tasks over node
sets. Experiments on one important two-node representation learning task, link
prediction, verified our theory. Our work explains the superior performance of
previous node-labeling-based methods, and establishes a theoretical foundation
of using GNNs for multi-node representation learning.

positive:
Graph neural networks (GNNs) have achieved superior performance on node
classification tasks in the last few years. Commonly, this is framed in a
transductive semi-supervised learning setup wherein the entire graph, including
the target nodes to be labeled, is available for training. Driven in part by
scalability, recent works have focused on the inductive case where only the
labeled portion of a graph is available for training. In this context, our
current work considers a challenging inductive setting where a set of labeled
graphs are available for training while the unlabeled target graph is
completely separate, i.e., there are no connections between labeled and
unlabeled nodes. Under the implicit assumption that the testing and training
graphs come from similar distributions, our goal is to develop a labeling
function that generalizes to unobserved connectivity structures. To that end,
we employ a graph neural tangent kernel (GNTK) that corresponds to infinitely
wide GNNs to find correspondences between nodes in different graphs based on
both the topology and the node features. We augment the capabilities of the
GNTK with residual connections and empirically illustrate its performance gains
on standard benchmarks.

positive:
Graph Neural Networks (GNNs), which generalize deep neural networks to
graph-structured data, have drawn considerable attention and achieved
state-of-the-art performance in numerous graph related tasks. However, existing
GNN models mainly focus on designing graph convolution operations. The graph
pooling (or downsampling) operations, that play an important role in learning
hierarchical representations, are usually overlooked. In this paper, we propose
a novel graph pooling operator, called Hierarchical Graph Pooling with
Structure Learning (HGP-SL), which can be integrated into various graph neural
network architectures. HGP-SL incorporates graph pooling and structure learning
into a unified module to generate hierarchical representations of graphs. More
specifically, the graph pooling operation adaptively selects a subset of nodes
to form an induced subgraph for the subsequent layers. To preserve the
integrity of graph's topological information, we further introduce a structure
learning mechanism to learn a refined graph structure for the pooled graph at
each layer. By combining HGP-SL operator with graph neural networks, we perform
graph level representation learning with focus on graph classification task.
Experimental results on six widely used benchmarks demonstrate the
effectiveness of our proposed model.

positive:
Driven by the outstanding performance of neural networks in the structured
Euclidean domain, recent years have seen a surge of interest in developing
neural networks for graphs and data supported on graphs. The graph is leveraged
at each layer of the neural network as a parameterization to capture detail at
the node level with a reduced number of parameters and computational
complexity. Following this rationale, this paper puts forth a general framework
that unifies state-of-the-art graph neural networks (GNNs) through the concept
of EdgeNet. An EdgeNet is a GNN architecture that allows different nodes to use
different parameters to weigh the information of different neighbors. By
extrapolating this strategy to more iterations between neighboring nodes, the
EdgeNet learns edge- and neighbor-dependent weights to capture local detail.
This is a general linear and local operation that a node can perform and
encompasses under one formulation all existing graph convolutional neural
networks (GCNNs) as well as graph attention networks (GATs). In writing
different GNN architectures with a common language, EdgeNets highlight specific
architecture advantages and limitations, while providing guidelines to improve
their capacity without compromising their local implementation. An interesting
conclusion is the unification of GCNNs and GATs -- approaches that have been so
far perceived as separate. In particular, we show that GATs are GCNNs on a
graph that is learned from the features. This particularization opens the doors
to develop alternative attention mechanisms for improving discriminatory power.

positive:
Recently, graph neural networks (GNNs) have proved to be suitable in tasks on
unstructured data. Particularly in tasks as community detection, node
classification, and link prediction. However, most GNN models still operate
with static relationships. We propose the Graph Learning Network (GLN), a
simple yet effective process to learn node embeddings and structure prediction
functions. Our model uses graph convolutions to propose expected node features,
and predict the best structure based on them. We repeat these steps recursively
to enhance the prediction and the embeddings.

positive:
We propose interpretable graph neural networks for sampling and recovery of
graph signals, respectively. To take informative measurements, we propose a new
graph neural sampling module, which aims to select those vertices that
maximally express their corresponding neighborhoods. Such expressiveness can be
quantified by the mutual information between vertices' features and
neighborhoods' features, which are estimated via a graph neural network. To
reconstruct an original graph signal from the sampled measurements, we propose
a graph neural recovery module based on the algorithm-unrolling technique.
Compared to previous analytical sampling and recovery, the proposed methods are
able to flexibly learn a variety of graph signal models from data by leveraging
the learning ability of neural networks; compared to previous
neural-network-based sampling and recovery, the proposed methods are designed
through exploiting specific graph properties and provide interpretability. We
further design a new multiscale graph neural network, which is a trainable
multiscale graph filter bank and can handle various graph-related learning
tasks. The multiscale network leverages the proposed graph neural sampling and
recovery modules to achieve multiscale representations of a graph. In the
experiments, we illustrate the effects of the proposed graph neural sampling
and recovery modules and find that the modules can flexibly adapt to various
graph structures and graph signals. In the task of active-sampling-based
semi-supervised learning, the graph neural sampling module improves the
classification accuracy over 10% in Cora dataset. We further validate the
proposed multiscale graph neural network on several standard datasets for both
vertex and graph classification. The results show that our method consistently
improves the classification accuracies.

positive:
Graph distance metric learning serves as the foundation for many graph
learning problems, e.g., graph clustering, graph classification and graph
matching. Existing research works on graph distance metric (or graph kernels)
learning fail to maintain the basic properties of such metrics, e.g.,
non-negative, identity of indiscernibles, symmetry and triangle inequality,
respectively. In this paper, we will introduce a new graph neural network based
distance metric learning approaches, namely GB-DISTANCE (GRAPH-BERT based
Neural Distance). Solely based on the attention mechanism, GB-DISTANCE can
learn graph instance representations effectively based on a pre-trained
GRAPH-BERT model. Different from the existing supervised/unsupervised metrics,
GB-DISTANCE can be learned effectively in a semi-supervised manner. In
addition, GB-DISTANCE can also maintain the distance metric basic properties
mentioned above. Extensive experiments have been done on several benchmark
graph datasets, and the results demonstrate that GB-DISTANCE can out-perform
the existing baseline methods, especially the recent graph neural network model
based graph metrics, with a significant gap in computing the graph distance.

positive:
The majority of popular graph kernels is based on the concept of Haussler's
$\mathcal{R}$-convolution kernel and defines graph similarities in terms of
mutual substructures. In this work, we enrich these similarity measures by
considering graph filtrations: Using meaningful orders on the set of edges,
which allow to construct a sequence of nested graphs, we can consider a graph
at multiple granularities. For one thing, this provides access to features on
different levels of resolution. Furthermore, rather than to simply compare
frequencies of features in graphs, it allows for their comparison in terms of
when and for how long they exist in the sequences. In this work, we propose a
family of graph kernels that incorporate these existence intervals of features.
While our approach can be applied to arbitrary graph features, we particularly
highlight Weisfeiler-Lehman vertex labels, leading to efficient kernels. We
show that using Weisfeiler-Lehman labels over certain filtrations strictly
increases the expressive power over the ordinary Weisfeiler-Lehman procedure in
terms of deciding graph isomorphism. In fact, this result directly yields more
powerful graph kernels based on such features and has implications to graph
neural networks due to their close relationship to the Weisfeiler-Lehman
method. We empirically validate the expressive power of our graph kernels and
show significant improvements over state-of-the-art graph kernels in terms of
predictive performance on various real-world benchmark datasets.

positive:
Graph Neural Networks (GNNs) are efficient approaches to process
graph-structured data. Modelling long-distance node relations is essential for
GNN training and applications. However, conventional GNNs suffer from bad
performance in modelling long-distance node relations due to limited-layer
information propagation. Existing studies focus on building deep GNN
architectures, which face the over-smoothing issue and cannot model node
relations in particularly long distance. To address this issue, we propose to
model long-distance node relations by simply relying on shallow GNN
architectures with two solutions: (1) Implicitly modelling by learning to
predict node pair relations (2) Explicitly modelling by adding edges between
nodes that potentially have the same label. To combine our two solutions, we
propose a model-agnostic training framework named HighwayGraph, which overcomes
the challenge of insufficient labeled nodes by sampling node pairs from the
training set and adopting the self-training method. Extensive experimental
results show that our HighwayGraph achieves consistent and significant
improvements over four representative GNNs on three benchmark datasets.

positive:
Graph neural networks (GNNs) have achieved great success on various tasks and
fields that require relational modeling. GNNs aggregate node features using the
graph structure as inductive biases resulting in flexible and powerful models.
However, GNNs remain hard to interpret as the interplay between node features
and graph structure is only implicitly learned. In this paper, we propose a
novel method called Kedge for explicitly sparsifying the underlying graph by
removing unnecessary neighbors. Our key idea is based on a tractable method for
sparsification using the Hard Kumaraswamy distribution that can be used in
conjugation with any GNN model. Kedge learns edge masks in a modular fashion
trained with any GNN allowing for gradient based optimization in an end-to-end
fashion. We demonstrate through extensive experiments that our model Kedge can
prune a large proportion of the edges with only a minor effect on the test
accuracy. Specifically, in the PubMed dataset, Kedge learns to drop more than
80% of the edges with an accuracy drop of merely 2% showing that graph
structure has only a small contribution in comparison to node features.
Finally, we also show that Kedge effectively counters the over-smoothing
phenomena in deep GNNs by maintaining good task performance with increasing GNN
layers.

positive:
Graph neural networks (GNNs) provide a powerful and scalable solution for
modeling continuous spatial data. However, they often rely on Euclidean
distances to construct the input graphs. This assumption can be improbable in
many real-world settings, where the spatial structure is more complex and
explicitly non-Euclidean (e.g., road networks). Here, we propose PE-GNN, a new
framework that incorporates spatial context and correlation explicitly into the
models. Building on recent advances in geospatial auxiliary task learning and
semantic spatial embeddings, our proposed method (1) learns a context-aware
vector encoding of the geographic coordinates and (2) predicts spatial
autocorrelation in the data in parallel with the main task. On spatial
interpolation and regression tasks, we show the effectiveness of our approach,
improving performance over different state-of-the-art GNN approaches. We
observe that our approach not only vastly improves over the GNN baselines, but
can match Gaussian processes, the most commonly utilized method for spatial
interpolation problems.

positive:
After observing a snapshot of a social network, a link prediction (LP)
algorithm identifies node pairs between which new edges will likely materialize
in future. Most LP algorithms estimate a score for currently non-neighboring
node pairs, and rank them by this score. Recent LP systems compute this score
by comparing dense, low dimensional vector representations of nodes. Graph
neural networks (GNNs), in particular graph convolutional networks (GCNs), are
popular examples. For two nodes to be meaningfully compared, their embeddings
should be indifferent to reordering of their neighbors. GNNs typically use
simple, symmetric set aggregators to ensure this property, but this design
decision has been shown to produce representations with limited expressive
power. Sequence encoders are more expressive, but are permutation sensitive by
design. Recent efforts to overcome this dilemma turn out to be unsatisfactory
for LP tasks. In response, we propose PermGNN, which aggregates neighbor
features using a recurrent, order-sensitive aggregator and directly minimizes
an LP loss while it is `attacked' by adversarial generator of neighbor
permutations. By design, PermGNN{} has more expressive power compared to
earlier symmetric aggregators. Next, we devise an optimization framework to map
PermGNN's node embeddings to a suitable locality-sensitive hash, which speeds
up reporting the top-$K$ most likely edges for the LP task. Our experiments on
diverse datasets show that \our outperforms several state-of-the-art link
predictors by a significant margin, and can predict the most likely edges fast.

positive:
From the perspective of expressive power, this work compares multi-layer
Graph Neural Networks (GNNs) with a simplified alternative that we call
Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node
features with certain multi-hop operators on the graph and then applies an MLP
in a node-wise fashion. From the perspective of graph isomorphism testing, we
show both theoretically and numerically that GA-MLPs with suitable operators
can distinguish almost all non-isomorphic graphs, just like the
Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions
and examining the equivalence classes they induce on rooted graphs, we prove a
separation in expressive power between GA-MLPs and GNNs that grows
exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count
the number of attributed walks. We also demonstrate via community detection
experiments that GA-MLPs can be limited by their choice of operator family, as
compared to GNNs with higher flexibility in learning.

positive:
Graph Neural Networks (GNNs) have received increasing attention for
representation learning in various machine learning tasks. However, most
existing GNNs applying neighborhood aggregation usually perform poorly on the
graph with heterophily where adjacent nodes belong to different classes. In
this paper, we show that in typical heterphilous graphs, the edges may be
directed, and whether to treat the edges as is or simply make them undirected
greatly affects the performance of the GNN models. Furthermore, due to the
limitation of heterophily, it is highly beneficial for the nodes to aggregate
messages from similar nodes beyond local neighborhood.These motivate us to
develop a model that adaptively learns the directionality of the graph, and
exploits the underlying long-distance correlations between nodes. We first
generalize the graph Laplacian to digraph based on the proposed Feature-Aware
PageRank algorithm, which simultaneously considers the graph directionality and
long-distance feature similarity between nodes. Then digraph Laplacian defines
a graph propagation matrix that leads to a model called {\em DiglacianGCN}.
Based on this, we further leverage the node proximity measured by commute times
between nodes, in order to preserve the nodes' long-distance correlation on the
topology level. Extensive experiments on ten datasets with different levels of
homophily demonstrate the effectiveness of our method over existing solutions
in the task of node classification.

positive:
Most approaches that tackle the problem of node classification consider nodes
to be similar, if they have shared neighbors or are close to each other in the
graph. Recent methods for attributed graphs additionally take attributes of
neighboring nodes into account. We argue that the class labels of the neighbors
bear important information and considering them helps to improve classification
quality. Two nodes which are similar based on class labels in their
neighborhood do not need to be close-by in the graph and may even belong to
different connected components. In this work, we propose a novel approach for
the semi-supervised node classification. Precisely, we propose a new node
embedding which is based on the class labels in the local neighborhood of a
node. We show that this is a different setting from attribute-based embeddings
and thus, we propose a new method to learn label-based node embeddings which
can mirror a variety of relations between the class labels of neighboring
nodes. Our experimental evaluation demonstrates that our new methods can
significantly improve the prediction quality on real world data sets.

positive:
Graph Neural Networks (GNNs) have achieved much success on graph-structured
data. In light of this, there have been increasing interests in studying their
expressive power. One line of work studies the capability of GNNs to
approximate permutation-invariant functions on graphs, and another focuses on
the their power as tests for graph isomorphism. Our work connects these two
perspectives and proves their equivalence. We further develop a framework of
the expressive power of GNNs that incorporates both of these viewpoints using
the language of sigma-algebra, through which we compare the expressive power of
different types of GNNs together with other graph isomorphism tests. In
particular, we prove that the second-order Invariant Graph Network fails to
distinguish non-isomorphic regular graphs with the same degree. Then, we extend
it to a new architecture, Ring-GNN, which succeeds in distinguishing these
graphs and achieves good performances on real-world datasets.

positive:
Graph neural networks for heterogeneous graph embedding is to project nodes
into a low-dimensional space by exploring the heterogeneity and semantics of
the heterogeneous graph. However, on the one hand, most of existing
heterogeneous graph embedding methods either insufficiently model the local
structure under specific semantic, or neglect the heterogeneity when
aggregating information from it. On the other hand, representations from
multiple semantics are not comprehensively integrated to obtain versatile node
embeddings. To address the problem, we propose a Heterogeneous Graph Neural
Network with Multi-View Representation Learning (named MV-HetGNN) for
heterogeneous graph embedding by introducing the idea of multi-view
representation learning. The proposed model consists of node feature
transformation, view-specific ego graph encoding and auto multi-view fusion to
thoroughly learn complex structural and semantic information for generating
comprehensive node representations. Extensive experiments on three real-world
heterogeneous graph datasets show that the proposed MV-HetGNN model
consistently outperforms all the state-of-the-art GNN baselines in various
downstream tasks, e.g., node classification, node clustering, and link
prediction.

positive:
Graph neural networks (GNNs) are shown to be successful in modeling
applications with graph structures. However, training an accurate GNN model
requires a large collection of labeled data and expressive features, which
might be inaccessible for some applications. To tackle this problem, we propose
a pre-training framework that captures generic graph structural information
that is transferable across tasks. Our framework can leverage the following
three tasks: 1) denoising link reconstruction, 2) centrality score ranking, and
3) cluster preserving. The pre-training procedure can be conducted purely on
the synthetic graphs, and the pre-trained GNN is then adapted for downstream
applications. With the proposed pre-training procedure, the generic structural
information is learned and preserved, thus the pre-trained GNN requires less
amount of labeled data and fewer domain-specific features to achieve high
performance on different downstream tasks. Comprehensive experiments
demonstrate that our proposed framework can significantly enhance the
performance of various tasks at the level of node, link, and graph.

negative:
Graph neural networks exhibit remarkable performance in graph data analysis.
However, the robustness of GNN models remains a challenge. As a result, they
are not reliable enough to be deployed in critical applications. Recent studies
demonstrate that GNNs could be easily fooled with adversarial perturbations,
especially structural perturbations. Such vulnerability is attributed to the
excessive dependence on the structure information to make predictions. To
achieve better robustness, it is desirable to build the prediction of GNNs with
more comprehensive features. Graph data, in most cases, has two views of
information, namely structure information and feature information. In this
paper, we propose CoG, a simple yet effective co-training framework to combine
these two views for the purpose of robustness. CoG trains sub-models from the
feature view and the structure view independently and allows them to distill
knowledge from each other by adding their most confident unlabeled data into
the training set. The orthogonality of these two views diversifies the
sub-models, thus enhancing the robustness of their ensemble. We evaluate our
framework on three popular datasets, and results show that CoG significantly
improves the robustness of graph models against adversarial attacks without
sacrificing their performance on clean data. We also show that CoG still
achieves good robustness when both node features and graph structures are
perturbed.

negative:
Real data collected from different applications that have additional
topological structures and connection information are amenable to be
represented as a weighted graph. Considering the node labeling problem, Graph
Neural Networks (GNNs) is a powerful tool, which can mimic experts' decision on
node labeling. GNNs combine node features, connection patterns, and graph
structure by using a neural network to embed node information and pass it
through edges in the graph. We want to identify the patterns in the input data
used by the GNN model to make a decision and examine if the model works as we
desire. However, due to the complex data representation and non-linear
transformations, explaining decisions made by GNNs is challenging. In this
work, we propose new graph features' explanation methods to identify the
informative components and important node features. Besides, we propose a
pipeline to identify the key factors used for node classification. We use four
datasets (two synthetic and two real) to validate our methods. Our results
demonstrate that our explanation approach can mimic data patterns used for node
classification by human interpretation and disentangle different features in
the graphs. Furthermore, our explanation methods can be used for understanding
data, debugging GNN models, and examine model decisions.

negative:
Recently, Graph Neural Networks (GNNs) have greatly advanced the task of
graph classification. Typically, we first build a unified GNN model with graphs
in a given training set and then use this unified model to predict labels of
all the unseen graphs in the test set. However, graphs in the same dataset
often have dramatically distinct structures, which indicates that a unified
model may be sub-optimal given an individual graph. Therefore, in this paper,
we aim to develop customized graph neural networks for graph classification.
Specifically, we propose a novel customized graph neural network framework,
i.e., Customized-GNN. Given a graph sample, Customized-GNN can generate a
sample-specific model for this graph based on its structure. Meanwhile, the
proposed framework is very general that can be applied to numerous existing
graph neural network models. Comprehensive experiments on various graph
classification benchmarks demonstrate the effectiveness of the proposed
framework.

negative:
In recent years, graph neural networks (GNNs) have gained increasing
popularity and have shown very promising results for data that are represented
by graphs. The majority of GNN architectures are designed based on developing
new convolutional and/or pooling layers that better extract the hidden and
deeper representations of the graphs to be used for different prediction tasks.
The inputs to these layers are mainly the three default descriptors of a graph,
node features $(X)$, adjacency matrix $(A)$, and edge features $(W)$ (if
available). To provide a more enriched input to the network, we propose a
random walk data processing of the graphs based on three selected lengths.
Namely, (regular) walks of length 1 and 2, and a fractional walk of length
$\gamma \in (0,1)$, in order to capture the different local and global dynamics
on the graphs. We also calculate the stationary distribution of each random
walk, which is then used as a scaling factor for the initial node features
($X$). This way, for each graph, the network receives multiple adjacency
matrices along with their individual weighting for the node features. We test
our method on various molecular datasets by passing the processed node features
to the network in order to perform several classification and regression tasks.
Interestingly, our method, not using edge features which are heavily exploited
in molecular graph learning, let a shallow network outperform well known deep
GNNs.

negative:
Graphs play an important role in many applications. Recently, Graph Neural
Networks (GNNs) have achieved promising results in graph analysis tasks. Some
state-of-the-art GNN models have been proposed, e.g., Graph Convolutional
Networks (GCNs), Graph Attention Networks (GATs), etc. Despite these successes,
most of the GNNs only have shallow structure. This causes the low expressive
power of the GNNs. To fully utilize the power of the deep neural network, some
deep GNNs have been proposed recently. However, the design of deep GNNs
requires significant architecture engineering. In this work, we propose a
method to automate the deep GNNs design. In our proposed method, we add a new
type of skip connection to the GNNs search space to encourage feature reuse and
alleviate the vanishing gradient problem. We also allow our evolutionary
algorithm to increase the layers of GNNs during the evolution to generate
deeper networks. We evaluate our method in the graph node classification task.
The experiments show that the GNNs generated by our method can obtain
state-of-the-art results in Cora, Citeseer, Pubmed and PPI datasets.

negative:
Controversial content refers to any content that attracts both positive and
negative feedback. Its automatic identification, especially on social media, is
a challenging task as it should be done on a large number of continuously
evolving posts, covering a large variety of topics. Most of the existing
approaches rely on the graph structure of a topic-discussion and/or the content
of messages. This paper proposes a controversy detection approach based on both
graph structure of a discussion and text features. Our proposed approach relies
on Graph Neural Network (gnn) to encode the graph representation (including its
texts) in an embedding vector before performing a graph classification task.
The latter will classify the post as controversial or not. Two controversy
detection strategies are proposed. The first one is based on a hierarchical
graph representation learning. Graph user nodes are embedded hierarchically and
iteratively to compute the whole graph embedding vector. The second one is
based on the attention mechanism, which allows each user node to give more or
less importance to its neighbors when computing node embeddings. We conduct
experiments to evaluate our approach using different real-world datasets.
Conducted experiments show the positive impact of combining textual features
and structural information in terms of performance.

negative:
Graph neural networks (GNNs) have significantly improved the representation
power for graph-structured data. Despite of the recent success of GNNs, the
graph convolution in most GNNs have two limitations. Since the graph
convolution is performed in a small local neighborhood on the input graph, it
is inherently incapable to capture long-range dependencies between distance
nodes. In addition, when a node has neighbors that belong to different classes,
i.e., heterophily, the aggregated messages from them often negatively affect
representation learning. To address the two common problems of graph
convolution, in this paper, we propose Deformable Graph Convolutional Networks
(Deformable GCNs) that adaptively perform convolution in multiple latent spaces
and capture short/long-range dependencies between nodes. Separated from node
representations (features), our framework simultaneously learns the node
positional embeddings (coordinates) to determine the relations between nodes in
an end-to-end fashion. Depending on node position, the convolution kernels are
deformed by deformation vectors and apply different transformations to its
neighbor nodes. Our extensive experiments demonstrate that Deformable GCNs
flexibly handles the heterophily and achieve the best performance in node
classification tasks on six heterophilic graph datasets.

negative:
Graph neural networks (GNNs) rely on graph convolutions to extract local
features from network data. These graph convolutions combine information from
adjacent nodes using coefficients that are shared across all nodes. Since these
coefficients are shared and do not depend on the graph, one can envision using
the same coefficients to define a GNN on another graph. This motivates
analyzing the transferability of GNNs across graphs. In this paper we introduce
graphon NNs as limit objects of GNNs and prove a bound on the difference
between the output of a GNN and its limit graphon-NN. This bound vanishes with
growing number of nodes if the graph convolutional filters are bandlimited in
the graph spectral domain. This result establishes a tradeoff between
discriminability and transferability of GNNs.

negative:
Existing popular methods for semi-supervised learning with Graph Neural
Networks (such as the Graph Convolutional Network) provably cannot learn a
general class of neighborhood mixing relationships. To address this weakness,
we propose a new model, MixHop, that can learn these relationships, including
difference operators, by repeatedly mixing feature representations of neighbors
at various distances. Mixhop requires no additional memory or computational
complexity, and outperforms on challenging baselines. In addition, we propose
sparsity regularization that allows us to visualize how the network prioritizes
neighborhood information across different graph datasets. Our analysis of the
learned architectures reveals that neighborhood mixing varies per datasets.

negative:
Graph neural networks (GNNs) are important tools for transductive learning
tasks, such as node classification in graphs, due to their expressive power in
capturing complex interdependency between nodes. To enable graph neural network
learning, existing works typically assume that labeled nodes, from two or
multiple classes, are provided, so that a discriminative classifier can be
learned from the labeled data. In reality, this assumption might be too
restrictive for applications, as users may only provide labels of interest in a
single class for a small number of nodes. In addition, most GNN models only
aggregate information from short distances (e.g., 1-hop neighbors) in each
round, and fail to capture long distance relationship in graphs. In this paper,
we propose a novel graph neural network framework, long-short distance
aggregation networks (LSDAN), to overcome these limitations. By generating
multiple graphs at different distance levels, based on the adjacency matrix, we
develop a long-short distance attention model to model these graphs. The direct
neighbors are captured via a short-distance attention mechanism, and neighbors
with long distance are captured by a long distance attention mechanism. Two
novel risk estimators are further employed to aggregate long-short-distance
networks, for PU learning and the loss is back-propagated for model learning.
Experimental results on real-world datasets demonstrate the effectiveness of
our algorithm.

negative:
Graph Representation Learning (GRL) has experienced significant progress as a
means to extract structural information in a meaningful way for subsequent
learning tasks. Current approaches including shallow embeddings and Graph
Neural Networks have mostly been tested with node classification and link
prediction tasks. In this work, we provide an application oriented perspective
to a set of popular embedding approaches and evaluate their representational
power with respect to real-world graph properties. We implement an extensive
empirical data-driven framework to challenge existing norms regarding the
expressive power of embedding approaches in graphs with varying patterns along
with a theoretical analysis of the limitations we discovered in this process.
Our results suggest that "one-to-fit-all" GRL approaches are hard to define in
real-world scenarios and as new methods are being introduced they should be
explicit about their ability to capture graph properties and their
applicability in datasets with non-trivial structural differences.

negative:
The nodes of a graph existing in a cluster are more likely to connect to each
other than with other nodes in the graph. Then revealing some information about
some nodes, the structure of the graph (graph edges) provides this opportunity
to know more information about other nodes. From this perspective, this paper
revisits the node classification task in a semi-supervised scenario by graph
convolutional networks (GCNs). The goal is to benefit from the flow of
information that circulates around the revealed node labels. The contribution
of this paper is twofold. First, this paper provides a method for extracting
side information from a graph realization. Then a new GCN architecture is
presented that combines the output of traditional GCN and the extracted side
information. Another contribution of this paper is relevant to non-graph
observations (independent side information) that exists beside a graph
realization in many applications. Indeed, the extracted side information can be
replaced by a sequence of side information that is independent of the graph
structure. For both cases, the experiments on synthetic and real-world datasets
demonstrate that the proposed model achieves a higher prediction accuracy in
comparison to the existing state-of-the-art methods for the node classification
task.

negative:
Graphs are the most ubiquitous form of structured data representation used in
machine learning. They model, however, only pairwise relations between nodes
and are not designed for encoding the higher-order relations found in many
real-world datasets. To model such complex relations, hypergraphs have proven
to be a natural representation. Learning the node representations in a
hypergraph is more complex than in a graph as it involves information
propagation at two levels: within every hyperedge and across the hyperedges.
Most current approaches first transform a hypergraph structure to a graph for
use in existing geometric deep learning algorithms. This transformation leads
to information loss, and sub-optimal exploitation of the hypergraph's
expressive power. We present HyperSAGE, a novel hypergraph learning framework
that uses a two-level neural message passing strategy to accurately and
efficiently propagate information through hypergraphs. The flexible design of
HyperSAGE facilitates different ways of aggregating neighborhood information.
Unlike the majority of related work which is transductive, our approach,
inspired by the popular GraphSAGE method, is inductive. Thus, it can also be
used on previously unseen nodes, facilitating deployment in problems such as
evolving or partially observed hypergraphs. Through extensive experimentation,
we show that HyperSAGE outperforms state-of-the-art hypergraph learning methods
on representative benchmark datasets. We also demonstrate that the higher
expressive power of HyperSAGE makes it more stable in learning node
representations as compared to the alternatives.

negative:
In this paper, we propose an end-to-end graph learning framework, namely Deep
Iterative and Adaptive Learning for Graph Neural Networks (DIAL-GNN), for
jointly learning the graph structure and graph embeddings simultaneously. We
first cast the graph structure learning problem as a similarity metric learning
problem and leverage an adapted graph regularization for controlling
smoothness, connectivity and sparsity of the generated graph. We further
propose a novel iterative method for searching for a hidden graph structure
that augments the initial graph structure. Our iterative method dynamically
stops when the learned graph structure approaches close enough to the optimal
graph. Our extensive experiments demonstrate that the proposed DIAL-GNN model
can consistently outperform or match state-of-the-art baselines in terms of
both downstream task performance and computational time. The proposed approach
can cope with both transductive learning and inductive learning.

negative:
Graph Neural Networks (GNNs) have been a latest hot research topic in data
science, due to the fact that they use the ubiquitous data structure graphs as
the underlying elements for constructing and training neural networks. In a
GNN, each node has numerous features associated with it. The entire task (for
example, classification, or clustering) utilizes the features of the nodes to
make decisions, at node level or graph level. In this paper, (1) we extend the
feature selection algorithm presented in via Gumbel Softmax to GNNs. We conduct
a series of experiments on our feature selection algorithms, using various
benchmark datasets: Cora, Citeseer and Pubmed. (2) We implement a mechanism to
rank the extracted features. We demonstrate the effectiveness of our
algorithms, for both feature selection and ranking. For the Cora dataset, (1)
we use the algorithm to select 225 features out of 1433 features. Our
experimental results demonstrate their effectiveness for the same
classification problem. (2) We extract features such that they are linear
combinations of the original features, where the coefficients for each
extracted features are non-negative and sum up to one. We propose an algorithm
to rank the extracted features in the sense that when using them for the same
classification problem, the accuracy goes down gradually for the extracted
features within the rank 1 - 50, 51 - 100, 100 - 150, and 151 - 200.

negative:
Graph Neural Network (GNN) has been demonstrated its effectiveness in dealing
with non-Euclidean structural data. Both spatial-based and spectral-based GNNs
are relying on adjacency matrix to guide message passing among neighbors during
feature aggregation. Recent works have mainly focused on powerful message
passing modules, however, in this paper, we show that none of the message
passing modules is necessary. Instead, we propose a pure
multilayer-perceptron-based framework, Graph-MLP with the supervision signal
leveraging graph structure, which is sufficient for learning discriminative
node representation. In model-level, Graph-MLP only includes multi-layer
perceptrons, activation function, and layer normalization. In the loss level,
we design a neighboring contrastive (NContrast) loss to bridge the gap between
GNNs and MLPs by utilizing the adjacency information implicitly. This design
allows our model to be lighter and more robust when facing large-scale graph
data and corrupted adjacency information. Extensive experiments prove that even
without adjacency information in testing phase, our framework can still reach
comparable and even superior performance against the state-of-the-art models in
the graph node classification task.

negative:
Graph representation learning methods generate numerical vector
representations for the nodes in a network, thereby enabling their use in
standard machine learning models. These methods aim to preserve relational
information, such that nodes that are similar in the graph are found close to
one another in the representation space. Similarity can be based largely on one
of two notions: connectivity or structural role. In tasks where node structural
role is important, connectivity based methods show poor performance. Recent
work has begun to focus on scalability of learning methods to massive graphs of
millions to billions of nodes and edges. Many unsupervised node representation
learning algorithms are incapable of scaling to large graphs, and are unable to
generate node representations for unseen nodes. In this work, we propose
Inferential SIR-GN, a model which is pre-trained on random graphs, then
computes node representations rapidly, including for very large networks. We
demonstrate that the model is able to capture node's structural role
information, and show excellent performance at node and graph classification
tasks, on unseen networks. Additionally, we observe the scalability of
Inferential SIR-GN is comparable to the fastest current approaches for massive
graphs.

negative:
Recently, graph neural networks (GNNs) have revolutionized the field of graph
representation learning through effectively learned node embeddings, and
achieved state-of-the-art results in tasks such as node classification and link
prediction. However, current GNN methods are inherently flat and do not learn
hierarchical representations of graphs---a limitation that is especially
problematic for the task of graph classification, where the goal is to predict
the label associated with an entire graph. Here we propose DiffPool, a
differentiable graph pooling module that can generate hierarchical
representations of graphs and can be combined with various graph neural network
architectures in an end-to-end fashion. DiffPool learns a differentiable soft
cluster assignment for nodes at each layer of a deep GNN, mapping nodes to a
set of clusters, which then form the coarsened input for the next GNN layer.
Our experimental results show that combining existing GNN methods with DiffPool
yields an average improvement of 5-10% accuracy on graph classification
benchmarks, compared to all existing pooling approaches, achieving a new
state-of-the-art on four out of five benchmark data sets.

negative:
Graph neural network (GNN) is a deep model for graph representation learning.
One advantage of graph neural network is its ability to incorporate node
features into the learning process. However, this prevents graph neural network
from being applied into featureless graphs. In this paper, we first analyze the
effects of node features on the performance of graph neural network. We show
that GNNs work well if there is a strong correlation between node features and
node labels. Based on these results, we propose new feature initialization
methods that allows to apply graph neural network to non-attributed graphs. Our
experimental results show that the artificial features are highly competitive
with real features.

negative:
Recently, there has been great success in applying deep neural networks on
graph structured data. Most work, however, focuses on either node- or
graph-level supervised learning, such as node, link or graph classification or
node-level unsupervised learning (e.g. node clustering). Despite its wide range
of possible applications, graph-level unsupervised learning has not received
much attention yet. This might be mainly attributed to the high representation
complexity of graphs, which can be represented by n! equivalent adjacency
matrices, where n is the number of nodes. In this work we address this issue by
proposing a permutation-invariant variational autoencoder for graph structured
data. Our proposed model indirectly learns to match the node ordering of input
and output graph, without imposing a particular node ordering or performing
expensive graph matching. We demonstrate the effectiveness of our proposed
model on various graph reconstruction and generation tasks and evaluate the
expressive power of extracted representations for downstream graph-level
classification and regression.

negative:
Graph embedding techniques allow to learn high-quality feature vectors from
graph structures and are useful in a variety of tasks, from node classification
to clustering. Existing approaches have only focused on learning feature
vectors for the nodes in a (knowledge) graph. To the best of our knowledge,
none of them has tackled the problem of embedding of graph edges, that is,
knowledge graph triples. The approaches that are closer to this task have
focused on homogeneous graphs involving only one type of edge and obtain edge
embeddings by applying some operation (e.g., average) on the embeddings of the
endpoint nodes. The goal of this paper is to introduce Triple2Vec, a new
technique to directly embed edges in (knowledge) graphs. Trple2Vec builds upon
three main ingredients. The first is the notion of line graph. The line graph
of a graph is another graph representing the adjacency between edges of the
original graph. In particular, the nodes of the line graph are the edges of the
original graph. We show that directly applying existing embedding techniques on
the nodes of the line graph to learn edge embeddings is not enough in the
context of knowledge graphs. Thus, we introduce the notion of triple line
graph. The second is an edge weighting mechanism both for line graphs derived
from knowledge graphs and homogeneous graphs. The third is a strategy based on
graph walks on the weighted triple line graph that can preserve proximity
between nodes. Embeddings are finally generated by adopting the SkipGram model,
where sentences are replaced with graph walks. We evaluate our approach on
different real world (knowledge) graphs and compared it with related work.

negative:
The expressive power of graph neural network formalisms is commonly measured
by their ability to distinguish graphs. For many formalisms, the k-dimensional
Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this
paper we consider the expressive power of kth-order invariant (linear) graph
networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate
k-WL. This means that for any two graphs that can be distinguished by k-WL, one
can find a k-IGN which also distinguishes those graphs. The question remains
whether k-IGNs can distinguish more graphs than k-WL. This was recently shown
to be false for k=2. Here, we generalise this result to arbitrary k. In other
words, we show that k-IGNs are bounded in expressive power by k-WL. This
implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.

negative:
Graph embedding is a transformation of nodes of a network into a set of
vectors. A good embedding should capture the underlying graph topology and
structure, node-to-node relationship, and other relevant information about the
graph, its subgraphs, and nodes themselves. If these objectives are achieved,
an embedding is a meaningful, understandable, and often compressed
representation of a network. Unfortunately, selecting the best embedding is a
challenging task and very often requires domain experts. In this paper, we
extend the framework for evaluating graph embeddings that was recently
introduced by the authors. Now, the framework assigns two scores, local and
global, to each embedding that measure the quality of an evaluated embedding
for tasks that require good representation of local and, respectively, global
properties of the network. The best embedding, if needed, can be selected in an
unsupervised way, or the framework can identify a few embeddings that are worth
further investigation. The framework is flexible, scalable, and can deal with
undirected/directed, weighted/unweighted graphs.

negative:
Tensor-network techniques have enjoyed outstanding success in physics, and
have recently attracted attention in machine learning, both as a tool for the
formulation of new learning algorithms and for enhancing the mathematical
understanding of existing methods. Inspired by these developments, and the
natural correspondence between tensor networks and probabilistic graphical
models, we provide a rigorous analysis of the expressive power of various
tensor-network factorizations of discrete multivariate probability
distributions. These factorizations include non-negative tensor-trains/MPS,
which are in correspondence with hidden Markov models, and Born machines, which
are naturally related to local quantum circuits. When used to model probability
distributions, they exhibit tractable likelihoods and admit efficient learning
algorithms. Interestingly, we prove that there exist probability distributions
for which there are unbounded separations between the resource requirements of
some of these tensor-network factorizations. Particularly surprising is the
fact that using complex instead of real tensors can lead to an arbitrarily
large reduction in the number of parameters of the network. Additionally, we
introduce locally purified states (LPS), a new factorization inspired by
techniques for the simulation of quantum systems, with provably better
expressive power than all other representations considered. The ramifications
of this result are explored through numerical experiments. Our findings imply
that LPS should be considered over hidden Markov models, and furthermore
provide guidelines for the design of local quantum circuits for probabilistic
modeling.

negative:
Improving the resilience of a network is a fundamental problem in network
science, which protects the underlying system from natural disasters and
malicious attacks. This is traditionally achieved via successive
degree-preserving edge rewiring operations, with the major limitation of being
transductive. Inductively solving graph-related tasks with sequential actions
is accomplished by adopting graph neural networks (GNNs) coupled with
reinforcement learning under the scenario with rich graph features. However,
such frameworks cannot be directly applied to resilience tasks where only pure
topological structure is available. In this case, GNNs can barely learn useful
information, resulting in prohibitive difficulty in making actions for
successively rewiring edges under a reinforcement learning context. In this
paper, we study in depth the reasons why typical GNNs cause such failure. Based
on this investigation, we propose ResiNet, the first end-to-end trainable
inductive framework to discover resilient network topologies while balancing
network utility. To this end, we reformulate resilience optimization as an MDP
equipped with edge rewiring action space, and propose a pure topology-oriented
variant of GNN called filtration enhanced graph neural network (FireGNN), which
can learn from graphs without rich features. Extensive experiments demonstrate
that ResiNet achieves a near-optimal resilience gain on various graphs while
balancing the utility, and outperforms existing approaches by a large margin.

negative:
Graph Neural Networks (GNNs), which generalize the deep neural networks to
graph-structured data, have achieved great success in modeling graphs. However,
as an extension of deep learning for graphs, GNNs lack explainability, which
largely limits their adoption in scenarios that demand the transparency of
models. Though many efforts are taken to improve the explainability of deep
learning, they mainly focus on i.i.d data, which cannot be directly applied to
explain the predictions of GNNs because GNNs utilize both node features and
graph topology to make predictions. There are only very few work on the
explainability of GNNs and they focus on post-hoc explanations. Since post-hoc
explanations are not directly obtained from the GNNs, they can be biased and
misrepresent the true explanations. Therefore, in this paper, we study a novel
problem of self-explainable GNNs which can simultaneously give predictions and
explanations. We propose a new framework which can find $K$-nearest labeled
nodes for each unlabeled node to give explainable node classification, where
nearest labeled nodes are found by interpretable similarity module in terms of
both node similarity and local structure similarity. Extensive experiments on
real-world and synthetic datasets demonstrate the effectiveness of the proposed
framework for explainable node classification.

negative:
Graph embedding methods are becoming increasingly popular in the machine
learning community, where they are widely used for tasks such as node
classification and link prediction. Embedding graphs in geometric spaces should
aid the identification of network communities as well, because nodes in the
same community should be projected close to each other in the geometric space,
where they can be detected via standard data clustering algorithms. In this
paper, we test the ability of several graph embedding techniques to detect
communities on benchmark graphs. We compare their performance against that of
traditional community detection algorithms. We find that the performance is
comparable, if the parameters of the embedding techniques are suitably chosen.
However, the optimal parameter set varies with the specific features of the
benchmark graphs, like their size, whereas popular community detection
algorithms do not require any parameter. So it is not possible to indicate
beforehand good parameter sets for the analysis of real networks. This finding,
along with the high computational cost of embedding a network and grouping the
points, suggests that, for community detection, current embedding techniques do
not represent an improvement over network clustering algorithms.

negative:
Many real-world problems can be formalized as predicting links in a partially
observed network. Examples include Facebook friendship suggestions,
consumer-product recommendations, and the identification of hidden interactions
between actors in a crime network. Several link prediction algorithms, notably
those recently introduced using network embedding, are capable of doing this by
just relying on the observed part of the network. Often, the link status of a
node pair can be queried, which can be used as additional information by the
link prediction algorithm. Unfortunately, such queries can be expensive or
time-consuming, mandating the careful consideration of which node pairs to
query. In this paper we estimate the improvement in link prediction accuracy
after querying any particular node pair, to use in an active learning setup.
Specifically, we propose ALPINE (Active Link Prediction usIng Network
Embedding), the first method to achieve this for link prediction based on
network embedding. To this end, we generalized the notion of V-optimality from
experimental design to this setting, as well as more basic active learning
heuristics originally developed in standard classification settings. Empirical
results on real data show that ALPINE is scalable, and boosts link prediction
accuracy with far fewer queries.

negative:
Networks provide a powerful formalism for modeling complex systems by using a
model of pairwise interactions. But much of the structure within these systems
involves interactions that take place among more than two nodes at once; for
example, communication within a group rather than person-to person,
collaboration among a team rather than a pair of coauthors, or biological
interaction between a set of molecules rather than just two. Such higher-order
interactions are ubiquitous, but their empirical study has received limited
attention, and little is known about possible organizational principles of such
structures. Here we study the temporal evolution of 19 datasets with explicit
accounting for higher-order interactions. We show that there is a rich variety
of structure in our datasets but datasets from the same system types have
consistent patterns of higher-order structure. Furthermore, we find that tie
strength and edge density are competing positive indicators of higher-order
organization, and these trends are consistent across interactions involving
differing numbers of nodes. To systematically further the study of theories for
such higher-order structures, we propose higher-order link prediction as a
benchmark problem to assess models and algorithms that predict higher-order
structure. We find a fundamental differences from traditional pairwise link
prediction, with a greater role for local rather than long-range information in
predicting the appearance of new interactions.

negative:
Graph neural networks provide a powerful toolkit for embedding real-world
graphs into low-dimensional spaces according to specific tasks. Up to now,
there have been several surveys on this topic. However, they usually lay
emphasis on different angles so that the readers can not see a panorama of the
graph neural networks. This survey aims to overcome this limitation, and
provide a comprehensive review on the graph neural networks. First of all, we
provide a novel taxonomy for the graph neural networks, and then refer to up to
400 relevant literatures to show the panorama of the graph neural networks. All
of them are classified into the corresponding categories. In order to drive the
graph neural networks into a new stage, we summarize four future research
directions so as to overcome the facing challenges. It is expected that more
and more scholars can understand and exploit the graph neural networks, and use
them in their research community.

negative:
The traditional setup of link prediction in networks assumes that a test set
of node pairs, which is usually balanced, is available over which to predict
the presence of links. However, in practice, there is no test set: the
ground-truth is not known, so the number of possible pairs to predict over is
quadratic in the number of nodes in the graph. Moreover, because graphs are
sparse, most of these possible pairs will not be links. Thus, link prediction
methods, which often rely on proximity-preserving embeddings or heuristic
notions of node similarity, face a vast search space, with many pairs that are
in close proximity, but that should not be linked. To mitigate this issue, we
introduce LinkWaldo, a framework for choosing from this quadratic,
massively-skewed search space of node pairs, a concise set of candidate pairs
that, in addition to being in close proximity, also structurally resemble the
observed edges. This allows it to ignore some high-proximity but
low-resemblance pairs, and also identify high-resemblance, lower-proximity
pairs. Our framework is built on a model that theoretically combines Stochastic
Block Models (SBMs) with node proximity models. The block structure of the SBM
maps out where in the search space new links are expected to fall, and the
proximity identifies the most plausible links within these blocks, using
locality sensitive hashing to avoid expensive exhaustive search. LinkWaldo can
use any node representation learning or heuristic definition of proximity, and
can generate candidate pairs for any link prediction method, allowing the
representation power of current and future methods to be realized for link
prediction in practice. We evaluate LinkWaldo on 13 networks across multiple
domains, and show that on average it returns candidate sets containing 7-33%
more missing and future links than both embedding-based and heuristic
baselines' sets.

negative:
Data collection often involves the partial measurement of a larger system. A
common example arises in collecting network data: we often obtain network
datasets by recording all of the interactions among a small set of core nodes,
so that we end up with a measurement of the network consisting of these core
nodes along with a potentially much larger set of fringe nodes that have links
to the core. Given the ubiquity of this process for assembling network data, it
is crucial to understand the role of such a `core-fringe' structure.
  Here we study how the inclusion of fringe nodes affects the standard task of
network link prediction. One might initially think the inclusion of any
additional data is useful, and hence that it should be beneficial to include
all fringe nodes that are available. However, we find that this is not true; in
fact, there is substantial variability in the value of the fringe nodes for
prediction. Once an algorithm is selected, in some datasets, including any
additional data from the fringe can actually hurt prediction performance; in
other datasets, including some amount of fringe information is useful before
prediction performance saturates or even declines; and in further cases,
including the entire fringe leads to the best performance. While such variety
might seem surprising, we show that these behaviors are exhibited by simple
random graph models.

negative:
Graphs are widely used as a popular representation of the network structure
of connected data. Graph data can be found in a broad spectrum of application
domains such as social systems, ecosystems, biological networks, knowledge
graphs, and information systems. With the continuous penetration of artificial
intelligence technologies, graph learning (i.e., machine learning on graphs) is
gaining attention from both researchers and practitioners. Graph learning
proves effective for many tasks, such as classification, link prediction, and
matching. Generally, graph learning methods extract relevant features of graphs
by taking advantage of machine learning algorithms. In this survey, we present
a comprehensive overview on the state-of-the-art of graph learning. Special
attention is paid to four categories of existing graph learning methods,
including graph signal processing, matrix factorization, random walk, and deep
learning. Major models and algorithms under these categories are reviewed
respectively. We examine graph learning applications in areas such as text,
images, science, knowledge graphs, and combinatorial optimization. In addition,
we discuss several promising research directions in this field.

negative:
The success of deep convolutional neural network (CNN) in computer vision
especially image classification problems requests a new information theory for
function of image, instead of image itself. In this article, after establishing
a deep mathematical connection between image classification problem and quantum
spin model, we propose to use entanglement entropy, a generalization of
classical Boltzmann-Shannon entropy, as a powerful tool to characterize the
information needed for representation of general function of image. We prove
that there is a sub-volume-law bound for entanglement entropy of target
functions of reasonable image classification problems. Therefore target
functions of image classification only occupy a small subspace of the whole
Hilbert space. As a result, a neural network with polynomial number of
parameters is efficient for representation of such target functions of image.
The concept of entanglement entropy can also be useful to characterize the
expressive power of different neural networks. For example, we show that to
maintain the same expressive power, number of channels $D$ in a convolutional
neural network should scale with the number of convolution layers $n_c$ as
$D\sim D_0^{\frac{1}{n_c}}$. Therefore, deeper CNN with large $n_c$ is more
efficient than shallow ones.

negative:
We consider the data shuffling problem in a distributed learning system, in
which a master node is connected to a set of worker nodes, via a shared link,
in order to communicate a set of files to the worker nodes. The master node has
access to a database of files. In every shuffling iteration, each worker node
processes a new subset of files, and has excess storage to partially cache the
remaining files, assuming the cached files are uncoded. The caches of the
worker nodes are updated every iteration, and they should be designed to
satisfy any possible unknown permutation of the files in subsequent iterations.
For this problem, we characterize the exact load-memory trade-off for
worst-case shuffling by deriving the minimum communication load for a given
storage capacity per worker node. As a byproduct, the exact load-memory
trade-off for any shuffling is characterized when the number of files is equal
to the number of worker nodes. We propose a novel deterministic coded shuffling
scheme, which improves the state of the art, by exploiting the cache memories
to create coded functions that can be decoded by several worker nodes. Then, we
prove the optimality of our proposed scheme by deriving a matching lower bound
and showing that the placement phase of the proposed coded shuffling scheme is
optimal over all shuffles.