With the rise of machine learning techniques, ensuring the fairness of decisions made by machine learning algorithms has become of great importance in critical applications. However, measuring fairness often requires full access to the model parameters, which compromises the confidentiality of the models. In this paper, we propose a solution using zero-knowledge proofs, which allows the model owner to convince the public that a machine learning model is fair while preserving the secrecy of the model. To circumvent the efficiency barrier of naively proving machine learning inferences in zero-knowledge, our key innovation is a new approach to measure fairness only with model parameters and some aggregated information of the input, but not on any specific dataset. To achieve this goal, we derive new bounds for the fairness of logistic regression and deep neural network models that are tighter and better reflecting the fairness compared to prior work. Moreover, we develop efficient zero-knowledge proof protocols for common computations involved in measuring fairness, including the spectral norm of matrices, maximum, absolute value, and fixed-point arithmetic. We have fully implemented our system, FairZK, that proves machine learning fairness in zero-knowledge. Experimental results show that Fairzk is significantly faster than the naive approach and an existing scheme that use zero-knowledge inferences as a subroutine. The prover time is improved by 3.1x-1789x depending on the size of the model and the dataset. FairZK can scale to a large model with 47 million parameters for the first time, and generates a proof for its fairness in 343 seconds. This is estimated to be 4 orders of magnitude faster than existing schemes, which only scale to small models with hundreds to thousands of parameters.

Machine learning over graphs has recently attracted growing attention due to its ability to analyze and learn complex relations within critical interconnected systems. However, the disparate impact that is amplified by the use of biased graph structures in these algorithms has raised significant concerns for their deployment in real-world decision systems. In addition, while synthetic graph generation has become pivotal for privacy and scalability considerations, the impact of generative learning algorithms on structural bias has not yet been investigated. Motivated by this, this work focuses on the analysis and mitigation of structural bias for both real and synthetic graphs. Specifically, we first theoretically analyze the sources of structural bias that result in disparity for the predictions of dyadic relations. To alleviate the identified bias factors, we design a novel fairness regularizer that offers a versatile use. Faced with the bias amplification in graph generation models brought to light in this work, we further propose a fair graph generation framework, FairWire, by leveraging our fair regularizer design in a generative model. Experimental results on real-world networks validate that the proposed tools herein deliver effective structural bias mitigation for both real and synthetic graphs.

Graphs can facilitate modeling various complex systems such as gene networks and power grids as well as analyzing the underlying relations within them. Learning over graphs has recently attracted increasing attention, particularly graph neural network (GNN)–based solutions, among which graph attention networks (GATs) have become one of the most widely utilized neural network structures for graph-based tasks. Although it is shown that the use of graph structures in learning results in the amplification of algorithmic bias, the influence of the attention design in GATs on algorithmic bias has not been investigated. Motivated by this, the present study first carries out a theoretical analysis in order to demonstrate the sources of algorithmic bias in GAT-based learning for node classification. Then, a novel algorithm, FairGAT, which leverages a fairness-aware attention design, is developed based on the theoretical findings. Experimental results on real-world networks demonstrate that FairGAT improves group fairness measures while also providing comparable utility to the fairness-aware baselines for node classification and link prediction.

Node representation learning has attracted increasing attention due to its efficacy for various applications on graphs. However, fairness is a largely under-explored territory within the field, although it is shown that the use of graph structure in learning amplifies bias. To this end, this work theoretically explains the sources of bias in node representations obtained via graph neural networks (GNNs). It is revealed that both nodal features and graph structure lead to bias in the obtained representations. Building upon the analysis, fairness-aware data augmentation frameworks are developed to reduce the intrinsic bias. Our theoretical analysis and proposed schemes can be readily employed in understanding and mitigating bias for various GNN-based learning mechanisms. Extensive experiments on node classification and link prediction over multiple real networks are carried out, and it is shown that the proposed augmentation strategies can improve fairness while providing comparable utility to state-of-the-art methods.

Many real-world networks such as social networks, traffic networks vary over time, which can be modeled as dynamic graphs. Despite the significant number of systems that can facilitate from the algorithmic tools over dynamic graphs, dynamic graph representation learning is an under-explored research area. Furthermore, while the fairness of algorithms is essential for their deployment in real-world systems, this issue has never been considered in the context of dynamic graphs to the best of our knowledge. Motivated by this, the present study proposes an efficient online node representation learning framework over dynamic graphs that can also mitigate bias. Specifically, the proposed technique combines different observations (graph structure and nodal attributes) of the same source (attributed graph) in a complementary way while also reducing the intrinsic bias in the learned representations. Experimental results on dynamic graphs show that the proposed online strategy can improve the group fairness measures for node classification together with comparable/better utility to the baselines.

Graph machine learning algorithms have become popular tools in helping us gain a deeper understanding of the ubiquitous graph data. Despite their effectiveness, most graph machine learning algorithms lack considerations for fairness, which can result in discriminatory outcomes against certain demographic subgroups or individuals. As a result, there is a growing societal concern about mitigating the bias exhibited in these algorithms. To tackle the problem of algorithmic bias in graph machine learning algorithms, this tutorial aims to provide a comprehensive overview of recent research progress in measuring and mitigating the bias in machine learning algorithms on graphs. Specifically, this tutorial first introduces several widely-used fairness notions and the corresponding metrics. Then, we present a well-organized review of the theoretical understanding of bias in graph machine learning algorithms, followed by a summary of existing techniques to debias graph machine learning algorithms. Furthermore, we demonstrate how different real-world applications benefit from these graph machine learning algorithms after debiasing. Finally, we provide insights on current research challenges and open questions to encourage further advances.

Selective sampling is an online learning framework where the learner tries to detect the data samples whose labels can boost the performance maximally, and only the labels of chosen data samples are queried. While the design of selective sampling algorithms is extensively studied for independent data samples, the area is rather under-explored in the context of graphs. Furthermore, the limited number of existing graph-based approaches do not take into consideration the nodal attributes that are available in attributed graphs. In this study, existing online learning and selective sampling algorithms are modified to be used with graphs that have nodal features. Additionally, the bias in the results of original algorithms is investigated, and a novel bias reduction strategy is proposed that can be embedded into the dimensionality reduction step without incurring a significant complexity cost. Experiments for node classification are carried out on real social networks to showcase the advantages of incorporating nodal features, as well as the fairness-enhancement framework.

Representations for data subunits can help with recent data accumulation by enabling efficient storage and retrieval systems. In this paper, we investigate the problem of representation generation for phone classification and cross-modal same-different word discrimination tasks. The benefits of utilizing multimodal data on these tasks are examined together with different data fusion schemes. Mainly, the paper considers two different data modalities, upper airway mid-sagittal plane real-time magnetic resonance imaging (rtMRI) videos and the corresponding speech waveforms, and experiments on USC-TIMIT rtMRI dataset. For the phone classification task, two unimodal neural networks are designed, and these separate systems are merged in two different ways that provide data fusion between two modalities. The proposed networks differ in their stages in which they perform the data fusion. As hypothesized, our results show that data fusion indeed brings a performance improvement over both unimodal approaches, and performing fusion in earlier stages with cross-connections yields better results than fusing the data in later stages. In addition to the proposed phone classification schemes, different unimodal and multimodal systems are designed to obtain phone recognition results on USC-TIMIT rtMRI dataset. Phone representations generated for the phone classification task are also utilized in the phone recognition task, and their representative power is illustrated. Finally, we define a cross-view same-different word discrimination task on USC-TIMIT. We propose two different schemes to tackle this task, and find that for cross-view same-different discrimination, generating representations with the help of cross-modality yields better accuracy than a system employing independently created representations.

In this paper, the use of word embeddings for the segments found in audio and real-time magnetic resonance imaging (rtMRI) videos is addressed. In this study, word embeddings are created to store and retrieve data efficiently, and their representation power of the original data is evaluated by the same-different word-discrimination task that is defined for both unimodal and cross-view settings. In order to create the word embeddings for two different data modalities independently for the unimodal setting, a Siamese neural network is designed. For the rtMRI videos, inputs to the network are generated through a correspondence autoencoder. In the cross-view setting, a recurrent neural network (RNN), which inputs data of different modalities, is trained to generate embeddings jointly for both data sources. The problem of objective function selection to the RNN is also investigated. The results on the USC-TIMIT rtMRI dataset outperform the conventional dynamic time warping (DTW) baseline by a clear margin. Outcomes demonstrate that the proposed word embeddings can be a step towards faster unimodal or cross-view queryby-example search tasks.