The Graph Learning Attention Mechanism: Learnable Sparsification Without Heuristics
Authors: Mattson Thieme
Yada Zhu
Han Liu
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph structure learning
graph attention networks

Abstract: Graph Neural Networks (GNNs) are local aggregators that derive their expressive power from their sensitivity to network structure. However, this sensitivity comes at a cost: noisy edges degrade performance. In response, many GNNs include edge-weighting mechanisms that scale the contribution of each edge in the aggregation step. However, to account for neighborhoods of varying size, node-embedding mechanisms must normalize these edge-weights across each neighborhood. As such, the impact of noisy edges cannot be eliminated without removing those edges altogether. Motivated by this issue, we introduce the Graph Learning Attention Mechanism (GLAM): a drop-in, differentiable structure learning layer for GNNs that separates the distinct tasks of structure learning and node embedding. In contrast to existing graph learning approaches, GLAM does not require the addition of exogenous structural regularizers or edge-selection heuristics to learn optimal graph structures. In experiments on citation and co-purchase datasets, we demonstrate that our approach can match state of the art semi-supervised node classification accuracies while inducing an order of magnitude greater sparsity than existing graph learning methods.

Under review as a conference paper at ICLR 2023
THE GRAPH LEARNING ATTENTION MECHANISM: LEARNABLE SPARSIFICATION WITHOUT HEURISTICS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) are local aggregators that derive their expres- sive power from their sensitivity to network structure. However, this sensitivity comes at a cost: noisy edges degrade performance. In response, many GNNs in- clude adge-weighting mechanisms that scale the contribution of each edge in the aggregation step. However, to account for neighborhoods of varying size, node- embedding mechanisms must normalize these edge-weigghs across each neighbor- hood. As such, the impact of noisy edges cannot be eliminated without removing those edges altogether. Motivated by this issue, we introduce the Graph Learn- ing Attention Mechanism (GLAM): a drop-in, differentiable structure learning layer for GNNs that separates the distinct tasks of structure learning and node embedding. In contrast to existing graph learning approaches, GLAM does not require the addition of exogenous structural regularizers or edge-selection heuris- ties to learn optimal graph structures. In experiments on citation and co-purchase datasets, we demonstrate that our approach can match state of the semi- supervised node classification accuracies while inducing an order of magnitude greater sparsity than existing graph learning methods.
INTRODUCTION
Local interactions govern the properties of nearly all complex systems, from protein folding and cellular proliferation to group dynamies and financial markets (Stocker et al., 1996 Doyle et al, 1997 Mathur 2006 Özgür 2011 Jiang et al. 2014). When modeling such systems, representing interactions explicitly the form of a graph can improve model performance dramatically, both at the local and global level. Graph Neural Networks (GNNs) are designed to operate on such graph- structured data and have quickly become state the art in a host of structured domains (Wu et al., 2019). However, GNN models rely heavily the provided graph structures representing meaningful relations, for example, the bonds between atoms in a molecule (Fang et al. (022).. Additionally, to generate useful node embeddings, GNNs employ permutation invariant neighborhood aggregation functions which implicitly assume that neighborhoods satisfy certain homogeneity properties (Zhu al. 2020). If noisy edges are introduced, or if the neighborhood assumptions are not met, GNN performance suffers.
To address both issues simultaneously, many GNNs include mechanisms for learning edge weights which scale the influence of the features on neighboring nodes in the aggregation step. The Graph Attention Network (GAT) (Veličković al. 2017). for example, adapts the typical attention mech- anism (Vaswani et al., 2017) to the graph setting, learning attention coefficients between adjacent nodes in the graph as opposed tokens in sequence. As we will show Section 3 the demands of edge weighting (or structure learning) inherently conflict with those of node embedding, and edge weighting mechanisms that are joined together with node embedding mechanisms are not capable of eliminating the negative impact of noisy edges their
In this paper, we introduce a method for separating the distinct tasks of structure learning and node embedding in GNNs. Our method takes the form of structure learning layer that be placed in front of existing GNN layers to learn fask-informed graph structures that optimize performance on the downstream task. Our primary contributions are as follows:

---

Under review as a conference paper at ICLR 2023
1. We first introduce principled framework for considering the inherent conflicts between structure learning and node embedding.
2. Motivated by this framework, we introduce the Graph Learning Attention Mechanism (GLAM) layer that, when used alongside GNNs, separates the distinct tasks of structure learning and node embedding.
In addition to enabling GAT models to meet or exceed state the art performance semi- supervised node classification tasks, the GLAM layer induces order of magnitude greater sparsity than other structure learning methods (Luo et al. 2020 Ye & Ji [021] Chen et al.) (0200] |Fanceechh] 2021/Chen al., 2019 Shang et al. 2021 Miao al. 2022) Also, in contrast the existing structure learning methods, GLAM does not employ any edge selection heuristics, exogenous structural regularizers or otherwise modify the existing loss function to accommodate the structure learning task. This makes it simpler to apply in existing GNN pipelines as there is no need to modify carefully crafted and domain- speccffc objective functions. Our approach is also scalable and generalizable to the inductive setting as it does not rely on optimizing fixed adjacency matrix.
2 PRELIMINARIES
As our method takes inspiration from the original GAT, we begin by reviewing the mechanism by which the GAT layer generates edge weights, as well as how those edge weights are used to aggregate neighborhood information. Understanding this mechanism is important to understanding our conceptual framework (Section as well as the GLAM layer (Section 4
Graph attention networks learn weighted attention scores Etj for all edges between nodes i and j.j E Nr where N₁ is the one-hop neighborhood of node i. These attention scores represent the importance of the features node j to node and are computed in the following manner.
Eij = LeakyReLU a" [WGATh, Il Waarh!)
(1)
where hi F.F are node feature vectors, || is vector concatenation, WGar E FF xF is shared linear transformation for transforming input features into higher level representations, and ä E 2 the learnable attention weights that take the form of single-layer feedforward neural network.
To ensure the attention scores are comparable across neighborhoods of varying size, they are nor- malized into attention coefficients oi using softmax activation:
exp(ery
Oij softmax,(esg) = ΣjeN; exp(er))
For stability and expressivity, the mechanism is extended to employ multi-head attention, and the outputs of the heads in the final layer are aggregated by averaging:
M softmax
Σ
Σ
aij W
Warnh
K
k=1jeN:
In the next section, we explain why the normalization procedure Eq. 2 while crucial for node embedding, is an impediment for structure learning.
3 CONFLICTING DEMANDS: NODE EMBEDDING VS. STRUCTURE LEARNING
At first glance, it may seem could address the structure learning problem by simply threshold- ing the existing GAT attention coefficients a,y. However, due to the need for neighborhood wise normalization and permutation invariant aggregation, this would not be ideal. As motivating ample, consider the following: if we add three random edges per node to the standard Cora dataset McCallum et al. (2000), then train GAT to perform semi-supervised node classification, get
2

---

Under review as a conference paper at ICLR 2023
classification accuracy of 65.9%. If we manually set the edge weights for each of those newly added random edges to zero (note: the GAT is not able to learn this weighting on its own) the same GAT is able to achieve 79% accuracy. However, if we simply remove all the newly added random edges so the GAT does not consider them at all, the GAT can achieve 82. 1 1% accuracy. In GNNs with permutation sermutation-invariint aggregation mechanisms, dropping noisy edges is more effective than learning to zero their edge weights.
To understand this result, it's important to understand why the GAT attention coefficients are calcu- lated as the softmax of the attention scores. This softmax step serves two important purposes:
1. It normalizes the attention scores into attention coefficients that sum to one, which ensures the sum of the neighboring representations (as defined in Eq. (3) is also normalized. This is a crucial function of any node embedding mechanism because normalizes the distributional characteristics of hi not just across different neighborhoods but across neighborhoods of varying size. Without this, the downstream layers that ingest hi would need to account for widely variable magnitudes the values of R2 and performance would suffer.
2. The softmax serves as an implicit, low-resolution structure learning device. To locate the maximum input element in differentiable manner, softmax uses exponentials to exagger- ate the difference between the maximum element and all of the rest. In graph attention networks, this means exaggerating the difference between the attention coefficient of the single most important neighbor vs. all the rest. This imbues the attention coefficients, and thus each nodes' neighborhood, with soft-sparsity that improves the learned node embeddings by minimizing the influence of all but the single most useful neighbor.
For these reasons, if our aim is to generate useful node embeddings for node-wise prediction, should not do away with the softmax activation to normalize attention coefficients in each neigh- borhood. However, as aim is to jointly learn useful node embeddings and the graph structure, this embedding mechanism alone is not sufficient. distinct structure learning mechanism would require the following:
To learn the graph structure, we need to assess the value of each neighbor independently. This is because, in graph learning, local neighborhoods are subject noisy evolution as the network samples edges. If the value each neighbor is conditional on the present neighborhood, it will be difficult to disentangle the relative value of one neighbor from another as the neighborhood evolves.
This is why the existing edge-weighting + node embedding paradigm is insufficient if our goal is to simultaneously learn node embedding and graph structure: the neighborhood-wisg normalization (softmax over edge-weigh weights) expresses each neighbors' importance relative to all the other nodes in the neighborhood, which is in direct conflict with the edge-wise independence requirements of structure learning.
To preserve the embedding advantages of GNNs while accommodating the conflicting demands of structure learning, introduce the Graph learning Attention Mechanism (GLAM).
THE GRAPH LEARNING ATTENTION MECHANISM (GLAM)
Like the GAT layer, the GLAM layer ingests the node features NxF and the edge set E, where N is the number of nodes and F is the number of features per node. For each node i, we transform the node features h; into higher order representations z; using a shared linear transformation W e R P
x4 = W(h), 24 E F
(4)
For each edge between nodes and j in the provided edge set E, we then construct a represen- tation for that edge by concatenating the node representations. x; and xj. From here, our GLAM layer differs from the GAT layer. Using another shared linear layer S RRIxs,, we map these
3

---

Under review as a conference paper at ICLR 2023
A.
GLAM Layer
S
h2
Wh
Σ
+
(0.1)
h2j
Why
sigmoid
discard retain edge
mask
B.
h'
h
GNN
GNN
GLAM
8'
GLAM
8"
Figure I: A: An illustration of the Graph Learning Attention Mechanism operating on a single pair of connected nodes with features h4 hy IR", using the shared weight matrix W Fx* and multi-headed attention with K = 3 heads. B: A high level overview of how the GLAM layer is used learn optimal graph structures at each layer. The input is the original graph with node features h E R NXF and edge set x. To make as few assumptions about the optimal graph structure as possible, we feed the original edge set into each GLAM layer to reassess the utility each edge at each layer. We note that this is optional, and chaining edge sets across layers is also possible.
edge representations onto structure learning n I where the score my for each edge becomes:
Mi = o (S + +u)
(5)
where || vector concatenation, u E R i.i.d. noise drawn from U(- 0.5, 0.5) distribution cen- tered about zero, and a is sigmoid activation allowing each Th to be interpreted the probability of retaining the edge between nodes and j. We note here that the noise term not strictly required, but we found that it helped to smooth out the training.
Finally, we extend the GLAM layer to include K attention heads, and the final structure learning score 7/j for each edge becomes:
S [
Tie
Next, we sample discrete mask M (0, 1}16) from the distribution parameterized by the structure learning scores 77. When applied to the given graph E, get sparsified graph (E) E' C E. To sample the discrete values M from the continuous probabilities 7 differentiably, we use the Gumbel-Softmax reparameterization trick introduced by Jang al. (016)) and retain the edge between nodes and j if fıj > 0.5.
This graph El is then used in place of E in the downstream GNN representation learner. If that downstream GNN were GAT, using the equations from Section 2 the attention coefficients would become:
4

---

Under review as a conference paper at ICLR 2023
exp(eij)
aij = softmax,(es))
EjENy exp(e())
and
7 softmax
Σ JEN?
W
dg
K
where the neighborhoods .V are defined by the non-masked edges in E' where >> 0.5.
As each GNN model incorporates graph structure in its own way, we have ensured that GLAM pro- duces maximally general, differentiable mask on the given edges. This mask may be readily used to separate the structure learning tasks from node embedding regardless of the particular embedding mechanism.
For example, our implementation, we incorporate the learned graph M into the GAT by trivially swapping the softmax over the attention coefficients with sparse softmax that respects the masked edges (as shown in Eq. 7). Extending beyond the GAT, we could incorporate the learned graph into the widely used Graph Convolutional Network (GCN) (Kipf & Welling 2016), for example, by sim- ply multiplying the adjacency matrix A by the mask M before the application of the renormalization trick. To apply M in arbitrary GNNs, need only insert it before the neighborhood aggregation step.
RELATED WORK
The structure learning literature includes many effective methods for inducing task-informed, spar- sified subgraphs. However, each of them relies on either selectsn heuristics (such as top-k selection) or exogenous structural regularizers (such as penalties on retained edges) to stabilize the structure learning process. contrast, our approach requires none of these, making more read- ily deployable in existing GNN pipelines and obviating the need to interfere with carefully crafted objective functions or training methodologies.
Approaches such Neural Relational Inference (Kipf et al. 2018) and Graphs for Time Series (Shang et al., [202I) introduce methods for learning probabilistic graph models optimized for various time-series forecasting tasks. However, while both induce sparse subgraphs, they rely exogenous regularization (penalties on retained edges) and suffer from scalability issues as both learn fixed adjacency matrices.
More closely related to our approach are the Graph Stochastic Attention, GSAT (Miao et al. 2022) and Stochastic Graph Attention, SGAT (Ye & Ji (021) models, which also adapt the graph attention layer to learn sparse subgraphs. SGAT attaches a binary gate to each edge in the given graph, then learns a single adjacency matrix that shared across all layers. While effective, this adjacency matrix makes it difficult to scale and they employ an Lo norm in the loss function to penalize retained edges.
GSAT (Mio et al.) 2022), based on the graph information bottleneck principle (Wu et al.) 2020) designed be an interpretable graph learner and uses a similar sparse attention mechanism to assess the utility of each edge. However, in spite of not using sparsity constraints such as L. norms, they do add additional structural regularization terms into loss function. Additionally, learnable weights in GSAT are shared between the GNN used to generate the binary mask and the GNN used for downstream node embedding. As we reviewed Section 3 the demands of structure learning conflict with those of node embedding, sharing weights/archiieecures between these networks may reduce performance some tasks.
As GSAT not evaluated on datasets, and SGAT more closely resembles GLAM in design and functionality (inducing an edge sparsified graph) we confine our direct comparison to SGAT to ensure fairness and clarity.
5

---

Under review as a conference paper at ICLR 2023
Type
Nodes
Edges
Features
Classes
H(G)
Cora PubMed
Citation Network
2,708
13,264
1,433
0.83
Citation Network
19,717
108,365
500
0.79
Citeseer
Citation Network
3,307
12,431
3,703
6
0.71
Amazon Photo
Co-Purchase
7,487
245,812
745
8
0.84
Amazon Computers
Co-Purchase 13,385
505,474
767
10
0.79
Table I: Homophilic graph datasets used in our experiments.
EXPERIMENTS
To demonstrate the efficacy of the GLAM layer, we report performance in semi-supervised node classification tasks on real-world graph datasets. As it is well known that GNNs performance is degraded by heterophilic graphs (in which adjacent nodes tend to have different labels) we look only those graphs where the edges bring material value for GNNs, i.e. homophilous graphs. Formally, the edge homophily ratio of a graph is value the range [0, 1] that denotes the fraction of edges in the graph that join nodes with the same labels:
H(G, (URiE VJ)
Σ (B.J)EE
(v: Uÿ)
(8)
[
Where G is an input graph with nodes E V having labels y. While homophily isn't It unrealistic assumption, with most graphs being constructed this way (McPherson et al. 200T), a method for graph-adaptation based on the assumptions of the downstream GNN is still desirable many GNN models implicitly assume a high degree of homophily and perform poorly when this assumption violated (Zhu et al.) 2020). In graphs with low homophily, such the WebKK""dataseer performance is often optimized by removing nearly every edge. For this reason, to get a better understanding of the GLAM layer's efficacy, confine our study to the homophilic graphs detailed in Table
GNN
Cora, PubMed and Citeseer (McCallum al. 2000). [en al. (2008). Giles et al. (1998)
citation datasets with relatively low average degree. Nodes correspond to documents (academic papers) and edges represent citations between these documents. Node features are the bag of words representation of the document and the task is to classify each document by its topic. Amazon Photo and Amazon Computers (Shchur et al. (018)) are co-purctee co-purchase datasets with a much higher average degree, where each node corresponds to a product and two nodes are linked if those products are frequently bought together. The node features are also bag of words representations but of the reviews of each product. Similarly, the task is to classify each product into its product category.
For fair comparison with SGAT, we use the same canonical splits in each dataset: 20 nodes per class for training, 500 nodes for validation and 1,000 for testing.
6.1 TRAINING METHODOLOOGY
In all our experiments, train layer GAT, using the GLAM layer to learn optimal structures for each GAT layer. Crucially, to demonstrate how the GLAM layer may be 'dropped in' to an existing GNN model with little no modification the training scheme, we use the known opti- mal hyperparameters and training methodology for the GAT layers (as reported in Veličković et al. (017)) without modification. This covers all components of the model including loss functions, reg- ularization, optimizers and layer sizes. The only hyperparameters we modify are those associated with the inserted GLAM layers and, as mentioned in Section 4, the learned mask enforeed using a sparse softmax activation in the GAT layers that respects the mask M. As the Co-Purchase datasets were not tested in the original GAT paper, we began optimization with the same hyperparameters as

---

Under review as a conference paper at ICLR 2023
Dataset
Cora
PubMed
Citeseer
Photo
Computers
MLP
49.5%
68.1 %
46.9%
70.5%
53.1%
GAT
82.4%
78.2%
70.9%
89.1%
81.5%
SGAT
83.0%
78.3%
71.5%
89.9%
81.8%
GLAM
82.4%
78.6%
70.5%
90.3%
83.0%
% Edges Removed (layer / layer 2)
SGAT 2.0/-
2.2/
1.2 /
42.3
63.6 /
GLAM
22.3 22.3/2.2 2.2
30.0/ / 0.3
46.3 / 1.4 63.1 / 13.2 55.0 / 8.7
Table 2: Top: supersupe node classification accuracies are listed percent. Bottom: Per- centage of edges removed at the first / second layer. For SGAT, single graph is learned the first layer and reused for all following layers. In our experiments, the GLAM layer is used to learn an optimal graph each layer.
Cora, and found that increasing the hidden dimension from 8 to 32 led optimal performance. In all cases, we use cross entropy as our loss function and the Adam optimizer Kingma & Ba (2014) perform gradient descent. In all experiments report the average classification performance and induced sparsity over 10 independent trials (Table All hyperparameters are available in the GitHub.
Additionally, to make as few assumptions about the optimal graph as possible, we use the GLAM layer to independently assess the utility of each edge at each layer, as shown in Figure [ and report the induced sparsity at each layer. This is in contrast to existing methods which learn a single graph the first layer that then reused for all the downstream layers. As we will discuss more Section 6.2 learning the optimal graph at each layer not only improves performance and induces greater sparsity but allows us better observe the relationship between the data, the GNN aggregator, and the downstream task more clearly.
We note here that the use of exogenous regularizers and edge-selection heuristics, as employed by other structure learning methods, is help the structure learner better adapt the demands of the downstream GNN. With the GLAM layer, we enable this same sort of adaptation by simply making these layers more sensitive than the downstream GNN layers. To do so, relax the regularization (weight decay) and amplify the learning signal (increase the learning rate) for just the GLAM layers. Doing for only the GLAM layers allows them adapt the GNN representation learner without the need for additional terms in the loss function. These layer-wise changes are slight and optimal values vary by dataset. All layer-specific learning rates and regularization coefficients are outlined in the hyperparameter configuration files at [GitHub redacted for review].
Finally, self-loops have disproportionate utility in any node-wise prediction task, the GLAM layers only attends over those edges that adjoin separate nodes, retaining all self-loops by default.
6.2 PREDICTION PERFORMANCE AND INDUCED SPARSITY
On semi-supervised node classification datasets, the GLAM layer enables the GAT to reach simi- lar accuracies while inducing an order of magnitude greater sparsity than existing methods. This increased sparsification is notable as we do not explicitly enforce sparsity constraints or penalize retained edges. As the GLAM method fundamentally about inducing task-informed subgraphs, and classification accuracies are all similar to SGAT, confine our analysis to the sparsification aspect of the results. Complete results can be found in Table
On each of the citation datasets, the GLAM layer is competitive with SGAT on prediction perfor- mance while inducing over an order of magnitude greater sparsity. This degree of sparsity has not yet been induced in these datasets while preserving SOTA classification performance. As such, view these results as indicating, in addition to the efficacy of the GLAM layer, that there may be more redundant edges in these datasets than previously thought. Part of the advantage of the GLAM
7

---

Under review as a conference paper at ICLR 2023
layer is that train it using using only the signal from the downstream task. As such, the in- duced graph is a reflection purely of the relationship between the data, the GNN aggregation scheme, and the downstream task. Following from this, note that the first GLAM layer trained on these datasets removes closer to - H (G) percent of the edges. There is not an exact correspondence, but the proximity between these downstream GAT performs best on neighborhoods with higher homophily. The second GLAM layer removes on the order of 1% of the edges, which is similar to SGAT. We hypothesize that more edges are retained in the second and final layer due to the node representations already containing infor- mation from their 1 -hop neighborhood, and there being additional value in aggregating information from the h-hop neighborhood.
quantities is likely reflection of the GLAM layers learning that the
On the co- co-purchase datasets which have much larger average degrees, the GLAM layers remove substantially more edges in the first layer but fewer in the second. We emphasize here that as there are no structural regularizers, GLAM is not encouraged to learn the sparsest graph possible, but rather the graph which optimizes downstream task performance. As we can see with the Comput- ers dataset, retaining a few more edges in the first layer and a few less in the second resulted in substantially higher classification accuracies.
While our method does not always achieve state of the art classification performance, we do achieve similar performance with far greater sparsification and without changes to the canonical loss func- tion. As the GL.AM layer is differentiable and can be readily integrated with arbitrary downstream GNNs, we believe it could be widely useful and is worthy of further study.
7 CONCLUSIONS
We presented a principled framework for considering the graph structure learning problem in the context of graph neural networks, well the Graph Learning Attention Mechanism (GLAM) novel structure learning layer motivated by this framework. In contrast to existing structure learn- ing approaches, GLAM does not require exogenous structural regularizers nor does it utilize edge- selection heuristics. In experiments on citation and co-purchase datasets the GLAM layer allows an unmodified GAT to match state of the art performance while inducing an order of magnitude greater sparsity than other graph learning approaches.
There are several improvements that could be made the method, especially as it relates to stabiliz- ing the structure learning layers without augmenting canonical loss functions. Future research could be directed at adaptive methods of decaying the learning rates in those layers or layer-specific early stopping.
Finally, as our approach yields graph structures uncorrupted by the influence of exogenous heuris- tics, we also see the potential for its use in the design and analysis of novel GNN architectures. In the GLAM layer, edges are retained or discarded based whether the downstream GNN can make productive use of them. By interpreting the distributions of retained edges at each layer, designers could, for example, better understand how well some aggregation scheme integrates information from heterophilic
homophilic neighborhoods. In a similar way, GLAM may be used princi- pled method for assessing the value depth in GNNs, a persistent issue due to the over-smoothing problem (Oono& & Suzuki 2019). If GNN layer were tion of structural information, iee. the number of retained edges yielded by its preceding GLAM layer was close to zero, then the GNN may be too deep, and adding additional layers may introduce complexity without increasing performance.
longer benefit from the incorpora-
REPRODUCIBILITY
All code, data and configuration scripts are available in [GitHub redacted for review]. Our models were built using the open source PyTorch Geometric library (Fey & Lenssen 2019) and we provide setup scripts configure Anaconda environment that contains all necessary packages. All hyper- parameters and the training methodology are clearly documented in the code and the benchmarks runnable on CPU or GPU with single command.
8

---

Under review as a conference paper at ICLR 2023
REFERENCES
Yu Chen, Lingfei Wu, and Mohammed J Zaki. Iterative deep graph learning for graph neural net- works: Better and robust node embeddings. June 2020.
R Doyle, K Simons, H Qian, and D Baker. Local interactions and the optimization of protein folding. Proteins, 29(3):282-22 2912, November 1997.
Xiaomin Fang, Lihang Liu, Jieqiong Lei, Donglong He, Shanzhuo Zhang, Jingbo Zhou, Fan Wang, Hua Wu, and Haifeng Wang. Geometry-eehanneed molecular representation learning for property prediction. Nature Machine Intelligence, 4(2): 127-134, February 2022.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric, In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks, In Kamalika Chaudhuri and Ruslan Salakbutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pp. 1972-1982. PMLR, 2019.
Lee Giles, Kurt D Bollacker, and Steve Lawrence. CiteScer: automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, DL '98, pp. 89-98, New York, NY, USA, May 1998. Association for Computing Machinery.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparamcterization with Gumbel-Softmax. November 2016.
F Jiang, T Chen, and B Zheng. Structure local interactions in complex financial dynamics. Scientific reports, 4:5321, June 2014.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. ICLR, 2014.
Thomas Kipf, Ethan Fetaya, Kuan-Chiel Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. Proceedings of the 35th International Conference on Machine Learning, February 2018.
Thomas N Kipf and Max Welling. Sunii-upervised classification with graph convolutional net- works. September 2016.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang- Learning drop: Robust graph neural network via topological denoising. November 2020.
Jaideep Mathur. Local interactions shape plant cells. Current opinion in cell biology, 18(1):40-46 February 2006.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information retrieval, 3(2): July 2000.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-44) 444, August 2001.
Siqi Miao, Miaoyuan Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. January 2022.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. ICLR, 2019.
Onur Özgür. Local interactions. In Jess Benhabib, Alberto Bisin, and Matthew O Jackson (eds.), Handbook of Social Economics, volume pp. 587-644. North-Holland, January 2011.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Ran -ad.. Collective classification in network data. Al Magazine, 29(3):93-93, September 2008.

---

Under review as a conference paper at ICLR 2023
Chao Shang, Jie Chen, and Jinbo Bi. Discrete graph structure learning for forecasting multiple time series. January 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. ArXiv, 2018.
Rob Stocker, Herbert Jelinek, and Bohdan Durnota. Complex Systems: From Local Interactions to Global Phenomena. IOS Press, 1996.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. June 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. October 2017.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. October 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. A comprehensive survey graph neural networks. January 2019.
Yang Ye and Shihao Ji. Sparse graph attention networks. IEEE transactions knowledge and data engineering, pp. 1-1, 2021.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. September 2020.
10


Reviews:
[{"review_id": "eMIkuNtZzh", "reviewer": "Reviewer_7cxi", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work aims to tackle the challenges of noisy edges in graph learning problems. It first points out the finding that the demands of structure learning and node embedding are inherently conflicting with each other, so it is not proper to optimize both jointly.  Then, based on their finding, they propose the Graph Learning Attention Mechanism （GLAM） layer, which is a non-heuristic differentiable network layer that can be inserted into existing GNN models and can focus on the graph structure learning objective to learn a task-informed graph structure and benefit the graph learning. ", "summary_of_the_review": "This is a well-motivated work focusing on how to separate the structure learning and node embedding task to best solve the graph learning problems. Though the writing is clear and the explored topic is meaningful, I have major concerns about the method evaluation. First, it is not compared with comprehensive suitable baselines, and the benefit of the proposed method is not distinctive; second, the authors only provide one simple experimental result (in table 2), and no ablation studies are provided to examine the GLAM method comprehensively; another minor point is, neither the code link nor details of the experimental set-up are provided.", "strength_and_weaknesses": "Strength:\n1. This work is clearly motivated, and the studied topic is meaningful.\n2. The writing of this work is easy-to-follow.\n\nWeakness:\n1. Model Evaluation\n1) The proposed GLAM is only examined with 3 baselines, which I think is not enough. \n- The authors mentioned that \"GSAT was not evaluated on our datasets\", I am wondering why GSAT is excluded.\n- I think it would be better if the authors can also compare with more challenging baselines, especially some SOTA models on structure learning.\n2) no ablation study is provided to examine the GLAM method comprehensively, for some examples, I am curious about the following aspects:\n- is it necessary to apply a GLAM layer before every GNN layer? \n- the authors claim that the GLAM can be incorporated with various GNN backbones, however, only an example with GAT is provided. I am curious to see how GLAM performs on other GNN models, such as GCN.\n\n2. Reproducibility\n- Though the authors provide the section to clarify the reproducibility and the experimental set-up details claimed to be provided in the code, the code link is missing. So essentially no useful information is provided in the paper, which makes the reproducibility fair.\n\n\nSome questions:\n1. In equations (5) and (6), what is the major benefit of adding the noise term u? is it for the Gumble softmax trick for differentiability?\n2. if we apply GAT after GLAM, it seems to me that we are still jointly considering the structure learning and node embedding tasks simultaneously as the model still uses the weight on each edge learned by GAT for message passing. Does it contradict the claim that these two objectives should be considered separately?\n3. It looks to me that, the major drawback of GAT is the softmax which expresses the neighbors' importance relatively to other nodes. Then, does it mean, as long as we come up with a way to get rid of this softmax, the limitation can be solved? \n4. In section 5, I don't quite understand, why it would be problematic to add penalties on retained edges?\n5. In section 6.2, the authors claims one of the benefits of GLAM is sparsification, I am wondering, is this sparsification mainly for efficiency purpose? If so, then how much speed/memory improvement can this sparsification bring to GAT? If not, then why is sparsification important here?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NeG0pIoz9mN", "reviewer": "Reviewer_jLy4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work presents a graph structure refinement layer named GLAM based on a neighborhood attention schema slightly different from the Softmax attention, which disentangles the optimization of node embeddings and graph structures. The proposed GLAM layer learns more sparse subgraphs than prior arts by giving the known adjacency matrix.", "summary_of_the_review": "Following my comment above, there are several questions:\n\n- What are the exact conflicts between the learning of graph structures and node embeddings? Specifically, in Sec. 3, I have these questions: (1) What are the roles of the permutation invariant aggregator in hindering the use of $\\alpha_{ij}$ as the bases of structure learning? (2) I partially agree with your analysis about the Softmax attention, but how to get your conclusion of “For these reasons, …, we should not do away with the Softmax activation to normalize attention coefficients…”? (3) I cannot see your principled analysis to answer why it is not desired to learn edge weights together with node embeddings, e.g., how do you estimate the noisy evolution of local neighbourhoods, and why the improvements over GAT are less significant if your conjectures hold?\n\n- I notice the authors mentioned graph sparsity several times, especially in Sec. 6, but there is no experiment to discuss the consequent benefits, e.g., efficiency and scalability. Have you evaluated the proposal on some larger real-world graphs, e.g., OGB datasets?\n", "strength_and_weaknesses": "Pros:\n- The insight of the addressing the conflicts between structure learning and node embedding optimization is interesting\n- Simplicity of the methodology\n- The paper is well written and easy to follow despite some confusing points\n\nCons:\n- Lack of a more principled motivations and justifications behind the proposed design\n- Limited evaluation setup\n- Limited technical novelty\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EPycoifTdy9", "reviewer": "Reviewer_aSBH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses issues of GNN sensitivity to graph structures. Specifically how noisy edges degrade performance which cannot be mitigated without complete removal. This paper proposed a novel layer Graph Learning Attention Mechanism (GLAM) which isolates structure learning from node embeddings. This technique does not require using costly exogenous structural regularizers or edge-selection heuristics to learn optimal graph structures. Experiments on benchmark datasets including Cora, PubMed, Citeseer, Amazon Photo, and Amazon Computers show comparable classification performance with significantly higher sparsity in structure.", "summary_of_the_review": "The work in this paper is good with promising results in an interesting direction beyond plainly increasing prediction accuracy on benchmark datasets. Additional work may be needed to expand upon this research for publication. ", "strength_and_weaknesses": "The experiments indicate the GLAM layer when applied achieves comparable prediction accuracies to state-of-the-art methods on benchmark datasets but with a significantly sparser graph structure. \n\nSince the experiments do not show great improvement in prediction accuracies on benchmark datasets, the justification for using this method would rely on applications that can take full advantage of the edge removal capabilities in this paper.\n\nFuture experiments can uncover the reasoning behind the drastic differences in the number of removed edges between the first and second GLAM layers. \n\nDuring experiments, each dataset has a drastically different % of edges removed during training. Further research may be able to explain this occurrence.\n\nDetermining cutoffs for low homophily thresholds for usable datasets can open the door for applications to more diverse datasets and applications.\n\nDoes the GLAM layer offer any runtime benefits during training?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8th6g7kuia", "reviewer": "Reviewer_BqHK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a topology optimization method for message passing-based graph learning models, termed Graph Learning Attention Mechanism (GLAM). The proposed model is differentiable and removes edges in an end-to-end manner. The method can be integrated into GCN and GAT. The experimental results show the proposed GLAM can improve the performance of GCNs.", "summary_of_the_review": "I recommend a weak reject because of the weak motivation and validation.", "strength_and_weaknesses": "Strengths,\n\nS1: The proposed topology optimization method is differentiable;\n\nS2: This paper studies an interesting problem;\n\nS3: This paper is well-written.\n\nWeaknesses,\n\nW1: There is a lack of evidence to support the analysis of the conflations in Section 3, which weakens the motivation of this paper.\n\nW2: Topology optimization is not new in graph learning, especially edge movement.\n\nW3: The improvement from GLAM seems limited in experiments. And the empirical support for the effectiveness of GLAM is weak.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject