Social media have become the main platforms for expressing and supplementing nuanced human activity such as engaging in public and private conversations, creating and sharing multimedia content, participating to digital culture events, and recently describing emotions about events, places, or even products. In this survey, we provide a comprehensive overview of graph mining and machine learning on afective social media through graph neural networks (GNNs). The latter are capable of performing a variety of tasks, such as graph and vertex classification, link prediction, and graph clustering using vertex information, edge information, and topological structure. These capabilities are critical in harnessing the vast emotional information available in social media in order to generate meaningful and scalable afective analytics. graph neural networks, distributed computation, graph mining, graph convolution, network topology, convergence, link prediction, label prediction, community discovery, afective computing, PyTorch, ∗Corresponding author.
Currently social media are widely considered to be the digital reflection, or even the digital twin in certain cases, class of neural network architectures depending strongly on information propagation mechanisms such as message passing between graph nodes or attention functions between network layers to encapsulate the higher order tion found in social media are afective indicators such of individuals and groups. Among the prime informa- communication flow and interplay inherent in graphs. Although their functionality may resemble that of other as the emotional polarity of posts or reactions to them. architectures like the established multilayer perceptrons This is especially true in Twitter which abounds with long conversations full with emotionally charged replies [1][2], whereas Facebook [3] and LinkedIn [4][5] have dedicated emotional reaction buttons for each post. Even Instagram contains images which have been reported to elicit emotional responses [6].
Typically, in deep learning applications, such as fraud detection, natural language processing (NLP), biomedical image processing, and computer vision, the datasets are represented as manifolds in the Euclidean space. However, recently the number of engineering scenarios requiring non-Euclidean data and instead rely on graphs has been rising. Therein topological relations and interconnectivity play a major role. Graphs enable the modeling of important problems in various scientific fields including complex systems, social networks, protein-protein interaction networks, logistics and long supply chains, transportation networks, knowledge graphs, and others.
CIKM’22: 31st ACM International Conference on Information and (S. Sioutas) diag [ 1,1, … , , ]
× identity matrix
Eq. (1) Eq. (4) Eq. (8) Eq. (1) Eq. (1) Eq. (2)
section 2 the recent scientific literature regarding GNNs, afective social media, and graph mining is overviewed.
Then in section 3 the primary properties of GNNs are enu© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License merated in detail, whereas in section 4 the applications of CEUR htp:/ceur-ws.org ISN1613-073
CEUR
Workshop Proceedings (CEUR-WS.org)
Future research directions are given in section 5. Capital boldface letters denote matrices, small boldface vectors, and normal small scalars. Acronyms are explained the ifrst time they are encountered in the text. Additionally, the terms vertex and node are used interchangeably in this work. The same holds true for the terms edge and link. In function definitions parameters follow the respective arguments after a semicolon. Finally, in table 1 the notation used in this work is summarized.
As stated earlier GNNs are neural networks tailored for
natively handling graphs or any kind of linked data for
that matter [7]. Techniques for doing so include graph
embedding [8], message passing [9], and attention
mechanisms [10], the latter primarily in the form of graph
attention networks (GATs) [11]. The current state of
the art in GNNs allows them to perform link prediction
[12], graph convolution [
Neural network architectures are ubiquitous in ML
[28, 29], especially in conjunction with low rank tensor
approximation [30], and signal processing [31]. Bayesian
neural networks stem directly from non-classical signal
estimation theory [32]. Convolutional neural networks
(CNNs) are extensively used in image processing [
Graph mining aims at locating and extracting latent
and non-trivial knowledge from graphs such as cycle
lengths in massive graphs [41], higher order
spatiotemporal patterns [42], and triangles [43]. Techniques include
employing intelligent agents for autonomous mining
[44], approximating directed graphs with undirected ones
based on enegry criteria [45], managing graph streams
with relational algebra [46], computing graph topological
correlation [47], eficiently inferring graph isomorphism
[
Social network analysis, although it relies heavily on
graph mining [
3.2. GNN Tasks Typically, every application for afective social media fits into one of the following basic tasks: • Node classification: The goal is to predict missing node labels in a social network using the labels of the neighbor nodes. For example, the emotional state of a user can be predicted as a function of the attributes of that user and of its neighbours. • Link prediction: In this scenario the objective is to predict the link between various entities in a network by utilizing a partial or otherwise incom- There are two diferent types of graph convolution plete adjacency matrix. This task is frequently operations, which in turn determine the domain a given used in social network settings because it can pre- GCN is defined on: dict whether any two vertices, which may well be accounts, pages, or even entire communities, • Spatial convolution: These GCNs operate diare likely to be connected. Moreover, in certain rectly on the graph adjacency matrix as if were a cases and depending on the available features, the grid but with additional constraints. Thus, constrength of this link may be estimated as well. volution is performed in a way similar to images by using spatial features learned from the graph. • Community detection: The case here is to allo- This is the equivalent to the time domain filtering. cate nodes into clusters whose size is unknown beforehand, namely it is a clustering problem. This • eSipgeecntdreaclocmopnovsoiltiuotnioonf:thTehegsreapGhCLNaspluatciliiazne mthaecan be done by partitioning the vertex sex based trix in order to propagate information across on edge features like weights or, alternatively, nodes. Therefore, processing takes place in the by viewing the nodes as items and by grouping two-dimensional spatial frequency domain akin together items with comparable properties. For to the transform domain adaptive algorithms. instance, community detection can be used on afective social media analysis to locate communities with similar emotional characteristics.
defined based on the graph degree matrix of equation (1). Observe that nodes of zero degree essentially do not contribute to the overall graph structure and thus are considered to have been removed during a preprocessing stage. Therefore, matrix D is always invertible.
D =△ diag [deg ( 1), … , deg ( )] (1)
then be constructed from the respective adjacency matrix A as shown in equation (2). The eigenexpansion of L is the graph spectrum on the corresponding basis.
△ L = I − D−1A (2) 3.3. Architectures GNNs constitute a class of neural networks based on the dependence between the elements of the graph. The term GNN does not refer to a single algorithm or architecture but rather to a plethora of distinct algorithms. The common denominator for each GNN is the ability to exploit the information inherent in graph topology in order to compute a global steady state. This is more evident in the message passing architectures, but this can also be seen in some other of the most common GNN architectures that have been developed in recent years like graph convolutional networks (GCNs) and graph attention networks (GATs). In table 2 the architectures examined here and their main properties are presented.
representations and act as convolutional filters for graph classification with considerable accuracy, they fail to utilize feature locality commonly found in most graphs. Ad3.3.1. Graph Convolutional Networks ditionally, spectral GCNs come with great computational Graph convolutional networks (GCNs), which seek to cost, especially for large networks. imitate the functionality of ordinary CNNs, are currently In order to address the issues of locality and computathe prime candidate architectures for most real life ap- tional complexity, ChebNets were developed in order to plications. Specifically, the main idea behind GCNs is combine CNNs with the spectral networks theory. Thus, to adapt CNNs to natively handle linked data, namely in ChebNets the representation of any feature vector graphs. CNNs in order to create highly expressive repre- should only be influenced by the -hop neighbors. Theresentations can extract multiscale localized spatial infor- fore, ChebNets provide the essential algorithmic founmation and combine it in order to yield the final result. In dation and efective schemes since the convolution is this sense, they exploit the higher order patterns inherent computed using Chebyshev polynomials instead of the in graphs. Since CNNs are able to capture meaningful eigenvectors of the Laplacian matrix. Therefore, spectral features across the entire data sets, GCNs adjust the oper- GCNs can be considered as ChebNets where the neighation of convolution from grid data to graph data. Graph borhood depth equals one. The objective of this model is convolution uses the features of the neighbors of a given to learn a function of features which operates on a graph node to make predictions by transforming the features of represented as in equation (3): taontordaienina faulnactetinotnspoafcfeea.tTuhreesoobnjeactgivraepfhorwthheesree mthoedienlpsuist =△ ( , ) (3) is a set of nodes and edges which are described from a feature vector that contains their attributes.
and is the number of vertices. Said matrix is iteratively constructed given the following graph input.
• Feature description vectors, one for each of the nodes, are stacked are form a × feature matrix where denotes the number of features. • The × graph adjacency matrix. Therein are contained all local patterns and its powers encode all higher order ones.
Each network layer has a nonlinear function which acts as the ChebNet propagation rule. Based in the choice of the propagation rule and the numbers this is successively applied models may vary. The most common propagation rule is ReLU operating on a linear combination of the outputs of the previous layers. The features processed at each layer are aggregated to form the attributes of the following layer. This implies that each node in the -th layer will collect information from their -hop neighbors. It has been observed that a small number of layers, typically at most four, sufices.
Since in this model the aggregated representation of each vertex includes only local features, namely those of its neighbors, this has to be taken into consideration in the structure of the adjacency matrix. This is done in two ways, by adding the identity matrix to it to allow the construction of its powers and also by normalizing it similarly to the graph Laplacian of (2). So when GCNs and ChebNets are trained by stochastic gradient descent algorithms, which tend to be sensitive to the scale of input features, there are no vanishing or exploding gradients which frequently delay or even derail training.
It should be also mentioned that GCNs are mainly used for semi-supervised node classification, whether binary or multi-class by adding a softmax layer at the end. Also by combining graph convolution layers with graph pooling layers the GCN model will be able to predict the class labels for an entire graph. 3.3.2. Graph Attention Networks Analogous to GCNs, GATs average hidden attributes on a local level. But unlike GCN, which compute the propagation weights explicitly during training, GATs define them implicitly. This is accomplished by the attention mechanism, namely a learnable function to re-weight synapses between neurons as a function of the values of the hidden features. In this way, the significance of each node can be specified by utilizing more information than the structure of the graph and the connectivity patterns contained in the latter. However, this local aggregation has to be eventually compensated for when values are propagated to other layers and this is in fact one of the factors diferentiating GATs.
In particular, the synaptic weights are computed as a result of an attention mechanism which computes the 1–10 normalised coeficients from the unnormalized ones. Typically, the softmax function is the key to normalizing these coeficients as it can convert a set of raw scores to an exponentially weighted distribution. 3.3.3. Message Passing Neural Networks Message passing neural networks (MPNNs) are decentralized architectures which rely heavily on message passing in order to perform a given computation. Such communication may take place synchronously or asynchronously. Each node starts with a local ground truth vector and progressively based on input from neighboring vertices evolves into a steady state vector. Although initially the information exchanged between vertices may be inaccurate, this is remedied at later stages, provided the update mechanisms are designed to do so. This is by no means a trivial task as essentially this is a decentralized nonlinear control problem. Therefore, extended care must be taken beforehand in order to avoid efects such as Witsenhausen’s counterexample [73].
In contrast to other neural network architectures, MPNNs have a flat architecture in the sense that there are no layers. This implies that the diameter of the network plays a crucial role as it represents the maximum amount of time, measured in the number of hops, which is necessary in order for a given piece of information to be transmitted across the MPNN. Related metrics such as the efective diameter reveal the links necessary for a considerable segment of the graph to be reached. Strong locality, expressed in the number of triangles or equivalently in the clustering coeficient, contributes to quick propagation. On the contrary, bridges may be congestion points. In any case, topology is central in MPNNs and its efects are more intense compared to other GNN types.
In table 2 are listed some of the most representative convergence schemes proposed in the bibliography. 3.4. Convergence 3.4.1. State Vectors Convergence is a major topic since GNNs are distributed and, hence, there is not a single point of centralized control. As such, various techniques based on traditional control equations such as those describing continuous, linear, and time invariant systems as in equation (4) do MPNNs which employ with proper scaling the sigmoid not directly apply. Therein A is the system plant, b is the or hyperbolic function as activation function as shown input distribution vector, and x is the state vector. in equation (8). ẋ =△ Ax + b,
A ∈ ℝ× , b ∈ ℝ×1 3.4.2. Brower’s Fixed Point Lemma For most message passing architectures an alternative methodology to monitor convergence lies in the Brower’s ifxed point lemma (BFPL). The latter states that any conat least one fixed point 0 ∈ 0 as shown in (7). tinuous function (⋅) mapping any interval 0 to itself has 0 = ( 0), ∶ 0 → 0 (7)
The existence of the fixed point 0 guarantees that the MPNN cannot escape from it and as such it is in one of the potentially many steady states. However, that requires that a significant number of neurons reach that state before they start propagating it to their neighbors. Moreover, methodologies based on the BFPL are considered to be indirect in the sense that they monitor the output of Therefore, the global convergence is tracked through individual vertices. Still, they have been applied successfully, especially when the processing involves smooth functions, in cases where the local computation is yields a single scalar. For instance, BFPL has been applied to (4) (5) (6)
vergence, since it determines the average and maximum rate of spatial information propagation in terms of the number of links between any two processing vertices.
each node and not their internal state vector s as before. than one definition of what makes a community as this community discovery. Moreover, since this task relies on higher order patterns, it is also computationally challenging. Consequently, a number of diverse heuristics have been developed for it.
Message passing mechanisms are crucial in most engineering scenarios involving graphs, even indirectly since most networks are set up in order to achieve coherency and communication. Especially in MPNNs selecting the attributes represented in the ground truth vector of each vertex is of paramount importance since that determines what is exchanged during communication. A static snapshot of message passing is shown in figure 2.
each vertex is assigned one out of many possible labels drawn out of a finite label set based on a decision rule. This functionality is shown in figure 3. Labels may be repeated and, depending on the problem, some vertices may already have a label. Moreover, this task has close ties with the community discovery task, although in classification nonadjacent nodes may have the same label. More recently ML models which can utilize structural and functional attributes, whenever the latter are available, have been proposed in the literature. It should be noted though that functional features depend heavily on the underlying domain, whereas structural attributes can be applied to any scenario.
Graph convolution is an operation involving a pair of graphs and yields a larger one whose topology depends on theirs. This allows the eficient discovery of local patterns and, depending on how convolution is defined, even their variants or incomplete ones. This operation initially appeared in the field of computer vision and has found numerous applications in social media analysis and ML. Figure 4 shows an instance of this operation.
Finally in figure 5 the task of link prediction task is shown. It is an important task where given a partial graph or an evolving one and a decision rule must be devised which can predict whether a link between any two given nodes exists. In order to determine whether such link should be added to the graph, a segment of the graph considered as ground truth is used along with the assumption that scale free graphs exhibit self-similarity in many levels. Alternatively, state vectors in every vertex or structural patterns may be used to train an ML model. Either case may require a considerable amount
of computational resources, depending on the algorithm. tive communities in case of a bridge, it also depends on its functionality. As such, in addition to node classification and graph attention analysis pertaining to message 4. Afective Social Media Analysis passing should be employed.
Tracing the emotional efect of a post is more challengAfective computing is a recent field which extends the ing since a number of interconnected instances of the existing knowledge in social network analysis with emo- previous problem should be studied as a post propagates tional attributes and their study. It has already bore fruits through a graph. Moreover, possible variations of or in[5, 4] and its prospects look bright with the advent of tentional modification to the latter should be also taken sophisticated DL techniques such as the GNN architec- into consideration as well as the overall information contures described earlier but also like autoencoders, graph text of the adjacent edges and vertices. Consequently, the adversarial networks (GANs), and CNNs. All these mod- entire route of a post should be analyzed in this case usels operate on a plethora of afective attributes including ing graph convolutions and node classification, whereas among others word length and polarity, number of sen- certain propagation patterns of important posts may be tences, use of punctuation, mentions, and words having explained with link prediction techniques. special meaning such as modifiers, negations, and of con- The afective influence of a node can be considered as a siderable emotional weight. generalization of a potentially nonlinear combination of
As stated above, afective social media analysis places determining the emotional state of a number of vertices emphasis on the emotional state of social media accounts with evaluating the impact of the posts of the node under through their posts as well as through the interactions be- consideration. This happens as influence is frequently tween them. The methodologies most commonly found taken to be a function of the topological properties of its in the scientific literature can be broadly divided into the high order neighborhood and of the emotional potential following categories. Furthermore, in table 4 is shown of its post. In order to evaluate said afective influence, how each of the afective applications presented in this node classification techniques, message passing, and link section can take advantage of the potential ofered by the prediction are frequently employed. learning tasks of GNNs. Finally, afective community discovery is perhaps the
The determination of the afective state of a node or a most challenging of the tasks commonly encountered in group of nodes is paramount as it allows, among others, afective social media analysis since it entails the compufor locating potential starting points for various online tation of various higher order influence metrics. Theredigital campaigns with political, commercial, or social fore, a considerable portion of or even the entire graph topics. Moreover, it determines which sort or messages topology and, depending on the problem perhaps the are appropriate for a given node given its afective state. associated functionality, must be factored in. However, a To this end, a number of node classification techniques or, far more accurate insight into the total network dynammore recently graph attention-based mechanisms, can be ics is obtained. Therefore, approximate analysis of an applied. Given the phenomenon of homophily in social evolving network for a number of steps can take place media stating that nodes with similar behavior eventu- before such a computation can be performed again. ally tend to connect with each other, the neighborhood of the vertex under consideration may as well provide additional afective attributes. 5. Conclusions
In a sense the dual problem of the above is finding out the afective potential of an edge as the latter is primarily This conference paper focuses on a comprehensive prea function of the afective state of its endpoints. How- sentation of a large number of graph neural network ever, since links in a network may accommodate other architectures tailored for performing afective analysis communication needs, for instance that of the respec- on social media. The latter abound with heterogeneous