Social graphs abound with information which can be harnessed for numerous behavioral purposes including online political campaigns, digital marketing operations such as brand loyalty assessment and opinion mining, and determining public sentiment regarding an event. In such scenarios the eficiency of the deployed methods depends critically on three factors, namely the account behavioral model, the social graph topology, and the nature of the information collected. A prime example is Twitter which is especially known for the lively activity and the intense conversations. Here an extensible computational methodology is proposed based on a graph neural network operating on an edge fuzzy graph constructed by a combination of structural, functional, and emotional Twitter attributes. These graphs constitute a strong algorithmic cornerstone for engineering cases where a properly formulated potential or uncertainty functional is linked to each edge. Starting from the ground truth in each individual vertex, the graph neural network progressively computes in an unsupervised manner a global graph state which can in turn be subject to further processing. The results, obtained using as a benchmark a recent similar graph neural network architecture along with two Twitter graphs, are promising.
GNNs operate on irregular domains expressing relation- In order to describe the proposed architecture a few basic ships. Heterogeneous GNN architectures are examined concepts must be first revised or defined. First the class in [1] and representative GNNs designed to complete ver- of edge fuzzy graphs is introduced in definition 1. satile tasks in [2]. Edge labeling is proposed in [3] in the Definition 1 (Edge fuzzy graph). An edge fuzzy context of few-short learning for GNNs. The technique graph is a combinatorial object represented by the ordered of aggregated neural path in conjunction with machine triplet shown in equation (1). learning (ML) tasks is described in [4]. The emotional coherency of Twitter graphs with GNNs is explored in =△ (, , ℎ) (1) [5], whereas in [6] are given guidelines for social recommendation based on GNNs. The elements in (1) have the following meaning:
Graph mining is a mainstay of current ML [7]. In a graph signal processing (GSP) context adjacency matrices • The vertex set . In the context of this work are considered as two-dimensional signals and signal pro- each vertex corresponds to a single Twitter account cessing techniques are then employed to extract patterns through a bijection. of interest [8]. An overview of the connections to deep • The set of fuzzy edges where ⊆ × . The learning are given in [9]. In [10] a tensor stack network connectivity patterns therein reflect the underlying (TSN) is trained to estimate the topological correlation graph dynamics. of graph pairs compressed with the two-dimensional dis- • The functional ℎ : → [0, 1] maps each edge to a crete cosine transform (DCT2), while the same architec- probability drawn from a single distribution. These ture evaluates graph resiliency in [11]. Flow-based GSP result from graph semantics and functionality. is examined in [12]. The basic operations of GSP such as In the general case the digital account behavior for any shifting and sampling are defined in [ 13]. A graph ver- online social network is given in definition 2. sion of the LMS adaptive filtering algorithm is presented in [14]. A versatile and space eficient data structure for Definition 2 (Account behavior). The online behavior persistent graphs is described in [15]. of an account consists of the total peer interaction over all
Behavioral attributes have recently emerged as an inte- possible ways ofered by the given social medium. gral part of many recent computational systems [16]. The connection between behavioral systems and data driven analysis is explored in [17]. Digital trust is a paramount factor for recruiting candidates from LinkedIn [18]. Clustering fMRI images with tensor distances for emotion recognition [19], while gamification strategies are explored in [20]. An overview of behavioral systems is given in [21].
The above definition can be readily extended in the case two or more accounts are connected over multiple social media, expanding thus the interaction potential. However, this is outside the scope of this work.
In this work the online behavior of Twitter accounts has three distinct components, namely the follow relationships, retweet patterns, and emotional polarity with respect to a reference hashtag set. The intuition behind their selection is as follows:
In this section the proposed GNN architecture as well as the notions underlying it are described. • The follow relationships capture the structural aspect of the Twitter graph since they constitute the core of its edges. • The retweet patterns are an integral part of the functionality taking place bridging accounts in a diferent way. • The emotional coherency is a factor evaluating the similarity of sentiments towards selected top• Whether there is a directed follow link from the -th account to the -th one denoted by the binary tal fact that edges are fuzzy, namely that they belong to The proposed GNN architecture relies on the fundamen- , , and express the relative contribution of each term and in our experiments follow the semantic strength Account behavior Retweet patterns Follow patterns
Emotional polarity
However, it should be noted that for larger benchmark graphs or for dynamic ones alternative criteria should be sought in order to avoid the overwhelming complexity of determining a vertex cover. 3.2. Architecture (2) (3) the graph with a certain probability which in the general case depends on an attribute set. The latter is frequently strictly local or a function of a small neighborhood and rarely global since updating such a set is costly and prone to dependency bottlenecks. In the context of this conference paper the probability , for edge , between vertices and is computed as in equation (4): prob {, } =△ , = , + In (4) three factors are taken into consideration:
, + , (4) indicator , . • The ratio of the number , of retweets of the -th account coming from the -th one to the total retweets in the graph. • The signed correlation factor , expressing the emotional coherency of the -th and -th accounts with respect to the reference hashtag set.
The sentiment [] of the -th account during iteration consists of a vector containing an emotional polarity score, namely the percentage of the how positive, neutral, of negative the -th account feels towards the as shown in (5). Initially the ground truth vector of the -th account is the respective average percentage of positive, neutral, or negatively charged words in the tweets containing at least one hashtag from the reference set.
[] =△ [︀ , , ,
︀]
Given the iteration-dependent value of [], the value
of the correlation factor , should be computed
during each iteration as shown in (
=1 ∑︀3 =1 ︁( [] [] − 1/3︁) ∑︀3 ︁( [] [] − 1/3
︁)
︁( [] [] − 1/3
︁) 2
(5)
(
The weights of the linear combination in (4) encode the sign and relative strength of each factor contribution, namely how much each factor participates to the edge probability existence and whether such participation reinforces or weakens said probability respectively.
Moreover, they ensure the numerical stability of , .
Intuitively speaking, equation (4) is a linear estimator of the true edge existence probability. The weights , =△ 1 , , =△
1 1 + , , =△
1 1 + 2,
However, the weight selection of (
Another option for the weight function is that the inverse square function of equation (10). The latter typically expresses a potential function in various applications.
In figure 2 the weight functions of (
At the core of the proposed GNN architecture is the update mechanism of (11). For the -th vertex the [] is computed as in (11). Therein the index ranges over all inbound neighbors of the -th vertex and thus it depends on local connectivity patterns. However, since the state vector of its neighbors depends on recursively on that of its own vectors, this mechanism is essentially a higher order status computation. During an update it may be possible that certain neighbors may have already had their own state vectors updated, whereas others not.
Thus, the iteration indicator * will be used. This process terminates when the state vectors remain unchanged under a threshold of 0 for three consecutive iterations.
[+1] = ︃( 20 [− 1] + 20 ∑︁ ∆ , [* ]
)︃ of the respective factor. This means that is higher The hyperparameter 0 scales input to a practical dosince the follow denotes a high degree of coherency be- main for the sigmoid function (· ), , is the weight of tween the two accounts. Along a similar line of reason- the edge, and ∆ is the sum of the edge weights of the ining, frequent retweets between two accounts indicate a bound neighbors. In (11) the sigmoid function is defined somewhat strong connection between them. Moreover, as in (12) which is diferentiable and smooth everywhere. a consistent emotional coherency between two accounts may well suggest a behavioral link between them. (; 0) =△ 1 (12)
Additionally the weight , assigned to each edge is a 1 + exp (− 0) function of the strength of the corresponding edge.
The derivative of the sigmoid function is given in (13).
, =△ (, )
The weight function (· ) of (7) is the same for each
edge and it is directly or at least indirectly linked to
the semantics of the underlying graph. One of the most
common options is that shown in (
(7)
(
(13)
The last form of (13) comes from the fundamental property of the sigmoid function described in (14) below: (; 0) + (− ; 0) = 1
(14)
The preceding properties ensure that (· ) is smooth enough to prevent divergence in most cases for a broad spectrum of distributions.
The results of the proposed GNN methodology are presented in this section along with intuition about them. They are divided to four groups, one for each possible combination of benchmark graph (1821 / US2020) and weight function (inverse linear / inverse square).
The two benchmark graphs used in the experiments were taken from [5]. They represent two characteristic cases of social graphs, namely one with a relative quiet and coherent one (1821) and one containing heated conversations and a considerable degree of dissonance (US2020). The Twitter sampling interval was 8/2020-10/2020.
In table 3 the parameters used in the experimental setup of this work are shown. This allows for the easy exploration of the parameter space. Observe that the actual values of these parameters are in accordance of the strength of the respective factor.
Table 4 contains the normalized number of iterations
as a function of the hyperparameter 0 of (11) for the
two benchmark graphs of table 2 and for the two possible
weight functions shown in equations (
0 Weight functions vs edge probability 0.2 0.4 0.6 0.8
1
Edge probability GNN is run with the latter removed from the initial local case. There it can be seen that the US2020 yields for ground truth vectors at the vertices. both weight choices slightly diferent results from the
From table 4 it follows immediately that the inclusion initial distribution when the emotional factor is excluded of the behavioral factor in (4) leads to quicker conver- but considerably diferent ones when they are included. gence of the proposed GNN architecture. This can be Thus, it is a graph with a heavy emotional charge. On the attributed to the following reasons: other hand, the 1821 graph tends to yield similar results in every case, signifying thus greater coherency.
• Information enrichment: From an algorithmic perspective, the behavioral factor adds an independent dimension to the profile of each vertex.
Hence, the new vertex profile space can diferentiate adequately between dissimilar vertices while maintaining close enough similar ones. • Numerical variation: The above is enhanced by having more diversified edge weights. Besides the additional factor, the behavioral term is also signed. In turn this expands the range of weights, increasing thus the possible number of values.
This conference paper focuses on a graph neural network architecture for discovering community structure in large Twitter graphs. In this approach said structure is formed using a Twitter account behavioral model which results from fusing structural and functional attributes with emotional ones. The proposed model can be naturally extended to include additional features from these categories or even ones belonging to diferent categories
The above factors suggest that variability in the weight as long as they can be expressed in a numerical scale space as well as in the vertex profile increase the flexibil- where normalization does not influence semantics. In ity of the update mechanism of (11). This is in accordance our experiments the inclusion of behavioral attributes with the standard pattern recognition maxim stating that leads consistently to quicker GNN convergence. mapping data to a space of higher dimensionality facil- This work can be extended in a number of ways. First, itates their clustering. On the other hand, the curse of multiple weight functions can map each edge to a weight dimensionality imposes a limit on how big this new space vector and hence to a multidimensional weight space can get. As both spaces used in this work however are where each dimension has its own semantics. Then the low dimensional, this does not constitute a problem. fundamental parameters of candidate distributions de
Regarding the total sentiment, in table 5 is shown the scribing this space can be derived through signal estiaverage emotional distribution before and after the GNN mation techniques. Second, alternative behavioral modexecution in each case using the value of hyperparame- els depending only on local properties or on local estiter 0 which leads to the quickest convergence in each mates of global ones should be developed as this would be