– Information about the non euclidean space incorporated – 2D conversion of image as input vs 3D image as input – Ideas about no connectivity in cases of pixels – Atoms, molecules, SMILE notation, what it leaves behind is the actual structural information – Nodes, edges, labels, attributes, rule(function that gives another node from one node) – Static and dynamic graphs will have different ways – Graph embedding: process of representing graphs vectorically with lower dimensions with as low information loss as possible – Adjacency Matrix are mostly used. – Laplcian matrix = Degree - adjacency matrix – Generally all three types of matrices are used in many of the approaches. – Degree Matrix are diagonal matrices with the value of degree along the diagonal. – In case of undirected graphs, the no of connections is the degree. – In case of directed graphs, degree is either out degree or in degree – In case of weighted graphs, it is the sum of weights on all nodes – Node level, Sub graph level embeddings

– Graph Embedding Techniques:

– Deepwalk: uses concept of walk as embedding process

-- walk: traversal of graph by moving from one node to another as long as they have common edge
-- Traversal can be represented by having one node representation after other and continue the chain.
-- Similar to word vectors: inputs can be splits of the sequence of such giant representation of walk.
-- Now, the probability of having some node as output given the total representation is computed.
-- Instead of running along word corpus, the graph network instead runs across graphs
-- Operation is similar to Word2Vec
-- Problem: Whenever a new node is added, the network must be retrained again to incorporate it's info.

– Node2Vec – If you turn each node in a graph into an embedding as you would words in sentence, a neural network can learn representations for each node. – The difference between Node2vec and DeepWalk is subtle but significant. Node2vec features a walk bias variable α(alpha), which is parameterized by p and q. The parameter p prioritizes a breadth-first-search (BFS) procedure, while the parameter q prioritizes a depth-first-search (DFS) procedure. The decision of where to walk next is therefore influenced by probabilities 1/p or 1/q. – BFS is ideal for learning local neighbors, while DFS is better for learning global variables. – BFS is better at classifying according to structural roles (hubs, bridges, outliers, etc.) while DFS returns a more community driven classification scheme. – Graph2Vec – Using an analogy with word2vec, if a document is made of sentences (which is then made of words), then a graph is made of sub-graphs (which is then made of nodes). – We use the sub graph embedding in this process. – Similar to word embedding vector computation, it utilizes similar formula for subgraph embedding vector.

– SDNE: – Not just learn from walks but tries to learn from two different metrics: – 1st order proximity: nodes said to be similar if they share an edge – 2nd order: if they share many neighboring nodes – Goal: to capture highly non linear structure – This is achieved by using deep autoencoders (semi-supervised) to preserve the first order (supervised) and second order (unsupervised) network proximities. – Laplacian Eigenmaps: to preserve first order proximity – Laplacian Eigenmap embedding algorithm applies a penalty when similar nodes are mapped far from each other in the embedded space, thus allowing for optimization by minimizing the space between similar nodes. – The second order proximity is preserved by passing the adjacency matrix of the graph through an unsupervised autoencoder which has a built in reconstruction loss function it must minimize. – Together, these two losses are used to train a proper embedding for the graph data.

– LINE: Large scale Network Embedding – Explicitly define two functions for 1st and 2nd order proximity. – EMpirically,found that the 2nd order proximity performed better and improved accuracy. – Goal: to decrease KL divergence between the input and the embedding distributions – Since the algorithm has to define new functions for each increasing order of proximity, LINE doesn’t perform very well if the application needs an understanding of node community structure.

– HARP: – Previous models risked getting stuck in local optima since their objective functions are non-convex. – Graph coarsening to make similar nodes into super nodes – After coarsening the graph, it then generates an embedding of the coarsest “supernode”, followed by an embedding of the entire graph (which itself is made of supernodes). – As a preprocessing step rather than a solution: can be used with other techniques.

– Graph Convolutions:

– What is inductive bias ? – Inductive bias of a learning algorithm is the set of assumptions that the learner uses to predict outputs given inputs that it has not encountered. – Neural Networks tend to discard the features that have very less significance in task at hand. – Similary, GNNs have bias: By structuring the data in a way that prioritizes certain patterns, we can improve model performance, even if the data is the same. – Graphs are more abstract, and variables like node degree, proximity, and neighborhood structure provide far more information about the data

– Convolutions are basically pooling, kernels and strides. As like in euclidean space, where we have notion of left right, and so on ; we can’t use such concepts in graphs due to their irregular structure.

– So, to perform convolution; we need to start from what convolution means so that we can mimic the process At a high level, convolutions aggregate information from surrounding or adjacent entities. Convolutions in Deep Learning take this aggregated information to build feature maps (the grid values), which are used to make predictions with a neural network. We want to do this on graphs.

– Now we know what are we trying to do. So, we need a method to do this now. – Spatial and Spectral methods: One that requires Eigen and another that doesn’take

– Graph Signal Processing: – Spectral Graph Convolutional Network: – GSP is the key to generalizing convolutions, allowing us to build functions that can take into account both the overall structure of the graph and the individual properties of the graph’s components.

– It is the graph fourier transform that allows one to introduce the notion of a “bandwidth” or “smoothness” to a graph – In GCNs, node features and attributes are represented by “signals”. – Calculating the eigenvectors of the Laplacian, returns the Fourier basis for the graph.

So, steps in Graph Signal Processing are as follows: So the overall steps are:

– Transform the graph into the spectral domain using eigendecomposition – Apply eigendecomposition to the specified kernel – Multiply the spectral graph and spectral kernel (like vanilla convolutions) – Return results in the original spatial domain (analogous to inverse GFT)

– ChebNets: – Spectral convolutions are defined as the multiplication of a signal (node features/attributes) by a kernel. – Thus similar to original convolution operation – The kernel used in a spectral convolution made of Chebyshev polynomials of the diagonal matrix of Laplacian eigenvalues – The kernel equals the sum of all Chebyshev polynomial kernels applied to the diagonal matrix of scaled Laplacian eigenvalues for each order of k up to K-1. – Using graph coarsening, it also introduced pooling methods similar to original convolution. – ChebNet implicitly avoids computing the eigendomposition opting to approximate it instead. – GCNs are basically first order ChebNets. – In GCNs, this is intended to alleviate the risk of overfitting on a local neighborhood of a graph. – GCNs performed well in node classification tasks and other graph applications, but the main drawback is how eigenvalues tend to cluster together in a very small range, with large gaps in between each cluster. – The problem of such GCNS was later solved by Cayleynets.

– Fast GCNs/ SGCs – The kernel is defined in Fourier space and graph Fourier transforms are notoriously expensive to compute. – O(N²) operation for a graph with N nodes: the multiplication operation for i/p nodes and eigenvec of graph’s laplacian. – Thus as a solution to the computational complexity introduced by it, Monte Carlo (biased random sampling method) approaches to consistently estimate the integrals, which allowed for batch training, reducing the overall training time. – We hypothesize that the nonlinearity between GCN layers is not critical — but that the majority of the benefit arises from the local averaging. –IBM paper on Fast GCN – The project removed the nonlinear transition functions between each convolutional layer. The final softmax activation allowed for probabilistic outputs that can be optimized with stochastic gradient descent.

– Cayley Nets: – Cayley Transform: Unit half circle transform – useful notion of localization – Cayley has proven to perform better on a wide range of Graph Learning tasks due to their ability to detect narrow frequency bands of importance during training, and to specialize on them while being well-localized on the graph.

– Motifs: – Essentially, the mode partitions input graphs into motifs which are unique substructures of x length, such that any graph in the dataset can be built by some combination of the motifs. – The motifs take into directionality of edges into consideration, a detail in graph theory that has been omitted in previous graph learning approaches. – Each convolutional layer of a MotifNet has a multivariate matrix polynomial (a fancy kernel where each element is a polynomial with multiple variables), which is applied to and learns from the motif’s Laplacian matrices.

– Spatial Convolutional Networks – GraphSage: – It is especially powerful because it scales well with large, dense, homogenous, dynamic networks – Stages: – Neighborhood Sampling: Takes param ‘k’ to define depth – Search neighbors of neighbors – Aggregation: Bring together properties of neighboring node to the target node – Types: – Mean : mean of all node’s features – LSTM : random out of the nodes – Max pooling: Only the best feature from experiments – Prediction: – Based on a neural network , using the aggregated values , perform node classification or context determination. – This 3 step process repeated for all the nodes in the graph. – Being used by Pinterest as PinSage. – Pooling performed best and computationally also simpler than others.

– MoNets: – Base of research such as Spline CNNs, Geodesic, Anisotropic CNNs etc. – Contributions: – A generalization of various Graph Learning approaches, unifying spatial and spectral approaches – A new approach using parametric kernels, pseudo-coordinates, integrated with existing models (Anistropic CNN, Geodesic CNN,) – A series of experiments performed on different benchmark manifolds, graphs, and networks – MoNet’s generalization first considers variable x as a point in the manifold or node in a graph depending on the application, task, and input. Variables y is considered the neighboring nodes or points, which is associated with a vector of pseudo-coordinates in d-dimensional space, such that u(x, y) are the pseudo-coordinates of which there is a unique set for each neighbor of x. – Each pseudo-coordinate is put through a weighting function, which replicates the effect of a traditional image convolution kernel whereby each value of the kernel is multiplied by the value that is currently in consideration. In the case of MoNet, the weighting function is a kernel with learnable parameters that operates on the pseudo-coordinates:

– we will have covariance matrix of order ’d’ by ’d’ and mean vector of order 1 by ’d’ for the kernel. – patch operator weighting functions (fancy way of saying kernel) used in different convolutional operations on the manifold. ( the heatmap figure of 3d models) – This kernel is learned only in MoNet, versus hard-coded in GCNNs and ACNNs. The first thing one might notice is how much “smoother” the weights (red curves) are in MoNet, versus the more distinct (GCNN) and more integrated (ACNN) weights of the other approaches. – This flexibility is part of the reason why both allow for the sharing of parameters cross-dataset. This opens up the capacity for ideas like Transfer Learning to be applied to the geometric domain.

– Spectral convolutions are mathematically as well as theoretically similar to their vanilla convolution counterparts whereas spatial convolutions are conceptually as well as markedly similar to vanilla convolutions.