PATCHY-SAN

Context:
- It was first introduced by Niepert et al. (2016).
Example(s):
- that described in Niepert et al. (2016).
- …
Counter-Example(s):
See: Recurrent Neural Network, Feedforward Neural Network, Attention Mechanism.

References

(Wu et al., 2020) ⇒ Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu (2020). "A Comprehensive Survey on Graph Neural Networks". In: IEEE transactions on neural networks and learning systems, 32(1), 4-24.
- QUOTE: Another distinct line of works achieve weight sharing across different locations by ranking a node's neighbors based on certain criteria and associating each ranking with a learnable weight. PATCHY-SAN (Niepert et al., 2016) orders neighbors of each node according to their graph labelings and selects the top q neighbors. Graph labelings are essentially node scores which can be derived by node degree, centrality, and WeisfeilerLehman color (...). As each node now has a fixed number of ordered neighbors, graph-structured data can be converted into grid-structured data. PATCHY-SAN applies a standard 1D convolutional filter to aggregate neighborhood feature information where the order of the filter’s weights corresponds to the order of a node’s neighbors. The ranking criterion of PATCHY-SAN only considers graph structures, which requires heavy computation for data processing.

(Zhang et al., 2019) ⇒ Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski (2019). "Graph convolutional networks: a comprehensive review". In: Computational Social Networks, 6(1), 1-23.
- QUOTE: The proposed PATCHY-SAN model first determines the nodes ordering by a given graph labeling approach such as centrality-based methods (e.g., degree, PageRank, betweenness, etc.) and selects a fixed-length sequence of nodes. Second, to address the issue of arbitrary neighborhood size of nodes, a fixed-size neighborhood for each node is constructed. Finally, the neighborhood graph is normalized according to graph labeling procedures, so that nodes of similar structural roles are assigned similar relative positions, followed by the representation learning with classic CNNs. However, as the spatial order of nodes is determined by the given graph labeling approach that is often solely based on graph structure, PATCHY-SAN lacks the learning flexibility and generality to a broader range of applications.

(Niepert et al., 2016) ⇒ Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov (2016). "Learning Convolutional Neural Networks for Graphs" In: Proceedings of The 33rd International Conference on Machine Learning (PMLR 2016).
- QUOTE: The proposed approach, termed PATCHY-SAN, addresses these two problems for arbitrary graphs. For each input graph, it first determines nodes (and their order) for which neighborhood graphs are created. For each of these nodes, a neighborhood consisting of exactly $k$ nodes is extracted and normalized, that is, it is uniquely mapped to a space with a fixed linear order. The normalized neighborhood serves as the receptive field for a node under consideration. Finally, feature learning components such as convolutional and dense layers are combined with the normalized neighborhood graphs as the CNN's receptive fields.
  Figure 2 illustrates the PATCHY-SAN architecture (...)

**Figure 2:** An illustration of the proposed architecture. A node sequence is selected from a graph via a graph labeling procedure. For some nodes in the sequence, a local neighborhood graph is assembled and normalized. The normalized neighborhoods are used as receptive fields and combined with existing CNN components.